|
1
21
22 package org.armedbear.lisp;
23
24 public abstract class HashTable extends LispObject
25 {
26 protected static final int TEST_EQ = 0;
27 protected static final int TEST_EQL = 1;
28 protected static final int TEST_EQUAL = 2;
29 protected static final int TEST_EQUALP = 3;
30
31 private int test;
32
33 protected final LispObject rehashSize;
34 protected final LispObject rehashThreshold;
35
36 protected int threshold;
39
40 private final float loadFactor = 0.75f;
41
42 protected HashEntry[] buckets;
44
45 private int count;
47
48 protected HashTable(int test, int size, LispObject rehashSize,
49 LispObject rehashThreshold)
50 {
51 this.test = test;
52 this.rehashSize = rehashSize;
53 this.rehashThreshold = rehashThreshold;
54 buckets = new HashEntry[size];
55 threshold = (int) (size * loadFactor);
56 }
57
58 private int getCount()
59 {
60 return count;
61 }
62
63 public LispObject typeOf()
64 {
65 return Symbol.HASH_TABLE;
66 }
67
68 public LispClass classOf()
69 {
70 return BuiltInClass.HASH_TABLE;
71 }
72
73 public LispObject typep(LispObject type) throws ConditionThrowable
74 {
75 if (type == Symbol.HASH_TABLE)
76 return T;
77 if (type == BuiltInClass.HASH_TABLE)
78 return T;
79 return super.typep(type);
80 }
81
82 public boolean equalp(LispObject obj) throws ConditionThrowable
83 {
84 if (this == obj)
85 return true;
86 if (obj instanceof HashTable) {
87 HashTable ht = (HashTable) obj;
88 if (count != ht.count)
89 return false;
90 if (test != ht.test)
91 return false;
92 LispObject entries = ENTRIES();
93 while (entries != NIL) {
94 LispObject entry = entries.car();
95 LispObject key = entry.car();
96 LispObject value = entry.cdr();
97 if (!value.equalp(ht.get(key)))
98 return false;
99 entries = entries.cdr();
100 }
101 return true;
102 }
103 return false;
104 }
105
106 public synchronized void clear()
107 {
108 for (int i = buckets.length; i-- > 0;)
109 buckets[i] = null;
110 count = 0;
111 }
112
113 public synchronized LispObject gethash(LispObject key,
115 LispObject defaultValue)
116 throws ConditionThrowable
117 {
118 LispObject value = (LispObject) get(key);
119 final LispObject presentp;
120 if (value == null) {
121 value = defaultValue;
122 presentp = NIL;
123 } else
124 presentp = T;
125 return LispThread.currentThread().setValues(value, presentp);
126 }
127
128 public synchronized LispObject puthash(LispObject key, LispObject newValue)
129 throws ConditionThrowable
130 {
131 put(key, newValue);
132 return newValue;
133 }
134
135 public synchronized LispObject remhash(LispObject key) throws ConditionThrowable
137 {
138 return remove(key) != null ? T : NIL;
140 }
141
142 public String  writeToString()
143 {
144 StringBuffer sb = new StringBuffer ("#<");
145 switch (test) {
146 case TEST_EQ:
147 sb.append("EQ");
148 break;
149 case TEST_EQL:
150 sb.append("EQL");
151 break;
152 case TEST_EQUAL:
153 sb.append("EQUAL");
154 break;
155 case TEST_EQUALP:
156 sb.append("EQUALP");
157 break;
158 default:
159 Debug.bug();
160 }
161 sb.append(" hash table, ");
162 sb.append(count);
163 if (count == 1)
164 sb.append(" entry>");
165 else
166 sb.append(" entries>");
167 return sb.toString();
168 }
169
170 public LispObject get(LispObject key) throws ConditionThrowable
171 {
172 int idx = hash(key);
173 HashEntry e = buckets[idx];
174 while (e != null) {
175 if (equals(key, e.key))
176 return e.value;
177 e = e.next;
178 }
179 return null;
180 }
181
182 public void put(LispObject key, LispObject value) throws ConditionThrowable
183 {
184 int idx = hash(key);
185 HashEntry e = buckets[idx];
186 while (e != null) {
187 if (equals(key, e.key)) {
188 e.value = value;
189 return;
190 }
191 e = e.next;
192 }
193 if (++count > threshold) {
195 rehash();
196 idx = hash(key);
198 }
199 e = new HashEntry(key, value);
200 e.next = buckets[idx];
201 buckets[idx] = e;
202 }
203
204 public LispObject remove(LispObject key) throws ConditionThrowable
205 {
206 int idx = hash(key);
207 HashEntry e = buckets[idx];
208 HashEntry last = null;
209 while (e != null) {
210 if (equals(key, e.key)) {
211 if (last == null)
212 buckets[idx] = e.next;
213 else
214 last.next = e.next;
215 --count;
216 return e.value;
217 }
218 last = e;
219 e = e.next;
220 }
221 return null;
222 }
223
224 protected int hash(LispObject key) throws ConditionThrowable
225 {
226 return (key.sxhash() % buckets.length);
227 }
228
229 protected abstract boolean equals(LispObject o1, LispObject o2)
230 throws ConditionThrowable;
231
232 private void rehash() throws ConditionThrowable
233 {
234 HashEntry[] oldBuckets = buckets;
235 int newCapacity = buckets.length * 2 + 1;
236 threshold = (int) (newCapacity * loadFactor);
237 buckets = new HashEntry[newCapacity];
238 for (int i = oldBuckets.length; i-- > 0;) {
239 HashEntry e = oldBuckets[i];
240 while (e != null) {
241 int idx = hash(e.key);
242 HashEntry dest = buckets[idx];
243 if (dest != null) {
244 while (dest.next != null)
245 dest = dest.next;
246 dest.next = e;
247 } else
248 buckets[idx] = e;
249 HashEntry next = e.next;
250 e.next = null;
251 e = next;
252 }
253 }
254 }
255
256 private LispObject ENTRIES()
258 {
259 LispObject list = NIL;
260 for (int i = buckets.length; i-- > 0;) {
261 HashEntry e = buckets[i];
262 while (e != null) {
263 list = new Cons(new Cons(e.key, e.value), list);
264 e = e.next;
265 }
266 }
267 return list;
268 }
269
270 protected static class HashEntry
271 {
272 LispObject key;
273 LispObject value;
274 HashEntry next;
275
276 HashEntry(LispObject key, LispObject value)
277 {
278 this.key = key;
279 this.value = value;
280 }
281 }
282
283 private static final LispObject FUNCTION_EQ =
284 Symbol.EQ.getSymbolFunction();
285 private static final LispObject FUNCTION_EQL =
286 Symbol.EQL.getSymbolFunction();
287 private static final LispObject FUNCTION_EQUAL =
288 Symbol.EQUAL.getSymbolFunction();
289 private static final LispObject FUNCTION_EQUALP =
290 Symbol.EQUALP.getSymbolFunction();
291
292 private static final Primitive4 _MAKE_HASH_TABLE =
294 new Primitive4("%make-hash-table", PACKAGE_SYS, false)
295 {
296 public LispObject execute(LispObject test, LispObject size,
297 LispObject rehashSize, LispObject rehashThreshold)
298 throws ConditionThrowable
299 {
300 int n;
301 try {
302 n = ((Fixnum)size).value;
303 }
304 catch (ClassCastException e) {
305 return signal(new TypeError(size, Symbol.FIXNUM));
306 }
307 if (test == FUNCTION_EQL || test == NIL)
308 return new EqlHashTable(n, rehashSize, rehashThreshold);
309 if (test == FUNCTION_EQ)
310 return new EqHashTable(n, rehashSize, rehashThreshold);
311 if (test == FUNCTION_EQUAL)
312 return new EqualHashTable(n, rehashSize, rehashThreshold);
313 if (test == FUNCTION_EQUALP)
314 return new EqualpHashTable(n, rehashSize, rehashThreshold);
315 return signal(new LispError("Unknown test for MAKE-HASH-TABLE: " +
316 test.writeToString()));
317 }
318 };
319
320 private static final Primitive GETHASH =
323 new Primitive("gethash","key hash-table &optional default")
324 {
325 public LispObject execute(LispObject first, LispObject second)
326 throws ConditionThrowable
327 {
328 try {
329 return ((HashTable)second).gethash(first, NIL);
330 }
331 catch (ClassCastException e) {
332 return signal(new TypeError(second, Symbol.HASH_TABLE));
333 }
334 }
335 public LispObject execute(LispObject first, LispObject second,
336 LispObject third)
337 throws ConditionThrowable
338 {
339 try {
340 return ((HashTable)second).gethash(first, third);
341 }
342 catch (ClassCastException e) {
343 return signal(new TypeError(second, Symbol.HASH_TABLE));
344 }
345 }
346 };
347
348 private static final Primitive PUTHASH =
351 new Primitive("puthash", PACKAGE_SYS, false)
352 {
353 public LispObject execute(LispObject[] args) throws ConditionThrowable
354 {
355 final int length = args.length;
356 if (length < 3 || length > 4)
357 return signal(new WrongNumberOfArgumentsException(this));
358 if (args[1] instanceof HashTable) {
359 LispObject key = args[0];
360 HashTable ht = (HashTable) args[1];
361 LispObject value;
362 if (length == 3)
363 value = args[2];
364 else {
365 Debug.assertTrue(length == 4);
366 value = args[3];
367 }
368 return ht.puthash(key, value);
369 }
370 return signal(new TypeError(args[1], "hash-table"));
371 }
372 };
373
374 private static final Primitive2 REMHASH =
376 new Primitive2("remhash", "key hash-table")
377 {
378 public LispObject execute(LispObject first, LispObject second)
379 throws ConditionThrowable
380 {
381 if (second instanceof HashTable) {
382 LispObject key = first;
383 HashTable ht = (HashTable) second;
384 return ht.remhash(key);
385 }
386 return signal(new TypeError(second, "hash-table"));
387 }
388 };
389
390 private static final Primitive1 CLRHASH =
393 new Primitive1("clrhash", "hash-table")
394 {
395 public LispObject execute(LispObject arg) throws ConditionThrowable
396 {
397 if (arg instanceof HashTable) {
398 ((HashTable)arg).clear();
399 return arg;
400 }
401 return signal(new TypeError(arg, "hash-table"));
402 }
403 };
404
405 private static final Primitive1 HASH_TABLE_COUNT =
407 new Primitive1("hash-table-count", "hash-table")
408 {
409 public LispObject execute(LispObject arg) throws ConditionThrowable
410 {
411 if (arg instanceof HashTable)
412 return new Fixnum(((HashTable)arg).getCount());
413 return signal(new TypeError(arg, "hash-table"));
414 }
415 };
416
417 private static final Primitive1 SXHASH = new Primitive1("sxhash", "object")
420 {
421 public LispObject execute(LispObject arg) throws ConditionThrowable
422 {
423 return new Fixnum(arg.sxhash());
424 }
425 };
426
427 private static final Primitive1 PSXHASH =
431 new Primitive1("psxhash", PACKAGE_SYS, false, "object")
432 {
433 public LispObject execute(LispObject arg) throws ConditionThrowable
434 {
435 return new Fixnum(arg.psxhash());
436 }
437 };
438
439 private static final Primitive2 MIX =
440 new Primitive2("mix", PACKAGE_SYS, false, "x y")
441 {
442 public LispObject execute(LispObject first, LispObject second)
443 throws ConditionThrowable
444 {
445 return number(mix(Fixnum.getValue(first), Fixnum.getValue(second)));
446 }
447 };
448
449 private static final Primitive1 HASH_TABLE_P =
451 new Primitive1("hash-table-p","object") {
452 public LispObject execute(LispObject arg) throws ConditionThrowable
453 {
454 return arg instanceof HashTable ? T : NIL;
455 }
456 };
457
458 private static final Primitive1 HASH_TABLE_ENTRIES =
460 new Primitive1("hash-table-entries", PACKAGE_SYS, false) {
461 public LispObject execute(LispObject arg) throws ConditionThrowable
462 {
463 if (arg instanceof HashTable)
464 return ((HashTable)arg).ENTRIES();
465 return signal(new TypeError(arg, Symbol.HASH_TABLE));
466 }
467 };
468
469 private static final Primitive1 HASH_TABLE_TEST =
470 new Primitive1("hash-table-test", "hash-table")
471 {
472 public LispObject execute(LispObject arg) throws ConditionThrowable
473 {
474 if (arg instanceof HashTable) {
475 switch (((HashTable)arg).test) {
476 case TEST_EQ:
477 return Symbol.EQ;
478 case TEST_EQL:
479 return Symbol.EQL;
480 case TEST_EQUAL:
481 return Symbol.EQUAL;
482 case TEST_EQUALP:
483 return Symbol.EQUALP;
484 default:
485 Debug.assertTrue(false);
486 return NIL;
487 }
488 }
489 return signal(new TypeError(arg, Symbol.HASH_TABLE));
490 }
491 };
492
493 private static final Primitive1 HASH_TABLE_SIZE =
494 new Primitive1("hash-table-size", "hash-table")
495 {
496 public LispObject execute(LispObject arg) throws ConditionThrowable
497 {
498 if (arg instanceof HashTable)
499 return new Fixnum(((HashTable)arg).buckets.length);
500 return signal(new TypeError(arg, Symbol.HASH_TABLE));
501 }
502 };
503
504 private static final Primitive1 HASH_TABLE_REHASH_SIZE =
505 new Primitive1("hash-table-rehash-size", "hash-table")
506 {
507 public LispObject execute(LispObject arg) throws ConditionThrowable
508 {
509 if (arg instanceof HashTable)
510 return ((HashTable)arg).rehashSize;
511 return signal(new TypeError(arg, Symbol.HASH_TABLE));
512 }
513 };
514
515 private static final Primitive1 HASH_TABLE_REHASH_THRESHOLD =
516 new Primitive1("hash-table-rehash-threshold", "hash-table")
517 {
518 public LispObject execute(LispObject arg) throws ConditionThrowable
519 {
520 if (arg instanceof HashTable)
521 return ((HashTable)arg).rehashThreshold;
522 return signal(new TypeError(arg, Symbol.HASH_TABLE));
523 }
524 };
525 }
526 |
Popular Tags |
Java API By Example, From Geeks To Geeks.