001: /*
002: * HashTable.java
003: *
004: * Copyright (C) 2002-2003 Peter Graves
005: * $Id: HashTable.java,v 1.6 2003/11/15 11:03:31 beedlem 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 final class HashTable extends LispObject {
025: private static final int TEST_EQ = 0;
026: private static final int TEST_EQL = 1;
027: private static final int TEST_EQUAL = 2;
028: private static final int TEST_EQUALP = 3;
029:
030: private int test;
031:
032: // The rounded product of the capacity and the load factor. When the number
033: // of elements exceeds the threshold, the implementation calls rehash().
034: private int threshold;
035:
036: private final float loadFactor = 0.75f;
037:
038: // Array containing the actual key-value mappings.
039: private HashEntry[] buckets;
040:
041: // The number of key-value pairs.
042: private int count;
043:
044: private HashTable(LispObject test, int size, LispObject rehashSize,
045: LispObject rehashThreshold) throws ConditionThrowable {
046: if (test == NIL || test == Symbol.EQ.getSymbolFunction())
047: this .test = TEST_EQ;
048: else if (test == Symbol.EQL.getSymbolFunction())
049: this .test = TEST_EQL;
050: else if (test == Symbol.EQUAL.getSymbolFunction())
051: this .test = TEST_EQUAL;
052: else if (test == Symbol.EQUALP.getSymbolFunction())
053: this .test = TEST_EQUALP;
054: else
055: throw new ConditionThrowable(new LispError(
056: "MAKE-HASH-TABLE: test " + test));
057: // Ignore rehashSize and rehashThreshold.
058: buckets = new HashEntry[size];
059: threshold = (int) (size * loadFactor);
060: }
061:
062: private int getCount() {
063: return count;
064: }
065:
066: public LispObject typeOf() {
067: return Symbol.HASH_TABLE;
068: }
069:
070: public LispClass classOf() {
071: return BuiltInClass.HASH_TABLE;
072: }
073:
074: public LispObject typep(LispObject type) throws ConditionThrowable {
075: if (type == Symbol.HASH_TABLE)
076: return T;
077: if (type == BuiltInClass.HASH_TABLE)
078: return T;
079: return super .typep(type);
080: }
081:
082: public synchronized void clear() {
083: for (int i = buckets.length; i-- > 0;)
084: buckets[i] = null;
085: count = 0;
086: }
087:
088: // gethash key hash-table &optional default => value, present-p
089: public synchronized LispObject gethash(LispObject key,
090: LispObject defaultValue) throws ConditionThrowable {
091: LispObject[] values = new LispObject[2];
092: LispObject value = (LispObject) get(key);
093: if (value == null) {
094: value = defaultValue;
095: values[1] = NIL;
096: } else
097: values[1] = T;
098: values[0] = value;
099: LispThread.currentThread().setValues(values);
100: return value;
101: }
102:
103: public synchronized LispObject puthash(LispObject key,
104: LispObject newValue) throws ConditionThrowable {
105: put(key, newValue);
106: return newValue;
107: }
108:
109: // remhash key hash-table => generalized-boolean
110: public synchronized LispObject remhash(LispObject key)
111: throws ConditionThrowable {
112: // A value in a Lisp hash table can never be null, so...
113: return remove(key) != null ? T : NIL;
114: }
115:
116: public String toString() {
117: StringBuffer sb = new StringBuffer("#<");
118: switch (test) {
119: case TEST_EQ:
120: sb.append("EQ");
121: break;
122: case TEST_EQL:
123: sb.append("EQL");
124: break;
125: case TEST_EQUAL:
126: sb.append("EQUAL");
127: break;
128: case TEST_EQUALP:
129: sb.append("EQUALP");
130: break;
131: default:
132: Debug.bug();
133: }
134: sb.append(" hash table, ");
135: sb.append(count);
136: if (count == 1)
137: sb.append(" entry>");
138: else
139: sb.append(" entries>");
140: return sb.toString();
141: }
142:
143: public LispObject get(LispObject key) throws ConditionThrowable {
144: int idx = hash(key);
145: HashEntry e = buckets[idx];
146: while (e != null) {
147: if (equals(key, e.key))
148: return e.value;
149: e = e.next;
150: }
151: return null;
152: }
153:
154: public LispObject put(LispObject key, LispObject value)
155: throws ConditionThrowable {
156: int idx = hash(key);
157: HashEntry e = buckets[idx];
158: while (e != null) {
159: if (equals(key, e.key)) {
160: LispObject r = e.value;
161: e.value = value;
162: return r;
163: } else
164: e = e.next;
165: }
166: // Not found. We need to add a new entry.
167: if (++count > threshold) {
168: rehash();
169: // Need a new hash value to suit the bigger table.
170: idx = hash(key);
171: }
172: e = new HashEntry(key, value);
173: e.next = buckets[idx];
174: buckets[idx] = e;
175: return null;
176: }
177:
178: public LispObject remove(LispObject key) throws ConditionThrowable {
179: int idx = hash(key);
180: HashEntry e = buckets[idx];
181: HashEntry last = null;
182: while (e != null) {
183: if (equals(key, e.key)) {
184: if (last == null)
185: buckets[idx] = e.next;
186: else
187: last.next = e.next;
188: --count;
189: return e.value;
190: }
191: last = e;
192: e = e.next;
193: }
194: return null;
195: }
196:
197: final int hash(LispObject key) {
198: return key == null ? 0 : Math.abs(key.hashCode()
199: % buckets.length);
200: }
201:
202: private final boolean equals(LispObject o1, LispObject o2)
203: throws ConditionThrowable {
204: switch (test) {
205: case TEST_EQ:
206: return o1 == o2;
207: case TEST_EQL:
208: return o1.eql(o2);
209: case TEST_EQUAL:
210: return o1.equal(o2);
211: case TEST_EQUALP:
212: return o1.equalp(o2);
213: default:
214: Debug.bug();
215: return false;
216: }
217: }
218:
219: private static final int hashCode(LispObject o) {
220: return o == null ? 0 : o.hashCode();
221: }
222:
223: private void rehash() {
224: HashEntry[] oldBuckets = buckets;
225: int newCapacity = buckets.length * 2 + 1;
226: threshold = (int) (newCapacity * loadFactor);
227: buckets = new HashEntry[newCapacity];
228: for (int i = oldBuckets.length; i-- > 0;) {
229: HashEntry e = oldBuckets[i];
230: while (e != null) {
231: int idx = hash(e.key);
232: HashEntry dest = buckets[idx];
233: if (dest != null) {
234: while (dest.next != null)
235: dest = dest.next;
236: dest.next = e;
237: } else
238: buckets[idx] = e;
239: HashEntry next = e.next;
240: e.next = null;
241: e = next;
242: }
243: }
244: }
245:
246: // Returns a list of (key . value) pairs.
247: private LispObject ENTRIES() {
248: LispObject list = NIL;
249: for (int i = buckets.length; i-- > 0;) {
250: HashEntry e = buckets[i];
251: while (e != null) {
252: list = new Cons(new Cons(e.key, e.value), list);
253: e = e.next;
254: }
255: }
256: return list;
257: }
258:
259: private static class HashEntry {
260: LispObject key;
261: LispObject value;
262: HashEntry next;
263:
264: HashEntry(LispObject key, LispObject value) {
265: this .key = key;
266: this .value = value;
267: }
268: }
269:
270: // ### %make-hash-table
271: private static final Primitive _MAKE_HASH_TABLE = new Primitive(
272: "%make-hash-table", PACKAGE_SYS, false) {
273: public LispObject execute(LispObject[] args)
274: throws ConditionThrowable {
275: if (args.length != 4)
276: throw new ConditionThrowable(
277: new WrongNumberOfArgumentsException(this ));
278: LispObject test = args[0];
279: int size = Fixnum.getValue(args[1]);
280: LispObject rehashSize = args[2];
281: LispObject rehashThreshold = args[3];
282: return new HashTable(test, size, rehashSize,
283: rehashThreshold);
284: }
285: };
286:
287: // ### gethash
288: // gethash key hash-table &optional default => value, present-p
289: private static final Primitive GETHASH = new Primitive("gethash") {
290: public LispObject execute(LispObject[] args)
291: throws ConditionThrowable {
292: final int length = args.length;
293: if (length < 2 || length > 3)
294: throw new ConditionThrowable(
295: new WrongNumberOfArgumentsException(this ));
296: if (args[1] instanceof HashTable) {
297: LispObject key = args[0];
298: HashTable ht = (HashTable) args[1];
299: LispObject defaultValue = length == 3 ? args[2] : NIL;
300: return ht.gethash(key, defaultValue);
301: }
302: throw new ConditionThrowable(new TypeError(args[1],
303: "hash-table"));
304: }
305: };
306:
307: // ### puthash
308: // puthash key hash-table default &optional (value default) => value
309: private static final Primitive PUTHASH = new Primitive("puthash",
310: PACKAGE_SYS, false) {
311: public LispObject execute(LispObject[] args)
312: throws ConditionThrowable {
313: final int length = args.length;
314: if (length < 3 || length > 4)
315: throw new ConditionThrowable(
316: new WrongNumberOfArgumentsException(this ));
317: if (args[1] instanceof HashTable) {
318: LispObject key = args[0];
319: HashTable ht = (HashTable) args[1];
320: LispObject value;
321: if (length == 3)
322: value = args[2];
323: else {
324: Debug.assertTrue(length == 4);
325: value = args[3];
326: }
327: return ht.puthash(key, value);
328: }
329: throw new ConditionThrowable(new TypeError(args[1],
330: "hash-table"));
331: }
332: };
333:
334: // remhash key hash-table => generalized-boolean
335: private static final Primitive2 REMHASH = new Primitive2("remhash") {
336: public LispObject execute(LispObject first, LispObject second)
337: throws ConditionThrowable {
338: if (second instanceof HashTable) {
339: LispObject key = first;
340: HashTable ht = (HashTable) second;
341: return ht.remhash(key);
342: }
343: throw new ConditionThrowable(new TypeError(second,
344: "hash-table"));
345: }
346: };
347:
348: // ### clrhash
349: // clrhash hash-table => hash-table
350: private static final Primitive1 CLRHASH = new Primitive1("clrhash") {
351: public LispObject execute(LispObject arg)
352: throws ConditionThrowable {
353: if (arg instanceof HashTable) {
354: ((HashTable) arg).clear();
355: return arg;
356: }
357: throw new ConditionThrowable(new TypeError(arg,
358: "hash-table"));
359: }
360: };
361:
362: // ### hash-table-count
363: private static final Primitive1 HASH_TABLE_COUNT = new Primitive1(
364: "hash-table-count") {
365: public LispObject execute(LispObject arg)
366: throws ConditionThrowable {
367: if (arg instanceof HashTable)
368: return new Fixnum(((HashTable) arg).getCount());
369: throw new ConditionThrowable(new TypeError(arg,
370: "hash-table"));
371: }
372: };
373:
374: // ### sxhash
375: // sxhash object => hash-code
376: private static final Primitive1 SXHASH = new Primitive1("sxhash") {
377: public LispObject execute(LispObject arg)
378: throws ConditionThrowable {
379: return new Fixnum(arg.hashCode());
380: }
381: };
382:
383: // ### hash-table-p
384: private static final Primitive1 HASH_TABLE_P = new Primitive1(
385: "hash-table-p") {
386: public LispObject execute(LispObject arg)
387: throws ConditionThrowable {
388: return arg instanceof HashTable ? T : NIL;
389: }
390: };
391:
392: // ### hash-table-entries
393: private static final Primitive1 HASH_TABLE_ENTRIES = new Primitive1(
394: "hash-table-entries", PACKAGE_SYS, false) {
395: public LispObject execute(LispObject arg)
396: throws ConditionThrowable {
397: if (arg instanceof HashTable)
398: return ((HashTable) arg).ENTRIES();
399: throw new ConditionThrowable(new TypeError(arg,
400: "hash-table"));
401: }
402: };
403: }
|