001: /*
002: * HashTable.java
003: *
004: * Copyright (C) 2002-2004 Peter Graves
005: * $Id: HashTable.java,v 1.38 2004/09/20 17:43:58 piso Exp $
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * as published by the Free Software Foundation; either version 2
010: * of the License, or (at your option) any later version.
011: *
012: * This program is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
015: * GNU General Public License for more details.
016: *
017: * You should have received a copy of the GNU General Public License
018: * along with this program; if not, write to the Free Software
019: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
020: */
021:
022: package org.armedbear.lisp;
023:
024: public abstract class HashTable extends LispObject {
025: protected static final int TEST_EQ = 0;
026: protected static final int TEST_EQL = 1;
027: protected static final int TEST_EQUAL = 2;
028: protected static final int TEST_EQUALP = 3;
029:
030: private int test;
031:
032: protected final LispObject rehashSize;
033: protected final LispObject rehashThreshold;
034:
035: // The rounded product of the capacity and the load factor. When the number
036: // of elements exceeds the threshold, the implementation calls rehash().
037: protected int threshold;
038:
039: private final float loadFactor = 0.75f;
040:
041: // Array containing the actual key-value mappings.
042: protected HashEntry[] buckets;
043:
044: // The number of key-value pairs.
045: private int count;
046:
047: protected HashTable(int test, int size, LispObject rehashSize,
048: LispObject rehashThreshold) {
049: this .test = test;
050: this .rehashSize = rehashSize;
051: this .rehashThreshold = rehashThreshold;
052: buckets = new HashEntry[size];
053: threshold = (int) (size * loadFactor);
054: }
055:
056: private int getCount() {
057: return count;
058: }
059:
060: public LispObject typeOf() {
061: return Symbol.HASH_TABLE;
062: }
063:
064: public LispClass classOf() {
065: return BuiltInClass.HASH_TABLE;
066: }
067:
068: public LispObject typep(LispObject type) throws ConditionThrowable {
069: if (type == Symbol.HASH_TABLE)
070: return T;
071: if (type == BuiltInClass.HASH_TABLE)
072: return T;
073: return super .typep(type);
074: }
075:
076: public boolean equalp(LispObject obj) throws ConditionThrowable {
077: if (this == obj)
078: return true;
079: if (obj instanceof HashTable) {
080: HashTable ht = (HashTable) obj;
081: if (count != ht.count)
082: return false;
083: if (test != ht.test)
084: return false;
085: LispObject entries = ENTRIES();
086: while (entries != NIL) {
087: LispObject entry = entries.car();
088: LispObject key = entry.car();
089: LispObject value = entry.cdr();
090: if (!value.equalp(ht.get(key)))
091: return false;
092: entries = entries.cdr();
093: }
094: return true;
095: }
096: return false;
097: }
098:
099: public synchronized void clear() {
100: for (int i = buckets.length; i-- > 0;)
101: buckets[i] = null;
102: count = 0;
103: }
104:
105: // gethash key hash-table &optional default => value, present-p
106: public synchronized LispObject gethash(LispObject key,
107: LispObject defaultValue) throws ConditionThrowable {
108: LispObject value = (LispObject) get(key);
109: final LispObject presentp;
110: if (value == null) {
111: value = defaultValue;
112: presentp = NIL;
113: } else
114: presentp = T;
115: return LispThread.currentThread().setValues(value, presentp);
116: }
117:
118: public synchronized LispObject puthash(LispObject key,
119: LispObject newValue) throws ConditionThrowable {
120: put(key, newValue);
121: return newValue;
122: }
123:
124: // remhash key hash-table => generalized-boolean
125: public synchronized LispObject remhash(LispObject key)
126: throws ConditionThrowable {
127: // A value in a Lisp hash table can never be null, so...
128: return remove(key) != null ? T : NIL;
129: }
130:
131: public String writeToString() {
132: StringBuffer sb = new StringBuffer("#<");
133: switch (test) {
134: case TEST_EQ:
135: sb.append("EQ");
136: break;
137: case TEST_EQL:
138: sb.append("EQL");
139: break;
140: case TEST_EQUAL:
141: sb.append("EQUAL");
142: break;
143: case TEST_EQUALP:
144: sb.append("EQUALP");
145: break;
146: default:
147: Debug.bug();
148: }
149: sb.append(" hash table, ");
150: sb.append(count);
151: if (count == 1)
152: sb.append(" entry>");
153: else
154: sb.append(" entries>");
155: return sb.toString();
156: }
157:
158: public LispObject get(LispObject key) throws ConditionThrowable {
159: int idx = hash(key);
160: HashEntry e = buckets[idx];
161: while (e != null) {
162: if (equals(key, e.key))
163: return e.value;
164: e = e.next;
165: }
166: return null;
167: }
168:
169: public void put(LispObject key, LispObject value)
170: throws ConditionThrowable {
171: int idx = hash(key);
172: HashEntry e = buckets[idx];
173: while (e != null) {
174: if (equals(key, e.key)) {
175: e.value = value;
176: return;
177: }
178: e = e.next;
179: }
180: // Not found. We need to add a new entry.
181: if (++count > threshold) {
182: rehash();
183: // Need a new hash value to suit the bigger table.
184: idx = hash(key);
185: }
186: e = new HashEntry(key, value);
187: e.next = buckets[idx];
188: buckets[idx] = e;
189: }
190:
191: public LispObject remove(LispObject key) throws ConditionThrowable {
192: int idx = hash(key);
193: HashEntry e = buckets[idx];
194: HashEntry last = null;
195: while (e != null) {
196: if (equals(key, e.key)) {
197: if (last == null)
198: buckets[idx] = e.next;
199: else
200: last.next = e.next;
201: --count;
202: return e.value;
203: }
204: last = e;
205: e = e.next;
206: }
207: return null;
208: }
209:
210: protected int hash(LispObject key) throws ConditionThrowable {
211: return (key.sxhash() % buckets.length);
212: }
213:
214: protected abstract boolean equals(LispObject o1, LispObject o2)
215: throws ConditionThrowable;
216:
217: private void rehash() throws ConditionThrowable {
218: HashEntry[] oldBuckets = buckets;
219: int newCapacity = buckets.length * 2 + 1;
220: threshold = (int) (newCapacity * loadFactor);
221: buckets = new HashEntry[newCapacity];
222: for (int i = oldBuckets.length; i-- > 0;) {
223: HashEntry e = oldBuckets[i];
224: while (e != null) {
225: int idx = hash(e.key);
226: HashEntry dest = buckets[idx];
227: if (dest != null) {
228: while (dest.next != null)
229: dest = dest.next;
230: dest.next = e;
231: } else
232: buckets[idx] = e;
233: HashEntry next = e.next;
234: e.next = null;
235: e = next;
236: }
237: }
238: }
239:
240: // Returns a list of (key . value) pairs.
241: private LispObject ENTRIES() {
242: LispObject list = NIL;
243: for (int i = buckets.length; i-- > 0;) {
244: HashEntry e = buckets[i];
245: while (e != null) {
246: list = new Cons(new Cons(e.key, e.value), list);
247: e = e.next;
248: }
249: }
250: return list;
251: }
252:
253: protected static class HashEntry {
254: LispObject key;
255: LispObject value;
256: HashEntry next;
257:
258: HashEntry(LispObject key, LispObject value) {
259: this .key = key;
260: this .value = value;
261: }
262: }
263:
264: private static final LispObject FUNCTION_EQ = Symbol.EQ
265: .getSymbolFunction();
266: private static final LispObject FUNCTION_EQL = Symbol.EQL
267: .getSymbolFunction();
268: private static final LispObject FUNCTION_EQUAL = Symbol.EQUAL
269: .getSymbolFunction();
270: private static final LispObject FUNCTION_EQUALP = Symbol.EQUALP
271: .getSymbolFunction();
272:
273: // ### %make-hash-table
274: private static final Primitive4 _MAKE_HASH_TABLE = new Primitive4(
275: "%make-hash-table", PACKAGE_SYS, false) {
276: public LispObject execute(LispObject test, LispObject size,
277: LispObject rehashSize, LispObject rehashThreshold)
278: throws ConditionThrowable {
279: int n;
280: try {
281: n = ((Fixnum) size).value;
282: } catch (ClassCastException e) {
283: return signal(new TypeError(size, Symbol.FIXNUM));
284: }
285: if (test == FUNCTION_EQL || test == NIL)
286: return new EqlHashTable(n, rehashSize, rehashThreshold);
287: if (test == FUNCTION_EQ)
288: return new EqHashTable(n, rehashSize, rehashThreshold);
289: if (test == FUNCTION_EQUAL)
290: return new EqualHashTable(n, rehashSize,
291: rehashThreshold);
292: if (test == FUNCTION_EQUALP)
293: return new EqualpHashTable(n, rehashSize,
294: rehashThreshold);
295: return signal(new LispError(
296: "Unknown test for MAKE-HASH-TABLE: "
297: + test.writeToString()));
298: }
299: };
300:
301: // ### gethash
302: // gethash key hash-table &optional default => value, present-p
303: private static final Primitive GETHASH = new Primitive("gethash",
304: "key hash-table &optional default") {
305: public LispObject execute(LispObject first, LispObject second)
306: throws ConditionThrowable {
307: try {
308: return ((HashTable) second).gethash(first, NIL);
309: } catch (ClassCastException e) {
310: return signal(new TypeError(second, Symbol.HASH_TABLE));
311: }
312: }
313:
314: public LispObject execute(LispObject first, LispObject second,
315: LispObject third) throws ConditionThrowable {
316: try {
317: return ((HashTable) second).gethash(first, third);
318: } catch (ClassCastException e) {
319: return signal(new TypeError(second, Symbol.HASH_TABLE));
320: }
321: }
322: };
323:
324: // ### puthash
325: // puthash key hash-table default &optional (value default) => value
326: private static final Primitive PUTHASH = new Primitive("puthash",
327: PACKAGE_SYS, false) {
328: public LispObject execute(LispObject[] args)
329: throws ConditionThrowable {
330: final int length = args.length;
331: if (length < 3 || length > 4)
332: return signal(new WrongNumberOfArgumentsException(this ));
333: if (args[1] instanceof HashTable) {
334: LispObject key = args[0];
335: HashTable ht = (HashTable) args[1];
336: LispObject value;
337: if (length == 3)
338: value = args[2];
339: else {
340: Debug.assertTrue(length == 4);
341: value = args[3];
342: }
343: return ht.puthash(key, value);
344: }
345: return signal(new TypeError(args[1], "hash-table"));
346: }
347: };
348:
349: // remhash key hash-table => generalized-boolean
350: private static final Primitive2 REMHASH = new Primitive2("remhash",
351: "key hash-table") {
352: public LispObject execute(LispObject first, LispObject second)
353: throws ConditionThrowable {
354: if (second instanceof HashTable) {
355: LispObject key = first;
356: HashTable ht = (HashTable) second;
357: return ht.remhash(key);
358: }
359: return signal(new TypeError(second, "hash-table"));
360: }
361: };
362:
363: // ### clrhash
364: // clrhash hash-table => hash-table
365: private static final Primitive1 CLRHASH = new Primitive1("clrhash",
366: "hash-table") {
367: public LispObject execute(LispObject arg)
368: throws ConditionThrowable {
369: if (arg instanceof HashTable) {
370: ((HashTable) arg).clear();
371: return arg;
372: }
373: return signal(new TypeError(arg, "hash-table"));
374: }
375: };
376:
377: // ### hash-table-count
378: private static final Primitive1 HASH_TABLE_COUNT = new Primitive1(
379: "hash-table-count", "hash-table") {
380: public LispObject execute(LispObject arg)
381: throws ConditionThrowable {
382: if (arg instanceof HashTable)
383: return new Fixnum(((HashTable) arg).getCount());
384: return signal(new TypeError(arg, "hash-table"));
385: }
386: };
387:
388: // ### sxhash
389: // sxhash object => hash-code
390: private static final Primitive1 SXHASH = new Primitive1("sxhash",
391: "object") {
392: public LispObject execute(LispObject arg)
393: throws ConditionThrowable {
394: return new Fixnum(arg.sxhash());
395: }
396: };
397:
398: // ### psxhash
399: // psxhash object => hash-code
400: // For EQUALP hash tables.
401: private static final Primitive1 PSXHASH = new Primitive1("psxhash",
402: PACKAGE_SYS, false, "object") {
403: public LispObject execute(LispObject arg)
404: throws ConditionThrowable {
405: return new Fixnum(arg.psxhash());
406: }
407: };
408:
409: private static final Primitive2 MIX = new Primitive2("mix",
410: PACKAGE_SYS, false, "x y") {
411: public LispObject execute(LispObject first, LispObject second)
412: throws ConditionThrowable {
413: return number(mix(Fixnum.getValue(first), Fixnum
414: .getValue(second)));
415: }
416: };
417:
418: // ### hash-table-p
419: private static final Primitive1 HASH_TABLE_P = new Primitive1(
420: "hash-table-p", "object") {
421: public LispObject execute(LispObject arg)
422: throws ConditionThrowable {
423: return arg instanceof HashTable ? T : NIL;
424: }
425: };
426:
427: // ### hash-table-entries
428: private static final Primitive1 HASH_TABLE_ENTRIES = new Primitive1(
429: "hash-table-entries", PACKAGE_SYS, false) {
430: public LispObject execute(LispObject arg)
431: throws ConditionThrowable {
432: if (arg instanceof HashTable)
433: return ((HashTable) arg).ENTRIES();
434: return signal(new TypeError(arg, Symbol.HASH_TABLE));
435: }
436: };
437:
438: private static final Primitive1 HASH_TABLE_TEST = new Primitive1(
439: "hash-table-test", "hash-table") {
440: public LispObject execute(LispObject arg)
441: throws ConditionThrowable {
442: if (arg instanceof HashTable) {
443: switch (((HashTable) arg).test) {
444: case TEST_EQ:
445: return Symbol.EQ;
446: case TEST_EQL:
447: return Symbol.EQL;
448: case TEST_EQUAL:
449: return Symbol.EQUAL;
450: case TEST_EQUALP:
451: return Symbol.EQUALP;
452: default:
453: Debug.assertTrue(false);
454: return NIL;
455: }
456: }
457: return signal(new TypeError(arg, Symbol.HASH_TABLE));
458: }
459: };
460:
461: private static final Primitive1 HASH_TABLE_SIZE = new Primitive1(
462: "hash-table-size", "hash-table") {
463: public LispObject execute(LispObject arg)
464: throws ConditionThrowable {
465: if (arg instanceof HashTable)
466: return new Fixnum(((HashTable) arg).buckets.length);
467: return signal(new TypeError(arg, Symbol.HASH_TABLE));
468: }
469: };
470:
471: private static final Primitive1 HASH_TABLE_REHASH_SIZE = new Primitive1(
472: "hash-table-rehash-size", "hash-table") {
473: public LispObject execute(LispObject arg)
474: throws ConditionThrowable {
475: if (arg instanceof HashTable)
476: return ((HashTable) arg).rehashSize;
477: return signal(new TypeError(arg, Symbol.HASH_TABLE));
478: }
479: };
480:
481: private static final Primitive1 HASH_TABLE_REHASH_THRESHOLD = new Primitive1(
482: "hash-table-rehash-threshold", "hash-table") {
483: public LispObject execute(LispObject arg)
484: throws ConditionThrowable {
485: if (arg instanceof HashTable)
486: return ((HashTable) arg).rehashThreshold;
487: return signal(new TypeError(arg, Symbol.HASH_TABLE));
488: }
489: };
490: }
|