--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.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.ibex.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