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