-// Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
+// 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.*;
* 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
private int usedslots = 0;
/** the number of entries with non-null values */
- private int size = 0;
+ protected int size = 0;
/** when num_slots < loadFactor * size, rehash into a bigger table */
private final int loadFactor;
}
/** returns all the primary keys in the table */
- public Object[] keys() {
- int howmany = 0;
- for(int i=0; i<vals.length; i++) if (keys1[i] != null) howmany++;
- Object[] ret = new Object[howmany];
- int where = 0;
- for(int i=0; i<vals.length; i++) if (keys1[i] != null) ret[where++] = keys1[i];
- return ret;
- }
+ public Enumeration keys() { return new HashEnum(); }
public Hash() { this(25, 3); }
public Hash(int initialcapacity, int loadFactor) {
}
public void remove(Object k1) { remove(k1, null); }
- public void remove(Object k1, Object k2) { put(k1, k2, null); }
+ public void remove(Object k1, Object k2) { put_(k1, k2, null); }
private void rehash() {
Object[] oldkeys1 = keys1;
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]);
+ put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
}
public Object get(Object k1) { return get(k1, null); }
}
public void put(Object k1, Object v) { put(k1, null, v); }
- public void put(Object k1, Object k2, Object 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;
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;
+ }
+ }
}