1// Copyright (C) 2016 and later: Unicode, Inc. and others. 2// License & terms of use: http://www.unicode.org/copyright.html 3/* 4****************************************************************************** 5* Copyright (C) 1997-2016, International Business Machines 6* Corporation and others. All Rights Reserved. 7****************************************************************************** 8* Date Name Description 9* 03/22/00 aliu Adapted from original C++ ICU Hashtable. 10* 07/06/01 aliu Modified to support int32_t keys on 11* platforms with sizeof(void*) < 32. 12****************************************************************************** 13*/ 14 15#include "uhash.h" 16#include "unicode/ustring.h" 17#include "cstring.h" 18#include "cmemory.h" 19#include "uassert.h" 20#include "ustr_imp.h" 21 22/* This hashtable is implemented as a double hash. All elements are 23 * stored in a single array with no secondary storage for collision 24 * resolution (no linked list, etc.). When there is a hash collision 25 * (when two unequal keys have the same hashcode) we resolve this by 26 * using a secondary hash. The secondary hash is an increment 27 * computed as a hash function (a different one) of the primary 28 * hashcode. This increment is added to the initial hash value to 29 * obtain further slots assigned to the same hash code. For this to 30 * work, the length of the array and the increment must be relatively 31 * prime. The easiest way to achieve this is to have the length of 32 * the array be prime, and the increment be any value from 33 * 1..length-1. 34 * 35 * Hashcodes are 32-bit integers. We make sure all hashcodes are 36 * non-negative by masking off the top bit. This has two effects: (1) 37 * modulo arithmetic is simplified. If we allowed negative hashcodes, 38 * then when we computed hashcode % length, we could get a negative 39 * result, which we would then have to adjust back into range. It's 40 * simpler to just make hashcodes non-negative. (2) It makes it easy 41 * to check for empty vs. occupied slots in the table. We just mark 42 * empty or deleted slots with a negative hashcode. 43 * 44 * The central function is _uhash_find(). This function looks for a 45 * slot matching the given key and hashcode. If one is found, it 46 * returns a pointer to that slot. If the table is full, and no match 47 * is found, it returns NULL -- in theory. This would make the code 48 * more complicated, since all callers of _uhash_find() would then 49 * have to check for a NULL result. To keep this from happening, we 50 * don't allow the table to fill. When there is only one 51 * empty/deleted slot left, uhash_put() will refuse to increase the 52 * count, and fail. This simplifies the code. In practice, one will 53 * seldom encounter this using default UHashtables. However, if a 54 * hashtable is set to a U_FIXED resize policy, or if memory is 55 * exhausted, then the table may fill. 56 * 57 * High and low water ratios control rehashing. They establish levels 58 * of fullness (from 0 to 1) outside of which the data array is 59 * reallocated and repopulated. Setting the low water ratio to zero 60 * means the table will never shrink. Setting the high water ratio to 61 * one means the table will never grow. The ratios should be 62 * coordinated with the ratio between successive elements of the 63 * PRIMES table, so that when the primeIndex is incremented or 64 * decremented during rehashing, it brings the ratio of count / length 65 * back into the desired range (between low and high water ratios). 66 */ 67 68/******************************************************************** 69 * PRIVATE Constants, Macros 70 ********************************************************************/ 71 72/* This is a list of non-consecutive primes chosen such that 73 * PRIMES[i+1] ~ 2*PRIMES[i]. (Currently, the ratio ranges from 1.81 74 * to 2.18; the inverse ratio ranges from 0.459 to 0.552.) If this 75 * ratio is changed, the low and high water ratios should also be 76 * adjusted to suit. 77 * 78 * These prime numbers were also chosen so that they are the largest 79 * prime number while being less than a power of two. 80 */ 81static const int32_t PRIMES[] = { 82 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 83 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 84 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 85 1073741789, 2147483647 /*, 4294967291 */ 86}; 87 88#define PRIMES_LENGTH UPRV_LENGTHOF(PRIMES) 89#define DEFAULT_PRIME_INDEX 3 90 91/* These ratios are tuned to the PRIMES array such that a resize 92 * places the table back into the zone of non-resizing. That is, 93 * after a call to _uhash_rehash(), a subsequent call to 94 * _uhash_rehash() should do nothing (should not churn). This is only 95 * a potential problem with U_GROW_AND_SHRINK. 96 */ 97static const float RESIZE_POLICY_RATIO_TABLE[6] = { 98 /* low, high water ratio */ 99 0.0F, 0.5F, /* U_GROW: Grow on demand, do not shrink */ 100 0.1F, 0.5F, /* U_GROW_AND_SHRINK: Grow and shrink on demand */ 101 0.0F, 1.0F /* U_FIXED: Never change size */ 102}; 103 104/* 105 Invariants for hashcode values: 106 107 * DELETED < 0 108 * EMPTY < 0 109 * Real hashes >= 0 110 111 Hashcodes may not start out this way, but internally they are 112 adjusted so that they are always positive. We assume 32-bit 113 hashcodes; adjust these constants for other hashcode sizes. 114*/ 115#define HASH_DELETED ((int32_t) 0x80000000) 116#define HASH_EMPTY ((int32_t) HASH_DELETED + 1) 117 118#define IS_EMPTY_OR_DELETED(x) ((x) < 0) 119 120/* This macro expects a UHashTok.pointer as its keypointer and 121 valuepointer parameters */ 122#define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) \ 123 if (hash->keyDeleter != NULL && keypointer != NULL) { \ 124 (*hash->keyDeleter)(keypointer); \ 125 } \ 126 if (hash->valueDeleter != NULL && valuepointer != NULL) { \ 127 (*hash->valueDeleter)(valuepointer); \ 128 } 129 130/* 131 * Constants for hinting whether a key or value is an integer 132 * or a pointer. If a hint bit is zero, then the associated 133 * token is assumed to be an integer. 134 */ 135#define HINT_KEY_POINTER (1) 136#define HINT_VALUE_POINTER (2) 137 138/******************************************************************** 139 * PRIVATE Implementation 140 ********************************************************************/ 141 142static UHashTok 143_uhash_setElement(UHashtable *hash, UHashElement* e, 144 int32_t hashcode, 145 UHashTok key, UHashTok value, int8_t hint) { 146 147 UHashTok oldValue = e->value; 148 if (hash->keyDeleter != NULL && e->key.pointer != NULL && 149 e->key.pointer != key.pointer) { /* Avoid double deletion */ 150 (*hash->keyDeleter)(e->key.pointer); 151 } 152 if (hash->valueDeleter != NULL) { 153 if (oldValue.pointer != NULL && 154 oldValue.pointer != value.pointer) { /* Avoid double deletion */ 155 (*hash->valueDeleter)(oldValue.pointer); 156 } 157 oldValue.pointer = NULL; 158 } 159 /* Compilers should copy the UHashTok union correctly, but even if 160 * they do, memory heap tools (e.g. BoundsChecker) can get 161 * confused when a pointer is cloaked in a union and then copied. 162 * TO ALLEVIATE THIS, we use hints (based on what API the user is 163 * calling) to copy pointers when we know the user thinks 164 * something is a pointer. */ 165 if (hint & HINT_KEY_POINTER) { 166 e->key.pointer = key.pointer; 167 } else { 168 e->key = key; 169 } 170 if (hint & HINT_VALUE_POINTER) { 171 e->value.pointer = value.pointer; 172 } else { 173 e->value = value; 174 } 175 e->hashcode = hashcode; 176 return oldValue; 177} 178 179/** 180 * Assumes that the given element is not empty or deleted. 181 */ 182static UHashTok 183_uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) { 184 UHashTok empty; 185 U_ASSERT(!IS_EMPTY_OR_DELETED(e->hashcode)); 186 --hash->count; 187 empty.pointer = NULL; empty.integer = 0; 188 return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0); 189} 190 191static void 192_uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) { 193 U_ASSERT(hash != NULL); 194 U_ASSERT(((int32_t)policy) >= 0); 195 U_ASSERT(((int32_t)policy) < 3); 196 hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2]; 197 hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1]; 198} 199 200/** 201 * Allocate internal data array of a size determined by the given 202 * prime index. If the index is out of range it is pinned into range. 203 * If the allocation fails the status is set to 204 * U_MEMORY_ALLOCATION_ERROR and all array storage is freed. In 205 * either case the previous array pointer is overwritten. 206 * 207 * Caller must ensure primeIndex is in range 0..PRIME_LENGTH-1. 208 */ 209static void 210_uhash_allocate(UHashtable *hash, 211 int32_t primeIndex, 212 UErrorCode *status) { 213 214 UHashElement *p, *limit; 215 UHashTok emptytok; 216 217 if (U_FAILURE(*status)) return; 218 219 U_ASSERT(primeIndex >= 0 && primeIndex < PRIMES_LENGTH); 220 221 hash->primeIndex = primeIndex; 222 hash->length = PRIMES[primeIndex]; 223 224 p = hash->elements = (UHashElement*) 225 uprv_malloc(sizeof(UHashElement) * hash->length); 226 227 if (hash->elements == NULL) { 228 *status = U_MEMORY_ALLOCATION_ERROR; 229 return; 230 } 231 232 emptytok.pointer = NULL; /* Only one of these two is needed */ 233 emptytok.integer = 0; /* but we don't know which one. */ 234 235 limit = p + hash->length; 236 while (p < limit) { 237 p->key = emptytok; 238 p->value = emptytok; 239 p->hashcode = HASH_EMPTY; 240 ++p; 241 } 242 243 hash->count = 0; 244 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio); 245 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio); 246} 247 248static UHashtable* 249_uhash_init(UHashtable *result, 250 UHashFunction *keyHash, 251 UKeyComparator *keyComp, 252 UValueComparator *valueComp, 253 int32_t primeIndex, 254 UErrorCode *status) 255{ 256 if (U_FAILURE(*status)) return NULL; 257 U_ASSERT(keyHash != NULL); 258 U_ASSERT(keyComp != NULL); 259 260 result->keyHasher = keyHash; 261 result->keyComparator = keyComp; 262 result->valueComparator = valueComp; 263 result->keyDeleter = NULL; 264 result->valueDeleter = NULL; 265 result->allocated = FALSE; 266 _uhash_internalSetResizePolicy(result, U_GROW); 267 268 _uhash_allocate(result, primeIndex, status); 269 270 if (U_FAILURE(*status)) { 271 return NULL; 272 } 273 274 return result; 275} 276 277static UHashtable* 278_uhash_create(UHashFunction *keyHash, 279 UKeyComparator *keyComp, 280 UValueComparator *valueComp, 281 int32_t primeIndex, 282 UErrorCode *status) { 283 UHashtable *result; 284 285 if (U_FAILURE(*status)) return NULL; 286 287 result = (UHashtable*) uprv_malloc(sizeof(UHashtable)); 288 if (result == NULL) { 289 *status = U_MEMORY_ALLOCATION_ERROR; 290 return NULL; 291 } 292 293 _uhash_init(result, keyHash, keyComp, valueComp, primeIndex, status); 294 result->allocated = TRUE; 295 296 if (U_FAILURE(*status)) { 297 uprv_free(result); 298 return NULL; 299 } 300 301 return result; 302} 303 304/** 305 * Look for a key in the table, or if no such key exists, the first 306 * empty slot matching the given hashcode. Keys are compared using 307 * the keyComparator function. 308 * 309 * First find the start position, which is the hashcode modulo 310 * the length. Test it to see if it is: 311 * 312 * a. identical: First check the hash values for a quick check, 313 * then compare keys for equality using keyComparator. 314 * b. deleted 315 * c. empty 316 * 317 * Stop if it is identical or empty, otherwise continue by adding a 318 * "jump" value (moduloing by the length again to keep it within 319 * range) and retesting. For efficiency, there need enough empty 320 * values so that the searchs stop within a reasonable amount of time. 321 * This can be changed by changing the high/low water marks. 322 * 323 * In theory, this function can return NULL, if it is full (no empty 324 * or deleted slots) and if no matching key is found. In practice, we 325 * prevent this elsewhere (in uhash_put) by making sure the last slot 326 * in the table is never filled. 327 * 328 * The size of the table should be prime for this algorithm to work; 329 * otherwise we are not guaranteed that the jump value (the secondary 330 * hash) is relatively prime to the table length. 331 */ 332static UHashElement* 333_uhash_find(const UHashtable *hash, UHashTok key, 334 int32_t hashcode) { 335 336 int32_t firstDeleted = -1; /* assume invalid index */ 337 int32_t theIndex, startIndex; 338 int32_t jump = 0; /* lazy evaluate */ 339 int32_t tableHash; 340 UHashElement *elements = hash->elements; 341 342 hashcode &= 0x7FFFFFFF; /* must be positive */ 343 startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length; 344 345 do { 346 tableHash = elements[theIndex].hashcode; 347 if (tableHash == hashcode) { /* quick check */ 348 if ((*hash->keyComparator)(key, elements[theIndex].key)) { 349 return &(elements[theIndex]); 350 } 351 } else if (!IS_EMPTY_OR_DELETED(tableHash)) { 352 /* We have hit a slot which contains a key-value pair, 353 * but for which the hash code does not match. Keep 354 * looking. 355 */ 356 } else if (tableHash == HASH_EMPTY) { /* empty, end o' the line */ 357 break; 358 } else if (firstDeleted < 0) { /* remember first deleted */ 359 firstDeleted = theIndex; 360 } 361 if (jump == 0) { /* lazy compute jump */ 362 /* The jump value must be relatively prime to the table 363 * length. As long as the length is prime, then any value 364 * 1..length-1 will be relatively prime to it. 365 */ 366 jump = (hashcode % (hash->length - 1)) + 1; 367 } 368 theIndex = (theIndex + jump) % hash->length; 369 } while (theIndex != startIndex); 370 371 if (firstDeleted >= 0) { 372 theIndex = firstDeleted; /* reset if had deleted slot */ 373 } else if (tableHash != HASH_EMPTY) { 374 /* We get to this point if the hashtable is full (no empty or 375 * deleted slots), and we've failed to find a match. THIS 376 * WILL NEVER HAPPEN as long as uhash_put() makes sure that 377 * count is always < length. 378 */ 379 U_ASSERT(FALSE); 380 return NULL; /* Never happens if uhash_put() behaves */ 381 } 382 return &(elements[theIndex]); 383} 384 385/** 386 * Attempt to grow or shrink the data arrays in order to make the 387 * count fit between the high and low water marks. hash_put() and 388 * hash_remove() call this method when the count exceeds the high or 389 * low water marks. This method may do nothing, if memory allocation 390 * fails, or if the count is already in range, or if the length is 391 * already at the low or high limit. In any case, upon return the 392 * arrays will be valid. 393 */ 394static void 395_uhash_rehash(UHashtable *hash, UErrorCode *status) { 396 397 UHashElement *old = hash->elements; 398 int32_t oldLength = hash->length; 399 int32_t newPrimeIndex = hash->primeIndex; 400 int32_t i; 401 402 if (hash->count > hash->highWaterMark) { 403 if (++newPrimeIndex >= PRIMES_LENGTH) { 404 return; 405 } 406 } else if (hash->count < hash->lowWaterMark) { 407 if (--newPrimeIndex < 0) { 408 return; 409 } 410 } else { 411 return; 412 } 413 414 _uhash_allocate(hash, newPrimeIndex, status); 415 416 if (U_FAILURE(*status)) { 417 hash->elements = old; 418 hash->length = oldLength; 419 return; 420 } 421 422 for (i = oldLength - 1; i >= 0; --i) { 423 if (!IS_EMPTY_OR_DELETED(old[i].hashcode)) { 424 UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode); 425 U_ASSERT(e != NULL); 426 U_ASSERT(e->hashcode == HASH_EMPTY); 427 e->key = old[i].key; 428 e->value = old[i].value; 429 e->hashcode = old[i].hashcode; 430 ++hash->count; 431 } 432 } 433 434 uprv_free(old); 435} 436 437static UHashTok 438_uhash_remove(UHashtable *hash, 439 UHashTok key) { 440 /* First find the position of the key in the table. If the object 441 * has not been removed already, remove it. If the user wanted 442 * keys deleted, then delete it also. We have to put a special 443 * hashcode in that position that means that something has been 444 * deleted, since when we do a find, we have to continue PAST any 445 * deleted values. 446 */ 447 UHashTok result; 448 UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key)); 449 U_ASSERT(e != NULL); 450 result.pointer = NULL; 451 result.integer = 0; 452 if (!IS_EMPTY_OR_DELETED(e->hashcode)) { 453 result = _uhash_internalRemoveElement(hash, e); 454 if (hash->count < hash->lowWaterMark) { 455 UErrorCode status = U_ZERO_ERROR; 456 _uhash_rehash(hash, &status); 457 } 458 } 459 return result; 460} 461 462static UHashTok 463_uhash_put(UHashtable *hash, 464 UHashTok key, 465 UHashTok value, 466 int8_t hint, 467 UErrorCode *status) { 468 469 /* Put finds the position in the table for the new value. If the 470 * key is already in the table, it is deleted, if there is a 471 * non-NULL keyDeleter. Then the key, the hash and the value are 472 * all put at the position in their respective arrays. 473 */ 474 int32_t hashcode; 475 UHashElement* e; 476 UHashTok emptytok; 477 478 if (U_FAILURE(*status)) { 479 goto err; 480 } 481 U_ASSERT(hash != NULL); 482 /* Cannot always check pointer here or iSeries sees NULL every time. */ 483 if ((hint & HINT_VALUE_POINTER) && value.pointer == NULL) { 484 /* Disallow storage of NULL values, since NULL is returned by 485 * get() to indicate an absent key. Storing NULL == removing. 486 */ 487 return _uhash_remove(hash, key); 488 } 489 if (hash->count > hash->highWaterMark) { 490 _uhash_rehash(hash, status); 491 if (U_FAILURE(*status)) { 492 goto err; 493 } 494 } 495 496 hashcode = (*hash->keyHasher)(key); 497 e = _uhash_find(hash, key, hashcode); 498 U_ASSERT(e != NULL); 499 500 if (IS_EMPTY_OR_DELETED(e->hashcode)) { 501 /* Important: We must never actually fill the table up. If we 502 * do so, then _uhash_find() will return NULL, and we'll have 503 * to check for NULL after every call to _uhash_find(). To 504 * avoid this we make sure there is always at least one empty 505 * or deleted slot in the table. This only is a problem if we 506 * are out of memory and rehash isn't working. 507 */ 508 ++hash->count; 509 if (hash->count == hash->length) { 510 /* Don't allow count to reach length */ 511 --hash->count; 512 *status = U_MEMORY_ALLOCATION_ERROR; 513 goto err; 514 } 515 } 516 517 /* We must in all cases handle storage properly. If there was an 518 * old key, then it must be deleted (if the deleter != NULL). 519 * Make hashcodes stored in table positive. 520 */ 521 return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value, hint); 522 523 err: 524 /* If the deleters are non-NULL, this method adopts its key and/or 525 * value arguments, and we must be sure to delete the key and/or 526 * value in all cases, even upon failure. 527 */ 528 HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer); 529 emptytok.pointer = NULL; emptytok.integer = 0; 530 return emptytok; 531} 532 533 534/******************************************************************** 535 * PUBLIC API 536 ********************************************************************/ 537 538U_CAPI UHashtable* U_EXPORT2 539uhash_open(UHashFunction *keyHash, 540 UKeyComparator *keyComp, 541 UValueComparator *valueComp, 542 UErrorCode *status) { 543 544 return _uhash_create(keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status); 545} 546 547U_CAPI UHashtable* U_EXPORT2 548uhash_openSize(UHashFunction *keyHash, 549 UKeyComparator *keyComp, 550 UValueComparator *valueComp, 551 int32_t size, 552 UErrorCode *status) { 553 554 /* Find the smallest index i for which PRIMES[i] >= size. */ 555 int32_t i = 0; 556 while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) { 557 ++i; 558 } 559 560 return _uhash_create(keyHash, keyComp, valueComp, i, status); 561} 562 563U_CAPI UHashtable* U_EXPORT2 564uhash_init(UHashtable *fillinResult, 565 UHashFunction *keyHash, 566 UKeyComparator *keyComp, 567 UValueComparator *valueComp, 568 UErrorCode *status) { 569 570 return _uhash_init(fillinResult, keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status); 571} 572 573U_CAPI void U_EXPORT2 574uhash_close(UHashtable *hash) { 575 if (hash == NULL) { 576 return; 577 } 578 if (hash->elements != NULL) { 579 if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) { 580 int32_t pos=UHASH_FIRST; 581 UHashElement *e; 582 while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) { 583 HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer); 584 } 585 } 586 uprv_free(hash->elements); 587 hash->elements = NULL; 588 } 589 if (hash->allocated) { 590 uprv_free(hash); 591 } 592} 593 594U_CAPI UHashFunction *U_EXPORT2 595uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) { 596 UHashFunction *result = hash->keyHasher; 597 hash->keyHasher = fn; 598 return result; 599} 600 601U_CAPI UKeyComparator *U_EXPORT2 602uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) { 603 UKeyComparator *result = hash->keyComparator; 604 hash->keyComparator = fn; 605 return result; 606} 607U_CAPI UValueComparator *U_EXPORT2 608uhash_setValueComparator(UHashtable *hash, UValueComparator *fn){ 609 UValueComparator *result = hash->valueComparator; 610 hash->valueComparator = fn; 611 return result; 612} 613 614U_CAPI UObjectDeleter *U_EXPORT2 615uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) { 616 UObjectDeleter *result = hash->keyDeleter; 617 hash->keyDeleter = fn; 618 return result; 619} 620 621U_CAPI UObjectDeleter *U_EXPORT2 622uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) { 623 UObjectDeleter *result = hash->valueDeleter; 624 hash->valueDeleter = fn; 625 return result; 626} 627 628U_CAPI void U_EXPORT2 629uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) { 630 UErrorCode status = U_ZERO_ERROR; 631 _uhash_internalSetResizePolicy(hash, policy); 632 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio); 633 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio); 634 _uhash_rehash(hash, &status); 635} 636 637U_CAPI int32_t U_EXPORT2 638uhash_count(const UHashtable *hash) { 639 return hash->count; 640} 641 642U_CAPI void* U_EXPORT2 643uhash_get(const UHashtable *hash, 644 const void* key) { 645 UHashTok keyholder; 646 keyholder.pointer = (void*) key; 647 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer; 648} 649 650U_CAPI void* U_EXPORT2 651uhash_iget(const UHashtable *hash, 652 int32_t key) { 653 UHashTok keyholder; 654 keyholder.integer = key; 655 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer; 656} 657 658U_CAPI int32_t U_EXPORT2 659uhash_geti(const UHashtable *hash, 660 const void* key) { 661 UHashTok keyholder; 662 keyholder.pointer = (void*) key; 663 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer; 664} 665 666U_CAPI int32_t U_EXPORT2 667uhash_igeti(const UHashtable *hash, 668 int32_t key) { 669 UHashTok keyholder; 670 keyholder.integer = key; 671 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer; 672} 673 674U_CAPI void* U_EXPORT2 675uhash_put(UHashtable *hash, 676 void* key, 677 void* value, 678 UErrorCode *status) { 679 UHashTok keyholder, valueholder; 680 keyholder.pointer = key; 681 valueholder.pointer = value; 682 return _uhash_put(hash, keyholder, valueholder, 683 HINT_KEY_POINTER | HINT_VALUE_POINTER, 684 status).pointer; 685} 686 687U_CAPI void* U_EXPORT2 688uhash_iput(UHashtable *hash, 689 int32_t key, 690 void* value, 691 UErrorCode *status) { 692 UHashTok keyholder, valueholder; 693 keyholder.integer = key; 694 valueholder.pointer = value; 695 return _uhash_put(hash, keyholder, valueholder, 696 HINT_VALUE_POINTER, 697 status).pointer; 698} 699 700U_CAPI int32_t U_EXPORT2 701uhash_puti(UHashtable *hash, 702 void* key, 703 int32_t value, 704 UErrorCode *status) { 705 UHashTok keyholder, valueholder; 706 keyholder.pointer = key; 707 valueholder.integer = value; 708 return _uhash_put(hash, keyholder, valueholder, 709 HINT_KEY_POINTER, 710 status).integer; 711} 712 713 714U_CAPI int32_t U_EXPORT2 715uhash_iputi(UHashtable *hash, 716 int32_t key, 717 int32_t value, 718 UErrorCode *status) { 719 UHashTok keyholder, valueholder; 720 keyholder.integer = key; 721 valueholder.integer = value; 722 return _uhash_put(hash, keyholder, valueholder, 723 0, /* neither is a ptr */ 724 status).integer; 725} 726 727U_CAPI void* U_EXPORT2 728uhash_remove(UHashtable *hash, 729 const void* key) { 730 UHashTok keyholder; 731 keyholder.pointer = (void*) key; 732 return _uhash_remove(hash, keyholder).pointer; 733} 734 735U_CAPI void* U_EXPORT2 736uhash_iremove(UHashtable *hash, 737 int32_t key) { 738 UHashTok keyholder; 739 keyholder.integer = key; 740 return _uhash_remove(hash, keyholder).pointer; 741} 742 743U_CAPI int32_t U_EXPORT2 744uhash_removei(UHashtable *hash, 745 const void* key) { 746 UHashTok keyholder; 747 keyholder.pointer = (void*) key; 748 return _uhash_remove(hash, keyholder).integer; 749} 750 751U_CAPI int32_t U_EXPORT2 752uhash_iremovei(UHashtable *hash, 753 int32_t key) { 754 UHashTok keyholder; 755 keyholder.integer = key; 756 return _uhash_remove(hash, keyholder).integer; 757} 758 759U_CAPI void U_EXPORT2 760uhash_removeAll(UHashtable *hash) { 761 int32_t pos = UHASH_FIRST; 762 const UHashElement *e; 763 U_ASSERT(hash != NULL); 764 if (hash->count != 0) { 765 while ((e = uhash_nextElement(hash, &pos)) != NULL) { 766 uhash_removeElement(hash, e); 767 } 768 } 769 U_ASSERT(hash->count == 0); 770} 771 772U_CAPI const UHashElement* U_EXPORT2 773uhash_find(const UHashtable *hash, const void* key) { 774 UHashTok keyholder; 775 const UHashElement *e; 776 keyholder.pointer = (void*) key; 777 e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder)); 778 return IS_EMPTY_OR_DELETED(e->hashcode) ? NULL : e; 779} 780 781U_CAPI const UHashElement* U_EXPORT2 782uhash_nextElement(const UHashtable *hash, int32_t *pos) { 783 /* Walk through the array until we find an element that is not 784 * EMPTY and not DELETED. 785 */ 786 int32_t i; 787 U_ASSERT(hash != NULL); 788 for (i = *pos + 1; i < hash->length; ++i) { 789 if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) { 790 *pos = i; 791 return &(hash->elements[i]); 792 } 793 } 794 795 /* No more elements */ 796 return NULL; 797} 798 799U_CAPI void* U_EXPORT2 800uhash_removeElement(UHashtable *hash, const UHashElement* e) { 801 U_ASSERT(hash != NULL); 802 U_ASSERT(e != NULL); 803 if (!IS_EMPTY_OR_DELETED(e->hashcode)) { 804 UHashElement *nce = (UHashElement *)e; 805 return _uhash_internalRemoveElement(hash, nce).pointer; 806 } 807 return NULL; 808} 809 810/******************************************************************** 811 * UHashTok convenience 812 ********************************************************************/ 813 814/** 815 * Return a UHashTok for an integer. 816 */ 817/*U_CAPI UHashTok U_EXPORT2 818uhash_toki(int32_t i) { 819 UHashTok tok; 820 tok.integer = i; 821 return tok; 822}*/ 823 824/** 825 * Return a UHashTok for a pointer. 826 */ 827/*U_CAPI UHashTok U_EXPORT2 828uhash_tokp(void* p) { 829 UHashTok tok; 830 tok.pointer = p; 831 return tok; 832}*/ 833 834/******************************************************************** 835 * PUBLIC Key Hash Functions 836 ********************************************************************/ 837 838U_CAPI int32_t U_EXPORT2 839uhash_hashUChars(const UHashTok key) { 840 const UChar *s = (const UChar *)key.pointer; 841 return s == NULL ? 0 : ustr_hashUCharsN(s, u_strlen(s)); 842} 843 844U_CAPI int32_t U_EXPORT2 845uhash_hashChars(const UHashTok key) { 846 const char *s = (const char *)key.pointer; 847 return s == NULL ? 0 : ustr_hashCharsN(s, uprv_strlen(s)); 848} 849 850U_CAPI int32_t U_EXPORT2 851uhash_hashIChars(const UHashTok key) { 852 const char *s = (const char *)key.pointer; 853 return s == NULL ? 0 : ustr_hashICharsN(s, uprv_strlen(s)); 854} 855 856U_CAPI UBool U_EXPORT2 857uhash_equals(const UHashtable* hash1, const UHashtable* hash2){ 858 int32_t count1, count2, pos, i; 859 860 if(hash1==hash2){ 861 return TRUE; 862 } 863 864 /* 865 * Make sure that we are comparing 2 valid hashes of the same type 866 * with valid comparison functions. 867 * Without valid comparison functions, a binary comparison 868 * of the hash values will yield random results on machines 869 * with 64-bit pointers and 32-bit integer hashes. 870 * A valueComparator is normally optional. 871 */ 872 if (hash1==NULL || hash2==NULL || 873 hash1->keyComparator != hash2->keyComparator || 874 hash1->valueComparator != hash2->valueComparator || 875 hash1->valueComparator == NULL) 876 { 877 /* 878 Normally we would return an error here about incompatible hash tables, 879 but we return FALSE instead. 880 */ 881 return FALSE; 882 } 883 884 count1 = uhash_count(hash1); 885 count2 = uhash_count(hash2); 886 if(count1!=count2){ 887 return FALSE; 888 } 889 890 pos=UHASH_FIRST; 891 for(i=0; i<count1; i++){ 892 const UHashElement* elem1 = uhash_nextElement(hash1, &pos); 893 const UHashTok key1 = elem1->key; 894 const UHashTok val1 = elem1->value; 895 /* here the keys are not compared, instead the key form hash1 is used to fetch 896 * value from hash2. If the hashes are equal then then both hashes should 897 * contain equal values for the same key! 898 */ 899 const UHashElement* elem2 = _uhash_find(hash2, key1, hash2->keyHasher(key1)); 900 const UHashTok val2 = elem2->value; 901 if(hash1->valueComparator(val1, val2)==FALSE){ 902 return FALSE; 903 } 904 } 905 return TRUE; 906} 907 908/******************************************************************** 909 * PUBLIC Comparator Functions 910 ********************************************************************/ 911 912U_CAPI UBool U_EXPORT2 913uhash_compareUChars(const UHashTok key1, const UHashTok key2) { 914 const UChar *p1 = (const UChar*) key1.pointer; 915 const UChar *p2 = (const UChar*) key2.pointer; 916 if (p1 == p2) { 917 return TRUE; 918 } 919 if (p1 == NULL || p2 == NULL) { 920 return FALSE; 921 } 922 while (*p1 != 0 && *p1 == *p2) { 923 ++p1; 924 ++p2; 925 } 926 return (UBool)(*p1 == *p2); 927} 928 929U_CAPI UBool U_EXPORT2 930uhash_compareChars(const UHashTok key1, const UHashTok key2) { 931 const char *p1 = (const char*) key1.pointer; 932 const char *p2 = (const char*) key2.pointer; 933 if (p1 == p2) { 934 return TRUE; 935 } 936 if (p1 == NULL || p2 == NULL) { 937 return FALSE; 938 } 939 while (*p1 != 0 && *p1 == *p2) { 940 ++p1; 941 ++p2; 942 } 943 return (UBool)(*p1 == *p2); 944} 945 946U_CAPI UBool U_EXPORT2 947uhash_compareIChars(const UHashTok key1, const UHashTok key2) { 948 const char *p1 = (const char*) key1.pointer; 949 const char *p2 = (const char*) key2.pointer; 950 if (p1 == p2) { 951 return TRUE; 952 } 953 if (p1 == NULL || p2 == NULL) { 954 return FALSE; 955 } 956 while (*p1 != 0 && uprv_tolower(*p1) == uprv_tolower(*p2)) { 957 ++p1; 958 ++p2; 959 } 960 return (UBool)(*p1 == *p2); 961} 962 963/******************************************************************** 964 * PUBLIC int32_t Support Functions 965 ********************************************************************/ 966 967U_CAPI int32_t U_EXPORT2 968uhash_hashLong(const UHashTok key) { 969 return key.integer; 970} 971 972U_CAPI UBool U_EXPORT2 973uhash_compareLong(const UHashTok key1, const UHashTok key2) { 974 return (UBool)(key1.integer == key2.integer); 975} 976