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