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