Commit | Line | Data |
---|---|---|
fb8b2a9d LC |
1 | /* Copyright (C) 1995, 1996, 1998, 1999, 2000, 2001, 2003, 2004, 2006, |
2 | * 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc. | |
3 | * | |
73be1d9e | 4 | * This library is free software; you can redistribute it and/or |
53befeb7 NJ |
5 | * modify it under the terms of the GNU Lesser General Public License |
6 | * as published by the Free Software Foundation; either version 3 of | |
7 | * the License, or (at your option) any later version. | |
0f2d19dd | 8 | * |
53befeb7 NJ |
9 | * This library is distributed in the hope that it will be useful, but |
10 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
73be1d9e MV |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | * Lesser General Public License for more details. | |
0f2d19dd | 13 | * |
73be1d9e MV |
14 | * You should have received a copy of the GNU Lesser General Public |
15 | * License along with this library; if not, write to the Free Software | |
53befeb7 NJ |
16 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
17 | * 02110-1301 USA | |
73be1d9e | 18 | */ |
1bbd0b84 | 19 | |
1bbd0b84 | 20 | |
0f2d19dd | 21 | \f |
dbb605f5 LC |
22 | #ifdef HAVE_CONFIG_H |
23 | # include <config.h> | |
24 | #endif | |
0f2d19dd | 25 | |
cdd47ec7 | 26 | #include <alloca.h> |
06c1d900 | 27 | #include <stdio.h> |
63229905 | 28 | #include <assert.h> |
06c1d900 | 29 | |
a0599745 MD |
30 | #include "libguile/_scm.h" |
31 | #include "libguile/alist.h" | |
32 | #include "libguile/hash.h" | |
33 | #include "libguile/eval.h" | |
fdc28395 | 34 | #include "libguile/root.h" |
a0599745 | 35 | #include "libguile/vectors.h" |
f59a096e | 36 | #include "libguile/ports.h" |
62c290e9 | 37 | #include "libguile/bdw-gc.h" |
a0599745 MD |
38 | |
39 | #include "libguile/validate.h" | |
40 | #include "libguile/hashtab.h" | |
e4d21e6b | 41 | |
e4d21e6b | 42 | |
0f2d19dd JB |
43 | \f |
44 | ||
c99de5aa | 45 | /* A hash table is a cell containing a vector of association lists. |
c35738c1 MD |
46 | * |
47 | * Growing or shrinking, with following rehashing, is triggered when | |
48 | * the load factor | |
49 | * | |
50 | * L = N / S (N: number of items in table, S: bucket vector length) | |
51 | * | |
52 | * passes an upper limit of 0.9 or a lower limit of 0.25. | |
53 | * | |
54 | * The implementation stores the upper and lower number of items which | |
55 | * trigger a resize in the hashtable object. | |
56 | * | |
328255e4 AW |
57 | * Weak hash tables use weak pairs in the bucket lists rather than |
58 | * normal pairs. | |
59 | * | |
c35738c1 MD |
60 | * Possible hash table sizes (primes) are stored in the array |
61 | * hashtable_size. | |
f59a096e MD |
62 | */ |
63 | ||
0a4c1355 MD |
64 | static unsigned long hashtable_size[] = { |
65 | 31, 61, 113, 223, 443, 883, 1759, 3517, 7027, 14051, 28099, 56197, 112363, | |
93777082 | 66 | 224717, 449419, 898823, 1797641, 3595271, 7190537, 14381041 |
328255e4 AW |
67 | #if SIZEOF_SCM_T_BITS > 4 |
68 | /* vector lengths are stored in the first word of vectors, shifted by | |
69 | 8 bits for the tc8, so for 32-bit we only get 2^24-1 = 16777215 | |
70 | elements. But we allow a few more sizes for 64-bit. */ | |
71 | , 28762081, 57524111, 115048217, 230096423, 460192829 | |
93777082 | 72 | #endif |
f59a096e MD |
73 | }; |
74 | ||
93777082 MV |
75 | #define HASHTABLE_SIZE_N (sizeof(hashtable_size)/sizeof(unsigned long)) |
76 | ||
f59a096e MD |
77 | static char *s_hashtable = "hashtable"; |
78 | ||
e4d21e6b | 79 | |
3a2de079 | 80 | \f |
986ec822 | 81 | /* Helper functions and macros to deal with weak pairs. |
3a2de079 | 82 | |
986ec822 LC |
83 | Weak pairs need to be accessed very carefully since their components can |
84 | be nullified by the GC when the object they refer to becomes unreachable. | |
85 | Hence the macros and functions below that detect such weak pairs within | |
86 | buckets and remove them. */ | |
3a2de079 LC |
87 | |
88 | ||
63229905 LC |
89 | /* Remove nullified weak pairs from ALIST such that the result contains only |
90 | valid pairs. Set REMOVED_ITEMS to the number of pairs that have been | |
d9c82e20 | 91 | deleted. */ |
3a2de079 | 92 | static SCM |
d9c82e20 | 93 | scm_fixup_weak_alist (SCM alist, size_t *removed_items) |
3a2de079 LC |
94 | { |
95 | SCM result; | |
96 | SCM prev = SCM_EOL; | |
97 | ||
d9c82e20 | 98 | *removed_items = 0; |
3a2de079 LC |
99 | for (result = alist; |
100 | scm_is_pair (alist); | |
dff58577 | 101 | alist = SCM_CDR (alist)) |
3a2de079 LC |
102 | { |
103 | SCM pair = SCM_CAR (alist); | |
104 | ||
dff58577 | 105 | if (SCM_WEAK_PAIR_DELETED_P (pair)) |
3a2de079 | 106 | { |
dff58577 LC |
107 | /* Remove from ALIST weak pair PAIR whose car/cdr has been |
108 | nullified by the GC. */ | |
393baa8a | 109 | if (scm_is_null (prev)) |
dff58577 LC |
110 | result = SCM_CDR (alist); |
111 | else | |
112 | SCM_SETCDR (prev, SCM_CDR (alist)); | |
113 | ||
114 | (*removed_items)++; | |
115 | ||
116 | /* Leave PREV unchanged. */ | |
3a2de079 | 117 | } |
dff58577 LC |
118 | else |
119 | prev = alist; | |
3a2de079 LC |
120 | } |
121 | ||
122 | return result; | |
123 | } | |
124 | ||
40d2a007 AW |
125 | static void |
126 | vacuum_weak_hash_table (SCM table) | |
127 | { | |
128 | SCM buckets = SCM_HASHTABLE_VECTOR (table); | |
129 | unsigned long k = SCM_SIMPLE_VECTOR_LENGTH (buckets); | |
130 | size_t len = SCM_HASHTABLE_N_ITEMS (table); | |
131 | ||
132 | while (k--) | |
133 | { | |
134 | size_t removed; | |
135 | SCM alist = SCM_SIMPLE_VECTOR_REF (buckets, k); | |
136 | alist = scm_fixup_weak_alist (alist, &removed); | |
137 | assert (removed <= len); | |
138 | len -= removed; | |
139 | SCM_SIMPLE_VECTOR_SET (buckets, k, alist); | |
140 | } | |
141 | ||
142 | SCM_SET_HASHTABLE_N_ITEMS (table, len); | |
143 | } | |
144 | ||
d9c82e20 | 145 | |
e9bac3be LC |
146 | /* Packed arguments for `do_weak_bucket_fixup'. */ |
147 | struct t_fixup_args | |
63229905 | 148 | { |
e9bac3be LC |
149 | SCM bucket; |
150 | SCM *bucket_copy; | |
63229905 LC |
151 | size_t removed_items; |
152 | }; | |
153 | ||
154 | static void * | |
e9bac3be | 155 | do_weak_bucket_fixup (void *data) |
63229905 | 156 | { |
e9bac3be LC |
157 | struct t_fixup_args *args; |
158 | SCM pair, *copy; | |
63229905 | 159 | |
e9bac3be | 160 | args = (struct t_fixup_args *) data; |
c6a35e35 | 161 | |
e9bac3be | 162 | args->bucket = scm_fixup_weak_alist (args->bucket, &args->removed_items); |
63229905 | 163 | |
e9bac3be LC |
164 | for (pair = args->bucket, copy = args->bucket_copy; |
165 | scm_is_pair (pair); | |
166 | pair = SCM_CDR (pair), copy += 2) | |
167 | { | |
168 | /* At this point, all weak pairs have been removed. */ | |
169 | assert (!SCM_WEAK_PAIR_DELETED_P (SCM_CAR (pair))); | |
63229905 | 170 | |
e9bac3be LC |
171 | /* Copy the key and value. */ |
172 | copy[0] = SCM_CAAR (pair); | |
173 | copy[1] = SCM_CDAR (pair); | |
174 | } | |
63229905 LC |
175 | |
176 | return args; | |
177 | } | |
178 | ||
179 | /* Lookup OBJECT in weak hash table TABLE using ASSOC. OBJECT is searched | |
180 | for in the alist that is the BUCKET_INDEXth element of BUCKETS. | |
181 | Optionally update TABLE and rehash it. */ | |
182 | static SCM | |
183 | weak_bucket_assoc (SCM table, SCM buckets, size_t bucket_index, | |
184 | scm_t_hash_fn hash_fn, | |
185 | scm_t_assoc_fn assoc, SCM object, void *closure) | |
186 | { | |
187 | SCM result; | |
e9bac3be LC |
188 | SCM bucket, *strong_refs; |
189 | struct t_fixup_args args; | |
190 | ||
191 | bucket = SCM_SIMPLE_VECTOR_REF (buckets, bucket_index); | |
192 | ||
193 | /* Prepare STRONG_REFS as an array large enough to hold all the keys | |
194 | and values in BUCKET. */ | |
195 | strong_refs = alloca (scm_ilength (bucket) * 2 * sizeof (SCM)); | |
196 | ||
197 | args.bucket = bucket; | |
198 | args.bucket_copy = strong_refs; | |
199 | ||
200 | /* Fixup BUCKET. Do that with the allocation lock held to avoid | |
201 | seeing disappearing links pointing to objects that have already | |
202 | been reclaimed (this happens when the disappearing links that point | |
203 | to it haven't yet been cleared.) | |
204 | ||
205 | The `do_weak_bucket_fixup' call populates STRONG_REFS with a copy | |
206 | of BUCKET's entries after it's been fixed up. Thus, all the | |
207 | entries kept in BUCKET are still reachable when ASSOC sees | |
208 | them. */ | |
209 | GC_call_with_alloc_lock (do_weak_bucket_fixup, &args); | |
210 | ||
211 | bucket = args.bucket; | |
212 | SCM_SIMPLE_VECTOR_SET (buckets, bucket_index, bucket); | |
213 | ||
214 | result = assoc (object, bucket, closure); | |
6bb2c00a AW |
215 | |
216 | /* If we got a result, it should not have NULL fields. */ | |
217 | if (scm_is_pair (result) && SCM_WEAK_PAIR_DELETED_P (result)) | |
218 | abort (); | |
63229905 | 219 | |
e9bac3be LC |
220 | scm_remember_upto_here_1 (strong_refs); |
221 | ||
f0554ee7 | 222 | if (args.removed_items > 0) |
63229905 LC |
223 | { |
224 | /* Update TABLE's item count and optionally trigger a rehash. */ | |
225 | size_t remaining; | |
226 | ||
227 | assert (SCM_HASHTABLE_N_ITEMS (table) >= args.removed_items); | |
228 | ||
229 | remaining = SCM_HASHTABLE_N_ITEMS (table) - args.removed_items; | |
230 | SCM_SET_HASHTABLE_N_ITEMS (table, remaining); | |
231 | ||
70249b98 LC |
232 | if (remaining < SCM_HASHTABLE_LOWER (table)) |
233 | scm_i_rehash (table, hash_fn, closure, "weak_bucket_assoc"); | |
63229905 LC |
234 | } |
235 | ||
236 | return result; | |
237 | } | |
d9c82e20 LC |
238 | |
239 | ||
6efbc280 AW |
240 | /* Packed arguments for `weak_bucket_assoc_by_hash'. */ |
241 | struct assoc_by_hash_data | |
242 | { | |
243 | SCM alist; | |
244 | SCM ret; | |
245 | scm_t_hash_predicate_fn predicate; | |
246 | void *closure; | |
247 | }; | |
248 | ||
249 | /* See scm_hash_fn_get_handle_by_hash below. */ | |
250 | static void* | |
251 | weak_bucket_assoc_by_hash (void *args) | |
252 | { | |
253 | struct assoc_by_hash_data *data = args; | |
254 | SCM alist = data->alist; | |
255 | ||
256 | for (; scm_is_pair (alist); alist = SCM_CDR (alist)) | |
257 | { | |
258 | SCM pair = SCM_CAR (alist); | |
259 | ||
260 | if (!SCM_WEAK_PAIR_DELETED_P (pair) | |
261 | && data->predicate (SCM_CAR (pair), data->closure)) | |
262 | { | |
263 | data->ret = pair; | |
264 | break; | |
265 | } | |
266 | } | |
267 | return args; | |
268 | } | |
269 | ||
270 | ||
3a2de079 | 271 | \f |
c35738c1 | 272 | static SCM |
a9cf5c71 MV |
273 | make_hash_table (int flags, unsigned long k, const char *func_name) |
274 | { | |
c99de5aa | 275 | SCM vector; |
9358af6a | 276 | scm_t_hashtable *t; |
110beb83 | 277 | int i = 0, n = k ? k : 31; |
7c888dfa | 278 | while (i + 1 < HASHTABLE_SIZE_N && n > hashtable_size[i]) |
110beb83 MD |
279 | ++i; |
280 | n = hashtable_size[i]; | |
3a2de079 LC |
281 | |
282 | /* In both cases, i.e., regardless of whether we are creating a weak hash | |
283 | table, we return a non-weak vector. This is because the vector itself | |
284 | is not weak in the case of a weak hash table: the alist pairs are. */ | |
285 | vector = scm_c_make_vector (n, SCM_EOL); | |
286 | ||
287 | t = scm_gc_malloc_pointerless (sizeof (*t), s_hashtable); | |
c35738c1 | 288 | t->min_size_index = t->size_index = i; |
f59a096e | 289 | t->n_items = 0; |
c35738c1 | 290 | t->lower = 0; |
110beb83 | 291 | t->upper = 9 * n / 10; |
c35738c1 | 292 | t->flags = flags; |
d3a80924 | 293 | t->hash_fn = NULL; |
c6a35e35 | 294 | |
c99de5aa AW |
295 | /* FIXME: we just need two words of storage, not three */ |
296 | return scm_double_cell (scm_tc7_hashtable, SCM_UNPACK (vector), | |
297 | (scm_t_bits)t, 0); | |
f59a096e MD |
298 | } |
299 | ||
c35738c1 MD |
300 | void |
301 | scm_i_rehash (SCM table, | |
f044da55 | 302 | scm_t_hash_fn hash_fn, |
c35738c1 MD |
303 | void *closure, |
304 | const char* func_name) | |
305 | { | |
306 | SCM buckets, new_buckets; | |
307 | int i; | |
308 | unsigned long old_size; | |
309 | unsigned long new_size; | |
310 | ||
311 | if (SCM_HASHTABLE_N_ITEMS (table) < SCM_HASHTABLE_LOWER (table)) | |
312 | { | |
313 | /* rehashing is not triggered when i <= min_size */ | |
314 | i = SCM_HASHTABLE (table)->size_index; | |
315 | do | |
316 | --i; | |
317 | while (i > SCM_HASHTABLE (table)->min_size_index | |
318 | && SCM_HASHTABLE_N_ITEMS (table) < hashtable_size[i] / 4); | |
319 | } | |
320 | else | |
321 | { | |
322 | i = SCM_HASHTABLE (table)->size_index + 1; | |
323 | if (i >= HASHTABLE_SIZE_N) | |
324 | /* don't rehash */ | |
325 | return; | |
d3a80924 MV |
326 | |
327 | /* Remember HASH_FN for rehash_after_gc, but only when CLOSURE | |
328 | is not needed since CLOSURE can not be guaranteed to be valid | |
329 | after this function returns. | |
330 | */ | |
331 | if (closure == NULL) | |
332 | SCM_HASHTABLE (table)->hash_fn = hash_fn; | |
c35738c1 MD |
333 | } |
334 | SCM_HASHTABLE (table)->size_index = i; | |
76da80e7 | 335 | |
c35738c1 MD |
336 | new_size = hashtable_size[i]; |
337 | if (i <= SCM_HASHTABLE (table)->min_size_index) | |
338 | SCM_HASHTABLE (table)->lower = 0; | |
339 | else | |
340 | SCM_HASHTABLE (table)->lower = new_size / 4; | |
341 | SCM_HASHTABLE (table)->upper = 9 * new_size / 10; | |
342 | buckets = SCM_HASHTABLE_VECTOR (table); | |
3a2de079 LC |
343 | |
344 | new_buckets = scm_c_make_vector (new_size, SCM_EOL); | |
c35738c1 | 345 | |
bc6580eb MV |
346 | /* When this is a weak hashtable, running the GC might change it. |
347 | We need to cope with this while rehashing its elements. We do | |
06c1d900 MV |
348 | this by first installing the new, empty bucket vector. Then we |
349 | remove the elements from the old bucket vector and insert them | |
350 | into the new one. | |
bc6580eb MV |
351 | */ |
352 | ||
353 | SCM_SET_HASHTABLE_VECTOR (table, new_buckets); | |
354 | SCM_SET_HASHTABLE_N_ITEMS (table, 0); | |
bc6580eb | 355 | |
3ebc1832 | 356 | old_size = SCM_SIMPLE_VECTOR_LENGTH (buckets); |
c35738c1 MD |
357 | for (i = 0; i < old_size; ++i) |
358 | { | |
bc6580eb MV |
359 | SCM ls, cell, handle; |
360 | ||
361 | ls = SCM_SIMPLE_VECTOR_REF (buckets, i); | |
c2f21af5 MV |
362 | SCM_SIMPLE_VECTOR_SET (buckets, i, SCM_EOL); |
363 | ||
bc6580eb | 364 | while (scm_is_pair (ls)) |
c35738c1 MD |
365 | { |
366 | unsigned long h; | |
c6a35e35 | 367 | |
bc6580eb MV |
368 | cell = ls; |
369 | handle = SCM_CAR (cell); | |
370 | ls = SCM_CDR (ls); | |
c6a35e35 | 371 | |
986ec822 | 372 | if (SCM_WEAK_PAIR_DELETED_P (handle)) |
639e56a4 LC |
373 | /* HANDLE is a nullified weak pair: skip it. */ |
374 | continue; | |
c6a35e35 | 375 | |
c35738c1 MD |
376 | h = hash_fn (SCM_CAR (handle), new_size, closure); |
377 | if (h >= new_size) | |
b9bd8526 | 378 | scm_out_of_range (func_name, scm_from_ulong (h)); |
bc6580eb MV |
379 | SCM_SETCDR (cell, SCM_SIMPLE_VECTOR_REF (new_buckets, h)); |
380 | SCM_SIMPLE_VECTOR_SET (new_buckets, h, cell); | |
381 | SCM_HASHTABLE_INCREMENT (table); | |
c35738c1 MD |
382 | } |
383 | } | |
c35738c1 MD |
384 | } |
385 | ||
386 | ||
c99de5aa AW |
387 | void |
388 | scm_i_hashtable_print (SCM exp, SCM port, scm_print_state *pstate) | |
f59a096e | 389 | { |
c35738c1 MD |
390 | scm_puts ("#<", port); |
391 | if (SCM_HASHTABLE_WEAK_KEY_P (exp)) | |
392 | scm_puts ("weak-key-", port); | |
393 | else if (SCM_HASHTABLE_WEAK_VALUE_P (exp)) | |
394 | scm_puts ("weak-value-", port); | |
395 | else if (SCM_HASHTABLE_DOUBLY_WEAK_P (exp)) | |
396 | scm_puts ("doubly-weak-", port); | |
397 | scm_puts ("hash-table ", port); | |
73c080f9 | 398 | scm_uintprint (SCM_UNPACK (exp), 16, port); |
fb8b2a9d | 399 | scm_putc (' ', port); |
06c1d900 | 400 | scm_uintprint (SCM_HASHTABLE_N_ITEMS (exp), 10, port); |
f59a096e | 401 | scm_putc ('/', port); |
3ebc1832 MV |
402 | scm_uintprint (SCM_SIMPLE_VECTOR_LENGTH (SCM_HASHTABLE_VECTOR (exp)), |
403 | 10, port); | |
f59a096e | 404 | scm_puts (">", port); |
c99de5aa AW |
405 | } |
406 | ||
f59a096e | 407 | |
00ffa0e7 | 408 | SCM |
c014a02e | 409 | scm_c_make_hash_table (unsigned long k) |
00ffa0e7 | 410 | { |
c35738c1 | 411 | return make_hash_table (0, k, "scm_c_make_hash_table"); |
f59a096e MD |
412 | } |
413 | ||
414 | SCM_DEFINE (scm_make_hash_table, "make-hash-table", 0, 1, 0, | |
415 | (SCM n), | |
a9cf5c71 | 416 | "Make a new abstract hash table object with minimum number of buckets @var{n}\n") |
f59a096e MD |
417 | #define FUNC_NAME s_scm_make_hash_table |
418 | { | |
419 | if (SCM_UNBNDP (n)) | |
c35738c1 | 420 | return make_hash_table (0, 0, FUNC_NAME); |
f59a096e | 421 | else |
a55c2b68 | 422 | return make_hash_table (0, scm_to_ulong (n), FUNC_NAME); |
f59a096e MD |
423 | } |
424 | #undef FUNC_NAME | |
425 | ||
66b229d5 AW |
426 | /* The before-gc C hook only runs if GC_set_start_callback is available, |
427 | so if not, fall back on a finalizer-based implementation. */ | |
428 | static int | |
429 | weak_gc_callback (void **weak) | |
62c290e9 | 430 | { |
631e49ed AW |
431 | void *val = weak[0]; |
432 | void (*callback) (SCM) = weak[1]; | |
62c290e9 | 433 | |
66b229d5 AW |
434 | if (!val) |
435 | return 0; | |
436 | ||
437 | callback (PTR2SCM (val)); | |
438 | ||
439 | return 1; | |
440 | } | |
441 | ||
442 | #ifdef HAVE_GC_SET_START_CALLBACK | |
443 | static void* | |
444 | weak_gc_hook (void *hook_data, void *fn_data, void *data) | |
445 | { | |
446 | if (!weak_gc_callback (fn_data)) | |
447 | scm_c_hook_remove (&scm_before_gc_c_hook, weak_gc_hook, fn_data); | |
62c290e9 | 448 | |
631e49ed | 449 | return NULL; |
62c290e9 | 450 | } |
66b229d5 AW |
451 | #else |
452 | static void | |
453 | weak_gc_finalizer (void *ptr, void *data) | |
454 | { | |
455 | if (weak_gc_callback (ptr)) | |
456 | GC_REGISTER_FINALIZER_NO_ORDER (ptr, weak_gc_finalizer, data, NULL, NULL); | |
457 | } | |
458 | #endif | |
62c290e9 AW |
459 | |
460 | static void | |
461 | scm_c_register_weak_gc_callback (SCM obj, void (*callback) (SCM)) | |
462 | { | |
631e49ed | 463 | void **weak = GC_MALLOC_ATOMIC (sizeof (void*) * 2); |
62c290e9 | 464 | |
631e49ed AW |
465 | weak[0] = SCM2PTR (obj); |
466 | weak[1] = (void*)callback; | |
62c290e9 AW |
467 | GC_GENERAL_REGISTER_DISAPPEARING_LINK (weak, SCM2PTR (obj)); |
468 | ||
66b229d5 AW |
469 | #ifdef HAVE_GC_SET_START_CALLBACK |
470 | scm_c_hook_add (&scm_before_gc_c_hook, weak_gc_hook, weak, 0); | |
471 | #else | |
472 | GC_REGISTER_FINALIZER_NO_ORDER (weak, weak_gc_finalizer, NULL, NULL, NULL); | |
473 | #endif | |
62c290e9 AW |
474 | } |
475 | ||
c35738c1 MD |
476 | SCM_DEFINE (scm_make_weak_key_hash_table, "make-weak-key-hash-table", 0, 1, 0, |
477 | (SCM n), | |
478 | "@deffnx {Scheme Procedure} make-weak-value-hash-table size\n" | |
479 | "@deffnx {Scheme Procedure} make-doubly-weak-hash-table size\n" | |
a9cf5c71 | 480 | "Return a weak hash table with @var{size} buckets.\n" |
c35738c1 MD |
481 | "\n" |
482 | "You can modify weak hash tables in exactly the same way you\n" | |
483 | "would modify regular hash tables. (@pxref{Hash Tables})") | |
484 | #define FUNC_NAME s_scm_make_weak_key_hash_table | |
f59a096e | 485 | { |
6800f86d AW |
486 | SCM ret; |
487 | ||
c35738c1 | 488 | if (SCM_UNBNDP (n)) |
6800f86d | 489 | ret = make_hash_table (SCM_HASHTABLEF_WEAK_CAR, 0, FUNC_NAME); |
f59a096e | 490 | else |
6800f86d AW |
491 | ret = make_hash_table (SCM_HASHTABLEF_WEAK_CAR, |
492 | scm_to_ulong (n), FUNC_NAME); | |
493 | ||
494 | scm_c_register_weak_gc_callback (ret, vacuum_weak_hash_table); | |
495 | ||
496 | return ret; | |
c35738c1 MD |
497 | } |
498 | #undef FUNC_NAME | |
499 | ||
500 | ||
501 | SCM_DEFINE (scm_make_weak_value_hash_table, "make-weak-value-hash-table", 0, 1, 0, | |
502 | (SCM n), | |
503 | "Return a hash table with weak values with @var{size} buckets.\n" | |
504 | "(@pxref{Hash Tables})") | |
505 | #define FUNC_NAME s_scm_make_weak_value_hash_table | |
506 | { | |
62c290e9 AW |
507 | SCM ret; |
508 | ||
c35738c1 | 509 | if (SCM_UNBNDP (n)) |
62c290e9 | 510 | ret = make_hash_table (SCM_HASHTABLEF_WEAK_CDR, 0, FUNC_NAME); |
f59a096e | 511 | else |
62c290e9 AW |
512 | ret = make_hash_table (SCM_HASHTABLEF_WEAK_CDR, |
513 | scm_to_ulong (n), FUNC_NAME); | |
514 | ||
515 | scm_c_register_weak_gc_callback (ret, vacuum_weak_hash_table); | |
516 | ||
517 | return ret; | |
c35738c1 MD |
518 | } |
519 | #undef FUNC_NAME | |
f59a096e | 520 | |
c35738c1 | 521 | |
b86069c1 | 522 | SCM_DEFINE (scm_make_doubly_weak_hash_table, "make-doubly-weak-hash-table", 0, 1, 0, |
c35738c1 MD |
523 | (SCM n), |
524 | "Return a hash table with weak keys and values with @var{size}\n" | |
525 | "buckets. (@pxref{Hash Tables})") | |
526 | #define FUNC_NAME s_scm_make_doubly_weak_hash_table | |
527 | { | |
62c290e9 AW |
528 | SCM ret; |
529 | ||
c35738c1 | 530 | if (SCM_UNBNDP (n)) |
62c290e9 AW |
531 | ret = make_hash_table (SCM_HASHTABLEF_WEAK_CAR | SCM_HASHTABLEF_WEAK_CDR, |
532 | 0, FUNC_NAME); | |
c35738c1 | 533 | else |
62c290e9 AW |
534 | ret = make_hash_table (SCM_HASHTABLEF_WEAK_CAR | SCM_HASHTABLEF_WEAK_CDR, |
535 | scm_to_ulong (n), FUNC_NAME); | |
536 | ||
537 | scm_c_register_weak_gc_callback (ret, vacuum_weak_hash_table); | |
538 | ||
539 | return ret; | |
f59a096e | 540 | } |
c35738c1 MD |
541 | #undef FUNC_NAME |
542 | ||
543 | ||
544 | SCM_DEFINE (scm_hash_table_p, "hash-table?", 1, 0, 0, | |
545 | (SCM obj), | |
a9cf5c71 | 546 | "Return @code{#t} if @var{obj} is an abstract hash table object.") |
c35738c1 MD |
547 | #define FUNC_NAME s_scm_hash_table_p |
548 | { | |
7888309b | 549 | return scm_from_bool (SCM_HASHTABLE_P (obj)); |
c35738c1 MD |
550 | } |
551 | #undef FUNC_NAME | |
552 | ||
553 | ||
554 | SCM_DEFINE (scm_weak_key_hash_table_p, "weak-key-hash-table?", 1, 0, 0, | |
555 | (SCM obj), | |
556 | "@deffnx {Scheme Procedure} weak-value-hash-table? obj\n" | |
557 | "@deffnx {Scheme Procedure} doubly-weak-hash-table? obj\n" | |
558 | "Return @code{#t} if @var{obj} is the specified weak hash\n" | |
559 | "table. Note that a doubly weak hash table is neither a weak key\n" | |
560 | "nor a weak value hash table.") | |
561 | #define FUNC_NAME s_scm_weak_key_hash_table_p | |
562 | { | |
7888309b | 563 | return scm_from_bool (SCM_HASHTABLE_P (obj) && SCM_HASHTABLE_WEAK_KEY_P (obj)); |
c35738c1 MD |
564 | } |
565 | #undef FUNC_NAME | |
566 | ||
567 | ||
568 | SCM_DEFINE (scm_weak_value_hash_table_p, "weak-value-hash-table?", 1, 0, 0, | |
569 | (SCM obj), | |
570 | "Return @code{#t} if @var{obj} is a weak value hash table.") | |
571 | #define FUNC_NAME s_scm_weak_value_hash_table_p | |
572 | { | |
7888309b | 573 | return scm_from_bool (SCM_HASHTABLE_P (obj) && SCM_HASHTABLE_WEAK_VALUE_P (obj)); |
c35738c1 MD |
574 | } |
575 | #undef FUNC_NAME | |
576 | ||
577 | ||
578 | SCM_DEFINE (scm_doubly_weak_hash_table_p, "doubly-weak-hash-table?", 1, 0, 0, | |
579 | (SCM obj), | |
580 | "Return @code{#t} if @var{obj} is a doubly weak hash table.") | |
581 | #define FUNC_NAME s_scm_doubly_weak_hash_table_p | |
582 | { | |
7888309b | 583 | return scm_from_bool (SCM_HASHTABLE_P (obj) && SCM_HASHTABLE_DOUBLY_WEAK_P (obj)); |
c35738c1 MD |
584 | } |
585 | #undef FUNC_NAME | |
586 | ||
3330f00f | 587 | |
d587c9e8 LC |
588 | \f |
589 | /* Accessing hash table entries. */ | |
22a52da1 | 590 | |
0f2d19dd | 591 | SCM |
d587c9e8 LC |
592 | scm_hash_fn_get_handle (SCM table, SCM obj, |
593 | scm_t_hash_fn hash_fn, scm_t_assoc_fn assoc_fn, | |
594 | void * closure) | |
22a52da1 | 595 | #define FUNC_NAME "scm_hash_fn_get_handle" |
0f2d19dd | 596 | { |
c014a02e | 597 | unsigned long k; |
63229905 | 598 | SCM buckets, h; |
0f2d19dd | 599 | |
f0554ee7 AW |
600 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); |
601 | buckets = SCM_HASHTABLE_VECTOR (table); | |
d9c82e20 LC |
602 | |
603 | if (SCM_SIMPLE_VECTOR_LENGTH (buckets) == 0) | |
22a52da1 | 604 | return SCM_BOOL_F; |
d9c82e20 LC |
605 | k = hash_fn (obj, SCM_SIMPLE_VECTOR_LENGTH (buckets), closure); |
606 | if (k >= SCM_SIMPLE_VECTOR_LENGTH (buckets)) | |
f0554ee7 | 607 | scm_out_of_range (FUNC_NAME, scm_from_ulong (k)); |
3a2de079 | 608 | |
f0554ee7 | 609 | if (SCM_HASHTABLE_WEAK_P (table)) |
63229905 LC |
610 | h = weak_bucket_assoc (table, buckets, k, hash_fn, |
611 | assoc_fn, obj, closure); | |
612 | else | |
613 | h = assoc_fn (obj, SCM_SIMPLE_VECTOR_REF (buckets, k), closure); | |
e4d21e6b | 614 | |
0f2d19dd JB |
615 | return h; |
616 | } | |
22a52da1 | 617 | #undef FUNC_NAME |
0f2d19dd JB |
618 | |
619 | ||
6efbc280 AW |
620 | /* This procedure implements three optimizations, with respect to the |
621 | raw get_handle(): | |
622 | ||
623 | 1. For weak tables, it's assumed that calling the predicate in the | |
624 | allocation lock is safe. In practice this means that the predicate | |
625 | cannot call arbitrary scheme functions. | |
626 | ||
627 | 2. We don't check for overflow / underflow and rehash. | |
628 | ||
629 | 3. We don't actually have to allocate a key -- instead we get the | |
630 | hash value directly. This is useful for, for example, looking up | |
631 | strings in the symbol table. | |
632 | */ | |
633 | SCM | |
634 | scm_hash_fn_get_handle_by_hash (SCM table, unsigned long raw_hash, | |
635 | scm_t_hash_predicate_fn predicate_fn, | |
636 | void *closure) | |
637 | #define FUNC_NAME "scm_hash_fn_ref_by_hash" | |
638 | { | |
639 | unsigned long k; | |
640 | SCM buckets, alist, h = SCM_BOOL_F; | |
641 | ||
642 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); | |
643 | buckets = SCM_HASHTABLE_VECTOR (table); | |
644 | ||
645 | if (SCM_SIMPLE_VECTOR_LENGTH (buckets) == 0) | |
646 | return SCM_BOOL_F; | |
647 | ||
648 | k = raw_hash % SCM_SIMPLE_VECTOR_LENGTH (buckets); | |
649 | alist = SCM_SIMPLE_VECTOR_REF (buckets, k); | |
650 | ||
651 | if (SCM_HASHTABLE_WEAK_P (table)) | |
652 | { | |
653 | struct assoc_by_hash_data args; | |
654 | ||
655 | args.alist = alist; | |
656 | args.ret = SCM_BOOL_F; | |
657 | args.predicate = predicate_fn; | |
658 | args.closure = closure; | |
659 | GC_call_with_alloc_lock (weak_bucket_assoc_by_hash, &args); | |
660 | h = args.ret; | |
661 | } | |
662 | else | |
663 | for (; scm_is_pair (alist); alist = SCM_CDR (alist)) | |
664 | { | |
665 | SCM pair = SCM_CAR (alist); | |
666 | if (predicate_fn (SCM_CAR (pair), closure)) | |
667 | { | |
668 | h = pair; | |
669 | break; | |
670 | } | |
671 | } | |
672 | ||
673 | return h; | |
674 | } | |
675 | #undef FUNC_NAME | |
676 | ||
677 | ||
0f2d19dd | 678 | SCM |
f044da55 LC |
679 | scm_hash_fn_create_handle_x (SCM table, SCM obj, SCM init, |
680 | scm_t_hash_fn hash_fn, scm_t_assoc_fn assoc_fn, | |
681 | void * closure) | |
cbaadf02 | 682 | #define FUNC_NAME "scm_hash_fn_create_handle_x" |
0f2d19dd | 683 | { |
c014a02e | 684 | unsigned long k; |
63229905 | 685 | SCM buckets, it; |
0f2d19dd | 686 | |
f0554ee7 AW |
687 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); |
688 | buckets = SCM_HASHTABLE_VECTOR (table); | |
689 | ||
3ebc1832 | 690 | if (SCM_SIMPLE_VECTOR_LENGTH (buckets) == 0) |
cbaadf02 DH |
691 | SCM_MISC_ERROR ("void hashtable", SCM_EOL); |
692 | ||
3ebc1832 MV |
693 | k = hash_fn (obj, SCM_SIMPLE_VECTOR_LENGTH (buckets), closure); |
694 | if (k >= SCM_SIMPLE_VECTOR_LENGTH (buckets)) | |
b9bd8526 | 695 | scm_out_of_range ("hash_fn_create_handle_x", scm_from_ulong (k)); |
3a2de079 | 696 | |
f0554ee7 | 697 | if (SCM_HASHTABLE_WEAK_P (table)) |
63229905 LC |
698 | it = weak_bucket_assoc (table, buckets, k, hash_fn, |
699 | assoc_fn, obj, closure); | |
700 | else | |
701 | it = assoc_fn (obj, SCM_SIMPLE_VECTOR_REF (buckets, k), closure); | |
e4d21e6b | 702 | |
0306509b | 703 | if (scm_is_pair (it)) |
0a4c1355 | 704 | return it; |
15bd90ea NJ |
705 | else if (scm_is_true (it)) |
706 | scm_wrong_type_arg_msg (NULL, 0, it, "a pair"); | |
ee083ac2 DH |
707 | else |
708 | { | |
5b582466 MV |
709 | /* When this is a weak hashtable, running the GC can change it. |
710 | Thus, we must allocate the new cells first and can only then | |
711 | access BUCKETS. Also, we need to fetch the bucket vector | |
712 | again since the hashtable might have been rehashed. This | |
713 | necessitates a new hash value as well. | |
bc6580eb | 714 | */ |
3a2de079 LC |
715 | SCM handle, new_bucket; |
716 | ||
f0554ee7 | 717 | if (SCM_HASHTABLE_WEAK_P (table)) |
3a2de079 | 718 | { |
741e83fc | 719 | /* FIXME: We don't support weak alist vectors. */ |
3a2de079 LC |
720 | /* Use a weak cell. */ |
721 | if (SCM_HASHTABLE_DOUBLY_WEAK_P (table)) | |
986ec822 | 722 | handle = scm_doubly_weak_pair (obj, init); |
3a2de079 | 723 | else if (SCM_HASHTABLE_WEAK_KEY_P (table)) |
986ec822 | 724 | handle = scm_weak_car_pair (obj, init); |
3a2de079 | 725 | else |
986ec822 | 726 | handle = scm_weak_cdr_pair (obj, init); |
3a2de079 LC |
727 | } |
728 | else | |
729 | /* Use a regular, non-weak cell. */ | |
730 | handle = scm_cons (obj, init); | |
731 | ||
732 | new_bucket = scm_cons (handle, SCM_EOL); | |
733 | ||
f0554ee7 | 734 | if (!scm_is_eq (SCM_HASHTABLE_VECTOR (table), buckets)) |
5b582466 MV |
735 | { |
736 | buckets = SCM_HASHTABLE_VECTOR (table); | |
737 | k = hash_fn (obj, SCM_SIMPLE_VECTOR_LENGTH (buckets), closure); | |
738 | if (k >= SCM_SIMPLE_VECTOR_LENGTH (buckets)) | |
739 | scm_out_of_range ("hash_fn_create_handle_x", scm_from_ulong (k)); | |
740 | } | |
bc6580eb | 741 | SCM_SETCDR (new_bucket, SCM_SIMPLE_VECTOR_REF (buckets, k)); |
3ebc1832 | 742 | SCM_SIMPLE_VECTOR_SET (buckets, k, new_bucket); |
f0554ee7 | 743 | SCM_HASHTABLE_INCREMENT (table); |
40d2a007 | 744 | |
62c290e9 | 745 | /* Maybe rehash the table. */ |
f0554ee7 AW |
746 | if (SCM_HASHTABLE_N_ITEMS (table) < SCM_HASHTABLE_LOWER (table) |
747 | || SCM_HASHTABLE_N_ITEMS (table) > SCM_HASHTABLE_UPPER (table)) | |
748 | scm_i_rehash (table, hash_fn, closure, FUNC_NAME); | |
ee083ac2 DH |
749 | return SCM_CAR (new_bucket); |
750 | } | |
0f2d19dd | 751 | } |
cbaadf02 | 752 | #undef FUNC_NAME |
0f2d19dd | 753 | |
1cc91f1b | 754 | |
f044da55 LC |
755 | SCM |
756 | scm_hash_fn_ref (SCM table, SCM obj, SCM dflt, | |
757 | scm_t_hash_fn hash_fn, scm_t_assoc_fn assoc_fn, | |
758 | void *closure) | |
0f2d19dd | 759 | { |
22a52da1 | 760 | SCM it = scm_hash_fn_get_handle (table, obj, hash_fn, assoc_fn, closure); |
d2e53ed6 | 761 | if (scm_is_pair (it)) |
0f2d19dd | 762 | return SCM_CDR (it); |
22a52da1 DH |
763 | else |
764 | return dflt; | |
0f2d19dd JB |
765 | } |
766 | ||
636c99d4 | 767 | struct weak_cdr_data |
ecc9d1b5 AW |
768 | { |
769 | SCM pair; | |
636c99d4 | 770 | SCM cdr; |
ecc9d1b5 AW |
771 | }; |
772 | ||
773 | static void* | |
636c99d4 | 774 | get_weak_cdr (void *data) |
ecc9d1b5 | 775 | { |
636c99d4 | 776 | struct weak_cdr_data *d = data; |
ecc9d1b5 | 777 | |
636c99d4 AW |
778 | if (SCM_WEAK_PAIR_CDR_DELETED_P (d->pair)) |
779 | d->cdr = SCM_BOOL_F; | |
ecc9d1b5 | 780 | else |
636c99d4 AW |
781 | d->cdr = SCM_CDR (d->pair); |
782 | ||
ecc9d1b5 AW |
783 | return NULL; |
784 | } | |
785 | ||
636c99d4 AW |
786 | static SCM |
787 | weak_pair_cdr (SCM x) | |
788 | { | |
789 | struct weak_cdr_data data; | |
790 | ||
791 | data.pair = x; | |
792 | GC_call_with_alloc_lock (get_weak_cdr, &data); | |
793 | ||
794 | return data.cdr; | |
795 | } | |
796 | ||
f044da55 LC |
797 | SCM |
798 | scm_hash_fn_set_x (SCM table, SCM obj, SCM val, | |
799 | scm_t_hash_fn hash_fn, scm_t_assoc_fn assoc_fn, | |
800 | void *closure) | |
0f2d19dd | 801 | { |
ecc9d1b5 | 802 | SCM pair; |
0f2d19dd | 803 | |
ecc9d1b5 AW |
804 | pair = scm_hash_fn_create_handle_x (table, obj, val, |
805 | hash_fn, assoc_fn, closure); | |
5a99a574 | 806 | |
636c99d4 | 807 | if (!scm_is_eq (SCM_CDR (pair), val)) |
ecc9d1b5 AW |
808 | { |
809 | if (SCM_UNLIKELY (SCM_HASHTABLE_WEAK_VALUE_P (table))) | |
810 | { | |
636c99d4 AW |
811 | /* If the former value was on the heap, we need to unregister |
812 | the weak link. */ | |
813 | SCM prev = weak_pair_cdr (pair); | |
ecc9d1b5 | 814 | |
636c99d4 AW |
815 | SCM_SETCDR (pair, val); |
816 | ||
817 | if (SCM_NIMP (prev) && !SCM_NIMP (val)) | |
6922d92f | 818 | GC_unregister_disappearing_link ((void **) SCM_CDRLOC (pair)); |
636c99d4 | 819 | else |
6922d92f LC |
820 | SCM_I_REGISTER_DISAPPEARING_LINK ((void **) SCM_CDRLOC (pair), |
821 | SCM2PTR (val)); | |
ecc9d1b5 AW |
822 | } |
823 | else | |
824 | SCM_SETCDR (pair, val); | |
825 | } | |
826 | ||
0f2d19dd JB |
827 | return val; |
828 | } | |
829 | ||
830 | ||
d9c82e20 | 831 | SCM |
a9cf5c71 | 832 | scm_hash_fn_remove_x (SCM table, SCM obj, |
f044da55 LC |
833 | scm_t_hash_fn hash_fn, |
834 | scm_t_assoc_fn assoc_fn, | |
a9cf5c71 | 835 | void *closure) |
f0554ee7 | 836 | #define FUNC_NAME "hash_fn_remove_x" |
0f2d19dd | 837 | { |
c014a02e | 838 | unsigned long k; |
63229905 | 839 | SCM buckets, h; |
0f2d19dd | 840 | |
f0554ee7 AW |
841 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); |
842 | ||
843 | buckets = SCM_HASHTABLE_VECTOR (table); | |
844 | ||
c99de5aa | 845 | if (SCM_SIMPLE_VECTOR_LENGTH (buckets) == 0) |
0f2d19dd | 846 | return SCM_EOL; |
87ca11ff | 847 | |
3ebc1832 MV |
848 | k = hash_fn (obj, SCM_SIMPLE_VECTOR_LENGTH (buckets), closure); |
849 | if (k >= SCM_SIMPLE_VECTOR_LENGTH (buckets)) | |
f0554ee7 | 850 | scm_out_of_range (FUNC_NAME, scm_from_ulong (k)); |
3a2de079 | 851 | |
f0554ee7 | 852 | if (SCM_HASHTABLE_WEAK_P (table)) |
63229905 LC |
853 | h = weak_bucket_assoc (table, buckets, k, hash_fn, |
854 | assoc_fn, obj, closure); | |
855 | else | |
856 | h = assoc_fn (obj, SCM_SIMPLE_VECTOR_REF (buckets, k), closure); | |
e4d21e6b | 857 | |
7888309b | 858 | if (scm_is_true (h)) |
87ca11ff | 859 | { |
3ebc1832 | 860 | SCM_SIMPLE_VECTOR_SET |
a9cf5c71 | 861 | (buckets, k, scm_delq_x (h, SCM_SIMPLE_VECTOR_REF (buckets, k))); |
f0554ee7 AW |
862 | SCM_HASHTABLE_DECREMENT (table); |
863 | if (SCM_HASHTABLE_N_ITEMS (table) < SCM_HASHTABLE_LOWER (table)) | |
864 | scm_i_rehash (table, hash_fn, closure, FUNC_NAME); | |
87ca11ff | 865 | } |
0f2d19dd JB |
866 | return h; |
867 | } | |
f0554ee7 | 868 | #undef FUNC_NAME |
0f2d19dd | 869 | |
c35738c1 MD |
870 | SCM_DEFINE (scm_hash_clear_x, "hash-clear!", 1, 0, 0, |
871 | (SCM table), | |
a9cf5c71 | 872 | "Remove all items from @var{table} (without triggering a resize).") |
c35738c1 MD |
873 | #define FUNC_NAME s_scm_hash_clear_x |
874 | { | |
f0554ee7 AW |
875 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); |
876 | ||
877 | scm_vector_fill_x (SCM_HASHTABLE_VECTOR (table), SCM_EOL); | |
878 | SCM_SET_HASHTABLE_N_ITEMS (table, 0); | |
879 | ||
c35738c1 MD |
880 | return SCM_UNSPECIFIED; |
881 | } | |
882 | #undef FUNC_NAME | |
0f2d19dd JB |
883 | |
884 | \f | |
885 | ||
a1ec6916 | 886 | SCM_DEFINE (scm_hashq_get_handle, "hashq-get-handle", 2, 0, 0, |
22a52da1 DH |
887 | (SCM table, SCM key), |
888 | "This procedure returns the @code{(key . value)} pair from the\n" | |
889 | "hash table @var{table}. If @var{table} does not hold an\n" | |
890 | "associated value for @var{key}, @code{#f} is returned.\n" | |
891 | "Uses @code{eq?} for equality testing.") | |
1bbd0b84 | 892 | #define FUNC_NAME s_scm_hashq_get_handle |
0f2d19dd | 893 | { |
1d9c2e62 AW |
894 | if (SCM_UNLIKELY (SCM_HASHTABLE_P (table) && SCM_HASHTABLE_WEAK_P (table))) |
895 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
896 | ||
d587c9e8 LC |
897 | return scm_hash_fn_get_handle (table, key, |
898 | (scm_t_hash_fn) scm_ihashq, | |
899 | (scm_t_assoc_fn) scm_sloppy_assq, | |
900 | 0); | |
0f2d19dd | 901 | } |
1bbd0b84 | 902 | #undef FUNC_NAME |
0f2d19dd JB |
903 | |
904 | ||
a1ec6916 | 905 | SCM_DEFINE (scm_hashq_create_handle_x, "hashq-create-handle!", 3, 0, 0, |
d550d22a GB |
906 | (SCM table, SCM key, SCM init), |
907 | "This function looks up @var{key} in @var{table} and returns its handle.\n" | |
b380b885 MD |
908 | "If @var{key} is not already present, a new handle is created which\n" |
909 | "associates @var{key} with @var{init}.") | |
1bbd0b84 | 910 | #define FUNC_NAME s_scm_hashq_create_handle_x |
0f2d19dd | 911 | { |
1d9c2e62 AW |
912 | if (SCM_UNLIKELY (SCM_HASHTABLE_P (table) && SCM_HASHTABLE_WEAK_P (table))) |
913 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
914 | ||
d587c9e8 LC |
915 | return scm_hash_fn_create_handle_x (table, key, init, |
916 | (scm_t_hash_fn) scm_ihashq, | |
917 | (scm_t_assoc_fn) scm_sloppy_assq, | |
918 | 0); | |
0f2d19dd | 919 | } |
1bbd0b84 | 920 | #undef FUNC_NAME |
0f2d19dd JB |
921 | |
922 | ||
a1ec6916 | 923 | SCM_DEFINE (scm_hashq_ref, "hashq-ref", 2, 1, 0, |
1e6808ea | 924 | (SCM table, SCM key, SCM dflt), |
b380b885 MD |
925 | "Look up @var{key} in the hash table @var{table}, and return the\n" |
926 | "value (if any) associated with it. If @var{key} is not found,\n" | |
b7e64f8b | 927 | "return @var{dflt} (or @code{#f} if no @var{dflt} argument\n" |
5352393c | 928 | "is supplied). Uses @code{eq?} for equality testing.") |
1bbd0b84 | 929 | #define FUNC_NAME s_scm_hashq_ref |
0f2d19dd | 930 | { |
54778cd3 | 931 | if (SCM_UNBNDP (dflt)) |
0f2d19dd | 932 | dflt = SCM_BOOL_F; |
d587c9e8 LC |
933 | return scm_hash_fn_ref (table, key, dflt, |
934 | (scm_t_hash_fn) scm_ihashq, | |
935 | (scm_t_assoc_fn) scm_sloppy_assq, | |
936 | 0); | |
0f2d19dd | 937 | } |
1bbd0b84 | 938 | #undef FUNC_NAME |
0f2d19dd JB |
939 | |
940 | ||
941 | ||
a1ec6916 | 942 | SCM_DEFINE (scm_hashq_set_x, "hashq-set!", 3, 0, 0, |
1e6808ea | 943 | (SCM table, SCM key, SCM val), |
5352393c | 944 | "Find the entry in @var{table} associated with @var{key}, and\n" |
b7e64f8b | 945 | "store @var{val} there. Uses @code{eq?} for equality testing.") |
1bbd0b84 | 946 | #define FUNC_NAME s_scm_hashq_set_x |
0f2d19dd | 947 | { |
d587c9e8 LC |
948 | return scm_hash_fn_set_x (table, key, val, |
949 | (scm_t_hash_fn) scm_ihashq, | |
950 | (scm_t_assoc_fn) scm_sloppy_assq, | |
951 | 0); | |
0f2d19dd | 952 | } |
1bbd0b84 | 953 | #undef FUNC_NAME |
0f2d19dd JB |
954 | |
955 | ||
956 | ||
a1ec6916 | 957 | SCM_DEFINE (scm_hashq_remove_x, "hashq-remove!", 2, 0, 0, |
1e6808ea | 958 | (SCM table, SCM key), |
5352393c MG |
959 | "Remove @var{key} (and any value associated with it) from\n" |
960 | "@var{table}. Uses @code{eq?} for equality tests.") | |
1bbd0b84 | 961 | #define FUNC_NAME s_scm_hashq_remove_x |
0f2d19dd | 962 | { |
d587c9e8 LC |
963 | return scm_hash_fn_remove_x (table, key, |
964 | (scm_t_hash_fn) scm_ihashq, | |
965 | (scm_t_assoc_fn) scm_sloppy_assq, | |
966 | 0); | |
0f2d19dd | 967 | } |
1bbd0b84 | 968 | #undef FUNC_NAME |
0f2d19dd JB |
969 | |
970 | ||
971 | \f | |
972 | ||
a1ec6916 | 973 | SCM_DEFINE (scm_hashv_get_handle, "hashv-get-handle", 2, 0, 0, |
22a52da1 DH |
974 | (SCM table, SCM key), |
975 | "This procedure returns the @code{(key . value)} pair from the\n" | |
976 | "hash table @var{table}. If @var{table} does not hold an\n" | |
977 | "associated value for @var{key}, @code{#f} is returned.\n" | |
978 | "Uses @code{eqv?} for equality testing.") | |
1bbd0b84 | 979 | #define FUNC_NAME s_scm_hashv_get_handle |
0f2d19dd | 980 | { |
1d9c2e62 AW |
981 | if (SCM_UNLIKELY (SCM_HASHTABLE_P (table) && SCM_HASHTABLE_WEAK_P (table))) |
982 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
983 | ||
d587c9e8 LC |
984 | return scm_hash_fn_get_handle (table, key, |
985 | (scm_t_hash_fn) scm_ihashv, | |
986 | (scm_t_assoc_fn) scm_sloppy_assv, | |
987 | 0); | |
0f2d19dd | 988 | } |
1bbd0b84 | 989 | #undef FUNC_NAME |
0f2d19dd JB |
990 | |
991 | ||
a1ec6916 | 992 | SCM_DEFINE (scm_hashv_create_handle_x, "hashv-create-handle!", 3, 0, 0, |
d550d22a GB |
993 | (SCM table, SCM key, SCM init), |
994 | "This function looks up @var{key} in @var{table} and returns its handle.\n" | |
995 | "If @var{key} is not already present, a new handle is created which\n" | |
996 | "associates @var{key} with @var{init}.") | |
1bbd0b84 | 997 | #define FUNC_NAME s_scm_hashv_create_handle_x |
0f2d19dd | 998 | { |
1d9c2e62 AW |
999 | if (SCM_UNLIKELY (SCM_HASHTABLE_P (table) && SCM_HASHTABLE_WEAK_P (table))) |
1000 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
1001 | ||
d587c9e8 LC |
1002 | return scm_hash_fn_create_handle_x (table, key, init, |
1003 | (scm_t_hash_fn) scm_ihashv, | |
1004 | (scm_t_assoc_fn) scm_sloppy_assv, | |
1005 | 0); | |
0f2d19dd | 1006 | } |
1bbd0b84 | 1007 | #undef FUNC_NAME |
0f2d19dd JB |
1008 | |
1009 | ||
a1ec6916 | 1010 | SCM_DEFINE (scm_hashv_ref, "hashv-ref", 2, 1, 0, |
1e6808ea | 1011 | (SCM table, SCM key, SCM dflt), |
d550d22a GB |
1012 | "Look up @var{key} in the hash table @var{table}, and return the\n" |
1013 | "value (if any) associated with it. If @var{key} is not found,\n" | |
b7e64f8b | 1014 | "return @var{dflt} (or @code{#f} if no @var{dflt} argument\n" |
5352393c | 1015 | "is supplied). Uses @code{eqv?} for equality testing.") |
1bbd0b84 | 1016 | #define FUNC_NAME s_scm_hashv_ref |
0f2d19dd | 1017 | { |
54778cd3 | 1018 | if (SCM_UNBNDP (dflt)) |
0f2d19dd | 1019 | dflt = SCM_BOOL_F; |
d587c9e8 LC |
1020 | return scm_hash_fn_ref (table, key, dflt, |
1021 | (scm_t_hash_fn) scm_ihashv, | |
1022 | (scm_t_assoc_fn) scm_sloppy_assv, | |
1023 | 0); | |
0f2d19dd | 1024 | } |
1bbd0b84 | 1025 | #undef FUNC_NAME |
0f2d19dd JB |
1026 | |
1027 | ||
1028 | ||
a1ec6916 | 1029 | SCM_DEFINE (scm_hashv_set_x, "hashv-set!", 3, 0, 0, |
1e6808ea | 1030 | (SCM table, SCM key, SCM val), |
5352393c MG |
1031 | "Find the entry in @var{table} associated with @var{key}, and\n" |
1032 | "store @var{value} there. Uses @code{eqv?} for equality testing.") | |
1bbd0b84 | 1033 | #define FUNC_NAME s_scm_hashv_set_x |
0f2d19dd | 1034 | { |
d587c9e8 LC |
1035 | return scm_hash_fn_set_x (table, key, val, |
1036 | (scm_t_hash_fn) scm_ihashv, | |
1037 | (scm_t_assoc_fn) scm_sloppy_assv, | |
1038 | 0); | |
0f2d19dd | 1039 | } |
1bbd0b84 | 1040 | #undef FUNC_NAME |
0f2d19dd JB |
1041 | |
1042 | ||
a1ec6916 | 1043 | SCM_DEFINE (scm_hashv_remove_x, "hashv-remove!", 2, 0, 0, |
1e6808ea | 1044 | (SCM table, SCM key), |
5352393c MG |
1045 | "Remove @var{key} (and any value associated with it) from\n" |
1046 | "@var{table}. Uses @code{eqv?} for equality tests.") | |
1bbd0b84 | 1047 | #define FUNC_NAME s_scm_hashv_remove_x |
0f2d19dd | 1048 | { |
d587c9e8 LC |
1049 | return scm_hash_fn_remove_x (table, key, |
1050 | (scm_t_hash_fn) scm_ihashv, | |
1051 | (scm_t_assoc_fn) scm_sloppy_assv, | |
1052 | 0); | |
0f2d19dd | 1053 | } |
1bbd0b84 | 1054 | #undef FUNC_NAME |
0f2d19dd JB |
1055 | |
1056 | \f | |
1057 | ||
a1ec6916 | 1058 | SCM_DEFINE (scm_hash_get_handle, "hash-get-handle", 2, 0, 0, |
22a52da1 DH |
1059 | (SCM table, SCM key), |
1060 | "This procedure returns the @code{(key . value)} pair from the\n" | |
1061 | "hash table @var{table}. If @var{table} does not hold an\n" | |
1062 | "associated value for @var{key}, @code{#f} is returned.\n" | |
1063 | "Uses @code{equal?} for equality testing.") | |
1bbd0b84 | 1064 | #define FUNC_NAME s_scm_hash_get_handle |
0f2d19dd | 1065 | { |
1d9c2e62 AW |
1066 | if (SCM_UNLIKELY (SCM_HASHTABLE_P (table) && SCM_HASHTABLE_WEAK_P (table))) |
1067 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
1068 | ||
d587c9e8 LC |
1069 | return scm_hash_fn_get_handle (table, key, |
1070 | (scm_t_hash_fn) scm_ihash, | |
1071 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
1072 | 0); | |
0f2d19dd | 1073 | } |
1bbd0b84 | 1074 | #undef FUNC_NAME |
0f2d19dd JB |
1075 | |
1076 | ||
a1ec6916 | 1077 | SCM_DEFINE (scm_hash_create_handle_x, "hash-create-handle!", 3, 0, 0, |
d550d22a GB |
1078 | (SCM table, SCM key, SCM init), |
1079 | "This function looks up @var{key} in @var{table} and returns its handle.\n" | |
1080 | "If @var{key} is not already present, a new handle is created which\n" | |
1081 | "associates @var{key} with @var{init}.") | |
1bbd0b84 | 1082 | #define FUNC_NAME s_scm_hash_create_handle_x |
0f2d19dd | 1083 | { |
1d9c2e62 AW |
1084 | if (SCM_UNLIKELY (SCM_HASHTABLE_P (table) && SCM_HASHTABLE_WEAK_P (table))) |
1085 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
1086 | ||
d587c9e8 LC |
1087 | return scm_hash_fn_create_handle_x (table, key, init, |
1088 | (scm_t_hash_fn) scm_ihash, | |
1089 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
1090 | 0); | |
0f2d19dd | 1091 | } |
1bbd0b84 | 1092 | #undef FUNC_NAME |
0f2d19dd JB |
1093 | |
1094 | ||
a1ec6916 | 1095 | SCM_DEFINE (scm_hash_ref, "hash-ref", 2, 1, 0, |
1e6808ea | 1096 | (SCM table, SCM key, SCM dflt), |
d550d22a GB |
1097 | "Look up @var{key} in the hash table @var{table}, and return the\n" |
1098 | "value (if any) associated with it. If @var{key} is not found,\n" | |
b7e64f8b | 1099 | "return @var{dflt} (or @code{#f} if no @var{dflt} argument\n" |
5352393c | 1100 | "is supplied). Uses @code{equal?} for equality testing.") |
1bbd0b84 | 1101 | #define FUNC_NAME s_scm_hash_ref |
0f2d19dd | 1102 | { |
54778cd3 | 1103 | if (SCM_UNBNDP (dflt)) |
0f2d19dd | 1104 | dflt = SCM_BOOL_F; |
d587c9e8 LC |
1105 | return scm_hash_fn_ref (table, key, dflt, |
1106 | (scm_t_hash_fn) scm_ihash, | |
1107 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
1108 | 0); | |
0f2d19dd | 1109 | } |
1bbd0b84 | 1110 | #undef FUNC_NAME |
0f2d19dd JB |
1111 | |
1112 | ||
1113 | ||
a1ec6916 | 1114 | SCM_DEFINE (scm_hash_set_x, "hash-set!", 3, 0, 0, |
1e6808ea | 1115 | (SCM table, SCM key, SCM val), |
5352393c | 1116 | "Find the entry in @var{table} associated with @var{key}, and\n" |
b7e64f8b | 1117 | "store @var{val} there. Uses @code{equal?} for equality\n" |
5352393c | 1118 | "testing.") |
1bbd0b84 | 1119 | #define FUNC_NAME s_scm_hash_set_x |
0f2d19dd | 1120 | { |
d587c9e8 LC |
1121 | return scm_hash_fn_set_x (table, key, val, |
1122 | (scm_t_hash_fn) scm_ihash, | |
1123 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
1124 | 0); | |
0f2d19dd | 1125 | } |
1bbd0b84 | 1126 | #undef FUNC_NAME |
0f2d19dd JB |
1127 | |
1128 | ||
1129 | ||
a1ec6916 | 1130 | SCM_DEFINE (scm_hash_remove_x, "hash-remove!", 2, 0, 0, |
1e6808ea | 1131 | (SCM table, SCM key), |
5352393c MG |
1132 | "Remove @var{key} (and any value associated with it) from\n" |
1133 | "@var{table}. Uses @code{equal?} for equality tests.") | |
1bbd0b84 | 1134 | #define FUNC_NAME s_scm_hash_remove_x |
0f2d19dd | 1135 | { |
d587c9e8 LC |
1136 | return scm_hash_fn_remove_x (table, key, |
1137 | (scm_t_hash_fn) scm_ihash, | |
1138 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
1139 | 0); | |
0f2d19dd | 1140 | } |
1bbd0b84 | 1141 | #undef FUNC_NAME |
0f2d19dd JB |
1142 | |
1143 | \f | |
1144 | ||
1145 | ||
92c2555f | 1146 | typedef struct scm_t_ihashx_closure |
0f2d19dd JB |
1147 | { |
1148 | SCM hash; | |
1149 | SCM assoc; | |
92c2555f | 1150 | } scm_t_ihashx_closure; |
0f2d19dd JB |
1151 | |
1152 | ||
1cc91f1b | 1153 | |
c014a02e | 1154 | static unsigned long |
d587c9e8 | 1155 | scm_ihashx (SCM obj, unsigned long n, void *arg) |
0f2d19dd | 1156 | { |
d587c9e8 LC |
1157 | SCM answer; |
1158 | scm_t_ihashx_closure *closure = (scm_t_ihashx_closure *) arg; | |
1159 | answer = scm_call_2 (closure->hash, obj, scm_from_ulong (n)); | |
a55c2b68 | 1160 | return scm_to_ulong (answer); |
0f2d19dd JB |
1161 | } |
1162 | ||
1163 | ||
1cc91f1b | 1164 | |
0f2d19dd | 1165 | static SCM |
d587c9e8 | 1166 | scm_sloppy_assx (SCM obj, SCM alist, void *arg) |
0f2d19dd | 1167 | { |
d587c9e8 | 1168 | scm_t_ihashx_closure *closure = (scm_t_ihashx_closure *) arg; |
87ca11ff | 1169 | return scm_call_2 (closure->assoc, obj, alist); |
0f2d19dd JB |
1170 | } |
1171 | ||
1172 | ||
a1ec6916 | 1173 | SCM_DEFINE (scm_hashx_get_handle, "hashx-get-handle", 4, 0, 0, |
1e6808ea MG |
1174 | (SCM hash, SCM assoc, SCM table, SCM key), |
1175 | "This behaves the same way as the corresponding\n" | |
1176 | "@code{-get-handle} function, but uses @var{hash} as a hash\n" | |
1177 | "function and @var{assoc} to compare keys. @code{hash} must be\n" | |
1178 | "a function that takes two arguments, a key to be hashed and a\n" | |
d550d22a GB |
1179 | "table size. @code{assoc} must be an associator function, like\n" |
1180 | "@code{assoc}, @code{assq} or @code{assv}.") | |
1bbd0b84 | 1181 | #define FUNC_NAME s_scm_hashx_get_handle |
0f2d19dd | 1182 | { |
92c2555f | 1183 | scm_t_ihashx_closure closure; |
0f2d19dd JB |
1184 | closure.hash = hash; |
1185 | closure.assoc = assoc; | |
1d9c2e62 AW |
1186 | |
1187 | if (SCM_UNLIKELY (SCM_HASHTABLE_P (table) && SCM_HASHTABLE_WEAK_P (table))) | |
1188 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
1189 | ||
1e6808ea | 1190 | return scm_hash_fn_get_handle (table, key, scm_ihashx, scm_sloppy_assx, |
87ca11ff | 1191 | (void *) &closure); |
0f2d19dd | 1192 | } |
1bbd0b84 | 1193 | #undef FUNC_NAME |
0f2d19dd JB |
1194 | |
1195 | ||
a1ec6916 | 1196 | SCM_DEFINE (scm_hashx_create_handle_x, "hashx-create-handle!", 5, 0, 0, |
1e6808ea MG |
1197 | (SCM hash, SCM assoc, SCM table, SCM key, SCM init), |
1198 | "This behaves the same way as the corresponding\n" | |
1199 | "@code{-create-handle} function, but uses @var{hash} as a hash\n" | |
1200 | "function and @var{assoc} to compare keys. @code{hash} must be\n" | |
1201 | "a function that takes two arguments, a key to be hashed and a\n" | |
d550d22a GB |
1202 | "table size. @code{assoc} must be an associator function, like\n" |
1203 | "@code{assoc}, @code{assq} or @code{assv}.") | |
1bbd0b84 | 1204 | #define FUNC_NAME s_scm_hashx_create_handle_x |
0f2d19dd | 1205 | { |
92c2555f | 1206 | scm_t_ihashx_closure closure; |
0f2d19dd JB |
1207 | closure.hash = hash; |
1208 | closure.assoc = assoc; | |
1d9c2e62 AW |
1209 | |
1210 | if (SCM_UNLIKELY (SCM_HASHTABLE_P (table) && SCM_HASHTABLE_WEAK_P (table))) | |
1211 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
1212 | ||
1e6808ea MG |
1213 | return scm_hash_fn_create_handle_x (table, key, init, scm_ihashx, |
1214 | scm_sloppy_assx, (void *)&closure); | |
0f2d19dd | 1215 | } |
1bbd0b84 | 1216 | #undef FUNC_NAME |
0f2d19dd JB |
1217 | |
1218 | ||
1219 | ||
a1ec6916 | 1220 | SCM_DEFINE (scm_hashx_ref, "hashx-ref", 4, 1, 0, |
1e6808ea | 1221 | (SCM hash, SCM assoc, SCM table, SCM key, SCM dflt), |
d550d22a | 1222 | "This behaves the same way as the corresponding @code{ref}\n" |
1e6808ea MG |
1223 | "function, but uses @var{hash} as a hash function and\n" |
1224 | "@var{assoc} to compare keys. @code{hash} must be a function\n" | |
1225 | "that takes two arguments, a key to be hashed and a table size.\n" | |
1226 | "@code{assoc} must be an associator function, like @code{assoc},\n" | |
1227 | "@code{assq} or @code{assv}.\n" | |
1228 | "\n" | |
1229 | "By way of illustration, @code{hashq-ref table key} is\n" | |
1230 | "equivalent to @code{hashx-ref hashq assq table key}.") | |
1bbd0b84 | 1231 | #define FUNC_NAME s_scm_hashx_ref |
0f2d19dd | 1232 | { |
92c2555f | 1233 | scm_t_ihashx_closure closure; |
54778cd3 | 1234 | if (SCM_UNBNDP (dflt)) |
0f2d19dd JB |
1235 | dflt = SCM_BOOL_F; |
1236 | closure.hash = hash; | |
1237 | closure.assoc = assoc; | |
1e6808ea MG |
1238 | return scm_hash_fn_ref (table, key, dflt, scm_ihashx, scm_sloppy_assx, |
1239 | (void *)&closure); | |
0f2d19dd | 1240 | } |
1bbd0b84 | 1241 | #undef FUNC_NAME |
0f2d19dd JB |
1242 | |
1243 | ||
1244 | ||
1245 | ||
a1ec6916 | 1246 | SCM_DEFINE (scm_hashx_set_x, "hashx-set!", 5, 0, 0, |
1e6808ea | 1247 | (SCM hash, SCM assoc, SCM table, SCM key, SCM val), |
d550d22a | 1248 | "This behaves the same way as the corresponding @code{set!}\n" |
1e6808ea MG |
1249 | "function, but uses @var{hash} as a hash function and\n" |
1250 | "@var{assoc} to compare keys. @code{hash} must be a function\n" | |
1251 | "that takes two arguments, a key to be hashed and a table size.\n" | |
1252 | "@code{assoc} must be an associator function, like @code{assoc},\n" | |
1253 | "@code{assq} or @code{assv}.\n" | |
1254 | "\n" | |
1255 | " By way of illustration, @code{hashq-set! table key} is\n" | |
1256 | "equivalent to @code{hashx-set! hashq assq table key}.") | |
1bbd0b84 | 1257 | #define FUNC_NAME s_scm_hashx_set_x |
0f2d19dd | 1258 | { |
92c2555f | 1259 | scm_t_ihashx_closure closure; |
0f2d19dd JB |
1260 | closure.hash = hash; |
1261 | closure.assoc = assoc; | |
1e6808ea MG |
1262 | return scm_hash_fn_set_x (table, key, val, scm_ihashx, scm_sloppy_assx, |
1263 | (void *)&closure); | |
0f2d19dd | 1264 | } |
1bbd0b84 | 1265 | #undef FUNC_NAME |
0f2d19dd | 1266 | |
a9cf5c71 MV |
1267 | SCM_DEFINE (scm_hashx_remove_x, "hashx-remove!", 4, 0, 0, |
1268 | (SCM hash, SCM assoc, SCM table, SCM obj), | |
1269 | "This behaves the same way as the corresponding @code{remove!}\n" | |
1270 | "function, but uses @var{hash} as a hash function and\n" | |
1271 | "@var{assoc} to compare keys. @code{hash} must be a function\n" | |
1272 | "that takes two arguments, a key to be hashed and a table size.\n" | |
1273 | "@code{assoc} must be an associator function, like @code{assoc},\n" | |
1274 | "@code{assq} or @code{assv}.\n" | |
1275 | "\n" | |
1276 | " By way of illustration, @code{hashq-remove! table key} is\n" | |
1277 | "equivalent to @code{hashx-remove! hashq assq #f table key}.") | |
1278 | #define FUNC_NAME s_scm_hashx_remove_x | |
0f2d19dd | 1279 | { |
92c2555f | 1280 | scm_t_ihashx_closure closure; |
0f2d19dd JB |
1281 | closure.hash = hash; |
1282 | closure.assoc = assoc; | |
4cff503f KR |
1283 | return scm_hash_fn_remove_x (table, obj, scm_ihashx, scm_sloppy_assx, |
1284 | (void *) &closure); | |
0f2d19dd | 1285 | } |
a9cf5c71 | 1286 | #undef FUNC_NAME |
0f2d19dd | 1287 | |
711a9fd7 | 1288 | /* Hash table iterators */ |
b94903c2 | 1289 | |
162125af AW |
1290 | SCM_DEFINE (scm_hash_fold, "hash-fold", 3, 0, 0, |
1291 | (SCM proc, SCM init, SCM table), | |
1292 | "An iterator over hash-table elements.\n" | |
1293 | "Accumulates and returns a result by applying PROC successively.\n" | |
1294 | "The arguments to PROC are \"(key value prior-result)\" where key\n" | |
1295 | "and value are successive pairs from the hash table TABLE, and\n" | |
1296 | "prior-result is either INIT (for the first application of PROC)\n" | |
1297 | "or the return value of the previous application of PROC.\n" | |
1298 | "For example, @code{(hash-fold acons '() tab)} will convert a hash\n" | |
1299 | "table into an a-list of key-value pairs.") | |
1300 | #define FUNC_NAME s_scm_hash_fold | |
1301 | { | |
1302 | SCM_VALIDATE_PROC (1, proc); | |
2dd7d8ce | 1303 | SCM_VALIDATE_HASHTABLE (3, table); |
162125af AW |
1304 | return scm_internal_hash_fold ((scm_t_hash_fold_fn) scm_call_3, |
1305 | (void *) SCM_UNPACK (proc), init, table); | |
1306 | } | |
1307 | #undef FUNC_NAME | |
1308 | ||
1309 | static SCM | |
1310 | for_each_proc (void *proc, SCM handle) | |
1311 | { | |
1312 | return scm_call_2 (SCM_PACK (proc), SCM_CAR (handle), SCM_CDR (handle)); | |
1313 | } | |
1314 | ||
1315 | SCM_DEFINE (scm_hash_for_each, "hash-for-each", 2, 0, 0, | |
1316 | (SCM proc, SCM table), | |
1317 | "An iterator over hash-table elements.\n" | |
1318 | "Applies PROC successively on all hash table items.\n" | |
1319 | "The arguments to PROC are \"(key value)\" where key\n" | |
1320 | "and value are successive pairs from the hash table TABLE.") | |
1321 | #define FUNC_NAME s_scm_hash_for_each | |
1322 | { | |
1323 | SCM_VALIDATE_PROC (1, proc); | |
2dd7d8ce | 1324 | SCM_VALIDATE_HASHTABLE (2, table); |
162125af AW |
1325 | |
1326 | scm_internal_hash_for_each_handle (for_each_proc, | |
1327 | (void *) SCM_UNPACK (proc), | |
1328 | table); | |
1329 | return SCM_UNSPECIFIED; | |
1330 | } | |
1331 | #undef FUNC_NAME | |
1332 | ||
1333 | SCM_DEFINE (scm_hash_for_each_handle, "hash-for-each-handle", 2, 0, 0, | |
1334 | (SCM proc, SCM table), | |
1335 | "An iterator over hash-table elements.\n" | |
1336 | "Applies PROC successively on all hash table handles.") | |
1337 | #define FUNC_NAME s_scm_hash_for_each_handle | |
1338 | { | |
1339 | SCM_ASSERT (scm_is_true (scm_procedure_p (proc)), proc, 1, FUNC_NAME); | |
2dd7d8ce | 1340 | SCM_VALIDATE_HASHTABLE (2, table); |
162125af | 1341 | |
1d9c2e62 AW |
1342 | if (SCM_UNLIKELY (SCM_HASHTABLE_WEAK_P (table))) |
1343 | SCM_MISC_ERROR ("Handle access not permitted on weak table", SCM_EOL); | |
1344 | ||
162125af AW |
1345 | scm_internal_hash_for_each_handle ((scm_t_hash_handle_fn) scm_call_1, |
1346 | (void *) SCM_UNPACK (proc), | |
1347 | table); | |
1348 | return SCM_UNSPECIFIED; | |
1349 | } | |
1350 | #undef FUNC_NAME | |
1351 | ||
1352 | static SCM | |
1353 | map_proc (void *proc, SCM key, SCM data, SCM value) | |
1354 | { | |
1355 | return scm_cons (scm_call_2 (SCM_PACK (proc), key, data), value); | |
1356 | } | |
1357 | ||
1358 | SCM_DEFINE (scm_hash_map_to_list, "hash-map->list", 2, 0, 0, | |
1359 | (SCM proc, SCM table), | |
1360 | "An iterator over hash-table elements.\n" | |
1361 | "Accumulates and returns as a list the results of applying PROC successively.\n" | |
1362 | "The arguments to PROC are \"(key value)\" where key\n" | |
1363 | "and value are successive pairs from the hash table TABLE.") | |
1364 | #define FUNC_NAME s_scm_hash_map_to_list | |
1365 | { | |
1366 | SCM_VALIDATE_PROC (1, proc); | |
2dd7d8ce | 1367 | SCM_VALIDATE_HASHTABLE (2, table); |
162125af AW |
1368 | return scm_internal_hash_fold (map_proc, |
1369 | (void *) SCM_UNPACK (proc), | |
1370 | SCM_EOL, | |
1371 | table); | |
1372 | } | |
1373 | #undef FUNC_NAME | |
1374 | ||
3330f00f DH |
1375 | static SCM |
1376 | count_proc (void *pred, SCM key, SCM data, SCM value) | |
1377 | { | |
1378 | if (scm_is_false (scm_call_2 (SCM_PACK (pred), key, data))) | |
1379 | return value; | |
1380 | else | |
1381 | return scm_oneplus(value); | |
1382 | } | |
1383 | ||
1384 | SCM_DEFINE (scm_hash_count, "hash-count", 2, 0, 0, | |
1385 | (SCM pred, SCM table), | |
1386 | "Return the number of elements in the given hash TABLE that\n" | |
1387 | "cause `(PRED KEY VALUE)' to return true. To quickly determine\n" | |
1388 | "the total number of elements, use `(const #t)' for PRED.") | |
1389 | #define FUNC_NAME s_scm_hash_count | |
1390 | { | |
1391 | SCM init; | |
1392 | ||
1393 | SCM_VALIDATE_PROC (1, pred); | |
1394 | SCM_VALIDATE_HASHTABLE (2, table); | |
1395 | ||
1396 | init = scm_from_int (0); | |
1397 | return scm_internal_hash_fold ((scm_t_hash_fold_fn) count_proc, | |
1398 | (void *) SCM_UNPACK (pred), init, table); | |
1399 | } | |
1400 | #undef FUNC_NAME | |
1401 | ||
162125af | 1402 | \f |
c7df61cd MD |
1403 | |
1404 | SCM | |
a07010bf LC |
1405 | scm_internal_hash_fold (scm_t_hash_fold_fn fn, void *closure, |
1406 | SCM init, SCM table) | |
2dd7d8ce | 1407 | #define FUNC_NAME s_scm_hash_fold |
c7df61cd | 1408 | { |
87ca11ff MD |
1409 | long i, n; |
1410 | SCM buckets, result = init; | |
87ca11ff | 1411 | |
2dd7d8ce AW |
1412 | SCM_VALIDATE_HASHTABLE (0, table); |
1413 | buckets = SCM_HASHTABLE_VECTOR (table); | |
0a4c1355 | 1414 | |
3ebc1832 | 1415 | n = SCM_SIMPLE_VECTOR_LENGTH (buckets); |
c7df61cd MD |
1416 | for (i = 0; i < n; ++i) |
1417 | { | |
2187975e | 1418 | SCM ls, handle; |
741e83fc | 1419 | |
2187975e AW |
1420 | for (ls = SCM_SIMPLE_VECTOR_REF (buckets, i); !scm_is_null (ls); |
1421 | ls = SCM_CDR (ls)) | |
c7df61cd | 1422 | { |
c7df61cd | 1423 | handle = SCM_CAR (ls); |
2187975e AW |
1424 | |
1425 | if (SCM_HASHTABLE_WEAK_P (table) && SCM_WEAK_PAIR_DELETED_P (handle)) | |
1426 | /* Don't try to unlink this weak pair, as we're not within | |
1427 | the allocation lock. Instead rely on | |
1428 | vacuum_weak_hash_table to do its job. */ | |
1429 | continue; | |
1430 | else | |
1431 | result = fn (closure, SCM_CAR (handle), SCM_CDR (handle), result); | |
c7df61cd MD |
1432 | } |
1433 | } | |
87ca11ff | 1434 | |
c7df61cd MD |
1435 | return result; |
1436 | } | |
2dd7d8ce | 1437 | #undef FUNC_NAME |
c7df61cd | 1438 | |
711a9fd7 MD |
1439 | /* The following redundant code is here in order to be able to support |
1440 | hash-for-each-handle. An alternative would have been to replace | |
1441 | this code and scm_internal_hash_fold above with a single | |
1442 | scm_internal_hash_fold_handles, but we don't want to promote such | |
1443 | an API. */ | |
1444 | ||
711a9fd7 | 1445 | void |
a07010bf LC |
1446 | scm_internal_hash_for_each_handle (scm_t_hash_handle_fn fn, void *closure, |
1447 | SCM table) | |
2dd7d8ce | 1448 | #define FUNC_NAME s_scm_hash_for_each |
711a9fd7 MD |
1449 | { |
1450 | long i, n; | |
1451 | SCM buckets; | |
1452 | ||
2dd7d8ce AW |
1453 | SCM_VALIDATE_HASHTABLE (0, table); |
1454 | buckets = SCM_HASHTABLE_VECTOR (table); | |
3ebc1832 | 1455 | n = SCM_SIMPLE_VECTOR_LENGTH (buckets); |
2dd7d8ce | 1456 | |
711a9fd7 MD |
1457 | for (i = 0; i < n; ++i) |
1458 | { | |
3ebc1832 | 1459 | SCM ls = SCM_SIMPLE_VECTOR_REF (buckets, i), handle; |
d2e53ed6 | 1460 | while (!scm_is_null (ls)) |
711a9fd7 | 1461 | { |
d2e53ed6 | 1462 | if (!scm_is_pair (ls)) |
2dd7d8ce | 1463 | SCM_WRONG_TYPE_ARG (SCM_ARG3, buckets); |
711a9fd7 | 1464 | handle = SCM_CAR (ls); |
d2e53ed6 | 1465 | if (!scm_is_pair (handle)) |
2dd7d8ce | 1466 | SCM_WRONG_TYPE_ARG (SCM_ARG3, buckets); |
c6a2691f DT |
1467 | if (!SCM_HASHTABLE_WEAK_P (table) |
1468 | || !SCM_WEAK_PAIR_DELETED_P (handle)) | |
1469 | fn (closure, handle); | |
711a9fd7 MD |
1470 | ls = SCM_CDR (ls); |
1471 | } | |
1472 | } | |
1473 | } | |
2dd7d8ce | 1474 | #undef FUNC_NAME |
711a9fd7 | 1475 | |
0f2d19dd JB |
1476 | \f |
1477 | ||
1cc91f1b | 1478 | |
c35738c1 MD |
1479 | void |
1480 | scm_init_hashtab () | |
1481 | { | |
a0599745 | 1482 | #include "libguile/hashtab.x" |
0f2d19dd | 1483 | } |
89e00824 ML |
1484 | |
1485 | /* | |
1486 | Local Variables: | |
1487 | c-file-style: "gnu" | |
1488 | End: | |
1489 | */ |