+++ /dev/null
-// Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
-//
-// You may modify, copy, and redistribute this code under the terms of
-// the GNU Library Public License version 2.1, with the exception of
-// the portion of clause 6a after the semicolon (aka the "obnoxious
-// relink clause")
-
-package org.xwt.util;
-
-import java.util.*;
-
-/** Implementation of an unsynchronized hash table, with one or two
- * keys, using Radke's quadradic residue linear probing instead of
- * buckets to minimize object count (less allocations, faster GC).
- * See C. Radke, Communications of the ACM, 1970, 103-105
- *
- * Not threadsafe.
- */
-public class Hash {
- /** this object is inserted as key in a slot when the
- * corresponding value is removed -- this ensures that the
- * probing sequence for any given key remains the same even if
- * other keys are removed.
- */
- private static Object placeholder = new Object();
-
- /** the number of entries with at least one non-null key */
- private int usedslots = 0;
-
- /** the number of entries with non-null values */
- protected int size = 0;
-
- /** when num_slots < loadFactor * size, rehash into a bigger table */
- private final int loadFactor;
-
- /** primary keys */
- private Object[] keys1 = null;
-
- /** secondary keys; null if no secondary key has ever been added */
- private Object[] keys2 = null;
-
- /** the values for the table */
- private Object[] vals = null;
-
- /** the number of entries with a non-null value */
- public int size() { return size; }
-
- /** empties the table */
- public void clear() {
- size = 0;
- usedslots = 0;
- for(int i=0; i<vals.length; i++) {
- vals[i] = null;
- keys1[i] = null;
- if (keys2 != null) keys2[i] = null;
- }
- }
-
- /** returns all the primary keys in the table */
- public Enumeration keys() { return new HashEnum(); }
-
- public Hash() { this(25, 3); }
- public Hash(int initialcapacity, int loadFactor) {
- // using a pseudoprime in the form 4x+3 ensures full coverage
- initialcapacity = initialcapacity / 4;
- initialcapacity = 4 * initialcapacity + 3;
- keys1 = new Object[initialcapacity];
- vals = new Object[initialcapacity];
- this.loadFactor = loadFactor;
- }
-
- public void remove(Object k1) { remove(k1, null); }
- public void remove(Object k1, Object k2) { put_(k1, k2, null); }
-
- private void rehash() {
- Object[] oldkeys1 = keys1;
- Object[] oldkeys2 = keys2;
- Object[] oldvals = vals;
- keys1 = new Object[oldvals.length * 2];
- keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
- vals = new Object[oldvals.length * 2];
- size = 0;
- usedslots = 0;
- for(int i=0; i<oldvals.length; i++)
- if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
- put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
- }
-
- public Object get(Object k1) { return get(k1, null); }
- public Object get(Object k1, Object k2) {
- if (k2 != null && keys2 == null) return null;
- int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
- int dest = Math.abs(hash) % vals.length;
- int odest = dest;
- int tries = 1;
- boolean plus = true;
- while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
- Object hk1 = keys1[dest];
- Object hk2 = keys2 == null ? null : keys2[dest];
- if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
- (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
- return vals[dest];
- }
- dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
- if (plus) tries++;
- plus = !plus;
- }
- return null;
- }
-
- public void put(Object k1, Object v) { put(k1, null, v); }
- public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
- private void put_(Object k1, Object k2, Object v) {
- if (usedslots * loadFactor > vals.length) rehash();
- int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
- int dest = Math.abs(hash) % vals.length;
- int odest = dest;
- boolean plus = true;
- int tries = 1;
- while (true) {
- Object hk1 = keys1[dest];
- Object hk2 = keys2 == null ? null : keys2[dest];
- if (hk1 == null && hk2 == null) { // empty slot
- if (v == null) return;
- size++;
- usedslots++;
- break;
- }
-
- if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) && // replacing former entry
- (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
-
- // we don't actually remove things from the table; rather, we insert a placeholder
- if (v == null) {
- k1 = placeholder;
- k2 = null;
- size--;
- }
- break;
- }
-
- dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
- if (plus) tries++;
- plus = !plus;
- }
-
- keys1[dest] = k1;
- if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
- if (keys2 != null) keys2[dest] = k2;
- vals[dest] = v;
- }
-
- private class HashEnum implements java.util.Enumeration {
- private int iterator = 0;
- private int found = 0;
-
- public HashEnum () { }
-
- public boolean hasMoreElements() {
- return found < usedslots;
- }
-
- public Object nextElement() {
- if (!hasMoreElements()) throw new java.util.NoSuchElementException();
-
- Object o = null;
- while (o == null) o = keys1[iterator++];
- if (o == null) throw new IllegalStateException("Didn't find an element, when I should have.");
- found++;
-
- return o;
- }
- }
-}
-
-
projects / org.ibex.core.git / blobdiff