Debian Codegraph @

src/hash.c

raw
1 /*
2 * hash.c - hash table implementation
3 *
4 * Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #define LIBGAUCHE_BODY
35 #include <math.h>
36 #include "gauche.h"
37 #include "gauche/priv/configP.h"
38 #include "gauche/priv/atomicP.h"
39
40 /*============================================================
41 * Internal structures
42 */
43
44 /* The beginning of this structure must match ScmDictEntry. */
45 typedef struct EntryRec {
46 intptr_t key;
47 intptr_t value;
48 struct EntryRec *next;
49 u_long hashval;
50 } Entry;
51
52 #define BUCKETS(hc) ((Entry**)hc->buckets)
53
54 #define DEFAULT_NUM_BUCKETS 4
55 #define MAX_AVG_CHAIN_LIMITS 3
56 #define EXTEND_BITS 2
57
58 /* We limit portable hash value to 32bits */
59 #define PORTABLE_HASHMASK 0xffffffffUL
60
61 /* For other hash values, we limit it in the fixnum range. */
62 #define HASHMASK SCM_SMALL_INT_MAX
63
64 typedef Entry *SearchProc(ScmHashCore *core, intptr_t key, ScmDictOp op);
65
66 static u_int round2up(unsigned int val);
67
68 /*============================================================
69 * Hash salt
70 */
71
72 /* The salt value is nonnegative fixnum. For the time being, we initialize
73 the default salt value for each run of the process; we might do
74 per-hashtable salt in future.
75
76 Internally we use parameter slot to keep the hash salt value, but
77 we provide dedicated C API to access it to avoid overhead of parameter
78 mechanism.
79 */
80
81 static ScmPrimitiveParameter *hash_salt; /* initialized by Scm__InitHash() */
82
83 ScmSmallInt Scm_HashSaltRef()
84 {
85 return SCM_INT_VALUE(Scm_PrimitiveParameterRef(Scm_VM(), hash_salt));
86 }
87
88 ScmSmallInt Scm_HashSaltSet(ScmSmallInt newval) /* returns old value */
89 {
90 return SCM_INT_VALUE(Scm_PrimitiveParameterSet(Scm_VM(), hash_salt,
91 SCM_MAKE_INT(newval)));
92 }
93
94 /*============================================================
95 * Hash functions
96 */
97
98 /* Hash function calculates 32bit hash value from the given object.
99 HASH2INDEX macro maps the hash value to the bucket number.
100 (On 64 bit architecture, it's OK to calculate 64bit, but the
101 upper bits are discarded by HASH2INDEX to maintain compatibility. */
102
103 /* Integer and address. */
104 /* Integer and address hash is a variation of "multiplicative hashing"
105 scheme described in Knuth, TAOCP, section 6.4. The final shifting
106 is done by HASH2INDEX macro */
107
108 #define SMALL_INT_HASH(result, val) \
109 (result) = ((val)*2654435761UL)
110
111 #define ADDRESS_HASH(result, val) \
112 (result) = (u_long)((SCM_WORD(val) >> 3)*2654435761UL)
113
114 /* HASH2INDEX
115 Map a hash value to bucket number.
116 We fix the word length to 32bits, since the multiplication
117 constant above is fixed. */
118 #define HASH2INDEX(tabsiz, bits, hashval) \
119 (((hashval)+((hashval)>>(32-(bits)))) & ((tabsiz) - 1))
120
121 /* Combining two hash values. */
122 #define COMBINE(hv1, hv2) ((hv1)*5+(hv2))
123
124 /* For strings, we employ siphash.
125 We use public domain implementation by Sam Trenholme
126 http://samiam.org/blog/20131006.html. It has a version suitable
127 for 32bit architecture, too.
128 See dws_adapter.h for the details.
129 */
130 #define SCM_DWSIPHASH_INTERFACE
131 #include "gauche/priv/dws_adapter.h"
132
133 u_long Scm_EqHash(ScmObj obj)
134 {
135 u_long hashval;
136 ADDRESS_HASH(hashval, obj);
137 return hashval&HASHMASK;
138 }
139
140 static u_long number_hash(ScmObj obj, u_long salt, int portable);
141
142 static u_long flonum_hash(double d, u_long salt, int portable)
143 {
144 int exp, sign;
145 ScmObj mantissa = Scm_DecodeFlonum(d, &exp, &sign);
146 u_long xh;
147 SMALL_INT_HASH(xh, exp*sign);
148 if (SCM_NUMBERP(mantissa)) {
149 return COMBINE(number_hash(mantissa, salt, portable), xh);
150 } else {
151 /* d is not finite. we just map +inf.0, -inf.0 and nan.0 to 0. */
152 return 0;
153 }
154 }
155
156 static u_long number_hash(ScmObj obj, u_long salt, int portable)
157 {
158 u_long hashval;
159 if (SCM_INTP(obj)) {
160 /* On 64bit platform, if we have fixnum that is beyond the range
161 of 32bit fixnum, we have to calculate the hash value the same
162 way as 32bit bignum would do. */
163 long u = SCM_INT_VALUE(obj);
164 if (portable) {
165 if (u < 0) u = -u; /* safe, for u is in fixnum range */
166 #if SIZEOF_LONG == 8
167 u = ((u & ((1UL<<32) - 1)) + (u >> 32)) & ((1UL<<32)-1);
168 #endif
169 }
170 SMALL_INT_HASH(hashval, u);
171 } else if (SCM_BIGNUMP(obj)) {
172 if (portable) {
173 u_int i;
174 u_long u = 0;
175 for (i=0; i<SCM_BIGNUM_SIZE(obj); i++) {
176 #if SIZEOF_LONG == 4
177 u += SCM_BIGNUM(obj)->values[i];
178 #elif SIZEOF_LONG == 8
179 u += (SCM_BIGNUM(obj)->values[i] & ((1UL<<32) - 1))
180 + (SCM_BIGNUM(obj)->values[i] >> 32);
181 #else
182 #error "sizeof(long) > 8 platform unsupported"
183 #endif
184 }
185 SMALL_INT_HASH(hashval, u);
186 } else {
187 u_int i;
188 u_long u = 0;
189 for (i=0; i<SCM_BIGNUM_SIZE(obj); i++) {
190 u += SCM_BIGNUM(obj)->values[i];
191 }
192 SMALL_INT_HASH(hashval, u);
193 }
194 } else if (SCM_FLONUMP(obj)) {
195 hashval = flonum_hash(SCM_FLONUM_VALUE(obj), salt, portable);
196 } else if (SCM_RATNUMP(obj)) {
197 /* Ratnum must already be normalized, so we can simply combine
198 hashvals of numerator and denominator. */
199 u_long h1 = number_hash(SCM_RATNUM_NUMER(obj), salt, portable);
200 u_long h2 = number_hash(SCM_RATNUM_DENOM(obj), salt, portable);
201 hashval = COMBINE(h1, h2);
202 } else {
203 SCM_ASSERT(SCM_COMPNUMP(obj));
204 hashval = COMBINE(flonum_hash(SCM_COMPNUM_REAL(obj), salt, portable),
205 flonum_hash(SCM_COMPNUM_IMAG(obj), salt, portable));
206 }
207 return hashval & (portable ? PORTABLE_HASHMASK : HASHMASK);
208 }
209
210 u_long Scm_EqvHash(ScmObj obj)
211 {
212 u_long hashval;
213 if (SCM_NUMBERP(obj)) {
214 hashval = number_hash(obj, 0, FALSE);
215 } else {
216 ADDRESS_HASH(hashval, obj);
217 }
218 return hashval&HASHMASK;
219 }
220
221 static u_long internal_string_hash(ScmString *str, u_long salt, int portable)
222 {
223 const ScmStringBody *b = SCM_STRING_BODY(str);
224 if (portable) {
225 return (u_long)Scm__DwSipPortableHash((uint8_t*)b->start, b->size,
226 salt, salt);
227 } else {
228 return Scm__DwSipDefaultHash((uint8_t*)b->start, b->size,
229 salt, salt);
230 }
231 }
232
233 static u_long internal_uvector_hash(ScmUVector *u, u_long salt, int portable)
234 {
235 if (portable) {
236 ScmUVectorType uvtype = Scm_UVectorType(Scm_ClassOf(SCM_OBJ(u)));
237 u_long r, seed;
238 size_t s = SCM_UVECTOR_SIZE(u);
239
240 switch (uvtype) {
241 /* We can use siphash if u is u8vector or s8vector. */
242 case SCM_UVECTOR_S8:
243 case SCM_UVECTOR_U8:
244 return Scm__DwSipPortableHash((uint8_t*)SCM_UVECTOR_ELEMENTS(u),
245 (uint32_t)Scm_UVectorSizeInBytes(u),
246 salt, salt^uvtype);
247 /* We need to avoid depending on endianness of multibyte numbers.
248 Using siphash after canonicalizing byte order can be expensive,
249 for we need to allocate a buffer.
250 (Unless we directly access siphash setup/round function
251 and feed one word at a time--which is tedious.)
252 The current code may not be ideal, but just as good as our
253 other primitive portable hash functions. */
254
255 /* Initial hash value. The seed value for each uvector type
256 is just a random value I generated. */
257 #define INIT_R(r, seed) SMALL_INT_HASH(r, seed^salt)
258
259 case SCM_UVECTOR_S16:
260 seed = 3499211612ul;
261 goto do16;
262 case SCM_UVECTOR_U16:
263 seed = 3890346734ul;
264 goto do16;
265 case SCM_UVECTOR_F16:
266 seed = 545404204ul;
267 do16:
268 {
269 INIT_R(r, seed);
270 for (size_t i=0; i<s; i++) {
271 u_long e = SCM_U16VECTOR_ELEMENT(u, i);
272 SMALL_INT_HASH(e, e);
273 r = COMBINE(r, e);
274 }
275 return r;
276 }
277 case SCM_UVECTOR_S32:
278 seed = 4161255391ul;
279 goto do32;
280 case SCM_UVECTOR_U32:
281 seed = 3922919429ul;
282 goto do32;
283 case SCM_UVECTOR_F32:
284 seed = 949333985ul;
285 do32:
286 {
287 INIT_R(r, seed);
288 for (size_t i=0; i<s; i++) {
289 u_long e = SCM_U32VECTOR_ELEMENT(u, i);
290 SMALL_INT_HASH(e, e);
291 r = COMBINE(r, e);
292 }
293 return r;
294 }
295 case SCM_UVECTOR_S64:
296 seed = 2715962298ul;
297 goto do64;
298 case SCM_UVECTOR_U64:
299 seed = 1323567403ul;
300 do64:
301 {
302 INIT_R(r, seed);
303 for (size_t i=0; i<s; i++) {
304 uint64_t e = SCM_U64VECTOR_ELEMENT(u, i);
305 u_long z = (e >> 32) ^ e;
306 SMALL_INT_HASH(z, z);
307 r = COMBINE(r, z);
308 }
309 return r;
310 }
311 case SCM_UVECTOR_F64: {
312 /* We can't reinterpret f64 as u64, since ARM mixed-endian would
313 yield nonportable result. */
314 seed = 2350294565ul;
315 INIT_R(r, seed);
316 for (size_t i=0; i<s; i++) {
317 double e = SCM_F64VECTOR_ELEMENT(u, i);
318 r = COMBINE(r, flonum_hash(e, salt, TRUE));
319 }
320 return r;
321 }
322 #undef INIT_R
323 case SCM_UVECTOR_RESERVED1:
324 case SCM_UVECTOR_C32:
325 case SCM_UVECTOR_C64:
326 case SCM_UVECTOR_C128:
327 case SCM_UVECTOR_RESERVED2:
328 case SCM_UVECTOR_INVALID:
329 case SCM_UVECTOR_GENERIC:
330 Scm_Panic("invalid uvector class.");
331 }
332 return 0; /* dummy */
333 } else {
334 return Scm__DwSipDefaultHash((uint8_t*)SCM_UVECTOR_ELEMENTS(u),
335 (uint32_t)Scm_UVectorSizeInBytes(u),
336 salt, salt);
337 }
338 }
339
340 /* equal-hash, which satisfies
341 forall x, y: equal(x,y) => hash(x) = hash(y)
342
343 Both default-hash and portable-hash have this property but their
344 requirements are slightly different, so here's the common part.
345 */
346 static u_long equal_hash_common(ScmObj obj, u_long salt, int portable)
347 {
348 if (SCM_NUMBERP(obj)) {
349 return number_hash(obj, salt, portable);
350 } else if (!SCM_PTRP(obj)) {
351 u_long hashval;
352 SMALL_INT_HASH(hashval, (u_long)SCM_WORD(obj));
353 return hashval&PORTABLE_HASHMASK;
354 } else if (SCM_STRINGP(obj)) {
355 return internal_string_hash(SCM_STRING(obj), salt, portable);
356 } else if (SCM_PAIRP(obj)) {
357 u_long h = 0, h2;
358 ScmObj cp;
359 SCM_FOR_EACH(cp, obj) {
360 h2 = equal_hash_common(SCM_CAR(cp), salt, portable);
361 h = COMBINE(h, h2);
362 }
363 h2 = equal_hash_common(cp, salt, portable);
364 return COMBINE(h, h2);
365 } else if (SCM_VECTORP(obj)) {
366 int siz = SCM_VECTOR_SIZE(obj);
367 u_long h = 0, h2;
368 for (int i=0; i<siz; i++) {
369 h2 = equal_hash_common(SCM_VECTOR_ELEMENT(obj, i), salt, portable);
370 h = COMBINE(h, h2);
371 }
372 return h;
373 /* uvector hash support */
374 } else if (SCM_UVECTORP(obj)) {
375 return internal_uvector_hash(SCM_UVECTOR(obj), salt, portable);
376 #if GAUCHE_KEEP_DISJOINT_KEYWORD_OPTION
377 } else if (SCM_KEYWORDP(obj)) {
378 if (portable) {
379 if (SCM_SYMBOLP(obj)) {
380 /* GAUCHE_KEYWORD_IS_SYMBOL mode */
381 return internal_string_hash(SCM_KEYWORD_NAME(obj), salt, TRUE);
382 } else {
383 /* GAUCHE_KEYWORD_IS_DISJOINT mode. SCM_KEYWORD_NAME does
384 not include prefix ':'. We should append it so that
385 the hash value stays the same. Appending string incurs
386 allocation, but we expect this branch isn't taken often
387 and eventually fade away. */
388 static ScmString *prefix = NULL;
389 if (prefix == NULL) {
390 /* idempotent. no MT hazard. */
391 prefix = SCM_STRING(Scm_MakeString(":", 1, 1, 0));
392 }
393 ScmObj name = Scm_StringAppend2(prefix, SCM_KEYWORD_NAME(obj));
394 return internal_string_hash(SCM_STRING(name), salt, TRUE);
395 }
396 } else {
397 u_long hashval;
398 ADDRESS_HASH(hashval, obj);
399 return hashval;
400 }
401 #endif /*GAUCHE_KEEP_DISJOINT_KEYWORD_OPTION*/
402 } else if (SCM_SYMBOLP(obj)) {
403 if (portable) {
404 return internal_string_hash(SCM_SYMBOL_NAME(obj), salt, TRUE);
405 } else {
406 u_long hashval;
407 ADDRESS_HASH(hashval, obj);
408 return hashval;
409 }
410 }
411
412 ScmClass *k = SCM_CLASS_OF(obj);
413 if (k->hash) {
414 return (u_long)k->hash(obj, salt,
415 (portable? SCM_HASH_PORTABLE:0));
416 }
417
418 /* Call specialized object-hash method
419 We need some trick; See libomega.scm for the details. */
420 static ScmObj call_object_hash_proc = SCM_UNDEFINED;
421 static ScmObj portable_hash_proc = SCM_UNDEFINED;
422 static ScmObj default_hash_proc = SCM_UNDEFINED;
423 SCM_BIND_PROC(call_object_hash_proc, "%call-object-hash",
424 Scm_GaucheInternalModule());
425 SCM_BIND_PROC(portable_hash_proc, "portable-hash", Scm_GaucheModule());
426 SCM_BIND_PROC(default_hash_proc, "default-hash", Scm_GaucheModule());
427 ScmObj r = Scm_ApplyRec3(call_object_hash_proc, obj,
428 (portable
429 ? portable_hash_proc
430 : default_hash_proc),
431 (portable
432 ? Scm_MakeIntegerU(salt)
433 : SCM_FALSE));
434 if (SCM_INTP(r)) {
435 return (u_long)SCM_INT_VALUE(r);
436 }
437 if (SCM_BIGNUMP(r)) {
438 /* NB: Scm_GetUInteger clamps the result to [0, ULONG_MAX],
439 so taking the LSW would give better distribution. */
440 return SCM_BIGNUM(r)->values[0];
441 }
442 Scm_Error("object-hash returned non-integer: %S", r);
443 return 0; /* dummy */
444 }
445
446 /* For recursive call to the current hash function - see call-object-hash
447 and object-hash definitions in libomega.scm. */
448 static ScmPrimitiveParameter *current_recursive_hash;
449
450 /* This must be called after symbols and modules are initialized.
451 See Scm__InitModule(). */
452 void Scm__InitCurrentRecursiveHash()
453 {
454 SCM_DEFINE(Scm_GaucheInternalModule(),
455 "%current-recursive-hash",
456 Scm_MakePrimitiveParameterSubr(current_recursive_hash));
457 }
458
459 /* 'Portable' general hash function.
460
461 It is guaranteed that the hash value won't change for the same objects
462 (roughly, indistinguishable in their external representation)
463 across the runs of the program, and among different platforms.
464 That is, the value can be used in persistent stores.
465 */
466 u_long Scm_PortableHash(ScmObj obj, u_long salt)
467 {
468 return equal_hash_common(obj, salt, TRUE) & PORTABLE_HASHMASK;
469 }
470
471 /* 'Default' general hash function. */
472 ScmSmallInt Scm_DefaultHash(ScmObj obj)
473 {
474 return equal_hash_common(obj, Scm_HashSaltRef(), FALSE) & HASHMASK;
475 }
476
477 /* This is to be called from ScmClass->hash if it needs to compute
478 hash value of field values. */
479 ScmSmallInt Scm_RecursiveHash(ScmObj obj, ScmSmallInt salt, u_long flags)
480 {
481 if (flags & SCM_HASH_PORTABLE) {
482 return equal_hash_common(obj, salt, TRUE) & PORTABLE_HASHMASK;
483 } else {
484 return equal_hash_common(obj, salt, FALSE) & HASHMASK;
485 }
486 }
487
488 ScmSmallInt Scm_SmallIntHash(ScmSmallInt val,
489 ScmSmallInt salt SCM_UNUSED,
490 u_long flags SCM_UNUSED)
491 {
492 ScmSmallInt v;
493 SMALL_INT_HASH(v, val);
494 return v;
495 }
496
497 ScmSmallInt Scm_Int64Hash(int64_t val,
498 ScmSmallInt salt SCM_UNUSED,
499 u_long flags SCM_UNUSED)
500 {
501 ScmSmallInt v;
502 SMALL_INT_HASH(v, val);
503 return v;
504 }
505
506
507 /* This is to expose string hash function. Modulo is for the compatibility
508 of srfi-13; just give 0 as modulo if you don't need it. */
509 u_long Scm_HashString(ScmString *str, u_long modulo)
510 {
511 u_long hashval = internal_string_hash(str, Scm_HashSaltRef(), FALSE);
512 if (modulo == 0) return hashval&HASHMASK;
513 else return (hashval % modulo);
514 }
515
516 /* Expose COMBINE. */
517 u_long Scm_CombineHashValue(u_long a, u_long b)
518 {
519 u_long c = COMBINE(a, b);
520 #if SIZEOF_LONG == 8
521 /* we limit portable hash value to 32bit. */
522 c &= 0xffffffff;
523 #endif /**/
524 return c;
525 }
526
527 /*------------------------------------------------------------
528 * Parameterization
529 *
530 * Conceptually hash tables are parameterized by hash function and
531 * compare function. However, if they are trivial functions, calling
532 * them via function pointers incur overhead. So we layered the
533 * parameterization.
534 *
535 * For the pre-defined simple hash tables, the calls to the hash and
536 * compare functions are inlined in a single "access" function.
537 * (In this case hashfn and cmpfn are never used.)
538 * For the generic hash tables, the general_access function uses
539 * the info in hashfn and cmpfn fields.
540 *
541 * The accessor function takes three arguments.
542 *
543 * ScmHashCore *core : hash table core
544 * intptr_t key : key
545 * ScmDictOp op : operation
546 */
547
548 /* NOTE: eq?, eqv?, and string=? hash tables are guaranteed not to
549 * throw an error during hash table access (except the case that string=?
550 * hash table gets non-string key). So the caller doesn't need to
551 * set unwind handler in case it needs cleanup (like unlocking mutex).
552 * However, equal? hash may call back to Scheme method, so it can
553 * throw Scheme error. Be aware of that.
554 */
555
556 /*
557 * Common function called when the accessor function needs to add an entry.
558 */
559 static Entry *insert_entry(ScmHashCore *table,
560 intptr_t key,
561 u_long hashval,
562 int index)
563 {
564 Entry *e = SCM_NEW(Entry);
565 Entry **buckets = BUCKETS(table);
566 e->key = key;
567 e->value = 0;
568 e->next = buckets[index];
569 e->hashval = hashval;
570 buckets[index] = e;
571 table->numEntries++;
572
573 if (table->numEntries > table->numBuckets*MAX_AVG_CHAIN_LIMITS) {
574 /* Extend the table */
575 int newsize = (table->numBuckets << EXTEND_BITS);
576 int newbits = table->numBucketsLog2 + EXTEND_BITS;
577
578 Entry **newb = SCM_NEW_ARRAY(Entry*, newsize);
579 for (int i=0; i<newsize; i++) newb[i] = NULL;
580
581 ScmHashIter iter;
582 Entry *f;
583 Scm_HashIterInit(&iter, table);
584 while ((f = (Entry*)Scm_HashIterNext(&iter)) != NULL) {
585 index = HASH2INDEX(newsize, newbits, f->hashval);
586 f->next = newb[index];
587 newb[index] = f;
588 }
589 /* gc friendliness */
590 for (int i=0; i<table->numBuckets; i++) table->buckets[i] = NULL;
591
592 table->numBuckets = newsize;
593 table->numBucketsLog2 = newbits;
594 table->buckets = (void**)newb;
595 }
596 return e;
597 }
598
599 /* NB: Deleting entry E doesn't modify E's key and value, but cut
600 the "next" link for the sake of weak-gc robustness. The hash core
601 iterator prefetches a pointer to the next entry, so deleting the
602 "current" entry of iteration is safe as far as other iterators
603 are running on the same hash table. */
604 static Entry *delete_entry(ScmHashCore *table,
605 Entry *entry, Entry *prev,
606 int index)
607 {
608 if (prev) prev->next = entry->next;
609 else table->buckets[index] = (void*)entry->next;
610 table->numEntries--;
611 SCM_ASSERT(table->numEntries >= 0);
612 entry->next = NULL; /* GC friendliness */
613 return entry;
614 }
615
616 #define FOUND(table, op, e, p, index) \
617 do { \
618 switch (op) { \
619 case SCM_DICT_GET:; \
620 case SCM_DICT_CREATE:; \
621 return e; \
622 case SCM_DICT_DELETE:; \
623 return delete_entry(table, e, p, index); \
624 } \
625 } while (0)
626
627 #define NOTFOUND(table, op, key, hashval, index) \
628 do { \
629 if (op == SCM_DICT_CREATE) { \
630 return insert_entry(table, key, hashval, index); \
631 } else { \
632 return NULL; \
633 } \
634 } while (0)
635
636 /*
637 * Accessor function for address. Used for EQ-type hash.
638 */
639 static Entry *address_access(ScmHashCore *table,
640 intptr_t key,
641 ScmDictOp op)
642 {
643 u_long hashval, index;
644 Entry **buckets = (Entry**)table->buckets;
645
646 ADDRESS_HASH(hashval, key);
647 index = HASH2INDEX(table->numBuckets, table->numBucketsLog2, hashval);
648
649 for (Entry *e = buckets[index], *p = NULL; e; p = e, e = e->next) {
650 if (e->key == key) FOUND(table, op, e, p, index);
651 }
652 NOTFOUND(table, op, key, hashval, index);
653 }
654
655 static u_long address_hash(const ScmHashCore *ht SCM_UNUSED, intptr_t obj)
656 {
657 u_long hashval;
658 ADDRESS_HASH(hashval, obj);
659 return hashval;
660 }
661
662 static int address_cmp(const ScmHashCore *ht SCM_UNUSED,
663 intptr_t key, intptr_t k2)
664 {
665 return (key == k2);
666 }
667
668 /*
669 * Accessor function for equal and eqv-hash.
670 * We assume KEY is ScmObj.
671 */
672 static u_long eqv_hash(const ScmHashCore *ht SCM_UNUSED, intptr_t key)
673 {
674 return Scm_EqvHash(SCM_OBJ(key));
675 }
676
677 static int eqv_cmp(const ScmHashCore *ht SCM_UNUSED, intptr_t key, intptr_t k2)
678 {
679 return Scm_EqvP(SCM_OBJ(key), SCM_OBJ(k2));
680 }
681
682 static u_long equal_hash(const ScmHashCore *ht SCM_UNUSED, intptr_t key)
683 {
684 return Scm_DefaultHash(SCM_OBJ(key));
685 }
686
687 static int equal_cmp(const ScmHashCore *ht SCM_UNUSED, intptr_t key, intptr_t k2)
688 {
689 return Scm_EqualP(SCM_OBJ(key), SCM_OBJ(k2));
690 }
691
692
693 /*
694 * Accessor function for string type.
695 */
696 static Entry *string_access(ScmHashCore *table, intptr_t k, ScmDictOp op)
697 {
698 ScmObj key = SCM_OBJ(k);
699
700 if (!SCM_STRINGP(key)) {
701 Scm_Error("Got non-string key %S to the string hashtable.", key);
702 }
703 u_long hashval = Scm_HashString(SCM_STRING(key), 0);
704 u_long index = HASH2INDEX(table->numBuckets, table->numBucketsLog2, hashval);
705 Entry **buckets = (Entry**)table->buckets;
706
707 const ScmStringBody *keyb = SCM_STRING_BODY(key);
708 long size = SCM_STRING_BODY_SIZE(keyb);
709 for (Entry *e = buckets[index], *p = NULL; e; p = e, e = e->next) {
710 ScmObj ee = SCM_OBJ(e->key);
711 const ScmStringBody *eeb = SCM_STRING_BODY(ee);
712 int eesize = SCM_STRING_BODY_SIZE(eeb);
713 if (size == eesize
714 && memcmp(SCM_STRING_BODY_START(keyb),
715 SCM_STRING_BODY_START(eeb), eesize) == 0){
716 FOUND(table, op, e, p, index);
717 }
718 }
719 NOTFOUND(table, op, k, hashval, index);
720 }
721
722 static u_long string_hash(const ScmHashCore *ht SCM_UNUSED, intptr_t key)
723 {
724 return Scm_HashString(SCM_STRING(key), 0);
725 }
726
727 static int string_cmp(const ScmHashCore *ht SCM_UNUSED, intptr_t k1, intptr_t k2)
728 {
729 const ScmStringBody *b1 = SCM_STRING_BODY(k1);
730 const ScmStringBody *b2 = SCM_STRING_BODY(k2);
731 return ((SCM_STRING_BODY_SIZE(b1) == SCM_STRING_BODY_SIZE(b2))
732 && (memcmp(SCM_STRING_BODY_START(b1),
733 SCM_STRING_BODY_START(b2),
734 SCM_STRING_BODY_SIZE(b1)) == 0));
735 }
736
737 /*
738 * Accessor function for general case
739 * (hashfn and cmpfn are given by user)
740 */
741 static Entry *general_access(ScmHashCore *table, intptr_t key, ScmDictOp op)
742 {
743 u_long hashval, index;
744
745 hashval = table->hashfn(table, key);
746 index = HASH2INDEX(table->numBuckets, table->numBucketsLog2, hashval);
747 Entry **buckets = (Entry**)table->buckets;
748
749 for (Entry *e = buckets[index], *p = NULL; e; p = e, e = e->next) {
750 if (table->cmpfn(table, key, e->key)) FOUND(table, op, e, p, index);
751 }
752 NOTFOUND(table, op, key, hashval, index);
753 }
754
755 /*============================================================
756 * Hash Core functions
757 */
758
759 static void hash_core_init(ScmHashCore *table,
760 SearchProc *accessfn,
761 ScmHashProc *hashfn,
762 ScmHashCompareProc *cmpfn,
763 unsigned int initSize,
764 void *data)
765 {
766 if (initSize != 0) initSize = round2up(initSize);
767 else initSize = DEFAULT_NUM_BUCKETS;
768
769 Entry **b = SCM_NEW_ARRAY(Entry*, initSize);
770 table->buckets = (void**)b;
771 table->numBuckets = initSize;
772 table->numEntries = 0;
773 table->accessfn = (void*)accessfn;
774 table->hashfn = hashfn;
775 table->cmpfn = cmpfn;
776 table->data = data;
777 table->numBucketsLog2 = 0;
778 for (u_int i=initSize; i > 1; i /= 2) {
779 table->numBucketsLog2++;
780 }
781 for (u_int i=0; i<initSize; i++) table->buckets[i] = NULL;
782 }
783
784 /* choose appropriate procedures for predefined hash types. */
785 int hash_core_predef_procs(ScmHashType type,
786 SearchProc **accessfn,
787 ScmHashProc **hashfn,
788 ScmHashCompareProc **cmpfn)
789 {
790 switch (type) {
791 case SCM_HASH_EQ:
792 case SCM_HASH_WORD:
793 *accessfn = address_access;
794 *hashfn = address_hash;
795 *cmpfn = address_cmp;
796 return TRUE;
797 case SCM_HASH_EQV:
798 *accessfn = general_access;
799 *hashfn = eqv_hash;
800 *cmpfn = eqv_cmp;
801 return TRUE;
802 case SCM_HASH_EQUAL:
803 *accessfn = general_access;
804 *hashfn = equal_hash;
805 *cmpfn = equal_cmp;
806 return TRUE;
807 case SCM_HASH_STRING:
808 *accessfn = string_access;
809 *hashfn = string_hash;
810 *cmpfn = string_cmp;
811 return TRUE;
812 default:
813 return FALSE;
814 }
815 }
816
817 void Scm_HashCoreInitSimple(ScmHashCore *core,
818 ScmHashType type,
819 unsigned int initSize,
820 void *data)
821 {
822 SearchProc *accessfn = NULL;
823 ScmHashProc *hashfn = NULL;
824 ScmHashCompareProc *cmpfn = NULL;
825
826 if (hash_core_predef_procs(type, &accessfn, &hashfn, &cmpfn) == FALSE) {
827 Scm_Error("[internal error]: wrong TYPE argument passed to Scm_HashCoreInitSimple: %d", type);
828 }
829 hash_core_init(core, accessfn, hashfn, cmpfn, initSize, data);
830 }
831
832 void Scm_HashCoreInitGeneral(ScmHashCore *core,
833 ScmHashProc *hashfn,
834 ScmHashCompareProc *cmpfn,
835 unsigned int initSize,
836 void *data)
837 {
838 hash_core_init(core, general_access, hashfn,
839 cmpfn, initSize, data);
840 }
841
842 int Scm_HashCoreTypeToProcs(ScmHashType type,
843 ScmHashProc **hashfn,
844 ScmHashCompareProc **cmpfn)
845 {
846 SearchProc *accessfn; /* dummy */
847 return hash_core_predef_procs(type, &accessfn, hashfn, cmpfn);
848 }
849
850 void Scm_HashCoreCopy(ScmHashCore *dst, const ScmHashCore *src)
851 {
852 Entry **b = SCM_NEW_ARRAY(Entry*, src->numBuckets);
853
854 for (int i=0; i<src->numBuckets; i++) {
855 Entry *p = NULL;
856 Entry *s = (Entry*)src->buckets[i];
857 b[i] = NULL;
858 while (s) {
859 Entry *e = SCM_NEW(Entry);
860 e->key = s->key;
861 e->value = s->value;
862 e->next = NULL;
863 e->hashval = s->hashval;
864 if (p) p->next = e;
865 else b[i] = e;
866 p = e;
867 s = s->next;
868 }
869 }
870
871 /* A little trick to avoid hazard in careless race condition */
872 dst->numBuckets = dst->numEntries = 0;
873
874 dst->buckets = (void**)b;
875 dst->hashfn = src->hashfn;
876 dst->cmpfn = src->cmpfn;
877 dst->accessfn = src->accessfn;
878 dst->data = src->data;
879 dst->numEntries = src->numEntries;
880 dst->numBucketsLog2 = src->numBucketsLog2;
881 dst->numBuckets = src->numBuckets;
882 }
883
884 void Scm_HashCoreClear(ScmHashCore *table)
885 {
886 for (int i=0; i<table->numBuckets; i++) {
887 table->buckets[i] = NULL;
888 }
889 table->numEntries = 0;
890 }
891
892 ScmDictEntry *Scm_HashCoreSearch(ScmHashCore *table, intptr_t key,
893 ScmDictOp op)
894 {
895 SearchProc *p = (SearchProc*)table->accessfn;
896 return (ScmDictEntry*)p(table, key, op);
897 }
898
899 int Scm_HashCoreNumEntries(ScmHashCore *table)
900 {
901 return table->numEntries;
902 }
903
904 /*
905 * NB: It is important to keep the pointer to the "next" entry,
906 * not the "current", since the current entry may be deleted,
907 * erasing its next pointer.
908 */
909 void Scm_HashIterInit(ScmHashIter *iter, ScmHashCore *table)
910 {
911 iter->core = table;
912 for (int i=0; i<table->numBuckets; i++) {
913 if (table->buckets[i]) {
914 iter->bucket = i;
915 iter->next = table->buckets[i];
916 return;
917 }
918 }
919 iter->next = NULL;
920 }
921
922 ScmDictEntry *Scm_HashIterNext(ScmHashIter *iter)
923 {
924 Entry *e = (Entry*)iter->next;
925 if (e != NULL) {
926 if (e->next) iter->next = e->next;
927 else {
928 int i = iter->bucket + 1;
929 for (; i < iter->core->numBuckets; i++) {
930 if (iter->core->buckets[i]) {
931 iter->bucket = i;
932 iter->next = iter->core->buckets[i];
933 return (ScmDictEntry*)e;
934 }
935 }
936 iter->next = NULL;
937 }
938 }
939 return (ScmDictEntry*)e;
940 }
941
942 /*============================================================
943 * Scheme <hash-table> object
944 */
945
946 static void hash_print(ScmObj obj, ScmPort *port, ScmWriteContext *ctx);
947
948 SCM_DEFINE_BUILTIN_CLASS(Scm_HashTableClass, hash_print, Scm_ObjectCompare,
949 NULL, NULL,
950 SCM_CLASS_DICTIONARY_CPL);
951
952 ScmObj Scm_MakeHashTableSimple(ScmHashType type, unsigned int initSize)
953 {
954 /* We only allow ScmObj in <hash-table> */
955 if (type > SCM_HASH_GENERAL) {
956 Scm_Error("Scm_MakeHashTableSimple: wrong type arg: %d", type);
957 }
958 ScmHashTable *z = SCM_NEW(ScmHashTable);
959 SCM_SET_CLASS(z, SCM_CLASS_HASH_TABLE);
960 Scm_HashCoreInitSimple(&z->core, type, initSize, NULL);
961 z->type = type;
962 return SCM_OBJ(z);
963 }
964
965 ScmObj Scm_MakeHashTableFull(ScmHashProc hashfn,
966 ScmHashCompareProc cmpfn,
967 unsigned int initSize, void *data)
968 {
969 ScmHashTable *z = SCM_NEW(ScmHashTable);
970 SCM_SET_CLASS(z, SCM_CLASS_HASH_TABLE);
971 z->type = SCM_HASH_GENERAL;
972 Scm_HashCoreInitGeneral(&z->core, hashfn, cmpfn, initSize, data);
973 return SCM_OBJ(z);
974 }
975
976 ScmObj Scm_HashTableCopy(ScmHashTable *src)
977 {
978 ScmHashTable *dst = SCM_NEW(ScmHashTable);
979 SCM_SET_CLASS(dst, SCM_CLASS_HASH_TABLE);
980 Scm_HashCoreCopy(SCM_HASH_TABLE_CORE(dst), SCM_HASH_TABLE_CORE(src));
981 dst->type = src->type;
982 return SCM_OBJ(dst);
983 }
984
985 ScmHashType Scm_HashTableType(ScmHashTable *ht)
986 {
987 return ht->type;
988 }
989
990 ScmObj Scm_HashTableRef(ScmHashTable *ht, ScmObj key, ScmObj fallback)
991 {
992 ScmDictEntry *e = Scm_HashCoreSearch(SCM_HASH_TABLE_CORE(ht),
993 (intptr_t)key, SCM_DICT_GET);
994 if (!e) return fallback;
995 else return SCM_DICT_VALUE(e);
996 }
997
998 /* Returns previous value; can return SCM_UNBOUND when the association hasn't
999 been there. Be careful not to let SCM_UNBOUND leak out to Scheme! */
1000 ScmObj Scm_HashTableSet(ScmHashTable *ht, ScmObj key, ScmObj value, int flags)
1001 {
1002 ScmDictEntry *e;
1003
1004 e = Scm_HashCoreSearch(SCM_HASH_TABLE_CORE(ht),
1005 (intptr_t)key,
1006 (flags&SCM_DICT_NO_CREATE)?SCM_DICT_GET: SCM_DICT_CREATE);
1007 if (!e) return SCM_UNBOUND;
1008 ScmObj oldval = e->value? SCM_DICT_VALUE(e) : SCM_UNBOUND;
1009 if (!(flags&SCM_DICT_NO_OVERWRITE) || SCM_UNBOUNDP(oldval)) {
1010 return SCM_DICT_SET_VALUE(e, value);
1011 }
1012 return oldval;
1013 }
1014
1015 ScmObj Scm_HashTableDelete(ScmHashTable *ht, ScmObj key)
1016 {
1017 ScmDictEntry *e = Scm_HashCoreSearch(SCM_HASH_TABLE_CORE(ht),
1018 (intptr_t)key, SCM_DICT_DELETE);
1019 if (e && e->value) return SCM_DICT_VALUE(e);
1020 else return SCM_UNBOUND;
1021 }
1022
1023 ScmObj Scm_HashTableKeys(ScmHashTable *table)
1024 {
1025 ScmHashIter iter;
1026 ScmDictEntry *e;
1027 ScmObj h = SCM_NIL, t = SCM_NIL;
1028 Scm_HashIterInit(&iter, SCM_HASH_TABLE_CORE(table));
1029 while ((e = Scm_HashIterNext(&iter)) != NULL) {
1030 SCM_APPEND1(h, t, SCM_DICT_KEY(e));
1031 }
1032 return h;
1033 }
1034
1035 ScmObj Scm_HashTableValues(ScmHashTable *table)
1036 {
1037 ScmHashIter iter;
1038 ScmDictEntry *e;
1039 ScmObj h = SCM_NIL, t = SCM_NIL;
1040 Scm_HashIterInit(&iter, SCM_HASH_TABLE_CORE(table));
1041 while ((e = Scm_HashIterNext(&iter)) != NULL) {
1042 SCM_APPEND1(h, t, SCM_DICT_VALUE(e));
1043 }
1044 return h;
1045 }
1046
1047 ScmObj Scm_HashTableStat(ScmHashTable *table)
1048 {
1049 ScmObj h = SCM_NIL, t = SCM_NIL;
1050 ScmHashCore *c = SCM_HASH_TABLE_CORE(table);
1051 SCM_APPEND1(h, t, SCM_MAKE_KEYWORD("num-entries"));
1052 SCM_APPEND1(h, t, Scm_MakeInteger(c->numEntries));
1053 SCM_APPEND1(h, t, SCM_MAKE_KEYWORD("num-buckets"));
1054 SCM_APPEND1(h, t, Scm_MakeInteger(c->numBuckets));
1055 SCM_APPEND1(h, t, SCM_MAKE_KEYWORD("num-buckets-log2"));
1056 SCM_APPEND1(h, t, Scm_MakeInteger(c->numBucketsLog2));
1057
1058 Entry** b = BUCKETS(c);
1059 ScmVector *v = SCM_VECTOR(Scm_MakeVector(c->numBuckets, SCM_NIL));
1060 ScmObj *vp = SCM_VECTOR_ELEMENTS(v);
1061 for (int i = 0; i<c->numBuckets; i++, vp++) {
1062 Entry *e = b[i];
1063 for (; e; e = e->next) {
1064 *vp = Scm_Acons(SCM_DICT_KEY(e), SCM_DICT_VALUE(e), *vp);
1065 }
1066 }
1067 SCM_APPEND1(h, t, SCM_MAKE_KEYWORD("contents"));
1068 SCM_APPEND1(h, t, SCM_OBJ(v));
1069 return h;
1070 }
1071
1072
1073 /*
1074 * Utilities
1075 */
1076
1077 /*
1078 * Printer
1079 */
1080
1081 /* Note: When pprint is used, hash table priting is directly handled by pprint
1082 and this is never called. */
1083 static void hash_print(ScmObj obj, ScmPort *port,
1084 ScmWriteContext *ctx SCM_UNUSED)
1085 {
1086 ScmHashTable *ht = (ScmHashTable*)obj;
1087 char *str = "";
1088
1089 switch (ht->type) {
1090 case SCM_HASH_EQ: str = "eq"; break;
1091 case SCM_HASH_EQV: str = "eqv"; break;
1092 case SCM_HASH_EQUAL: str = "equal"; break;
1093 case SCM_HASH_STRING: str = "string"; break;
1094 case SCM_HASH_GENERAL: str = "general"; break;
1095 default: Scm_Panic("something wrong with a hash table");
1096 }
1097
1098 Scm_Printf(port, "#<hash-table %s[%d] @%p>", str,
1099 SCM_HASH_TABLE_CORE(ht)->numEntries, ht);
1100 }
1101
1102 static unsigned int round2up(unsigned int val)
1103 {
1104 unsigned int n = 1;
1105 while (n < val) {
1106 n <<= 1;
1107 SCM_ASSERT(n > 1); /* check overflow */
1108 }
1109 return n;
1110 }
1111
1112 /*====================================================================
1113 * Initialization
1114 */
1115
1116 void Scm__InitHash()
1117 {
1118 struct timeval t;
1119 if (gettimeofday(&t, NULL) < 0) {
1120 Scm_Panic("gettimeofday failed");
1121 }
1122 u_long salt = ((u_long)getpid() * ((u_long)t.tv_sec^(u_long)t.tv_usec));
1123 ADDRESS_HASH(salt, salt);
1124 salt &= SCM_SMALL_INT_MAX;
1125 /*
1126 * We can't use Scm_BindPrimitiveParameter here, since symbol table
1127 * is not initialized yet (symbol table uses hashtable!)
1128 */
1129 hash_salt =
1130 Scm_MakePrimitiveParameter(SCM_CLASS_PRIMITIVE_PARAMETER, SCM_FALSE,
1131 Scm_MakeIntegerU(salt), 0);
1132 current_recursive_hash =
1133 Scm_MakePrimitiveParameter(SCM_CLASS_PRIMITIVE_PARAMETER, SCM_FALSE,
1134 SCM_FALSE, 0);
1135 }
1136
1137 /*====================================================================
1138 * For backward compatibility
1139 */
1140
1141 #if GAUCHE_API_VERSION < 1000
1142 /* Backward compatibility.
1143 NB: Casting ScmDictEntry* to ScmHashEntry* would be invalid if
1144 sizeof(intptr_t) and sizeof(void*) differ. I know only one
1145 such platform (PlayStation2). If it is a problem, moving to
1146 the new API is recommended. */
1147 ScmHashEntry *Scm_HashTableGet(ScmHashTable *ht, ScmObj key)
1148 {
1149 if (sizeof(intptr_t) != sizeof(void*)) {
1150 Scm_Error("[internal] Scm_HashTableGet is obsoleted on this platform. You should use the new hashtable API.");
1151 }
1152 return (ScmHashEntry*)Scm_HashCoreSearch(SCM_HASH_TABLE_CORE(ht),
1153 (intptr_t)key,
1154 SCM_DICT_GET);
1155 }
1156
1157 ScmHashEntry *Scm_HashTableAdd(ScmHashTable *ht, ScmObj key, ScmObj value)
1158 {
1159 ScmDictEntry *e = Scm_HashCoreSearch(SCM_HASH_TABLE_CORE(ht),
1160 (intptr_t)key, SCM_DICT_CREATE);
1161 if (sizeof(intptr_t) != sizeof(void*)) {
1162 Scm_Error("[internal] Scm_HashTableAdd is obsoleted on this platform. You should use the new hashtable API.");
1163 }
1164 if (!e->value) (void)SCM_DICT_SET_VALUE(e, value);
1165 return (ScmHashEntry*)e;
1166 }
1167
1168 ScmHashEntry *Scm_HashTablePut(ScmHashTable *ht, ScmObj key, ScmObj value)
1169 {
1170 ScmDictEntry *e = Scm_HashCoreSearch(SCM_HASH_TABLE_CORE(ht),
1171 (intptr_t)key, SCM_DICT_CREATE);
1172 if (sizeof(intptr_t) != sizeof(void*)) {
1173 Scm_Error("[internal] Scm_HashTablePut is obsoleted on this platform. You should use the new hashtable API.");
1174 }
1175 (void)SCM_DICT_SET_VALUE(e, value);
1176 return (ScmHashEntry*)e;
1177 }
1178
1179 /* TRANSIENT: Pre-0.9 Compatibility routine. Kept for the binary compatibility.
1180 Will be removed on 1.0 */
1181 void Scm__HashIterInitCompat(ScmHashTable *table, ScmHashIter *iter)
1182 {
1183 Scm_HashIterInit(iter, SCM_HASH_TABLE_CORE(table));
1184 }
1185
1186 /* TRANSIENT: Pre-0.9 Compatibility routine. Kept for the binary compatibility.
1187 Will be removed on 1.0 */
1188 ScmHashEntry *Scm__HashIterNextCompat(ScmHashIter *iter)
1189 {
1190 ScmDictEntry *e = Scm_HashIterNext(iter);
1191 return (ScmHashEntry*)e;
1192 }
1193
1194 /* Legacy constructor. DEPRECATED. Will go away soon. */
1195 ScmObj Scm_MakeHashTable(ScmHashProc *hashfn,
1196 ScmHashCompareProc *cmpfn SCM_UNUSED,
1197 unsigned int initSize)
1198 {
1199 if (hashfn == (ScmHashProc*)SCM_HASH_EQ) {
1200 return Scm_MakeHashTableSimple(SCM_HASH_EQ, initSize);
1201 } else if (hashfn == (ScmHashProc*)SCM_HASH_EQV) {
1202 return Scm_MakeHashTableSimple(SCM_HASH_EQV, initSize);
1203 } else if (hashfn == (ScmHashProc*)SCM_HASH_EQUAL) {
1204 return Scm_MakeHashTableSimple(SCM_HASH_EQUAL, initSize);
1205 } else if (hashfn == (ScmHashProc*)SCM_HASH_STRING) {
1206 return Scm_MakeHashTableSimple(SCM_HASH_STRING, initSize);
1207 }
1208 return SCM_UNDEFINED;
1209 }
1210 #endif /*GAUCHE_API_VERSION < 1000*/
1211
1212 /* Legacy hash function.
1213 *
1214 * This used to be used for equal?-hashtable hash. It also guaranteed
1215 * that the hash result won't change between runs and among different
1216 * platforms, so it can be used for persistent data.
1217 *
1218 * There are several drawbacks, though. The guaranteed hash value means
1219 * we can't change hash function. The quality of the original hash
1220 * function wasn't good (it behaves terrible on flonums and compnums);
1221 * it's vulnerable to collision attacks; and it had a few bugs in the
1222 * number hash that broke the 'portable' guarantee between platforms.
1223 *
1224 * Since there have already been stored data relying on the original hash
1225 * values, we keep the old function (with bugs fixed) here.
1226 * Scm_Hash() and Scheme's 'hash' function uses this for the backward
1227 * comaptibility, but it is not recommended for the new code.
1228 */
1229
1230 static u_long legacy_number_hash(ScmObj obj);
1231 static u_long legacy_string_hash(ScmString *str);
1232
1233 u_long Scm_Hash(ScmObj obj)
1234 {
1235 if (!SCM_PTRP(obj)) {
1236 u_long hashval;
1237 SMALL_INT_HASH(hashval, (u_long)SCM_WORD(obj));
1238 return hashval&PORTABLE_HASHMASK;
1239 } else if (SCM_NUMBERP(obj)) {
1240 return legacy_number_hash(obj);
1241 } else if (SCM_STRINGP(obj)) {
1242 goto string_hash;
1243 } else if (SCM_PAIRP(obj)) {
1244 u_long h = 0, h2;
1245 ScmObj cp;
1246 SCM_FOR_EACH(cp, obj) {
1247 h2 = Scm_Hash(SCM_CAR(cp));
1248 h = COMBINE(h, h2);
1249 }
1250 h2 = Scm_Hash(cp);
1251 h = COMBINE(h, h2);
1252 return h&PORTABLE_HASHMASK;
1253 } else if (SCM_VECTORP(obj)) {
1254 int siz = SCM_VECTOR_SIZE(obj);
1255 u_long h = 0, h2;
1256 for (int i=0; i<siz; i++) {
1257 h2 = Scm_Hash(SCM_VECTOR_ELEMENT(obj, i));
1258 h = COMBINE(h, h2);
1259 }
1260 return h&PORTABLE_HASHMASK;
1261 } else if (SCM_KEYWORDP(obj)) {
1262 /* If we have keyword and symbol unified, KEYWORD_NAME includes
1263 ':'. Legacy hash didn't consider it. */
1264 #if GAUCHE_KEEP_DISJOINT_KEYWORD_OPTION
1265 if (SCM_SYMBOLP(obj)) {
1266 obj = Scm_Substring(SCM_KEYWORD_NAME(obj), 1, -1, FALSE);
1267 } else {
1268 obj = SCM_OBJ(SCM_KEYWORD_NAME(obj));
1269 }
1270 #else /*!GAUCHE_KEEP_DISJOINT_KEYWORD_OPTION*/
1271 obj = Scm_Substring(SCM_KEYWORD_NAME(obj), 1, -1, FALSE);
1272 #endif /*!GAUCHE_KEEP_DISJOINT_KEYWORD_OPTION*/
1273 goto string_hash;
1274 } else if (SCM_SYMBOLP(obj)) {
1275 obj = SCM_OBJ(SCM_SYMBOL_NAME(obj));
1276 goto string_hash;
1277 } else {
1278 /* Call specialized object-hash method */
1279 ScmObj r = Scm_ApplyRec(SCM_OBJ(&Scm_GenericObjectHash),
1280 SCM_LIST1(obj));
1281 if (SCM_INTP(r)) {
1282 return ((u_long)SCM_INT_VALUE(r))&PORTABLE_HASHMASK;
1283 }
1284 if (SCM_BIGNUMP(r)) {
1285 /* NB: Scm_GetUInteger clamps the result to [0, ULONG_MAX],
1286 but taking the LSW would give better distribution. */
1287 return (SCM_BIGNUM(r)->values[0])&PORTABLE_HASHMASK;
1288 }
1289 Scm_Error("object-hash returned non-integer: %S", r);
1290 return 0; /* dummy */
1291 }
1292 string_hash:
1293 return legacy_string_hash(SCM_STRING(obj));
1294 }
1295
1296 static u_long legacy_flonum_hash(double f)
1297 {
1298 /* Originally the code was just (u_long)(f * 2654435761UL), but that's
1299 UB when the multiplication yields out of range of u_long. I don't
1300 even remember why I adopted that for the hash function in the
1301 first place, but we have to stick to existing hash values recorded
1302 elsewhere.
1303
1304 On x86 with 8087-compatible FPU, (u_long)(d) behaves as follows.
1305 If -2^63 < d < 2^63, the modulo of 2^32 is taken. Otherwise
1306 it yields 0.
1307
1308 On x86 with SSE, the out-of-range value yields #x8000_0000.
1309
1310 On x86_64, if -2^63 < d < 2^64, the modulo of 2^32 is taken.
1311 Otherwise it yields #x8000_0000_0000_0000.
1312
1313 To achieve maximum compatibility with historical data, we
1314 take the range of 8087, and the calculation is adjusted for
1315 x86_64 behavior. There can be a slight discrepancy from the
1316 result of 8087 because of its internal 80bit calculation---for
1317 example, 3.767278962604362e-10 * 2654435761 is just tiny little
1318 bit less than 1.0 but with 64bit calculation it is rounded up
1319 to 1.0. With 80 bit and integer truncation the result is 0 but
1320 with 64bit we get 1.
1321 */
1322 volatile double d = f * 2654435761UL;
1323 static double two_pow_63 = 0.0;
1324 static double minus_two_pow_63 = 0.0;
1325 static double two_pow_32 = 0.0;
1326 static int initialized = FALSE;
1327
1328 if (!initialized) {
1329 /* This is idempotent - no need to lock */
1330 two_pow_63 = ldexp(1.0, 63);
1331 minus_two_pow_63 = -ldexp(1.0, 63);
1332 two_pow_32 = ldexp(1.0, 32);
1333 Scm_AtomicThreadFence();
1334 initialized = TRUE;
1335 }
1336 /* This condition eliminates NaN as well. */
1337 if (!(minus_two_pow_63 < d && d < two_pow_63)) return 0;
1338 if (-0.5 < d && d < 0.5) return 0;
1339
1340 double dm = trunc(fmod(d, two_pow_32));
1341 if (dm < 0) dm += two_pow_32;
1342 return (u_long)trunc(dm);
1343 }
1344
1345 /* Old hash function for numeric objects. This is terrible for flonums,
1346 and we only keep it in order to maintain portable hash value generated
1347 by legacy hash function. */
1348 static u_long legacy_number_hash(ScmObj obj)
1349 {
1350 u_long hashval;
1351 SCM_ASSERT(SCM_NUMBERP(obj));
1352 if (SCM_INTP(obj)) {
1353 SMALL_INT_HASH(hashval, SCM_INT_VALUE(obj));
1354 } else if (SCM_BIGNUMP(obj)) {
1355 u_int i;
1356 u_long u = 0;
1357 for (i=0; i<SCM_BIGNUM_SIZE(obj); i++) {
1358 #if SIZEOF_LONG == 4
1359 u += SCM_BIGNUM(obj)->values[i];
1360 #elif SIZEOF_LONG == 8
1361 u += (SCM_BIGNUM(obj)->values[i] & ((1UL<<32) - 1))
1362 + (SCM_BIGNUM(obj)->values[i] >> 32);
1363 #else
1364 #error "sizeof(long) > 8 platform unsupported"
1365 #endif
1366 }
1367 SMALL_INT_HASH(hashval, u);
1368 } else if (SCM_FLONUMP(obj)) {
1369 hashval = legacy_flonum_hash(SCM_FLONUM_VALUE(obj));
1370 } else if (SCM_RATNUMP(obj)) {
1371 /* Ratnum must already be normalized, so we can simply combine
1372 hashvals of numerator and denominator. */
1373 u_long h1 = legacy_number_hash(SCM_RATNUM_NUMER(obj));
1374 u_long h2 = legacy_number_hash(SCM_RATNUM_DENOM(obj));
1375 hashval = COMBINE(h1, h2);
1376 } else {
1377 hashval =
1378 legacy_flonum_hash(SCM_COMPNUM_REAL(obj)+SCM_COMPNUM_IMAG(obj));
1379 }
1380 return hashval&PORTABLE_HASHMASK;
1381 }
1382
1383 /* Legacy hash function for strings. This isn't very good hash function
1384 either, and it's difficult to adopt salting. */
1385 static u_long legacy_string_hash(ScmString *str)
1386 {
1387 const ScmStringBody *b = SCM_STRING_BODY(str);
1388 const char *p = SCM_STRING_BODY_START(b);
1389 long k = SCM_STRING_BODY_SIZE(b);
1390 u_long hv = 0;
1391 while (k-- > 0) {
1392 hv = (hv<<5) - (hv) + ((unsigned char)*p++);
1393 }
1394 return hv&PORTABLE_HASHMASK;
1395 }