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