|
0
|
1 /* Lisp interface to hash tables.
|
|
|
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
|
|
|
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 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
|
|
|
25 #include <config.h>
|
|
|
26 #include "lisp.h"
|
|
|
27 #include "hash.h"
|
|
|
28 #include "elhash.h"
|
|
|
29 #include "bytecode.h"
|
|
|
30
|
|
223
|
31 Lisp_Object Qhashtablep, Qhashtable;
|
|
|
32 Lisp_Object Qweak, Qkey_weak, Qvalue_weak, Qnon_weak;
|
|
0
|
33
|
|
|
34 #define LISP_OBJECTS_PER_HENTRY (sizeof (hentry) / sizeof (Lisp_Object))/* 2 */
|
|
|
35
|
|
185
|
36 struct hashtable
|
|
0
|
37 {
|
|
|
38 struct lcrecord_header header;
|
|
|
39 unsigned int fullness;
|
|
|
40 unsigned long (*hash_function) (CONST void *);
|
|
|
41 int (*test_function) (CONST void *, CONST void *);
|
|
|
42 Lisp_Object zero_entry;
|
|
|
43 Lisp_Object harray;
|
|
|
44 enum hashtable_type type; /* whether and how this hashtable is weak */
|
|
|
45 Lisp_Object next_weak; /* Used to chain together all of the weak
|
|
|
46 hashtables. Don't mark through this. */
|
|
|
47 };
|
|
|
48
|
|
|
49 static Lisp_Object Vall_weak_hashtables;
|
|
|
50
|
|
|
51 static Lisp_Object mark_hashtable (Lisp_Object, void (*) (Lisp_Object));
|
|
|
52 static void print_hashtable (Lisp_Object, Lisp_Object, int);
|
|
231
|
53 static int hashtable_equal (Lisp_Object t1, Lisp_Object t2, int depth);
|
|
241
|
54 static unsigned long hashtable_hash (Lisp_Object obj, int depth);
|
|
0
|
55 DEFINE_LRECORD_IMPLEMENTATION ("hashtable", hashtable,
|
|
231
|
56 mark_hashtable, print_hashtable, 0,
|
|
241
|
57 hashtable_equal, hashtable_hash,
|
|
|
58 struct hashtable);
|
|
0
|
59
|
|
|
60 static Lisp_Object
|
|
|
61 mark_hashtable (Lisp_Object obj, void (*markobj) (Lisp_Object))
|
|
|
62 {
|
|
185
|
63 struct hashtable *table = XHASHTABLE (obj);
|
|
0
|
64
|
|
|
65 if (table->type != HASHTABLE_NONWEAK)
|
|
|
66 {
|
|
|
67 /* If the table is weak, we don't want to mark the keys and values
|
|
|
68 (we scan over them after everything else has been marked,
|
|
|
69 and mark or remove them as necessary). Note that we will mark
|
|
|
70 the table->harray itself at the same time; it's hard to mark
|
|
|
71 that here without also marking its contents. */
|
|
|
72 return Qnil;
|
|
|
73 }
|
|
|
74 ((markobj) (table->zero_entry));
|
|
173
|
75 return table->harray;
|
|
0
|
76 }
|
|
223
|
77
|
|
231
|
78 /* Equality of hashtables. Two hashtables are equal when they are of
|
|
|
79 the same type and test function, they have the same number of
|
|
|
80 elements, and for each key in hashtable, the values are `equal'.
|
|
|
81
|
|
|
82 This is similar to Common Lisp `equalp' of hashtables, with the
|
|
241
|
83 difference that CL requires the keys to be compared with the test
|
|
|
84 function, which we don't do. Doing that would require consing, and
|
|
|
85 consing is bad idea in `equal'. Anyway, our method should provide
|
|
|
86 the same result -- if the keys are not equal according to test
|
|
|
87 function, then Fgethash() in hashtable_equal_mapper() will fail. */
|
|
231
|
88 struct hashtable_equal_closure
|
|
|
89 {
|
|
|
90 int depth;
|
|
241
|
91 int equal;
|
|
231
|
92 Lisp_Object other_table;
|
|
|
93 };
|
|
|
94
|
|
241
|
95 static int
|
|
231
|
96 hashtable_equal_mapper (void *key, void *contents, void *arg)
|
|
|
97 {
|
|
|
98 struct hashtable_equal_closure *closure =
|
|
|
99 (struct hashtable_equal_closure *)arg;
|
|
|
100 Lisp_Object keytem, valuetem;
|
|
241
|
101 Lisp_Object value_in_other;
|
|
231
|
102
|
|
241
|
103 CVOID_TO_LISP (keytem, key);
|
|
|
104 CVOID_TO_LISP (valuetem, contents);
|
|
|
105 /* Look up the key in the other hashtable, and compare the values. */
|
|
|
106 value_in_other = Fgethash (keytem, closure->other_table, Qunbound);
|
|
|
107 if (UNBOUNDP (value_in_other)
|
|
|
108 || !internal_equal (valuetem, value_in_other, closure->depth))
|
|
231
|
109 {
|
|
241
|
110 /* Give up. */
|
|
|
111 closure->equal = 0;
|
|
|
112 return 1;
|
|
231
|
113 }
|
|
241
|
114 return 0;
|
|
231
|
115 }
|
|
|
116
|
|
|
117 static int
|
|
|
118 hashtable_equal (Lisp_Object t1, Lisp_Object t2, int depth)
|
|
|
119 {
|
|
|
120 struct hashtable_equal_closure closure;
|
|
|
121 struct hashtable *table1 = XHASHTABLE (t1);
|
|
|
122 struct hashtable *table2 = XHASHTABLE (t2);
|
|
|
123
|
|
|
124 /* The objects are `equal' if they are of the same type, so return 0
|
|
|
125 if types or test functions are not the same. Obviously, the
|
|
|
126 number of elements must be equal, too. */
|
|
|
127 if ((table1->test_function != table2->test_function)
|
|
|
128 || (table1->type != table2->type)
|
|
|
129 || (table1->fullness != table2->fullness))
|
|
|
130 return 0;
|
|
|
131
|
|
|
132 closure.depth = depth + 1;
|
|
241
|
133 closure.equal = 1;
|
|
231
|
134 closure.other_table = t2;
|
|
|
135 elisp_maphash (hashtable_equal_mapper, t1, &closure);
|
|
241
|
136 return closure.equal;
|
|
|
137 }
|
|
|
138
|
|
|
139 /* Hashtable hash function. This hashes 5 key-value pairs. For EQ
|
|
|
140 hashtables, keys are used as the hash value themselves, whereas
|
|
|
141 values are hashed with internal_hash(). For EQUAL hashtables, both
|
|
|
142 keys and values are hashed properly. EQL tables are handled as
|
|
|
143 necessary. All of this should make the hash function compatible
|
|
|
144 with hashtable_equal(). The elements hashed are the first five
|
|
|
145 mapped over by maphash(). */
|
|
|
146
|
|
|
147 struct hashtable_hash_closure
|
|
|
148 {
|
|
|
149 struct hashtable *table;
|
|
|
150 int depth;
|
|
|
151 unsigned long hash;
|
|
|
152 int count;
|
|
|
153 };
|
|
|
154
|
|
|
155 /* Needed for tests. */
|
|
|
156 static int lisp_object_eql_equal (CONST void *x1, CONST void *x2);
|
|
|
157 static int lisp_object_equal_equal (CONST void *x1, CONST void *x2);
|
|
|
158
|
|
|
159 static int
|
|
|
160 hashtable_hash_mapper (void *key, void *contents, void *arg)
|
|
|
161 {
|
|
|
162 struct hashtable_hash_closure *closure =
|
|
|
163 (struct hashtable_hash_closure *)arg;
|
|
|
164 Lisp_Object valuetem, keytem;
|
|
|
165 unsigned long keyhash;
|
|
|
166
|
|
|
167 CVOID_TO_LISP (keytem, key);
|
|
|
168 CVOID_TO_LISP (valuetem, contents);
|
|
|
169
|
|
|
170 if (!closure->table->test_function)
|
|
|
171 /* For eq, use key itself as hash. */
|
|
|
172 keyhash = LISP_HASH (keytem);
|
|
|
173 else if (closure->table->test_function == lisp_object_eql_equal)
|
|
|
174 /* The same as eq, unless the key is float. */
|
|
|
175 keyhash = (FLOATP (keytem)
|
|
|
176 ? internal_hash (keytem, closure->depth) : LISP_HASH (keytem));
|
|
|
177 else
|
|
|
178 /* equal: hash the key properly. */
|
|
|
179 keyhash = internal_hash (keytem, closure->depth);
|
|
|
180
|
|
|
181 closure->hash = HASH3 (closure->hash, keyhash,
|
|
|
182 internal_hash (valuetem, closure->depth));
|
|
|
183 return (++closure->count > 5) ? 1 : 0;
|
|
|
184 }
|
|
|
185
|
|
|
186 static unsigned long
|
|
|
187 hashtable_hash (Lisp_Object obj, int depth)
|
|
|
188 {
|
|
|
189 struct hashtable_hash_closure closure;
|
|
|
190
|
|
|
191 closure.table = XHASHTABLE (obj);
|
|
|
192 closure.depth = depth + 1;
|
|
|
193 closure.hash = 0;
|
|
|
194 closure.count = 0;
|
|
|
195
|
|
|
196 elisp_maphash (hashtable_hash_mapper, obj, &closure);
|
|
|
197 return closure.hash;
|
|
231
|
198 }
|
|
|
199
|
|
223
|
200 /* Printing hashtables.
|
|
|
201
|
|
|
202 This is non-trivial, because we use a readable structure-style
|
|
|
203 syntax for hashtables. This means that a typical hashtable will be
|
|
|
204 readably printed in the form of:
|
|
|
205
|
|
|
206 #s(hashtable size 2 data (key1 value1 key2 value2))
|
|
|
207
|
|
|
208 The supported keywords are `type' (non-weak (or nil), weak,
|
|
|
209 key-weak and value-weak), `test' (eql (or nil), eq or equal),
|
|
|
210 `size' (a natnum or nil) and `data' (a list).
|
|
|
211
|
|
|
212 If `print-readably' is non-nil, then a simpler syntax is used; for
|
|
|
213 instance:
|
|
|
214
|
|
|
215 #<hashtable size 2/13 data (key1 value1 key2 value2) 0x874d>
|
|
|
216
|
|
|
217 The data is truncated to four pairs, and the rest is shown with
|
|
241
|
218 `...'. This printer does not cons. */
|
|
223
|
219
|
|
231
|
220 struct print_hashtable_data_closure
|
|
|
221 {
|
|
|
222 EMACS_INT count; /* Used to implement truncation for
|
|
|
223 non-readable printing, as well as
|
|
|
224 to avoid the unnecessary space at
|
|
|
225 the beginning. */
|
|
223
|
226 Lisp_Object printcharfun;
|
|
|
227 };
|
|
|
228
|
|
241
|
229 static int
|
|
223
|
230 print_hashtable_data_mapper (void *key, void *contents, void *arg)
|
|
|
231 {
|
|
|
232 Lisp_Object keytem, valuetem;
|
|
231
|
233 struct print_hashtable_data_closure *closure =
|
|
|
234 (struct print_hashtable_data_closure *)arg;
|
|
223
|
235
|
|
|
236 if (closure->count < 4 || print_readably)
|
|
|
237 {
|
|
|
238 CVOID_TO_LISP (keytem, key);
|
|
|
239 CVOID_TO_LISP (valuetem, contents);
|
|
|
240
|
|
|
241 if (closure->count)
|
|
|
242 write_c_string (" ", closure->printcharfun);
|
|
|
243
|
|
|
244 print_internal (keytem, closure->printcharfun, 1);
|
|
|
245 write_c_string (" ", closure->printcharfun);
|
|
|
246 print_internal (valuetem, closure->printcharfun, 1);
|
|
|
247 }
|
|
|
248 ++closure->count;
|
|
241
|
249 return 0;
|
|
223
|
250 }
|
|
|
251
|
|
|
252 /* Print the data of the hashtable. This maps through a Lisp
|
|
|
253 hashtable and prints key/value pairs using PRINTCHARFUN. */
|
|
|
254 static void
|
|
|
255 print_hashtable_data (Lisp_Object hashtable, Lisp_Object printcharfun)
|
|
|
256 {
|
|
231
|
257 struct print_hashtable_data_closure closure;
|
|
223
|
258 closure.count = 0;
|
|
|
259 closure.printcharfun = printcharfun;
|
|
|
260
|
|
|
261 write_c_string (" data (", printcharfun);
|
|
|
262 elisp_maphash (print_hashtable_data_mapper, hashtable, &closure);
|
|
|
263 write_c_string ((!print_readably && closure.count > 4) ? " ...)" : ")",
|
|
|
264 printcharfun);
|
|
|
265 }
|
|
|
266
|
|
0
|
267 static void
|
|
|
268 print_hashtable (Lisp_Object obj, Lisp_Object printcharfun, int escapeflag)
|
|
|
269 {
|
|
185
|
270 struct hashtable *table = XHASHTABLE (obj);
|
|
223
|
271 char buf[128];
|
|
|
272
|
|
|
273 write_c_string (print_readably ? "#s(hashtable" : "#<hashtable",
|
|
|
274 printcharfun);
|
|
|
275 if (table->type != HASHTABLE_NONWEAK)
|
|
|
276 {
|
|
|
277 sprintf (buf, " type %s",
|
|
|
278 (table->type == HASHTABLE_WEAK ? "weak" :
|
|
|
279 table->type == HASHTABLE_KEY_WEAK ? "key-weak" :
|
|
|
280 table->type == HASHTABLE_VALUE_WEAK ? "value-weak" :
|
|
|
281 "you-d-better-not-see-this"));
|
|
|
282 write_c_string (buf, printcharfun);
|
|
|
283 }
|
|
241
|
284 /* These checks have a kludgy look to them, but they are safe. Due
|
|
|
285 to nature of hashing, you cannot use arbitrary test functions
|
|
|
286 anyway. */
|
|
|
287 if (!table->test_function)
|
|
223
|
288 write_c_string (" test eq", printcharfun);
|
|
|
289 else if (table->test_function == lisp_object_equal_equal)
|
|
|
290 write_c_string (" test equal", printcharfun);
|
|
|
291 else if (table->test_function == lisp_object_eql_equal)
|
|
231
|
292 DO_NOTHING;
|
|
223
|
293 else
|
|
|
294 abort ();
|
|
|
295 if (table->fullness || !print_readably)
|
|
|
296 {
|
|
|
297 if (print_readably)
|
|
231
|
298 sprintf (buf, " size %u", table->fullness);
|
|
223
|
299 else
|
|
|
300 sprintf (buf, " size %u/%ld", table->fullness,
|
|
|
301 XVECTOR_LENGTH (table->harray) / LISP_OBJECTS_PER_HENTRY);
|
|
|
302 write_c_string (buf, printcharfun);
|
|
|
303 }
|
|
|
304 if (table->fullness)
|
|
|
305 print_hashtable_data (obj, printcharfun);
|
|
0
|
306 if (print_readably)
|
|
223
|
307 write_c_string (")", printcharfun);
|
|
|
308 else
|
|
|
309 {
|
|
|
310 sprintf (buf, " 0x%x>", table->header.uid);
|
|
|
311 write_c_string (buf, printcharfun);
|
|
|
312 }
|
|
|
313 }
|
|
|
314
|
|
|
315
|
|
|
316 /* Pretty reading of hashtables.
|
|
|
317
|
|
|
318 Here we use the existing structures mechanism (which is,
|
|
|
319 unfortunately, pretty cumbersome) for validating and instantiating
|
|
|
320 the hashtables. The idea is that the side-effect of reading a
|
|
|
321 #s(hashtable PLIST) object is creation of a hashtable with desired
|
|
|
322 properties, and that the hashtable is returned. */
|
|
|
323
|
|
|
324 /* Validation functions: each keyword provides its own validation
|
|
|
325 function. The errors should maybe be continuable, but it is
|
|
|
326 unclear how this would cope with ERRB. */
|
|
|
327 static int
|
|
|
328 hashtable_type_validate (Lisp_Object keyword, Lisp_Object value,
|
|
|
329 Error_behavior errb)
|
|
|
330 {
|
|
|
331 if (!(NILP (value)
|
|
|
332 || EQ (value, Qnon_weak)
|
|
|
333 || EQ (value, Qweak)
|
|
|
334 || EQ (value, Qkey_weak)
|
|
|
335 || EQ (value, Qvalue_weak)))
|
|
|
336 {
|
|
|
337 maybe_signal_simple_error ("Invalid hashtable type", value,
|
|
|
338 Qhashtable, errb);
|
|
|
339 return 0;
|
|
|
340 }
|
|
|
341 return 1;
|
|
|
342 }
|
|
|
343
|
|
|
344 static int
|
|
|
345 hashtable_test_validate (Lisp_Object keyword, Lisp_Object value,
|
|
|
346 Error_behavior errb)
|
|
|
347 {
|
|
|
348 if (!(NILP (value)
|
|
|
349 || EQ (value, Qeq)
|
|
|
350 || EQ (value, Qeql)
|
|
|
351 || EQ (value, Qequal)))
|
|
|
352 {
|
|
|
353 maybe_signal_simple_error ("Invalid hashtable test", value,
|
|
|
354 Qhashtable, errb);
|
|
|
355 return 0;
|
|
|
356 }
|
|
|
357 return 1;
|
|
|
358 }
|
|
|
359
|
|
|
360 static int
|
|
|
361 hashtable_size_validate (Lisp_Object keyword, Lisp_Object value,
|
|
|
362 Error_behavior errb)
|
|
|
363 {
|
|
|
364 if (!NATNUMP (value))
|
|
|
365 {
|
|
|
366 maybe_signal_error (Qwrong_type_argument, list2 (Qnatnump, value),
|
|
|
367 Qhashtable, errb);
|
|
|
368 return 0;
|
|
|
369 }
|
|
|
370 return 1;
|
|
0
|
371 }
|
|
|
372
|
|
223
|
373 static int
|
|
|
374 hashtable_data_validate (Lisp_Object keyword, Lisp_Object value,
|
|
|
375 Error_behavior errb)
|
|
|
376 {
|
|
|
377 int num = 0;
|
|
|
378 Lisp_Object tail;
|
|
|
379
|
|
|
380 /* #### Doesn't respect ERRB! */
|
|
|
381 EXTERNAL_LIST_LOOP (tail, value)
|
|
|
382 {
|
|
|
383 ++num;
|
|
|
384 QUIT;
|
|
|
385 }
|
|
|
386 if (num & 1)
|
|
|
387 {
|
|
|
388 maybe_signal_simple_error
|
|
|
389 ("Hashtable data must have alternating keyword/value pairs", value,
|
|
|
390 Qhashtable, errb);
|
|
|
391 return 0;
|
|
|
392 }
|
|
|
393 return 1;
|
|
|
394 }
|
|
|
395
|
|
|
396 /* The actual instantiation of hashtable. This does practically no
|
|
|
397 error checking, because it relies on the fact that the paranoid
|
|
|
398 functions above have error-checked everything to the last details.
|
|
|
399 If this assumption is wrong, we will get a crash immediately (with
|
|
|
400 error-checking compiled in), and we'll know if there is a bug in
|
|
|
401 the structure mechanism. So there. */
|
|
|
402 static Lisp_Object
|
|
|
403 hashtable_instantiate (Lisp_Object plist)
|
|
|
404 {
|
|
|
405 /* I'm not sure whether this can GC, but better safe than sorry. */
|
|
|
406 Lisp_Object hashtab = Qnil;
|
|
|
407 Lisp_Object type = Qnil, test = Qnil, size = Qnil, data = Qnil;
|
|
|
408 Lisp_Object key, value;
|
|
|
409 struct gcpro gcpro1;
|
|
|
410 GCPRO1 (hashtab);
|
|
|
411
|
|
|
412 while (!NILP (plist))
|
|
|
413 {
|
|
|
414 key = XCAR (plist);
|
|
|
415 plist = XCDR (plist);
|
|
|
416 value = XCAR (plist);
|
|
|
417 plist = XCDR (plist);
|
|
|
418 if (EQ (key, Qtype))
|
|
|
419 type = value;
|
|
|
420 else if (EQ (key, Qtest))
|
|
|
421 test = value;
|
|
|
422 else if (EQ (key, Qsize))
|
|
|
423 size = value;
|
|
|
424 else if (EQ (key, Qdata))
|
|
|
425 data = value;
|
|
|
426 else
|
|
|
427 abort ();
|
|
|
428 }
|
|
|
429 if (NILP (type))
|
|
|
430 type = Qnon_weak;
|
|
|
431 if (NILP (size))
|
|
|
432 {
|
|
|
433 /* Divide by two, because data is a plist. */
|
|
|
434 XSETINT (size, XINT (Flength (data)) / 2);
|
|
|
435 }
|
|
|
436
|
|
|
437 /* Create the hashtable. */
|
|
|
438 if (EQ (type, Qnon_weak))
|
|
|
439 hashtab = Fmake_hashtable (size, test);
|
|
|
440 else if (EQ (type, Qweak))
|
|
|
441 hashtab = Fmake_weak_hashtable (size, test);
|
|
|
442 else if (EQ (type, Qkey_weak))
|
|
|
443 hashtab = Fmake_key_weak_hashtable (size, test);
|
|
|
444 else if (EQ (type, Qvalue_weak))
|
|
|
445 hashtab = Fmake_value_weak_hashtable (size, test);
|
|
|
446 else
|
|
|
447 abort ();
|
|
|
448
|
|
|
449 /* And fill it with data. */
|
|
|
450 while (!NILP (data))
|
|
|
451 {
|
|
|
452 key = XCAR (data);
|
|
|
453 data = XCDR (data);
|
|
|
454 value = XCAR (data);
|
|
|
455 data = XCDR (data);
|
|
|
456 Fputhash (key, value, hashtab);
|
|
|
457 }
|
|
|
458
|
|
|
459 UNGCPRO;
|
|
|
460 return hashtab;
|
|
|
461 }
|
|
|
462
|
|
|
463 /* Initialize the hashtable as a structure type. This is called from
|
|
|
464 emacs.c. */
|
|
|
465 void
|
|
|
466 structure_type_create_hashtable (void)
|
|
|
467 {
|
|
|
468 struct structure_type *st;
|
|
|
469
|
|
|
470 st = define_structure_type (Qhashtable, 0, hashtable_instantiate);
|
|
|
471 define_structure_type_keyword (st, Qtype, hashtable_type_validate);
|
|
|
472 define_structure_type_keyword (st, Qtest, hashtable_test_validate);
|
|
|
473 define_structure_type_keyword (st, Qsize, hashtable_size_validate);
|
|
|
474 define_structure_type_keyword (st, Qdata, hashtable_data_validate);
|
|
|
475 }
|
|
|
476
|
|
|
477 /* Basic conversion and allocation functions. */
|
|
|
478
|
|
|
479 /* Create a C hashtable from the data in the Lisp hashtable. The
|
|
|
480 actual vector is not copied, nor are the keys or values copied. */
|
|
0
|
481 static void
|
|
185
|
482 ht_copy_to_c (struct hashtable *ht, c_hashtable c_table)
|
|
0
|
483 {
|
|
173
|
484 int len = XVECTOR_LENGTH (ht->harray);
|
|
0
|
485
|
|
185
|
486 c_table->harray = (hentry *) XVECTOR_DATA (ht->harray);
|
|
0
|
487 c_table->zero_set = (!GC_UNBOUNDP (ht->zero_entry));
|
|
|
488 c_table->zero_entry = LISP_TO_VOID (ht->zero_entry);
|
|
207
|
489 #ifndef LRECORD_VECTOR
|
|
0
|
490 if (len < 0)
|
|
|
491 {
|
|
|
492 /* #### if alloc.c mark_object() changes, this must change too. */
|
|
|
493 /* barf gag retch. When a vector is marked, its len is
|
|
|
494 made less than 0. In the prune_weak_hashtables() stage,
|
|
|
495 we are called on vectors that are like this, and we must
|
|
|
496 be able to deal. */
|
|
|
497 assert (gc_in_progress);
|
|
|
498 len = -1 - len;
|
|
|
499 }
|
|
207
|
500 #endif
|
|
173
|
501 c_table->size = len/LISP_OBJECTS_PER_HENTRY;
|
|
|
502 c_table->fullness = ht->fullness;
|
|
0
|
503 c_table->hash_function = ht->hash_function;
|
|
|
504 c_table->test_function = ht->test_function;
|
|
|
505 XSETHASHTABLE (c_table->elisp_table, ht);
|
|
|
506 }
|
|
|
507
|
|
|
508 static void
|
|
185
|
509 ht_copy_from_c (c_hashtable c_table, struct hashtable *ht)
|
|
0
|
510 {
|
|
|
511 struct Lisp_Vector dummy;
|
|
|
512 /* C is truly hateful */
|
|
|
513 void *vec_addr
|
|
185
|
514 = ((char *) c_table->harray
|
|
173
|
515 - ((char *) &(dummy.contents[0]) - (char *) &dummy));
|
|
0
|
516
|
|
|
517 XSETVECTOR (ht->harray, vec_addr);
|
|
|
518 if (c_table->zero_set)
|
|
|
519 VOID_TO_LISP (ht->zero_entry, c_table->zero_entry);
|
|
|
520 else
|
|
|
521 ht->zero_entry = Qunbound;
|
|
|
522 ht->fullness = c_table->fullness;
|
|
|
523 }
|
|
|
524
|
|
|
525
|
|
185
|
526 static struct hashtable *
|
|
0
|
527 allocate_hashtable (void)
|
|
|
528 {
|
|
185
|
529 struct hashtable *table =
|
|
|
530 alloc_lcrecord_type (struct hashtable, lrecord_hashtable);
|
|
173
|
531 table->harray = Qnil;
|
|
|
532 table->zero_entry = Qunbound;
|
|
|
533 table->fullness = 0;
|
|
0
|
534 table->hash_function = 0;
|
|
|
535 table->test_function = 0;
|
|
173
|
536 return table;
|
|
0
|
537 }
|
|
|
538
|
|
173
|
539 void *
|
|
0
|
540 elisp_hvector_malloc (unsigned int bytes, Lisp_Object table)
|
|
|
541 {
|
|
|
542 Lisp_Object new_vector;
|
|
185
|
543 struct hashtable *ht = XHASHTABLE (table);
|
|
0
|
544
|
|
173
|
545 assert (bytes > XVECTOR_LENGTH (ht->harray) * sizeof (Lisp_Object));
|
|
207
|
546 new_vector = make_vector ((bytes / sizeof (Lisp_Object)), Qnull_pointer);
|
|
173
|
547 return (void *) XVECTOR_DATA (new_vector);
|
|
0
|
548 }
|
|
|
549
|
|
|
550 void
|
|
|
551 elisp_hvector_free (void *ptr, Lisp_Object table)
|
|
|
552 {
|
|
185
|
553 struct hashtable *ht = XHASHTABLE (table);
|
|
0
|
554 #if defined (USE_ASSERTIONS) || defined (DEBUG_XEMACS)
|
|
|
555 Lisp_Object current_vector = ht->harray;
|
|
|
556 #endif
|
|
|
557
|
|
173
|
558 assert (((void *) XVECTOR_DATA (current_vector)) == ptr);
|
|
0
|
559 ht->harray = Qnil; /* Let GC do its job */
|
|
|
560 }
|
|
|
561
|
|
|
562
|
|
20
|
563 DEFUN ("hashtablep", Fhashtablep, 1, 1, 0, /*
|
|
0
|
564 Return t if OBJ is a hashtable, else nil.
|
|
20
|
565 */
|
|
|
566 (obj))
|
|
0
|
567 {
|
|
173
|
568 return HASHTABLEP (obj) ? Qt : Qnil;
|
|
0
|
569 }
|
|
|
570
|
|
|
571
|
|
|
572
|
|
|
573
|
|
|
574 #if 0 /* I don't think these are needed any more.
|
|
|
575 If using the general lisp_object_equal_*() functions
|
|
|
576 causes efficiency problems, these can be resurrected. --ben */
|
|
|
577 /* equality and hash functions for Lisp strings */
|
|
|
578 int
|
|
|
579 lisp_string_equal (CONST void *x1, CONST void *x2)
|
|
|
580 {
|
|
241
|
581 /* This is wrong anyway. You can't use strcmp() on Lisp strings,
|
|
|
582 because they can contain zero characters. */
|
|
0
|
583 Lisp_Object str1, str2;
|
|
|
584 CVOID_TO_LISP (str1, x1);
|
|
|
585 CVOID_TO_LISP (str2, x2);
|
|
14
|
586 return !strcmp ((char *) XSTRING_DATA (str1), (char *) XSTRING_DATA (str2));
|
|
0
|
587 }
|
|
|
588
|
|
|
589 unsigned long
|
|
|
590 lisp_string_hash (CONST void *x)
|
|
|
591 {
|
|
|
592 Lisp_Object str;
|
|
|
593 CVOID_TO_LISP (str, x);
|
|
14
|
594 return hash_string (XSTRING_DATA (str), XSTRING_LENGTH (str));
|
|
0
|
595 }
|
|
|
596
|
|
|
597 #endif /* 0 */
|
|
|
598
|
|
|
599 static int
|
|
|
600 lisp_object_eql_equal (CONST void *x1, CONST void *x2)
|
|
|
601 {
|
|
|
602 Lisp_Object obj1, obj2;
|
|
|
603 CVOID_TO_LISP (obj1, x1);
|
|
|
604 CVOID_TO_LISP (obj2, x2);
|
|
195
|
605 return FLOATP (obj1) ? internal_equal (obj1, obj2, 0) : EQ (obj1, obj2);
|
|
0
|
606 }
|
|
|
607
|
|
|
608 static unsigned long
|
|
|
609 lisp_object_eql_hash (CONST void *x)
|
|
|
610 {
|
|
|
611 Lisp_Object obj;
|
|
|
612 CVOID_TO_LISP (obj, x);
|
|
|
613 if (FLOATP (obj))
|
|
|
614 return internal_hash (obj, 0);
|
|
|
615 else
|
|
|
616 return LISP_HASH (obj);
|
|
|
617 }
|
|
|
618
|
|
|
619 static int
|
|
|
620 lisp_object_equal_equal (CONST void *x1, CONST void *x2)
|
|
|
621 {
|
|
|
622 Lisp_Object obj1, obj2;
|
|
|
623 CVOID_TO_LISP (obj1, x1);
|
|
|
624 CVOID_TO_LISP (obj2, x2);
|
|
195
|
625 return internal_equal (obj1, obj2, 0);
|
|
0
|
626 }
|
|
|
627
|
|
|
628 static unsigned long
|
|
|
629 lisp_object_equal_hash (CONST void *x)
|
|
|
630 {
|
|
|
631 Lisp_Object obj;
|
|
|
632 CVOID_TO_LISP (obj, x);
|
|
|
633 return internal_hash (obj, 0);
|
|
|
634 }
|
|
|
635
|
|
|
636 Lisp_Object
|
|
|
637 make_lisp_hashtable (int size,
|
|
|
638 enum hashtable_type type,
|
|
|
639 enum hashtable_test_fun test)
|
|
|
640 {
|
|
|
641 Lisp_Object result;
|
|
185
|
642 struct hashtable *table = allocate_hashtable ();
|
|
0
|
643
|
|
|
644 table->harray = make_vector ((compute_harray_size (size)
|
|
|
645 * LISP_OBJECTS_PER_HENTRY),
|
|
207
|
646 Qnull_pointer);
|
|
0
|
647 switch (test)
|
|
|
648 {
|
|
|
649 case HASHTABLE_EQ:
|
|
187
|
650 table->test_function = NULL;
|
|
|
651 table->hash_function = NULL;
|
|
0
|
652 break;
|
|
|
653
|
|
|
654 case HASHTABLE_EQL:
|
|
|
655 table->test_function = lisp_object_eql_equal;
|
|
|
656 table->hash_function = lisp_object_eql_hash;
|
|
|
657 break;
|
|
|
658
|
|
|
659 case HASHTABLE_EQUAL:
|
|
|
660 table->test_function = lisp_object_equal_equal;
|
|
|
661 table->hash_function = lisp_object_equal_hash;
|
|
|
662 break;
|
|
|
663
|
|
|
664 default:
|
|
|
665 abort ();
|
|
|
666 }
|
|
|
667
|
|
|
668 table->type = type;
|
|
|
669 XSETHASHTABLE (result, table);
|
|
|
670
|
|
|
671 if (table->type != HASHTABLE_NONWEAK)
|
|
|
672 {
|
|
|
673 table->next_weak = Vall_weak_hashtables;
|
|
|
674 Vall_weak_hashtables = result;
|
|
|
675 }
|
|
|
676 else
|
|
|
677 table->next_weak = Qunbound;
|
|
|
678
|
|
173
|
679 return result;
|
|
0
|
680 }
|
|
|
681
|
|
|
682 static enum hashtable_test_fun
|
|
|
683 decode_hashtable_test_fun (Lisp_Object sym)
|
|
|
684 {
|
|
187
|
685 if (NILP (sym)) return HASHTABLE_EQL;
|
|
2
|
686 if (EQ (sym, Qeq)) return HASHTABLE_EQ;
|
|
|
687 if (EQ (sym, Qequal)) return HASHTABLE_EQUAL;
|
|
|
688 if (EQ (sym, Qeql)) return HASHTABLE_EQL;
|
|
185
|
689
|
|
231
|
690 signal_simple_error ("Invalid hashtable test function", sym);
|
|
2
|
691 return HASHTABLE_EQ; /* not reached */
|
|
0
|
692 }
|
|
|
693
|
|
20
|
694 DEFUN ("make-hashtable", Fmake_hashtable, 1, 2, 0, /*
|
|
0
|
695 Make a hashtable of initial size SIZE.
|
|
|
696 Comparison between keys is done with TEST-FUN, which must be one of
|
|
|
697 `eq', `eql', or `equal'. The default is `eql'; i.e. two keys must
|
|
|
698 be the same object (or have the same floating-point value, for floats)
|
|
|
699 to be considered equivalent.
|
|
|
700
|
|
|
701 See also `make-weak-hashtable', `make-key-weak-hashtable', and
|
|
|
702 `make-value-weak-hashtable'.
|
|
20
|
703 */
|
|
|
704 (size, test_fun))
|
|
0
|
705 {
|
|
|
706 CHECK_NATNUM (size);
|
|
|
707 return make_lisp_hashtable (XINT (size), HASHTABLE_NONWEAK,
|
|
|
708 decode_hashtable_test_fun (test_fun));
|
|
|
709 }
|
|
|
710
|
|
20
|
711 DEFUN ("copy-hashtable", Fcopy_hashtable, 1, 1, 0, /*
|
|
0
|
712 Make a new hashtable which contains the same keys and values
|
|
|
713 as the given table. The keys and values will not themselves be copied.
|
|
20
|
714 */
|
|
|
715 (old_table))
|
|
0
|
716 {
|
|
|
717 struct _C_hashtable old_htbl;
|
|
|
718 struct _C_hashtable new_htbl;
|
|
185
|
719 struct hashtable *old_ht;
|
|
|
720 struct hashtable *new_ht;
|
|
0
|
721 Lisp_Object result;
|
|
|
722
|
|
|
723 CHECK_HASHTABLE (old_table);
|
|
|
724 old_ht = XHASHTABLE (old_table);
|
|
|
725 ht_copy_to_c (old_ht, &old_htbl);
|
|
|
726
|
|
|
727 /* we can't just call Fmake_hashtable() here because that will make a
|
|
|
728 table that is slightly larger than the one we're trying to copy,
|
|
|
729 which will make copy_hash() blow up. */
|
|
|
730 new_ht = allocate_hashtable ();
|
|
|
731 new_ht->fullness = 0;
|
|
|
732 new_ht->zero_entry = Qunbound;
|
|
|
733 new_ht->hash_function = old_ht->hash_function;
|
|
|
734 new_ht->test_function = old_ht->test_function;
|
|
207
|
735 new_ht->harray = Fmake_vector (Flength (old_ht->harray), Qnull_pointer);
|
|
0
|
736 ht_copy_to_c (new_ht, &new_htbl);
|
|
|
737 copy_hash (&new_htbl, &old_htbl);
|
|
|
738 ht_copy_from_c (&new_htbl, new_ht);
|
|
|
739 new_ht->type = old_ht->type;
|
|
|
740 XSETHASHTABLE (result, new_ht);
|
|
|
741
|
|
|
742 if (UNBOUNDP (old_ht->next_weak))
|
|
|
743 new_ht->next_weak = Qunbound;
|
|
|
744 else
|
|
|
745 {
|
|
|
746 new_ht->next_weak = Vall_weak_hashtables;
|
|
|
747 Vall_weak_hashtables = result;
|
|
|
748 }
|
|
|
749
|
|
173
|
750 return result;
|
|
0
|
751 }
|
|
|
752
|
|
|
753
|
|
20
|
754 DEFUN ("gethash", Fgethash, 2, 3, 0, /*
|
|
187
|
755 Find hash value for KEY in HASHTABLE.
|
|
0
|
756 If there is no corresponding value, return DEFAULT (defaults to nil).
|
|
20
|
757 */
|
|
187
|
758 (key, hashtable, default_))
|
|
0
|
759 {
|
|
|
760 CONST void *vval;
|
|
|
761 struct _C_hashtable htbl;
|
|
|
762 if (!gc_in_progress)
|
|
187
|
763 CHECK_HASHTABLE (hashtable);
|
|
|
764 ht_copy_to_c (XHASHTABLE (hashtable), &htbl);
|
|
0
|
765 if (gethash (LISP_TO_VOID (key), &htbl, &vval))
|
|
|
766 {
|
|
|
767 Lisp_Object val;
|
|
|
768 CVOID_TO_LISP (val, vval);
|
|
|
769 return val;
|
|
|
770 }
|
|
185
|
771 else
|
|
173
|
772 return default_;
|
|
0
|
773 }
|
|
|
774
|
|
|
775
|
|
20
|
776 DEFUN ("remhash", Fremhash, 2, 2, 0, /*
|
|
187
|
777 Remove hash value for KEY in HASHTABLE.
|
|
20
|
778 */
|
|
187
|
779 (key, hashtable))
|
|
0
|
780 {
|
|
|
781 struct _C_hashtable htbl;
|
|
187
|
782 CHECK_HASHTABLE (hashtable);
|
|
0
|
783
|
|
187
|
784 ht_copy_to_c (XHASHTABLE (hashtable), &htbl);
|
|
0
|
785 remhash (LISP_TO_VOID (key), &htbl);
|
|
187
|
786 ht_copy_from_c (&htbl, XHASHTABLE (hashtable));
|
|
0
|
787 return Qnil;
|
|
|
788 }
|
|
|
789
|
|
|
790
|
|
20
|
791 DEFUN ("puthash", Fputhash, 3, 3, 0, /*
|
|
187
|
792 Hash KEY to VAL in HASHTABLE.
|
|
20
|
793 */
|
|
187
|
794 (key, val, hashtable))
|
|
0
|
795 {
|
|
185
|
796 struct hashtable *ht;
|
|
0
|
797 void *vkey = LISP_TO_VOID (key);
|
|
|
798
|
|
187
|
799 CHECK_HASHTABLE (hashtable);
|
|
|
800 ht = XHASHTABLE (hashtable);
|
|
0
|
801 if (!vkey)
|
|
|
802 ht->zero_entry = val;
|
|
|
803 else
|
|
|
804 {
|
|
|
805 struct gcpro gcpro1, gcpro2, gcpro3;
|
|
|
806 struct _C_hashtable htbl;
|
|
|
807
|
|
187
|
808 ht_copy_to_c (XHASHTABLE (hashtable), &htbl);
|
|
|
809 GCPRO3 (key, val, hashtable);
|
|
0
|
810 puthash (vkey, LISP_TO_VOID (val), &htbl);
|
|
187
|
811 ht_copy_from_c (&htbl, XHASHTABLE (hashtable));
|
|
0
|
812 UNGCPRO;
|
|
|
813 }
|
|
173
|
814 return val;
|
|
0
|
815 }
|
|
|
816
|
|
20
|
817 DEFUN ("clrhash", Fclrhash, 1, 1, 0, /*
|
|
187
|
818 Remove all entries from HASHTABLE.
|
|
20
|
819 */
|
|
187
|
820 (hashtable))
|
|
0
|
821 {
|
|
|
822 struct _C_hashtable htbl;
|
|
187
|
823 CHECK_HASHTABLE (hashtable);
|
|
|
824 ht_copy_to_c (XHASHTABLE (hashtable), &htbl);
|
|
0
|
825 clrhash (&htbl);
|
|
187
|
826 ht_copy_from_c (&htbl, XHASHTABLE (hashtable));
|
|
0
|
827 return Qnil;
|
|
|
828 }
|
|
|
829
|
|
20
|
830 DEFUN ("hashtable-fullness", Fhashtable_fullness, 1, 1, 0, /*
|
|
187
|
831 Return number of entries in HASHTABLE.
|
|
20
|
832 */
|
|
187
|
833 (hashtable))
|
|
0
|
834 {
|
|
|
835 struct _C_hashtable htbl;
|
|
187
|
836 CHECK_HASHTABLE (hashtable);
|
|
|
837 ht_copy_to_c (XHASHTABLE (hashtable), &htbl);
|
|
173
|
838 return make_int (htbl.fullness);
|
|
0
|
839 }
|
|
|
840
|
|
|
841
|
|
|
842 static void
|
|
|
843 verify_function (Lisp_Object function, CONST char *description)
|
|
|
844 {
|
|
223
|
845 /* #### Unused DESCRIPTION? */
|
|
0
|
846 if (SYMBOLP (function))
|
|
|
847 {
|
|
|
848 if (NILP (function))
|
|
|
849 return;
|
|
|
850 else
|
|
|
851 function = indirect_function (function, 1);
|
|
|
852 }
|
|
|
853 if (SUBRP (function) || COMPILED_FUNCTIONP (function))
|
|
|
854 return;
|
|
|
855 else if (CONSP (function))
|
|
|
856 {
|
|
223
|
857 Lisp_Object funcar = XCAR (function);
|
|
187
|
858 if ((SYMBOLP (funcar)) && (EQ (funcar, Qlambda) ||
|
|
|
859 EQ (funcar, Qautoload)))
|
|
0
|
860 return;
|
|
|
861 }
|
|
|
862 signal_error (Qinvalid_function, list1 (function));
|
|
|
863 }
|
|
|
864
|
|
241
|
865 static int
|
|
0
|
866 lisp_maphash_function (CONST void *void_key,
|
|
|
867 void *void_val,
|
|
|
868 void *void_fn)
|
|
|
869 {
|
|
|
870 /* This function can GC */
|
|
|
871 Lisp_Object key, val, fn;
|
|
|
872 CVOID_TO_LISP (key, void_key);
|
|
|
873 VOID_TO_LISP (val, void_val);
|
|
|
874 VOID_TO_LISP (fn, void_fn);
|
|
|
875 call2 (fn, key, val);
|
|
241
|
876 return 0;
|
|
0
|
877 }
|
|
|
878
|
|
|
879
|
|
20
|
880 DEFUN ("maphash", Fmaphash, 2, 2, 0, /*
|
|
187
|
881 Map FUNCTION over entries in HASHTABLE, calling it with two args,
|
|
0
|
882 each key and value in the table.
|
|
20
|
883 */
|
|
187
|
884 (function, hashtable))
|
|
0
|
885 {
|
|
|
886 struct _C_hashtable htbl;
|
|
|
887 struct gcpro gcpro1, gcpro2;
|
|
|
888
|
|
|
889 verify_function (function, GETTEXT ("hashtable mapping function"));
|
|
187
|
890 CHECK_HASHTABLE (hashtable);
|
|
|
891 ht_copy_to_c (XHASHTABLE (hashtable), &htbl);
|
|
|
892 GCPRO2 (hashtable, function);
|
|
0
|
893 maphash (lisp_maphash_function, &htbl, LISP_TO_VOID (function));
|
|
|
894 UNGCPRO;
|
|
|
895 return Qnil;
|
|
|
896 }
|
|
|
897
|
|
|
898
|
|
|
899 /* This function is for mapping a *C* function over the elements of a
|
|
|
900 lisp hashtable.
|
|
|
901 */
|
|
|
902 void
|
|
241
|
903 elisp_maphash (void (*function) (CONST void *key, void *contents,
|
|
|
904 void *extra_arg),
|
|
|
905 Lisp_Object hashtable, void *closure)
|
|
0
|
906 {
|
|
|
907 struct _C_hashtable htbl;
|
|
|
908
|
|
187
|
909 if (!gc_in_progress) CHECK_HASHTABLE (hashtable);
|
|
|
910 ht_copy_to_c (XHASHTABLE (hashtable), &htbl);
|
|
0
|
911 maphash (function, &htbl, closure);
|
|
|
912 }
|
|
|
913
|
|
|
914 void
|
|
241
|
915 elisp_map_remhash (int (*function) (CONST void *key,
|
|
|
916 CONST void *contents,
|
|
|
917 void *extra_arg),
|
|
|
918 Lisp_Object hashtable,
|
|
187
|
919 void *closure)
|
|
0
|
920 {
|
|
|
921 struct _C_hashtable htbl;
|
|
|
922
|
|
187
|
923 if (!gc_in_progress) CHECK_HASHTABLE (hashtable);
|
|
|
924 ht_copy_to_c (XHASHTABLE (hashtable), &htbl);
|
|
0
|
925 map_remhash (function, &htbl, closure);
|
|
187
|
926 ht_copy_from_c (&htbl, XHASHTABLE (hashtable));
|
|
0
|
927 }
|
|
|
928
|
|
|
929 #if 0
|
|
|
930 void
|
|
|
931 elisp_table_op (Lisp_Object table, generic_hashtable_op op, void *arg1,
|
|
|
932 void *arg2, void *arg3)
|
|
|
933 {
|
|
|
934 struct _C_hashtable htbl;
|
|
|
935 CHECK_HASHTABLE (table);
|
|
|
936 ht_copy_to_c (XHASHTABLE (table), &htbl);
|
|
|
937 (*op) (&htbl, arg1, arg2, arg3);
|
|
|
938 ht_copy_from_c (&htbl, XHASHTABLE (table));
|
|
|
939 }
|
|
|
940 #endif /* 0 */
|
|
|
941
|
|
|
942
|
|
|
943
|
|
20
|
944 DEFUN ("make-weak-hashtable", Fmake_weak_hashtable, 1, 2, 0, /*
|
|
0
|
945 Make a fully weak hashtable of initial size SIZE.
|
|
|
946 A weak hashtable is one whose pointers do not count as GC referents:
|
|
|
947 for any key-value pair in the hashtable, if the only remaining pointer
|
|
|
948 to either the key or the value is in a weak hash table, then the pair
|
|
|
949 will be removed from the table, and the key and value collected. A
|
|
|
950 non-weak hash table (or any other pointer) would prevent the object
|
|
|
951 from being collected.
|
|
|
952
|
|
|
953 You can also create semi-weak hashtables; see `make-key-weak-hashtable'
|
|
|
954 and `make-value-weak-hashtable'.
|
|
20
|
955 */
|
|
|
956 (size, test_fun))
|
|
0
|
957 {
|
|
|
958 CHECK_NATNUM (size);
|
|
|
959 return make_lisp_hashtable (XINT (size), HASHTABLE_WEAK,
|
|
|
960 decode_hashtable_test_fun (test_fun));
|
|
|
961 }
|
|
|
962
|
|
20
|
963 DEFUN ("make-key-weak-hashtable", Fmake_key_weak_hashtable, 1, 2, 0, /*
|
|
0
|
964 Make a key-weak hashtable of initial size SIZE.
|
|
|
965 A key-weak hashtable is similar to a fully-weak hashtable (see
|
|
|
966 `make-weak-hashtable') except that a key-value pair will be removed
|
|
|
967 only if the key remains unmarked outside of weak hashtables. The pair
|
|
|
968 will remain in the hashtable if the key is pointed to by something other
|
|
|
969 than a weak hashtable, even if the value is not.
|
|
20
|
970 */
|
|
|
971 (size, test_fun))
|
|
0
|
972 {
|
|
|
973 CHECK_NATNUM (size);
|
|
|
974 return make_lisp_hashtable (XINT (size), HASHTABLE_KEY_WEAK,
|
|
|
975 decode_hashtable_test_fun (test_fun));
|
|
|
976 }
|
|
|
977
|
|
20
|
978 DEFUN ("make-value-weak-hashtable", Fmake_value_weak_hashtable, 1, 2, 0, /*
|
|
0
|
979 Make a value-weak hashtable of initial size SIZE.
|
|
|
980 A value-weak hashtable is similar to a fully-weak hashtable (see
|
|
|
981 `make-weak-hashtable') except that a key-value pair will be removed only
|
|
|
982 if the value remains unmarked outside of weak hashtables. The pair will
|
|
|
983 remain in the hashtable if the value is pointed to by something other
|
|
|
984 than a weak hashtable, even if the key is not.
|
|
20
|
985 */
|
|
|
986 (size, test_fun))
|
|
0
|
987 {
|
|
|
988 CHECK_NATNUM (size);
|
|
|
989 return make_lisp_hashtable (XINT (size), HASHTABLE_VALUE_WEAK,
|
|
|
990 decode_hashtable_test_fun (test_fun));
|
|
|
991 }
|
|
|
992
|
|
|
993 struct marking_closure
|
|
|
994 {
|
|
|
995 int (*obj_marked_p) (Lisp_Object);
|
|
|
996 void (*markobj) (Lisp_Object);
|
|
|
997 enum hashtable_type type;
|
|
|
998 int did_mark;
|
|
|
999 };
|
|
|
1000
|
|
241
|
1001 static int
|
|
0
|
1002 marking_mapper (CONST void *key, void *contents, void *closure)
|
|
|
1003 {
|
|
|
1004 Lisp_Object keytem, valuetem;
|
|
|
1005 struct marking_closure *fmh =
|
|
|
1006 (struct marking_closure *) closure;
|
|
|
1007
|
|
|
1008 /* This function is called over each pair in the hashtable.
|
|
|
1009 We complete the marking for semi-weak hashtables. */
|
|
|
1010 CVOID_TO_LISP (keytem, key);
|
|
|
1011 CVOID_TO_LISP (valuetem, contents);
|
|
185
|
1012
|
|
0
|
1013 switch (fmh->type)
|
|
|
1014 {
|
|
|
1015 case HASHTABLE_KEY_WEAK:
|
|
|
1016 if ((fmh->obj_marked_p) (keytem) &&
|
|
|
1017 !(fmh->obj_marked_p) (valuetem))
|
|
|
1018 {
|
|
|
1019 (fmh->markobj) (valuetem);
|
|
|
1020 fmh->did_mark = 1;
|
|
|
1021 }
|
|
|
1022 break;
|
|
|
1023
|
|
|
1024 case HASHTABLE_VALUE_WEAK:
|
|
|
1025 if ((fmh->obj_marked_p) (valuetem) &&
|
|
|
1026 !(fmh->obj_marked_p) (keytem))
|
|
|
1027 {
|
|
|
1028 (fmh->markobj) (keytem);
|
|
|
1029 fmh->did_mark = 1;
|
|
|
1030 }
|
|
|
1031 break;
|
|
|
1032
|
|
|
1033 case HASHTABLE_KEY_CAR_WEAK:
|
|
|
1034 if (!CONSP (keytem) || (fmh->obj_marked_p) (XCAR (keytem)))
|
|
|
1035 {
|
|
|
1036 if (!(fmh->obj_marked_p) (keytem))
|
|
|
1037 {
|
|
|
1038 (fmh->markobj) (keytem);
|
|
|
1039 fmh->did_mark = 1;
|
|
|
1040 }
|
|
|
1041 if (!(fmh->obj_marked_p) (valuetem))
|
|
|
1042 {
|
|
|
1043 (fmh->markobj) (valuetem);
|
|
|
1044 fmh->did_mark = 1;
|
|
|
1045 }
|
|
|
1046 }
|
|
|
1047 break;
|
|
|
1048
|
|
|
1049 case HASHTABLE_VALUE_CAR_WEAK:
|
|
|
1050 if (!CONSP (valuetem) || (fmh->obj_marked_p) (XCAR (valuetem)))
|
|
|
1051 {
|
|
|
1052 if (!(fmh->obj_marked_p) (keytem))
|
|
|
1053 {
|
|
|
1054 (fmh->markobj) (keytem);
|
|
|
1055 fmh->did_mark = 1;
|
|
|
1056 }
|
|
|
1057 if (!(fmh->obj_marked_p) (valuetem))
|
|
|
1058 {
|
|
|
1059 (fmh->markobj) (valuetem);
|
|
|
1060 fmh->did_mark = 1;
|
|
|
1061 }
|
|
|
1062 }
|
|
|
1063 break;
|
|
|
1064
|
|
|
1065 default:
|
|
|
1066 abort (); /* Huh? */
|
|
|
1067 }
|
|
185
|
1068
|
|
241
|
1069 return 0;
|
|
0
|
1070 }
|
|
|
1071
|
|
|
1072 int
|
|
|
1073 finish_marking_weak_hashtables (int (*obj_marked_p) (Lisp_Object),
|
|
|
1074 void (*markobj) (Lisp_Object))
|
|
|
1075 {
|
|
|
1076 Lisp_Object rest;
|
|
|
1077 int did_mark = 0;
|
|
|
1078
|
|
|
1079 for (rest = Vall_weak_hashtables;
|
|
|
1080 !GC_NILP (rest);
|
|
|
1081 rest = XHASHTABLE (rest)->next_weak)
|
|
|
1082 {
|
|
|
1083 enum hashtable_type type;
|
|
|
1084
|
|
|
1085 if (! ((*obj_marked_p) (rest)))
|
|
|
1086 /* The hashtable is probably garbage. Ignore it. */
|
|
|
1087 continue;
|
|
|
1088 type = XHASHTABLE (rest)->type;
|
|
187
|
1089 if (type == HASHTABLE_KEY_WEAK ||
|
|
|
1090 type == HASHTABLE_VALUE_WEAK ||
|
|
|
1091 type == HASHTABLE_KEY_CAR_WEAK ||
|
|
|
1092 type == HASHTABLE_VALUE_CAR_WEAK)
|
|
0
|
1093 {
|
|
|
1094 struct marking_closure fmh;
|
|
|
1095
|
|
|
1096 fmh.obj_marked_p = obj_marked_p;
|
|
|
1097 fmh.markobj = markobj;
|
|
|
1098 fmh.type = type;
|
|
|
1099 fmh.did_mark = 0;
|
|
|
1100 /* Now, scan over all the pairs. For all pairs that are
|
|
|
1101 half-marked, we may need to mark the other half if we're
|
|
|
1102 keeping this pair. */
|
|
|
1103 elisp_maphash (marking_mapper, rest, &fmh);
|
|
|
1104 if (fmh.did_mark)
|
|
|
1105 did_mark = 1;
|
|
|
1106 }
|
|
|
1107
|
|
|
1108 /* #### If alloc.c mark_object changes, this must change also... */
|
|
|
1109 {
|
|
|
1110 /* Now mark the vector itself. (We don't need to call markobj
|
|
|
1111 here because we know that everything *in* it is already marked,
|
|
|
1112 we just need to prevent the vector itself from disappearing.)
|
|
|
1113 (The remhash above has taken care of zero_entry.)
|
|
|
1114 */
|
|
|
1115 struct Lisp_Vector *ptr = XVECTOR (XHASHTABLE (rest)->harray);
|
|
207
|
1116 #ifdef LRECORD_VECTOR
|
|
|
1117 if (! MARKED_RECORD_P(XHASHTABLE(rest)->harray))
|
|
|
1118 {
|
|
|
1119 MARK_RECORD_HEADER(&(ptr->header.lheader));
|
|
|
1120 did_mark = 1;
|
|
|
1121 }
|
|
|
1122 #else
|
|
223
|
1123 int len = vector_length (ptr);
|
|
0
|
1124 if (len >= 0)
|
|
|
1125 {
|
|
|
1126 ptr->size = -1 - len;
|
|
|
1127 did_mark = 1;
|
|
|
1128 }
|
|
207
|
1129 #endif
|
|
0
|
1130 /* else it's already marked (remember, this function is iterated
|
|
|
1131 until marking stops) */
|
|
|
1132 }
|
|
|
1133 }
|
|
|
1134
|
|
|
1135 return did_mark;
|
|
|
1136 }
|
|
|
1137
|
|
|
1138 struct pruning_closure
|
|
|
1139 {
|
|
|
1140 int (*obj_marked_p) (Lisp_Object);
|
|
|
1141 };
|
|
|
1142
|
|
|
1143 static int
|
|
|
1144 pruning_mapper (CONST void *key, CONST void *contents, void *closure)
|
|
|
1145 {
|
|
|
1146 Lisp_Object keytem, valuetem;
|
|
185
|
1147 struct pruning_closure *fmh = (struct pruning_closure *) closure;
|
|
0
|
1148
|
|
|
1149 /* This function is called over each pair in the hashtable.
|
|
|
1150 We remove the pairs that aren't completely marked (everything
|
|
|
1151 that is going to stay ought to have been marked already
|
|
|
1152 by the finish_marking stage). */
|
|
|
1153 CVOID_TO_LISP (keytem, key);
|
|
|
1154 CVOID_TO_LISP (valuetem, contents);
|
|
|
1155
|
|
173
|
1156 return ! ((*fmh->obj_marked_p) (keytem) &&
|
|
|
1157 (*fmh->obj_marked_p) (valuetem));
|
|
0
|
1158 }
|
|
|
1159
|
|
|
1160 void
|
|
|
1161 prune_weak_hashtables (int (*obj_marked_p) (Lisp_Object))
|
|
|
1162 {
|
|
|
1163 Lisp_Object rest, prev = Qnil;
|
|
|
1164 for (rest = Vall_weak_hashtables;
|
|
|
1165 !GC_NILP (rest);
|
|
|
1166 rest = XHASHTABLE (rest)->next_weak)
|
|
|
1167 {
|
|
|
1168 if (! ((*obj_marked_p) (rest)))
|
|
|
1169 {
|
|
|
1170 /* This table itself is garbage. Remove it from the list. */
|
|
|
1171 if (GC_NILP (prev))
|
|
|
1172 Vall_weak_hashtables = XHASHTABLE (rest)->next_weak;
|
|
|
1173 else
|
|
|
1174 XHASHTABLE (prev)->next_weak = XHASHTABLE (rest)->next_weak;
|
|
|
1175 }
|
|
|
1176 else
|
|
|
1177 {
|
|
|
1178 struct pruning_closure fmh;
|
|
|
1179 fmh.obj_marked_p = obj_marked_p;
|
|
|
1180 /* Now, scan over all the pairs. Remove all of the pairs
|
|
|
1181 in which the key or value, or both, is unmarked
|
|
|
1182 (depending on the type of weak hashtable). */
|
|
|
1183 elisp_map_remhash (pruning_mapper, rest, &fmh);
|
|
|
1184 prev = rest;
|
|
|
1185 }
|
|
|
1186 }
|
|
|
1187 }
|
|
|
1188
|
|
|
1189 /* Return a hash value for an array of Lisp_Objects of size SIZE. */
|
|
|
1190
|
|
|
1191 unsigned long
|
|
|
1192 internal_array_hash (Lisp_Object *arr, int size, int depth)
|
|
|
1193 {
|
|
|
1194 int i;
|
|
|
1195 unsigned long hash = 0;
|
|
|
1196
|
|
|
1197 if (size <= 5)
|
|
|
1198 {
|
|
|
1199 for (i = 0; i < size; i++)
|
|
|
1200 hash = HASH2 (hash, internal_hash (arr[i], depth + 1));
|
|
|
1201 return hash;
|
|
|
1202 }
|
|
185
|
1203
|
|
0
|
1204 /* just pick five elements scattered throughout the array.
|
|
|
1205 A slightly better approach would be to offset by some
|
|
|
1206 noise factor from the points chosen below. */
|
|
|
1207 for (i = 0; i < 5; i++)
|
|
|
1208 hash = HASH2 (hash, internal_hash (arr[i*size/5], depth + 1));
|
|
185
|
1209
|
|
0
|
1210 return hash;
|
|
|
1211 }
|
|
|
1212
|
|
|
1213 /* Return a hash value for a Lisp_Object. This is for use when hashing
|
|
|
1214 objects with the comparison being `equal' (for `eq', you can just
|
|
|
1215 use the Lisp_Object itself as the hash value). You need to make a
|
|
|
1216 tradeoff between the speed of the hash function and how good the
|
|
|
1217 hashing is. In particular, the hash function needs to be FAST,
|
|
|
1218 so you can't just traipse down the whole tree hashing everything
|
|
|
1219 together. Most of the time, objects will differ in the first
|
|
|
1220 few elements you hash. Thus, we only go to a short depth (5)
|
|
|
1221 and only hash at most 5 elements out of a vector. Theoretically
|
|
|
1222 we could still take 5^5 time (a big big number) to compute a
|
|
|
1223 hash, but practically this won't ever happen. */
|
|
|
1224
|
|
|
1225 unsigned long
|
|
|
1226 internal_hash (Lisp_Object obj, int depth)
|
|
|
1227 {
|
|
|
1228 if (depth > 5)
|
|
|
1229 return 0;
|
|
|
1230 if (CONSP (obj))
|
|
|
1231 {
|
|
|
1232 /* no point in worrying about tail recursion, since we're not
|
|
|
1233 going very deep */
|
|
|
1234 return HASH2 (internal_hash (XCAR (obj), depth + 1),
|
|
|
1235 internal_hash (XCDR (obj), depth + 1));
|
|
|
1236 }
|
|
|
1237 else if (STRINGP (obj))
|
|
14
|
1238 return hash_string (XSTRING_DATA (obj), XSTRING_LENGTH (obj));
|
|
0
|
1239 else if (VECTORP (obj))
|
|
|
1240 {
|
|
|
1241 struct Lisp_Vector *v = XVECTOR (obj);
|
|
|
1242 return HASH2 (vector_length (v),
|
|
|
1243 internal_array_hash (v->contents, vector_length (v),
|
|
|
1244 depth + 1));
|
|
|
1245 }
|
|
|
1246 else if (LRECORDP (obj))
|
|
|
1247 {
|
|
|
1248 CONST struct lrecord_implementation
|
|
211
|
1249 *imp = XRECORD_LHEADER_IMPLEMENTATION (obj);
|
|
0
|
1250 if (imp->hash)
|
|
173
|
1251 return (imp->hash) (obj, depth);
|
|
0
|
1252 }
|
|
|
1253
|
|
|
1254 return LISP_HASH (obj);
|
|
|
1255 }
|
|
|
1256
|
|
241
|
1257 #if 0
|
|
|
1258 xxDEFUN ("internal-hash-value", Finternal_hash_value, 1, 1, 0, /*
|
|
|
1259 Hash value of OBJECT. For debugging.
|
|
|
1260 The value is returned as (HIGH . LOW).
|
|
|
1261 */
|
|
|
1262 (object))
|
|
|
1263 {
|
|
|
1264 /* This function is pretty 32bit-centric. */
|
|
|
1265 unsigned long hash = internal_hash (object, 0);
|
|
|
1266 return Fcons (hash >> 16, hash & 0xffff);
|
|
|
1267 }
|
|
|
1268 #endif
|
|
|
1269
|
|
0
|
1270
|
|
|
1271 /************************************************************************/
|
|
|
1272 /* initialization */
|
|
|
1273 /************************************************************************/
|
|
|
1274
|
|
|
1275 void
|
|
|
1276 syms_of_elhash (void)
|
|
|
1277 {
|
|
20
|
1278 DEFSUBR (Fmake_hashtable);
|
|
|
1279 DEFSUBR (Fcopy_hashtable);
|
|
|
1280 DEFSUBR (Fhashtablep);
|
|
|
1281 DEFSUBR (Fgethash);
|
|
|
1282 DEFSUBR (Fputhash);
|
|
|
1283 DEFSUBR (Fremhash);
|
|
|
1284 DEFSUBR (Fclrhash);
|
|
|
1285 DEFSUBR (Fmaphash);
|
|
|
1286 DEFSUBR (Fhashtable_fullness);
|
|
|
1287 DEFSUBR (Fmake_weak_hashtable);
|
|
|
1288 DEFSUBR (Fmake_key_weak_hashtable);
|
|
|
1289 DEFSUBR (Fmake_value_weak_hashtable);
|
|
241
|
1290 #if 0
|
|
|
1291 DEFSUBR (Finternal_hash_value);
|
|
|
1292 #endif
|
|
0
|
1293 defsymbol (&Qhashtablep, "hashtablep");
|
|
223
|
1294 defsymbol (&Qhashtable, "hashtable");
|
|
|
1295 defsymbol (&Qweak, "weak");
|
|
|
1296 defsymbol (&Qkey_weak, "key-weak");
|
|
|
1297 defsymbol (&Qvalue_weak, "value-weak");
|
|
|
1298 defsymbol (&Qnon_weak, "non-weak");
|
|
0
|
1299 }
|
|
|
1300
|
|
|
1301 void
|
|
|
1302 vars_of_elhash (void)
|
|
|
1303 {
|
|
2
|
1304 /* This must NOT be staticpro'd */
|
|
0
|
1305 Vall_weak_hashtables = Qnil;
|
|
|
1306 }
|
