1 /* Implementation of the hash table lisp object type.
2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
3 Copyright (C) 1995, 1996 Ben Wing.
4 Copyright (C) 1997 Free Software Foundation, Inc.
6 This file is part of SXEmacs
8 SXEmacs is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
13 SXEmacs is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
22 /* Synched up with: Not in FSF. */
28 /* for the category subsystem */
33 Lisp_Object Qhash_tablep;
34 static Lisp_Object Qhashtable, Qhash_table;
35 static Lisp_Object Qweakness, Qvalue, Qkey_or_value, Qkey_and_value;
36 static Lisp_Object Vall_weak_hash_tables;
37 static Lisp_Object Qrehash_size, Qrehash_threshold;
38 static Lisp_Object Q_size, Q_test, Q_weakness;
39 static Lisp_Object Q_rehash_size, Q_rehash_threshold;
41 /* obsolete as of 19990901 in xemacs-21.2 */
42 static Lisp_Object Qweak, Qkey_weak, Qvalue_weak, Qkey_or_value_weak;
43 static Lisp_Object Qnon_weak, Q_type;
46 #define HASH_TABLE_DEFAULT_SIZE 16
47 #define HASH_TABLE_DEFAULT_REHASH_SIZE 1.3
48 #define HASH_TABLE_MIN_SIZE 10
50 #define HASH_CODE(key, ht) \
51 ((((ht)->hash_function ? (ht)->hash_function (key) : LISP_HASH (key)) \
52 * (ht)->golden_ratio) \
55 #define KEYS_EQUAL_P(key1, key2, testfun) \
56 (EQ (key1, key2) || ((testfun) && (testfun) (key1, key2)))
58 #define LINEAR_PROBING_LOOP(probe, entries, size) \
60 !HENTRY_CLEAR_P (probe) || \
61 (probe == entries + size ? \
62 (probe = entries, !HENTRY_CLEAR_P (probe)) : 0); \
65 #ifndef ERROR_CHECK_HASH_TABLE
66 # ifdef ERROR_CHECK_TYPECHECK
67 # define ERROR_CHECK_HASH_TABLE 1
69 # define ERROR_CHECK_HASH_TABLE 0
73 #if ERROR_CHECK_HASH_TABLE
75 check_hash_table_invariants(hash_table_t ht)
77 assert(ht->count < ht->size);
78 assert(ht->count <= ht->rehash_count);
79 assert(ht->rehash_count < ht->size);
80 assert((fpfloat)ht->count * ht->rehash_threshold - 1 <=
81 (fpfloat)ht->rehash_count);
82 assert(HENTRY_CLEAR_P(ht->hentries + ht->size));
85 #define check_hash_table_invariants(ht)
88 /* We use linear probing instead of double hashing, despite its lack
89 of blessing by Knuth and company, because, as a result of the
90 increasing discrepancy between CPU speeds and memory speeds, cache
91 behavior is becoming increasingly important, e.g:
93 For a trivial loop, the penalty for non-sequential access of an array is:
94 - a factor of 3-4 on Pentium Pro 200 Mhz
95 - a factor of 10 on Ultrasparc 300 Mhz */
97 /* Return a suitable size for a hash table, with at least SIZE slots. */
99 hash_table_size(size_t requested_size)
101 /* Return some prime near, but greater than or equal to, SIZE.
102 Decades from the time of writing, someone will have a system large
103 enough that the list below will be too short... */
104 static const size_t primes[] = {
105 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
106 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
107 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
108 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
109 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
110 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
111 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
112 243370577, 316381771, 411296309, 534685237, 695090819,
114 1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
116 /* We've heard of binary search. */
118 for (low = 0, high = countof(primes) - 1; high - low > 1;) {
119 /* Loop Invariant: size < primes [high] */
120 int mid = (low + high) / 2;
121 if (primes[mid] < requested_size)
129 static int lisp_object_eql_equal(Lisp_Object obj1, Lisp_Object obj2)
131 return EQ(obj1, obj2) || (FLOATP(obj1)
132 && internal_equal(obj1, obj2, 0));
135 static hcode_t lisp_object_eql_hash(Lisp_Object obj)
137 return FLOATP(obj) ? internal_hash(obj, 0) : LISP_HASH(obj);
140 static int lisp_object_equal_equal(Lisp_Object obj1, Lisp_Object obj2)
142 return internal_equal(obj1, obj2, 0);
145 static hcode_t lisp_object_equal_hash(Lisp_Object obj)
147 return internal_hash(obj, 0);
150 static Lisp_Object mark_hash_table(Lisp_Object obj)
152 hash_table_t ht = XHASH_TABLE(obj);
154 /* If the hash table is weak, we don't want to mark the keys and
155 values (we scan over them after everything else has been marked,
156 and mark or remove them as necessary). */
157 if (ht->weakness == HASH_TABLE_NON_WEAK) {
158 for (hentry_t e = ht->hentries, sentinel = e + ht->size;
160 if (!HENTRY_CLEAR_P(e)) {
162 mark_object(e->value);
169 /* Equality of hash tables. Two hash tables are equal when they are of
170 the same weakness and test function, they have the same number of
171 elements, and for each key in the hash table, the values are `equal'.
173 This is similar to Common Lisp `equalp' of hash tables, with the
174 difference that CL requires the keys to be compared with the test
175 function, which we don't do. Doing that would require consing, and
176 consing is a bad idea in `equal'. Anyway, our method should provide
177 the same result -- if the keys are not equal according to the test
178 function, then Fgethash() in hash_table_equal_mapper() will fail. */
180 hash_table_equal(Lisp_Object hash_table1, Lisp_Object hash_table2, int depth)
182 hash_table_t ht1 = XHASH_TABLE(hash_table1);
183 hash_table_t ht2 = XHASH_TABLE(hash_table2);
185 if ((ht1->test_function != ht2->test_function) ||
186 (ht1->weakness != ht2->weakness) || (ht1->count != ht2->count)) {
191 for (hentry_t e = ht1->hentries, sntl = e + ht1->size; e < sntl; e++) {
192 if (!HENTRY_CLEAR_P(e)) {
193 /* Look up the key in the other hash table, and compare
195 Lisp_Object value_in_other =
196 Fgethash(e->key, hash_table2, Qunbound);
197 if (UNBOUNDP(value_in_other) ||
198 !internal_equal(e->value, value_in_other, depth)) {
199 return 0; /* Give up */
206 /* This is not a great hash function, but it _is_ correct and fast.
207 Examining all entries is too expensive, and examining a random
208 subset does not yield a correct hash function. */
209 static hcode_t hash_table_hash(Lisp_Object hash_table, int depth)
211 return XHASH_TABLE(hash_table)->count;
214 /* Printing hash tables.
216 This is non-trivial, because we use a readable structure-style
217 syntax for hash tables. This means that a typical hash table will be
218 readably printed in the form of:
220 #s(hash-table size 2 data (key1 value1 key2 value2))
222 The supported hash table structure keywords and their values are:
223 `test' (eql (or nil), eq or equal)
224 `size' (a natnum or nil)
225 `rehash-size' (a float)
226 `rehash-threshold' (a float)
227 `weakness' (nil, key, value, key-and-value, or key-or-value)
230 If `print-readably' is nil, then a simpler syntax is used, for example
232 #<hash-table size 2/13 data (key1 value1 key2 value2) 0x874d>
234 The data is truncated to four pairs, and the rest is shown with
235 `...'. This printer does not cons. */
237 /* Print the data of the hash table. This maps through a Lisp
238 hash table and prints key/value pairs using PRINTCHARFUN. */
240 print_hash_table_data(hash_table_t ht, Lisp_Object printcharfun)
244 write_c_string(" data (", printcharfun);
246 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
247 if (!HENTRY_CLEAR_P(e)) {
249 write_c_string(" ", printcharfun);
250 if (!print_readably && count > 3) {
251 write_c_string("...", printcharfun);
254 print_internal(e->key, printcharfun, 1);
255 write_c_string(" ", printcharfun);
256 print_internal(e->value, printcharfun, 1);
260 write_c_string(")", printcharfun);
264 print_hash_table(Lisp_Object obj, Lisp_Object printcharfun, int escapeflag)
266 hash_table_t ht = XHASH_TABLE(obj);
268 write_c_string(print_readably ? "#s(hash-table" : "#<hash-table",
271 /* These checks have a kludgy look to them, but they are safe.
272 Due to nature of hashing, you cannot use arbitrary
273 test functions anyway. */
274 if (!ht->test_function)
275 write_c_string(" test eq", printcharfun);
276 else if (ht->test_function == lisp_object_equal_equal)
277 write_c_string(" test equal", printcharfun);
278 else if (ht->test_function == lisp_object_eql_equal)
283 if (ht->count || !print_readably) {
285 write_fmt_str(printcharfun, " size %lu", (unsigned long)ht->count);
287 write_fmt_str(printcharfun, " size %lu/%lu",
288 (unsigned long)ht->count,
289 (unsigned long)ht->size);
292 if (ht->weakness != HASH_TABLE_NON_WEAK) {
293 write_fmt_str(printcharfun, " weakness %s",
294 (ht->weakness == HASH_TABLE_WEAK ? "key-and-value" :
295 ht->weakness == HASH_TABLE_KEY_WEAK ? "key" :
296 ht->weakness == HASH_TABLE_VALUE_WEAK ? "value" :
298 HASH_TABLE_KEY_VALUE_WEAK ? "key-or-value" :
299 "you-d-better-not-see-this"));
303 print_hash_table_data(ht, printcharfun);
306 write_c_string(")", printcharfun);
308 write_fmt_str(printcharfun, " 0x%x>", ht->header.uid);
311 static void finalize_hash_table(void *header, int for_disksave)
314 hash_table_t ht = (hash_table_t ) header;
321 static const struct lrecord_description hentry_description_1[] = {
322 {XD_LISP_OBJECT, offsetof(struct hentry_s, key)},
323 {XD_LISP_OBJECT, offsetof(struct hentry_s, value)},
327 static const struct struct_description hentry_description = {
328 sizeof(struct hentry_s),
332 const struct lrecord_description hash_table_description[] = {
333 {XD_SIZE_T, offsetof(struct hash_table_s, size)},
334 {XD_STRUCT_PTR, offsetof(struct hash_table_s, hentries),
335 XD_INDIRECT(0, 1), &hentry_description},
336 {XD_LO_LINK, offsetof(struct hash_table_s, next_weak)},
340 DEFINE_LRECORD_IMPLEMENTATION(
341 "hash-table", hash_table,
342 mark_hash_table, print_hash_table, finalize_hash_table,
343 hash_table_equal, hash_table_hash, hash_table_description,
344 struct hash_table_s);
347 xhash_table(Lisp_Object hash_table)
350 CHECK_HASH_TABLE(hash_table);
351 check_hash_table_invariants(XHASH_TABLE(hash_table));
352 return XHASH_TABLE(hash_table);
355 /************************************************************************/
356 /* Creation of Hash Tables */
357 /************************************************************************/
359 /* Creation of hash tables, without error-checking. */
360 static void compute_hash_table_derived_values(hash_table_t ht)
362 ht->rehash_count = (size_t)
363 ((fpfloat)ht->size * ht->rehash_threshold);
364 ht->golden_ratio = (size_t)
365 ((fpfloat)ht->size * (.6180339887 / (fpfloat)sizeof(Lisp_Object)));
369 make_standard_lisp_hash_table(
370 enum hash_table_test test,
371 size_t size, fpfloat rehash_size, fpfloat rehash_threshold,
372 enum hash_table_weakness weakness)
374 hash_table_hash_f hash_function = 0;
375 hash_table_test_f test_function = 0;
384 test_function = lisp_object_eql_equal;
385 hash_function = lisp_object_eql_hash;
388 case HASH_TABLE_EQUAL:
389 test_function = lisp_object_equal_equal;
390 hash_function = lisp_object_equal_hash;
397 return make_general_lisp_hash_table(hash_function, test_function,
398 size, rehash_size, rehash_threshold,
403 make_general_lisp_hash_table(
404 hash_table_hash_f hash_function, hash_table_test_f test_function,
405 size_t size, fpfloat rehash_size, fpfloat rehash_threshold,
406 enum hash_table_weakness weakness)
408 Lisp_Object hash_table;
409 hash_table_t ht = alloc_lcrecord_type(
410 struct hash_table_s, &lrecord_hash_table);
412 /* the categories are actually seq and dict, but use the per-type
413 implementation for a start */
414 ht->header.lheader.morphisms = (1<<cat_mk_lc);
416 ht->test_function = test_function;
417 ht->hash_function = hash_function;
418 ht->weakness = weakness;
420 ht->rehash_size = rehash_size > 1.0
422 : HASH_TABLE_DEFAULT_REHASH_SIZE;
424 ht->rehash_threshold = rehash_threshold > 0.0
426 : size > 4096 && !ht->test_function ? 0.7 : 0.6;
428 if (size < HASH_TABLE_MIN_SIZE)
429 size = HASH_TABLE_MIN_SIZE;
430 ht->size = hash_table_size(
431 (size_t)(((fpfloat)size / ht->rehash_threshold) + 1.0));
434 compute_hash_table_derived_values(ht);
436 /* We leave room for one never-occupied sentinel hentry at the end. */
437 ht->hentries = xnew_array_and_zero(struct hentry_s, ht->size + 1);
439 XSETHASH_TABLE(hash_table, ht);
441 if (weakness == HASH_TABLE_NON_WEAK) {
442 ht->next_weak = Qunbound;
444 ht->next_weak = Vall_weak_hash_tables,
445 Vall_weak_hash_tables = hash_table;
451 make_lisp_hash_table(size_t size,
452 enum hash_table_weakness weakness,
453 enum hash_table_test test)
455 return make_standard_lisp_hash_table(test, size, -1.0, -1.0, weakness);
458 /* Pretty reading of hash tables.
460 Here we use the existing structures mechanism (which is,
461 unfortunately, pretty cumbersome) for validating and instantiating
462 the hash tables. The idea is that the side-effect of reading a
463 #s(hash-table PLIST) object is creation of a hash table with desired
464 properties, and that the hash table is returned. */
466 /* Validation functions: each keyword provides its own validation
467 function. The errors should maybe be continuable, but it is
468 unclear how this would cope with ERRB. */
470 hash_table_size_validate(Lisp_Object keyword, Lisp_Object value,
473 #ifdef WITH_NUMBER_TYPES
474 if (!NILP(Fnonnegativep(value)))
477 maybe_signal_error(Qwrong_type_argument, list2(Qnonnegativep, value),
479 #else /* !WITH_NUMBER_TYPES */
483 maybe_signal_error(Qwrong_type_argument, list2(Qnatnump, value),
485 #endif /* WITH_NUMBER_TYPES */
489 static size_t decode_hash_table_size(Lisp_Object obj)
491 #ifdef WITH_NUMBER_TYPES
492 return NILP(obj) ? HASH_TABLE_DEFAULT_SIZE :
493 XINT(Fcoerce_number(obj, Qint, Qnil));
495 return NILP(obj) ? HASH_TABLE_DEFAULT_SIZE : XINT(obj);
500 hash_table_weakness_validate(Lisp_Object keyword, Lisp_Object value,
509 if (EQ(value, Qkey_and_value))
511 if (EQ(value, Qkey_or_value))
513 if (EQ(value, Qvalue))
516 /* Following values are obsolete as of 19990901 in xemacs-21.2 */
517 if (EQ(value, Qnon_weak))
519 if (EQ(value, Qweak))
521 if (EQ(value, Qkey_weak))
523 if (EQ(value, Qkey_or_value_weak))
525 if (EQ(value, Qvalue_weak))
528 maybe_signal_simple_error("Invalid hash table weakness",
529 value, Qhash_table, errb);
533 static enum hash_table_weakness decode_hash_table_weakness(Lisp_Object obj)
536 return HASH_TABLE_NON_WEAK;
538 return HASH_TABLE_WEAK;
539 if (EQ(obj, Qkey_and_value))
540 return HASH_TABLE_WEAK;
542 return HASH_TABLE_KEY_WEAK;
543 if (EQ(obj, Qkey_or_value))
544 return HASH_TABLE_KEY_VALUE_WEAK;
546 return HASH_TABLE_VALUE_WEAK;
548 /* Following values are obsolete as of 19990901 in xemacs-21.2 */
549 if (EQ(obj, Qnon_weak))
550 return HASH_TABLE_NON_WEAK;
552 return HASH_TABLE_WEAK;
553 if (EQ(obj, Qkey_weak))
554 return HASH_TABLE_KEY_WEAK;
555 if (EQ(obj, Qkey_or_value_weak))
556 return HASH_TABLE_KEY_VALUE_WEAK;
557 if (EQ(obj, Qvalue_weak))
558 return HASH_TABLE_VALUE_WEAK;
560 signal_simple_error("Invalid hash table weakness", obj);
561 return HASH_TABLE_NON_WEAK; /* not reached */
565 hash_table_test_validate(Lisp_Object keyword, Lisp_Object value,
572 if (EQ(value, Qequal))
577 maybe_signal_simple_error("Invalid hash table test",
578 value, Qhash_table, errb);
582 static enum hash_table_test decode_hash_table_test(Lisp_Object obj)
585 return HASH_TABLE_EQL;
587 return HASH_TABLE_EQ;
589 return HASH_TABLE_EQUAL;
591 return HASH_TABLE_EQL;
593 signal_simple_error("Invalid hash table test", obj);
594 return HASH_TABLE_EQ; /* not reached */
598 hash_table_rehash_size_validate(Lisp_Object keyword, Lisp_Object value,
601 if (!FLOATP(value)) {
602 maybe_signal_error(Qwrong_type_argument, list2(Qfloatp, value),
608 fpfloat rehash_size = XFLOAT_DATA(value);
609 if (rehash_size <= 1.0) {
610 maybe_signal_simple_error
611 ("Hash table rehash size must be greater than 1.0",
612 value, Qhash_table, errb);
620 static fpfloat decode_hash_table_rehash_size(Lisp_Object rehash_size)
622 return NILP(rehash_size) ? -1.0 : XFLOAT_DATA(rehash_size);
626 hash_table_rehash_threshold_validate(Lisp_Object keyword, Lisp_Object value,
629 if (!FLOATP(value)) {
630 maybe_signal_error(Qwrong_type_argument, list2(Qfloatp, value),
636 fpfloat rehash_threshold = XFLOAT_DATA(value);
637 if (rehash_threshold <= 0.0 || rehash_threshold >= 1.0) {
638 maybe_signal_simple_error
639 ("Hash table rehash threshold must be between 0.0 and 1.0",
640 value, Qhash_table, errb);
648 static fpfloat decode_hash_table_rehash_threshold(Lisp_Object rehash_threshold)
650 return NILP(rehash_threshold) ? -1.0 : XFLOAT_DATA(rehash_threshold);
654 hash_table_data_validate(Lisp_Object keyword, Lisp_Object value,
659 GET_EXTERNAL_LIST_LENGTH(value, len);
662 maybe_signal_simple_error
663 ("Hash table data must have alternating key/value pairs",
664 value, Qhash_table, errb);
670 /* The actual instantiation of a hash table. This does practically no
671 error checking, because it relies on the fact that the paranoid
672 functions above have error-checked everything to the last details.
673 If this assumption is wrong, we will get a crash immediately (with
674 error-checking compiled in), and we'll know if there is a bug in
675 the structure mechanism. So there. */
676 static Lisp_Object hash_table_instantiate(Lisp_Object plist)
678 Lisp_Object hash_table;
679 Lisp_Object test = Qnil;
680 Lisp_Object size = Qnil;
681 Lisp_Object rehash_size = Qnil;
682 Lisp_Object rehash_threshold = Qnil;
683 Lisp_Object weakness = Qnil;
684 Lisp_Object data = Qnil;
686 while (!NILP(plist)) {
687 Lisp_Object key, value;
695 else if (EQ(key, Qsize))
697 else if (EQ(key, Qrehash_size))
699 else if (EQ(key, Qrehash_threshold))
700 rehash_threshold = value;
701 else if (EQ(key, Qweakness))
703 else if (EQ(key, Qdata))
705 else if (EQ(key, Qtype)) /*obsolete */
711 /* Create the hash table. */
712 hash_table = make_standard_lisp_hash_table
713 (decode_hash_table_test(test),
714 decode_hash_table_size(size),
715 decode_hash_table_rehash_size(rehash_size),
716 decode_hash_table_rehash_threshold(rehash_threshold),
717 decode_hash_table_weakness(weakness));
719 /* I'm not sure whether this can GC, but better safe than sorry. */
724 /* And fill it with data. */
725 while (!NILP(data)) {
726 Lisp_Object key, value;
731 Fputhash(key, value, hash_table);
740 structure_type_create_hash_table_structure_name(Lisp_Object structure_name)
742 struct structure_type *st;
744 st = define_structure_type(structure_name, 0, hash_table_instantiate);
745 define_structure_type_keyword(st, Qtest, hash_table_test_validate);
746 define_structure_type_keyword(st, Qsize, hash_table_size_validate);
747 define_structure_type_keyword(st, Qrehash_size,
748 hash_table_rehash_size_validate);
749 define_structure_type_keyword(st, Qrehash_threshold,
750 hash_table_rehash_threshold_validate);
751 define_structure_type_keyword(st, Qweakness,
752 hash_table_weakness_validate);
753 define_structure_type_keyword(st, Qdata, hash_table_data_validate);
755 /* obsolete as of 19990901 in xemacs-21.2 */
756 define_structure_type_keyword(st, Qtype, hash_table_weakness_validate);
759 /* Create a built-in Lisp structure type named `hash-table'.
760 We make #s(hashtable ...) equivalent to #s(hash-table ...),
761 for backward compatibility.
762 This is called from emacs.c. */
763 void structure_type_create_hash_table(void)
765 structure_type_create_hash_table_structure_name(Qhash_table);
766 structure_type_create_hash_table_structure_name(Qhashtable); /* compat */
769 /************************************************************************/
770 /* Definition of Lisp-visible methods */
771 /************************************************************************/
773 DEFUN("hash-table-p", Fhash_table_p, 1, 1, 0, /*
774 Return t if OBJECT is a hash table, else nil.
778 return HASH_TABLEP(object) ? Qt : Qnil;
781 DEFUN("make-hash-table", Fmake_hash_table, 0, MANY, 0, /*
782 Return a new empty hash table object.
783 Use Common Lisp style keywords to specify hash table properties.
784 (make-hash-table &key test size rehash-size rehash-threshold weakness)
786 Keyword :test can be `eq', `eql' (default) or `equal'.
787 Comparison between keys is done using this function.
788 If speed is important, consider using `eq'.
789 When hash table keys may be strings, you will likely need to use `equal'.
791 Keyword :size specifies the number of keys likely to be inserted.
792 This number of entries can be inserted without enlarging the hash table.
794 Keyword :rehash-size must be a float greater than 1.0, and specifies
795 the factor by which to increase the size of the hash table when enlarging.
797 Keyword :rehash-threshold must be a float between 0.0 and 1.0,
798 and specifies the load factor of the hash table which triggers enlarging.
800 Non-standard keyword :weakness can be `nil' (default), `t', `key-and-value',
801 `key', `value' or `key-or-value'. `t' is an alias for `key-and-value'.
803 A key-and-value-weak hash table, also known as a fully-weak or simply
804 as a weak hash table, is one whose pointers do not count as GC
805 referents: for any key-value pair in the hash table, if the only
806 remaining pointer to either the key or the value is in a weak hash
807 table, then the pair will be removed from the hash table, and the key
808 and value collected. A non-weak hash table (or any other pointer)
809 would prevent the object from being collected.
811 A key-weak hash table is similar to a fully-weak hash table except that
812 a key-value pair will be removed only if the key remains unmarked
813 outside of weak hash tables. The pair will remain in the hash table if
814 the key is pointed to by something other than a weak hash table, even
817 A value-weak hash table is similar to a fully-weak hash table except
818 that a key-value pair will be removed only if the value remains
819 unmarked outside of weak hash tables. The pair will remain in the
820 hash table if the value is pointed to by something other than a weak
821 hash table, even if the key is not.
823 A key-or-value-weak hash table is similar to a fully-weak hash table except
824 that a key-value pair will be removed only if the value and the key remain
825 unmarked outside of weak hash tables. The pair will remain in the
826 hash table if the value or key are pointed to by something other than a weak
827 hash table, even if the other is not.
829 (int nargs, Lisp_Object * args))
832 Lisp_Object test = Qnil;
833 Lisp_Object size = Qnil;
834 Lisp_Object rehash_size = Qnil;
835 Lisp_Object rehash_threshold = Qnil;
836 Lisp_Object weakness = Qnil;
838 while (i + 1 < nargs) {
839 Lisp_Object keyword = args[i++];
840 Lisp_Object value = args[i++];
842 if (EQ(keyword, Q_test))
844 else if (EQ(keyword, Q_size))
846 else if (EQ(keyword, Q_rehash_size))
848 else if (EQ(keyword, Q_rehash_threshold))
849 rehash_threshold = value;
850 else if (EQ(keyword, Q_weakness))
852 else if (EQ(keyword, Q_type)) /*obsolete */
856 ("Invalid hash table property keyword", keyword);
860 signal_simple_error("Hash table property requires a value",
863 #define VALIDATE_VAR(var) \
864 if (!NILP (var)) hash_table_##var##_validate (Q##var, var, ERROR_ME);
868 VALIDATE_VAR(rehash_size);
869 VALIDATE_VAR(rehash_threshold);
870 VALIDATE_VAR(weakness);
872 return make_standard_lisp_hash_table
873 (decode_hash_table_test(test),
874 decode_hash_table_size(size),
875 decode_hash_table_rehash_size(rehash_size),
876 decode_hash_table_rehash_threshold(rehash_threshold),
877 decode_hash_table_weakness(weakness));
880 DEFUN("copy-hash-table", Fcopy_hash_table, 1, 1, 0, /*
881 Return a new hash table containing the same keys and values as HASH-TABLE.
882 The keys and values will not themselves be copied.
886 const hash_table_t ht_old = xhash_table(hash_table);
887 hash_table_t ht = alloc_lcrecord_type(
888 struct hash_table_s, &lrecord_hash_table);
890 copy_lcrecord(ht, ht_old);
892 ht->hentries = xnew_array(struct hentry_s, ht_old->size + 1);
893 memcpy(ht->hentries, ht_old->hentries,
894 (ht_old->size + 1) * sizeof(struct hentry_s));
896 /* the categories are actually seq and dict, but use the per-type
897 implementation for a start */
898 ht->header.lheader.morphisms = (1<<cat_mk_lc);
900 XSETHASH_TABLE(hash_table, ht);
902 if (!EQ(ht->next_weak, Qunbound)) {
903 ht->next_weak = Vall_weak_hash_tables,
904 Vall_weak_hash_tables = hash_table;
910 resize_hash_table(hash_table_t ht, size_t new_size)
912 hentry_t old_entries, new_entries;
918 old_entries = ht->hentries;
920 ht->hentries = xnew_array_and_zero(struct hentry_s, new_size + 1);
921 new_entries = ht->hentries;
923 compute_hash_table_derived_values(ht);
925 for (hentry_t e = old_entries, sentinel = e + old_size;
927 if (!HENTRY_CLEAR_P(e)) {
928 hentry_t probe = new_entries + HASH_CODE(e->key, ht);
929 LINEAR_PROBING_LOOP(probe, new_entries, new_size);
933 if (!DUMPEDP(old_entries)) {
938 /* After a hash table has been saved to disk and later restored by the
939 portable dumper, it contains the same objects, but their addresses
940 and thus their HASH_CODEs have changed. */
942 pdump_reorganize_hash_table(Lisp_Object hash_table)
944 const hash_table_t ht = xhash_table(hash_table);
945 hentry_t new_entries =
946 xnew_array_and_zero(struct hentry_s, ht->size + 1);
948 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
949 if (!HENTRY_CLEAR_P(e)) {
950 hentry_t probe = new_entries + HASH_CODE(e->key, ht);
951 LINEAR_PROBING_LOOP(probe, new_entries, ht->size);
955 memcpy(ht->hentries, new_entries, ht->size * sizeof(struct hentry_s));
961 static void enlarge_hash_table(hash_table_t ht)
964 hash_table_size((size_t) ((fpfloat)ht->size * ht->rehash_size));
965 resize_hash_table(ht, new_size);
969 find_hentry(Lisp_Object key, const hash_table_t ht)
971 hash_table_test_f test_function = ht->test_function;
972 hentry_t entries = ht->hentries;
973 hentry_t probe = entries + HASH_CODE(key, ht);
975 LINEAR_PROBING_LOOP(probe, entries, ht->size)
976 if (KEYS_EQUAL_P(probe->key, key, test_function))
982 static inline Lisp_Object
983 dict_ht_get(hash_table_t ht, Lisp_Object key, Lisp_Object _default)
985 const hentry_t e = find_hentry(key, ht);
987 return HENTRY_CLEAR_P(e) ? _default : e->value;
990 DEFUN("gethash", Fgethash, 2, 3, 0, /*
991 Find hash value for KEY in HASH-TABLE.
992 If there is no corresponding value, return DEFAULT (which defaults to nil).
994 (key, hash_table, default_))
996 return dict_ht_get(xhash_table(hash_table), key, default_);
999 static inline Lisp_Object
1000 dict_ht_put(hash_table_t ht, Lisp_Object key, Lisp_Object value)
1002 hentry_t e = find_hentry(key, ht);
1004 if (!HENTRY_CLEAR_P(e))
1005 return e->value = value;
1010 if (++ht->count >= ht->rehash_count) {
1011 enlarge_hash_table(ht);
1017 DEFUN("puthash", Fputhash, 3, 3, 0, /*
1018 Hash KEY to VALUE in HASH-TABLE.
1020 (key, value, hash_table))
1022 return dict_ht_put(xhash_table(hash_table), key, value);
1025 /* Remove hentry pointed at by PROBE.
1026 Subsequent entries are removed and reinserted.
1027 We don't use tombstones - too wasteful. */
1028 static void remhash_1(hash_table_t ht, hentry_t entries, hentry_t probe)
1030 size_t size = ht->size;
1031 CLEAR_HENTRY(probe);
1035 LINEAR_PROBING_LOOP(probe, entries, size) {
1036 Lisp_Object key = probe->key;
1037 hentry_t probe2 = entries + HASH_CODE(key, ht);
1038 LINEAR_PROBING_LOOP(probe2, entries, size)
1039 if (EQ(probe2->key, key))
1040 /* hentry at probe doesn't need to move. */
1041 goto continue_outer_loop;
1042 /* Move hentry from probe to new home at probe2. */
1044 CLEAR_HENTRY(probe);
1045 continue_outer_loop:continue;
1049 static inline Lisp_Object
1050 dict_ht_remove(hash_table_t ht, Lisp_Object key)
1052 hentry_t e = find_hentry(key, ht);
1054 if (HENTRY_CLEAR_P(e)) {
1058 remhash_1(ht, ht->hentries, e);
1062 DEFUN("remhash", Fremhash, 2, 2, 0, /*
1063 Remove the entry for KEY from HASH-TABLE.
1064 Do nothing if there is no entry for KEY in HASH-TABLE.
1068 return dict_ht_remove(xhash_table(hash_table), key);
1071 DEFUN("clrhash", Fclrhash, 1, 1, 0, /*
1072 Remove all entries from HASH-TABLE, leaving it empty.
1076 hash_table_t ht = xhash_table(hash_table);
1078 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1086 /************************************************************************/
1087 /* Accessor Functions */
1088 /************************************************************************/
1090 DEFUN("hash-table-count", Fhash_table_count, 1, 1, 0, /*
1091 Return the number of entries in HASH-TABLE.
1095 return make_int(xhash_table(hash_table)->count);
1098 DEFUN("hash-table-test", Fhash_table_test, 1, 1, 0, /*
1099 Return the test function of HASH-TABLE.
1100 This can be one of `eq', `eql' or `equal'.
1104 hash_table_test_f fun = xhash_table(hash_table)->test_function;
1106 return (fun == lisp_object_eql_equal ? Qeql :
1107 fun == lisp_object_equal_equal ? Qequal : Qeq);
1111 dict_ht_size(const hash_table_t ht)
1116 DEFUN("hash-table-size", Fhash_table_size, 1, 1, 0, /*
1117 Return the size of HASH-TABLE.
1118 This is the current number of slots in HASH-TABLE, whether occupied or not.
1122 return make_int(xhash_table(hash_table)->size);
1125 DEFUN("hash-table-rehash-size", Fhash_table_rehash_size, 1, 1, 0, /*
1126 Return the current rehash size of HASH-TABLE.
1127 This is a float greater than 1.0; the factor by which HASH-TABLE
1128 is enlarged when the rehash threshold is exceeded.
1132 return make_float(xhash_table(hash_table)->rehash_size);
1135 DEFUN("hash-table-rehash-threshold", Fhash_table_rehash_threshold, 1, 1, 0, /*
1136 Return the current rehash threshold of HASH-TABLE.
1137 This is a float between 0.0 and 1.0; the maximum `load factor' of HASH-TABLE,
1138 beyond which the HASH-TABLE is enlarged by rehashing.
1142 return make_float(xhash_table(hash_table)->rehash_threshold);
1145 DEFUN("hash-table-weakness", Fhash_table_weakness, 1, 1, 0, /*
1146 Return the weakness of HASH-TABLE.
1147 This can be one of `nil', `key-and-value', `key-or-value', `key' or `value'.
1151 switch (xhash_table(hash_table)->weakness) {
1152 case HASH_TABLE_WEAK:
1153 return Qkey_and_value;
1154 case HASH_TABLE_KEY_WEAK:
1156 case HASH_TABLE_KEY_VALUE_WEAK:
1157 return Qkey_or_value;
1158 case HASH_TABLE_VALUE_WEAK:
1162 case HASH_TABLE_NON_WEAK:
1163 case HASH_TABLE_KEY_CAR_WEAK:
1164 case HASH_TABLE_VALUE_CAR_WEAK:
1165 case HASH_TABLE_KEY_CAR_VALUE_WEAK:
1172 /* obsolete as of 19990901 in xemacs-21.2 */
1173 DEFUN("hash-table-type", Fhash_table_type, 1, 1, 0, /*
1174 Return the type of HASH-TABLE.
1175 This can be one of `non-weak', `weak', `key-weak' or `value-weak'.
1179 switch (xhash_table(hash_table)->weakness) {
1180 case HASH_TABLE_WEAK:
1182 case HASH_TABLE_KEY_WEAK:
1184 case HASH_TABLE_KEY_VALUE_WEAK:
1185 return Qkey_or_value_weak;
1186 case HASH_TABLE_VALUE_WEAK:
1189 /* the bloody rest */
1190 case HASH_TABLE_NON_WEAK:
1191 case HASH_TABLE_KEY_CAR_WEAK:
1192 case HASH_TABLE_VALUE_CAR_WEAK:
1193 case HASH_TABLE_KEY_CAR_VALUE_WEAK:
1200 /************************************************************************/
1201 /* Mapping Functions */
1202 /************************************************************************/
1203 DEFUN("maphash", Fmaphash, 2, 2, 0, /*
1204 Map FUNCTION over entries in HASH-TABLE, calling it with two args,
1205 each key and value in HASH-TABLE.
1207 FUNCTION may not modify HASH-TABLE, with the one exception that FUNCTION
1208 may remhash or puthash the entry currently being processed by FUNCTION.
1210 (function, hash_table))
1212 const hash_table_t ht = xhash_table(hash_table);
1214 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1215 if (!HENTRY_CLEAR_P(e)) {
1216 Lisp_Object args[3], key;
1222 Ffuncall(countof(args), args);
1223 /* Has FUNCTION done a remhash? */
1224 if (!EQ(key, e->key) && !HENTRY_CLEAR_P(e))
1231 /* #### If the Lisp function being called does a puthash and this
1232 #### causes the hash table to be resized, the results will be quite
1233 #### random and we will likely crash. To fix this, either set a
1234 #### flag in the hash table while we're mapping and signal an error
1235 #### when new entries are added, or fix things to make this
1236 #### operation work properly, like this: Store two hash tables in
1237 #### each hash table object -- the second one is written to when
1238 #### you do a puthash inside of a mapping operation, and the
1239 #### various operations need to check both hash tables for entries.
1240 #### As soon as the last maphash over a particular hash table
1241 #### object terminates, the entries in the second table are added
1242 #### to the first (using an unwind-protect). --ben */
1244 /* Map *C* function FUNCTION over the elements of a lisp hash table. */
1246 elisp_maphash(maphash_f function, Lisp_Object hash_table, void *extra_arg)
1248 const hash_table_t ht = XHASH_TABLE(hash_table);
1250 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1251 if (!HENTRY_CLEAR_P(e)) {
1255 if (function(key, e->value, extra_arg)) {
1258 /* Has FUNCTION done a remhash? */
1259 if (!EQ(key, e->key) && !HENTRY_CLEAR_P(e)) {
1266 /* Remove all elements of a lisp hash table satisfying *C* predicate
1269 elisp_map_remhash(maphash_f predicate, Lisp_Object hash_table, void *extra_arg)
1271 hash_table_t ht = XHASH_TABLE(hash_table);
1274 for (hentry_t e = entries = ht->hentries, sentinel = e + ht->size;
1275 e < sentinel; e++) {
1276 if (!HENTRY_CLEAR_P(e)) {
1278 if (predicate(e->key, e->value, extra_arg)) {
1279 remhash_1(ht, entries, e);
1280 if (!HENTRY_CLEAR_P(e)) {
1288 /************************************************************************/
1289 /* garbage collecting weak hash tables */
1290 /************************************************************************/
1291 #define MARK_OBJ(obj) \
1293 Lisp_Object mo_obj = (obj); \
1294 if (!marked_p (mo_obj)) { \
1295 mark_object (mo_obj); \
1300 /* Complete the marking for semi-weak hash tables. */
1301 int finish_marking_weak_hash_tables(void)
1303 Lisp_Object hash_table;
1306 for (hash_table = Vall_weak_hash_tables;
1308 hash_table = XHASH_TABLE(hash_table)->next_weak) {
1309 const hash_table_t ht = XHASH_TABLE(hash_table);
1310 hentry_t e = ht->hentries;
1311 const hentry_t sentinel = e + ht->size;
1313 if (!marked_p(hash_table)) {
1314 /* The hash table is probably garbage. Ignore it. */
1318 /* Now, scan over all the pairs. For all pairs that are
1319 half-marked, we may need to mark the other half if we're
1320 keeping this pair. */
1321 switch (ht->weakness) {
1322 case HASH_TABLE_KEY_WEAK:
1323 for (; e < sentinel; e++) {
1324 if (!HENTRY_CLEAR_P(e)) {
1325 if (marked_p(e->key)) {
1332 case HASH_TABLE_VALUE_WEAK:
1333 for (; e < sentinel; e++) {
1334 if (!HENTRY_CLEAR_P(e)) {
1335 if (marked_p(e->value)) {
1342 case HASH_TABLE_KEY_VALUE_WEAK:
1343 for (; e < sentinel; e++) {
1344 if (!HENTRY_CLEAR_P(e)) {
1345 if (marked_p(e->value)) {
1347 } else if (marked_p(e->key)) {
1354 case HASH_TABLE_KEY_CAR_WEAK:
1355 for (; e < sentinel; e++) {
1356 if (!HENTRY_CLEAR_P(e)) {
1358 || marked_p(XCAR(e->key))) {
1366 /* We seem to be sprouting new weakness types at an
1367 alarming rate. At least this is not externally
1368 visible - and in fact all of these KEY_CAR_* types
1369 are only used by the glyph code. */
1370 case HASH_TABLE_KEY_CAR_VALUE_WEAK:
1371 for (; e < sentinel; e++) {
1372 if (!HENTRY_CLEAR_P(e)) {
1374 || marked_p(XCAR(e->key))) {
1377 } else if (marked_p(e->value)) {
1384 case HASH_TABLE_VALUE_CAR_WEAK:
1385 for (; e < sentinel; e++) {
1386 if (!HENTRY_CLEAR_P(e)) {
1387 if (!CONSP(e->value)
1388 || marked_p(XCAR(e->value))) {
1397 case HASH_TABLE_NON_WEAK:
1398 case HASH_TABLE_WEAK:
1407 void prune_weak_hash_tables(void)
1409 Lisp_Object hash_table, prev = Qnil;
1411 for (hash_table = Vall_weak_hash_tables; !NILP(hash_table);
1412 hash_table = XHASH_TABLE(hash_table)->next_weak) {
1413 if (!marked_p(hash_table)) {
1414 /* This hash table itself is garbage. Remove it from
1417 Vall_weak_hash_tables =
1418 XHASH_TABLE(hash_table)->next_weak;
1420 XHASH_TABLE(prev)->next_weak =
1421 XHASH_TABLE(hash_table)->next_weak;
1423 /* Now, scan over all the pairs. Remove all of the pairs
1424 in which the key or value, or both, is unmarked
1425 (depending on the weakness of the hash table). */
1426 hash_table_t ht = XHASH_TABLE(hash_table);
1427 hentry_t entries = ht->hentries;
1428 hentry_t sentinel = entries + ht->size;
1430 for (hentry_t e = entries; e < sentinel; e++) {
1431 if (!HENTRY_CLEAR_P(e)) {
1433 if (!marked_p(e->key) ||
1434 !marked_p(e->value)) {
1435 remhash_1(ht, entries, e);
1436 if (!HENTRY_CLEAR_P(e)) {
1449 /* Return a hash value for an array of Lisp_Objects of size SIZE. */
1452 internal_array_hash(const Lisp_Object *arr, size_t size, int depth)
1458 for (size_t i = 0; i < size; i++) {
1459 hash = HASH2(hash, internal_hash(arr[i], depth));
1464 /* just pick five elements scattered throughout the array.
1465 A slightly better approach would be to offset by some
1466 noise factor from the points chosen below. */
1467 for (int i = 0; i < 5; i++) {
1468 hash = HASH2(hash, internal_hash(arr[i * size / 5], depth));
1473 /* Return a hash value for a Lisp_Object. This is for use when hashing
1474 objects with the comparison being `equal' (for `eq', you can just
1475 use the Lisp_Object itself as the hash value). You need to make a
1476 tradeoff between the speed of the hash function and how good the
1477 hashing is. In particular, the hash function needs to be FAST,
1478 so you can't just traipse down the whole tree hashing everything
1479 together. Most of the time, objects will differ in the first
1480 few elements you hash. Thus, we only go to a short depth (5)
1481 and only hash at most 5 elements out of a vector. Theoretically
1482 we could still take 5^5 time (a big big number) to compute a
1483 hash, but practically this won't ever happen. */
1486 internal_hash(const Lisp_Object obj, int depth)
1490 if (CONSP(obj) && !CONSP(XCDR(obj))) {
1491 /* special case for '(a . b) conses */
1492 return HASH2(internal_hash(XCAR(obj), depth + 1),
1493 internal_hash(XCDR(obj), depth + 1));
1494 } else if (CONSP(obj)) {
1495 /* no point in worrying about tail recursion, since we're not
1497 Lisp_Object o = obj;
1499 hcode_t hash = internal_hash(XCAR(o), depth+1);
1502 for (int s = 1; s < 6 && CONSP(o); o = XCDR(o), s++) {
1503 hcode_t h = internal_hash(XCAR(o), depth+1);
1504 hash = HASH3(hash, h, s);
1509 return hash_string(XSTRING_DATA(obj), XSTRING_LENGTH(obj));
1511 if (LRECORDP(obj)) {
1512 const struct lrecord_implementation
1513 *imp = XRECORD_LHEADER_IMPLEMENTATION(obj);
1515 return imp->hash(obj, depth);
1518 return LISP_HASH(obj);
1521 DEFUN("sxhash", Fsxhash, 1, 1, 0, /*
1522 Return a hash value for OBJECT.
1523 \(equal obj1 obj2) implies (= (sxhash obj1) (sxhash obj2)).
1527 return make_int(internal_hash(object, 0));
1531 /* the seq/dict implementation */
1532 /* iterator stuff, only needed for dict so make it static */
1534 ht_iter_init(dict_t d, dict_iter_t di)
1536 const hash_table_t ht = (hash_table_t)d;
1539 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1540 if (!HENTRY_CLEAR_P(e)) {
1550 ht_iter_fini(dict_iter_t di)
1552 di->dict = di->data = NULL;
1557 ht_diter_next(dict_iter_t di, Lisp_Object *key, Lisp_Object *val)
1559 hentry_t e = di->data;
1560 const hash_table_t ht = (hash_table_t)di->dict;
1562 if (UNLIKELY(e == NULL)) {
1563 *key = *val = Qnull_pointer;
1570 /* wind to next hentry */
1571 for (const hentry_t last = ht->hentries + ht->size; ++e < last;) {
1572 if (!HENTRY_CLEAR_P(e)) {
1582 ht_siter_next(seq_iter_t si, void **elm)
1584 hentry_t e = si->data;
1585 const hash_table_t ht = (hash_table_t)si->seq;
1587 if (UNLIKELY(e == NULL)) {
1588 *elm = Qnull_pointer;
1592 *elm = (void*)e->key;
1594 /* wind to next hentry */
1595 for (const hentry_t last = ht->hentries + ht->size; ++e < last;) {
1596 if (!HENTRY_CLEAR_P(e)) {
1606 ht_iter_reset(seq_iter_t si)
1608 const hash_table_t ht = (hash_table_t)si->seq;
1610 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1611 if (!HENTRY_CLEAR_P(e)) {
1621 ht_explode(void *restrict tgt[], size_t ntgt, seq_t s)
1623 volatile size_t i = 0;
1624 const hash_table_t ht = (hash_table_t)s;
1626 for (hentry_t e = ht->hentries, sntl = e + ht->size;
1627 e < sntl && i < ntgt; e++) {
1628 if (!HENTRY_CLEAR_P(e)) {
1629 tgt[i++] = (void*)e->key;
1636 /************************************************************************/
1637 /* initialization */
1638 /************************************************************************/
1640 static struct seq_impl_s __shash_table = {
1641 .length_f = (seq_length_f)dict_ht_size,
1642 .iter_init_f = (seq_iter_init_f)ht_iter_init,
1643 .iter_next_f = ht_siter_next,
1644 .iter_fini_f = (seq_iter_fini_f)ht_iter_fini,
1645 .iter_reset_f = ht_iter_reset,
1646 .explode_f = ht_explode,
1649 static struct dict_impl_s __dhash_table = {
1650 .size_f = (dict_size_f)dict_ht_size,
1651 .put_f = (dict_put_f)dict_ht_put,
1652 .get_f = (dict_get_f)dict_ht_get,
1653 .remove_f = (dict_remove_f)dict_ht_remove,
1654 .iter_init_f = ht_iter_init,
1655 .iter_next_f = ht_diter_next,
1656 .iter_fini_f = ht_iter_fini,
1659 /* deal with seq interface */
1660 const seq_impl_t seq_hash_table = &__shash_table;
1661 /* deal with dict interface */
1662 const dict_impl_t dict_hash_table = &__dhash_table;
1664 void syms_of_elhash(void)
1666 INIT_LRECORD_IMPLEMENTATION(hash_table);
1668 DEFSUBR(Fhash_table_p);
1669 DEFSUBR(Fmake_hash_table);
1670 DEFSUBR(Fcopy_hash_table);
1676 DEFSUBR(Fhash_table_count);
1677 DEFSUBR(Fhash_table_test);
1678 DEFSUBR(Fhash_table_size);
1679 DEFSUBR(Fhash_table_rehash_size);
1680 DEFSUBR(Fhash_table_rehash_threshold);
1681 DEFSUBR(Fhash_table_weakness);
1682 DEFSUBR(Fhash_table_type); /* obsolete */
1685 DEFSUBR(Finternal_hash_value);
1688 defsymbol(&Qhash_tablep, "hash-table-p");
1689 defsymbol(&Qhash_table, "hash-table");
1690 defsymbol(&Qhashtable, "hashtable");
1691 defsymbol(&Qweakness, "weakness");
1692 defsymbol(&Qvalue, "value");
1693 defsymbol(&Qkey_or_value, "key-or-value");
1694 defsymbol(&Qkey_and_value, "key-and-value");
1695 defsymbol(&Qrehash_size, "rehash-size");
1696 defsymbol(&Qrehash_threshold, "rehash-threshold");
1698 defsymbol(&Qweak, "weak"); /* obsolete */
1699 defsymbol(&Qkey_weak, "key-weak"); /* obsolete */
1700 defsymbol(&Qkey_or_value_weak, "key-or-value-weak"); /* obsolete */
1701 defsymbol(&Qvalue_weak, "value-weak"); /* obsolete */
1702 defsymbol(&Qnon_weak, "non-weak"); /* obsolete */
1704 defkeyword(&Q_test, ":test");
1705 defkeyword(&Q_size, ":size");
1706 defkeyword(&Q_rehash_size, ":rehash-size");
1707 defkeyword(&Q_rehash_threshold, ":rehash-threshold");
1708 defkeyword(&Q_weakness, ":weakness");
1709 defkeyword(&Q_type, ":type"); /* obsolete */
1715 morphisms[lrecord_type_hash_table].seq_impl = seq_hash_table;
1716 morphisms[lrecord_type_hash_table].aset_impl = dict_hash_table;
1720 void vars_of_elhash(void)
1722 /* This must NOT be staticpro'd */
1723 Vall_weak_hash_tables = Qnil;
1724 dump_add_weak_object_chain(&Vall_weak_hash_tables);
1727 /* elhash.c ends here */