|
428
|
1 /* Implementation of the hash table lisp object type.
|
|
|
2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
|
|
2421
|
3 Copyright (C) 1995, 1996, 2002, 2004 Ben Wing.
|
|
428
|
4 Copyright (C) 1997 Free Software Foundation, Inc.
|
|
|
5
|
|
|
6 This file is part of XEmacs.
|
|
|
7
|
|
|
8 XEmacs is free software; you can redistribute it and/or modify it
|
|
|
9 under the terms of the GNU General Public License as published by the
|
|
|
10 Free Software Foundation; either version 2, or (at your option) any
|
|
|
11 later version.
|
|
|
12
|
|
|
13 XEmacs is distributed in the hope that it will be useful, but WITHOUT
|
|
|
14 ANY WARRANTY; without even the implied warranty of MERCNTABILITY or
|
|
|
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
16 for more details.
|
|
|
17
|
|
|
18 You should have received a copy of the GNU General Public License
|
|
|
19 along with XEmacs; see the file COPYING. If not, write to
|
|
|
20 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
|
|
|
21 Boston, MA 02111-1307, USA. */
|
|
|
22
|
|
|
23 /* Synched up with: Not in FSF. */
|
|
|
24
|
|
1292
|
25 /* Author: Lost in the mists of history. At least back to Lucid 19.3,
|
|
|
26 circa Sep 1992. Early hash table implementation allowed only `eq' as a
|
|
|
27 test -- other tests possible only when these objects were created from
|
|
|
28 the C code.
|
|
|
29
|
|
|
30 Expansion to allow general `equal'-test Lisp-creatable tables, and hash
|
|
|
31 methods for the various Lisp objects in existence at the time, added
|
|
|
32 during 19.12 I think (early 1995?), by Ben Wing.
|
|
|
33
|
|
|
34 Weak hash tables added by Jamie (maybe?) early on, perhaps around 19.6,
|
|
|
35 maybe earlier; again, only possible through the C code, and only
|
|
|
36 supported fully weak hash tables. Expansion to other kinds of weakness,
|
|
|
37 and exporting of the interface to Lisp, by Ben Wing during 19.12
|
|
|
38 (early-mid 1995) or maybe 19.13 cycle (mid 1995).
|
|
|
39
|
|
|
40 Expansion to full Common Lisp spec and interface, redoing of the
|
|
|
41 implementation, by Martin Buchholz, 1997? (Former hash table
|
|
|
42 implementation used "double hashing", I'm pretty sure, and was weirdly
|
|
|
43 tied into the generic hash.c code. Martin completely separated them.)
|
|
|
44 */
|
|
|
45
|
|
489
|
46 /* This file implements the hash table lisp object type.
|
|
|
47
|
|
504
|
48 This implementation was mostly written by Martin Buchholz in 1997.
|
|
|
49
|
|
|
50 The Lisp-level API (derived from Common Lisp) is almost completely
|
|
|
51 compatible with GNU Emacs 21, even though the implementations are
|
|
|
52 totally independent.
|
|
|
53
|
|
489
|
54 The hash table technique used is "linear probing". Collisions are
|
|
|
55 resolved by putting the item in the next empty place in the array
|
|
|
56 following the collision. Finding a hash entry performs a linear
|
|
|
57 search in the cluster starting at the hash value.
|
|
|
58
|
|
|
59 On deletions from the hash table, the entries immediately following
|
|
|
60 the deleted entry are re-entered in the hash table. We do not have
|
|
|
61 a special way to mark deleted entries (known as "tombstones").
|
|
|
62
|
|
|
63 At the end of the hash entries ("hentries"), we leave room for an
|
|
|
64 entry that is always empty (the "sentinel").
|
|
|
65
|
|
|
66 The traditional literature on hash table implementation
|
|
|
67 (e.g. Knuth) suggests that too much "primary clustering" occurs
|
|
|
68 with linear probing. However, this literature was written when
|
|
|
69 locality of reference was not a factor. The discrepancy between
|
|
|
70 CPU speeds and memory speeds is increasing, and the speed of access
|
|
|
71 to memory is highly dependent on memory caches which work best when
|
|
|
72 there is high locality of data reference. Random access to memory
|
|
|
73 is up to 20 times as expensive as access to the nearest address
|
|
|
74 (and getting worse). So linear probing makes sense.
|
|
|
75
|
|
|
76 But the representation doesn't actually matter that much with the
|
|
|
77 current elisp engine. Funcall is sufficiently slow that the choice
|
|
|
78 of hash table implementation is noise. */
|
|
|
79
|
|
428
|
80 #include <config.h>
|
|
|
81 #include "lisp.h"
|
|
|
82 #include "bytecode.h"
|
|
|
83 #include "elhash.h"
|
|
489
|
84 #include "opaque.h"
|
|
428
|
85
|
|
|
86 Lisp_Object Qhash_tablep;
|
|
|
87 static Lisp_Object Qhashtable, Qhash_table;
|
|
442
|
88 static Lisp_Object Qweakness, Qvalue, Qkey_or_value, Qkey_and_value;
|
|
428
|
89 static Lisp_Object Vall_weak_hash_tables;
|
|
|
90 static Lisp_Object Qrehash_size, Qrehash_threshold;
|
|
|
91 static Lisp_Object Q_size, Q_test, Q_weakness, Q_rehash_size, Q_rehash_threshold;
|
|
|
92
|
|
|
93 /* obsolete as of 19990901 in xemacs-21.2 */
|
|
442
|
94 static Lisp_Object Qweak, Qkey_weak, Qvalue_weak, Qkey_or_value_weak;
|
|
|
95 static Lisp_Object Qnon_weak, Q_type;
|
|
428
|
96
|
|
1204
|
97 typedef struct htentry
|
|
428
|
98 {
|
|
3092
|
99 #ifdef NEW_GC
|
|
|
100 struct lrecord_header lheader;
|
|
|
101 #endif /* NEW_GC */
|
|
428
|
102 Lisp_Object key;
|
|
|
103 Lisp_Object value;
|
|
1204
|
104 } htentry;
|
|
428
|
105
|
|
|
106 struct Lisp_Hash_Table
|
|
|
107 {
|
|
3017
|
108 struct LCRECORD_HEADER header;
|
|
665
|
109 Elemcount size;
|
|
|
110 Elemcount count;
|
|
|
111 Elemcount rehash_count;
|
|
428
|
112 double rehash_size;
|
|
|
113 double rehash_threshold;
|
|
665
|
114 Elemcount golden_ratio;
|
|
428
|
115 hash_table_hash_function_t hash_function;
|
|
|
116 hash_table_test_function_t test_function;
|
|
1204
|
117 htentry *hentries;
|
|
428
|
118 enum hash_table_weakness weakness;
|
|
|
119 Lisp_Object next_weak; /* Used to chain together all of the weak
|
|
|
120 hash tables. Don't mark through this. */
|
|
|
121 };
|
|
|
122
|
|
1204
|
123 #define HTENTRY_CLEAR_P(htentry) ((*(EMACS_UINT*)(&((htentry)->key))) == 0)
|
|
|
124 #define CLEAR_HTENTRY(htentry) \
|
|
|
125 ((*(EMACS_UINT*)(&((htentry)->key))) = 0, \
|
|
|
126 (*(EMACS_UINT*)(&((htentry)->value))) = 0)
|
|
428
|
127
|
|
|
128 #define HASH_TABLE_DEFAULT_SIZE 16
|
|
|
129 #define HASH_TABLE_DEFAULT_REHASH_SIZE 1.3
|
|
|
130 #define HASH_TABLE_MIN_SIZE 10
|
|
|
131
|
|
665
|
132 #define HASHCODE(key, ht) \
|
|
444
|
133 ((((ht)->hash_function ? (ht)->hash_function (key) : LISP_HASH (key)) \
|
|
|
134 * (ht)->golden_ratio) \
|
|
|
135 % (ht)->size)
|
|
428
|
136
|
|
|
137 #define KEYS_EQUAL_P(key1, key2, testfun) \
|
|
434
|
138 (EQ (key1, key2) || ((testfun) && (testfun) (key1, key2)))
|
|
428
|
139
|
|
|
140 #define LINEAR_PROBING_LOOP(probe, entries, size) \
|
|
|
141 for (; \
|
|
1204
|
142 !HTENTRY_CLEAR_P (probe) || \
|
|
428
|
143 (probe == entries + size ? \
|
|
1204
|
144 (probe = entries, !HTENTRY_CLEAR_P (probe)) : 0); \
|
|
428
|
145 probe++)
|
|
|
146
|
|
800
|
147 #ifdef ERROR_CHECK_STRUCTURES
|
|
428
|
148 static void
|
|
|
149 check_hash_table_invariants (Lisp_Hash_Table *ht)
|
|
|
150 {
|
|
|
151 assert (ht->count < ht->size);
|
|
|
152 assert (ht->count <= ht->rehash_count);
|
|
|
153 assert (ht->rehash_count < ht->size);
|
|
|
154 assert ((double) ht->count * ht->rehash_threshold - 1 <= (double) ht->rehash_count);
|
|
1204
|
155 assert (HTENTRY_CLEAR_P (ht->hentries + ht->size));
|
|
428
|
156 }
|
|
|
157 #else
|
|
|
158 #define check_hash_table_invariants(ht)
|
|
|
159 #endif
|
|
|
160
|
|
|
161 /* Return a suitable size for a hash table, with at least SIZE slots. */
|
|
665
|
162 static Elemcount
|
|
|
163 hash_table_size (Elemcount requested_size)
|
|
428
|
164 {
|
|
|
165 /* Return some prime near, but greater than or equal to, SIZE.
|
|
|
166 Decades from the time of writing, someone will have a system large
|
|
|
167 enough that the list below will be too short... */
|
|
665
|
168 static const Elemcount primes [] =
|
|
428
|
169 {
|
|
|
170 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
|
|
|
171 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
|
|
|
172 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
|
|
|
173 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
|
|
|
174 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
|
|
|
175 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
|
|
|
176 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
|
|
|
177 243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
|
|
647
|
178 1174703521, 1527114613, 1985248999 /* , 2580823717UL, 3355070839UL */
|
|
428
|
179 };
|
|
|
180 /* We've heard of binary search. */
|
|
|
181 int low, high;
|
|
|
182 for (low = 0, high = countof (primes) - 1; high - low > 1;)
|
|
|
183 {
|
|
|
184 /* Loop Invariant: size < primes [high] */
|
|
|
185 int mid = (low + high) / 2;
|
|
|
186 if (primes [mid] < requested_size)
|
|
|
187 low = mid;
|
|
|
188 else
|
|
|
189 high = mid;
|
|
|
190 }
|
|
|
191 return primes [high];
|
|
|
192 }
|
|
|
193
|
|
|
194
|
|
|
195 #if 0 /* I don't think these are needed any more.
|
|
|
196 If using the general lisp_object_equal_*() functions
|
|
|
197 causes efficiency problems, these can be resurrected. --ben */
|
|
|
198 /* equality and hash functions for Lisp strings */
|
|
|
199 int
|
|
|
200 lisp_string_equal (Lisp_Object str1, Lisp_Object str2)
|
|
|
201 {
|
|
|
202 /* This is wrong anyway. You can't use strcmp() on Lisp strings,
|
|
|
203 because they can contain zero characters. */
|
|
|
204 return !strcmp ((char *) XSTRING_DATA (str1), (char *) XSTRING_DATA (str2));
|
|
|
205 }
|
|
|
206
|
|
665
|
207 static Hashcode
|
|
428
|
208 lisp_string_hash (Lisp_Object obj)
|
|
|
209 {
|
|
|
210 return hash_string (XSTRING_DATA (str), XSTRING_LENGTH (str));
|
|
|
211 }
|
|
|
212
|
|
|
213 #endif /* 0 */
|
|
|
214
|
|
|
215 static int
|
|
|
216 lisp_object_eql_equal (Lisp_Object obj1, Lisp_Object obj2)
|
|
|
217 {
|
|
|
218 return EQ (obj1, obj2) || (FLOATP (obj1) && internal_equal (obj1, obj2, 0));
|
|
|
219 }
|
|
|
220
|
|
665
|
221 static Hashcode
|
|
428
|
222 lisp_object_eql_hash (Lisp_Object obj)
|
|
|
223 {
|
|
|
224 return FLOATP (obj) ? internal_hash (obj, 0) : LISP_HASH (obj);
|
|
|
225 }
|
|
|
226
|
|
|
227 static int
|
|
|
228 lisp_object_equal_equal (Lisp_Object obj1, Lisp_Object obj2)
|
|
|
229 {
|
|
|
230 return internal_equal (obj1, obj2, 0);
|
|
|
231 }
|
|
|
232
|
|
665
|
233 static Hashcode
|
|
428
|
234 lisp_object_equal_hash (Lisp_Object obj)
|
|
|
235 {
|
|
|
236 return internal_hash (obj, 0);
|
|
|
237 }
|
|
|
238
|
|
|
239
|
|
|
240 static Lisp_Object
|
|
|
241 mark_hash_table (Lisp_Object obj)
|
|
|
242 {
|
|
|
243 Lisp_Hash_Table *ht = XHASH_TABLE (obj);
|
|
|
244
|
|
|
245 /* If the hash table is weak, we don't want to mark the keys and
|
|
|
246 values (we scan over them after everything else has been marked,
|
|
|
247 and mark or remove them as necessary). */
|
|
|
248 if (ht->weakness == HASH_TABLE_NON_WEAK)
|
|
|
249 {
|
|
1204
|
250 htentry *e, *sentinel;
|
|
428
|
251
|
|
|
252 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
1204
|
253 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
254 {
|
|
|
255 mark_object (e->key);
|
|
|
256 mark_object (e->value);
|
|
|
257 }
|
|
|
258 }
|
|
|
259 return Qnil;
|
|
|
260 }
|
|
|
261
|
|
|
262 /* Equality of hash tables. Two hash tables are equal when they are of
|
|
|
263 the same weakness and test function, they have the same number of
|
|
|
264 elements, and for each key in the hash table, the values are `equal'.
|
|
|
265
|
|
|
266 This is similar to Common Lisp `equalp' of hash tables, with the
|
|
|
267 difference that CL requires the keys to be compared with the test
|
|
|
268 function, which we don't do. Doing that would require consing, and
|
|
|
269 consing is a bad idea in `equal'. Anyway, our method should provide
|
|
|
270 the same result -- if the keys are not equal according to the test
|
|
|
271 function, then Fgethash() in hash_table_equal_mapper() will fail. */
|
|
|
272 static int
|
|
|
273 hash_table_equal (Lisp_Object hash_table1, Lisp_Object hash_table2, int depth)
|
|
|
274 {
|
|
|
275 Lisp_Hash_Table *ht1 = XHASH_TABLE (hash_table1);
|
|
|
276 Lisp_Hash_Table *ht2 = XHASH_TABLE (hash_table2);
|
|
1204
|
277 htentry *e, *sentinel;
|
|
428
|
278
|
|
|
279 if ((ht1->test_function != ht2->test_function) ||
|
|
|
280 (ht1->weakness != ht2->weakness) ||
|
|
|
281 (ht1->count != ht2->count))
|
|
|
282 return 0;
|
|
|
283
|
|
|
284 depth++;
|
|
|
285
|
|
|
286 for (e = ht1->hentries, sentinel = e + ht1->size; e < sentinel; e++)
|
|
1204
|
287 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
288 /* Look up the key in the other hash table, and compare the values. */
|
|
|
289 {
|
|
|
290 Lisp_Object value_in_other = Fgethash (e->key, hash_table2, Qunbound);
|
|
|
291 if (UNBOUNDP (value_in_other) ||
|
|
|
292 !internal_equal (e->value, value_in_other, depth))
|
|
|
293 return 0; /* Give up */
|
|
|
294 }
|
|
|
295
|
|
|
296 return 1;
|
|
|
297 }
|
|
442
|
298
|
|
|
299 /* This is not a great hash function, but it _is_ correct and fast.
|
|
|
300 Examining all entries is too expensive, and examining a random
|
|
|
301 subset does not yield a correct hash function. */
|
|
665
|
302 static Hashcode
|
|
2286
|
303 hash_table_hash (Lisp_Object hash_table, int UNUSED (depth))
|
|
442
|
304 {
|
|
|
305 return XHASH_TABLE (hash_table)->count;
|
|
|
306 }
|
|
|
307
|
|
428
|
308
|
|
|
309 /* Printing hash tables.
|
|
|
310
|
|
|
311 This is non-trivial, because we use a readable structure-style
|
|
|
312 syntax for hash tables. This means that a typical hash table will be
|
|
|
313 readably printed in the form of:
|
|
|
314
|
|
|
315 #s(hash-table size 2 data (key1 value1 key2 value2))
|
|
|
316
|
|
|
317 The supported hash table structure keywords and their values are:
|
|
|
318 `test' (eql (or nil), eq or equal)
|
|
|
319 `size' (a natnum or nil)
|
|
|
320 `rehash-size' (a float)
|
|
|
321 `rehash-threshold' (a float)
|
|
442
|
322 `weakness' (nil, key, value, key-and-value, or key-or-value)
|
|
428
|
323 `data' (a list)
|
|
|
324
|
|
430
|
325 If `print-readably' is nil, then a simpler syntax is used, for example
|
|
428
|
326
|
|
|
327 #<hash-table size 2/13 data (key1 value1 key2 value2) 0x874d>
|
|
|
328
|
|
|
329 The data is truncated to four pairs, and the rest is shown with
|
|
|
330 `...'. This printer does not cons. */
|
|
|
331
|
|
|
332
|
|
|
333 /* Print the data of the hash table. This maps through a Lisp
|
|
|
334 hash table and prints key/value pairs using PRINTCHARFUN. */
|
|
|
335 static void
|
|
|
336 print_hash_table_data (Lisp_Hash_Table *ht, Lisp_Object printcharfun)
|
|
|
337 {
|
|
|
338 int count = 0;
|
|
1204
|
339 htentry *e, *sentinel;
|
|
428
|
340
|
|
826
|
341 write_c_string (printcharfun, " data (");
|
|
428
|
342
|
|
|
343 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
1204
|
344 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
345 {
|
|
|
346 if (count > 0)
|
|
826
|
347 write_c_string (printcharfun, " ");
|
|
428
|
348 if (!print_readably && count > 3)
|
|
|
349 {
|
|
826
|
350 write_c_string (printcharfun, "...");
|
|
428
|
351 break;
|
|
|
352 }
|
|
|
353 print_internal (e->key, printcharfun, 1);
|
|
800
|
354 write_fmt_string_lisp (printcharfun, " %S", 1, e->value);
|
|
428
|
355 count++;
|
|
|
356 }
|
|
|
357
|
|
826
|
358 write_c_string (printcharfun, ")");
|
|
428
|
359 }
|
|
|
360
|
|
|
361 static void
|
|
2286
|
362 print_hash_table (Lisp_Object obj, Lisp_Object printcharfun,
|
|
|
363 int UNUSED (escapeflag))
|
|
428
|
364 {
|
|
|
365 Lisp_Hash_Table *ht = XHASH_TABLE (obj);
|
|
|
366
|
|
826
|
367 write_c_string (printcharfun,
|
|
|
368 print_readably ? "#s(hash-table" : "#<hash-table");
|
|
428
|
369
|
|
|
370 /* These checks have a kludgy look to them, but they are safe.
|
|
|
371 Due to nature of hashing, you cannot use arbitrary
|
|
|
372 test functions anyway. */
|
|
|
373 if (!ht->test_function)
|
|
826
|
374 write_c_string (printcharfun, " test eq");
|
|
428
|
375 else if (ht->test_function == lisp_object_equal_equal)
|
|
826
|
376 write_c_string (printcharfun, " test equal");
|
|
428
|
377 else if (ht->test_function == lisp_object_eql_equal)
|
|
|
378 DO_NOTHING;
|
|
|
379 else
|
|
2500
|
380 ABORT ();
|
|
428
|
381
|
|
|
382 if (ht->count || !print_readably)
|
|
|
383 {
|
|
|
384 if (print_readably)
|
|
800
|
385 write_fmt_string (printcharfun, " size %ld", (long) ht->count);
|
|
428
|
386 else
|
|
800
|
387 write_fmt_string (printcharfun, " size %ld/%ld", (long) ht->count,
|
|
|
388 (long) ht->size);
|
|
428
|
389 }
|
|
|
390
|
|
|
391 if (ht->weakness != HASH_TABLE_NON_WEAK)
|
|
|
392 {
|
|
800
|
393 write_fmt_string
|
|
|
394 (printcharfun, " weakness %s",
|
|
|
395 (ht->weakness == HASH_TABLE_WEAK ? "key-and-value" :
|
|
|
396 ht->weakness == HASH_TABLE_KEY_WEAK ? "key" :
|
|
|
397 ht->weakness == HASH_TABLE_VALUE_WEAK ? "value" :
|
|
|
398 ht->weakness == HASH_TABLE_KEY_VALUE_WEAK ? "key-or-value" :
|
|
|
399 "you-d-better-not-see-this"));
|
|
428
|
400 }
|
|
|
401
|
|
|
402 if (ht->count)
|
|
|
403 print_hash_table_data (ht, printcharfun);
|
|
|
404
|
|
|
405 if (print_readably)
|
|
826
|
406 write_c_string (printcharfun, ")");
|
|
428
|
407 else
|
|
2421
|
408 write_fmt_string (printcharfun, " 0x%x>", ht->header.uid);
|
|
428
|
409 }
|
|
|
410
|
|
|
411 static void
|
|
3092
|
412 free_hentries (
|
|
|
413 #if defined (NEW_GC) && !defined (ERROR_CHECK_STRUCTURES)
|
|
|
414 htentry *UNUSED (hentries),
|
|
|
415 #else
|
|
|
416 htentry *hentries,
|
|
|
417 #endif
|
|
2333
|
418 #ifdef ERROR_CHECK_STRUCTURES
|
|
|
419 size_t size
|
|
3263
|
420 #else /* not (NEW_GC && ! ERROR_CHECK_STRUCTURES) */
|
|
2333
|
421 size_t UNUSED (size)
|
|
3263
|
422 #endif /* not (NEW_GC && ! ERROR_CHECK_STRUCTURES) */
|
|
2333
|
423 )
|
|
489
|
424 {
|
|
3092
|
425 #ifdef NEW_GC
|
|
|
426 #ifdef ERROR_CHECK_STRUCTURES
|
|
|
427 htentry *e, *sentinel;
|
|
|
428
|
|
|
429 for (e = hentries, sentinel = e + size; e < sentinel; e++)
|
|
|
430 mc_free (e);
|
|
|
431 #endif
|
|
|
432 #else /* not NEW_GC */
|
|
800
|
433 #ifdef ERROR_CHECK_STRUCTURES
|
|
489
|
434 /* Ensure a crash if other code uses the discarded entries afterwards. */
|
|
1204
|
435 htentry *e, *sentinel;
|
|
489
|
436
|
|
|
437 for (e = hentries, sentinel = e + size; e < sentinel; e++)
|
|
1204
|
438 * (unsigned long *) e = 0xdeadbeef; /* -559038737 base 10 */
|
|
489
|
439 #endif
|
|
|
440
|
|
|
441 if (!DUMPEDP (hentries))
|
|
1726
|
442 xfree (hentries, htentry *);
|
|
3092
|
443 #endif /* not NEW_GC */
|
|
489
|
444 }
|
|
|
445
|
|
3263
|
446 #ifndef NEW_GC
|
|
489
|
447 static void
|
|
428
|
448 finalize_hash_table (void *header, int for_disksave)
|
|
|
449 {
|
|
|
450 if (!for_disksave)
|
|
|
451 {
|
|
|
452 Lisp_Hash_Table *ht = (Lisp_Hash_Table *) header;
|
|
489
|
453 free_hentries (ht->hentries, ht->size);
|
|
428
|
454 ht->hentries = 0;
|
|
|
455 }
|
|
|
456 }
|
|
3263
|
457 #endif /* not NEW_GC */
|
|
428
|
458
|
|
1204
|
459 static const struct memory_description htentry_description_1[] = {
|
|
|
460 { XD_LISP_OBJECT, offsetof (htentry, key) },
|
|
|
461 { XD_LISP_OBJECT, offsetof (htentry, value) },
|
|
428
|
462 { XD_END }
|
|
|
463 };
|
|
|
464
|
|
1204
|
465 static const struct sized_memory_description htentry_description = {
|
|
|
466 sizeof (htentry),
|
|
|
467 htentry_description_1
|
|
428
|
468 };
|
|
|
469
|
|
3092
|
470 #ifdef NEW_GC
|
|
|
471 static const struct memory_description htentry_weak_description_1[] = {
|
|
|
472 { XD_LISP_OBJECT, offsetof (htentry, key), 0, { 0 }, XD_FLAG_NO_KKCC},
|
|
|
473 { XD_LISP_OBJECT, offsetof (htentry, value), 0, { 0 }, XD_FLAG_NO_KKCC},
|
|
|
474 { XD_END }
|
|
|
475 };
|
|
|
476
|
|
|
477 static const struct sized_memory_description htentry_weak_description = {
|
|
|
478 sizeof (htentry),
|
|
|
479 htentry_weak_description_1
|
|
|
480 };
|
|
|
481
|
|
|
482 DEFINE_LRECORD_IMPLEMENTATION ("hash-table-entry", hash_table_entry,
|
|
|
483 1, /*dumpable-flag*/
|
|
|
484 0, 0, 0, 0, 0,
|
|
|
485 htentry_description_1,
|
|
|
486 Lisp_Hash_Table_Entry);
|
|
|
487 #endif /* NEW_GC */
|
|
|
488
|
|
1204
|
489 static const struct memory_description htentry_union_description_1[] = {
|
|
|
490 /* Note: XD_INDIRECT in this table refers to the surrounding table,
|
|
|
491 and so this will work. */
|
|
3092
|
492 #ifdef NEW_GC
|
|
|
493 { XD_LISP_OBJECT_BLOCK_PTR, HASH_TABLE_NON_WEAK,
|
|
|
494 XD_INDIRECT (0, 1), { &htentry_description } },
|
|
|
495 { XD_LISP_OBJECT_BLOCK_PTR, 0, XD_INDIRECT (0, 1),
|
|
|
496 { &htentry_weak_description }, XD_FLAG_UNION_DEFAULT_ENTRY },
|
|
|
497 #else /* not NEW_GC */
|
|
2367
|
498 { XD_BLOCK_PTR, HASH_TABLE_NON_WEAK, XD_INDIRECT (0, 1),
|
|
2551
|
499 { &htentry_description } },
|
|
|
500 { XD_BLOCK_PTR, 0, XD_INDIRECT (0, 1), { &htentry_description },
|
|
1204
|
501 XD_FLAG_UNION_DEFAULT_ENTRY | XD_FLAG_NO_KKCC },
|
|
3092
|
502 #endif /* not NEW_GC */
|
|
1204
|
503 { XD_END }
|
|
|
504 };
|
|
|
505
|
|
|
506 static const struct sized_memory_description htentry_union_description = {
|
|
|
507 sizeof (htentry *),
|
|
|
508 htentry_union_description_1
|
|
|
509 };
|
|
|
510
|
|
|
511 const struct memory_description hash_table_description[] = {
|
|
|
512 { XD_ELEMCOUNT, offsetof (Lisp_Hash_Table, size) },
|
|
|
513 { XD_INT, offsetof (Lisp_Hash_Table, weakness) },
|
|
|
514 { XD_UNION, offsetof (Lisp_Hash_Table, hentries), XD_INDIRECT (1, 0),
|
|
2551
|
515 { &htentry_union_description } },
|
|
440
|
516 { XD_LO_LINK, offsetof (Lisp_Hash_Table, next_weak) },
|
|
428
|
517 { XD_END }
|
|
|
518 };
|
|
|
519
|
|
3263
|
520 #ifdef NEW_GC
|
|
|
521 DEFINE_LRECORD_IMPLEMENTATION ("hash-table", hash_table,
|
|
|
522 1, /*dumpable-flag*/
|
|
|
523 mark_hash_table, print_hash_table,
|
|
|
524 0, hash_table_equal, hash_table_hash,
|
|
|
525 hash_table_description,
|
|
|
526 Lisp_Hash_Table);
|
|
|
527 #else /* not NEW_GC */
|
|
934
|
528 DEFINE_LRECORD_IMPLEMENTATION ("hash-table", hash_table,
|
|
|
529 1, /*dumpable-flag*/
|
|
|
530 mark_hash_table, print_hash_table,
|
|
|
531 finalize_hash_table,
|
|
|
532 hash_table_equal, hash_table_hash,
|
|
|
533 hash_table_description,
|
|
|
534 Lisp_Hash_Table);
|
|
3263
|
535 #endif /* not NEW_GC */
|
|
428
|
536
|
|
|
537 static Lisp_Hash_Table *
|
|
|
538 xhash_table (Lisp_Object hash_table)
|
|
|
539 {
|
|
1123
|
540 /* #### What's going on here? Why the gc_in_progress check? */
|
|
428
|
541 if (!gc_in_progress)
|
|
|
542 CHECK_HASH_TABLE (hash_table);
|
|
|
543 check_hash_table_invariants (XHASH_TABLE (hash_table));
|
|
|
544 return XHASH_TABLE (hash_table);
|
|
|
545 }
|
|
|
546
|
|
|
547
|
|
|
548 /************************************************************************/
|
|
|
549 /* Creation of Hash Tables */
|
|
|
550 /************************************************************************/
|
|
|
551
|
|
|
552 /* Creation of hash tables, without error-checking. */
|
|
|
553 static void
|
|
|
554 compute_hash_table_derived_values (Lisp_Hash_Table *ht)
|
|
|
555 {
|
|
665
|
556 ht->rehash_count = (Elemcount)
|
|
438
|
557 ((double) ht->size * ht->rehash_threshold);
|
|
665
|
558 ht->golden_ratio = (Elemcount)
|
|
428
|
559 ((double) ht->size * (.6180339887 / (double) sizeof (Lisp_Object)));
|
|
|
560 }
|
|
|
561
|
|
|
562 Lisp_Object
|
|
450
|
563 make_standard_lisp_hash_table (enum hash_table_test test,
|
|
665
|
564 Elemcount size,
|
|
450
|
565 double rehash_size,
|
|
|
566 double rehash_threshold,
|
|
|
567 enum hash_table_weakness weakness)
|
|
|
568 {
|
|
462
|
569 hash_table_hash_function_t hash_function = 0;
|
|
450
|
570 hash_table_test_function_t test_function = 0;
|
|
|
571
|
|
|
572 switch (test)
|
|
|
573 {
|
|
|
574 case HASH_TABLE_EQ:
|
|
|
575 test_function = 0;
|
|
|
576 hash_function = 0;
|
|
|
577 break;
|
|
|
578
|
|
|
579 case HASH_TABLE_EQL:
|
|
|
580 test_function = lisp_object_eql_equal;
|
|
|
581 hash_function = lisp_object_eql_hash;
|
|
|
582 break;
|
|
|
583
|
|
|
584 case HASH_TABLE_EQUAL:
|
|
|
585 test_function = lisp_object_equal_equal;
|
|
|
586 hash_function = lisp_object_equal_hash;
|
|
|
587 break;
|
|
|
588
|
|
|
589 default:
|
|
2500
|
590 ABORT ();
|
|
450
|
591 }
|
|
|
592
|
|
|
593 return make_general_lisp_hash_table (hash_function, test_function,
|
|
|
594 size, rehash_size, rehash_threshold,
|
|
|
595 weakness);
|
|
|
596 }
|
|
|
597
|
|
|
598 Lisp_Object
|
|
|
599 make_general_lisp_hash_table (hash_table_hash_function_t hash_function,
|
|
|
600 hash_table_test_function_t test_function,
|
|
665
|
601 Elemcount size,
|
|
428
|
602 double rehash_size,
|
|
|
603 double rehash_threshold,
|
|
|
604 enum hash_table_weakness weakness)
|
|
|
605 {
|
|
|
606 Lisp_Object hash_table;
|
|
3017
|
607 Lisp_Hash_Table *ht = ALLOC_LCRECORD_TYPE (Lisp_Hash_Table, &lrecord_hash_table);
|
|
428
|
608
|
|
450
|
609 ht->test_function = test_function;
|
|
|
610 ht->hash_function = hash_function;
|
|
438
|
611 ht->weakness = weakness;
|
|
|
612
|
|
|
613 ht->rehash_size =
|
|
|
614 rehash_size > 1.0 ? rehash_size : HASH_TABLE_DEFAULT_REHASH_SIZE;
|
|
|
615
|
|
|
616 ht->rehash_threshold =
|
|
|
617 rehash_threshold > 0.0 ? rehash_threshold :
|
|
|
618 size > 4096 && !ht->test_function ? 0.7 : 0.6;
|
|
|
619
|
|
428
|
620 if (size < HASH_TABLE_MIN_SIZE)
|
|
|
621 size = HASH_TABLE_MIN_SIZE;
|
|
665
|
622 ht->size = hash_table_size ((Elemcount) (((double) size / ht->rehash_threshold)
|
|
438
|
623 + 1.0));
|
|
428
|
624 ht->count = 0;
|
|
438
|
625
|
|
428
|
626 compute_hash_table_derived_values (ht);
|
|
|
627
|
|
1204
|
628 /* We leave room for one never-occupied sentinel htentry at the end. */
|
|
3092
|
629 #ifdef NEW_GC
|
|
|
630 ht->hentries = (htentry *) alloc_lrecord_array (sizeof (htentry),
|
|
|
631 ht->size + 1,
|
|
|
632 &lrecord_hash_table_entry);
|
|
|
633 #else /* not NEW_GC */
|
|
1204
|
634 ht->hentries = xnew_array_and_zero (htentry, ht->size + 1);
|
|
3092
|
635 #endif /* not NEW_GC */
|
|
428
|
636
|
|
793
|
637 hash_table = wrap_hash_table (ht);
|
|
428
|
638
|
|
|
639 if (weakness == HASH_TABLE_NON_WEAK)
|
|
|
640 ht->next_weak = Qunbound;
|
|
|
641 else
|
|
|
642 ht->next_weak = Vall_weak_hash_tables, Vall_weak_hash_tables = hash_table;
|
|
|
643
|
|
|
644 return hash_table;
|
|
|
645 }
|
|
|
646
|
|
|
647 Lisp_Object
|
|
665
|
648 make_lisp_hash_table (Elemcount size,
|
|
428
|
649 enum hash_table_weakness weakness,
|
|
|
650 enum hash_table_test test)
|
|
|
651 {
|
|
450
|
652 return make_standard_lisp_hash_table (test, size, -1.0, -1.0, weakness);
|
|
428
|
653 }
|
|
|
654
|
|
|
655 /* Pretty reading of hash tables.
|
|
|
656
|
|
|
657 Here we use the existing structures mechanism (which is,
|
|
|
658 unfortunately, pretty cumbersome) for validating and instantiating
|
|
|
659 the hash tables. The idea is that the side-effect of reading a
|
|
|
660 #s(hash-table PLIST) object is creation of a hash table with desired
|
|
|
661 properties, and that the hash table is returned. */
|
|
|
662
|
|
|
663 /* Validation functions: each keyword provides its own validation
|
|
|
664 function. The errors should maybe be continuable, but it is
|
|
|
665 unclear how this would cope with ERRB. */
|
|
|
666 static int
|
|
2286
|
667 hash_table_size_validate (Lisp_Object UNUSED (keyword), Lisp_Object value,
|
|
|
668 Error_Behavior errb)
|
|
428
|
669 {
|
|
|
670 if (NATNUMP (value))
|
|
|
671 return 1;
|
|
|
672
|
|
563
|
673 maybe_signal_error_1 (Qwrong_type_argument, list2 (Qnatnump, value),
|
|
2286
|
674 Qhash_table, errb);
|
|
428
|
675 return 0;
|
|
|
676 }
|
|
|
677
|
|
665
|
678 static Elemcount
|
|
428
|
679 decode_hash_table_size (Lisp_Object obj)
|
|
|
680 {
|
|
|
681 return NILP (obj) ? HASH_TABLE_DEFAULT_SIZE : XINT (obj);
|
|
|
682 }
|
|
|
683
|
|
|
684 static int
|
|
2286
|
685 hash_table_weakness_validate (Lisp_Object UNUSED (keyword), Lisp_Object value,
|
|
578
|
686 Error_Behavior errb)
|
|
428
|
687 {
|
|
442
|
688 if (EQ (value, Qnil)) return 1;
|
|
|
689 if (EQ (value, Qt)) return 1;
|
|
|
690 if (EQ (value, Qkey)) return 1;
|
|
|
691 if (EQ (value, Qkey_and_value)) return 1;
|
|
|
692 if (EQ (value, Qkey_or_value)) return 1;
|
|
|
693 if (EQ (value, Qvalue)) return 1;
|
|
428
|
694
|
|
|
695 /* Following values are obsolete as of 19990901 in xemacs-21.2 */
|
|
442
|
696 if (EQ (value, Qnon_weak)) return 1;
|
|
|
697 if (EQ (value, Qweak)) return 1;
|
|
|
698 if (EQ (value, Qkey_weak)) return 1;
|
|
|
699 if (EQ (value, Qkey_or_value_weak)) return 1;
|
|
|
700 if (EQ (value, Qvalue_weak)) return 1;
|
|
428
|
701
|
|
563
|
702 maybe_invalid_constant ("Invalid hash table weakness",
|
|
428
|
703 value, Qhash_table, errb);
|
|
|
704 return 0;
|
|
|
705 }
|
|
|
706
|
|
|
707 static enum hash_table_weakness
|
|
|
708 decode_hash_table_weakness (Lisp_Object obj)
|
|
|
709 {
|
|
442
|
710 if (EQ (obj, Qnil)) return HASH_TABLE_NON_WEAK;
|
|
|
711 if (EQ (obj, Qt)) return HASH_TABLE_WEAK;
|
|
|
712 if (EQ (obj, Qkey_and_value)) return HASH_TABLE_WEAK;
|
|
|
713 if (EQ (obj, Qkey)) return HASH_TABLE_KEY_WEAK;
|
|
|
714 if (EQ (obj, Qkey_or_value)) return HASH_TABLE_KEY_VALUE_WEAK;
|
|
|
715 if (EQ (obj, Qvalue)) return HASH_TABLE_VALUE_WEAK;
|
|
428
|
716
|
|
|
717 /* Following values are obsolete as of 19990901 in xemacs-21.2 */
|
|
442
|
718 if (EQ (obj, Qnon_weak)) return HASH_TABLE_NON_WEAK;
|
|
|
719 if (EQ (obj, Qweak)) return HASH_TABLE_WEAK;
|
|
|
720 if (EQ (obj, Qkey_weak)) return HASH_TABLE_KEY_WEAK;
|
|
|
721 if (EQ (obj, Qkey_or_value_weak)) return HASH_TABLE_KEY_VALUE_WEAK;
|
|
|
722 if (EQ (obj, Qvalue_weak)) return HASH_TABLE_VALUE_WEAK;
|
|
428
|
723
|
|
563
|
724 invalid_constant ("Invalid hash table weakness", obj);
|
|
1204
|
725 RETURN_NOT_REACHED (HASH_TABLE_NON_WEAK);
|
|
428
|
726 }
|
|
|
727
|
|
|
728 static int
|
|
2286
|
729 hash_table_test_validate (Lisp_Object UNUSED (keyword), Lisp_Object value,
|
|
|
730 Error_Behavior errb)
|
|
428
|
731 {
|
|
|
732 if (EQ (value, Qnil)) return 1;
|
|
|
733 if (EQ (value, Qeq)) return 1;
|
|
|
734 if (EQ (value, Qequal)) return 1;
|
|
|
735 if (EQ (value, Qeql)) return 1;
|
|
|
736
|
|
563
|
737 maybe_invalid_constant ("Invalid hash table test",
|
|
2286
|
738 value, Qhash_table, errb);
|
|
428
|
739 return 0;
|
|
|
740 }
|
|
|
741
|
|
|
742 static enum hash_table_test
|
|
|
743 decode_hash_table_test (Lisp_Object obj)
|
|
|
744 {
|
|
|
745 if (EQ (obj, Qnil)) return HASH_TABLE_EQL;
|
|
|
746 if (EQ (obj, Qeq)) return HASH_TABLE_EQ;
|
|
|
747 if (EQ (obj, Qequal)) return HASH_TABLE_EQUAL;
|
|
|
748 if (EQ (obj, Qeql)) return HASH_TABLE_EQL;
|
|
|
749
|
|
563
|
750 invalid_constant ("Invalid hash table test", obj);
|
|
1204
|
751 RETURN_NOT_REACHED (HASH_TABLE_EQ);
|
|
428
|
752 }
|
|
|
753
|
|
|
754 static int
|
|
2286
|
755 hash_table_rehash_size_validate (Lisp_Object UNUSED (keyword),
|
|
|
756 Lisp_Object value, Error_Behavior errb)
|
|
428
|
757 {
|
|
|
758 if (!FLOATP (value))
|
|
|
759 {
|
|
563
|
760 maybe_signal_error_1 (Qwrong_type_argument, list2 (Qfloatp, value),
|
|
428
|
761 Qhash_table, errb);
|
|
|
762 return 0;
|
|
|
763 }
|
|
|
764
|
|
|
765 {
|
|
|
766 double rehash_size = XFLOAT_DATA (value);
|
|
|
767 if (rehash_size <= 1.0)
|
|
|
768 {
|
|
563
|
769 maybe_invalid_argument
|
|
428
|
770 ("Hash table rehash size must be greater than 1.0",
|
|
|
771 value, Qhash_table, errb);
|
|
|
772 return 0;
|
|
|
773 }
|
|
|
774 }
|
|
|
775
|
|
|
776 return 1;
|
|
|
777 }
|
|
|
778
|
|
|
779 static double
|
|
|
780 decode_hash_table_rehash_size (Lisp_Object rehash_size)
|
|
|
781 {
|
|
|
782 return NILP (rehash_size) ? -1.0 : XFLOAT_DATA (rehash_size);
|
|
|
783 }
|
|
|
784
|
|
|
785 static int
|
|
2286
|
786 hash_table_rehash_threshold_validate (Lisp_Object UNUSED (keyword),
|
|
|
787 Lisp_Object value, Error_Behavior errb)
|
|
428
|
788 {
|
|
|
789 if (!FLOATP (value))
|
|
|
790 {
|
|
563
|
791 maybe_signal_error_1 (Qwrong_type_argument, list2 (Qfloatp, value),
|
|
428
|
792 Qhash_table, errb);
|
|
|
793 return 0;
|
|
|
794 }
|
|
|
795
|
|
|
796 {
|
|
|
797 double rehash_threshold = XFLOAT_DATA (value);
|
|
|
798 if (rehash_threshold <= 0.0 || rehash_threshold >= 1.0)
|
|
|
799 {
|
|
563
|
800 maybe_invalid_argument
|
|
428
|
801 ("Hash table rehash threshold must be between 0.0 and 1.0",
|
|
|
802 value, Qhash_table, errb);
|
|
|
803 return 0;
|
|
|
804 }
|
|
|
805 }
|
|
|
806
|
|
|
807 return 1;
|
|
|
808 }
|
|
|
809
|
|
|
810 static double
|
|
|
811 decode_hash_table_rehash_threshold (Lisp_Object rehash_threshold)
|
|
|
812 {
|
|
|
813 return NILP (rehash_threshold) ? -1.0 : XFLOAT_DATA (rehash_threshold);
|
|
|
814 }
|
|
|
815
|
|
|
816 static int
|
|
2286
|
817 hash_table_data_validate (Lisp_Object UNUSED (keyword), Lisp_Object value,
|
|
|
818 Error_Behavior errb)
|
|
428
|
819 {
|
|
|
820 int len;
|
|
|
821
|
|
|
822 GET_EXTERNAL_LIST_LENGTH (value, len);
|
|
|
823
|
|
|
824 if (len & 1)
|
|
|
825 {
|
|
563
|
826 maybe_sferror
|
|
428
|
827 ("Hash table data must have alternating key/value pairs",
|
|
|
828 value, Qhash_table, errb);
|
|
|
829 return 0;
|
|
|
830 }
|
|
|
831 return 1;
|
|
|
832 }
|
|
|
833
|
|
|
834 /* The actual instantiation of a hash table. This does practically no
|
|
|
835 error checking, because it relies on the fact that the paranoid
|
|
|
836 functions above have error-checked everything to the last details.
|
|
|
837 If this assumption is wrong, we will get a crash immediately (with
|
|
|
838 error-checking compiled in), and we'll know if there is a bug in
|
|
|
839 the structure mechanism. So there. */
|
|
|
840 static Lisp_Object
|
|
|
841 hash_table_instantiate (Lisp_Object plist)
|
|
|
842 {
|
|
|
843 Lisp_Object hash_table;
|
|
|
844 Lisp_Object test = Qnil;
|
|
|
845 Lisp_Object size = Qnil;
|
|
|
846 Lisp_Object rehash_size = Qnil;
|
|
|
847 Lisp_Object rehash_threshold = Qnil;
|
|
|
848 Lisp_Object weakness = Qnil;
|
|
|
849 Lisp_Object data = Qnil;
|
|
|
850
|
|
2421
|
851 PROPERTY_LIST_LOOP_3 (key, value, plist)
|
|
428
|
852 {
|
|
|
853 if (EQ (key, Qtest)) test = value;
|
|
|
854 else if (EQ (key, Qsize)) size = value;
|
|
|
855 else if (EQ (key, Qrehash_size)) rehash_size = value;
|
|
|
856 else if (EQ (key, Qrehash_threshold)) rehash_threshold = value;
|
|
|
857 else if (EQ (key, Qweakness)) weakness = value;
|
|
|
858 else if (EQ (key, Qdata)) data = value;
|
|
|
859 else if (EQ (key, Qtype))/*obsolete*/ weakness = value;
|
|
|
860 else
|
|
2500
|
861 ABORT ();
|
|
428
|
862 }
|
|
|
863
|
|
|
864 /* Create the hash table. */
|
|
450
|
865 hash_table = make_standard_lisp_hash_table
|
|
428
|
866 (decode_hash_table_test (test),
|
|
|
867 decode_hash_table_size (size),
|
|
|
868 decode_hash_table_rehash_size (rehash_size),
|
|
|
869 decode_hash_table_rehash_threshold (rehash_threshold),
|
|
|
870 decode_hash_table_weakness (weakness));
|
|
|
871
|
|
|
872 /* I'm not sure whether this can GC, but better safe than sorry. */
|
|
|
873 {
|
|
|
874 struct gcpro gcpro1;
|
|
|
875 GCPRO1 (hash_table);
|
|
|
876
|
|
|
877 /* And fill it with data. */
|
|
|
878 while (!NILP (data))
|
|
|
879 {
|
|
|
880 Lisp_Object key, value;
|
|
|
881 key = XCAR (data); data = XCDR (data);
|
|
|
882 value = XCAR (data); data = XCDR (data);
|
|
|
883 Fputhash (key, value, hash_table);
|
|
|
884 }
|
|
|
885 UNGCPRO;
|
|
|
886 }
|
|
|
887
|
|
|
888 return hash_table;
|
|
|
889 }
|
|
|
890
|
|
|
891 static void
|
|
|
892 structure_type_create_hash_table_structure_name (Lisp_Object structure_name)
|
|
|
893 {
|
|
|
894 struct structure_type *st;
|
|
|
895
|
|
|
896 st = define_structure_type (structure_name, 0, hash_table_instantiate);
|
|
|
897 define_structure_type_keyword (st, Qtest, hash_table_test_validate);
|
|
|
898 define_structure_type_keyword (st, Qsize, hash_table_size_validate);
|
|
|
899 define_structure_type_keyword (st, Qrehash_size, hash_table_rehash_size_validate);
|
|
|
900 define_structure_type_keyword (st, Qrehash_threshold, hash_table_rehash_threshold_validate);
|
|
|
901 define_structure_type_keyword (st, Qweakness, hash_table_weakness_validate);
|
|
|
902 define_structure_type_keyword (st, Qdata, hash_table_data_validate);
|
|
|
903
|
|
|
904 /* obsolete as of 19990901 in xemacs-21.2 */
|
|
|
905 define_structure_type_keyword (st, Qtype, hash_table_weakness_validate);
|
|
|
906 }
|
|
|
907
|
|
|
908 /* Create a built-in Lisp structure type named `hash-table'.
|
|
|
909 We make #s(hashtable ...) equivalent to #s(hash-table ...),
|
|
|
910 for backward compatibility.
|
|
|
911 This is called from emacs.c. */
|
|
|
912 void
|
|
|
913 structure_type_create_hash_table (void)
|
|
|
914 {
|
|
|
915 structure_type_create_hash_table_structure_name (Qhash_table);
|
|
|
916 structure_type_create_hash_table_structure_name (Qhashtable); /* compat */
|
|
|
917 }
|
|
|
918
|
|
|
919
|
|
|
920 /************************************************************************/
|
|
|
921 /* Definition of Lisp-visible methods */
|
|
|
922 /************************************************************************/
|
|
|
923
|
|
|
924 DEFUN ("hash-table-p", Fhash_table_p, 1, 1, 0, /*
|
|
|
925 Return t if OBJECT is a hash table, else nil.
|
|
|
926 */
|
|
|
927 (object))
|
|
|
928 {
|
|
|
929 return HASH_TABLEP (object) ? Qt : Qnil;
|
|
|
930 }
|
|
|
931
|
|
|
932 DEFUN ("make-hash-table", Fmake_hash_table, 0, MANY, 0, /*
|
|
|
933 Return a new empty hash table object.
|
|
|
934 Use Common Lisp style keywords to specify hash table properties.
|
|
|
935 (make-hash-table &key test size rehash-size rehash-threshold weakness)
|
|
|
936
|
|
|
937 Keyword :test can be `eq', `eql' (default) or `equal'.
|
|
|
938 Comparison between keys is done using this function.
|
|
|
939 If speed is important, consider using `eq'.
|
|
|
940 When storing strings in the hash table, you will likely need to use `equal'.
|
|
|
941
|
|
|
942 Keyword :size specifies the number of keys likely to be inserted.
|
|
|
943 This number of entries can be inserted without enlarging the hash table.
|
|
|
944
|
|
|
945 Keyword :rehash-size must be a float greater than 1.0, and specifies
|
|
|
946 the factor by which to increase the size of the hash table when enlarging.
|
|
|
947
|
|
|
948 Keyword :rehash-threshold must be a float between 0.0 and 1.0,
|
|
|
949 and specifies the load factor of the hash table which triggers enlarging.
|
|
|
950
|
|
442
|
951 Non-standard keyword :weakness can be `nil' (default), `t', `key-and-value',
|
|
|
952 `key', `value' or `key-or-value'. `t' is an alias for `key-and-value'.
|
|
428
|
953
|
|
442
|
954 A key-and-value-weak hash table, also known as a fully-weak or simply
|
|
|
955 as a weak hash table, is one whose pointers do not count as GC
|
|
|
956 referents: for any key-value pair in the hash table, if the only
|
|
|
957 remaining pointer to either the key or the value is in a weak hash
|
|
|
958 table, then the pair will be removed from the hash table, and the key
|
|
|
959 and value collected. A non-weak hash table (or any other pointer)
|
|
|
960 would prevent the object from being collected.
|
|
428
|
961
|
|
|
962 A key-weak hash table is similar to a fully-weak hash table except that
|
|
|
963 a key-value pair will be removed only if the key remains unmarked
|
|
|
964 outside of weak hash tables. The pair will remain in the hash table if
|
|
|
965 the key is pointed to by something other than a weak hash table, even
|
|
|
966 if the value is not.
|
|
|
967
|
|
|
968 A value-weak hash table is similar to a fully-weak hash table except
|
|
|
969 that a key-value pair will be removed only if the value remains
|
|
|
970 unmarked outside of weak hash tables. The pair will remain in the
|
|
|
971 hash table if the value is pointed to by something other than a weak
|
|
|
972 hash table, even if the key is not.
|
|
442
|
973
|
|
|
974 A key-or-value-weak hash table is similar to a fully-weak hash table except
|
|
|
975 that a key-value pair will be removed only if the value and the key remain
|
|
|
976 unmarked outside of weak hash tables. The pair will remain in the
|
|
|
977 hash table if the value or key are pointed to by something other than a weak
|
|
|
978 hash table, even if the other is not.
|
|
428
|
979 */
|
|
|
980 (int nargs, Lisp_Object *args))
|
|
|
981 {
|
|
|
982 int i = 0;
|
|
|
983 Lisp_Object test = Qnil;
|
|
|
984 Lisp_Object size = Qnil;
|
|
|
985 Lisp_Object rehash_size = Qnil;
|
|
|
986 Lisp_Object rehash_threshold = Qnil;
|
|
|
987 Lisp_Object weakness = Qnil;
|
|
|
988
|
|
|
989 while (i + 1 < nargs)
|
|
|
990 {
|
|
|
991 Lisp_Object keyword = args[i++];
|
|
|
992 Lisp_Object value = args[i++];
|
|
|
993
|
|
|
994 if (EQ (keyword, Q_test)) test = value;
|
|
|
995 else if (EQ (keyword, Q_size)) size = value;
|
|
|
996 else if (EQ (keyword, Q_rehash_size)) rehash_size = value;
|
|
|
997 else if (EQ (keyword, Q_rehash_threshold)) rehash_threshold = value;
|
|
|
998 else if (EQ (keyword, Q_weakness)) weakness = value;
|
|
|
999 else if (EQ (keyword, Q_type))/*obsolete*/ weakness = value;
|
|
563
|
1000 else invalid_constant ("Invalid hash table property keyword", keyword);
|
|
428
|
1001 }
|
|
|
1002
|
|
|
1003 if (i < nargs)
|
|
563
|
1004 sferror ("Hash table property requires a value", args[i]);
|
|
428
|
1005
|
|
|
1006 #define VALIDATE_VAR(var) \
|
|
|
1007 if (!NILP (var)) hash_table_##var##_validate (Q##var, var, ERROR_ME);
|
|
|
1008
|
|
|
1009 VALIDATE_VAR (test);
|
|
|
1010 VALIDATE_VAR (size);
|
|
|
1011 VALIDATE_VAR (rehash_size);
|
|
|
1012 VALIDATE_VAR (rehash_threshold);
|
|
|
1013 VALIDATE_VAR (weakness);
|
|
|
1014
|
|
450
|
1015 return make_standard_lisp_hash_table
|
|
428
|
1016 (decode_hash_table_test (test),
|
|
|
1017 decode_hash_table_size (size),
|
|
|
1018 decode_hash_table_rehash_size (rehash_size),
|
|
|
1019 decode_hash_table_rehash_threshold (rehash_threshold),
|
|
|
1020 decode_hash_table_weakness (weakness));
|
|
|
1021 }
|
|
|
1022
|
|
|
1023 DEFUN ("copy-hash-table", Fcopy_hash_table, 1, 1, 0, /*
|
|
|
1024 Return a new hash table containing the same keys and values as HASH-TABLE.
|
|
|
1025 The keys and values will not themselves be copied.
|
|
|
1026 */
|
|
|
1027 (hash_table))
|
|
|
1028 {
|
|
442
|
1029 const Lisp_Hash_Table *ht_old = xhash_table (hash_table);
|
|
3017
|
1030 Lisp_Hash_Table *ht = ALLOC_LCRECORD_TYPE (Lisp_Hash_Table, &lrecord_hash_table);
|
|
|
1031 COPY_LCRECORD (ht, ht_old);
|
|
428
|
1032
|
|
3092
|
1033 #ifdef NEW_GC
|
|
|
1034 ht->hentries = (htentry *) alloc_lrecord_array (sizeof (htentry),
|
|
|
1035 ht_old->size + 1,
|
|
|
1036 &lrecord_hash_table_entry);
|
|
|
1037 #else /* not NEW_GC */
|
|
1204
|
1038 ht->hentries = xnew_array (htentry, ht_old->size + 1);
|
|
3092
|
1039 #endif /* not NEW_GC */
|
|
1204
|
1040 memcpy (ht->hentries, ht_old->hentries, (ht_old->size + 1) * sizeof (htentry));
|
|
428
|
1041
|
|
793
|
1042 hash_table = wrap_hash_table (ht);
|
|
428
|
1043
|
|
|
1044 if (! EQ (ht->next_weak, Qunbound))
|
|
|
1045 {
|
|
|
1046 ht->next_weak = Vall_weak_hash_tables;
|
|
|
1047 Vall_weak_hash_tables = hash_table;
|
|
|
1048 }
|
|
|
1049
|
|
|
1050 return hash_table;
|
|
|
1051 }
|
|
|
1052
|
|
|
1053 static void
|
|
665
|
1054 resize_hash_table (Lisp_Hash_Table *ht, Elemcount new_size)
|
|
428
|
1055 {
|
|
1204
|
1056 htentry *old_entries, *new_entries, *sentinel, *e;
|
|
665
|
1057 Elemcount old_size;
|
|
428
|
1058
|
|
|
1059 old_size = ht->size;
|
|
|
1060 ht->size = new_size;
|
|
|
1061
|
|
|
1062 old_entries = ht->hentries;
|
|
|
1063
|
|
3092
|
1064 #ifdef NEW_GC
|
|
|
1065 ht->hentries = (htentry *) alloc_lrecord_array (sizeof (htentry),
|
|
|
1066 new_size + 1,
|
|
|
1067 &lrecord_hash_table_entry);
|
|
|
1068 #else /* not NEW_GC */
|
|
1204
|
1069 ht->hentries = xnew_array_and_zero (htentry, new_size + 1);
|
|
3092
|
1070 #endif /* not NEW_GC */
|
|
428
|
1071 new_entries = ht->hentries;
|
|
|
1072
|
|
|
1073 compute_hash_table_derived_values (ht);
|
|
|
1074
|
|
440
|
1075 for (e = old_entries, sentinel = e + old_size; e < sentinel; e++)
|
|
1204
|
1076 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
1077 {
|
|
1204
|
1078 htentry *probe = new_entries + HASHCODE (e->key, ht);
|
|
428
|
1079 LINEAR_PROBING_LOOP (probe, new_entries, new_size)
|
|
|
1080 ;
|
|
|
1081 *probe = *e;
|
|
|
1082 }
|
|
|
1083
|
|
489
|
1084 free_hentries (old_entries, old_size);
|
|
428
|
1085 }
|
|
|
1086
|
|
440
|
1087 /* After a hash table has been saved to disk and later restored by the
|
|
|
1088 portable dumper, it contains the same objects, but their addresses
|
|
665
|
1089 and thus their HASHCODEs have changed. */
|
|
428
|
1090 void
|
|
440
|
1091 pdump_reorganize_hash_table (Lisp_Object hash_table)
|
|
428
|
1092 {
|
|
442
|
1093 const Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
3092
|
1094 #ifdef NEW_GC
|
|
|
1095 htentry *new_entries =
|
|
|
1096 (htentry *) alloc_lrecord_array (sizeof (htentry), ht->size + 1,
|
|
|
1097 &lrecord_hash_table_entry);
|
|
|
1098 #else /* not NEW_GC */
|
|
1204
|
1099 htentry *new_entries = xnew_array_and_zero (htentry, ht->size + 1);
|
|
3092
|
1100 #endif /* not NEW_GC */
|
|
1204
|
1101 htentry *e, *sentinel;
|
|
440
|
1102
|
|
|
1103 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
1204
|
1104 if (!HTENTRY_CLEAR_P (e))
|
|
440
|
1105 {
|
|
1204
|
1106 htentry *probe = new_entries + HASHCODE (e->key, ht);
|
|
440
|
1107 LINEAR_PROBING_LOOP (probe, new_entries, ht->size)
|
|
|
1108 ;
|
|
|
1109 *probe = *e;
|
|
|
1110 }
|
|
|
1111
|
|
1204
|
1112 memcpy (ht->hentries, new_entries, ht->size * sizeof (htentry));
|
|
440
|
1113
|
|
3092
|
1114 #ifdef NEW_GC
|
|
|
1115 mc_free (new_entries);
|
|
|
1116 #else /* not NEW_GC */
|
|
1726
|
1117 xfree (new_entries, htentry *);
|
|
3092
|
1118 #endif /* not NEW_GC */
|
|
428
|
1119 }
|
|
|
1120
|
|
|
1121 static void
|
|
|
1122 enlarge_hash_table (Lisp_Hash_Table *ht)
|
|
|
1123 {
|
|
665
|
1124 Elemcount new_size =
|
|
|
1125 hash_table_size ((Elemcount) ((double) ht->size * ht->rehash_size));
|
|
428
|
1126 resize_hash_table (ht, new_size);
|
|
|
1127 }
|
|
|
1128
|
|
1204
|
1129 static htentry *
|
|
|
1130 find_htentry (Lisp_Object key, const Lisp_Hash_Table *ht)
|
|
428
|
1131 {
|
|
|
1132 hash_table_test_function_t test_function = ht->test_function;
|
|
1204
|
1133 htentry *entries = ht->hentries;
|
|
|
1134 htentry *probe = entries + HASHCODE (key, ht);
|
|
428
|
1135
|
|
|
1136 LINEAR_PROBING_LOOP (probe, entries, ht->size)
|
|
|
1137 if (KEYS_EQUAL_P (probe->key, key, test_function))
|
|
|
1138 break;
|
|
|
1139
|
|
|
1140 return probe;
|
|
|
1141 }
|
|
|
1142
|
|
2421
|
1143 /* A version of Fputhash() that increments the value by the specified
|
|
|
1144 amount and dispenses will all error checks. Assumes that tables does
|
|
|
1145 comparison using EQ. Used by the profiling routines to avoid
|
|
|
1146 overhead -- profiling overhead was being recorded at up to 15% of the
|
|
|
1147 total time. */
|
|
|
1148
|
|
|
1149 void
|
|
|
1150 inchash_eq (Lisp_Object key, Lisp_Object table, EMACS_INT offset)
|
|
|
1151 {
|
|
|
1152 Lisp_Hash_Table *ht = XHASH_TABLE (table);
|
|
|
1153 htentry *entries = ht->hentries;
|
|
|
1154 htentry *probe = entries + HASHCODE (key, ht);
|
|
|
1155
|
|
|
1156 LINEAR_PROBING_LOOP (probe, entries, ht->size)
|
|
|
1157 if (EQ (probe->key, key))
|
|
|
1158 break;
|
|
|
1159
|
|
|
1160 if (!HTENTRY_CLEAR_P (probe))
|
|
|
1161 probe->value = make_int (XINT (probe->value) + offset);
|
|
|
1162 else
|
|
|
1163 {
|
|
|
1164 probe->key = key;
|
|
|
1165 probe->value = make_int (offset);
|
|
|
1166
|
|
|
1167 if (++ht->count >= ht->rehash_count)
|
|
|
1168 enlarge_hash_table (ht);
|
|
|
1169 }
|
|
|
1170 }
|
|
|
1171
|
|
428
|
1172 DEFUN ("gethash", Fgethash, 2, 3, 0, /*
|
|
|
1173 Find hash value for KEY in HASH-TABLE.
|
|
|
1174 If there is no corresponding value, return DEFAULT (which defaults to nil).
|
|
|
1175 */
|
|
|
1176 (key, hash_table, default_))
|
|
|
1177 {
|
|
442
|
1178 const Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
1204
|
1179 htentry *e = find_htentry (key, ht);
|
|
428
|
1180
|
|
1204
|
1181 return HTENTRY_CLEAR_P (e) ? default_ : e->value;
|
|
428
|
1182 }
|
|
|
1183
|
|
|
1184 DEFUN ("puthash", Fputhash, 3, 3, 0, /*
|
|
|
1185 Hash KEY to VALUE in HASH-TABLE.
|
|
|
1186 */
|
|
|
1187 (key, value, hash_table))
|
|
|
1188 {
|
|
|
1189 Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
1204
|
1190 htentry *e = find_htentry (key, ht);
|
|
428
|
1191
|
|
1204
|
1192 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
1193 return e->value = value;
|
|
|
1194
|
|
|
1195 e->key = key;
|
|
|
1196 e->value = value;
|
|
|
1197
|
|
|
1198 if (++ht->count >= ht->rehash_count)
|
|
|
1199 enlarge_hash_table (ht);
|
|
|
1200
|
|
|
1201 return value;
|
|
|
1202 }
|
|
|
1203
|
|
1204
|
1204 /* Remove htentry pointed at by PROBE.
|
|
428
|
1205 Subsequent entries are removed and reinserted.
|
|
|
1206 We don't use tombstones - too wasteful. */
|
|
|
1207 static void
|
|
1204
|
1208 remhash_1 (Lisp_Hash_Table *ht, htentry *entries, htentry *probe)
|
|
428
|
1209 {
|
|
665
|
1210 Elemcount size = ht->size;
|
|
1204
|
1211 CLEAR_HTENTRY (probe);
|
|
428
|
1212 probe++;
|
|
|
1213 ht->count--;
|
|
|
1214
|
|
|
1215 LINEAR_PROBING_LOOP (probe, entries, size)
|
|
|
1216 {
|
|
|
1217 Lisp_Object key = probe->key;
|
|
1204
|
1218 htentry *probe2 = entries + HASHCODE (key, ht);
|
|
428
|
1219 LINEAR_PROBING_LOOP (probe2, entries, size)
|
|
|
1220 if (EQ (probe2->key, key))
|
|
1204
|
1221 /* htentry at probe doesn't need to move. */
|
|
428
|
1222 goto continue_outer_loop;
|
|
1204
|
1223 /* Move htentry from probe to new home at probe2. */
|
|
428
|
1224 *probe2 = *probe;
|
|
1204
|
1225 CLEAR_HTENTRY (probe);
|
|
428
|
1226 continue_outer_loop: continue;
|
|
|
1227 }
|
|
|
1228 }
|
|
|
1229
|
|
|
1230 DEFUN ("remhash", Fremhash, 2, 2, 0, /*
|
|
|
1231 Remove the entry for KEY from HASH-TABLE.
|
|
|
1232 Do nothing if there is no entry for KEY in HASH-TABLE.
|
|
617
|
1233 Return non-nil if an entry was removed.
|
|
428
|
1234 */
|
|
|
1235 (key, hash_table))
|
|
|
1236 {
|
|
|
1237 Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
1204
|
1238 htentry *e = find_htentry (key, ht);
|
|
428
|
1239
|
|
1204
|
1240 if (HTENTRY_CLEAR_P (e))
|
|
428
|
1241 return Qnil;
|
|
|
1242
|
|
|
1243 remhash_1 (ht, ht->hentries, e);
|
|
|
1244 return Qt;
|
|
|
1245 }
|
|
|
1246
|
|
|
1247 DEFUN ("clrhash", Fclrhash, 1, 1, 0, /*
|
|
|
1248 Remove all entries from HASH-TABLE, leaving it empty.
|
|
|
1249 */
|
|
|
1250 (hash_table))
|
|
|
1251 {
|
|
|
1252 Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
1204
|
1253 htentry *e, *sentinel;
|
|
428
|
1254
|
|
|
1255 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
1204
|
1256 CLEAR_HTENTRY (e);
|
|
428
|
1257 ht->count = 0;
|
|
|
1258
|
|
|
1259 return hash_table;
|
|
|
1260 }
|
|
|
1261
|
|
|
1262 /************************************************************************/
|
|
|
1263 /* Accessor Functions */
|
|
|
1264 /************************************************************************/
|
|
|
1265
|
|
|
1266 DEFUN ("hash-table-count", Fhash_table_count, 1, 1, 0, /*
|
|
|
1267 Return the number of entries in HASH-TABLE.
|
|
|
1268 */
|
|
|
1269 (hash_table))
|
|
|
1270 {
|
|
|
1271 return make_int (xhash_table (hash_table)->count);
|
|
|
1272 }
|
|
|
1273
|
|
|
1274 DEFUN ("hash-table-test", Fhash_table_test, 1, 1, 0, /*
|
|
|
1275 Return the test function of HASH-TABLE.
|
|
|
1276 This can be one of `eq', `eql' or `equal'.
|
|
|
1277 */
|
|
|
1278 (hash_table))
|
|
|
1279 {
|
|
|
1280 hash_table_test_function_t fun = xhash_table (hash_table)->test_function;
|
|
|
1281
|
|
|
1282 return (fun == lisp_object_eql_equal ? Qeql :
|
|
|
1283 fun == lisp_object_equal_equal ? Qequal :
|
|
|
1284 Qeq);
|
|
|
1285 }
|
|
|
1286
|
|
|
1287 DEFUN ("hash-table-size", Fhash_table_size, 1, 1, 0, /*
|
|
|
1288 Return the size of HASH-TABLE.
|
|
|
1289 This is the current number of slots in HASH-TABLE, whether occupied or not.
|
|
|
1290 */
|
|
|
1291 (hash_table))
|
|
|
1292 {
|
|
|
1293 return make_int (xhash_table (hash_table)->size);
|
|
|
1294 }
|
|
|
1295
|
|
|
1296 DEFUN ("hash-table-rehash-size", Fhash_table_rehash_size, 1, 1, 0, /*
|
|
|
1297 Return the current rehash size of HASH-TABLE.
|
|
|
1298 This is a float greater than 1.0; the factor by which HASH-TABLE
|
|
|
1299 is enlarged when the rehash threshold is exceeded.
|
|
|
1300 */
|
|
|
1301 (hash_table))
|
|
|
1302 {
|
|
|
1303 return make_float (xhash_table (hash_table)->rehash_size);
|
|
|
1304 }
|
|
|
1305
|
|
|
1306 DEFUN ("hash-table-rehash-threshold", Fhash_table_rehash_threshold, 1, 1, 0, /*
|
|
|
1307 Return the current rehash threshold of HASH-TABLE.
|
|
|
1308 This is a float between 0.0 and 1.0; the maximum `load factor' of HASH-TABLE,
|
|
|
1309 beyond which the HASH-TABLE is enlarged by rehashing.
|
|
|
1310 */
|
|
|
1311 (hash_table))
|
|
|
1312 {
|
|
438
|
1313 return make_float (xhash_table (hash_table)->rehash_threshold);
|
|
428
|
1314 }
|
|
|
1315
|
|
|
1316 DEFUN ("hash-table-weakness", Fhash_table_weakness, 1, 1, 0, /*
|
|
|
1317 Return the weakness of HASH-TABLE.
|
|
442
|
1318 This can be one of `nil', `key-and-value', `key-or-value', `key' or `value'.
|
|
428
|
1319 */
|
|
|
1320 (hash_table))
|
|
|
1321 {
|
|
|
1322 switch (xhash_table (hash_table)->weakness)
|
|
|
1323 {
|
|
442
|
1324 case HASH_TABLE_WEAK: return Qkey_and_value;
|
|
|
1325 case HASH_TABLE_KEY_WEAK: return Qkey;
|
|
|
1326 case HASH_TABLE_KEY_VALUE_WEAK: return Qkey_or_value;
|
|
|
1327 case HASH_TABLE_VALUE_WEAK: return Qvalue;
|
|
|
1328 default: return Qnil;
|
|
428
|
1329 }
|
|
|
1330 }
|
|
|
1331
|
|
|
1332 /* obsolete as of 19990901 in xemacs-21.2 */
|
|
|
1333 DEFUN ("hash-table-type", Fhash_table_type, 1, 1, 0, /*
|
|
|
1334 Return the type of HASH-TABLE.
|
|
|
1335 This can be one of `non-weak', `weak', `key-weak' or `value-weak'.
|
|
|
1336 */
|
|
|
1337 (hash_table))
|
|
|
1338 {
|
|
|
1339 switch (xhash_table (hash_table)->weakness)
|
|
|
1340 {
|
|
442
|
1341 case HASH_TABLE_WEAK: return Qweak;
|
|
|
1342 case HASH_TABLE_KEY_WEAK: return Qkey_weak;
|
|
|
1343 case HASH_TABLE_KEY_VALUE_WEAK: return Qkey_or_value_weak;
|
|
|
1344 case HASH_TABLE_VALUE_WEAK: return Qvalue_weak;
|
|
|
1345 default: return Qnon_weak;
|
|
428
|
1346 }
|
|
|
1347 }
|
|
|
1348
|
|
|
1349 /************************************************************************/
|
|
|
1350 /* Mapping Functions */
|
|
|
1351 /************************************************************************/
|
|
489
|
1352
|
|
|
1353 /* We need to be careful when mapping over hash tables because the
|
|
|
1354 hash table might be modified during the mapping operation:
|
|
|
1355 - by the mapping function
|
|
|
1356 - by gc (if the hash table is weak)
|
|
|
1357
|
|
|
1358 So we make a copy of the hentries at the beginning of the mapping
|
|
497
|
1359 operation, and iterate over the copy. Naturally, this is
|
|
|
1360 expensive, but not as expensive as you might think, because no
|
|
|
1361 actual memory has to be collected by our notoriously inefficient
|
|
|
1362 GC; we use an unwind-protect instead to free the memory directly.
|
|
|
1363
|
|
|
1364 We could avoid the copying by having the hash table modifiers
|
|
|
1365 puthash and remhash check for currently active mapping functions.
|
|
|
1366 Disadvantages: it's hard to get right, and IMO hash mapping
|
|
|
1367 functions are basically rare, and no extra space in the hash table
|
|
|
1368 object and no extra cpu in puthash or remhash should be wasted to
|
|
|
1369 make maphash 3% faster. From a design point of view, the basic
|
|
|
1370 functions gethash, puthash and remhash should be implementable
|
|
|
1371 without having to think about maphash.
|
|
|
1372
|
|
|
1373 Note: We don't (yet) have Common Lisp's with-hash-table-iterator.
|
|
|
1374 If you implement this naively, you cannot have more than one
|
|
|
1375 concurrently active iterator over the same hash table. The `each'
|
|
|
1376 function in perl has this limitation.
|
|
|
1377
|
|
|
1378 Note: We GCPRO memory on the heap, not on the stack. There is no
|
|
|
1379 obvious reason why this is bad, but as of this writing this is the
|
|
|
1380 only known occurrence of this technique in the code.
|
|
504
|
1381
|
|
|
1382 -- Martin
|
|
|
1383 */
|
|
|
1384
|
|
|
1385 /* Ben disagrees with the "copying hentries" design, and says:
|
|
|
1386
|
|
|
1387 Another solution is the same as I've already proposed -- when
|
|
|
1388 mapping, mark the table as "change-unsafe", and in this case, use a
|
|
|
1389 secondary table to maintain changes. this could be basically a
|
|
|
1390 standard hash table, but with entries only for added or deleted
|
|
|
1391 entries in the primary table, and a marker like Qunbound to
|
|
|
1392 indicate a deleted entry. puthash, gethash and remhash need a
|
|
|
1393 single extra check for this secondary table -- totally
|
|
|
1394 insignificant speedwise. if you really cared about making
|
|
|
1395 recursive maphashes completely correct, you'd have to do a bit of
|
|
|
1396 extra work here -- when maphashing, if the secondary table exists,
|
|
|
1397 make a copy of it, and use the copy in conjunction with the primary
|
|
|
1398 table when mapping. the advantages of this are
|
|
|
1399
|
|
|
1400 [a] easy to demonstrate correct, even with weak hashtables.
|
|
|
1401
|
|
|
1402 [b] no extra overhead in the general maphash case -- only when you
|
|
|
1403 modify the table while maphashing, and even then the overhead is
|
|
|
1404 very small.
|
|
497
|
1405 */
|
|
|
1406
|
|
489
|
1407 static Lisp_Object
|
|
|
1408 maphash_unwind (Lisp_Object unwind_obj)
|
|
|
1409 {
|
|
|
1410 void *ptr = (void *) get_opaque_ptr (unwind_obj);
|
|
1726
|
1411 xfree (ptr, void *);
|
|
489
|
1412 free_opaque_ptr (unwind_obj);
|
|
|
1413 return Qnil;
|
|
|
1414 }
|
|
|
1415
|
|
|
1416 /* Return a malloced array of alternating key/value pairs from HT. */
|
|
|
1417 static Lisp_Object *
|
|
|
1418 copy_compress_hentries (const Lisp_Hash_Table *ht)
|
|
|
1419 {
|
|
|
1420 Lisp_Object * const objs =
|
|
|
1421 /* If the hash table is empty, ht->count could be 0. */
|
|
|
1422 xnew_array (Lisp_Object, 2 * (ht->count > 0 ? ht->count : 1));
|
|
1204
|
1423 const htentry *e, *sentinel;
|
|
489
|
1424 Lisp_Object *pobj;
|
|
|
1425
|
|
|
1426 for (e = ht->hentries, sentinel = e + ht->size, pobj = objs; e < sentinel; e++)
|
|
1204
|
1427 if (!HTENTRY_CLEAR_P (e))
|
|
489
|
1428 {
|
|
|
1429 *(pobj++) = e->key;
|
|
|
1430 *(pobj++) = e->value;
|
|
|
1431 }
|
|
|
1432
|
|
|
1433 type_checking_assert (pobj == objs + 2 * ht->count);
|
|
|
1434
|
|
|
1435 return objs;
|
|
|
1436 }
|
|
|
1437
|
|
428
|
1438 DEFUN ("maphash", Fmaphash, 2, 2, 0, /*
|
|
|
1439 Map FUNCTION over entries in HASH-TABLE, calling it with two args,
|
|
|
1440 each key and value in HASH-TABLE.
|
|
|
1441
|
|
489
|
1442 FUNCTION must not modify HASH-TABLE, with the one exception that FUNCTION
|
|
428
|
1443 may remhash or puthash the entry currently being processed by FUNCTION.
|
|
|
1444 */
|
|
|
1445 (function, hash_table))
|
|
|
1446 {
|
|
489
|
1447 const Lisp_Hash_Table * const ht = xhash_table (hash_table);
|
|
|
1448 Lisp_Object * const objs = copy_compress_hentries (ht);
|
|
|
1449 Lisp_Object args[3];
|
|
|
1450 const Lisp_Object *pobj, *end;
|
|
|
1451 int speccount = specpdl_depth ();
|
|
|
1452 struct gcpro gcpro1;
|
|
|
1453
|
|
|
1454 record_unwind_protect (maphash_unwind, make_opaque_ptr ((void *)objs));
|
|
|
1455 GCPRO1 (objs[0]);
|
|
|
1456 gcpro1.nvars = 2 * ht->count;
|
|
428
|
1457
|
|
489
|
1458 args[0] = function;
|
|
|
1459
|
|
|
1460 for (pobj = objs, end = pobj + 2 * ht->count; pobj < end; pobj += 2)
|
|
|
1461 {
|
|
|
1462 args[1] = pobj[0];
|
|
|
1463 args[2] = pobj[1];
|
|
|
1464 Ffuncall (countof (args), args);
|
|
|
1465 }
|
|
|
1466
|
|
771
|
1467 unbind_to (speccount);
|
|
489
|
1468 UNGCPRO;
|
|
428
|
1469
|
|
|
1470 return Qnil;
|
|
|
1471 }
|
|
|
1472
|
|
489
|
1473 /* Map *C* function FUNCTION over the elements of a non-weak lisp hash table.
|
|
|
1474 FUNCTION must not modify HASH-TABLE, with the one exception that FUNCTION
|
|
|
1475 may puthash the entry currently being processed by FUNCTION.
|
|
|
1476 Mapping terminates if FUNCTION returns something other than 0. */
|
|
428
|
1477 void
|
|
489
|
1478 elisp_maphash_unsafe (maphash_function_t function,
|
|
428
|
1479 Lisp_Object hash_table, void *extra_arg)
|
|
|
1480 {
|
|
442
|
1481 const Lisp_Hash_Table *ht = XHASH_TABLE (hash_table);
|
|
1204
|
1482 const htentry *e, *sentinel;
|
|
428
|
1483
|
|
|
1484 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
1204
|
1485 if (!HTENTRY_CLEAR_P (e))
|
|
489
|
1486 if (function (e->key, e->value, extra_arg))
|
|
|
1487 return;
|
|
428
|
1488 }
|
|
|
1489
|
|
489
|
1490 /* Map *C* function FUNCTION over the elements of a lisp hash table.
|
|
|
1491 It is safe for FUNCTION to modify HASH-TABLE.
|
|
|
1492 Mapping terminates if FUNCTION returns something other than 0. */
|
|
|
1493 void
|
|
|
1494 elisp_maphash (maphash_function_t function,
|
|
|
1495 Lisp_Object hash_table, void *extra_arg)
|
|
|
1496 {
|
|
|
1497 const Lisp_Hash_Table * const ht = xhash_table (hash_table);
|
|
|
1498 Lisp_Object * const objs = copy_compress_hentries (ht);
|
|
|
1499 const Lisp_Object *pobj, *end;
|
|
|
1500 int speccount = specpdl_depth ();
|
|
|
1501 struct gcpro gcpro1;
|
|
|
1502
|
|
|
1503 record_unwind_protect (maphash_unwind, make_opaque_ptr ((void *)objs));
|
|
|
1504 GCPRO1 (objs[0]);
|
|
|
1505 gcpro1.nvars = 2 * ht->count;
|
|
|
1506
|
|
|
1507 for (pobj = objs, end = pobj + 2 * ht->count; pobj < end; pobj += 2)
|
|
|
1508 if (function (pobj[0], pobj[1], extra_arg))
|
|
|
1509 break;
|
|
|
1510
|
|
771
|
1511 unbind_to (speccount);
|
|
489
|
1512 UNGCPRO;
|
|
|
1513 }
|
|
|
1514
|
|
|
1515 /* Remove all elements of a lisp hash table satisfying *C* predicate PREDICATE.
|
|
|
1516 PREDICATE must not modify HASH-TABLE. */
|
|
428
|
1517 void
|
|
|
1518 elisp_map_remhash (maphash_function_t predicate,
|
|
|
1519 Lisp_Object hash_table, void *extra_arg)
|
|
|
1520 {
|
|
489
|
1521 const Lisp_Hash_Table * const ht = xhash_table (hash_table);
|
|
|
1522 Lisp_Object * const objs = copy_compress_hentries (ht);
|
|
|
1523 const Lisp_Object *pobj, *end;
|
|
|
1524 int speccount = specpdl_depth ();
|
|
|
1525 struct gcpro gcpro1;
|
|
428
|
1526
|
|
489
|
1527 record_unwind_protect (maphash_unwind, make_opaque_ptr ((void *)objs));
|
|
|
1528 GCPRO1 (objs[0]);
|
|
|
1529 gcpro1.nvars = 2 * ht->count;
|
|
|
1530
|
|
|
1531 for (pobj = objs, end = pobj + 2 * ht->count; pobj < end; pobj += 2)
|
|
|
1532 if (predicate (pobj[0], pobj[1], extra_arg))
|
|
|
1533 Fremhash (pobj[0], hash_table);
|
|
|
1534
|
|
771
|
1535 unbind_to (speccount);
|
|
489
|
1536 UNGCPRO;
|
|
428
|
1537 }
|
|
|
1538
|
|
|
1539
|
|
|
1540 /************************************************************************/
|
|
|
1541 /* garbage collecting weak hash tables */
|
|
|
1542 /************************************************************************/
|
|
1598
|
1543 #ifdef USE_KKCC
|
|
2645
|
1544 #define MARK_OBJ(obj) do { \
|
|
|
1545 Lisp_Object mo_obj = (obj); \
|
|
|
1546 if (!marked_p (mo_obj)) \
|
|
|
1547 { \
|
|
|
1548 kkcc_gc_stack_push_lisp_object (mo_obj, 0, -1); \
|
|
|
1549 did_mark = 1; \
|
|
|
1550 } \
|
|
1598
|
1551 } while (0)
|
|
|
1552
|
|
|
1553 #else /* NO USE_KKCC */
|
|
|
1554
|
|
442
|
1555 #define MARK_OBJ(obj) do { \
|
|
|
1556 Lisp_Object mo_obj = (obj); \
|
|
|
1557 if (!marked_p (mo_obj)) \
|
|
|
1558 { \
|
|
|
1559 mark_object (mo_obj); \
|
|
|
1560 did_mark = 1; \
|
|
|
1561 } \
|
|
|
1562 } while (0)
|
|
1598
|
1563 #endif /*NO USE_KKCC */
|
|
442
|
1564
|
|
428
|
1565
|
|
|
1566 /* Complete the marking for semi-weak hash tables. */
|
|
|
1567 int
|
|
|
1568 finish_marking_weak_hash_tables (void)
|
|
|
1569 {
|
|
|
1570 Lisp_Object hash_table;
|
|
|
1571 int did_mark = 0;
|
|
|
1572
|
|
|
1573 for (hash_table = Vall_weak_hash_tables;
|
|
|
1574 !NILP (hash_table);
|
|
|
1575 hash_table = XHASH_TABLE (hash_table)->next_weak)
|
|
|
1576 {
|
|
442
|
1577 const Lisp_Hash_Table *ht = XHASH_TABLE (hash_table);
|
|
1204
|
1578 const htentry *e = ht->hentries;
|
|
|
1579 const htentry *sentinel = e + ht->size;
|
|
428
|
1580
|
|
|
1581 if (! marked_p (hash_table))
|
|
|
1582 /* The hash table is probably garbage. Ignore it. */
|
|
|
1583 continue;
|
|
|
1584
|
|
|
1585 /* Now, scan over all the pairs. For all pairs that are
|
|
|
1586 half-marked, we may need to mark the other half if we're
|
|
|
1587 keeping this pair. */
|
|
|
1588 switch (ht->weakness)
|
|
|
1589 {
|
|
|
1590 case HASH_TABLE_KEY_WEAK:
|
|
|
1591 for (; e < sentinel; e++)
|
|
1204
|
1592 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
1593 if (marked_p (e->key))
|
|
|
1594 MARK_OBJ (e->value);
|
|
|
1595 break;
|
|
|
1596
|
|
|
1597 case HASH_TABLE_VALUE_WEAK:
|
|
|
1598 for (; e < sentinel; e++)
|
|
1204
|
1599 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
1600 if (marked_p (e->value))
|
|
|
1601 MARK_OBJ (e->key);
|
|
|
1602 break;
|
|
|
1603
|
|
442
|
1604 case HASH_TABLE_KEY_VALUE_WEAK:
|
|
|
1605 for (; e < sentinel; e++)
|
|
1204
|
1606 if (!HTENTRY_CLEAR_P (e))
|
|
442
|
1607 {
|
|
|
1608 if (marked_p (e->value))
|
|
|
1609 MARK_OBJ (e->key);
|
|
|
1610 else if (marked_p (e->key))
|
|
|
1611 MARK_OBJ (e->value);
|
|
|
1612 }
|
|
|
1613 break;
|
|
|
1614
|
|
428
|
1615 case HASH_TABLE_KEY_CAR_WEAK:
|
|
|
1616 for (; e < sentinel; e++)
|
|
1204
|
1617 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
1618 if (!CONSP (e->key) || marked_p (XCAR (e->key)))
|
|
|
1619 {
|
|
|
1620 MARK_OBJ (e->key);
|
|
|
1621 MARK_OBJ (e->value);
|
|
|
1622 }
|
|
|
1623 break;
|
|
|
1624
|
|
450
|
1625 /* We seem to be sprouting new weakness types at an alarming
|
|
|
1626 rate. At least this is not externally visible - and in
|
|
|
1627 fact all of these KEY_CAR_* types are only used by the
|
|
|
1628 glyph code. */
|
|
|
1629 case HASH_TABLE_KEY_CAR_VALUE_WEAK:
|
|
|
1630 for (; e < sentinel; e++)
|
|
1204
|
1631 if (!HTENTRY_CLEAR_P (e))
|
|
450
|
1632 {
|
|
|
1633 if (!CONSP (e->key) || marked_p (XCAR (e->key)))
|
|
|
1634 {
|
|
|
1635 MARK_OBJ (e->key);
|
|
|
1636 MARK_OBJ (e->value);
|
|
|
1637 }
|
|
|
1638 else if (marked_p (e->value))
|
|
|
1639 MARK_OBJ (e->key);
|
|
|
1640 }
|
|
|
1641 break;
|
|
|
1642
|
|
428
|
1643 case HASH_TABLE_VALUE_CAR_WEAK:
|
|
|
1644 for (; e < sentinel; e++)
|
|
1204
|
1645 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
1646 if (!CONSP (e->value) || marked_p (XCAR (e->value)))
|
|
|
1647 {
|
|
|
1648 MARK_OBJ (e->key);
|
|
|
1649 MARK_OBJ (e->value);
|
|
|
1650 }
|
|
|
1651 break;
|
|
|
1652
|
|
|
1653 default:
|
|
|
1654 break;
|
|
|
1655 }
|
|
|
1656 }
|
|
|
1657
|
|
|
1658 return did_mark;
|
|
|
1659 }
|
|
|
1660
|
|
|
1661 void
|
|
|
1662 prune_weak_hash_tables (void)
|
|
|
1663 {
|
|
|
1664 Lisp_Object hash_table, prev = Qnil;
|
|
|
1665 for (hash_table = Vall_weak_hash_tables;
|
|
|
1666 !NILP (hash_table);
|
|
|
1667 hash_table = XHASH_TABLE (hash_table)->next_weak)
|
|
|
1668 {
|
|
|
1669 if (! marked_p (hash_table))
|
|
|
1670 {
|
|
|
1671 /* This hash table itself is garbage. Remove it from the list. */
|
|
|
1672 if (NILP (prev))
|
|
|
1673 Vall_weak_hash_tables = XHASH_TABLE (hash_table)->next_weak;
|
|
|
1674 else
|
|
|
1675 XHASH_TABLE (prev)->next_weak = XHASH_TABLE (hash_table)->next_weak;
|
|
|
1676 }
|
|
|
1677 else
|
|
|
1678 {
|
|
|
1679 /* Now, scan over all the pairs. Remove all of the pairs
|
|
|
1680 in which the key or value, or both, is unmarked
|
|
|
1681 (depending on the weakness of the hash table). */
|
|
|
1682 Lisp_Hash_Table *ht = XHASH_TABLE (hash_table);
|
|
1204
|
1683 htentry *entries = ht->hentries;
|
|
|
1684 htentry *sentinel = entries + ht->size;
|
|
|
1685 htentry *e;
|
|
428
|
1686
|
|
|
1687 for (e = entries; e < sentinel; e++)
|
|
1204
|
1688 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
1689 {
|
|
|
1690 again:
|
|
|
1691 if (!marked_p (e->key) || !marked_p (e->value))
|
|
|
1692 {
|
|
|
1693 remhash_1 (ht, entries, e);
|
|
1204
|
1694 if (!HTENTRY_CLEAR_P (e))
|
|
428
|
1695 goto again;
|
|
|
1696 }
|
|
|
1697 }
|
|
|
1698
|
|
|
1699 prev = hash_table;
|
|
|
1700 }
|
|
|
1701 }
|
|
|
1702 }
|
|
|
1703
|
|
|
1704 /* Return a hash value for an array of Lisp_Objects of size SIZE. */
|
|
|
1705
|
|
665
|
1706 Hashcode
|
|
428
|
1707 internal_array_hash (Lisp_Object *arr, int size, int depth)
|
|
|
1708 {
|
|
|
1709 int i;
|
|
665
|
1710 Hashcode hash = 0;
|
|
442
|
1711 depth++;
|
|
428
|
1712
|
|
|
1713 if (size <= 5)
|
|
|
1714 {
|
|
|
1715 for (i = 0; i < size; i++)
|
|
442
|
1716 hash = HASH2 (hash, internal_hash (arr[i], depth));
|
|
428
|
1717 return hash;
|
|
|
1718 }
|
|
|
1719
|
|
|
1720 /* just pick five elements scattered throughout the array.
|
|
|
1721 A slightly better approach would be to offset by some
|
|
|
1722 noise factor from the points chosen below. */
|
|
|
1723 for (i = 0; i < 5; i++)
|
|
442
|
1724 hash = HASH2 (hash, internal_hash (arr[i*size/5], depth));
|
|
428
|
1725
|
|
|
1726 return hash;
|
|
|
1727 }
|
|
|
1728
|
|
|
1729 /* Return a hash value for a Lisp_Object. This is for use when hashing
|
|
|
1730 objects with the comparison being `equal' (for `eq', you can just
|
|
|
1731 use the Lisp_Object itself as the hash value). You need to make a
|
|
|
1732 tradeoff between the speed of the hash function and how good the
|
|
|
1733 hashing is. In particular, the hash function needs to be FAST,
|
|
|
1734 so you can't just traipse down the whole tree hashing everything
|
|
|
1735 together. Most of the time, objects will differ in the first
|
|
|
1736 few elements you hash. Thus, we only go to a short depth (5)
|
|
|
1737 and only hash at most 5 elements out of a vector. Theoretically
|
|
|
1738 we could still take 5^5 time (a big big number) to compute a
|
|
|
1739 hash, but practically this won't ever happen. */
|
|
|
1740
|
|
665
|
1741 Hashcode
|
|
428
|
1742 internal_hash (Lisp_Object obj, int depth)
|
|
|
1743 {
|
|
|
1744 if (depth > 5)
|
|
|
1745 return 0;
|
|
|
1746 if (CONSP (obj))
|
|
|
1747 {
|
|
|
1748 /* no point in worrying about tail recursion, since we're not
|
|
|
1749 going very deep */
|
|
|
1750 return HASH2 (internal_hash (XCAR (obj), depth + 1),
|
|
|
1751 internal_hash (XCDR (obj), depth + 1));
|
|
|
1752 }
|
|
|
1753 if (STRINGP (obj))
|
|
|
1754 {
|
|
|
1755 return hash_string (XSTRING_DATA (obj), XSTRING_LENGTH (obj));
|
|
|
1756 }
|
|
|
1757 if (LRECORDP (obj))
|
|
|
1758 {
|
|
442
|
1759 const struct lrecord_implementation
|
|
428
|
1760 *imp = XRECORD_LHEADER_IMPLEMENTATION (obj);
|
|
|
1761 if (imp->hash)
|
|
|
1762 return imp->hash (obj, depth);
|
|
|
1763 }
|
|
|
1764
|
|
|
1765 return LISP_HASH (obj);
|
|
|
1766 }
|
|
|
1767
|
|
|
1768 DEFUN ("sxhash", Fsxhash, 1, 1, 0, /*
|
|
|
1769 Return a hash value for OBJECT.
|
|
444
|
1770 \(equal obj1 obj2) implies (= (sxhash obj1) (sxhash obj2)).
|
|
428
|
1771 */
|
|
|
1772 (object))
|
|
|
1773 {
|
|
|
1774 return make_int (internal_hash (object, 0));
|
|
|
1775 }
|
|
|
1776
|
|
|
1777 #if 0
|
|
826
|
1778 DEFUN ("internal-hash-value", Finternal_hash_value, 1, 1, 0, /*
|
|
428
|
1779 Hash value of OBJECT. For debugging.
|
|
|
1780 The value is returned as (HIGH . LOW).
|
|
|
1781 */
|
|
|
1782 (object))
|
|
|
1783 {
|
|
|
1784 /* This function is pretty 32bit-centric. */
|
|
665
|
1785 Hashcode hash = internal_hash (object, 0);
|
|
428
|
1786 return Fcons (hash >> 16, hash & 0xffff);
|
|
|
1787 }
|
|
|
1788 #endif
|
|
|
1789
|
|
|
1790
|
|
|
1791 /************************************************************************/
|
|
|
1792 /* initialization */
|
|
|
1793 /************************************************************************/
|
|
|
1794
|
|
|
1795 void
|
|
|
1796 syms_of_elhash (void)
|
|
|
1797 {
|
|
|
1798 DEFSUBR (Fhash_table_p);
|
|
|
1799 DEFSUBR (Fmake_hash_table);
|
|
|
1800 DEFSUBR (Fcopy_hash_table);
|
|
|
1801 DEFSUBR (Fgethash);
|
|
|
1802 DEFSUBR (Fremhash);
|
|
|
1803 DEFSUBR (Fputhash);
|
|
|
1804 DEFSUBR (Fclrhash);
|
|
|
1805 DEFSUBR (Fmaphash);
|
|
|
1806 DEFSUBR (Fhash_table_count);
|
|
|
1807 DEFSUBR (Fhash_table_test);
|
|
|
1808 DEFSUBR (Fhash_table_size);
|
|
|
1809 DEFSUBR (Fhash_table_rehash_size);
|
|
|
1810 DEFSUBR (Fhash_table_rehash_threshold);
|
|
|
1811 DEFSUBR (Fhash_table_weakness);
|
|
|
1812 DEFSUBR (Fhash_table_type); /* obsolete */
|
|
|
1813 DEFSUBR (Fsxhash);
|
|
|
1814 #if 0
|
|
|
1815 DEFSUBR (Finternal_hash_value);
|
|
|
1816 #endif
|
|
|
1817
|
|
563
|
1818 DEFSYMBOL_MULTIWORD_PREDICATE (Qhash_tablep);
|
|
|
1819 DEFSYMBOL (Qhash_table);
|
|
|
1820 DEFSYMBOL (Qhashtable);
|
|
|
1821 DEFSYMBOL (Qweakness);
|
|
|
1822 DEFSYMBOL (Qvalue);
|
|
|
1823 DEFSYMBOL (Qkey_or_value);
|
|
|
1824 DEFSYMBOL (Qkey_and_value);
|
|
|
1825 DEFSYMBOL (Qrehash_size);
|
|
|
1826 DEFSYMBOL (Qrehash_threshold);
|
|
428
|
1827
|
|
563
|
1828 DEFSYMBOL (Qweak); /* obsolete */
|
|
|
1829 DEFSYMBOL (Qkey_weak); /* obsolete */
|
|
|
1830 DEFSYMBOL (Qkey_or_value_weak); /* obsolete */
|
|
|
1831 DEFSYMBOL (Qvalue_weak); /* obsolete */
|
|
|
1832 DEFSYMBOL (Qnon_weak); /* obsolete */
|
|
428
|
1833
|
|
563
|
1834 DEFKEYWORD (Q_test);
|
|
|
1835 DEFKEYWORD (Q_size);
|
|
|
1836 DEFKEYWORD (Q_rehash_size);
|
|
|
1837 DEFKEYWORD (Q_rehash_threshold);
|
|
|
1838 DEFKEYWORD (Q_weakness);
|
|
|
1839 DEFKEYWORD (Q_type); /* obsolete */
|
|
428
|
1840 }
|
|
|
1841
|
|
|
1842 void
|
|
771
|
1843 init_elhash_once_early (void)
|
|
428
|
1844 {
|
|
771
|
1845 INIT_LRECORD_IMPLEMENTATION (hash_table);
|
|
3092
|
1846 #ifdef NEW_GC
|
|
|
1847 INIT_LRECORD_IMPLEMENTATION (hash_table_entry);
|
|
|
1848 #endif /* NEW_GC */
|
|
771
|
1849
|
|
428
|
1850 /* This must NOT be staticpro'd */
|
|
|
1851 Vall_weak_hash_tables = Qnil;
|
|
452
|
1852 dump_add_weak_object_chain (&Vall_weak_hash_tables);
|
|
428
|
1853 }
|
