|
380
|
1 /* Implementation of the hash table lisp object type.
|
|
0
|
2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
|
|
|
3 Copyright (C) 1995, 1996 Ben Wing.
|
|
223
|
4 Copyright (C) 1997 Free Software Foundation, Inc.
|
|
0
|
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
|
|
380
|
14 ANY WARRANTY; without even the implied warranty of MERCNTABILITY or
|
|
0
|
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
|
|
|
25 #include <config.h>
|
|
|
26 #include "lisp.h"
|
|
380
|
27 #include "bytecode.h"
|
|
0
|
28 #include "elhash.h"
|
|
|
29
|
|
412
|
30 Lisp_Object Qhash_tablep, Qhashtable, Qhash_table;
|
|
|
31 Lisp_Object Qweak, Qkey_weak, Qvalue_weak, Qnon_weak;
|
|
380
|
32 static Lisp_Object Vall_weak_hash_tables;
|
|
|
33 static Lisp_Object Qrehash_size, Qrehash_threshold;
|
|
412
|
34 static Lisp_Object Q_size, Q_test, Q_type, Q_rehash_size, Q_rehash_threshold;
|
|
272
|
35
|
|
380
|
36 typedef struct hentry
|
|
|
37 {
|
|
|
38 Lisp_Object key;
|
|
|
39 Lisp_Object value;
|
|
|
40 } hentry;
|
|
0
|
41
|
|
380
|
42 struct Lisp_Hash_Table
|
|
0
|
43 {
|
|
|
44 struct lcrecord_header header;
|
|
380
|
45 size_t size;
|
|
|
46 size_t count;
|
|
|
47 size_t rehash_count;
|
|
|
48 double rehash_size;
|
|
|
49 double rehash_threshold;
|
|
394
|
50 size_t golden_ratio;
|
|
380
|
51 hash_table_hash_function_t hash_function;
|
|
|
52 hash_table_test_function_t test_function;
|
|
|
53 hentry *hentries;
|
|
412
|
54 enum hash_table_type type; /* whether and how this hash table is weak */
|
|
380
|
55 Lisp_Object next_weak; /* Used to chain together all of the weak
|
|
|
56 hash tables. Don't mark through this. */
|
|
0
|
57 };
|
|
412
|
58 typedef struct Lisp_Hash_Table Lisp_Hash_Table;
|
|
0
|
59
|
|
380
|
60 #define HENTRY_CLEAR_P(hentry) ((*(EMACS_UINT*)(&((hentry)->key))) == 0)
|
|
412
|
61 #define CLEAR_HENTRY(hentry) ((*(EMACS_UINT*)(&((hentry)->key))) = 0)
|
|
380
|
62
|
|
|
63 #define HASH_TABLE_DEFAULT_SIZE 16
|
|
|
64 #define HASH_TABLE_DEFAULT_REHASH_SIZE 1.3
|
|
|
65 #define HASH_TABLE_MIN_SIZE 10
|
|
|
66
|
|
412
|
67 #define HASH_CODE(key, ht) \
|
|
|
68 (((((ht)->hash_function ? (ht)->hash_function (key) : LISP_HASH (key)) \
|
|
|
69 * (ht)->golden_ratio) \
|
|
|
70 % (ht)->size))
|
|
380
|
71
|
|
|
72 #define KEYS_EQUAL_P(key1, key2, testfun) \
|
|
412
|
73 (EQ ((key1), (key2)) || ((testfun) && (testfun) ((key1), (key2))))
|
|
380
|
74
|
|
|
75 #define LINEAR_PROBING_LOOP(probe, entries, size) \
|
|
|
76 for (; \
|
|
|
77 !HENTRY_CLEAR_P (probe) || \
|
|
|
78 (probe == entries + size ? \
|
|
|
79 (probe = entries, !HENTRY_CLEAR_P (probe)) : 0); \
|
|
|
80 probe++)
|
|
|
81
|
|
|
82 #ifndef ERROR_CHECK_HASH_TABLE
|
|
|
83 # ifdef ERROR_CHECK_TYPECHECK
|
|
|
84 # define ERROR_CHECK_HASH_TABLE 1
|
|
|
85 # else
|
|
|
86 # define ERROR_CHECK_HASH_TABLE 0
|
|
|
87 # endif
|
|
|
88 #endif
|
|
0
|
89
|
|
380
|
90 #if ERROR_CHECK_HASH_TABLE
|
|
|
91 static void
|
|
|
92 check_hash_table_invariants (Lisp_Hash_Table *ht)
|
|
0
|
93 {
|
|
380
|
94 assert (ht->count < ht->size);
|
|
|
95 assert (ht->count <= ht->rehash_count);
|
|
|
96 assert (ht->rehash_count < ht->size);
|
|
|
97 assert ((double) ht->count * ht->rehash_threshold - 1 <= (double) ht->rehash_count);
|
|
|
98 assert (HENTRY_CLEAR_P (ht->hentries + ht->size));
|
|
|
99 }
|
|
|
100 #else
|
|
|
101 #define check_hash_table_invariants(ht)
|
|
|
102 #endif
|
|
|
103
|
|
|
104 /* We use linear probing instead of double hashing, despite its lack
|
|
|
105 of blessing by Knuth and company, because, as a result of the
|
|
|
106 increasing discrepancy between CPU speeds and memory speeds, cache
|
|
|
107 behavior is becoming increasingly important, e.g:
|
|
|
108
|
|
|
109 For a trivial loop, the penalty for non-sequential access of an array is:
|
|
|
110 - a factor of 3-4 on Pentium Pro 200 Mhz
|
|
|
111 - a factor of 10 on Ultrasparc 300 Mhz */
|
|
0
|
112
|
|
380
|
113 /* Return a suitable size for a hash table, with at least SIZE slots. */
|
|
|
114 static size_t
|
|
|
115 hash_table_size (size_t requested_size)
|
|
|
116 {
|
|
|
117 /* Return some prime near, but greater than or equal to, SIZE.
|
|
|
118 Decades from the time of writing, someone will have a system large
|
|
|
119 enough that the list below will be too short... */
|
|
412
|
120 static CONST size_t primes [] =
|
|
380
|
121 {
|
|
|
122 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
|
|
|
123 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
|
|
|
124 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
|
|
|
125 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
|
|
|
126 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
|
|
|
127 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
|
|
|
128 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
|
|
|
129 243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
|
|
|
130 1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
|
|
|
131 };
|
|
|
132 /* We've heard of binary search. */
|
|
|
133 int low, high;
|
|
|
134 for (low = 0, high = countof (primes) - 1; high - low > 1;)
|
|
0
|
135 {
|
|
380
|
136 /* Loop Invariant: size < primes [high] */
|
|
|
137 int mid = (low + high) / 2;
|
|
|
138 if (primes [mid] < requested_size)
|
|
|
139 low = mid;
|
|
|
140 else
|
|
|
141 high = mid;
|
|
0
|
142 }
|
|
380
|
143 return primes [high];
|
|
0
|
144 }
|
|
380
|
145
|
|
223
|
146
|
|
380
|
147 #if 0 /* I don't think these are needed any more.
|
|
|
148 If using the general lisp_object_equal_*() functions
|
|
|
149 causes efficiency problems, these can be resurrected. --ben */
|
|
|
150 /* equality and hash functions for Lisp strings */
|
|
|
151 int
|
|
|
152 lisp_string_equal (Lisp_Object str1, Lisp_Object str2)
|
|
|
153 {
|
|
|
154 /* This is wrong anyway. You can't use strcmp() on Lisp strings,
|
|
|
155 because they can contain zero characters. */
|
|
|
156 return !strcmp ((char *) XSTRING_DATA (str1), (char *) XSTRING_DATA (str2));
|
|
|
157 }
|
|
231
|
158
|
|
380
|
159 static hashcode_t
|
|
|
160 lisp_string_hash (Lisp_Object obj)
|
|
231
|
161 {
|
|
380
|
162 return hash_string (XSTRING_DATA (str), XSTRING_LENGTH (str));
|
|
|
163 }
|
|
|
164
|
|
|
165 #endif /* 0 */
|
|
231
|
166
|
|
241
|
167 static int
|
|
380
|
168 lisp_object_eql_equal (Lisp_Object obj1, Lisp_Object obj2)
|
|
231
|
169 {
|
|
380
|
170 return EQ (obj1, obj2) || (FLOATP (obj1) && internal_equal (obj1, obj2, 0));
|
|
|
171 }
|
|
231
|
172
|
|
380
|
173 static hashcode_t
|
|
|
174 lisp_object_eql_hash (Lisp_Object obj)
|
|
|
175 {
|
|
|
176 return FLOATP (obj) ? internal_hash (obj, 0) : LISP_HASH (obj);
|
|
231
|
177 }
|
|
|
178
|
|
|
179 static int
|
|
380
|
180 lisp_object_equal_equal (Lisp_Object obj1, Lisp_Object obj2)
|
|
|
181 {
|
|
|
182 return internal_equal (obj1, obj2, 0);
|
|
|
183 }
|
|
|
184
|
|
|
185 static hashcode_t
|
|
|
186 lisp_object_equal_hash (Lisp_Object obj)
|
|
231
|
187 {
|
|
380
|
188 return internal_hash (obj, 0);
|
|
|
189 }
|
|
|
190
|
|
|
191
|
|
|
192 static Lisp_Object
|
|
412
|
193 mark_hash_table (Lisp_Object obj, void (*markobj) (Lisp_Object))
|
|
380
|
194 {
|
|
|
195 Lisp_Hash_Table *ht = XHASH_TABLE (obj);
|
|
|
196
|
|
|
197 /* If the hash table is weak, we don't want to mark the keys and
|
|
|
198 values (we scan over them after everything else has been marked,
|
|
|
199 and mark or remove them as necessary). */
|
|
412
|
200 if (ht->type == HASH_TABLE_NON_WEAK)
|
|
380
|
201 {
|
|
|
202 hentry *e, *sentinel;
|
|
231
|
203
|
|
380
|
204 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
|
205 if (!HENTRY_CLEAR_P (e))
|
|
|
206 {
|
|
412
|
207 markobj (e->key);
|
|
|
208 markobj (e->value);
|
|
380
|
209 }
|
|
|
210 }
|
|
|
211 return Qnil;
|
|
|
212 }
|
|
|
213
|
|
|
214 /* Equality of hash tables. Two hash tables are equal when they are of
|
|
412
|
215 the same type and test function, they have the same number of
|
|
380
|
216 elements, and for each key in the hash table, the values are `equal'.
|
|
|
217
|
|
|
218 This is similar to Common Lisp `equalp' of hash tables, with the
|
|
|
219 difference that CL requires the keys to be compared with the test
|
|
|
220 function, which we don't do. Doing that would require consing, and
|
|
|
221 consing is a bad idea in `equal'. Anyway, our method should provide
|
|
|
222 the same result -- if the keys are not equal according to the test
|
|
|
223 function, then Fgethash() in hash_table_equal_mapper() will fail. */
|
|
|
224 static int
|
|
|
225 hash_table_equal (Lisp_Object hash_table1, Lisp_Object hash_table2, int depth)
|
|
|
226 {
|
|
|
227 Lisp_Hash_Table *ht1 = XHASH_TABLE (hash_table1);
|
|
|
228 Lisp_Hash_Table *ht2 = XHASH_TABLE (hash_table2);
|
|
|
229 hentry *e, *sentinel;
|
|
|
230
|
|
|
231 if ((ht1->test_function != ht2->test_function) ||
|
|
412
|
232 (ht1->type != ht2->type) ||
|
|
380
|
233 (ht1->count != ht2->count))
|
|
231
|
234 return 0;
|
|
|
235
|
|
380
|
236 depth++;
|
|
|
237
|
|
|
238 for (e = ht1->hentries, sentinel = e + ht1->size; e < sentinel; e++)
|
|
|
239 if (!HENTRY_CLEAR_P (e))
|
|
|
240 /* Look up the key in the other hash table, and compare the values. */
|
|
|
241 {
|
|
|
242 Lisp_Object value_in_other = Fgethash (e->key, hash_table2, Qunbound);
|
|
|
243 if (UNBOUNDP (value_in_other) ||
|
|
|
244 !internal_equal (e->value, value_in_other, depth))
|
|
|
245 return 0; /* Give up */
|
|
|
246 }
|
|
|
247
|
|
|
248 return 1;
|
|
241
|
249 }
|
|
|
250
|
|
380
|
251 /* Printing hash tables.
|
|
223
|
252
|
|
|
253 This is non-trivial, because we use a readable structure-style
|
|
380
|
254 syntax for hash tables. This means that a typical hash table will be
|
|
223
|
255 readably printed in the form of:
|
|
|
256
|
|
380
|
257 #s(hash-table size 2 data (key1 value1 key2 value2))
|
|
223
|
258
|
|
412
|
259 The supported keywords are `type' (non-weak (or nil), weak,
|
|
|
260 key-weak and value-weak), `test' (eql (or nil), eq or equal),
|
|
|
261 `size' (a natnum or nil) and `data' (a list).
|
|
223
|
262
|
|
412
|
263 If `print-readably' is non-nil, then a simpler syntax is used; for
|
|
|
264 instance:
|
|
223
|
265
|
|
380
|
266 #<hash-table size 2/13 data (key1 value1 key2 value2) 0x874d>
|
|
223
|
267
|
|
|
268 The data is truncated to four pairs, and the rest is shown with
|
|
241
|
269 `...'. This printer does not cons. */
|
|
223
|
270
|
|
|
271
|
|
380
|
272 /* Print the data of the hash table. This maps through a Lisp
|
|
|
273 hash table and prints key/value pairs using PRINTCHARFUN. */
|
|
|
274 static void
|
|
|
275 print_hash_table_data (Lisp_Hash_Table *ht, Lisp_Object printcharfun)
|
|
223
|
276 {
|
|
380
|
277 int count = 0;
|
|
|
278 hentry *e, *sentinel;
|
|
223
|
279
|
|
380
|
280 write_c_string (" data (", printcharfun);
|
|
223
|
281
|
|
380
|
282 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
|
283 if (!HENTRY_CLEAR_P (e))
|
|
|
284 {
|
|
|
285 if (count > 0)
|
|
|
286 write_c_string (" ", printcharfun);
|
|
|
287 if (!print_readably && count > 3)
|
|
|
288 {
|
|
|
289 write_c_string ("...", printcharfun);
|
|
|
290 break;
|
|
|
291 }
|
|
|
292 print_internal (e->key, printcharfun, 1);
|
|
|
293 write_c_string (" ", printcharfun);
|
|
|
294 print_internal (e->value, printcharfun, 1);
|
|
|
295 count++;
|
|
|
296 }
|
|
223
|
297
|
|
380
|
298 write_c_string (")", printcharfun);
|
|
223
|
299 }
|
|
|
300
|
|
|
301 static void
|
|
380
|
302 print_hash_table (Lisp_Object obj, Lisp_Object printcharfun, int escapeflag)
|
|
223
|
303 {
|
|
380
|
304 Lisp_Hash_Table *ht = XHASH_TABLE (obj);
|
|
223
|
305 char buf[128];
|
|
|
306
|
|
380
|
307 write_c_string (print_readably ? "#s(hash-table" : "#<hash-table",
|
|
223
|
308 printcharfun);
|
|
380
|
309
|
|
412
|
310 if (ht->type != HASH_TABLE_NON_WEAK)
|
|
|
311 {
|
|
|
312 sprintf (buf, " type %s",
|
|
|
313 (ht->type == HASH_TABLE_WEAK ? "weak" :
|
|
|
314 ht->type == HASH_TABLE_KEY_WEAK ? "key-weak" :
|
|
|
315 ht->type == HASH_TABLE_VALUE_WEAK ? "value-weak" :
|
|
|
316 "you-d-better-not-see-this"));
|
|
|
317 write_c_string (buf, printcharfun);
|
|
|
318 }
|
|
|
319
|
|
380
|
320 /* These checks have a kludgy look to them, but they are safe.
|
|
|
321 Due to nature of hashing, you cannot use arbitrary
|
|
|
322 test functions anyway. */
|
|
|
323 if (!ht->test_function)
|
|
223
|
324 write_c_string (" test eq", printcharfun);
|
|
380
|
325 else if (ht->test_function == lisp_object_equal_equal)
|
|
223
|
326 write_c_string (" test equal", printcharfun);
|
|
380
|
327 else if (ht->test_function == lisp_object_eql_equal)
|
|
231
|
328 DO_NOTHING;
|
|
223
|
329 else
|
|
|
330 abort ();
|
|
380
|
331
|
|
|
332 if (ht->count || !print_readably)
|
|
223
|
333 {
|
|
|
334 if (print_readably)
|
|
380
|
335 sprintf (buf, " size %lu", (unsigned long) ht->count);
|
|
223
|
336 else
|
|
380
|
337 sprintf (buf, " size %lu/%lu",
|
|
|
338 (unsigned long) ht->count,
|
|
|
339 (unsigned long) ht->size);
|
|
223
|
340 write_c_string (buf, printcharfun);
|
|
|
341 }
|
|
380
|
342
|
|
|
343 if (ht->count)
|
|
|
344 print_hash_table_data (ht, printcharfun);
|
|
|
345
|
|
0
|
346 if (print_readably)
|
|
223
|
347 write_c_string (")", printcharfun);
|
|
|
348 else
|
|
|
349 {
|
|
380
|
350 sprintf (buf, " 0x%x>", ht->header.uid);
|
|
223
|
351 write_c_string (buf, printcharfun);
|
|
|
352 }
|
|
|
353 }
|
|
|
354
|
|
380
|
355 static void
|
|
|
356 finalize_hash_table (void *header, int for_disksave)
|
|
|
357 {
|
|
|
358 if (!for_disksave)
|
|
|
359 {
|
|
|
360 Lisp_Hash_Table *ht = (Lisp_Hash_Table *) header;
|
|
|
361
|
|
|
362 xfree (ht->hentries);
|
|
|
363 ht->hentries = 0;
|
|
|
364 }
|
|
|
365 }
|
|
|
366
|
|
420
|
367 static const struct lrecord_description hentry_description_1[] = {
|
|
|
368 { XD_LISP_OBJECT, offsetof(hentry, key), 2 },
|
|
|
369 { XD_END }
|
|
|
370 };
|
|
|
371
|
|
|
372 static const struct struct_description hentry_description = {
|
|
|
373 sizeof(hentry),
|
|
|
374 hentry_description_1
|
|
|
375 };
|
|
|
376
|
|
|
377 static const struct lrecord_description hash_table_description[] = {
|
|
|
378 { XD_SIZE_T, offsetof(Lisp_Hash_Table, size) },
|
|
|
379 { XD_STRUCT_PTR, offsetof(Lisp_Hash_Table, hentries), XD_INDIRECT(0), &hentry_description },
|
|
|
380 { XD_END }
|
|
|
381 };
|
|
|
382
|
|
380
|
383 DEFINE_LRECORD_IMPLEMENTATION ("hash-table", hash_table,
|
|
|
384 mark_hash_table, print_hash_table,
|
|
|
385 finalize_hash_table,
|
|
412
|
386 /* #### Implement hash_table_hash()! */
|
|
|
387 hash_table_equal, 0,
|
|
420
|
388 hash_table_description,
|
|
380
|
389 Lisp_Hash_Table);
|
|
|
390
|
|
|
391 static Lisp_Hash_Table *
|
|
|
392 xhash_table (Lisp_Object hash_table)
|
|
|
393 {
|
|
|
394 if (!gc_in_progress)
|
|
|
395 CHECK_HASH_TABLE (hash_table);
|
|
|
396 check_hash_table_invariants (XHASH_TABLE (hash_table));
|
|
|
397 return XHASH_TABLE (hash_table);
|
|
|
398 }
|
|
|
399
|
|
223
|
400
|
|
380
|
401 /************************************************************************/
|
|
|
402 /* Creation of Hash Tables */
|
|
|
403 /************************************************************************/
|
|
|
404
|
|
|
405 /* Creation of hash tables, without error-checking. */
|
|
412
|
406 static double
|
|
|
407 hash_table_rehash_threshold (Lisp_Hash_Table *ht)
|
|
|
408 {
|
|
|
409 return
|
|
|
410 ht->rehash_threshold > 0.0 ? ht->rehash_threshold :
|
|
|
411 ht->size > 4096 && !ht->test_function ? 0.7 : 0.6;
|
|
|
412 }
|
|
|
413
|
|
380
|
414 static void
|
|
|
415 compute_hash_table_derived_values (Lisp_Hash_Table *ht)
|
|
|
416 {
|
|
|
417 ht->rehash_count = (size_t)
|
|
412
|
418 ((double) ht->size * hash_table_rehash_threshold (ht));
|
|
394
|
419 ht->golden_ratio = (size_t)
|
|
380
|
420 ((double) ht->size * (.6180339887 / (double) sizeof (Lisp_Object)));
|
|
|
421 }
|
|
|
422
|
|
|
423 Lisp_Object
|
|
412
|
424 make_general_lisp_hash_table (size_t size,
|
|
|
425 enum hash_table_type type,
|
|
|
426 enum hash_table_test test,
|
|
|
427 double rehash_size,
|
|
|
428 double rehash_threshold)
|
|
380
|
429 {
|
|
|
430 Lisp_Object hash_table;
|
|
398
|
431 Lisp_Hash_Table *ht = alloc_lcrecord_type (Lisp_Hash_Table, &lrecord_hash_table);
|
|
380
|
432
|
|
412
|
433 ht->type = type;
|
|
|
434 ht->rehash_size = rehash_size;
|
|
|
435 ht->rehash_threshold = rehash_threshold;
|
|
|
436
|
|
380
|
437 switch (test)
|
|
|
438 {
|
|
|
439 case HASH_TABLE_EQ:
|
|
|
440 ht->test_function = 0;
|
|
|
441 ht->hash_function = 0;
|
|
|
442 break;
|
|
|
443
|
|
|
444 case HASH_TABLE_EQL:
|
|
|
445 ht->test_function = lisp_object_eql_equal;
|
|
|
446 ht->hash_function = lisp_object_eql_hash;
|
|
|
447 break;
|
|
|
448
|
|
|
449 case HASH_TABLE_EQUAL:
|
|
|
450 ht->test_function = lisp_object_equal_equal;
|
|
|
451 ht->hash_function = lisp_object_equal_hash;
|
|
|
452 break;
|
|
|
453
|
|
|
454 default:
|
|
|
455 abort ();
|
|
|
456 }
|
|
|
457
|
|
412
|
458 if (ht->rehash_size <= 0.0)
|
|
|
459 ht->rehash_size = HASH_TABLE_DEFAULT_REHASH_SIZE;
|
|
380
|
460 if (size < HASH_TABLE_MIN_SIZE)
|
|
|
461 size = HASH_TABLE_MIN_SIZE;
|
|
412
|
462 if (rehash_threshold < 0.0)
|
|
|
463 rehash_threshold = 0.75;
|
|
|
464 ht->size =
|
|
|
465 hash_table_size ((size_t) ((double) size / hash_table_rehash_threshold (ht)) + 1);
|
|
380
|
466 ht->count = 0;
|
|
|
467 compute_hash_table_derived_values (ht);
|
|
|
468
|
|
|
469 /* We leave room for one never-occupied sentinel hentry at the end. */
|
|
|
470 ht->hentries = xnew_array (hentry, ht->size + 1);
|
|
|
471
|
|
|
472 {
|
|
|
473 hentry *e, *sentinel;
|
|
|
474 for (e = ht->hentries, sentinel = e + ht->size; e <= sentinel; e++)
|
|
|
475 CLEAR_HENTRY (e);
|
|
|
476 }
|
|
|
477
|
|
|
478 XSETHASH_TABLE (hash_table, ht);
|
|
|
479
|
|
412
|
480 if (type == HASH_TABLE_NON_WEAK)
|
|
380
|
481 ht->next_weak = Qunbound;
|
|
|
482 else
|
|
|
483 ht->next_weak = Vall_weak_hash_tables, Vall_weak_hash_tables = hash_table;
|
|
|
484
|
|
|
485 return hash_table;
|
|
|
486 }
|
|
|
487
|
|
|
488 Lisp_Object
|
|
|
489 make_lisp_hash_table (size_t size,
|
|
412
|
490 enum hash_table_type type,
|
|
380
|
491 enum hash_table_test test)
|
|
|
492 {
|
|
412
|
493 return make_general_lisp_hash_table (size, type, test,
|
|
|
494 HASH_TABLE_DEFAULT_REHASH_SIZE, -1.0);
|
|
380
|
495 }
|
|
|
496
|
|
|
497 /* Pretty reading of hash tables.
|
|
223
|
498
|
|
|
499 Here we use the existing structures mechanism (which is,
|
|
|
500 unfortunately, pretty cumbersome) for validating and instantiating
|
|
380
|
501 the hash tables. The idea is that the side-effect of reading a
|
|
|
502 #s(hash-table PLIST) object is creation of a hash table with desired
|
|
|
503 properties, and that the hash table is returned. */
|
|
223
|
504
|
|
|
505 /* Validation functions: each keyword provides its own validation
|
|
|
506 function. The errors should maybe be continuable, but it is
|
|
|
507 unclear how this would cope with ERRB. */
|
|
|
508 static int
|
|
380
|
509 hash_table_size_validate (Lisp_Object keyword, Lisp_Object value,
|
|
|
510 Error_behavior errb)
|
|
|
511 {
|
|
|
512 if (NATNUMP (value))
|
|
|
513 return 1;
|
|
|
514
|
|
|
515 maybe_signal_error (Qwrong_type_argument, list2 (Qnatnump, value),
|
|
|
516 Qhash_table, errb);
|
|
|
517 return 0;
|
|
|
518 }
|
|
|
519
|
|
|
520 static size_t
|
|
|
521 decode_hash_table_size (Lisp_Object obj)
|
|
|
522 {
|
|
|
523 return NILP (obj) ? HASH_TABLE_DEFAULT_SIZE : XINT (obj);
|
|
|
524 }
|
|
|
525
|
|
|
526 static int
|
|
412
|
527 hash_table_type_validate (Lisp_Object keyword, Lisp_Object value,
|
|
|
528 Error_behavior errb)
|
|
223
|
529 {
|
|
380
|
530 if (EQ (value, Qnil)) return 1;
|
|
|
531 if (EQ (value, Qnon_weak)) return 1;
|
|
|
532 if (EQ (value, Qweak)) return 1;
|
|
|
533 if (EQ (value, Qkey_weak)) return 1;
|
|
|
534 if (EQ (value, Qvalue_weak)) return 1;
|
|
|
535
|
|
412
|
536 maybe_signal_simple_error ("Invalid hash table type",
|
|
380
|
537 value, Qhash_table, errb);
|
|
|
538 return 0;
|
|
|
539 }
|
|
|
540
|
|
412
|
541 static enum hash_table_type
|
|
|
542 decode_hash_table_type (Lisp_Object obj)
|
|
380
|
543 {
|
|
|
544 if (EQ (obj, Qnil)) return HASH_TABLE_NON_WEAK;
|
|
|
545 if (EQ (obj, Qnon_weak)) return HASH_TABLE_NON_WEAK;
|
|
|
546 if (EQ (obj, Qweak)) return HASH_TABLE_WEAK;
|
|
|
547 if (EQ (obj, Qkey_weak)) return HASH_TABLE_KEY_WEAK;
|
|
|
548 if (EQ (obj, Qvalue_weak)) return HASH_TABLE_VALUE_WEAK;
|
|
|
549
|
|
412
|
550 signal_simple_error ("Invalid hash table type", obj);
|
|
380
|
551 return HASH_TABLE_NON_WEAK; /* not reached */
|
|
|
552 }
|
|
|
553
|
|
|
554 static int
|
|
|
555 hash_table_test_validate (Lisp_Object keyword, Lisp_Object value,
|
|
|
556 Error_behavior errb)
|
|
|
557 {
|
|
|
558 if (EQ (value, Qnil)) return 1;
|
|
|
559 if (EQ (value, Qeq)) return 1;
|
|
|
560 if (EQ (value, Qequal)) return 1;
|
|
|
561 if (EQ (value, Qeql)) return 1;
|
|
|
562
|
|
|
563 maybe_signal_simple_error ("Invalid hash table test",
|
|
|
564 value, Qhash_table, errb);
|
|
|
565 return 0;
|
|
|
566 }
|
|
|
567
|
|
|
568 static enum hash_table_test
|
|
|
569 decode_hash_table_test (Lisp_Object obj)
|
|
|
570 {
|
|
|
571 if (EQ (obj, Qnil)) return HASH_TABLE_EQL;
|
|
|
572 if (EQ (obj, Qeq)) return HASH_TABLE_EQ;
|
|
|
573 if (EQ (obj, Qequal)) return HASH_TABLE_EQUAL;
|
|
|
574 if (EQ (obj, Qeql)) return HASH_TABLE_EQL;
|
|
|
575
|
|
|
576 signal_simple_error ("Invalid hash table test", obj);
|
|
|
577 return HASH_TABLE_EQ; /* not reached */
|
|
|
578 }
|
|
|
579
|
|
|
580 static int
|
|
|
581 hash_table_rehash_size_validate (Lisp_Object keyword, Lisp_Object value,
|
|
412
|
582 Error_behavior errb)
|
|
380
|
583 {
|
|
|
584 if (!FLOATP (value))
|
|
223
|
585 {
|
|
380
|
586 maybe_signal_error (Qwrong_type_argument, list2 (Qfloatp, value),
|
|
|
587 Qhash_table, errb);
|
|
223
|
588 return 0;
|
|
|
589 }
|
|
380
|
590
|
|
|
591 {
|
|
|
592 double rehash_size = XFLOAT_DATA (value);
|
|
|
593 if (rehash_size <= 1.0)
|
|
|
594 {
|
|
|
595 maybe_signal_simple_error
|
|
|
596 ("Hash table rehash size must be greater than 1.0",
|
|
|
597 value, Qhash_table, errb);
|
|
|
598 return 0;
|
|
|
599 }
|
|
|
600 }
|
|
|
601
|
|
223
|
602 return 1;
|
|
|
603 }
|
|
|
604
|
|
380
|
605 static double
|
|
|
606 decode_hash_table_rehash_size (Lisp_Object rehash_size)
|
|
|
607 {
|
|
|
608 return NILP (rehash_size) ? -1.0 : XFLOAT_DATA (rehash_size);
|
|
|
609 }
|
|
|
610
|
|
223
|
611 static int
|
|
380
|
612 hash_table_rehash_threshold_validate (Lisp_Object keyword, Lisp_Object value,
|
|
|
613 Error_behavior errb)
|
|
|
614 {
|
|
|
615 if (!FLOATP (value))
|
|
|
616 {
|
|
|
617 maybe_signal_error (Qwrong_type_argument, list2 (Qfloatp, value),
|
|
|
618 Qhash_table, errb);
|
|
|
619 return 0;
|
|
|
620 }
|
|
|
621
|
|
|
622 {
|
|
|
623 double rehash_threshold = XFLOAT_DATA (value);
|
|
|
624 if (rehash_threshold <= 0.0 || rehash_threshold >= 1.0)
|
|
|
625 {
|
|
|
626 maybe_signal_simple_error
|
|
|
627 ("Hash table rehash threshold must be between 0.0 and 1.0",
|
|
|
628 value, Qhash_table, errb);
|
|
|
629 return 0;
|
|
|
630 }
|
|
|
631 }
|
|
|
632
|
|
|
633 return 1;
|
|
|
634 }
|
|
|
635
|
|
|
636 static double
|
|
|
637 decode_hash_table_rehash_threshold (Lisp_Object rehash_threshold)
|
|
|
638 {
|
|
|
639 return NILP (rehash_threshold) ? -1.0 : XFLOAT_DATA (rehash_threshold);
|
|
|
640 }
|
|
|
641
|
|
|
642 static int
|
|
|
643 hash_table_data_validate (Lisp_Object keyword, Lisp_Object value,
|
|
223
|
644 Error_behavior errb)
|
|
|
645 {
|
|
380
|
646 int len;
|
|
|
647
|
|
|
648 GET_EXTERNAL_LIST_LENGTH (value, len);
|
|
|
649
|
|
|
650 if (len & 1)
|
|
223
|
651 {
|
|
380
|
652 maybe_signal_simple_error
|
|
|
653 ("Hash table data must have alternating key/value pairs",
|
|
|
654 value, Qhash_table, errb);
|
|
223
|
655 return 0;
|
|
|
656 }
|
|
|
657 return 1;
|
|
|
658 }
|
|
|
659
|
|
380
|
660 /* The actual instantiation of a hash table. This does practically no
|
|
223
|
661 error checking, because it relies on the fact that the paranoid
|
|
|
662 functions above have error-checked everything to the last details.
|
|
|
663 If this assumption is wrong, we will get a crash immediately (with
|
|
|
664 error-checking compiled in), and we'll know if there is a bug in
|
|
|
665 the structure mechanism. So there. */
|
|
|
666 static Lisp_Object
|
|
380
|
667 hash_table_instantiate (Lisp_Object plist)
|
|
223
|
668 {
|
|
380
|
669 Lisp_Object hash_table;
|
|
|
670 Lisp_Object test = Qnil;
|
|
412
|
671 Lisp_Object type = Qnil;
|
|
380
|
672 Lisp_Object size = Qnil;
|
|
412
|
673 Lisp_Object data = Qnil;
|
|
380
|
674 Lisp_Object rehash_size = Qnil;
|
|
|
675 Lisp_Object rehash_threshold = Qnil;
|
|
223
|
676
|
|
|
677 while (!NILP (plist))
|
|
|
678 {
|
|
272
|
679 Lisp_Object key, value;
|
|
|
680 key = XCAR (plist); plist = XCDR (plist);
|
|
|
681 value = XCAR (plist); plist = XCDR (plist);
|
|
|
682
|
|
380
|
683 if (EQ (key, Qtest)) test = value;
|
|
412
|
684 else if (EQ (key, Qtype)) type = value;
|
|
380
|
685 else if (EQ (key, Qsize)) size = value;
|
|
412
|
686 else if (EQ (key, Qdata)) data = value;
|
|
380
|
687 else if (EQ (key, Qrehash_size)) rehash_size = value;
|
|
|
688 else if (EQ (key, Qrehash_threshold)) rehash_threshold = value;
|
|
223
|
689 else
|
|
|
690 abort ();
|
|
|
691 }
|
|
272
|
692
|
|
380
|
693 /* Create the hash table. */
|
|
|
694 hash_table = make_general_lisp_hash_table
|
|
412
|
695 (decode_hash_table_size (size),
|
|
|
696 decode_hash_table_type (type),
|
|
|
697 decode_hash_table_test (test),
|
|
380
|
698 decode_hash_table_rehash_size (rehash_size),
|
|
412
|
699 decode_hash_table_rehash_threshold (rehash_threshold));
|
|
223
|
700
|
|
380
|
701 /* I'm not sure whether this can GC, but better safe than sorry. */
|
|
|
702 {
|
|
|
703 struct gcpro gcpro1;
|
|
|
704 GCPRO1 (hash_table);
|
|
223
|
705
|
|
380
|
706 /* And fill it with data. */
|
|
|
707 while (!NILP (data))
|
|
|
708 {
|
|
|
709 Lisp_Object key, value;
|
|
|
710 key = XCAR (data); data = XCDR (data);
|
|
|
711 value = XCAR (data); data = XCDR (data);
|
|
|
712 Fputhash (key, value, hash_table);
|
|
|
713 }
|
|
|
714 UNGCPRO;
|
|
|
715 }
|
|
223
|
716
|
|
380
|
717 return hash_table;
|
|
0
|
718 }
|
|
|
719
|
|
|
720 static void
|
|
380
|
721 structure_type_create_hash_table_structure_name (Lisp_Object structure_name)
|
|
0
|
722 {
|
|
380
|
723 struct structure_type *st;
|
|
0
|
724
|
|
380
|
725 st = define_structure_type (structure_name, 0, hash_table_instantiate);
|
|
412
|
726 define_structure_type_keyword (st, Qsize, hash_table_size_validate);
|
|
398
|
727 define_structure_type_keyword (st, Qtest, hash_table_test_validate);
|
|
412
|
728 define_structure_type_keyword (st, Qtype, hash_table_type_validate);
|
|
|
729 define_structure_type_keyword (st, Qdata, hash_table_data_validate);
|
|
380
|
730 define_structure_type_keyword (st, Qrehash_size, hash_table_rehash_size_validate);
|
|
|
731 define_structure_type_keyword (st, Qrehash_threshold, hash_table_rehash_threshold_validate);
|
|
0
|
732 }
|
|
|
733
|
|
380
|
734 /* Create a built-in Lisp structure type named `hash-table'.
|
|
|
735 We make #s(hashtable ...) equivalent to #s(hash-table ...),
|
|
412
|
736 for backward comptabibility.
|
|
380
|
737 This is called from emacs.c. */
|
|
0
|
738 void
|
|
380
|
739 structure_type_create_hash_table (void)
|
|
0
|
740 {
|
|
380
|
741 structure_type_create_hash_table_structure_name (Qhash_table);
|
|
|
742 structure_type_create_hash_table_structure_name (Qhashtable); /* compat */
|
|
0
|
743 }
|
|
|
744
|
|
|
745
|
|
380
|
746 /************************************************************************/
|
|
|
747 /* Definition of Lisp-visible methods */
|
|
|
748 /************************************************************************/
|
|
0
|
749
|
|
380
|
750 DEFUN ("hash-table-p", Fhash_table_p, 1, 1, 0, /*
|
|
|
751 Return t if OBJECT is a hash table, else nil.
|
|
|
752 */
|
|
|
753 (object))
|
|
0
|
754 {
|
|
380
|
755 return HASH_TABLEP (object) ? Qt : Qnil;
|
|
0
|
756 }
|
|
|
757
|
|
380
|
758 DEFUN ("make-hash-table", Fmake_hash_table, 0, MANY, 0, /*
|
|
|
759 Return a new empty hash table object.
|
|
|
760 Use Common Lisp style keywords to specify hash table properties.
|
|
412
|
761 (make-hash-table &key :size :test :type :rehash-size :rehash-threshold)
|
|
|
762
|
|
|
763 Keyword :size specifies the number of keys likely to be inserted.
|
|
|
764 This number of entries can be inserted without enlarging the hash table.
|
|
380
|
765
|
|
|
766 Keyword :test can be `eq', `eql' (default) or `equal'.
|
|
|
767 Comparison between keys is done using this function.
|
|
|
768 If speed is important, consider using `eq'.
|
|
|
769 When storing strings in the hash table, you will likely need to use `equal'.
|
|
|
770
|
|
412
|
771 Keyword :type can be `non-weak' (default), `weak', `key-weak' or `value-weak'.
|
|
380
|
772
|
|
|
773 A weak hash table is one whose pointers do not count as GC referents:
|
|
|
774 for any key-value pair in the hash table, if the only remaining pointer
|
|
|
775 to either the key or the value is in a weak hash table, then the pair
|
|
|
776 will be removed from the hash table, and the key and value collected.
|
|
|
777 A non-weak hash table (or any other pointer) would prevent the object
|
|
|
778 from being collected.
|
|
|
779
|
|
|
780 A key-weak hash table is similar to a fully-weak hash table except that
|
|
|
781 a key-value pair will be removed only if the key remains unmarked
|
|
|
782 outside of weak hash tables. The pair will remain in the hash table if
|
|
|
783 the key is pointed to by something other than a weak hash table, even
|
|
|
784 if the value is not.
|
|
|
785
|
|
|
786 A value-weak hash table is similar to a fully-weak hash table except
|
|
|
787 that a key-value pair will be removed only if the value remains
|
|
|
788 unmarked outside of weak hash tables. The pair will remain in the
|
|
|
789 hash table if the value is pointed to by something other than a weak
|
|
|
790 hash table, even if the key is not.
|
|
410
|
791
|
|
412
|
792 Keyword :rehash-size must be a float greater than 1.0, and specifies
|
|
|
793 the factor by which to increase the size of the hash table when enlarging.
|
|
|
794
|
|
|
795 Keyword :rehash-threshold must be a float between 0.0 and 1.0,
|
|
|
796 and specifies the load factor of the hash table which triggers enlarging.
|
|
|
797
|
|
380
|
798 */
|
|
|
799 (int nargs, Lisp_Object *args))
|
|
0
|
800 {
|
|
412
|
801 int j = 0;
|
|
|
802 Lisp_Object size = Qnil;
|
|
|
803 Lisp_Object type = Qnil;
|
|
398
|
804 Lisp_Object test = Qnil;
|
|
380
|
805 Lisp_Object rehash_size = Qnil;
|
|
|
806 Lisp_Object rehash_threshold = Qnil;
|
|
|
807
|
|
412
|
808 while (j < nargs)
|
|
398
|
809 {
|
|
412
|
810 Lisp_Object keyword, value;
|
|
380
|
811
|
|
412
|
812 keyword = args[j++];
|
|
|
813 if (!KEYWORDP (keyword))
|
|
|
814 signal_simple_error ("Invalid hash table property keyword", keyword);
|
|
|
815 if (j == nargs)
|
|
|
816 signal_simple_error ("Hash table property requires a value", keyword);
|
|
|
817
|
|
|
818 value = args[j++];
|
|
|
819
|
|
|
820 if (EQ (keyword, Q_size)) size = value;
|
|
|
821 else if (EQ (keyword, Q_type)) type = value;
|
|
|
822 else if (EQ (keyword, Q_test)) test = value;
|
|
380
|
823 else if (EQ (keyword, Q_rehash_size)) rehash_size = value;
|
|
|
824 else if (EQ (keyword, Q_rehash_threshold)) rehash_threshold = value;
|
|
|
825 else signal_simple_error ("Invalid hash table property keyword", keyword);
|
|
|
826 }
|
|
|
827
|
|
|
828 #define VALIDATE_VAR(var) \
|
|
|
829 if (!NILP (var)) hash_table_##var##_validate (Q##var, var, ERROR_ME);
|
|
|
830
|
|
412
|
831 VALIDATE_VAR (size);
|
|
|
832 VALIDATE_VAR (type);
|
|
398
|
833 VALIDATE_VAR (test);
|
|
380
|
834 VALIDATE_VAR (rehash_size);
|
|
|
835 VALIDATE_VAR (rehash_threshold);
|
|
|
836
|
|
|
837 return make_general_lisp_hash_table
|
|
412
|
838 (decode_hash_table_size (size),
|
|
|
839 decode_hash_table_type (type),
|
|
|
840 decode_hash_table_test (test),
|
|
380
|
841 decode_hash_table_rehash_size (rehash_size),
|
|
412
|
842 decode_hash_table_rehash_threshold (rehash_threshold));
|
|
0
|
843 }
|
|
|
844
|
|
380
|
845 DEFUN ("copy-hash-table", Fcopy_hash_table, 1, 1, 0, /*
|
|
|
846 Return a new hash table containing the same keys and values as HASH-TABLE.
|
|
|
847 The keys and values will not themselves be copied.
|
|
|
848 */
|
|
|
849 (hash_table))
|
|
0
|
850 {
|
|
412
|
851 CONST Lisp_Hash_Table *ht_old = xhash_table (hash_table);
|
|
398
|
852 Lisp_Hash_Table *ht = alloc_lcrecord_type (Lisp_Hash_Table, &lrecord_hash_table);
|
|
380
|
853
|
|
|
854 copy_lcrecord (ht, ht_old);
|
|
|
855
|
|
|
856 ht->hentries = xnew_array (hentry, ht_old->size + 1);
|
|
|
857 memcpy (ht->hentries, ht_old->hentries, (ht_old->size + 1) * sizeof (hentry));
|
|
|
858
|
|
|
859 XSETHASH_TABLE (hash_table, ht);
|
|
|
860
|
|
|
861 if (! EQ (ht->next_weak, Qunbound))
|
|
|
862 {
|
|
|
863 ht->next_weak = Vall_weak_hash_tables;
|
|
|
864 Vall_weak_hash_tables = hash_table;
|
|
|
865 }
|
|
|
866
|
|
|
867 return hash_table;
|
|
0
|
868 }
|
|
|
869
|
|
380
|
870 static void
|
|
412
|
871 enlarge_hash_table (Lisp_Hash_Table *ht)
|
|
0
|
872 {
|
|
412
|
873 hentry *old_entries, *new_entries, *old_sentinel, *new_sentinel, *e;
|
|
|
874 size_t old_size, new_size;
|
|
380
|
875
|
|
|
876 old_size = ht->size;
|
|
412
|
877 new_size = ht->size =
|
|
|
878 hash_table_size ((size_t) ((double) old_size * ht->rehash_size));
|
|
380
|
879
|
|
|
880 old_entries = ht->hentries;
|
|
|
881
|
|
412
|
882 ht->hentries = xnew_array (hentry, new_size + 1);
|
|
380
|
883 new_entries = ht->hentries;
|
|
|
884
|
|
412
|
885 old_sentinel = old_entries + old_size;
|
|
|
886 new_sentinel = new_entries + new_size;
|
|
|
887
|
|
|
888 for (e = new_entries; e <= new_sentinel; e++)
|
|
|
889 CLEAR_HENTRY (e);
|
|
|
890
|
|
380
|
891 compute_hash_table_derived_values (ht);
|
|
|
892
|
|
412
|
893 for (e = old_entries; e < old_sentinel; e++)
|
|
380
|
894 if (!HENTRY_CLEAR_P (e))
|
|
|
895 {
|
|
|
896 hentry *probe = new_entries + HASH_CODE (e->key, ht);
|
|
|
897 LINEAR_PROBING_LOOP (probe, new_entries, new_size)
|
|
|
898 ;
|
|
|
899 *probe = *e;
|
|
|
900 }
|
|
0
|
901
|
|
412
|
902 xfree (old_entries);
|
|
380
|
903 }
|
|
|
904
|
|
|
905 static hentry *
|
|
412
|
906 find_hentry (Lisp_Object key, CONST Lisp_Hash_Table *ht)
|
|
380
|
907 {
|
|
|
908 hash_table_test_function_t test_function = ht->test_function;
|
|
|
909 hentry *entries = ht->hentries;
|
|
|
910 hentry *probe = entries + HASH_CODE (key, ht);
|
|
|
911
|
|
|
912 LINEAR_PROBING_LOOP (probe, entries, ht->size)
|
|
|
913 if (KEYS_EQUAL_P (probe->key, key, test_function))
|
|
0
|
914 break;
|
|
|
915
|
|
380
|
916 return probe;
|
|
|
917 }
|
|
0
|
918
|
|
380
|
919 DEFUN ("gethash", Fgethash, 2, 3, 0, /*
|
|
|
920 Find hash value for KEY in HASH-TABLE.
|
|
|
921 If there is no corresponding value, return DEFAULT (which defaults to nil).
|
|
|
922 */
|
|
|
923 (key, hash_table, default_))
|
|
|
924 {
|
|
412
|
925 CONST Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
380
|
926 hentry *e = find_hentry (key, ht);
|
|
0
|
927
|
|
380
|
928 return HENTRY_CLEAR_P (e) ? default_ : e->value;
|
|
0
|
929 }
|
|
|
930
|
|
380
|
931 DEFUN ("puthash", Fputhash, 3, 3, 0, /*
|
|
|
932 Hash KEY to VALUE in HASH-TABLE.
|
|
|
933 */
|
|
|
934 (key, value, hash_table))
|
|
0
|
935 {
|
|
380
|
936 Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
|
937 hentry *e = find_hentry (key, ht);
|
|
0
|
938
|
|
380
|
939 if (!HENTRY_CLEAR_P (e))
|
|
|
940 return e->value = value;
|
|
0
|
941
|
|
380
|
942 e->key = key;
|
|
|
943 e->value = value;
|
|
|
944
|
|
|
945 if (++ht->count >= ht->rehash_count)
|
|
|
946 enlarge_hash_table (ht);
|
|
|
947
|
|
|
948 return value;
|
|
0
|
949 }
|
|
|
950
|
|
380
|
951 /* Remove hentry pointed at by PROBE.
|
|
|
952 Subsequent entries are removed and reinserted.
|
|
|
953 We don't use tombstones - too wasteful. */
|
|
|
954 static void
|
|
|
955 remhash_1 (Lisp_Hash_Table *ht, hentry *entries, hentry *probe)
|
|
0
|
956 {
|
|
380
|
957 size_t size = ht->size;
|
|
412
|
958 CLEAR_HENTRY (probe++);
|
|
380
|
959 ht->count--;
|
|
0
|
960
|
|
380
|
961 LINEAR_PROBING_LOOP (probe, entries, size)
|
|
0
|
962 {
|
|
380
|
963 Lisp_Object key = probe->key;
|
|
|
964 hentry *probe2 = entries + HASH_CODE (key, ht);
|
|
|
965 LINEAR_PROBING_LOOP (probe2, entries, size)
|
|
|
966 if (EQ (probe2->key, key))
|
|
|
967 /* hentry at probe doesn't need to move. */
|
|
|
968 goto continue_outer_loop;
|
|
|
969 /* Move hentry from probe to new home at probe2. */
|
|
|
970 *probe2 = *probe;
|
|
|
971 CLEAR_HENTRY (probe);
|
|
|
972 continue_outer_loop: continue;
|
|
0
|
973 }
|
|
|
974 }
|
|
|
975
|
|
380
|
976 DEFUN ("remhash", Fremhash, 2, 2, 0, /*
|
|
|
977 Remove the entry for KEY from HASH-TABLE.
|
|
|
978 Do nothing if there is no entry for KEY in HASH-TABLE.
|
|
20
|
979 */
|
|
380
|
980 (key, hash_table))
|
|
0
|
981 {
|
|
380
|
982 Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
|
983 hentry *e = find_hentry (key, ht);
|
|
0
|
984
|
|
380
|
985 if (HENTRY_CLEAR_P (e))
|
|
|
986 return Qnil;
|
|
0
|
987
|
|
380
|
988 remhash_1 (ht, ht->hentries, e);
|
|
|
989 return Qt;
|
|
0
|
990 }
|
|
|
991
|
|
20
|
992 DEFUN ("clrhash", Fclrhash, 1, 1, 0, /*
|
|
380
|
993 Remove all entries from HASH-TABLE, leaving it empty.
|
|
20
|
994 */
|
|
380
|
995 (hash_table))
|
|
0
|
996 {
|
|
380
|
997 Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
|
998 hentry *e, *sentinel;
|
|
|
999
|
|
|
1000 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
|
1001 CLEAR_HENTRY (e);
|
|
|
1002 ht->count = 0;
|
|
|
1003
|
|
|
1004 return hash_table;
|
|
0
|
1005 }
|
|
|
1006
|
|
380
|
1007 /************************************************************************/
|
|
|
1008 /* Accessor Functions */
|
|
|
1009 /************************************************************************/
|
|
|
1010
|
|
|
1011 DEFUN ("hash-table-count", Fhash_table_count, 1, 1, 0, /*
|
|
|
1012 Return the number of entries in HASH-TABLE.
|
|
20
|
1013 */
|
|
380
|
1014 (hash_table))
|
|
0
|
1015 {
|
|
380
|
1016 return make_int (xhash_table (hash_table)->count);
|
|
0
|
1017 }
|
|
|
1018
|
|
412
|
1019 DEFUN ("hash-table-size", Fhash_table_size, 1, 1, 0, /*
|
|
|
1020 Return the size of HASH-TABLE.
|
|
|
1021 This is the current number of slots in HASH-TABLE, whether occupied or not.
|
|
|
1022 */
|
|
|
1023 (hash_table))
|
|
|
1024 {
|
|
|
1025 return make_int (xhash_table (hash_table)->size);
|
|
|
1026 }
|
|
|
1027
|
|
|
1028 DEFUN ("hash-table-type", Fhash_table_type, 1, 1, 0, /*
|
|
|
1029 Return the type of HASH-TABLE.
|
|
|
1030 This can be one of `non-weak', `weak', `key-weak' or `value-weak'.
|
|
|
1031 */
|
|
|
1032 (hash_table))
|
|
|
1033 {
|
|
|
1034 switch (xhash_table (hash_table)->type)
|
|
|
1035 {
|
|
|
1036 case HASH_TABLE_WEAK: return Qweak;
|
|
|
1037 case HASH_TABLE_KEY_WEAK: return Qkey_weak;
|
|
|
1038 case HASH_TABLE_VALUE_WEAK: return Qvalue_weak;
|
|
|
1039 default: return Qnon_weak;
|
|
|
1040 }
|
|
|
1041 }
|
|
|
1042
|
|
380
|
1043 DEFUN ("hash-table-test", Fhash_table_test, 1, 1, 0, /*
|
|
|
1044 Return the test function of HASH-TABLE.
|
|
243
|
1045 This can be one of `eq', `eql' or `equal'.
|
|
|
1046 */
|
|
380
|
1047 (hash_table))
|
|
243
|
1048 {
|
|
380
|
1049 hash_table_test_function_t fun = xhash_table (hash_table)->test_function;
|
|
243
|
1050
|
|
380
|
1051 return (fun == lisp_object_eql_equal ? Qeql :
|
|
|
1052 fun == lisp_object_equal_equal ? Qequal :
|
|
|
1053 Qeq);
|
|
|
1054 }
|
|
243
|
1055
|
|
380
|
1056 DEFUN ("hash-table-rehash-size", Fhash_table_rehash_size, 1, 1, 0, /*
|
|
|
1057 Return the current rehash size of HASH-TABLE.
|
|
|
1058 This is a float greater than 1.0; the factor by which HASH-TABLE
|
|
|
1059 is enlarged when the rehash threshold is exceeded.
|
|
|
1060 */
|
|
|
1061 (hash_table))
|
|
|
1062 {
|
|
|
1063 return make_float (xhash_table (hash_table)->rehash_size);
|
|
243
|
1064 }
|
|
0
|
1065
|
|
380
|
1066 DEFUN ("hash-table-rehash-threshold", Fhash_table_rehash_threshold, 1, 1, 0, /*
|
|
|
1067 Return the current rehash threshold of HASH-TABLE.
|
|
|
1068 This is a float between 0.0 and 1.0; the maximum `load factor' of HASH-TABLE,
|
|
|
1069 beyond which the HASH-TABLE is enlarged by rehashing.
|
|
|
1070 */
|
|
|
1071 (hash_table))
|
|
0
|
1072 {
|
|
412
|
1073 return make_float (hash_table_rehash_threshold (xhash_table (hash_table)));
|
|
0
|
1074 }
|
|
|
1075
|
|
380
|
1076 /************************************************************************/
|
|
|
1077 /* Mapping Functions */
|
|
|
1078 /************************************************************************/
|
|
|
1079 DEFUN ("maphash", Fmaphash, 2, 2, 0, /*
|
|
|
1080 Map FUNCTION over entries in HASH-TABLE, calling it with two args,
|
|
|
1081 each key and value in HASH-TABLE.
|
|
|
1082
|
|
|
1083 FUNCTION may not modify HASH-TABLE, with the one exception that FUNCTION
|
|
|
1084 may remhash or puthash the entry currently being processed by FUNCTION.
|
|
|
1085 */
|
|
|
1086 (function, hash_table))
|
|
0
|
1087 {
|
|
412
|
1088 CONST Lisp_Hash_Table *ht = xhash_table (hash_table);
|
|
|
1089 CONST hentry *e, *sentinel;
|
|
0
|
1090
|
|
380
|
1091 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
|
1092 if (!HENTRY_CLEAR_P (e))
|
|
|
1093 {
|
|
|
1094 Lisp_Object args[3], key;
|
|
|
1095 again:
|
|
|
1096 key = e->key;
|
|
|
1097 args[0] = function;
|
|
|
1098 args[1] = key;
|
|
|
1099 args[2] = e->value;
|
|
|
1100 Ffuncall (countof (args), args);
|
|
|
1101 /* Has FUNCTION done a remhash? */
|
|
|
1102 if (!EQ (key, e->key) && !HENTRY_CLEAR_P (e))
|
|
|
1103 goto again;
|
|
|
1104 }
|
|
0
|
1105
|
|
|
1106 return Qnil;
|
|
|
1107 }
|
|
|
1108
|
|
380
|
1109 /* Map *C* function FUNCTION over the elements of a lisp hash table. */
|
|
0
|
1110 void
|
|
380
|
1111 elisp_maphash (maphash_function_t function,
|
|
|
1112 Lisp_Object hash_table, void *extra_arg)
|
|
0
|
1113 {
|
|
412
|
1114 CONST Lisp_Hash_Table *ht = XHASH_TABLE (hash_table);
|
|
|
1115 CONST hentry *e, *sentinel;
|
|
0
|
1116
|
|
380
|
1117 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
|
1118 if (!HENTRY_CLEAR_P (e))
|
|
|
1119 {
|
|
|
1120 Lisp_Object key;
|
|
|
1121 again:
|
|
|
1122 key = e->key;
|
|
|
1123 if (function (key, e->value, extra_arg))
|
|
|
1124 return;
|
|
|
1125 /* Has FUNCTION done a remhash? */
|
|
|
1126 if (!EQ (key, e->key) && !HENTRY_CLEAR_P (e))
|
|
|
1127 goto again;
|
|
|
1128 }
|
|
0
|
1129 }
|
|
|
1130
|
|
380
|
1131 /* Remove all elements of a lisp hash table satisfying *C* predicate PREDICATE. */
|
|
0
|
1132 void
|
|
380
|
1133 elisp_map_remhash (maphash_function_t predicate,
|
|
|
1134 Lisp_Object hash_table, void *extra_arg)
|
|
0
|
1135 {
|
|
380
|
1136 Lisp_Hash_Table *ht = XHASH_TABLE (hash_table);
|
|
|
1137 hentry *e, *entries, *sentinel;
|
|
0
|
1138
|
|
380
|
1139 for (e = entries = ht->hentries, sentinel = e + ht->size; e < sentinel; e++)
|
|
|
1140 if (!HENTRY_CLEAR_P (e))
|
|
|
1141 {
|
|
|
1142 again:
|
|
|
1143 if (predicate (e->key, e->value, extra_arg))
|
|
|
1144 {
|
|
|
1145 remhash_1 (ht, entries, e);
|
|
|
1146 if (!HENTRY_CLEAR_P (e))
|
|
|
1147 goto again;
|
|
|
1148 }
|
|
|
1149 }
|
|
0
|
1150 }
|
|
|
1151
|
|
380
|
1152
|
|
|
1153 /************************************************************************/
|
|
|
1154 /* garbage collecting weak hash tables */
|
|
|
1155 /************************************************************************/
|
|
0
|
1156
|
|
380
|
1157 /* Complete the marking for semi-weak hash tables. */
|
|
0
|
1158 int
|
|
412
|
1159 finish_marking_weak_hash_tables (int (*obj_marked_p) (Lisp_Object),
|
|
|
1160 void (*markobj) (Lisp_Object))
|
|
0
|
1161 {
|
|
380
|
1162 Lisp_Object hash_table;
|
|
0
|
1163 int did_mark = 0;
|
|
|
1164
|
|
380
|
1165 for (hash_table = Vall_weak_hash_tables;
|
|
412
|
1166 !GC_NILP (hash_table);
|
|
380
|
1167 hash_table = XHASH_TABLE (hash_table)->next_weak)
|
|
0
|
1168 {
|
|
412
|
1169 CONST Lisp_Hash_Table *ht = XHASH_TABLE (hash_table);
|
|
|
1170 CONST hentry *e = ht->hentries;
|
|
|
1171 CONST hentry *sentinel = e + ht->size;
|
|
380
|
1172
|
|
412
|
1173 if (! obj_marked_p (hash_table))
|
|
380
|
1174 /* The hash table is probably garbage. Ignore it. */
|
|
|
1175 continue;
|
|
0
|
1176
|
|
380
|
1177 /* Now, scan over all the pairs. For all pairs that are
|
|
|
1178 half-marked, we may need to mark the other half if we're
|
|
|
1179 keeping this pair. */
|
|
412
|
1180 #define MARK_OBJ(obj) \
|
|
|
1181 do { if (!obj_marked_p (obj)) markobj (obj), did_mark = 1; } while (0)
|
|
|
1182
|
|
|
1183 switch (ht->type)
|
|
0
|
1184 {
|
|
380
|
1185 case HASH_TABLE_KEY_WEAK:
|
|
|
1186 for (; e < sentinel; e++)
|
|
|
1187 if (!HENTRY_CLEAR_P (e))
|
|
412
|
1188 if (obj_marked_p (e->key))
|
|
380
|
1189 MARK_OBJ (e->value);
|
|
|
1190 break;
|
|
0
|
1191
|
|
380
|
1192 case HASH_TABLE_VALUE_WEAK:
|
|
|
1193 for (; e < sentinel; e++)
|
|
|
1194 if (!HENTRY_CLEAR_P (e))
|
|
412
|
1195 if (obj_marked_p (e->value))
|
|
380
|
1196 MARK_OBJ (e->key);
|
|
|
1197 break;
|
|
0
|
1198
|
|
380
|
1199 case HASH_TABLE_KEY_CAR_WEAK:
|
|
|
1200 for (; e < sentinel; e++)
|
|
|
1201 if (!HENTRY_CLEAR_P (e))
|
|
412
|
1202 if (!CONSP (e->key) || obj_marked_p (XCAR (e->key)))
|
|
380
|
1203 {
|
|
|
1204 MARK_OBJ (e->key);
|
|
|
1205 MARK_OBJ (e->value);
|
|
|
1206 }
|
|
|
1207 break;
|
|
|
1208
|
|
|
1209 case HASH_TABLE_VALUE_CAR_WEAK:
|
|
|
1210 for (; e < sentinel; e++)
|
|
|
1211 if (!HENTRY_CLEAR_P (e))
|
|
412
|
1212 if (!CONSP (e->value) || obj_marked_p (XCAR (e->value)))
|
|
380
|
1213 {
|
|
|
1214 MARK_OBJ (e->key);
|
|
|
1215 MARK_OBJ (e->value);
|
|
|
1216 }
|
|
|
1217 break;
|
|
|
1218
|
|
|
1219 default:
|
|
|
1220 break;
|
|
|
1221 }
|
|
0
|
1222 }
|
|
|
1223
|
|
|
1224 return did_mark;
|
|
|
1225 }
|
|
|
1226
|
|
380
|
1227 void
|
|
412
|
1228 prune_weak_hash_tables (int (*obj_marked_p) (Lisp_Object))
|
|
0
|
1229 {
|
|
380
|
1230 Lisp_Object hash_table, prev = Qnil;
|
|
|
1231 for (hash_table = Vall_weak_hash_tables;
|
|
412
|
1232 !GC_NILP (hash_table);
|
|
380
|
1233 hash_table = XHASH_TABLE (hash_table)->next_weak)
|
|
0
|
1234 {
|
|
412
|
1235 if (! obj_marked_p (hash_table))
|
|
0
|
1236 {
|
|
380
|
1237 /* This hash table itself is garbage. Remove it from the list. */
|
|
412
|
1238 if (GC_NILP (prev))
|
|
380
|
1239 Vall_weak_hash_tables = XHASH_TABLE (hash_table)->next_weak;
|
|
0
|
1240 else
|
|
380
|
1241 XHASH_TABLE (prev)->next_weak = XHASH_TABLE (hash_table)->next_weak;
|
|
0
|
1242 }
|
|
|
1243 else
|
|
|
1244 {
|
|
|
1245 /* Now, scan over all the pairs. Remove all of the pairs
|
|
|
1246 in which the key or value, or both, is unmarked
|
|
412
|
1247 (depending on the type of weak hash table). */
|
|
380
|
1248 Lisp_Hash_Table *ht = XHASH_TABLE (hash_table);
|
|
|
1249 hentry *entries = ht->hentries;
|
|
|
1250 hentry *sentinel = entries + ht->size;
|
|
|
1251 hentry *e;
|
|
|
1252
|
|
|
1253 for (e = entries; e < sentinel; e++)
|
|
|
1254 if (!HENTRY_CLEAR_P (e))
|
|
|
1255 {
|
|
|
1256 again:
|
|
412
|
1257 if (!obj_marked_p (e->key) || !obj_marked_p (e->value))
|
|
380
|
1258 {
|
|
|
1259 remhash_1 (ht, entries, e);
|
|
|
1260 if (!HENTRY_CLEAR_P (e))
|
|
|
1261 goto again;
|
|
|
1262 }
|
|
|
1263 }
|
|
|
1264
|
|
|
1265 prev = hash_table;
|
|
0
|
1266 }
|
|
|
1267 }
|
|
|
1268 }
|
|
|
1269
|
|
|
1270 /* Return a hash value for an array of Lisp_Objects of size SIZE. */
|
|
|
1271
|
|
380
|
1272 hashcode_t
|
|
0
|
1273 internal_array_hash (Lisp_Object *arr, int size, int depth)
|
|
|
1274 {
|
|
|
1275 int i;
|
|
412
|
1276 unsigned long hash = 0;
|
|
0
|
1277
|
|
|
1278 if (size <= 5)
|
|
|
1279 {
|
|
|
1280 for (i = 0; i < size; i++)
|
|
412
|
1281 hash = HASH2 (hash, internal_hash (arr[i], depth + 1));
|
|
0
|
1282 return hash;
|
|
|
1283 }
|
|
185
|
1284
|
|
0
|
1285 /* just pick five elements scattered throughout the array.
|
|
|
1286 A slightly better approach would be to offset by some
|
|
|
1287 noise factor from the points chosen below. */
|
|
|
1288 for (i = 0; i < 5; i++)
|
|
412
|
1289 hash = HASH2 (hash, internal_hash (arr[i*size/5], depth + 1));
|
|
185
|
1290
|
|
0
|
1291 return hash;
|
|
|
1292 }
|
|
|
1293
|
|
|
1294 /* Return a hash value for a Lisp_Object. This is for use when hashing
|
|
|
1295 objects with the comparison being `equal' (for `eq', you can just
|
|
|
1296 use the Lisp_Object itself as the hash value). You need to make a
|
|
|
1297 tradeoff between the speed of the hash function and how good the
|
|
|
1298 hashing is. In particular, the hash function needs to be FAST,
|
|
|
1299 so you can't just traipse down the whole tree hashing everything
|
|
|
1300 together. Most of the time, objects will differ in the first
|
|
|
1301 few elements you hash. Thus, we only go to a short depth (5)
|
|
|
1302 and only hash at most 5 elements out of a vector. Theoretically
|
|
|
1303 we could still take 5^5 time (a big big number) to compute a
|
|
|
1304 hash, but practically this won't ever happen. */
|
|
|
1305
|
|
380
|
1306 hashcode_t
|
|
0
|
1307 internal_hash (Lisp_Object obj, int depth)
|
|
|
1308 {
|
|
|
1309 if (depth > 5)
|
|
|
1310 return 0;
|
|
|
1311 if (CONSP (obj))
|
|
|
1312 {
|
|
|
1313 /* no point in worrying about tail recursion, since we're not
|
|
|
1314 going very deep */
|
|
|
1315 return HASH2 (internal_hash (XCAR (obj), depth + 1),
|
|
|
1316 internal_hash (XCDR (obj), depth + 1));
|
|
|
1317 }
|
|
380
|
1318 if (STRINGP (obj))
|
|
0
|
1319 {
|
|
380
|
1320 return hash_string (XSTRING_DATA (obj), XSTRING_LENGTH (obj));
|
|
|
1321 }
|
|
412
|
1322 if (VECTORP (obj))
|
|
|
1323 {
|
|
|
1324 return HASH2 (XVECTOR_LENGTH (obj),
|
|
|
1325 internal_array_hash (XVECTOR_DATA (obj),
|
|
|
1326 XVECTOR_LENGTH (obj),
|
|
|
1327 depth + 1));
|
|
|
1328 }
|
|
380
|
1329 if (LRECORDP (obj))
|
|
0
|
1330 {
|
|
412
|
1331 CONST struct lrecord_implementation
|
|
211
|
1332 *imp = XRECORD_LHEADER_IMPLEMENTATION (obj);
|
|
0
|
1333 if (imp->hash)
|
|
380
|
1334 return imp->hash (obj, depth);
|
|
0
|
1335 }
|
|
|
1336
|
|
|
1337 return LISP_HASH (obj);
|
|
|
1338 }
|
|
|
1339
|
|
241
|
1340 #if 0
|
|
|
1341 xxDEFUN ("internal-hash-value", Finternal_hash_value, 1, 1, 0, /*
|
|
|
1342 Hash value of OBJECT. For debugging.
|
|
|
1343 The value is returned as (HIGH . LOW).
|
|
|
1344 */
|
|
|
1345 (object))
|
|
|
1346 {
|
|
|
1347 /* This function is pretty 32bit-centric. */
|
|
412
|
1348 unsigned long hash = internal_hash (object, 0);
|
|
241
|
1349 return Fcons (hash >> 16, hash & 0xffff);
|
|
|
1350 }
|
|
|
1351 #endif
|
|
|
1352
|
|
0
|
1353
|
|
|
1354 /************************************************************************/
|
|
|
1355 /* initialization */
|
|
|
1356 /************************************************************************/
|
|
|
1357
|
|
|
1358 void
|
|
|
1359 syms_of_elhash (void)
|
|
|
1360 {
|
|
380
|
1361 DEFSUBR (Fhash_table_p);
|
|
|
1362 DEFSUBR (Fmake_hash_table);
|
|
|
1363 DEFSUBR (Fcopy_hash_table);
|
|
20
|
1364 DEFSUBR (Fgethash);
|
|
380
|
1365 DEFSUBR (Fremhash);
|
|
20
|
1366 DEFSUBR (Fputhash);
|
|
|
1367 DEFSUBR (Fclrhash);
|
|
|
1368 DEFSUBR (Fmaphash);
|
|
380
|
1369 DEFSUBR (Fhash_table_count);
|
|
|
1370 DEFSUBR (Fhash_table_size);
|
|
|
1371 DEFSUBR (Fhash_table_rehash_size);
|
|
|
1372 DEFSUBR (Fhash_table_rehash_threshold);
|
|
412
|
1373 DEFSUBR (Fhash_table_type);
|
|
|
1374 DEFSUBR (Fhash_table_test);
|
|
241
|
1375 #if 0
|
|
|
1376 DEFSUBR (Finternal_hash_value);
|
|
|
1377 #endif
|
|
380
|
1378
|
|
|
1379 defsymbol (&Qhash_tablep, "hash-table-p");
|
|
|
1380 defsymbol (&Qhash_table, "hash-table");
|
|
223
|
1381 defsymbol (&Qhashtable, "hashtable");
|
|
412
|
1382 defsymbol (&Qweak, "weak");
|
|
|
1383 defsymbol (&Qkey_weak, "key-weak");
|
|
|
1384 defsymbol (&Qvalue_weak, "value-weak");
|
|
|
1385 defsymbol (&Qnon_weak, "non-weak");
|
|
380
|
1386 defsymbol (&Qrehash_size, "rehash-size");
|
|
|
1387 defsymbol (&Qrehash_threshold, "rehash-threshold");
|
|
|
1388
|
|
412
|
1389 defkeyword (&Q_size, ":size");
|
|
380
|
1390 defkeyword (&Q_test, ":test");
|
|
412
|
1391 defkeyword (&Q_type, ":type");
|
|
380
|
1392 defkeyword (&Q_rehash_size, ":rehash-size");
|
|
|
1393 defkeyword (&Q_rehash_threshold, ":rehash-threshold");
|
|
0
|
1394 }
|
|
|
1395
|
|
|
1396 void
|
|
|
1397 vars_of_elhash (void)
|
|
|
1398 {
|
|
2
|
1399 /* This must NOT be staticpro'd */
|
|
380
|
1400 Vall_weak_hash_tables = Qnil;
|
|
0
|
1401 }
|
