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 */
34 Lisp_Object Qhash_tablep;
35 static Lisp_Object Qhashtable, Qhash_table;
36 static Lisp_Object Qweakness, Qvalue, Qkey_or_value, Qkey_and_value;
37 static Lisp_Object Vall_weak_hash_tables;
38 static Lisp_Object Qrehash_size, Qrehash_threshold;
39 static Lisp_Object Q_size, Q_weakness;
41 static Lisp_Object Q_rehash_size, Q_rehash_threshold;
43 /* obsolete as of 19990901 in xemacs-21.2 */
44 static Lisp_Object Qweak, Qkey_weak, Qvalue_weak, Qkey_or_value_weak;
45 static Lisp_Object Qnon_weak, Q_type;
48 #define HASH_TABLE_DEFAULT_SIZE 16
49 #define HASH_TABLE_DEFAULT_REHASH_SIZE 1.3
50 #define HASH_TABLE_MIN_SIZE 10
52 #define HASH_CODE(key, ht) \
53 ((((ht)->hash_function ? (ht)->hash_function (key) : LISP_HASH (key)) \
54 * (ht)->golden_ratio) \
57 #define KEYS_EQUAL_P(key1, key2, testfun) \
58 (EQ (key1, key2) || ((testfun) && (testfun) (key1, key2)))
60 #define LINEAR_PROBING_LOOP(probe, entries, size) \
62 !HENTRY_CLEAR_P (probe) || \
63 (probe == entries + size ? \
64 (probe = entries, !HENTRY_CLEAR_P (probe)) : 0); \
67 #ifndef ERROR_CHECK_HASH_TABLE
68 # ifdef ERROR_CHECK_TYPECHECK
69 # define ERROR_CHECK_HASH_TABLE 1
71 # define ERROR_CHECK_HASH_TABLE 0
75 #if ERROR_CHECK_HASH_TABLE
77 check_hash_table_invariants(hash_table_t ht)
79 assert(ht->count < ht->size);
80 assert(ht->count <= ht->rehash_count);
81 assert(ht->rehash_count < ht->size);
82 assert((fpfloat)ht->count * ht->rehash_threshold - 1 <=
83 (fpfloat)ht->rehash_count);
84 assert(HENTRY_CLEAR_P(ht->hentries + ht->size));
87 #define check_hash_table_invariants(ht)
90 /* We use linear probing instead of double hashing, despite its lack
91 of blessing by Knuth and company, because, as a result of the
92 increasing discrepancy between CPU speeds and memory speeds, cache
93 behavior is becoming increasingly important, e.g:
95 For a trivial loop, the penalty for non-sequential access of an array is:
96 - a factor of 3-4 on Pentium Pro 200 Mhz
97 - a factor of 10 on Ultrasparc 300 Mhz */
99 /* Return a suitable size for a hash table, with at least SIZE slots. */
101 hash_table_size(size_t requested_size)
103 /* Return some prime near, but greater than or equal to, SIZE.
104 Decades from the time of writing, someone will have a system large
105 enough that the list below will be too short... */
106 static const size_t primes[] = {
107 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
108 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
109 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
110 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
111 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
112 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
113 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
114 243370577, 316381771, 411296309, 534685237, 695090819,
116 1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
118 /* We've heard of binary search. */
120 for (low = 0, high = countof(primes) - 1; high - low > 1;) {
121 /* Loop Invariant: size < primes [high] */
122 int mid = (low + high) / 2;
123 if (primes[mid] < requested_size)
131 static int lisp_object_eql_equal(Lisp_Object obj1, Lisp_Object obj2)
133 return EQ(obj1, obj2) || (FLOATP(obj1)
134 && internal_equal(obj1, obj2, 0));
137 static hcode_t lisp_object_eql_hash(Lisp_Object obj)
139 return FLOATP(obj) ? internal_hash(obj, 0) : LISP_HASH(obj);
142 static int lisp_object_equal_equal(Lisp_Object obj1, Lisp_Object obj2)
144 return internal_equal(obj1, obj2, 0);
147 static hcode_t lisp_object_equal_hash(Lisp_Object obj)
149 return internal_hash(obj, 0);
152 static Lisp_Object mark_hash_table(Lisp_Object obj)
154 hash_table_t ht = XHASH_TABLE(obj);
156 /* If the hash table is weak, we don't want to mark the keys and
157 values (we scan over them after everything else has been marked,
158 and mark or remove them as necessary). */
159 if (ht->weakness == HASH_TABLE_NON_WEAK) {
160 for (hentry_t e = ht->hentries, sentinel = e + ht->size;
162 if (!HENTRY_CLEAR_P(e)) {
164 mark_object(e->value);
171 /* Equality of hash tables. Two hash tables are equal when they are of
172 the same weakness and test function, they have the same number of
173 elements, and for each key in the hash table, the values are `equal'.
175 This is similar to Common Lisp `equalp' of hash tables, with the
176 difference that CL requires the keys to be compared with the test
177 function, which we don't do. Doing that would require consing, and
178 consing is a bad idea in `equal'. Anyway, our method should provide
179 the same result -- if the keys are not equal according to the test
180 function, then Fgethash() in hash_table_equal_mapper() will fail. */
182 hash_table_equal(Lisp_Object hash_table1, Lisp_Object hash_table2, int depth)
184 hash_table_t ht1 = XHASH_TABLE(hash_table1);
185 hash_table_t ht2 = XHASH_TABLE(hash_table2);
187 if ((ht1->test_function != ht2->test_function) ||
188 (ht1->weakness != ht2->weakness) || (ht1->count != ht2->count)) {
193 for (hentry_t e = ht1->hentries, sntl = e + ht1->size; e < sntl; e++) {
194 if (!HENTRY_CLEAR_P(e)) {
195 /* Look up the key in the other hash table, and compare
197 Lisp_Object value_in_other =
198 Fgethash(e->key, hash_table2, Qunbound);
199 if (UNBOUNDP(value_in_other) ||
200 !internal_equal(e->value, value_in_other, depth)) {
201 return 0; /* Give up */
208 /* This is not a great hash function, but it _is_ correct and fast.
209 Examining all entries is too expensive, and examining a random
210 subset does not yield a correct hash function. */
211 static hcode_t hash_table_hash(Lisp_Object hash_table, int depth)
213 return XHASH_TABLE(hash_table)->count;
216 /* Printing hash tables.
218 This is non-trivial, because we use a readable structure-style
219 syntax for hash tables. This means that a typical hash table will be
220 readably printed in the form of:
222 #s(hash-table size 2 data (key1 value1 key2 value2))
224 The supported hash table structure keywords and their values are:
225 `test' (eql (or nil), eq or equal)
226 `size' (a natnum or nil)
227 `rehash-size' (a float)
228 `rehash-threshold' (a float)
229 `weakness' (nil, key, value, key-and-value, or key-or-value)
232 If `print-readably' is nil, then a simpler syntax is used, for example
234 #<hash-table size 2/13 data (key1 value1 key2 value2) 0x874d>
236 The data is truncated to four pairs, and the rest is shown with
237 `...'. This printer does not cons. */
239 /* Print the data of the hash table. This maps through a Lisp
240 hash table and prints key/value pairs using PRINTCHARFUN. */
242 print_hash_table_data(hash_table_t ht, Lisp_Object printcharfun)
246 write_c_string(" data (", printcharfun);
248 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
249 if (!HENTRY_CLEAR_P(e)) {
251 write_c_string(" ", printcharfun);
252 if (!print_readably && count > 3) {
253 write_c_string("...", printcharfun);
256 print_internal(e->key, printcharfun, 1);
257 write_c_string(" ", printcharfun);
258 print_internal(e->value, printcharfun, 1);
262 write_c_string(")", printcharfun);
266 print_hash_table(Lisp_Object obj, Lisp_Object printcharfun, int escapeflag)
268 hash_table_t ht = XHASH_TABLE(obj);
270 write_c_string(print_readably ? "#s(hash-table" : "#<hash-table",
273 /* These checks have a kludgy look to them, but they are safe.
274 Due to nature of hashing, you cannot use arbitrary
275 test functions anyway. */
276 if (!ht->test_function)
277 write_c_string(" test eq", printcharfun);
278 else if (ht->test_function == lisp_object_equal_equal)
279 write_c_string(" test equal", printcharfun);
280 else if (ht->test_function == lisp_object_eql_equal)
285 if (ht->count || !print_readably) {
287 write_fmt_str(printcharfun, " size %lu", (unsigned long)ht->count);
289 write_fmt_str(printcharfun, " size %lu/%lu",
290 (unsigned long)ht->count,
291 (unsigned long)ht->size);
294 if (ht->weakness != HASH_TABLE_NON_WEAK) {
295 write_fmt_str(printcharfun, " weakness %s",
296 (ht->weakness == HASH_TABLE_WEAK ? "key-and-value" :
297 ht->weakness == HASH_TABLE_KEY_WEAK ? "key" :
298 ht->weakness == HASH_TABLE_VALUE_WEAK ? "value" :
300 HASH_TABLE_KEY_VALUE_WEAK ? "key-or-value" :
301 "you-d-better-not-see-this"));
305 print_hash_table_data(ht, printcharfun);
308 write_c_string(")", printcharfun);
310 write_fmt_str(printcharfun, " 0x%x>", ht->header.uid);
313 static void finalize_hash_table(void *header, int for_disksave)
316 hash_table_t ht = (hash_table_t ) header;
323 static const struct lrecord_description hentry_description_1[] = {
324 {XD_LISP_OBJECT, offsetof(struct hentry_s, key)},
325 {XD_LISP_OBJECT, offsetof(struct hentry_s, value)},
329 static const struct struct_description hentry_description = {
330 sizeof(struct hentry_s),
334 const struct lrecord_description hash_table_description[] = {
335 {XD_SIZE_T, offsetof(struct hash_table_s, size)},
336 {XD_STRUCT_PTR, offsetof(struct hash_table_s, hentries),
337 XD_INDIRECT(0, 1), &hentry_description},
338 {XD_LO_LINK, offsetof(struct hash_table_s, next_weak)},
342 DEFINE_LRECORD_IMPLEMENTATION(
343 "hash-table", hash_table,
344 mark_hash_table, print_hash_table, finalize_hash_table,
345 hash_table_equal, hash_table_hash, hash_table_description,
346 struct hash_table_s);
349 xhash_table(Lisp_Object hash_table)
352 CHECK_HASH_TABLE(hash_table);
353 check_hash_table_invariants(XHASH_TABLE(hash_table));
354 return XHASH_TABLE(hash_table);
357 /************************************************************************/
358 /* Creation of Hash Tables */
359 /************************************************************************/
361 /* Creation of hash tables, without error-checking. */
362 static void compute_hash_table_derived_values(hash_table_t ht)
364 ht->rehash_count = (size_t)
365 ((fpfloat)ht->size * ht->rehash_threshold);
366 ht->golden_ratio = (size_t)
367 ((fpfloat)ht->size * (.6180339887 / (fpfloat)sizeof(Lisp_Object)));
371 make_standard_lisp_hash_table(
372 enum hash_table_test test,
373 size_t size, fpfloat rehash_size, fpfloat rehash_threshold,
374 enum hash_table_weakness weakness)
376 hash_table_hash_f hash_function = 0;
377 hash_table_test_f test_function = 0;
386 test_function = lisp_object_eql_equal;
387 hash_function = lisp_object_eql_hash;
390 case HASH_TABLE_EQUAL:
391 test_function = lisp_object_equal_equal;
392 hash_function = lisp_object_equal_hash;
399 return make_general_lisp_hash_table(hash_function, test_function,
400 size, rehash_size, rehash_threshold,
405 make_general_lisp_hash_table(
406 hash_table_hash_f hash_function, hash_table_test_f test_function,
407 size_t size, fpfloat rehash_size, fpfloat rehash_threshold,
408 enum hash_table_weakness weakness)
410 Lisp_Object hash_table;
411 hash_table_t ht = alloc_lcrecord_type(
412 struct hash_table_s, &lrecord_hash_table);
414 /* the categories are actually seq and dict, but use the per-type
415 implementation for a start */
416 ht->header.lheader.morphisms = (1<<cat_mk_lc);
418 ht->test_function = test_function;
419 ht->hash_function = hash_function;
420 ht->weakness = weakness;
422 ht->rehash_size = rehash_size > 1.0
424 : HASH_TABLE_DEFAULT_REHASH_SIZE;
426 ht->rehash_threshold = rehash_threshold > 0.0
428 : size > 4096 && !ht->test_function ? 0.7 : 0.6;
430 if (size < HASH_TABLE_MIN_SIZE)
431 size = HASH_TABLE_MIN_SIZE;
432 ht->size = hash_table_size(
433 (size_t)(((fpfloat)size / ht->rehash_threshold) + 1.0));
436 compute_hash_table_derived_values(ht);
438 /* We leave room for one never-occupied sentinel hentry at the end. */
439 ht->hentries = xnew_array_and_zero(struct hentry_s, ht->size + 1);
441 XSETHASH_TABLE(hash_table, ht);
443 if (weakness == HASH_TABLE_NON_WEAK) {
444 ht->next_weak = Qunbound;
446 ht->next_weak = Vall_weak_hash_tables,
447 Vall_weak_hash_tables = hash_table;
453 make_lisp_hash_table(size_t size,
454 enum hash_table_weakness weakness,
455 enum hash_table_test test)
457 return make_standard_lisp_hash_table(test, size, -1.0, -1.0, weakness);
460 /* Pretty reading of hash tables.
462 Here we use the existing structures mechanism (which is,
463 unfortunately, pretty cumbersome) for validating and instantiating
464 the hash tables. The idea is that the side-effect of reading a
465 #s(hash-table PLIST) object is creation of a hash table with desired
466 properties, and that the hash table is returned. */
468 /* Validation functions: each keyword provides its own validation
469 function. The errors should maybe be continuable, but it is
470 unclear how this would cope with ERRB. */
472 hash_table_size_validate(Lisp_Object keyword, Lisp_Object value,
475 #ifdef WITH_NUMBER_TYPES
476 if (!NILP(Fnonnegativep(value)))
479 maybe_signal_error(Qwrong_type_argument, list2(Qnonnegativep, value),
481 #else /* !WITH_NUMBER_TYPES */
485 maybe_signal_error(Qwrong_type_argument, list2(Qnatnump, value),
487 #endif /* WITH_NUMBER_TYPES */
491 static size_t decode_hash_table_size(Lisp_Object obj)
493 #ifdef WITH_NUMBER_TYPES
494 return NILP(obj) ? HASH_TABLE_DEFAULT_SIZE :
495 XINT(Fcoerce_number(obj, Qint, Qnil));
497 return NILP(obj) ? HASH_TABLE_DEFAULT_SIZE : XINT(obj);
502 hash_table_weakness_validate(Lisp_Object keyword, Lisp_Object value,
511 if (EQ(value, Qkey_and_value))
513 if (EQ(value, Qkey_or_value))
515 if (EQ(value, Qvalue))
518 /* Following values are obsolete as of 19990901 in xemacs-21.2 */
519 if (EQ(value, Qnon_weak))
521 if (EQ(value, Qweak))
523 if (EQ(value, Qkey_weak))
525 if (EQ(value, Qkey_or_value_weak))
527 if (EQ(value, Qvalue_weak))
530 maybe_signal_simple_error("Invalid hash table weakness",
531 value, Qhash_table, errb);
535 static enum hash_table_weakness decode_hash_table_weakness(Lisp_Object obj)
538 return HASH_TABLE_NON_WEAK;
540 return HASH_TABLE_WEAK;
541 if (EQ(obj, Qkey_and_value))
542 return HASH_TABLE_WEAK;
544 return HASH_TABLE_KEY_WEAK;
545 if (EQ(obj, Qkey_or_value))
546 return HASH_TABLE_KEY_VALUE_WEAK;
548 return HASH_TABLE_VALUE_WEAK;
550 /* Following values are obsolete as of 19990901 in xemacs-21.2 */
551 if (EQ(obj, Qnon_weak))
552 return HASH_TABLE_NON_WEAK;
554 return HASH_TABLE_WEAK;
555 if (EQ(obj, Qkey_weak))
556 return HASH_TABLE_KEY_WEAK;
557 if (EQ(obj, Qkey_or_value_weak))
558 return HASH_TABLE_KEY_VALUE_WEAK;
559 if (EQ(obj, Qvalue_weak))
560 return HASH_TABLE_VALUE_WEAK;
562 signal_simple_error("Invalid hash table weakness", obj);
563 return HASH_TABLE_NON_WEAK; /* not reached */
567 hash_table_test_validate(Lisp_Object keyword, Lisp_Object value,
574 if (EQ(value, Qequal))
579 maybe_signal_simple_error("Invalid hash table test",
580 value, Qhash_table, errb);
584 static enum hash_table_test decode_hash_table_test(Lisp_Object obj)
587 return HASH_TABLE_EQL;
589 return HASH_TABLE_EQ;
591 return HASH_TABLE_EQUAL;
593 return HASH_TABLE_EQL;
595 signal_simple_error("Invalid hash table test", obj);
596 return HASH_TABLE_EQ; /* not reached */
600 hash_table_rehash_size_validate(Lisp_Object keyword, Lisp_Object value,
603 if (!FLOATP(value)) {
604 maybe_signal_error(Qwrong_type_argument, list2(Qfloatp, value),
610 fpfloat rehash_size = XFLOAT_DATA(value);
611 if (rehash_size <= 1.0) {
612 maybe_signal_simple_error
613 ("Hash table rehash size must be greater than 1.0",
614 value, Qhash_table, errb);
622 static fpfloat decode_hash_table_rehash_size(Lisp_Object rehash_size)
624 return NILP(rehash_size) ? -1.0 : XFLOAT_DATA(rehash_size);
628 hash_table_rehash_threshold_validate(Lisp_Object keyword, Lisp_Object value,
631 if (!FLOATP(value)) {
632 maybe_signal_error(Qwrong_type_argument, list2(Qfloatp, value),
638 fpfloat rehash_threshold = XFLOAT_DATA(value);
639 if (rehash_threshold <= 0.0 || rehash_threshold >= 1.0) {
640 maybe_signal_simple_error
641 ("Hash table rehash threshold must be between 0.0 and 1.0",
642 value, Qhash_table, errb);
650 static fpfloat decode_hash_table_rehash_threshold(Lisp_Object rehash_threshold)
652 return NILP(rehash_threshold) ? -1.0 : XFLOAT_DATA(rehash_threshold);
656 hash_table_data_validate(Lisp_Object keyword, Lisp_Object value,
661 GET_EXTERNAL_LIST_LENGTH(value, len);
664 maybe_signal_simple_error
665 ("Hash table data must have alternating key/value pairs",
666 value, Qhash_table, errb);
672 /* The actual instantiation of a hash table. This does practically no
673 error checking, because it relies on the fact that the paranoid
674 functions above have error-checked everything to the last details.
675 If this assumption is wrong, we will get a crash immediately (with
676 error-checking compiled in), and we'll know if there is a bug in
677 the structure mechanism. So there. */
678 static Lisp_Object hash_table_instantiate(Lisp_Object plist)
680 Lisp_Object hash_table;
681 Lisp_Object test = Qnil;
682 Lisp_Object size = Qnil;
683 Lisp_Object rehash_size = Qnil;
684 Lisp_Object rehash_threshold = Qnil;
685 Lisp_Object weakness = Qnil;
686 Lisp_Object data = Qnil;
688 while (!NILP(plist)) {
689 Lisp_Object key, value;
697 else if (EQ(key, Qsize))
699 else if (EQ(key, Qrehash_size))
701 else if (EQ(key, Qrehash_threshold))
702 rehash_threshold = value;
703 else if (EQ(key, Qweakness))
705 else if (EQ(key, Qdata))
707 else if (EQ(key, Qtype)) /*obsolete */
713 /* Create the hash table. */
714 hash_table = make_standard_lisp_hash_table
715 (decode_hash_table_test(test),
716 decode_hash_table_size(size),
717 decode_hash_table_rehash_size(rehash_size),
718 decode_hash_table_rehash_threshold(rehash_threshold),
719 decode_hash_table_weakness(weakness));
721 /* I'm not sure whether this can GC, but better safe than sorry. */
726 /* And fill it with data. */
727 while (!NILP(data)) {
728 Lisp_Object key, value;
733 Fputhash(key, value, hash_table);
742 structure_type_create_hash_table_structure_name(Lisp_Object structure_name)
744 struct structure_type *st;
746 st = define_structure_type(structure_name, 0, hash_table_instantiate);
747 define_structure_type_keyword(st, Qtest, hash_table_test_validate);
748 define_structure_type_keyword(st, Qsize, hash_table_size_validate);
749 define_structure_type_keyword(st, Qrehash_size,
750 hash_table_rehash_size_validate);
751 define_structure_type_keyword(st, Qrehash_threshold,
752 hash_table_rehash_threshold_validate);
753 define_structure_type_keyword(st, Qweakness,
754 hash_table_weakness_validate);
755 define_structure_type_keyword(st, Qdata, hash_table_data_validate);
757 /* obsolete as of 19990901 in xemacs-21.2 */
758 define_structure_type_keyword(st, Qtype, hash_table_weakness_validate);
761 /* Create a built-in Lisp structure type named `hash-table'.
762 We make #s(hashtable ...) equivalent to #s(hash-table ...),
763 for backward compatibility.
764 This is called from emacs.c. */
765 void structure_type_create_hash_table(void)
767 structure_type_create_hash_table_structure_name(Qhash_table);
768 structure_type_create_hash_table_structure_name(Qhashtable); /* compat */
771 /************************************************************************/
772 /* Definition of Lisp-visible methods */
773 /************************************************************************/
775 DEFUN("hash-table-p", Fhash_table_p, 1, 1, 0, /*
776 Return t if OBJECT is a hash table, else nil.
780 return HASH_TABLEP(object) ? Qt : Qnil;
783 DEFUN("make-hash-table", Fmake_hash_table, 0, MANY, 0, /*
784 Return a new empty hash table object.
785 Use Common Lisp style keywords to specify hash table properties.
786 (make-hash-table &key test size rehash-size rehash-threshold weakness)
788 Keyword :test can be `eq', `eql' (default) or `equal'.
789 Comparison between keys is done using this function.
790 If speed is important, consider using `eq'.
791 When hash table keys may be strings, you will likely need to use `equal'.
793 Keyword :size specifies the number of keys likely to be inserted.
794 This number of entries can be inserted without enlarging the hash table.
796 Keyword :rehash-size must be a float greater than 1.0, and specifies
797 the factor by which to increase the size of the hash table when enlarging.
799 Keyword :rehash-threshold must be a float between 0.0 and 1.0,
800 and specifies the load factor of the hash table which triggers enlarging.
802 Non-standard keyword :weakness can be `nil' (default), `t', `key-and-value',
803 `key', `value' or `key-or-value'. `t' is an alias for `key-and-value'.
805 A key-and-value-weak hash table, also known as a fully-weak or simply
806 as a weak hash table, is one whose pointers do not count as GC
807 referents: for any key-value pair in the hash table, if the only
808 remaining pointer to either the key or the value is in a weak hash
809 table, then the pair will be removed from the hash table, and the key
810 and value collected. A non-weak hash table (or any other pointer)
811 would prevent the object from being collected.
813 A key-weak hash table is similar to a fully-weak hash table except that
814 a key-value pair will be removed only if the key remains unmarked
815 outside of weak hash tables. The pair will remain in the hash table if
816 the key is pointed to by something other than a weak hash table, even
819 A value-weak hash table is similar to a fully-weak hash table except
820 that a key-value pair will be removed only if the value remains
821 unmarked outside of weak hash tables. The pair will remain in the
822 hash table if the value is pointed to by something other than a weak
823 hash table, even if the key is not.
825 A key-or-value-weak hash table is similar to a fully-weak hash table except
826 that a key-value pair will be removed only if the value and the key remain
827 unmarked outside of weak hash tables. The pair will remain in the
828 hash table if the value or key are pointed to by something other than a weak
829 hash table, even if the other is not.
831 (int nargs, Lisp_Object * args))
834 Lisp_Object test = Qnil;
835 Lisp_Object size = Qnil;
836 Lisp_Object rehash_size = Qnil;
837 Lisp_Object rehash_threshold = Qnil;
838 Lisp_Object weakness = Qnil;
840 while (i + 1 < nargs) {
841 Lisp_Object keyword = args[i++];
842 Lisp_Object value = args[i++];
844 if (EQ(keyword, Q_test))
846 else if (EQ(keyword, Q_size))
848 else if (EQ(keyword, Q_rehash_size))
850 else if (EQ(keyword, Q_rehash_threshold))
851 rehash_threshold = value;
852 else if (EQ(keyword, Q_weakness))
854 else if (EQ(keyword, Q_type)) /*obsolete */
858 ("Invalid hash table property keyword", keyword);
862 signal_simple_error("Hash table property requires a value",
865 #define VALIDATE_VAR(var) \
866 if (!NILP (var)) hash_table_##var##_validate (Q##var, var, ERROR_ME);
870 VALIDATE_VAR(rehash_size);
871 VALIDATE_VAR(rehash_threshold);
872 VALIDATE_VAR(weakness);
874 return make_standard_lisp_hash_table
875 (decode_hash_table_test(test),
876 decode_hash_table_size(size),
877 decode_hash_table_rehash_size(rehash_size),
878 decode_hash_table_rehash_threshold(rehash_threshold),
879 decode_hash_table_weakness(weakness));
882 DEFUN("copy-hash-table", Fcopy_hash_table, 1, 1, 0, /*
883 Return a new hash table containing the same keys and values as HASH-TABLE.
884 The keys and values will not themselves be copied.
888 const hash_table_t ht_old = xhash_table(hash_table);
889 hash_table_t ht = alloc_lcrecord_type(
890 struct hash_table_s, &lrecord_hash_table);
892 copy_lcrecord(ht, ht_old);
894 ht->hentries = xnew_array(struct hentry_s, ht_old->size + 1);
895 memcpy(ht->hentries, ht_old->hentries,
896 (ht_old->size + 1) * sizeof(struct hentry_s));
898 /* the categories are actually seq and dict, but use the per-type
899 implementation for a start */
900 ht->header.lheader.morphisms = (1<<cat_mk_lc);
902 XSETHASH_TABLE(hash_table, ht);
904 if (!EQ(ht->next_weak, Qunbound)) {
905 ht->next_weak = Vall_weak_hash_tables,
906 Vall_weak_hash_tables = hash_table;
912 resize_hash_table(hash_table_t ht, size_t new_size)
914 hentry_t old_entries, new_entries;
920 old_entries = ht->hentries;
922 ht->hentries = xnew_array_and_zero(struct hentry_s, new_size + 1);
923 new_entries = ht->hentries;
925 compute_hash_table_derived_values(ht);
927 for (hentry_t e = old_entries, sentinel = e + old_size;
929 if (!HENTRY_CLEAR_P(e)) {
930 hentry_t probe = new_entries + HASH_CODE(e->key, ht);
931 LINEAR_PROBING_LOOP(probe, new_entries, new_size);
935 if (!DUMPEDP(old_entries)) {
940 /* After a hash table has been saved to disk and later restored by the
941 portable dumper, it contains the same objects, but their addresses
942 and thus their HASH_CODEs have changed. */
944 pdump_reorganize_hash_table(Lisp_Object hash_table)
946 const hash_table_t ht = xhash_table(hash_table);
947 hentry_t new_entries =
948 xnew_array_and_zero(struct hentry_s, ht->size + 1);
950 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
951 if (!HENTRY_CLEAR_P(e)) {
952 hentry_t probe = new_entries + HASH_CODE(e->key, ht);
953 LINEAR_PROBING_LOOP(probe, new_entries, ht->size);
957 memcpy(ht->hentries, new_entries, ht->size * sizeof(struct hentry_s));
963 static void enlarge_hash_table(hash_table_t ht)
966 hash_table_size((size_t) ((fpfloat)ht->size * ht->rehash_size));
967 resize_hash_table(ht, new_size);
971 find_hentry(Lisp_Object key, const hash_table_t ht)
973 hash_table_test_f test_function = ht->test_function;
974 hentry_t entries = ht->hentries;
975 hentry_t probe = entries + HASH_CODE(key, ht);
977 LINEAR_PROBING_LOOP(probe, entries, ht->size)
978 if (KEYS_EQUAL_P(probe->key, key, test_function))
984 static inline Lisp_Object
985 dict_ht_get(hash_table_t ht, Lisp_Object key, Lisp_Object _default)
987 const hentry_t e = find_hentry(key, ht);
989 return HENTRY_CLEAR_P(e) ? _default : e->value;
992 DEFUN("gethash", Fgethash, 2, 3, 0, /*
993 Find hash value for KEY in HASH-TABLE.
994 If there is no corresponding value, return DEFAULT (which defaults to nil).
996 (key, hash_table, default_))
998 return dict_ht_get(xhash_table(hash_table), key, default_);
1001 static inline Lisp_Object
1002 dict_ht_put(hash_table_t ht, Lisp_Object key, Lisp_Object value)
1004 hentry_t e = find_hentry(key, ht);
1006 if (!HENTRY_CLEAR_P(e))
1007 return e->value = value;
1012 if (++ht->count >= ht->rehash_count) {
1013 enlarge_hash_table(ht);
1019 DEFUN("puthash", Fputhash, 3, 3, 0, /*
1020 Hash KEY to VALUE in HASH-TABLE.
1022 (key, value, hash_table))
1024 return dict_ht_put(xhash_table(hash_table), key, value);
1027 /* Remove hentry pointed at by PROBE.
1028 Subsequent entries are removed and reinserted.
1029 We don't use tombstones - too wasteful. */
1030 static void remhash_1(hash_table_t ht, hentry_t entries, hentry_t probe)
1032 size_t size = ht->size;
1033 CLEAR_HENTRY(probe);
1037 LINEAR_PROBING_LOOP(probe, entries, size) {
1038 Lisp_Object key = probe->key;
1039 hentry_t probe2 = entries + HASH_CODE(key, ht);
1040 LINEAR_PROBING_LOOP(probe2, entries, size)
1041 if (EQ(probe2->key, key))
1042 /* hentry at probe doesn't need to move. */
1043 goto continue_outer_loop;
1044 /* Move hentry from probe to new home at probe2. */
1046 CLEAR_HENTRY(probe);
1047 continue_outer_loop:continue;
1051 static inline Lisp_Object
1052 dict_ht_remove(hash_table_t ht, Lisp_Object key)
1054 hentry_t e = find_hentry(key, ht);
1056 if (HENTRY_CLEAR_P(e)) {
1060 remhash_1(ht, ht->hentries, e);
1064 DEFUN("remhash", Fremhash, 2, 2, 0, /*
1065 Remove the entry for KEY from HASH-TABLE.
1066 Do nothing if there is no entry for KEY in HASH-TABLE.
1070 return dict_ht_remove(xhash_table(hash_table), key);
1073 DEFUN("clrhash", Fclrhash, 1, 1, 0, /*
1074 Remove all entries from HASH-TABLE, leaving it empty.
1078 hash_table_t ht = xhash_table(hash_table);
1080 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1088 /************************************************************************/
1089 /* Accessor Functions */
1090 /************************************************************************/
1092 DEFUN("hash-table-count", Fhash_table_count, 1, 1, 0, /*
1093 Return the number of entries in HASH-TABLE.
1097 return make_int(xhash_table(hash_table)->count);
1100 DEFUN("hash-table-test", Fhash_table_test, 1, 1, 0, /*
1101 Return the test function of HASH-TABLE.
1102 This can be one of `eq', `eql' or `equal'.
1106 hash_table_test_f fun = xhash_table(hash_table)->test_function;
1108 return (fun == lisp_object_eql_equal ? Qeql :
1109 fun == lisp_object_equal_equal ? Qequal : Qeq);
1113 dict_ht_size(const hash_table_t ht)
1118 DEFUN("hash-table-size", Fhash_table_size, 1, 1, 0, /*
1119 Return the size of HASH-TABLE.
1120 This is the current number of slots in HASH-TABLE, whether occupied or not.
1124 return make_int(xhash_table(hash_table)->size);
1127 DEFUN("hash-table-rehash-size", Fhash_table_rehash_size, 1, 1, 0, /*
1128 Return the current rehash size of HASH-TABLE.
1129 This is a float greater than 1.0; the factor by which HASH-TABLE
1130 is enlarged when the rehash threshold is exceeded.
1134 return make_float(xhash_table(hash_table)->rehash_size);
1137 DEFUN("hash-table-rehash-threshold", Fhash_table_rehash_threshold, 1, 1, 0, /*
1138 Return the current rehash threshold of HASH-TABLE.
1139 This is a float between 0.0 and 1.0; the maximum `load factor' of HASH-TABLE,
1140 beyond which the HASH-TABLE is enlarged by rehashing.
1144 return make_float(xhash_table(hash_table)->rehash_threshold);
1147 DEFUN("hash-table-weakness", Fhash_table_weakness, 1, 1, 0, /*
1148 Return the weakness of HASH-TABLE.
1149 This can be one of `nil', `key-and-value', `key-or-value', `key' or `value'.
1153 switch (xhash_table(hash_table)->weakness) {
1154 case HASH_TABLE_WEAK:
1155 return Qkey_and_value;
1156 case HASH_TABLE_KEY_WEAK:
1158 case HASH_TABLE_KEY_VALUE_WEAK:
1159 return Qkey_or_value;
1160 case HASH_TABLE_VALUE_WEAK:
1164 case HASH_TABLE_NON_WEAK:
1165 case HASH_TABLE_KEY_CAR_WEAK:
1166 case HASH_TABLE_VALUE_CAR_WEAK:
1167 case HASH_TABLE_KEY_CAR_VALUE_WEAK:
1174 /* obsolete as of 19990901 in xemacs-21.2 */
1175 DEFUN("hash-table-type", Fhash_table_type, 1, 1, 0, /*
1176 Return the type of HASH-TABLE.
1177 This can be one of `non-weak', `weak', `key-weak' or `value-weak'.
1181 switch (xhash_table(hash_table)->weakness) {
1182 case HASH_TABLE_WEAK:
1184 case HASH_TABLE_KEY_WEAK:
1186 case HASH_TABLE_KEY_VALUE_WEAK:
1187 return Qkey_or_value_weak;
1188 case HASH_TABLE_VALUE_WEAK:
1191 /* the bloody rest */
1192 case HASH_TABLE_NON_WEAK:
1193 case HASH_TABLE_KEY_CAR_WEAK:
1194 case HASH_TABLE_VALUE_CAR_WEAK:
1195 case HASH_TABLE_KEY_CAR_VALUE_WEAK:
1202 /************************************************************************/
1203 /* Mapping Functions */
1204 /************************************************************************/
1205 DEFUN("maphash", Fmaphash, 2, 2, 0, /*
1206 Map FUNCTION over entries in HASH-TABLE, calling it with two args,
1207 each key and value in HASH-TABLE.
1209 FUNCTION may not modify HASH-TABLE, with the one exception that FUNCTION
1210 may remhash or puthash the entry currently being processed by FUNCTION.
1212 (function, hash_table))
1214 const hash_table_t ht = xhash_table(hash_table);
1216 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1217 if (!HENTRY_CLEAR_P(e)) {
1218 Lisp_Object args[3], key;
1224 Ffuncall(countof(args), args);
1225 /* Has FUNCTION done a remhash? */
1226 if (!EQ(key, e->key) && !HENTRY_CLEAR_P(e))
1233 /* #### If the Lisp function being called does a puthash and this
1234 #### causes the hash table to be resized, the results will be quite
1235 #### random and we will likely crash. To fix this, either set a
1236 #### flag in the hash table while we're mapping and signal an error
1237 #### when new entries are added, or fix things to make this
1238 #### operation work properly, like this: Store two hash tables in
1239 #### each hash table object -- the second one is written to when
1240 #### you do a puthash inside of a mapping operation, and the
1241 #### various operations need to check both hash tables for entries.
1242 #### As soon as the last maphash over a particular hash table
1243 #### object terminates, the entries in the second table are added
1244 #### to the first (using an unwind-protect). --ben */
1246 /* Map *C* function FUNCTION over the elements of a lisp hash table. */
1248 elisp_maphash(maphash_f function, Lisp_Object hash_table, void *extra_arg)
1250 const hash_table_t ht = XHASH_TABLE(hash_table);
1252 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1253 if (!HENTRY_CLEAR_P(e)) {
1257 if (function(key, e->value, extra_arg)) {
1260 /* Has FUNCTION done a remhash? */
1261 if (!EQ(key, e->key) && !HENTRY_CLEAR_P(e)) {
1268 /* Remove all elements of a lisp hash table satisfying *C* predicate
1271 elisp_map_remhash(maphash_f predicate, Lisp_Object hash_table, void *extra_arg)
1273 hash_table_t ht = XHASH_TABLE(hash_table);
1276 for (hentry_t e = entries = ht->hentries, sentinel = e + ht->size;
1277 e < sentinel; e++) {
1278 if (!HENTRY_CLEAR_P(e)) {
1280 if (predicate(e->key, e->value, extra_arg)) {
1281 remhash_1(ht, entries, e);
1282 if (!HENTRY_CLEAR_P(e)) {
1290 /************************************************************************/
1291 /* garbage collecting weak hash tables */
1292 /************************************************************************/
1293 #define MARK_OBJ(obj) \
1295 Lisp_Object mo_obj = (obj); \
1296 if (!marked_p (mo_obj)) { \
1297 mark_object (mo_obj); \
1302 /* Complete the marking for semi-weak hash tables. */
1303 int finish_marking_weak_hash_tables(void)
1305 Lisp_Object hash_table;
1308 for (hash_table = Vall_weak_hash_tables;
1310 hash_table = XHASH_TABLE(hash_table)->next_weak) {
1311 const hash_table_t ht = XHASH_TABLE(hash_table);
1312 hentry_t e = ht->hentries;
1313 const hentry_t sentinel = e + ht->size;
1315 if (!marked_p(hash_table)) {
1316 /* The hash table is probably garbage. Ignore it. */
1320 /* Now, scan over all the pairs. For all pairs that are
1321 half-marked, we may need to mark the other half if we're
1322 keeping this pair. */
1323 switch (ht->weakness) {
1324 case HASH_TABLE_KEY_WEAK:
1325 for (; e < sentinel; e++) {
1326 if (!HENTRY_CLEAR_P(e)) {
1327 if (marked_p(e->key)) {
1334 case HASH_TABLE_VALUE_WEAK:
1335 for (; e < sentinel; e++) {
1336 if (!HENTRY_CLEAR_P(e)) {
1337 if (marked_p(e->value)) {
1344 case HASH_TABLE_KEY_VALUE_WEAK:
1345 for (; e < sentinel; e++) {
1346 if (!HENTRY_CLEAR_P(e)) {
1347 if (marked_p(e->value)) {
1349 } else if (marked_p(e->key)) {
1356 case HASH_TABLE_KEY_CAR_WEAK:
1357 for (; e < sentinel; e++) {
1358 if (!HENTRY_CLEAR_P(e)) {
1360 || marked_p(XCAR(e->key))) {
1368 /* We seem to be sprouting new weakness types at an
1369 alarming rate. At least this is not externally
1370 visible - and in fact all of these KEY_CAR_* types
1371 are only used by the glyph code. */
1372 case HASH_TABLE_KEY_CAR_VALUE_WEAK:
1373 for (; e < sentinel; e++) {
1374 if (!HENTRY_CLEAR_P(e)) {
1376 || marked_p(XCAR(e->key))) {
1379 } else if (marked_p(e->value)) {
1386 case HASH_TABLE_VALUE_CAR_WEAK:
1387 for (; e < sentinel; e++) {
1388 if (!HENTRY_CLEAR_P(e)) {
1389 if (!CONSP(e->value)
1390 || marked_p(XCAR(e->value))) {
1399 case HASH_TABLE_NON_WEAK:
1400 case HASH_TABLE_WEAK:
1409 void prune_weak_hash_tables(void)
1411 Lisp_Object hash_table, prev = Qnil;
1413 for (hash_table = Vall_weak_hash_tables; !NILP(hash_table);
1414 hash_table = XHASH_TABLE(hash_table)->next_weak) {
1415 if (!marked_p(hash_table)) {
1416 /* This hash table itself is garbage. Remove it from
1419 Vall_weak_hash_tables =
1420 XHASH_TABLE(hash_table)->next_weak;
1422 XHASH_TABLE(prev)->next_weak =
1423 XHASH_TABLE(hash_table)->next_weak;
1425 /* Now, scan over all the pairs. Remove all of the pairs
1426 in which the key or value, or both, is unmarked
1427 (depending on the weakness of the hash table). */
1428 hash_table_t ht = XHASH_TABLE(hash_table);
1429 hentry_t entries = ht->hentries;
1430 hentry_t sentinel = entries + ht->size;
1432 for (hentry_t e = entries; e < sentinel; e++) {
1433 if (!HENTRY_CLEAR_P(e)) {
1435 if (!marked_p(e->key) ||
1436 !marked_p(e->value)) {
1437 remhash_1(ht, entries, e);
1438 if (!HENTRY_CLEAR_P(e)) {
1451 /* Return a hash value for an array of Lisp_Objects of size SIZE. */
1454 internal_array_hash(const Lisp_Object *arr, size_t size, int depth)
1460 for (size_t i = 0; i < size; i++) {
1461 hash = HASH2(hash, internal_hash(arr[i], depth));
1466 /* just pick five elements scattered throughout the array.
1467 A slightly better approach would be to offset by some
1468 noise factor from the points chosen below. */
1469 for (int i = 0; i < 5; i++) {
1470 hash = HASH2(hash, internal_hash(arr[i * size / 5], depth));
1475 /* Return a hash value for a Lisp_Object. This is for use when hashing
1476 objects with the comparison being `equal' (for `eq', you can just
1477 use the Lisp_Object itself as the hash value). You need to make a
1478 tradeoff between the speed of the hash function and how good the
1479 hashing is. In particular, the hash function needs to be FAST,
1480 so you can't just traipse down the whole tree hashing everything
1481 together. Most of the time, objects will differ in the first
1482 few elements you hash. Thus, we only go to a short depth (5)
1483 and only hash at most 5 elements out of a vector. Theoretically
1484 we could still take 5^5 time (a big big number) to compute a
1485 hash, but practically this won't ever happen. */
1488 internal_hash(const Lisp_Object obj, int depth)
1492 if (CONSP(obj) && !CONSP(XCDR(obj))) {
1493 /* special case for '(a . b) conses */
1494 return HASH2(internal_hash(XCAR(obj), depth + 1),
1495 internal_hash(XCDR(obj), depth + 1));
1496 } else if (CONSP(obj)) {
1497 /* no point in worrying about tail recursion, since we're not
1499 Lisp_Object o = obj;
1501 hcode_t hash = internal_hash(XCAR(o), depth+1);
1504 for (int s = 1; s < 6 && CONSP(o); o = XCDR(o), s++) {
1505 hcode_t h = internal_hash(XCAR(o), depth+1);
1506 hash = HASH3(hash, h, s);
1511 return hash_string(XSTRING_DATA(obj), XSTRING_LENGTH(obj));
1513 if (LRECORDP(obj)) {
1514 const struct lrecord_implementation
1515 *imp = XRECORD_LHEADER_IMPLEMENTATION(obj);
1517 return imp->hash(obj, depth);
1520 return LISP_HASH(obj);
1523 DEFUN("sxhash", Fsxhash, 1, 1, 0, /*
1524 Return a hash value for OBJECT.
1525 \(equal obj1 obj2) implies (= (sxhash obj1) (sxhash obj2)).
1529 return make_int(internal_hash(object, 0));
1533 /* the seq/dict implementation */
1534 /* iterator stuff, only needed for dict so make it static */
1536 ht_iter_init(dict_t d, dict_iter_t di)
1538 const hash_table_t ht = (hash_table_t)d;
1541 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1542 if (!HENTRY_CLEAR_P(e)) {
1552 ht_iter_fini(dict_iter_t di)
1554 di->dict = di->data = NULL;
1559 ht_diter_next(dict_iter_t di, Lisp_Object *key, Lisp_Object *val)
1561 hentry_t e = di->data;
1562 const hash_table_t ht = (hash_table_t)di->dict;
1564 if (UNLIKELY(e == NULL)) {
1565 *key = *val = Qnull_pointer;
1572 /* wind to next hentry */
1573 for (const hentry_t last = ht->hentries + ht->size; ++e < last;) {
1574 if (!HENTRY_CLEAR_P(e)) {
1584 ht_siter_next(seq_iter_t si, void **elm)
1586 hentry_t e = si->data;
1587 const hash_table_t ht = (hash_table_t)si->seq;
1589 if (UNLIKELY(e == NULL)) {
1590 *elm = Qnull_pointer;
1594 *elm = (void*)e->key;
1596 /* wind to next hentry */
1597 for (const hentry_t last = ht->hentries + ht->size; ++e < last;) {
1598 if (!HENTRY_CLEAR_P(e)) {
1608 ht_iter_reset(seq_iter_t si)
1610 const hash_table_t ht = (hash_table_t)si->seq;
1612 for (hentry_t e = ht->hentries, sntl = e + ht->size; e < sntl; e++) {
1613 if (!HENTRY_CLEAR_P(e)) {
1623 ht_explode(void *restrict tgt[], size_t ntgt, seq_t s)
1625 volatile size_t i = 0;
1626 const hash_table_t ht = (hash_table_t)s;
1628 for (hentry_t e = ht->hentries, sntl = e + ht->size;
1629 e < sntl && i < ntgt; e++) {
1630 if (!HENTRY_CLEAR_P(e)) {
1631 tgt[i++] = (void*)e->key;
1638 /************************************************************************/
1639 /* initialization */
1640 /************************************************************************/
1642 static struct seq_impl_s __shash_table = {
1643 .length_f = (seq_length_f)dict_ht_size,
1644 .iter_init_f = (seq_iter_init_f)ht_iter_init,
1645 .iter_next_f = ht_siter_next,
1646 .iter_fini_f = (seq_iter_fini_f)ht_iter_fini,
1647 .iter_reset_f = ht_iter_reset,
1648 .explode_f = ht_explode,
1651 static struct dict_impl_s __dhash_table = {
1652 .size_f = (dict_size_f)dict_ht_size,
1653 .put_f = (dict_put_f)dict_ht_put,
1654 .get_f = (dict_get_f)dict_ht_get,
1655 .remove_f = (dict_remove_f)dict_ht_remove,
1656 .iter_init_f = ht_iter_init,
1657 .iter_next_f = ht_diter_next,
1658 .iter_fini_f = ht_iter_fini,
1661 /* deal with seq interface */
1662 const seq_impl_t seq_hash_table = &__shash_table;
1663 /* deal with dict interface */
1664 const dict_impl_t dict_hash_table = &__dhash_table;
1666 void syms_of_elhash(void)
1668 INIT_LRECORD_IMPLEMENTATION(hash_table);
1670 DEFSUBR(Fhash_table_p);
1671 DEFSUBR(Fmake_hash_table);
1672 DEFSUBR(Fcopy_hash_table);
1678 DEFSUBR(Fhash_table_count);
1679 DEFSUBR(Fhash_table_test);
1680 DEFSUBR(Fhash_table_size);
1681 DEFSUBR(Fhash_table_rehash_size);
1682 DEFSUBR(Fhash_table_rehash_threshold);
1683 DEFSUBR(Fhash_table_weakness);
1684 DEFSUBR(Fhash_table_type); /* obsolete */
1687 DEFSUBR(Finternal_hash_value);
1690 defsymbol(&Qhash_tablep, "hash-table-p");
1691 defsymbol(&Qhash_table, "hash-table");
1692 defsymbol(&Qhashtable, "hashtable");
1693 defsymbol(&Qweakness, "weakness");
1694 defsymbol(&Qvalue, "value");
1695 defsymbol(&Qkey_or_value, "key-or-value");
1696 defsymbol(&Qkey_and_value, "key-and-value");
1697 defsymbol(&Qrehash_size, "rehash-size");
1698 defsymbol(&Qrehash_threshold, "rehash-threshold");
1700 defsymbol(&Qweak, "weak"); /* obsolete */
1701 defsymbol(&Qkey_weak, "key-weak"); /* obsolete */
1702 defsymbol(&Qkey_or_value_weak, "key-or-value-weak"); /* obsolete */
1703 defsymbol(&Qvalue_weak, "value-weak"); /* obsolete */
1704 defsymbol(&Qnon_weak, "non-weak"); /* obsolete */
1706 defkeyword(&Q_test, ":test");
1707 defkeyword(&Q_size, ":size");
1708 defkeyword(&Q_rehash_size, ":rehash-size");
1709 defkeyword(&Q_rehash_threshold, ":rehash-threshold");
1710 defkeyword(&Q_weakness, ":weakness");
1711 defkeyword(&Q_type, ":type"); /* obsolete */
1717 morphisms[lrecord_type_hash_table].seq_impl = seq_hash_table;
1718 morphisms[lrecord_type_hash_table].aset_impl = dict_hash_table;
1722 void vars_of_elhash(void)
1724 /* This must NOT be staticpro'd */
1725 Vall_weak_hash_tables = Qnil;
1726 dump_add_weak_object_chain(&Vall_weak_hash_tables);
1729 /* elhash.c ends here */