| 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 |
} |