Commit | Line | Data |
---|---|---|
fb8b2a9d | 1 | /* Copyright (C) 1995, 1996, 1998, 1999, 2000, 2001, 2003, 2004, 2006, |
789dd40b | 2 | * 2008, 2009, 2010, 2011, 2012, 2013 Free Software Foundation, Inc. |
fb8b2a9d | 3 | * |
73be1d9e | 4 | * This library is free software; you can redistribute it and/or |
53befeb7 NJ |
5 | * modify it under the terms of the GNU Lesser General Public License |
6 | * as published by the Free Software Foundation; either version 3 of | |
7 | * the License, or (at your option) any later version. | |
0f2d19dd | 8 | * |
53befeb7 NJ |
9 | * This library is distributed in the hope that it will be useful, but |
10 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
73be1d9e MV |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | * Lesser General Public License for more details. | |
0f2d19dd | 13 | * |
73be1d9e MV |
14 | * You should have received a copy of the GNU Lesser General Public |
15 | * License along with this library; if not, write to the Free Software | |
53befeb7 NJ |
16 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
17 | * 02110-1301 USA | |
73be1d9e | 18 | */ |
1bbd0b84 | 19 | |
1bbd0b84 | 20 | |
0f2d19dd | 21 | \f |
dbb605f5 LC |
22 | #ifdef HAVE_CONFIG_H |
23 | # include <config.h> | |
24 | #endif | |
0f2d19dd | 25 | |
cdd47ec7 | 26 | #include <alloca.h> |
06c1d900 | 27 | #include <stdio.h> |
63229905 | 28 | #include <assert.h> |
06c1d900 | 29 | |
a0599745 MD |
30 | #include "libguile/_scm.h" |
31 | #include "libguile/alist.h" | |
32 | #include "libguile/hash.h" | |
33 | #include "libguile/eval.h" | |
fdc28395 | 34 | #include "libguile/root.h" |
a0599745 | 35 | #include "libguile/vectors.h" |
f59a096e | 36 | #include "libguile/ports.h" |
62c290e9 | 37 | #include "libguile/bdw-gc.h" |
a0599745 MD |
38 | |
39 | #include "libguile/validate.h" | |
40 | #include "libguile/hashtab.h" | |
e4d21e6b | 41 | |
e4d21e6b | 42 | |
0f2d19dd JB |
43 | \f |
44 | ||
c99de5aa | 45 | /* A hash table is a cell containing a vector of association lists. |
c35738c1 MD |
46 | * |
47 | * Growing or shrinking, with following rehashing, is triggered when | |
48 | * the load factor | |
49 | * | |
50 | * L = N / S (N: number of items in table, S: bucket vector length) | |
51 | * | |
52 | * passes an upper limit of 0.9 or a lower limit of 0.25. | |
53 | * | |
54 | * The implementation stores the upper and lower number of items which | |
55 | * trigger a resize in the hashtable object. | |
56 | * | |
57 | * Possible hash table sizes (primes) are stored in the array | |
58 | * hashtable_size. | |
f59a096e MD |
59 | */ |
60 | ||
0a4c1355 MD |
61 | static unsigned long hashtable_size[] = { |
62 | 31, 61, 113, 223, 443, 883, 1759, 3517, 7027, 14051, 28099, 56197, 112363, | |
93777082 | 63 | 224717, 449419, 898823, 1797641, 3595271, 7190537, 14381041 |
328255e4 AW |
64 | #if SIZEOF_SCM_T_BITS > 4 |
65 | /* vector lengths are stored in the first word of vectors, shifted by | |
66 | 8 bits for the tc8, so for 32-bit we only get 2^24-1 = 16777215 | |
67 | elements. But we allow a few more sizes for 64-bit. */ | |
68 | , 28762081, 57524111, 115048217, 230096423, 460192829 | |
93777082 | 69 | #endif |
f59a096e MD |
70 | }; |
71 | ||
93777082 MV |
72 | #define HASHTABLE_SIZE_N (sizeof(hashtable_size)/sizeof(unsigned long)) |
73 | ||
f59a096e MD |
74 | static char *s_hashtable = "hashtable"; |
75 | ||
3a2de079 | 76 | static SCM |
54a9b981 | 77 | make_hash_table (unsigned long k, const char *func_name) |
a9cf5c71 | 78 | { |
c99de5aa | 79 | SCM vector; |
9358af6a | 80 | scm_t_hashtable *t; |
110beb83 | 81 | int i = 0, n = k ? k : 31; |
7c888dfa | 82 | while (i + 1 < HASHTABLE_SIZE_N && n > hashtable_size[i]) |
110beb83 MD |
83 | ++i; |
84 | n = hashtable_size[i]; | |
3a2de079 | 85 | |
3a2de079 LC |
86 | vector = scm_c_make_vector (n, SCM_EOL); |
87 | ||
88 | t = scm_gc_malloc_pointerless (sizeof (*t), s_hashtable); | |
c35738c1 | 89 | t->min_size_index = t->size_index = i; |
f59a096e | 90 | t->n_items = 0; |
c35738c1 | 91 | t->lower = 0; |
110beb83 | 92 | t->upper = 9 * n / 10; |
c6a35e35 | 93 | |
c99de5aa AW |
94 | /* FIXME: we just need two words of storage, not three */ |
95 | return scm_double_cell (scm_tc7_hashtable, SCM_UNPACK (vector), | |
96 | (scm_t_bits)t, 0); | |
f59a096e MD |
97 | } |
98 | ||
c35738c1 MD |
99 | void |
100 | scm_i_rehash (SCM table, | |
f044da55 | 101 | scm_t_hash_fn hash_fn, |
c35738c1 MD |
102 | void *closure, |
103 | const char* func_name) | |
104 | { | |
105 | SCM buckets, new_buckets; | |
106 | int i; | |
107 | unsigned long old_size; | |
108 | unsigned long new_size; | |
109 | ||
110 | if (SCM_HASHTABLE_N_ITEMS (table) < SCM_HASHTABLE_LOWER (table)) | |
111 | { | |
112 | /* rehashing is not triggered when i <= min_size */ | |
113 | i = SCM_HASHTABLE (table)->size_index; | |
114 | do | |
115 | --i; | |
116 | while (i > SCM_HASHTABLE (table)->min_size_index | |
117 | && SCM_HASHTABLE_N_ITEMS (table) < hashtable_size[i] / 4); | |
118 | } | |
119 | else | |
120 | { | |
121 | i = SCM_HASHTABLE (table)->size_index + 1; | |
122 | if (i >= HASHTABLE_SIZE_N) | |
123 | /* don't rehash */ | |
124 | return; | |
c35738c1 MD |
125 | } |
126 | SCM_HASHTABLE (table)->size_index = i; | |
76da80e7 | 127 | |
c35738c1 MD |
128 | new_size = hashtable_size[i]; |
129 | if (i <= SCM_HASHTABLE (table)->min_size_index) | |
130 | SCM_HASHTABLE (table)->lower = 0; | |
131 | else | |
132 | SCM_HASHTABLE (table)->lower = new_size / 4; | |
133 | SCM_HASHTABLE (table)->upper = 9 * new_size / 10; | |
134 | buckets = SCM_HASHTABLE_VECTOR (table); | |
3a2de079 LC |
135 | |
136 | new_buckets = scm_c_make_vector (new_size, SCM_EOL); | |
c35738c1 | 137 | |
bc6580eb MV |
138 | SCM_SET_HASHTABLE_VECTOR (table, new_buckets); |
139 | SCM_SET_HASHTABLE_N_ITEMS (table, 0); | |
bc6580eb | 140 | |
3ebc1832 | 141 | old_size = SCM_SIMPLE_VECTOR_LENGTH (buckets); |
c35738c1 MD |
142 | for (i = 0; i < old_size; ++i) |
143 | { | |
bc6580eb MV |
144 | SCM ls, cell, handle; |
145 | ||
146 | ls = SCM_SIMPLE_VECTOR_REF (buckets, i); | |
c2f21af5 MV |
147 | SCM_SIMPLE_VECTOR_SET (buckets, i, SCM_EOL); |
148 | ||
bc6580eb | 149 | while (scm_is_pair (ls)) |
c35738c1 MD |
150 | { |
151 | unsigned long h; | |
c6a35e35 | 152 | |
bc6580eb MV |
153 | cell = ls; |
154 | handle = SCM_CAR (cell); | |
155 | ls = SCM_CDR (ls); | |
c6a35e35 | 156 | |
c35738c1 MD |
157 | h = hash_fn (SCM_CAR (handle), new_size, closure); |
158 | if (h >= new_size) | |
b9bd8526 | 159 | scm_out_of_range (func_name, scm_from_ulong (h)); |
bc6580eb MV |
160 | SCM_SETCDR (cell, SCM_SIMPLE_VECTOR_REF (new_buckets, h)); |
161 | SCM_SIMPLE_VECTOR_SET (new_buckets, h, cell); | |
162 | SCM_HASHTABLE_INCREMENT (table); | |
c35738c1 MD |
163 | } |
164 | } | |
c35738c1 MD |
165 | } |
166 | ||
167 | ||
c99de5aa AW |
168 | void |
169 | scm_i_hashtable_print (SCM exp, SCM port, scm_print_state *pstate) | |
f59a096e | 170 | { |
0607ebbf | 171 | scm_puts_unlocked ("#<hash-table ", port); |
73c080f9 | 172 | scm_uintprint (SCM_UNPACK (exp), 16, port); |
fb8b2a9d | 173 | scm_putc (' ', port); |
06c1d900 | 174 | scm_uintprint (SCM_HASHTABLE_N_ITEMS (exp), 10, port); |
0607ebbf | 175 | scm_putc_unlocked ('/', port); |
3ebc1832 MV |
176 | scm_uintprint (SCM_SIMPLE_VECTOR_LENGTH (SCM_HASHTABLE_VECTOR (exp)), |
177 | 10, port); | |
0607ebbf | 178 | scm_puts_unlocked (">", port); |
c99de5aa AW |
179 | } |
180 | ||
f59a096e | 181 | |
00ffa0e7 | 182 | SCM |
c014a02e | 183 | scm_c_make_hash_table (unsigned long k) |
00ffa0e7 | 184 | { |
54a9b981 | 185 | return make_hash_table (k, "scm_c_make_hash_table"); |
f59a096e MD |
186 | } |
187 | ||
188 | SCM_DEFINE (scm_make_hash_table, "make-hash-table", 0, 1, 0, | |
189 | (SCM n), | |
a9cf5c71 | 190 | "Make a new abstract hash table object with minimum number of buckets @var{n}\n") |
f59a096e MD |
191 | #define FUNC_NAME s_scm_make_hash_table |
192 | { | |
54a9b981 | 193 | return make_hash_table (SCM_UNBNDP (n) ? 0 : scm_to_ulong (n), FUNC_NAME); |
f59a096e | 194 | } |
c35738c1 MD |
195 | #undef FUNC_NAME |
196 | ||
54a9b981 | 197 | #define SCM_WEAK_TABLE_P(x) (scm_is_true (scm_weak_table_p (x))) |
c35738c1 MD |
198 | |
199 | SCM_DEFINE (scm_hash_table_p, "hash-table?", 1, 0, 0, | |
200 | (SCM obj), | |
a9cf5c71 | 201 | "Return @code{#t} if @var{obj} is an abstract hash table object.") |
c35738c1 MD |
202 | #define FUNC_NAME s_scm_hash_table_p |
203 | { | |
54a9b981 | 204 | return scm_from_bool (SCM_HASHTABLE_P (obj) || SCM_WEAK_TABLE_P (obj)); |
c35738c1 MD |
205 | } |
206 | #undef FUNC_NAME | |
207 | ||
3330f00f | 208 | |
d587c9e8 LC |
209 | \f |
210 | /* Accessing hash table entries. */ | |
22a52da1 | 211 | |
0f2d19dd | 212 | SCM |
d587c9e8 LC |
213 | scm_hash_fn_get_handle (SCM table, SCM obj, |
214 | scm_t_hash_fn hash_fn, scm_t_assoc_fn assoc_fn, | |
215 | void * closure) | |
22a52da1 | 216 | #define FUNC_NAME "scm_hash_fn_get_handle" |
0f2d19dd | 217 | { |
c014a02e | 218 | unsigned long k; |
63229905 | 219 | SCM buckets, h; |
0f2d19dd | 220 | |
f0554ee7 AW |
221 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); |
222 | buckets = SCM_HASHTABLE_VECTOR (table); | |
d9c82e20 LC |
223 | |
224 | if (SCM_SIMPLE_VECTOR_LENGTH (buckets) == 0) | |
22a52da1 | 225 | return SCM_BOOL_F; |
d9c82e20 LC |
226 | k = hash_fn (obj, SCM_SIMPLE_VECTOR_LENGTH (buckets), closure); |
227 | if (k >= SCM_SIMPLE_VECTOR_LENGTH (buckets)) | |
f0554ee7 | 228 | scm_out_of_range (FUNC_NAME, scm_from_ulong (k)); |
3a2de079 | 229 | |
54a9b981 | 230 | h = assoc_fn (obj, SCM_SIMPLE_VECTOR_REF (buckets, k), closure); |
6efbc280 AW |
231 | |
232 | return h; | |
233 | } | |
234 | #undef FUNC_NAME | |
235 | ||
236 | ||
0f2d19dd | 237 | SCM |
f044da55 LC |
238 | scm_hash_fn_create_handle_x (SCM table, SCM obj, SCM init, |
239 | scm_t_hash_fn hash_fn, scm_t_assoc_fn assoc_fn, | |
240 | void * closure) | |
cbaadf02 | 241 | #define FUNC_NAME "scm_hash_fn_create_handle_x" |
0f2d19dd | 242 | { |
c014a02e | 243 | unsigned long k; |
63229905 | 244 | SCM buckets, it; |
0f2d19dd | 245 | |
f0554ee7 AW |
246 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); |
247 | buckets = SCM_HASHTABLE_VECTOR (table); | |
248 | ||
3ebc1832 | 249 | if (SCM_SIMPLE_VECTOR_LENGTH (buckets) == 0) |
cbaadf02 DH |
250 | SCM_MISC_ERROR ("void hashtable", SCM_EOL); |
251 | ||
3ebc1832 MV |
252 | k = hash_fn (obj, SCM_SIMPLE_VECTOR_LENGTH (buckets), closure); |
253 | if (k >= SCM_SIMPLE_VECTOR_LENGTH (buckets)) | |
b9bd8526 | 254 | scm_out_of_range ("hash_fn_create_handle_x", scm_from_ulong (k)); |
3a2de079 | 255 | |
54a9b981 | 256 | it = assoc_fn (obj, SCM_SIMPLE_VECTOR_REF (buckets, k), closure); |
e4d21e6b | 257 | |
0306509b | 258 | if (scm_is_pair (it)) |
0a4c1355 | 259 | return it; |
15bd90ea NJ |
260 | else if (scm_is_true (it)) |
261 | scm_wrong_type_arg_msg (NULL, 0, it, "a pair"); | |
ee083ac2 DH |
262 | else |
263 | { | |
3a2de079 LC |
264 | SCM handle, new_bucket; |
265 | ||
54a9b981 | 266 | handle = scm_cons (obj, init); |
3a2de079 LC |
267 | new_bucket = scm_cons (handle, SCM_EOL); |
268 | ||
f0554ee7 | 269 | if (!scm_is_eq (SCM_HASHTABLE_VECTOR (table), buckets)) |
5b582466 MV |
270 | { |
271 | buckets = SCM_HASHTABLE_VECTOR (table); | |
272 | k = hash_fn (obj, SCM_SIMPLE_VECTOR_LENGTH (buckets), closure); | |
273 | if (k >= SCM_SIMPLE_VECTOR_LENGTH (buckets)) | |
274 | scm_out_of_range ("hash_fn_create_handle_x", scm_from_ulong (k)); | |
275 | } | |
bc6580eb | 276 | SCM_SETCDR (new_bucket, SCM_SIMPLE_VECTOR_REF (buckets, k)); |
3ebc1832 | 277 | SCM_SIMPLE_VECTOR_SET (buckets, k, new_bucket); |
f0554ee7 | 278 | SCM_HASHTABLE_INCREMENT (table); |
40d2a007 | 279 | |
62c290e9 | 280 | /* Maybe rehash the table. */ |
f0554ee7 AW |
281 | if (SCM_HASHTABLE_N_ITEMS (table) < SCM_HASHTABLE_LOWER (table) |
282 | || SCM_HASHTABLE_N_ITEMS (table) > SCM_HASHTABLE_UPPER (table)) | |
283 | scm_i_rehash (table, hash_fn, closure, FUNC_NAME); | |
ee083ac2 DH |
284 | return SCM_CAR (new_bucket); |
285 | } | |
0f2d19dd | 286 | } |
cbaadf02 | 287 | #undef FUNC_NAME |
0f2d19dd | 288 | |
1cc91f1b | 289 | |
f044da55 LC |
290 | SCM |
291 | scm_hash_fn_ref (SCM table, SCM obj, SCM dflt, | |
292 | scm_t_hash_fn hash_fn, scm_t_assoc_fn assoc_fn, | |
293 | void *closure) | |
0f2d19dd | 294 | { |
22a52da1 | 295 | SCM it = scm_hash_fn_get_handle (table, obj, hash_fn, assoc_fn, closure); |
d2e53ed6 | 296 | if (scm_is_pair (it)) |
0f2d19dd | 297 | return SCM_CDR (it); |
22a52da1 DH |
298 | else |
299 | return dflt; | |
0f2d19dd JB |
300 | } |
301 | ||
f044da55 LC |
302 | SCM |
303 | scm_hash_fn_set_x (SCM table, SCM obj, SCM val, | |
304 | scm_t_hash_fn hash_fn, scm_t_assoc_fn assoc_fn, | |
305 | void *closure) | |
0f2d19dd | 306 | { |
ecc9d1b5 | 307 | SCM pair; |
0f2d19dd | 308 | |
ecc9d1b5 AW |
309 | pair = scm_hash_fn_create_handle_x (table, obj, val, |
310 | hash_fn, assoc_fn, closure); | |
5a99a574 | 311 | |
636c99d4 | 312 | if (!scm_is_eq (SCM_CDR (pair), val)) |
54a9b981 | 313 | SCM_SETCDR (pair, val); |
ecc9d1b5 | 314 | |
0f2d19dd JB |
315 | return val; |
316 | } | |
317 | ||
318 | ||
d9c82e20 | 319 | SCM |
a9cf5c71 | 320 | scm_hash_fn_remove_x (SCM table, SCM obj, |
f044da55 LC |
321 | scm_t_hash_fn hash_fn, |
322 | scm_t_assoc_fn assoc_fn, | |
a9cf5c71 | 323 | void *closure) |
f0554ee7 | 324 | #define FUNC_NAME "hash_fn_remove_x" |
0f2d19dd | 325 | { |
c014a02e | 326 | unsigned long k; |
63229905 | 327 | SCM buckets, h; |
0f2d19dd | 328 | |
f0554ee7 AW |
329 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); |
330 | ||
331 | buckets = SCM_HASHTABLE_VECTOR (table); | |
332 | ||
c99de5aa | 333 | if (SCM_SIMPLE_VECTOR_LENGTH (buckets) == 0) |
0f2d19dd | 334 | return SCM_EOL; |
87ca11ff | 335 | |
3ebc1832 MV |
336 | k = hash_fn (obj, SCM_SIMPLE_VECTOR_LENGTH (buckets), closure); |
337 | if (k >= SCM_SIMPLE_VECTOR_LENGTH (buckets)) | |
f0554ee7 | 338 | scm_out_of_range (FUNC_NAME, scm_from_ulong (k)); |
3a2de079 | 339 | |
54a9b981 | 340 | h = assoc_fn (obj, SCM_SIMPLE_VECTOR_REF (buckets, k), closure); |
e4d21e6b | 341 | |
7888309b | 342 | if (scm_is_true (h)) |
87ca11ff | 343 | { |
3ebc1832 | 344 | SCM_SIMPLE_VECTOR_SET |
a9cf5c71 | 345 | (buckets, k, scm_delq_x (h, SCM_SIMPLE_VECTOR_REF (buckets, k))); |
f0554ee7 AW |
346 | SCM_HASHTABLE_DECREMENT (table); |
347 | if (SCM_HASHTABLE_N_ITEMS (table) < SCM_HASHTABLE_LOWER (table)) | |
348 | scm_i_rehash (table, hash_fn, closure, FUNC_NAME); | |
87ca11ff | 349 | } |
0f2d19dd JB |
350 | return h; |
351 | } | |
f0554ee7 | 352 | #undef FUNC_NAME |
0f2d19dd | 353 | |
c35738c1 MD |
354 | SCM_DEFINE (scm_hash_clear_x, "hash-clear!", 1, 0, 0, |
355 | (SCM table), | |
a9cf5c71 | 356 | "Remove all items from @var{table} (without triggering a resize).") |
c35738c1 MD |
357 | #define FUNC_NAME s_scm_hash_clear_x |
358 | { | |
54a9b981 | 359 | if (SCM_WEAK_TABLE_P (table)) |
07e69928 AW |
360 | { |
361 | scm_weak_table_clear_x (table); | |
362 | return SCM_UNSPECIFIED; | |
363 | } | |
54a9b981 | 364 | |
f0554ee7 AW |
365 | SCM_VALIDATE_HASHTABLE (SCM_ARG1, table); |
366 | ||
367 | scm_vector_fill_x (SCM_HASHTABLE_VECTOR (table), SCM_EOL); | |
368 | SCM_SET_HASHTABLE_N_ITEMS (table, 0); | |
369 | ||
c35738c1 MD |
370 | return SCM_UNSPECIFIED; |
371 | } | |
372 | #undef FUNC_NAME | |
0f2d19dd JB |
373 | |
374 | \f | |
375 | ||
a1ec6916 | 376 | SCM_DEFINE (scm_hashq_get_handle, "hashq-get-handle", 2, 0, 0, |
22a52da1 DH |
377 | (SCM table, SCM key), |
378 | "This procedure returns the @code{(key . value)} pair from the\n" | |
379 | "hash table @var{table}. If @var{table} does not hold an\n" | |
380 | "associated value for @var{key}, @code{#f} is returned.\n" | |
381 | "Uses @code{eq?} for equality testing.") | |
1bbd0b84 | 382 | #define FUNC_NAME s_scm_hashq_get_handle |
0f2d19dd | 383 | { |
d587c9e8 LC |
384 | return scm_hash_fn_get_handle (table, key, |
385 | (scm_t_hash_fn) scm_ihashq, | |
386 | (scm_t_assoc_fn) scm_sloppy_assq, | |
387 | 0); | |
0f2d19dd | 388 | } |
1bbd0b84 | 389 | #undef FUNC_NAME |
0f2d19dd JB |
390 | |
391 | ||
a1ec6916 | 392 | SCM_DEFINE (scm_hashq_create_handle_x, "hashq-create-handle!", 3, 0, 0, |
d550d22a GB |
393 | (SCM table, SCM key, SCM init), |
394 | "This function looks up @var{key} in @var{table} and returns its handle.\n" | |
b380b885 MD |
395 | "If @var{key} is not already present, a new handle is created which\n" |
396 | "associates @var{key} with @var{init}.") | |
1bbd0b84 | 397 | #define FUNC_NAME s_scm_hashq_create_handle_x |
0f2d19dd | 398 | { |
d587c9e8 LC |
399 | return scm_hash_fn_create_handle_x (table, key, init, |
400 | (scm_t_hash_fn) scm_ihashq, | |
401 | (scm_t_assoc_fn) scm_sloppy_assq, | |
402 | 0); | |
0f2d19dd | 403 | } |
1bbd0b84 | 404 | #undef FUNC_NAME |
0f2d19dd JB |
405 | |
406 | ||
a1ec6916 | 407 | SCM_DEFINE (scm_hashq_ref, "hashq-ref", 2, 1, 0, |
1e6808ea | 408 | (SCM table, SCM key, SCM dflt), |
b380b885 MD |
409 | "Look up @var{key} in the hash table @var{table}, and return the\n" |
410 | "value (if any) associated with it. If @var{key} is not found,\n" | |
b7e64f8b | 411 | "return @var{dflt} (or @code{#f} if no @var{dflt} argument\n" |
5352393c | 412 | "is supplied). Uses @code{eq?} for equality testing.") |
1bbd0b84 | 413 | #define FUNC_NAME s_scm_hashq_ref |
0f2d19dd | 414 | { |
54778cd3 | 415 | if (SCM_UNBNDP (dflt)) |
0f2d19dd | 416 | dflt = SCM_BOOL_F; |
54a9b981 AW |
417 | |
418 | if (SCM_WEAK_TABLE_P (table)) | |
419 | return scm_weak_table_refq (table, key, dflt); | |
420 | ||
d587c9e8 LC |
421 | return scm_hash_fn_ref (table, key, dflt, |
422 | (scm_t_hash_fn) scm_ihashq, | |
423 | (scm_t_assoc_fn) scm_sloppy_assq, | |
424 | 0); | |
0f2d19dd | 425 | } |
1bbd0b84 | 426 | #undef FUNC_NAME |
0f2d19dd JB |
427 | |
428 | ||
429 | ||
a1ec6916 | 430 | SCM_DEFINE (scm_hashq_set_x, "hashq-set!", 3, 0, 0, |
1e6808ea | 431 | (SCM table, SCM key, SCM val), |
5352393c | 432 | "Find the entry in @var{table} associated with @var{key}, and\n" |
b7e64f8b | 433 | "store @var{val} there. Uses @code{eq?} for equality testing.") |
1bbd0b84 | 434 | #define FUNC_NAME s_scm_hashq_set_x |
0f2d19dd | 435 | { |
54a9b981 | 436 | if (SCM_WEAK_TABLE_P (table)) |
07e69928 AW |
437 | { |
438 | scm_weak_table_putq_x (table, key, val); | |
439 | return val; | |
440 | } | |
54a9b981 | 441 | |
d587c9e8 LC |
442 | return scm_hash_fn_set_x (table, key, val, |
443 | (scm_t_hash_fn) scm_ihashq, | |
444 | (scm_t_assoc_fn) scm_sloppy_assq, | |
445 | 0); | |
0f2d19dd | 446 | } |
1bbd0b84 | 447 | #undef FUNC_NAME |
0f2d19dd JB |
448 | |
449 | ||
450 | ||
a1ec6916 | 451 | SCM_DEFINE (scm_hashq_remove_x, "hashq-remove!", 2, 0, 0, |
1e6808ea | 452 | (SCM table, SCM key), |
5352393c MG |
453 | "Remove @var{key} (and any value associated with it) from\n" |
454 | "@var{table}. Uses @code{eq?} for equality tests.") | |
1bbd0b84 | 455 | #define FUNC_NAME s_scm_hashq_remove_x |
0f2d19dd | 456 | { |
54a9b981 | 457 | if (SCM_WEAK_TABLE_P (table)) |
07e69928 AW |
458 | { |
459 | scm_weak_table_remq_x (table, key); | |
460 | /* This return value is for historical compatibility with | |
461 | hash-remove!, which returns either the "handle" corresponding | |
462 | to the entry, or #f. Since weak tables don't have handles, we | |
463 | have to return #f. */ | |
464 | return SCM_BOOL_F; | |
465 | } | |
54a9b981 | 466 | |
d587c9e8 LC |
467 | return scm_hash_fn_remove_x (table, key, |
468 | (scm_t_hash_fn) scm_ihashq, | |
469 | (scm_t_assoc_fn) scm_sloppy_assq, | |
470 | 0); | |
0f2d19dd | 471 | } |
1bbd0b84 | 472 | #undef FUNC_NAME |
0f2d19dd JB |
473 | |
474 | ||
475 | \f | |
476 | ||
a1ec6916 | 477 | SCM_DEFINE (scm_hashv_get_handle, "hashv-get-handle", 2, 0, 0, |
22a52da1 DH |
478 | (SCM table, SCM key), |
479 | "This procedure returns the @code{(key . value)} pair from the\n" | |
480 | "hash table @var{table}. If @var{table} does not hold an\n" | |
481 | "associated value for @var{key}, @code{#f} is returned.\n" | |
482 | "Uses @code{eqv?} for equality testing.") | |
1bbd0b84 | 483 | #define FUNC_NAME s_scm_hashv_get_handle |
0f2d19dd | 484 | { |
d587c9e8 LC |
485 | return scm_hash_fn_get_handle (table, key, |
486 | (scm_t_hash_fn) scm_ihashv, | |
487 | (scm_t_assoc_fn) scm_sloppy_assv, | |
488 | 0); | |
0f2d19dd | 489 | } |
1bbd0b84 | 490 | #undef FUNC_NAME |
0f2d19dd JB |
491 | |
492 | ||
a1ec6916 | 493 | SCM_DEFINE (scm_hashv_create_handle_x, "hashv-create-handle!", 3, 0, 0, |
d550d22a GB |
494 | (SCM table, SCM key, SCM init), |
495 | "This function looks up @var{key} in @var{table} and returns its handle.\n" | |
496 | "If @var{key} is not already present, a new handle is created which\n" | |
497 | "associates @var{key} with @var{init}.") | |
1bbd0b84 | 498 | #define FUNC_NAME s_scm_hashv_create_handle_x |
0f2d19dd | 499 | { |
d587c9e8 LC |
500 | return scm_hash_fn_create_handle_x (table, key, init, |
501 | (scm_t_hash_fn) scm_ihashv, | |
502 | (scm_t_assoc_fn) scm_sloppy_assv, | |
503 | 0); | |
0f2d19dd | 504 | } |
1bbd0b84 | 505 | #undef FUNC_NAME |
0f2d19dd JB |
506 | |
507 | ||
54a9b981 AW |
508 | static int |
509 | assv_predicate (SCM k, SCM v, void *closure) | |
510 | { | |
21041372 | 511 | return scm_is_true (scm_eqv_p (k, SCM_PACK_POINTER (closure))); |
54a9b981 AW |
512 | } |
513 | ||
a1ec6916 | 514 | SCM_DEFINE (scm_hashv_ref, "hashv-ref", 2, 1, 0, |
1e6808ea | 515 | (SCM table, SCM key, SCM dflt), |
d550d22a GB |
516 | "Look up @var{key} in the hash table @var{table}, and return the\n" |
517 | "value (if any) associated with it. If @var{key} is not found,\n" | |
b7e64f8b | 518 | "return @var{dflt} (or @code{#f} if no @var{dflt} argument\n" |
5352393c | 519 | "is supplied). Uses @code{eqv?} for equality testing.") |
1bbd0b84 | 520 | #define FUNC_NAME s_scm_hashv_ref |
0f2d19dd | 521 | { |
54778cd3 | 522 | if (SCM_UNBNDP (dflt)) |
0f2d19dd | 523 | dflt = SCM_BOOL_F; |
54a9b981 AW |
524 | |
525 | if (SCM_WEAK_TABLE_P (table)) | |
526 | return scm_c_weak_table_ref (table, scm_ihashv (key, -1), | |
789dd40b MW |
527 | assv_predicate, |
528 | (void *) SCM_UNPACK (key), dflt); | |
54a9b981 | 529 | |
d587c9e8 LC |
530 | return scm_hash_fn_ref (table, key, dflt, |
531 | (scm_t_hash_fn) scm_ihashv, | |
532 | (scm_t_assoc_fn) scm_sloppy_assv, | |
533 | 0); | |
0f2d19dd | 534 | } |
1bbd0b84 | 535 | #undef FUNC_NAME |
0f2d19dd JB |
536 | |
537 | ||
538 | ||
a1ec6916 | 539 | SCM_DEFINE (scm_hashv_set_x, "hashv-set!", 3, 0, 0, |
1e6808ea | 540 | (SCM table, SCM key, SCM val), |
5352393c MG |
541 | "Find the entry in @var{table} associated with @var{key}, and\n" |
542 | "store @var{value} there. Uses @code{eqv?} for equality testing.") | |
1bbd0b84 | 543 | #define FUNC_NAME s_scm_hashv_set_x |
0f2d19dd | 544 | { |
54a9b981 AW |
545 | if (SCM_WEAK_TABLE_P (table)) |
546 | { | |
547 | scm_c_weak_table_put_x (table, scm_ihashv (key, -1), | |
789dd40b | 548 | assv_predicate, (void *) SCM_UNPACK (key), |
54a9b981 | 549 | key, val); |
07e69928 | 550 | return val; |
54a9b981 AW |
551 | } |
552 | ||
d587c9e8 LC |
553 | return scm_hash_fn_set_x (table, key, val, |
554 | (scm_t_hash_fn) scm_ihashv, | |
555 | (scm_t_assoc_fn) scm_sloppy_assv, | |
556 | 0); | |
0f2d19dd | 557 | } |
1bbd0b84 | 558 | #undef FUNC_NAME |
0f2d19dd JB |
559 | |
560 | ||
a1ec6916 | 561 | SCM_DEFINE (scm_hashv_remove_x, "hashv-remove!", 2, 0, 0, |
1e6808ea | 562 | (SCM table, SCM key), |
5352393c MG |
563 | "Remove @var{key} (and any value associated with it) from\n" |
564 | "@var{table}. Uses @code{eqv?} for equality tests.") | |
1bbd0b84 | 565 | #define FUNC_NAME s_scm_hashv_remove_x |
0f2d19dd | 566 | { |
54a9b981 AW |
567 | if (SCM_WEAK_TABLE_P (table)) |
568 | { | |
569 | scm_c_weak_table_remove_x (table, scm_ihashv (key, -1), | |
789dd40b | 570 | assv_predicate, (void *) SCM_UNPACK (key)); |
07e69928 AW |
571 | /* See note in hashq-remove!. */ |
572 | return SCM_BOOL_F; | |
54a9b981 AW |
573 | } |
574 | ||
d587c9e8 LC |
575 | return scm_hash_fn_remove_x (table, key, |
576 | (scm_t_hash_fn) scm_ihashv, | |
577 | (scm_t_assoc_fn) scm_sloppy_assv, | |
578 | 0); | |
0f2d19dd | 579 | } |
1bbd0b84 | 580 | #undef FUNC_NAME |
0f2d19dd JB |
581 | |
582 | \f | |
583 | ||
a1ec6916 | 584 | SCM_DEFINE (scm_hash_get_handle, "hash-get-handle", 2, 0, 0, |
22a52da1 DH |
585 | (SCM table, SCM key), |
586 | "This procedure returns the @code{(key . value)} pair from the\n" | |
587 | "hash table @var{table}. If @var{table} does not hold an\n" | |
588 | "associated value for @var{key}, @code{#f} is returned.\n" | |
589 | "Uses @code{equal?} for equality testing.") | |
1bbd0b84 | 590 | #define FUNC_NAME s_scm_hash_get_handle |
0f2d19dd | 591 | { |
d587c9e8 LC |
592 | return scm_hash_fn_get_handle (table, key, |
593 | (scm_t_hash_fn) scm_ihash, | |
594 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
595 | 0); | |
0f2d19dd | 596 | } |
1bbd0b84 | 597 | #undef FUNC_NAME |
0f2d19dd JB |
598 | |
599 | ||
a1ec6916 | 600 | SCM_DEFINE (scm_hash_create_handle_x, "hash-create-handle!", 3, 0, 0, |
d550d22a GB |
601 | (SCM table, SCM key, SCM init), |
602 | "This function looks up @var{key} in @var{table} and returns its handle.\n" | |
603 | "If @var{key} is not already present, a new handle is created which\n" | |
604 | "associates @var{key} with @var{init}.") | |
1bbd0b84 | 605 | #define FUNC_NAME s_scm_hash_create_handle_x |
0f2d19dd | 606 | { |
d587c9e8 LC |
607 | return scm_hash_fn_create_handle_x (table, key, init, |
608 | (scm_t_hash_fn) scm_ihash, | |
609 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
610 | 0); | |
0f2d19dd | 611 | } |
1bbd0b84 | 612 | #undef FUNC_NAME |
0f2d19dd JB |
613 | |
614 | ||
54a9b981 AW |
615 | static int |
616 | assoc_predicate (SCM k, SCM v, void *closure) | |
617 | { | |
21041372 | 618 | return scm_is_true (scm_equal_p (k, SCM_PACK_POINTER (closure))); |
54a9b981 AW |
619 | } |
620 | ||
a1ec6916 | 621 | SCM_DEFINE (scm_hash_ref, "hash-ref", 2, 1, 0, |
1e6808ea | 622 | (SCM table, SCM key, SCM dflt), |
d550d22a GB |
623 | "Look up @var{key} in the hash table @var{table}, and return the\n" |
624 | "value (if any) associated with it. If @var{key} is not found,\n" | |
b7e64f8b | 625 | "return @var{dflt} (or @code{#f} if no @var{dflt} argument\n" |
5352393c | 626 | "is supplied). Uses @code{equal?} for equality testing.") |
1bbd0b84 | 627 | #define FUNC_NAME s_scm_hash_ref |
0f2d19dd | 628 | { |
54778cd3 | 629 | if (SCM_UNBNDP (dflt)) |
0f2d19dd | 630 | dflt = SCM_BOOL_F; |
54a9b981 AW |
631 | |
632 | if (SCM_WEAK_TABLE_P (table)) | |
633 | return scm_c_weak_table_ref (table, scm_ihash (key, -1), | |
789dd40b MW |
634 | assoc_predicate, |
635 | (void *) SCM_UNPACK (key), dflt); | |
54a9b981 | 636 | |
d587c9e8 LC |
637 | return scm_hash_fn_ref (table, key, dflt, |
638 | (scm_t_hash_fn) scm_ihash, | |
639 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
640 | 0); | |
0f2d19dd | 641 | } |
1bbd0b84 | 642 | #undef FUNC_NAME |
0f2d19dd JB |
643 | |
644 | ||
645 | ||
a1ec6916 | 646 | SCM_DEFINE (scm_hash_set_x, "hash-set!", 3, 0, 0, |
1e6808ea | 647 | (SCM table, SCM key, SCM val), |
5352393c | 648 | "Find the entry in @var{table} associated with @var{key}, and\n" |
b7e64f8b | 649 | "store @var{val} there. Uses @code{equal?} for equality\n" |
5352393c | 650 | "testing.") |
1bbd0b84 | 651 | #define FUNC_NAME s_scm_hash_set_x |
0f2d19dd | 652 | { |
54a9b981 AW |
653 | if (SCM_WEAK_TABLE_P (table)) |
654 | { | |
655 | scm_c_weak_table_put_x (table, scm_ihash (key, -1), | |
789dd40b | 656 | assoc_predicate, (void *) SCM_UNPACK (key), |
54a9b981 | 657 | key, val); |
07e69928 | 658 | return val; |
54a9b981 AW |
659 | } |
660 | ||
d587c9e8 LC |
661 | return scm_hash_fn_set_x (table, key, val, |
662 | (scm_t_hash_fn) scm_ihash, | |
663 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
664 | 0); | |
0f2d19dd | 665 | } |
1bbd0b84 | 666 | #undef FUNC_NAME |
0f2d19dd JB |
667 | |
668 | ||
669 | ||
a1ec6916 | 670 | SCM_DEFINE (scm_hash_remove_x, "hash-remove!", 2, 0, 0, |
1e6808ea | 671 | (SCM table, SCM key), |
5352393c MG |
672 | "Remove @var{key} (and any value associated with it) from\n" |
673 | "@var{table}. Uses @code{equal?} for equality tests.") | |
1bbd0b84 | 674 | #define FUNC_NAME s_scm_hash_remove_x |
0f2d19dd | 675 | { |
54a9b981 AW |
676 | if (SCM_WEAK_TABLE_P (table)) |
677 | { | |
678 | scm_c_weak_table_remove_x (table, scm_ihash (key, -1), | |
789dd40b | 679 | assoc_predicate, (void *) SCM_UNPACK (key)); |
07e69928 AW |
680 | /* See note in hashq-remove!. */ |
681 | return SCM_BOOL_F; | |
54a9b981 AW |
682 | } |
683 | ||
d587c9e8 LC |
684 | return scm_hash_fn_remove_x (table, key, |
685 | (scm_t_hash_fn) scm_ihash, | |
686 | (scm_t_assoc_fn) scm_sloppy_assoc, | |
687 | 0); | |
0f2d19dd | 688 | } |
1bbd0b84 | 689 | #undef FUNC_NAME |
0f2d19dd JB |
690 | |
691 | \f | |
692 | ||
693 | ||
92c2555f | 694 | typedef struct scm_t_ihashx_closure |
0f2d19dd JB |
695 | { |
696 | SCM hash; | |
697 | SCM assoc; | |
54a9b981 | 698 | SCM key; |
92c2555f | 699 | } scm_t_ihashx_closure; |
0f2d19dd | 700 | |
c014a02e | 701 | static unsigned long |
d587c9e8 | 702 | scm_ihashx (SCM obj, unsigned long n, void *arg) |
0f2d19dd | 703 | { |
d587c9e8 LC |
704 | SCM answer; |
705 | scm_t_ihashx_closure *closure = (scm_t_ihashx_closure *) arg; | |
706 | answer = scm_call_2 (closure->hash, obj, scm_from_ulong (n)); | |
a55c2b68 | 707 | return scm_to_ulong (answer); |
0f2d19dd JB |
708 | } |
709 | ||
0f2d19dd | 710 | static SCM |
d587c9e8 | 711 | scm_sloppy_assx (SCM obj, SCM alist, void *arg) |
0f2d19dd | 712 | { |
d587c9e8 | 713 | scm_t_ihashx_closure *closure = (scm_t_ihashx_closure *) arg; |
87ca11ff | 714 | return scm_call_2 (closure->assoc, obj, alist); |
0f2d19dd JB |
715 | } |
716 | ||
54a9b981 AW |
717 | static int |
718 | assx_predicate (SCM k, SCM v, void *closure) | |
719 | { | |
720 | scm_t_ihashx_closure *c = (scm_t_ihashx_closure *) closure; | |
721 | ||
722 | /* FIXME: The hashx interface is crazy. Hash tables have nothing to | |
723 | do with alists in principle. Instead of getting an assoc proc, | |
724 | hashx functions should use an equality predicate. Perhaps we can | |
725 | change this before 2.2, but until then, add a terrible, terrible | |
726 | hack. */ | |
727 | ||
728 | return scm_is_true (scm_call_2 (c->assoc, c->key, scm_acons (k, v, SCM_EOL))); | |
729 | } | |
730 | ||
0f2d19dd | 731 | |
a1ec6916 | 732 | SCM_DEFINE (scm_hashx_get_handle, "hashx-get-handle", 4, 0, 0, |
1e6808ea MG |
733 | (SCM hash, SCM assoc, SCM table, SCM key), |
734 | "This behaves the same way as the corresponding\n" | |
735 | "@code{-get-handle} function, but uses @var{hash} as a hash\n" | |
736 | "function and @var{assoc} to compare keys. @code{hash} must be\n" | |
737 | "a function that takes two arguments, a key to be hashed and a\n" | |
d550d22a GB |
738 | "table size. @code{assoc} must be an associator function, like\n" |
739 | "@code{assoc}, @code{assq} or @code{assv}.") | |
1bbd0b84 | 740 | #define FUNC_NAME s_scm_hashx_get_handle |
0f2d19dd | 741 | { |
92c2555f | 742 | scm_t_ihashx_closure closure; |
0f2d19dd JB |
743 | closure.hash = hash; |
744 | closure.assoc = assoc; | |
54a9b981 | 745 | closure.key = key; |
1d9c2e62 | 746 | |
1e6808ea | 747 | return scm_hash_fn_get_handle (table, key, scm_ihashx, scm_sloppy_assx, |
87ca11ff | 748 | (void *) &closure); |
0f2d19dd | 749 | } |
1bbd0b84 | 750 | #undef FUNC_NAME |
0f2d19dd JB |
751 | |
752 | ||
a1ec6916 | 753 | SCM_DEFINE (scm_hashx_create_handle_x, "hashx-create-handle!", 5, 0, 0, |
1e6808ea MG |
754 | (SCM hash, SCM assoc, SCM table, SCM key, SCM init), |
755 | "This behaves the same way as the corresponding\n" | |
756 | "@code{-create-handle} function, but uses @var{hash} as a hash\n" | |
757 | "function and @var{assoc} to compare keys. @code{hash} must be\n" | |
758 | "a function that takes two arguments, a key to be hashed and a\n" | |
d550d22a GB |
759 | "table size. @code{assoc} must be an associator function, like\n" |
760 | "@code{assoc}, @code{assq} or @code{assv}.") | |
1bbd0b84 | 761 | #define FUNC_NAME s_scm_hashx_create_handle_x |
0f2d19dd | 762 | { |
92c2555f | 763 | scm_t_ihashx_closure closure; |
0f2d19dd JB |
764 | closure.hash = hash; |
765 | closure.assoc = assoc; | |
54a9b981 | 766 | closure.key = key; |
1d9c2e62 | 767 | |
1e6808ea MG |
768 | return scm_hash_fn_create_handle_x (table, key, init, scm_ihashx, |
769 | scm_sloppy_assx, (void *)&closure); | |
0f2d19dd | 770 | } |
1bbd0b84 | 771 | #undef FUNC_NAME |
0f2d19dd JB |
772 | |
773 | ||
774 | ||
a1ec6916 | 775 | SCM_DEFINE (scm_hashx_ref, "hashx-ref", 4, 1, 0, |
1e6808ea | 776 | (SCM hash, SCM assoc, SCM table, SCM key, SCM dflt), |
d550d22a | 777 | "This behaves the same way as the corresponding @code{ref}\n" |
1e6808ea MG |
778 | "function, but uses @var{hash} as a hash function and\n" |
779 | "@var{assoc} to compare keys. @code{hash} must be a function\n" | |
780 | "that takes two arguments, a key to be hashed and a table size.\n" | |
781 | "@code{assoc} must be an associator function, like @code{assoc},\n" | |
782 | "@code{assq} or @code{assv}.\n" | |
783 | "\n" | |
784 | "By way of illustration, @code{hashq-ref table key} is\n" | |
785 | "equivalent to @code{hashx-ref hashq assq table key}.") | |
1bbd0b84 | 786 | #define FUNC_NAME s_scm_hashx_ref |
0f2d19dd | 787 | { |
92c2555f | 788 | scm_t_ihashx_closure closure; |
54778cd3 | 789 | if (SCM_UNBNDP (dflt)) |
0f2d19dd JB |
790 | dflt = SCM_BOOL_F; |
791 | closure.hash = hash; | |
792 | closure.assoc = assoc; | |
54a9b981 AW |
793 | closure.key = key; |
794 | ||
795 | if (SCM_WEAK_TABLE_P (table)) | |
796 | { | |
797 | unsigned long h = scm_to_ulong (scm_call_2 (hash, key, | |
798 | scm_from_ulong (-1))); | |
799 | return scm_c_weak_table_ref (table, h, assx_predicate, &closure, dflt); | |
800 | } | |
801 | ||
1e6808ea MG |
802 | return scm_hash_fn_ref (table, key, dflt, scm_ihashx, scm_sloppy_assx, |
803 | (void *)&closure); | |
0f2d19dd | 804 | } |
1bbd0b84 | 805 | #undef FUNC_NAME |
0f2d19dd JB |
806 | |
807 | ||
808 | ||
809 | ||
a1ec6916 | 810 | SCM_DEFINE (scm_hashx_set_x, "hashx-set!", 5, 0, 0, |
1e6808ea | 811 | (SCM hash, SCM assoc, SCM table, SCM key, SCM val), |
d550d22a | 812 | "This behaves the same way as the corresponding @code{set!}\n" |
1e6808ea MG |
813 | "function, but uses @var{hash} as a hash function and\n" |
814 | "@var{assoc} to compare keys. @code{hash} must be a function\n" | |
815 | "that takes two arguments, a key to be hashed and a table size.\n" | |
816 | "@code{assoc} must be an associator function, like @code{assoc},\n" | |
817 | "@code{assq} or @code{assv}.\n" | |
818 | "\n" | |
819 | " By way of illustration, @code{hashq-set! table key} is\n" | |
820 | "equivalent to @code{hashx-set! hashq assq table key}.") | |
1bbd0b84 | 821 | #define FUNC_NAME s_scm_hashx_set_x |
0f2d19dd | 822 | { |
92c2555f | 823 | scm_t_ihashx_closure closure; |
0f2d19dd JB |
824 | closure.hash = hash; |
825 | closure.assoc = assoc; | |
54a9b981 AW |
826 | closure.key = key; |
827 | ||
828 | if (SCM_WEAK_TABLE_P (table)) | |
829 | { | |
830 | unsigned long h = scm_to_ulong (scm_call_2 (hash, key, | |
831 | scm_from_ulong (-1))); | |
832 | scm_c_weak_table_put_x (table, h, assx_predicate, &closure, key, val); | |
07e69928 | 833 | return val; |
54a9b981 AW |
834 | } |
835 | ||
1e6808ea MG |
836 | return scm_hash_fn_set_x (table, key, val, scm_ihashx, scm_sloppy_assx, |
837 | (void *)&closure); | |
0f2d19dd | 838 | } |
1bbd0b84 | 839 | #undef FUNC_NAME |
0f2d19dd | 840 | |
a9cf5c71 MV |
841 | SCM_DEFINE (scm_hashx_remove_x, "hashx-remove!", 4, 0, 0, |
842 | (SCM hash, SCM assoc, SCM table, SCM obj), | |
843 | "This behaves the same way as the corresponding @code{remove!}\n" | |
844 | "function, but uses @var{hash} as a hash function and\n" | |
845 | "@var{assoc} to compare keys. @code{hash} must be a function\n" | |
846 | "that takes two arguments, a key to be hashed and a table size.\n" | |
847 | "@code{assoc} must be an associator function, like @code{assoc},\n" | |
848 | "@code{assq} or @code{assv}.\n" | |
849 | "\n" | |
850 | " By way of illustration, @code{hashq-remove! table key} is\n" | |
851 | "equivalent to @code{hashx-remove! hashq assq #f table key}.") | |
852 | #define FUNC_NAME s_scm_hashx_remove_x | |
0f2d19dd | 853 | { |
92c2555f | 854 | scm_t_ihashx_closure closure; |
0f2d19dd JB |
855 | closure.hash = hash; |
856 | closure.assoc = assoc; | |
54a9b981 AW |
857 | closure.key = obj; |
858 | ||
859 | if (SCM_WEAK_TABLE_P (table)) | |
860 | { | |
861 | unsigned long h = scm_to_ulong (scm_call_2 (hash, obj, | |
862 | scm_from_ulong (-1))); | |
863 | scm_c_weak_table_remove_x (table, h, assx_predicate, &closure); | |
07e69928 AW |
864 | /* See note in hashq-remove!. */ |
865 | return SCM_BOOL_F; | |
54a9b981 AW |
866 | } |
867 | ||
4cff503f KR |
868 | return scm_hash_fn_remove_x (table, obj, scm_ihashx, scm_sloppy_assx, |
869 | (void *) &closure); | |
0f2d19dd | 870 | } |
a9cf5c71 | 871 | #undef FUNC_NAME |
0f2d19dd | 872 | |
711a9fd7 | 873 | /* Hash table iterators */ |
b94903c2 | 874 | |
162125af AW |
875 | SCM_DEFINE (scm_hash_fold, "hash-fold", 3, 0, 0, |
876 | (SCM proc, SCM init, SCM table), | |
877 | "An iterator over hash-table elements.\n" | |
878 | "Accumulates and returns a result by applying PROC successively.\n" | |
879 | "The arguments to PROC are \"(key value prior-result)\" where key\n" | |
880 | "and value are successive pairs from the hash table TABLE, and\n" | |
881 | "prior-result is either INIT (for the first application of PROC)\n" | |
882 | "or the return value of the previous application of PROC.\n" | |
883 | "For example, @code{(hash-fold acons '() tab)} will convert a hash\n" | |
884 | "table into an a-list of key-value pairs.") | |
885 | #define FUNC_NAME s_scm_hash_fold | |
886 | { | |
887 | SCM_VALIDATE_PROC (1, proc); | |
54a9b981 AW |
888 | |
889 | if (SCM_WEAK_TABLE_P (table)) | |
890 | return scm_weak_table_fold (proc, init, table); | |
891 | ||
2dd7d8ce | 892 | SCM_VALIDATE_HASHTABLE (3, table); |
162125af AW |
893 | return scm_internal_hash_fold ((scm_t_hash_fold_fn) scm_call_3, |
894 | (void *) SCM_UNPACK (proc), init, table); | |
895 | } | |
896 | #undef FUNC_NAME | |
897 | ||
898 | static SCM | |
899 | for_each_proc (void *proc, SCM handle) | |
900 | { | |
901 | return scm_call_2 (SCM_PACK (proc), SCM_CAR (handle), SCM_CDR (handle)); | |
902 | } | |
903 | ||
904 | SCM_DEFINE (scm_hash_for_each, "hash-for-each", 2, 0, 0, | |
905 | (SCM proc, SCM table), | |
906 | "An iterator over hash-table elements.\n" | |
907 | "Applies PROC successively on all hash table items.\n" | |
908 | "The arguments to PROC are \"(key value)\" where key\n" | |
909 | "and value are successive pairs from the hash table TABLE.") | |
910 | #define FUNC_NAME s_scm_hash_for_each | |
911 | { | |
912 | SCM_VALIDATE_PROC (1, proc); | |
54a9b981 AW |
913 | |
914 | if (SCM_WEAK_TABLE_P (table)) | |
07e69928 AW |
915 | { |
916 | scm_weak_table_for_each (proc, table); | |
917 | return SCM_UNSPECIFIED; | |
918 | } | |
54a9b981 | 919 | |
2dd7d8ce | 920 | SCM_VALIDATE_HASHTABLE (2, table); |
162125af AW |
921 | |
922 | scm_internal_hash_for_each_handle (for_each_proc, | |
923 | (void *) SCM_UNPACK (proc), | |
924 | table); | |
925 | return SCM_UNSPECIFIED; | |
926 | } | |
927 | #undef FUNC_NAME | |
928 | ||
929 | SCM_DEFINE (scm_hash_for_each_handle, "hash-for-each-handle", 2, 0, 0, | |
930 | (SCM proc, SCM table), | |
931 | "An iterator over hash-table elements.\n" | |
932 | "Applies PROC successively on all hash table handles.") | |
933 | #define FUNC_NAME s_scm_hash_for_each_handle | |
934 | { | |
935 | SCM_ASSERT (scm_is_true (scm_procedure_p (proc)), proc, 1, FUNC_NAME); | |
2dd7d8ce | 936 | SCM_VALIDATE_HASHTABLE (2, table); |
162125af AW |
937 | |
938 | scm_internal_hash_for_each_handle ((scm_t_hash_handle_fn) scm_call_1, | |
939 | (void *) SCM_UNPACK (proc), | |
940 | table); | |
941 | return SCM_UNSPECIFIED; | |
942 | } | |
943 | #undef FUNC_NAME | |
944 | ||
945 | static SCM | |
946 | map_proc (void *proc, SCM key, SCM data, SCM value) | |
947 | { | |
948 | return scm_cons (scm_call_2 (SCM_PACK (proc), key, data), value); | |
949 | } | |
950 | ||
951 | SCM_DEFINE (scm_hash_map_to_list, "hash-map->list", 2, 0, 0, | |
952 | (SCM proc, SCM table), | |
953 | "An iterator over hash-table elements.\n" | |
954 | "Accumulates and returns as a list the results of applying PROC successively.\n" | |
955 | "The arguments to PROC are \"(key value)\" where key\n" | |
956 | "and value are successive pairs from the hash table TABLE.") | |
957 | #define FUNC_NAME s_scm_hash_map_to_list | |
958 | { | |
959 | SCM_VALIDATE_PROC (1, proc); | |
54a9b981 AW |
960 | |
961 | if (SCM_WEAK_TABLE_P (table)) | |
962 | return scm_weak_table_map_to_list (proc, table); | |
963 | ||
2dd7d8ce | 964 | SCM_VALIDATE_HASHTABLE (2, table); |
162125af AW |
965 | return scm_internal_hash_fold (map_proc, |
966 | (void *) SCM_UNPACK (proc), | |
967 | SCM_EOL, | |
968 | table); | |
969 | } | |
970 | #undef FUNC_NAME | |
971 | ||
3330f00f DH |
972 | static SCM |
973 | count_proc (void *pred, SCM key, SCM data, SCM value) | |
974 | { | |
975 | if (scm_is_false (scm_call_2 (SCM_PACK (pred), key, data))) | |
976 | return value; | |
977 | else | |
978 | return scm_oneplus(value); | |
979 | } | |
980 | ||
981 | SCM_DEFINE (scm_hash_count, "hash-count", 2, 0, 0, | |
982 | (SCM pred, SCM table), | |
983 | "Return the number of elements in the given hash TABLE that\n" | |
984 | "cause `(PRED KEY VALUE)' to return true. To quickly determine\n" | |
985 | "the total number of elements, use `(const #t)' for PRED.") | |
986 | #define FUNC_NAME s_scm_hash_count | |
987 | { | |
988 | SCM init; | |
989 | ||
990 | SCM_VALIDATE_PROC (1, pred); | |
991 | SCM_VALIDATE_HASHTABLE (2, table); | |
992 | ||
993 | init = scm_from_int (0); | |
994 | return scm_internal_hash_fold ((scm_t_hash_fold_fn) count_proc, | |
995 | (void *) SCM_UNPACK (pred), init, table); | |
996 | } | |
997 | #undef FUNC_NAME | |
998 | ||
162125af | 999 | \f |
c7df61cd MD |
1000 | |
1001 | SCM | |
a07010bf LC |
1002 | scm_internal_hash_fold (scm_t_hash_fold_fn fn, void *closure, |
1003 | SCM init, SCM table) | |
2dd7d8ce | 1004 | #define FUNC_NAME s_scm_hash_fold |
c7df61cd | 1005 | { |
87ca11ff MD |
1006 | long i, n; |
1007 | SCM buckets, result = init; | |
87ca11ff | 1008 | |
54a9b981 AW |
1009 | if (SCM_WEAK_TABLE_P (table)) |
1010 | return scm_c_weak_table_fold (fn, closure, init, table); | |
1011 | ||
2dd7d8ce AW |
1012 | SCM_VALIDATE_HASHTABLE (0, table); |
1013 | buckets = SCM_HASHTABLE_VECTOR (table); | |
0a4c1355 | 1014 | |
3ebc1832 | 1015 | n = SCM_SIMPLE_VECTOR_LENGTH (buckets); |
c7df61cd MD |
1016 | for (i = 0; i < n; ++i) |
1017 | { | |
2187975e | 1018 | SCM ls, handle; |
741e83fc | 1019 | |
2187975e AW |
1020 | for (ls = SCM_SIMPLE_VECTOR_REF (buckets, i); !scm_is_null (ls); |
1021 | ls = SCM_CDR (ls)) | |
c7df61cd | 1022 | { |
c7df61cd | 1023 | handle = SCM_CAR (ls); |
54a9b981 | 1024 | result = fn (closure, SCM_CAR (handle), SCM_CDR (handle), result); |
c7df61cd MD |
1025 | } |
1026 | } | |
87ca11ff | 1027 | |
c7df61cd MD |
1028 | return result; |
1029 | } | |
2dd7d8ce | 1030 | #undef FUNC_NAME |
c7df61cd | 1031 | |
711a9fd7 MD |
1032 | /* The following redundant code is here in order to be able to support |
1033 | hash-for-each-handle. An alternative would have been to replace | |
1034 | this code and scm_internal_hash_fold above with a single | |
1035 | scm_internal_hash_fold_handles, but we don't want to promote such | |
1036 | an API. */ | |
1037 | ||
711a9fd7 | 1038 | void |
a07010bf LC |
1039 | scm_internal_hash_for_each_handle (scm_t_hash_handle_fn fn, void *closure, |
1040 | SCM table) | |
2dd7d8ce | 1041 | #define FUNC_NAME s_scm_hash_for_each |
711a9fd7 MD |
1042 | { |
1043 | long i, n; | |
1044 | SCM buckets; | |
1045 | ||
2dd7d8ce AW |
1046 | SCM_VALIDATE_HASHTABLE (0, table); |
1047 | buckets = SCM_HASHTABLE_VECTOR (table); | |
3ebc1832 | 1048 | n = SCM_SIMPLE_VECTOR_LENGTH (buckets); |
2dd7d8ce | 1049 | |
711a9fd7 MD |
1050 | for (i = 0; i < n; ++i) |
1051 | { | |
3ebc1832 | 1052 | SCM ls = SCM_SIMPLE_VECTOR_REF (buckets, i), handle; |
d2e53ed6 | 1053 | while (!scm_is_null (ls)) |
711a9fd7 | 1054 | { |
d2e53ed6 | 1055 | if (!scm_is_pair (ls)) |
2dd7d8ce | 1056 | SCM_WRONG_TYPE_ARG (SCM_ARG3, buckets); |
711a9fd7 | 1057 | handle = SCM_CAR (ls); |
d2e53ed6 | 1058 | if (!scm_is_pair (handle)) |
2dd7d8ce | 1059 | SCM_WRONG_TYPE_ARG (SCM_ARG3, buckets); |
711a9fd7 MD |
1060 | fn (closure, handle); |
1061 | ls = SCM_CDR (ls); | |
1062 | } | |
1063 | } | |
1064 | } | |
2dd7d8ce | 1065 | #undef FUNC_NAME |
711a9fd7 | 1066 | |
0f2d19dd JB |
1067 | \f |
1068 | ||
1cc91f1b | 1069 | |
c35738c1 MD |
1070 | void |
1071 | scm_init_hashtab () | |
1072 | { | |
a0599745 | 1073 | #include "libguile/hashtab.x" |
0f2d19dd | 1074 | } |
89e00824 ML |
1075 | |
1076 | /* | |
1077 | Local Variables: | |
1078 | c-file-style: "gnu" | |
1079 | End: | |
1080 | */ |