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