source/common/uhash.c

   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  */
  81 static 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  */
  97 static 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
 142 static 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  */
 182 static 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
 191 static 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  */
 209 static 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
 248 static 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
 277 static 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  */
 332 static 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  */
 394 static 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
 437 static 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
 462 static 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
 538 U_CAPI UHashtable* U_EXPORT2
 539 uhash_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
 547 U_CAPI UHashtable* U_EXPORT2
 548 uhash_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
 563 U_CAPI UHashtable* U_EXPORT2
 564 uhash_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
 573 U_CAPI void U_EXPORT2
 574 uhash_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
 594 U_CAPI UHashFunction *U_EXPORT2
 595 uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) {
 596     UHashFunction *result = hash->keyHasher;
 597     hash->keyHasher = fn;
 598     return result;
 599 }
 600
 601 U_CAPI UKeyComparator *U_EXPORT2
 602 uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) {
 603     UKeyComparator *result = hash->keyComparator;
 604     hash->keyComparator = fn;
 605     return result;
 606 }
 607 U_CAPI UValueComparator *U_EXPORT2
 608 uhash_setValueComparator(UHashtable *hash, UValueComparator *fn){
 609     UValueComparator *result = hash->valueComparator;
 610     hash->valueComparator = fn;
 611     return result;
 612 }
 613
 614 U_CAPI UObjectDeleter *U_EXPORT2
 615 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) {
 616     UObjectDeleter *result = hash->keyDeleter;
 617     hash->keyDeleter = fn;
 618     return result;
 619 }
 620
 621 U_CAPI UObjectDeleter *U_EXPORT2
 622 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) {
 623     UObjectDeleter *result = hash->valueDeleter;
 624     hash->valueDeleter = fn;
 625     return result;
 626 }
 627
 628 U_CAPI void U_EXPORT2
 629 uhash_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
 637 U_CAPI int32_t U_EXPORT2
 638 uhash_count(const UHashtable *hash) {
 639     return hash->count;
 640 }
 641
 642 U_CAPI void* U_EXPORT2
 643 uhash_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
 650 U_CAPI void* U_EXPORT2
 651 uhash_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
 658 U_CAPI int32_t U_EXPORT2
 659 uhash_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
 666 U_CAPI int32_t U_EXPORT2
 667 uhash_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
 674 U_CAPI void* U_EXPORT2
 675 uhash_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
 687 U_CAPI void* U_EXPORT2
 688 uhash_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
 700 U_CAPI int32_t U_EXPORT2
 701 uhash_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
 714 U_CAPI int32_t U_EXPORT2
 715 uhash_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
 727 U_CAPI void* U_EXPORT2
 728 uhash_remove(UHashtable *hash,
 729              const void* key) {
 730     UHashTok keyholder;
 731     keyholder.pointer = (void*) key;
 732     return _uhash_remove(hash, keyholder).pointer;
 733 }
 734
 735 U_CAPI void* U_EXPORT2
 736 uhash_iremove(UHashtable *hash,
 737               int32_t key) {
 738     UHashTok keyholder;
 739     keyholder.integer = key;
 740     return _uhash_remove(hash, keyholder).pointer;
 741 }
 742
 743 U_CAPI int32_t U_EXPORT2
 744 uhash_removei(UHashtable *hash,
 745               const void* key) {
 746     UHashTok keyholder;
 747     keyholder.pointer = (void*) key;
 748     return _uhash_remove(hash, keyholder).integer;
 749 }
 750
 751 U_CAPI int32_t U_EXPORT2
 752 uhash_iremovei(UHashtable *hash,
 753                int32_t key) {
 754     UHashTok keyholder;
 755     keyholder.integer = key;
 756     return _uhash_remove(hash, keyholder).integer;
 757 }
 758
 759 U_CAPI void U_EXPORT2
 760 uhash_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
 772 U_CAPI const UHashElement* U_EXPORT2
 773 uhash_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
 781 U_CAPI const UHashElement* U_EXPORT2
 782 uhash_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
 799 U_CAPI void* U_EXPORT2
 800 uhash_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
 818 uhash_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
 828 uhash_tokp(void* p) {
 829     UHashTok tok;
 830     tok.pointer = p;
 831     return tok;
 832 }*/
 833
 834 /********************************************************************
 835  * PUBLIC Key Hash Functions
 836  ********************************************************************/
 837
 838 U_CAPI int32_t U_EXPORT2
 839 uhash_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
 844 U_CAPI int32_t U_EXPORT2
 845 uhash_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
 850 U_CAPI int32_t U_EXPORT2
 851 uhash_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
 856 U_CAPI UBool U_EXPORT2
 857 uhash_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
 912 U_CAPI UBool U_EXPORT2
 913 uhash_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
 929 U_CAPI UBool U_EXPORT2
 930 uhash_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
 946 U_CAPI UBool U_EXPORT2
 947 uhash_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
 967 U_CAPI int32_t U_EXPORT2
 968 uhash_hashLong(const UHashTok key) {
 969     return key.integer;
 970 }
 971
 972 U_CAPI UBool U_EXPORT2
 973 uhash_compareLong(const UHashTok key1, const UHashTok key2) {
 974     return (UBool)(key1.integer == key2.integer);
 975 }