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