001: // Copyright (c) 2005 Per M.A. Bothner.
002: // This is free software; for terms and warranty disclaimer see COPYING.
003:
004: package gnu.kawa.util;
005:
006: /** A generic hash table.
007: * Supports deletions, and re-allocates the table when too big.
008: * The equivalence relation can be customized. */
009:
010: public class GeneralHashTable
011: // FUTURE: implements java.util.Map
012: {
013: protected HashNode[] table;
014: protected int mask;
015: protected int num_bindings;
016:
017: public GeneralHashTable() {
018: this (64);
019: }
020:
021: public GeneralHashTable(int capacity) {
022: int log2Size = 4;
023: while (capacity > (1 << log2Size))
024: log2Size++;
025: capacity = 1 << log2Size;
026: table = new HashNode[capacity];
027: mask = capacity - 1;
028: }
029:
030: /** Allocate a new node in the hash table. */
031: protected HashNode makeEntry(Object key, int hash, Object value) {
032: HashNode node = new HashNode();
033: node.key = key;
034: node.hash = hash;
035: node.value = value;
036: return node;
037: }
038:
039: /** Calculate hash code of a key.
040: * You may need to override this if you override the <code>matches</code> method.
041: */
042: public int hash(Object key) {
043: // FIXME
044: return key == null ? 0 : key.hashCode();
045: }
046:
047: public int hash(HashNode node) {
048: //return hash(node.getKey());
049: return node.hash;
050: }
051:
052: public boolean matches(Object key, int hash, HashNode node) {
053: return node.hash == hash && matches(node.getKey(), key);
054: }
055:
056: /** Compare two keys for equivalence.
057: * Override this and the {@link #hash(Object)} method if you want
058: * a different equivalence relation.
059: */
060: public boolean matches(Object value1, Object value2) {
061: // FIXME
062: return value1 == value2
063: || (value1 != null && value1.equals(value2));
064: }
065:
066: public Object get(Object key, Object defaultValue) {
067: int hash = hash(key);
068: int index = hash & this .mask;
069: for (HashNode node = table[index]; node != null; node = node.next) {
070: if (matches(key, hash, node))
071: return node.getValue();
072: }
073: return defaultValue;
074: }
075:
076: public HashNode getNode(Object key) {
077: int hash = hash(key);
078: int index = hash & this .mask;
079: for (HashNode node = table[index]; node != null; node = node.next) {
080: if (matches(key, hash, node))
081: return node;
082: }
083: return null;
084: }
085:
086: public Object put(Object key, Object value) {
087: return put(key, hash(key), value);
088: }
089:
090: public Object put(Object key, int hash, Object value) {
091: int index = hash & mask;
092: HashNode first = table[index];
093: HashNode node = first;
094: for (;;) {
095: if (node == null) {
096: if (++num_bindings >= table.length) {
097: rehash();
098: index = hash & mask;
099: first = table[index];
100: }
101: node = makeEntry(key, hash, value);
102: node.next = first;
103: table[index] = node;
104: return null;
105: } else if (matches(key, hash, node)) {
106: return node.setValue(value);
107: }
108: node = node.next;
109: }
110: }
111:
112: public Object remove(Object key) {
113: int hash = hash(key);
114: int index = hash & this .mask;
115: HashNode prev = null;
116: HashNode node = table[index];
117: while (node != null) {
118: HashNode next = node.next;
119: if (matches(key, hash, node)) {
120: if (prev == null)
121: table[index] = next;
122: else
123: prev.next = node;
124: num_bindings--;
125: return node.getValue();
126: }
127: prev = node;
128: node = next;
129: }
130: return null;
131: }
132:
133: protected void rehash() {
134: HashNode[] oldTable = table;
135: int oldCapacity = oldTable.length;
136: int newCapacity = 2 * oldCapacity;
137: HashNode[] newTable = new HashNode[newCapacity];
138: int newMask = newCapacity - 1;
139: for (int i = oldCapacity; --i >= 0;) {
140: HashNode chain = oldTable[i];
141: if (chain != null && chain.next != null) {
142: // Reverse the old chain in place, so that after re-hashing the
143: // new chain has the same order.. This is useful for some
144: // subclasses (specifically gnu.expr.NameLookup), and it is
145: // cheap to so here where extra cache misses are unlikely.
146: HashNode prev = null;
147: do {
148: HashNode node = chain;
149: chain = node.next;
150: node.next = prev;
151: prev = node;
152: } while (chain != null);
153: chain = prev;
154: }
155:
156: for (HashNode element = chain; element != null;) {
157: HashNode next = element.next;
158: int hash = hash(element);
159: int j = hash & newMask;
160: HashNode head = newTable[j];
161: element.next = head;
162: newTable[j] = element;
163: element = next;
164: }
165: }
166: table = newTable;
167: mask = newMask;
168: }
169:
170: public void clear() {
171: HashNode[] t = this .table;
172: for (int i = t.length; --i >= 0;)
173: t[i] = null;
174: num_bindings = 0;
175: }
176:
177: public int size() {
178: return num_bindings;
179: }
180:
181: protected static HashNode next(HashNode node) {
182: return node.next;
183: }
184: }
|