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