00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "uhash.h"
00012 #include "unicode/ustring.h"
00013 #include "cstring.h"
00014 #include "cmemory.h"
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072 static int32_t PRIMES[] = {
00073 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771,
00074 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617,
00075 16777259, 33554467, 67108879, 134217757, 268435459, 536870923,
00076 1073741827, 2147483647
00077 };
00078
00079 #define PRIMES_LENGTH (sizeof(PRIMES) / sizeof(PRIMES[0]))
00080
00081
00082
00083
00084
00085
00086
00087 static const float RESIZE_POLICY_RATIO_TABLE[6] = {
00088
00089 0.0F, 0.5F,
00090 0.1F, 0.5F,
00091 0.0F, 1.0F
00092 };
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105 #define HASH_DELETED ((int32_t) 0x80000000)
00106 #define HASH_EMPTY ((int32_t) HASH_DELETED + 1)
00107
00108 #define IS_EMPTY_OR_DELETED(x) ((x) < 0)
00109
00110 #define HASH_DELETE_KEY_VALUE(hash, key, value) \
00111 if (hash->keyDeleter != NULL && key != NULL) { \
00112 (*hash->keyDeleter)(key); \
00113 } \
00114 if (hash->valueDeleter != NULL && value != NULL) { \
00115 (*hash->valueDeleter)(value); \
00116 }
00117
00118
00119
00120
00121
00122
00123
00124
00125 #ifdef HASH_DEBUG
00126
00127 #include <stdio.h>
00128
00129 #define assert(exp) (void)( (exp) || (_assert(#exp, __FILE__, __LINE__), 0) )
00130
00131 static void _assert(const char* exp, const char* file, int line) {
00132 printf("ERROR: assert(%s) failed: %s, line %d\n",
00133 exp, file, line);
00134 }
00135
00136 #else
00137
00138 #define assert(exp)
00139
00140 #endif
00141
00142
00143
00144
00145
00146 static UHashtable* _uhash_create(UHashFunction keyHash, UKeyComparator keyComp,
00147 int32_t primeIndex, UErrorCode *status);
00148
00149 static void _uhash_allocate(UHashtable *hash, int32_t primeIndex,
00150 UErrorCode *status);
00151
00152 static void _uhash_rehash(UHashtable *hash);
00153
00154 static UHashElement* _uhash_find(const UHashtable *hash, const void* key,
00155 int32_t hashcode);
00156
00157 static void* _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e);
00158
00159 static void* _uhash_setElement(UHashtable* hash, UHashElement* e,
00160 int32_t hashcode, void* key, void* value);
00161
00162 static void _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy);
00163
00164
00165
00166
00167
00168 U_CAPI UHashtable*
00169 uhash_open(UHashFunction keyHash, UKeyComparator keyComp,
00170 UErrorCode *status) {
00171
00172 return _uhash_create(keyHash, keyComp, 3, status);
00173 }
00174
00175 U_CAPI UHashtable*
00176 uhash_openSize(UHashFunction keyHash, UKeyComparator keyComp,
00177 int32_t size,
00178 UErrorCode *status) {
00179
00180
00181 int32_t i = 0;
00182 while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) {
00183 ++i;
00184 }
00185
00186 return _uhash_create(keyHash, keyComp, i, status);
00187 }
00188
00189 U_CAPI void
00190 uhash_close(UHashtable *hash) {
00191 assert(hash != NULL);
00192 if (hash->elements != NULL) {
00193 if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) {
00194 int32_t pos=-1;
00195 UHashElement *e;
00196 while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) {
00197 HASH_DELETE_KEY_VALUE(hash, e->key, e->value);
00198 }
00199 }
00200 uprv_free(hash->elements);
00201 hash->elements = NULL;
00202 }
00203 uprv_free(hash);
00204 }
00205
00206 U_CAPI UHashFunction
00207 uhash_setKeyHasher(UHashtable *hash, UHashFunction fn) {
00208 UHashFunction result = hash->keyHasher;
00209 hash->keyHasher = fn;
00210 return result;
00211 }
00212
00213 U_CAPI UKeyComparator
00214 uhash_setKeyComparator(UHashtable *hash, UKeyComparator fn) {
00215 UKeyComparator result = hash->keyComparator;
00216 hash->keyComparator = fn;
00217 return result;
00218 }
00219
00220 U_CAPI UObjectDeleter
00221 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter fn) {
00222 UObjectDeleter result = hash->keyDeleter;
00223 hash->keyDeleter = fn;
00224 return result;
00225 }
00226
00227 U_CAPI UObjectDeleter
00228 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter fn) {
00229 UObjectDeleter result = hash->valueDeleter;
00230 hash->valueDeleter = fn;
00231 return result;
00232 }
00233
00234 U_CAPI void
00235 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
00236 _uhash_internalSetResizePolicy(hash, policy);
00237 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
00238 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
00239 _uhash_rehash(hash);
00240 }
00241
00242 U_CAPI int32_t
00243 uhash_count(const UHashtable *hash) {
00244 return hash->count;
00245 }
00246
00247 U_CAPI void*
00248 uhash_get(const UHashtable *hash,
00249 const void* key) {
00250 return _uhash_find(hash, key, hash->keyHasher(key))->value;
00251 }
00252
00253 U_CAPI void*
00254 uhash_put(UHashtable *hash,
00255 void* key,
00256 void* value,
00257 UErrorCode *status) {
00258
00259
00260
00261
00262
00263
00264 int32_t hashcode;
00265 UHashElement* e;
00266
00267 if (U_FAILURE(*status)) {
00268 goto err;
00269 }
00270 assert(hash != NULL);
00271 if (value == NULL) {
00272
00273
00274
00275 return uhash_remove(hash, key);
00276 }
00277 if (hash->count > hash->highWaterMark) {
00278 _uhash_rehash(hash);
00279 }
00280
00281 hashcode = (*hash->keyHasher)(key);
00282 e = _uhash_find(hash, key, hashcode);
00283 assert(e != NULL);
00284
00285 if (IS_EMPTY_OR_DELETED(e->hashcode)) {
00286
00287
00288
00289
00290
00291
00292
00293 ++hash->count;
00294 if (hash->count == hash->length) {
00295
00296 --hash->count;
00297 *status = U_MEMORY_ALLOCATION_ERROR;
00298 goto err;
00299 }
00300 }
00301
00302
00303
00304
00305
00306 return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value);
00307
00308 err:
00309
00310
00311
00312
00313 HASH_DELETE_KEY_VALUE(hash, key, value);
00314 return NULL;
00315 }
00316
00317 U_CAPI void*
00318 uhash_remove(UHashtable *hash,
00319 const void* key) {
00320
00321
00322
00323
00324
00325
00326
00327 void* result = NULL;
00328 UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key));
00329 assert(e != NULL);
00330 if (!IS_EMPTY_OR_DELETED(e->hashcode)) {
00331 result = _uhash_internalRemoveElement(hash, e);
00332 if (hash->count < hash->lowWaterMark) {
00333 _uhash_rehash(hash);
00334 }
00335 }
00336 return result;
00337 }
00338
00339 U_CAPI void
00340 uhash_removeAll(UHashtable *hash) {
00341 int32_t pos = -1;
00342 const UHashElement *e;
00343 assert(hash != NULL);
00344 if (hash->count != 0) {
00345 while ((e = uhash_nextElement(hash, &pos)) != NULL) {
00346 uhash_removeElement(hash, e);
00347 }
00348 }
00349 assert(hash->count == 0);
00350 }
00351
00352 U_CAPI const UHashElement*
00353 uhash_nextElement(const UHashtable *hash, int32_t *pos) {
00354
00355
00356
00357 int32_t i;
00358 assert(hash != NULL);
00359 for (i = *pos + 1; i < hash->length; ++i) {
00360 if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) {
00361 *pos = i;
00362 return &(hash->elements[i]);
00363 }
00364 }
00365
00366
00367 return NULL;
00368 }
00369
00370 U_CAPI void*
00371 uhash_removeElement(UHashtable *hash, const UHashElement* e) {
00372 assert(hash != NULL);
00373 assert(e != NULL);
00374 if (!IS_EMPTY_OR_DELETED(e->hashcode)) {
00375 return _uhash_internalRemoveElement(hash, (UHashElement*) e);
00376 }
00377 return NULL;
00378 }
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393 #define STRING_HASH(TYPE, STRLEN, DEREF) \
00394 int32_t hash = 0; \
00395 if (key != NULL) { \
00396 const TYPE *p = (const TYPE*) key; \
00397 int32_t len = STRLEN; \
00398 int32_t inc = ((len - 32) / 32) + 1; \
00399 const TYPE *limit = p + len; \
00400 while (p<limit) { \
00401 hash = (hash * 37) + DEREF; \
00402 p += inc; \
00403 } \
00404 } \
00405 return hash
00406
00407 U_CAPI int32_t
00408 uhash_hashUChars(const void *key) {
00409 STRING_HASH(UChar, u_strlen(p), *p);
00410 }
00411
00412
00413 U_CAPI int32_t
00414 uhash_hashUCharsN(const UChar *key, int32_t length) {
00415 STRING_HASH(UChar, length, *p);
00416 }
00417
00418 U_CAPI int32_t
00419 uhash_hashChars(const void *key) {
00420 STRING_HASH(uint8_t, uprv_strlen((char*)p), *p);
00421 }
00422
00423 U_CAPI int32_t
00424 uhash_hashIChars(const void *key) {
00425 STRING_HASH(uint8_t, uprv_strlen((char*)p), uprv_tolower(*p));
00426 }
00427
00428
00429
00430
00431
00432 U_CAPI UBool
00433 uhash_compareUChars(const void *key1, const void *key2) {
00434 const UChar *p1 = (const UChar*) key1;
00435 const UChar *p2 = (const UChar*) key2;
00436 if (p1 == p2) {
00437 return TRUE;
00438 }
00439 if (p1 == NULL || p2 == NULL) {
00440 return FALSE;
00441 }
00442 while (*p1 != 0 && *p1 == *p2) {
00443 ++p1;
00444 ++p2;
00445 }
00446 return (UBool)(*p1 == *p2);
00447 }
00448
00449 U_CAPI UBool
00450 uhash_compareChars(const void *key1, const void *key2) {
00451 const char *p1 = (const char*) key1;
00452 const char *p2 = (const char*) key2;
00453 if (p1 == p2) {
00454 return TRUE;
00455 }
00456 if (p1 == NULL || p2 == NULL) {
00457 return FALSE;
00458 }
00459 while (*p1 != 0 && *p1 == *p2) {
00460 ++p1;
00461 ++p2;
00462 }
00463 return (UBool)(*p1 == *p2);
00464 }
00465
00466 U_CAPI UBool
00467 uhash_compareIChars(const void *key1, const void *key2) {
00468 const char *p1 = (const char*) key1;
00469 const char *p2 = (const char*) key2;
00470 if (p1 == p2) {
00471 return TRUE;
00472 }
00473 if (p1 == NULL || p2 == NULL) {
00474 return FALSE;
00475 }
00476 while (*p1 != 0 && uprv_tolower(*p1) == uprv_tolower(*p2)) {
00477 ++p1;
00478 ++p2;
00479 }
00480 return (UBool)(*p1 == *p2);
00481 }
00482
00483
00484
00485
00486
00487 U_CAPI int32_t
00488 uhash_hashLong(const void *key) {
00489 return (int32_t) key;
00490 }
00491
00492 U_CAPI UBool
00493 uhash_compareLong(const void *key1, const void *key2) {
00494 return (UBool)(key1 == key2);
00495 }
00496
00497
00498
00499
00500
00501 U_CAPI void
00502 uhash_freeBlock(void *obj) {
00503 uprv_free(obj);
00504 }
00505
00506
00507
00508
00509
00510 static UHashtable*
00511 _uhash_create(UHashFunction keyHash, UKeyComparator keyComp,
00512 int32_t primeIndex,
00513 UErrorCode *status) {
00514 UHashtable *result;
00515
00516 if (U_FAILURE(*status)) return NULL;
00517 assert(keyHash != NULL);
00518 assert(keyComp != NULL);
00519
00520 result = (UHashtable*) uprv_malloc(sizeof(UHashtable));
00521 if (result == NULL) {
00522 *status = U_MEMORY_ALLOCATION_ERROR;
00523 return NULL;
00524 }
00525
00526 result->keyHasher = keyHash;
00527 result->keyComparator = keyComp;
00528 result->keyDeleter = NULL;
00529 result->valueDeleter = NULL;
00530 _uhash_internalSetResizePolicy(result, U_GROW);
00531
00532 _uhash_allocate(result, primeIndex, status);
00533
00534 if (U_FAILURE(*status)) {
00535 uprv_free(result);
00536 return NULL;
00537 }
00538
00539 return result;
00540 }
00541
00551 static void
00552 _uhash_allocate(UHashtable *hash,
00553 int32_t primeIndex,
00554 UErrorCode *status) {
00555
00556 UHashElement *p, *limit;
00557
00558 if (U_FAILURE(*status)) return;
00559
00560 assert(primeIndex >= 0 && primeIndex < PRIMES_LENGTH);
00561
00562 hash->primeIndex = primeIndex;
00563 hash->length = PRIMES[primeIndex];
00564
00565 p = hash->elements = (UHashElement*)
00566 uprv_malloc(sizeof(UHashElement) * hash->length);
00567
00568 if (hash->elements == NULL) {
00569 *status = U_MEMORY_ALLOCATION_ERROR;
00570 return;
00571 }
00572
00573 limit = p + hash->length;
00574 while (p < limit) {
00575 p->key = NULL;
00576 p->value = NULL;
00577 p->hashcode = HASH_EMPTY;
00578 ++p;
00579 }
00580
00581 hash->count = 0;
00582 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
00583 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
00584 }
00585
00595 static void
00596 _uhash_rehash(UHashtable *hash) {
00597
00598 UHashElement *old = hash->elements;
00599 int32_t oldLength = hash->length;
00600 int32_t newPrimeIndex = hash->primeIndex;
00601 int32_t i;
00602 UErrorCode status = U_ZERO_ERROR;
00603
00604 if (hash->count > hash->highWaterMark) {
00605 if (++newPrimeIndex >= PRIMES_LENGTH) {
00606 return;
00607 }
00608 } else if (hash->count < hash->lowWaterMark) {
00609 if (--newPrimeIndex < 0) {
00610 return;
00611 }
00612 } else {
00613 return;
00614 }
00615
00616 _uhash_allocate(hash, newPrimeIndex, &status);
00617
00618 if (U_FAILURE(status)) {
00619 hash->elements = old;
00620 hash->length = oldLength;
00621 return;
00622 }
00623
00624 for (i = oldLength - 1; i >= 0; --i) {
00625 if (!IS_EMPTY_OR_DELETED(old[i].hashcode)) {
00626 UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode);
00627 assert(e != NULL);
00628 assert(e->hashcode == HASH_EMPTY);
00629 e->key = old[i].key;
00630 e->value = old[i].value;
00631 e->hashcode = old[i].hashcode;
00632 ++hash->count;
00633 }
00634 }
00635
00636 uprv_free(old);
00637 }
00638
00667 static UHashElement*
00668 _uhash_find(const UHashtable *hash, const void* key,
00669 int32_t hashcode) {
00670
00671 int32_t firstDeleted = -1;
00672 int32_t theIndex, startIndex;
00673 int32_t jump = 0;
00674 int32_t tableHash;
00675
00676 hashcode &= 0x7FFFFFFF;
00677 startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length;
00678
00679 do {
00680 tableHash = hash->elements[theIndex].hashcode;
00681 if (tableHash == hashcode) {
00682 if ((*hash->keyComparator)(key, hash->elements[theIndex].key)) {
00683 return &(hash->elements[theIndex]);
00684 }
00685 } else if (!IS_EMPTY_OR_DELETED(tableHash)) {
00686
00687
00688
00689
00690 } else if (tableHash == HASH_EMPTY) {
00691 break;
00692 } else if (firstDeleted < 0) {
00693 firstDeleted = theIndex;
00694 }
00695 if (jump == 0) {
00696
00697
00698
00699
00700 jump = (hashcode % (hash->length - 1)) + 1;
00701 }
00702 theIndex = (theIndex + jump) % hash->length;
00703 } while (theIndex != startIndex);
00704
00705 if (firstDeleted >= 0) {
00706 theIndex = firstDeleted;
00707 } else if (tableHash != HASH_EMPTY) {
00708
00709
00710
00711
00712
00713 assert(FALSE);
00714 return NULL;
00715 }
00716 return &(hash->elements[theIndex]);
00717 }
00718
00719 static void*
00720 _uhash_setElement(UHashtable *hash, UHashElement* e,
00721 int32_t hashcode, void* key, void* value) {
00722
00723 void* oldKey = e->key;
00724 void* oldValue = e->value;
00725 if (hash->keyDeleter != NULL && oldKey != NULL &&
00726 oldKey != key) {
00727 (*hash->keyDeleter)(oldKey);
00728 }
00729 if (oldValue == value) {
00730 oldValue = NULL;
00731 }
00732 if (hash->valueDeleter != NULL && oldValue != NULL) {
00733 (*hash->valueDeleter)(oldValue);
00734 oldValue = NULL;
00735 }
00736 e->key = key;
00737 e->value = value;
00738 e->hashcode = hashcode;
00739 return oldValue;
00740 }
00741
00745 static void*
00746 _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) {
00747 assert(!IS_EMPTY_OR_DELETED(e->hashcode));
00748 --hash->count;
00749 return _uhash_setElement(hash, e, HASH_DELETED, NULL, NULL);
00750 }
00751
00752 static void
00753 _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
00754 assert(hash == 0);
00755 assert(((int32_t)policy) >= 0);
00756 assert(((int32_t)policy) < 3);
00757 hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2];
00758 hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1];
00759 }