The Tor Browser / file revision

 /*

 ******************************************************************************

 *   Copyright (C) 1997-2011, International Business Machines

 *   Corporation and others.  All Rights Reserved.

 ******************************************************************************

 *   Date        Name        Description

 *   03/22/00    aliu        Adapted from original C++ ICU Hashtable.

 *   07/06/01    aliu        Modified to support int32_t keys on

 *                           platforms with sizeof(void*) < 32.

 ******************************************************************************

 */

 #include "uhash.h"

 #include "unicode/ustring.h"

 #include "cstring.h"

 #include "cmemory.h"

 #include "uassert.h"

 #include "ustr_imp.h"

 /* This hashtable is implemented as a double hash.  All elements are

  * stored in a single array with no secondary storage for collision

  * resolution (no linked list, etc.).  When there is a hash collision

  * (when two unequal keys have the same hashcode) we resolve this by

  * using a secondary hash.  The secondary hash is an increment

  * computed as a hash function (a different one) of the primary

  * hashcode.  This increment is added to the initial hash value to

  * obtain further slots assigned to the same hash code.  For this to

  * work, the length of the array and the increment must be relatively

  * prime.  The easiest way to achieve this is to have the length of

  * the array be prime, and the increment be any value from

  * 1..length-1.

  *

  * Hashcodes are 32-bit integers.  We make sure all hashcodes are

  * non-negative by masking off the top bit.  This has two effects: (1)

  * modulo arithmetic is simplified.  If we allowed negative hashcodes,

  * then when we computed hashcode % length, we could get a negative

  * result, which we would then have to adjust back into range.  It's

  * simpler to just make hashcodes non-negative. (2) It makes it easy

  * to check for empty vs. occupied slots in the table.  We just mark

  * empty or deleted slots with a negative hashcode.

  *

  * The central function is _uhash_find().  This function looks for a

  * slot matching the given key and hashcode.  If one is found, it

  * returns a pointer to that slot.  If the table is full, and no match

  * is found, it returns NULL -- in theory.  This would make the code

  * more complicated, since all callers of _uhash_find() would then

  * have to check for a NULL result.  To keep this from happening, we

  * don't allow the table to fill.  When there is only one

  * empty/deleted slot left, uhash_put() will refuse to increase the

  * count, and fail.  This simplifies the code.  In practice, one will

  * seldom encounter this using default UHashtables.  However, if a

  * hashtable is set to a U_FIXED resize policy, or if memory is

  * exhausted, then the table may fill.

  *

  * High and low water ratios control rehashing.  They establish levels

  * of fullness (from 0 to 1) outside of which the data array is

  * reallocated and repopulated.  Setting the low water ratio to zero

  * means the table will never shrink.  Setting the high water ratio to

  * one means the table will never grow.  The ratios should be

  * coordinated with the ratio between successive elements of the

  * PRIMES table, so that when the primeIndex is incremented or

  * decremented during rehashing, it brings the ratio of count / length

  * back into the desired range (between low and high water ratios).

  */

 /********************************************************************

  * PRIVATE Constants, Macros

  ********************************************************************/

 /* This is a list of non-consecutive primes chosen such that

  * PRIMES[i+1] ~ 2*PRIMES[i].  (Currently, the ratio ranges from 1.81

  * to 2.18; the inverse ratio ranges from 0.459 to 0.552.)  If this

  * ratio is changed, the low and high water ratios should also be

  * adjusted to suit.

  *

  * These prime numbers were also chosen so that they are the largest

  * prime number while being less than a power of two.

  */

 static const int32_t PRIMES[] = {

     13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749,

     65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593,

     16777213, 33554393, 67108859, 134217689, 268435399, 536870909,

     1073741789, 2147483647 /*, 4294967291 */

 };

 #define PRIMES_LENGTH (sizeof(PRIMES) / sizeof(PRIMES[0]))

 #define DEFAULT_PRIME_INDEX 3

 /* These ratios are tuned to the PRIMES array such that a resize

  * places the table back into the zone of non-resizing.  That is,

  * after a call to _uhash_rehash(), a subsequent call to

  * _uhash_rehash() should do nothing (should not churn).  This is only

  * a potential problem with U_GROW_AND_SHRINK.

  */

 static const float RESIZE_POLICY_RATIO_TABLE[6] = {

     /* low, high water ratio */

     0.0F, 0.5F, /* U_GROW: Grow on demand, do not shrink */

     0.1F, 0.5F, /* U_GROW_AND_SHRINK: Grow and shrink on demand */

     0.0F, 1.0F  /* U_FIXED: Never change size */

 };

 /*

   Invariants for hashcode values:

   * DELETED < 0

   * EMPTY < 0

   * Real hashes >= 0

   Hashcodes may not start out this way, but internally they are

   adjusted so that they are always positive.  We assume 32-bit

   hashcodes; adjust these constants for other hashcode sizes.

 */

 #define HASH_DELETED    ((int32_t) 0x80000000)

 #define HASH_EMPTY      ((int32_t) HASH_DELETED + 1)

 #define IS_EMPTY_OR_DELETED(x) ((x) < 0)

 /* This macro expects a UHashTok.pointer as its keypointer and

    valuepointer parameters */

 #define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) \

             if (hash->keyDeleter != NULL && keypointer != NULL) { \

                 (*hash->keyDeleter)(keypointer); \

             } \

             if (hash->valueDeleter != NULL && valuepointer != NULL) { \

                 (*hash->valueDeleter)(valuepointer); \

             }

 /*

  * Constants for hinting whether a key or value is an integer

  * or a pointer.  If a hint bit is zero, then the associated

  * token is assumed to be an integer.

  */

 #define HINT_KEY_POINTER   (1)

 #define HINT_VALUE_POINTER (2)

 /********************************************************************

  * PRIVATE Implementation

  ********************************************************************/

 static UHashTok

 _uhash_setElement(UHashtable *hash, UHashElement* e,

                   int32_t hashcode,

                   UHashTok key, UHashTok value, int8_t hint) {

     UHashTok oldValue = e->value;

     if (hash->keyDeleter != NULL && e->key.pointer != NULL &&

         e->key.pointer != key.pointer) { /* Avoid double deletion */

         (*hash->keyDeleter)(e->key.pointer);

     }

     if (hash->valueDeleter != NULL) {

         if (oldValue.pointer != NULL &&

             oldValue.pointer != value.pointer) { /* Avoid double deletion */

             (*hash->valueDeleter)(oldValue.pointer);

         }

         oldValue.pointer = NULL;

     }

     /* Compilers should copy the UHashTok union correctly, but even if

      * they do, memory heap tools (e.g. BoundsChecker) can get

      * confused when a pointer is cloaked in a union and then copied.

      * TO ALLEVIATE THIS, we use hints (based on what API the user is

      * calling) to copy pointers when we know the user thinks

      * something is a pointer. */

     if (hint & HINT_KEY_POINTER) {

         e->key.pointer = key.pointer;

     } else {

         e->key = key;

     }

     if (hint & HINT_VALUE_POINTER) {

         e->value.pointer = value.pointer;

     } else {

         e->value = value;

     }

     e->hashcode = hashcode;

     return oldValue;

 }

 /**

  * Assumes that the given element is not empty or deleted.

  */

 static UHashTok

 _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) {

     UHashTok empty;

     U_ASSERT(!IS_EMPTY_OR_DELETED(e->hashcode));

     --hash->count;

     empty.pointer = NULL; empty.integer = 0;

     return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0);

 }

 static void

 _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {

     U_ASSERT(hash != NULL);

     U_ASSERT(((int32_t)policy) >= 0);

     U_ASSERT(((int32_t)policy) < 3);

     hash->lowWaterRatio  = RESIZE_POLICY_RATIO_TABLE[policy * 2];

     hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1];

 }

 /**

  * Allocate internal data array of a size determined by the given

  * prime index.  If the index is out of range it is pinned into range.

  * If the allocation fails the status is set to

  * U_MEMORY_ALLOCATION_ERROR and all array storage is freed.  In

  * either case the previous array pointer is overwritten.

  *

  * Caller must ensure primeIndex is in range 0..PRIME_LENGTH-1.

  */

 static void

 _uhash_allocate(UHashtable *hash,

                 int32_t primeIndex,

                 UErrorCode *status) {

     UHashElement *p, *limit;

     UHashTok emptytok;

     if (U_FAILURE(*status)) return;

     U_ASSERT(primeIndex >= 0 && primeIndex < PRIMES_LENGTH);

     hash->primeIndex = primeIndex;

     hash->length = PRIMES[primeIndex];

     p = hash->elements = (UHashElement*)

         uprv_malloc(sizeof(UHashElement) * hash->length);

     if (hash->elements == NULL) {

         *status = U_MEMORY_ALLOCATION_ERROR;

         return;

     }

     emptytok.pointer = NULL; /* Only one of these two is needed */

     emptytok.integer = 0;    /* but we don't know which one. */

     limit = p + hash->length;

     while (p < limit) {

         p->key = emptytok;

         p->value = emptytok;

         p->hashcode = HASH_EMPTY;

         ++p;

     }

     hash->count = 0;

     hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);

     hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);

 }

 static UHashtable*

 _uhash_init(UHashtable *result,

               UHashFunction *keyHash, 

               UKeyComparator *keyComp,

               UValueComparator *valueComp,

               int32_t primeIndex,

               UErrorCode *status)

 {

     if (U_FAILURE(*status)) return NULL;

     U_ASSERT(keyHash != NULL);

     U_ASSERT(keyComp != NULL);

     result->keyHasher       = keyHash;

     result->keyComparator   = keyComp;

     result->valueComparator = valueComp;

     result->keyDeleter      = NULL;

     result->valueDeleter    = NULL;

     result->allocated       = FALSE;

     _uhash_internalSetResizePolicy(result, U_GROW);

     _uhash_allocate(result, primeIndex, status);

     if (U_FAILURE(*status)) {

         return NULL;

     }

     return result;

 }

 static UHashtable*

 _uhash_create(UHashFunction *keyHash, 

               UKeyComparator *keyComp,

               UValueComparator *valueComp,

               int32_t primeIndex,

               UErrorCode *status) {

     UHashtable *result;

     if (U_FAILURE(*status)) return NULL;

     result = (UHashtable*) uprv_malloc(sizeof(UHashtable));

     if (result == NULL) {

         *status = U_MEMORY_ALLOCATION_ERROR;

         return NULL;

     }

     _uhash_init(result, keyHash, keyComp, valueComp, primeIndex, status);

     result->allocated       = TRUE;

     if (U_FAILURE(*status)) {

         uprv_free(result);

         return NULL;

     }

     return result;

 }

 /**

  * Look for a key in the table, or if no such key exists, the first

  * empty slot matching the given hashcode.  Keys are compared using

  * the keyComparator function.

  *

  * First find the start position, which is the hashcode modulo

  * the length.  Test it to see if it is:

  *

  * a. identical:  First check the hash values for a quick check,

  *    then compare keys for equality using keyComparator.

  * b. deleted

  * c. empty

  *

  * Stop if it is identical or empty, otherwise continue by adding a

  * "jump" value (moduloing by the length again to keep it within

  * range) and retesting.  For efficiency, there need enough empty

  * values so that the searchs stop within a reasonable amount of time.

  * This can be changed by changing the high/low water marks.

  *

  * In theory, this function can return NULL, if it is full (no empty

  * or deleted slots) and if no matching key is found.  In practice, we

  * prevent this elsewhere (in uhash_put) by making sure the last slot

  * in the table is never filled.

  *

  * The size of the table should be prime for this algorithm to work;

  * otherwise we are not guaranteed that the jump value (the secondary

  * hash) is relatively prime to the table length.

  */

 static UHashElement*

 _uhash_find(const UHashtable *hash, UHashTok key,

             int32_t hashcode) {

     int32_t firstDeleted = -1;  /* assume invalid index */

     int32_t theIndex, startIndex;

     int32_t jump = 0; /* lazy evaluate */

     int32_t tableHash;

     UHashElement *elements = hash->elements;

     hashcode &= 0x7FFFFFFF; /* must be positive */

     startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length;

     do {

         tableHash = elements[theIndex].hashcode;

         if (tableHash == hashcode) {          /* quick check */

             if ((*hash->keyComparator)(key, elements[theIndex].key)) {

                 return &(elements[theIndex]);

             }

         } else if (!IS_EMPTY_OR_DELETED(tableHash)) {

             /* We have hit a slot which contains a key-value pair,

              * but for which the hash code does not match.  Keep

              * looking.

              */

         } else if (tableHash == HASH_EMPTY) { /* empty, end o' the line */

             break;

         } else if (firstDeleted < 0) { /* remember first deleted */

             firstDeleted = theIndex;

         }

         if (jump == 0) { /* lazy compute jump */

             /* The jump value must be relatively prime to the table

              * length.  As long as the length is prime, then any value

              * 1..length-1 will be relatively prime to it.

              */

             jump = (hashcode % (hash->length - 1)) + 1;

         }

         theIndex = (theIndex + jump) % hash->length;

     } while (theIndex != startIndex);

     if (firstDeleted >= 0) {

         theIndex = firstDeleted; /* reset if had deleted slot */

     } else if (tableHash != HASH_EMPTY) {

         /* We get to this point if the hashtable is full (no empty or

          * deleted slots), and we've failed to find a match.  THIS

          * WILL NEVER HAPPEN as long as uhash_put() makes sure that

          * count is always < length.

          */

         U_ASSERT(FALSE);

         return NULL; /* Never happens if uhash_put() behaves */

     }

     return &(elements[theIndex]);

 }

 /**

  * Attempt to grow or shrink the data arrays in order to make the

  * count fit between the high and low water marks.  hash_put() and

  * hash_remove() call this method when the count exceeds the high or

  * low water marks.  This method may do nothing, if memory allocation

  * fails, or if the count is already in range, or if the length is

  * already at the low or high limit.  In any case, upon return the

  * arrays will be valid.

  */

 static void

 _uhash_rehash(UHashtable *hash, UErrorCode *status) {

     UHashElement *old = hash->elements;

     int32_t oldLength = hash->length;

     int32_t newPrimeIndex = hash->primeIndex;

     int32_t i;

     if (hash->count > hash->highWaterMark) {

         if (++newPrimeIndex >= PRIMES_LENGTH) {

             return;

         }

     } else if (hash->count < hash->lowWaterMark) {

         if (--newPrimeIndex < 0) {

             return;

         }

     } else {

         return;

     }

     _uhash_allocate(hash, newPrimeIndex, status);

     if (U_FAILURE(*status)) {

         hash->elements = old;

         hash->length = oldLength;       

         return;

     }

     for (i = oldLength - 1; i >= 0; --i) {

         if (!IS_EMPTY_OR_DELETED(old[i].hashcode)) {

             UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode);

             U_ASSERT(e != NULL);

             U_ASSERT(e->hashcode == HASH_EMPTY);

             e->key = old[i].key;

             e->value = old[i].value;

             e->hashcode = old[i].hashcode;

             ++hash->count;

         }

     }

     uprv_free(old);

 }

 static UHashTok

 _uhash_remove(UHashtable *hash,

               UHashTok key) {

     /* First find the position of the key in the table.  If the object

      * has not been removed already, remove it.  If the user wanted

      * keys deleted, then delete it also.  We have to put a special

      * hashcode in that position that means that something has been

      * deleted, since when we do a find, we have to continue PAST any

      * deleted values.

      */

     UHashTok result;

     UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key));

     U_ASSERT(e != NULL);

     result.pointer = NULL;

     result.integer = 0;

     if (!IS_EMPTY_OR_DELETED(e->hashcode)) {

         result = _uhash_internalRemoveElement(hash, e);

         if (hash->count < hash->lowWaterMark) {

             UErrorCode status = U_ZERO_ERROR;

             _uhash_rehash(hash, &status);

         }

     }

     return result;

 }

 static UHashTok

 _uhash_put(UHashtable *hash,

            UHashTok key,

            UHashTok value,

            int8_t hint,

            UErrorCode *status) {

     /* Put finds the position in the table for the new value.  If the

      * key is already in the table, it is deleted, if there is a

      * non-NULL keyDeleter.  Then the key, the hash and the value are

      * all put at the position in their respective arrays.

      */

     int32_t hashcode;

     UHashElement* e;

     UHashTok emptytok;

     if (U_FAILURE(*status)) {

         goto err;

     }

     U_ASSERT(hash != NULL);

     /* Cannot always check pointer here or iSeries sees NULL every time. */

     if ((hint & HINT_VALUE_POINTER) && value.pointer == NULL) {

         /* Disallow storage of NULL values, since NULL is returned by

          * get() to indicate an absent key.  Storing NULL == removing.

          */

         return _uhash_remove(hash, key);

     }

     if (hash->count > hash->highWaterMark) {

         _uhash_rehash(hash, status);

         if (U_FAILURE(*status)) {

             goto err;

         }

     }

     hashcode = (*hash->keyHasher)(key);

     e = _uhash_find(hash, key, hashcode);

     U_ASSERT(e != NULL);

     if (IS_EMPTY_OR_DELETED(e->hashcode)) {

         /* Important: We must never actually fill the table up.  If we

          * do so, then _uhash_find() will return NULL, and we'll have

          * to check for NULL after every call to _uhash_find().  To

          * avoid this we make sure there is always at least one empty

          * or deleted slot in the table.  This only is a problem if we

          * are out of memory and rehash isn't working.

          */

         ++hash->count;

         if (hash->count == hash->length) {

             /* Don't allow count to reach length */

             --hash->count;

             *status = U_MEMORY_ALLOCATION_ERROR;

             goto err;

         }

     }

     /* We must in all cases handle storage properly.  If there was an

      * old key, then it must be deleted (if the deleter != NULL).

      * Make hashcodes stored in table positive.

      */

     return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value, hint);

  err:

     /* If the deleters are non-NULL, this method adopts its key and/or

      * value arguments, and we must be sure to delete the key and/or

      * value in all cases, even upon failure.

      */

     HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer);

     emptytok.pointer = NULL; emptytok.integer = 0;

     return emptytok;

 }

 /********************************************************************

  * PUBLIC API

  ********************************************************************/

 U_CAPI UHashtable* U_EXPORT2

 uhash_open(UHashFunction *keyHash, 

            UKeyComparator *keyComp,

            UValueComparator *valueComp,

            UErrorCode *status) {

     return _uhash_create(keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status);

 }

 U_CAPI UHashtable* U_EXPORT2

 uhash_openSize(UHashFunction *keyHash, 

                UKeyComparator *keyComp,

                UValueComparator *valueComp,

                int32_t size,

                UErrorCode *status) {

     /* Find the smallest index i for which PRIMES[i] >= size. */

     int32_t i = 0;

     while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) {

         ++i;

     }

     return _uhash_create(keyHash, keyComp, valueComp, i, status);

 }

 U_CAPI UHashtable* U_EXPORT2

 uhash_init(UHashtable *fillinResult,

            UHashFunction *keyHash, 

            UKeyComparator *keyComp,

            UValueComparator *valueComp,

            UErrorCode *status) {

     return _uhash_init(fillinResult, keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status);

 }

 U_CAPI void U_EXPORT2

 uhash_close(UHashtable *hash) {

     if (hash == NULL) {

         return;

     }

     if (hash->elements != NULL) {

         if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) {

             int32_t pos=-1;

             UHashElement *e;

             while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) {

                 HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer);

             }

         }

         uprv_free(hash->elements);

         hash->elements = NULL;

     }

     if (hash->allocated) {

         uprv_free(hash);

     }

 }

 U_CAPI UHashFunction *U_EXPORT2

 uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) {

     UHashFunction *result = hash->keyHasher;

     hash->keyHasher = fn;

     return result;

 }

 U_CAPI UKeyComparator *U_EXPORT2

 uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) {

     UKeyComparator *result = hash->keyComparator;

     hash->keyComparator = fn;

     return result;

 }

 U_CAPI UValueComparator *U_EXPORT2 

 uhash_setValueComparator(UHashtable *hash, UValueComparator *fn){

     UValueComparator *result = hash->valueComparator;

     hash->valueComparator = fn;

     return result;

 }

 U_CAPI UObjectDeleter *U_EXPORT2

 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) {

     UObjectDeleter *result = hash->keyDeleter;

     hash->keyDeleter = fn;

     return result;

 }

 U_CAPI UObjectDeleter *U_EXPORT2

 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) {

     UObjectDeleter *result = hash->valueDeleter;

     hash->valueDeleter = fn;

     return result;

 }

 U_CAPI void U_EXPORT2

 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {

     UErrorCode status = U_ZERO_ERROR;

     _uhash_internalSetResizePolicy(hash, policy);

     hash->lowWaterMark  = (int32_t)(hash->length * hash->lowWaterRatio);

     hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);    

     _uhash_rehash(hash, &status);

 }

 U_CAPI int32_t U_EXPORT2

 uhash_count(const UHashtable *hash) {

     return hash->count;

 }

 U_CAPI void* U_EXPORT2

 uhash_get(const UHashtable *hash,

           const void* key) {

     UHashTok keyholder;

     keyholder.pointer = (void*) key;

     return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;

 }

 U_CAPI void* U_EXPORT2

 uhash_iget(const UHashtable *hash,

            int32_t key) {

     UHashTok keyholder;

     keyholder.integer = key;

     return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;

 }

 U_CAPI int32_t U_EXPORT2

 uhash_geti(const UHashtable *hash,

            const void* key) {

     UHashTok keyholder;

     keyholder.pointer = (void*) key;

     return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;

 }

 U_CAPI int32_t U_EXPORT2

 uhash_igeti(const UHashtable *hash,

            int32_t key) {

     UHashTok keyholder;

     keyholder.integer = key;

     return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;

 }

 U_CAPI void* U_EXPORT2

 uhash_put(UHashtable *hash,

           void* key,

           void* value,

           UErrorCode *status) {

     UHashTok keyholder, valueholder;

     keyholder.pointer = key;

     valueholder.pointer = value;

     return _uhash_put(hash, keyholder, valueholder,

                       HINT_KEY_POINTER | HINT_VALUE_POINTER,

                       status).pointer;

 }

 U_CAPI void* U_EXPORT2

 uhash_iput(UHashtable *hash,

            int32_t key,

            void* value,

            UErrorCode *status) {

     UHashTok keyholder, valueholder;

     keyholder.integer = key;

     valueholder.pointer = value;

     return _uhash_put(hash, keyholder, valueholder,

                       HINT_VALUE_POINTER,

                       status).pointer;

 }

 U_CAPI int32_t U_EXPORT2

 uhash_puti(UHashtable *hash,

            void* key,

            int32_t value,

            UErrorCode *status) {

     UHashTok keyholder, valueholder;

     keyholder.pointer = key;

     valueholder.integer = value;

     return _uhash_put(hash, keyholder, valueholder,

                       HINT_KEY_POINTER,

                       status).integer;

 }

 U_CAPI int32_t U_EXPORT2

 uhash_iputi(UHashtable *hash,

            int32_t key,

            int32_t value,

            UErrorCode *status) {

     UHashTok keyholder, valueholder;

     keyholder.integer = key;

     valueholder.integer = value;

     return _uhash_put(hash, keyholder, valueholder,

                       0, /* neither is a ptr */

                       status).integer;

 }

 U_CAPI void* U_EXPORT2

 uhash_remove(UHashtable *hash,

              const void* key) {

     UHashTok keyholder;

     keyholder.pointer = (void*) key;

     return _uhash_remove(hash, keyholder).pointer;

 }

 U_CAPI void* U_EXPORT2

 uhash_iremove(UHashtable *hash,

               int32_t key) {

     UHashTok keyholder;

     keyholder.integer = key;

     return _uhash_remove(hash, keyholder).pointer;

 }

 U_CAPI int32_t U_EXPORT2

 uhash_removei(UHashtable *hash,

               const void* key) {

     UHashTok keyholder;

     keyholder.pointer = (void*) key;

     return _uhash_remove(hash, keyholder).integer;

 }

 U_CAPI int32_t U_EXPORT2

 uhash_iremovei(UHashtable *hash,

                int32_t key) {

     UHashTok keyholder;

     keyholder.integer = key;

     return _uhash_remove(hash, keyholder).integer;

 }

 U_CAPI void U_EXPORT2

 uhash_removeAll(UHashtable *hash) {

     int32_t pos = -1;

     const UHashElement *e;

     U_ASSERT(hash != NULL);

     if (hash->count != 0) {

         while ((e = uhash_nextElement(hash, &pos)) != NULL) {

             uhash_removeElement(hash, e);

         }

     }

     U_ASSERT(hash->count == 0);

 }

 U_CAPI const UHashElement* U_EXPORT2

 uhash_find(const UHashtable *hash, const void* key) {

     UHashTok keyholder;

     const UHashElement *e;

     keyholder.pointer = (void*) key;

     e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));

     return IS_EMPTY_OR_DELETED(e->hashcode) ? NULL : e;

 }

 U_CAPI const UHashElement* U_EXPORT2

 uhash_nextElement(const UHashtable *hash, int32_t *pos) {

     /* Walk through the array until we find an element that is not

      * EMPTY and not DELETED.

      */

     int32_t i;

     U_ASSERT(hash != NULL);

     for (i = *pos + 1; i < hash->length; ++i) {

         if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) {

             *pos = i;

             return &(hash->elements[i]);

         }

     }

     /* No more elements */

     return NULL;

 }

 U_CAPI void* U_EXPORT2

 uhash_removeElement(UHashtable *hash, const UHashElement* e) {

     U_ASSERT(hash != NULL);

     U_ASSERT(e != NULL);

     if (!IS_EMPTY_OR_DELETED(e->hashcode)) {

         UHashElement *nce = (UHashElement *)e;

         return _uhash_internalRemoveElement(hash, nce).pointer;

     }

     return NULL;

 }

 /********************************************************************

  * UHashTok convenience

  ********************************************************************/

 /**

  * Return a UHashTok for an integer.

  */

 /*U_CAPI UHashTok U_EXPORT2

 uhash_toki(int32_t i) {

     UHashTok tok;

     tok.integer = i;

     return tok;

 }*/

 /**

  * Return a UHashTok for a pointer.

  */

 /*U_CAPI UHashTok U_EXPORT2

 uhash_tokp(void* p) {

     UHashTok tok;

     tok.pointer = p;

     return tok;

 }*/

 /********************************************************************

  * PUBLIC Key Hash Functions

  ********************************************************************/

 U_CAPI int32_t U_EXPORT2

 uhash_hashUChars(const UHashTok key) {

     const UChar *s = (const UChar *)key.pointer;

     return s == NULL ? 0 : ustr_hashUCharsN(s, u_strlen(s));

 }

 U_CAPI int32_t U_EXPORT2

 uhash_hashChars(const UHashTok key) {

     const char *s = (const char *)key.pointer;

     return s == NULL ? 0 : ustr_hashCharsN(s, uprv_strlen(s));

 }

 U_CAPI int32_t U_EXPORT2

 uhash_hashIChars(const UHashTok key) {

     const char *s = (const char *)key.pointer;

     return s == NULL ? 0 : ustr_hashICharsN(s, uprv_strlen(s));

 }

 U_CAPI UBool U_EXPORT2 

 uhash_equals(const UHashtable* hash1, const UHashtable* hash2){

     int32_t count1, count2, pos, i;

     if(hash1==hash2){

         return TRUE;

     }

     /*

      * Make sure that we are comparing 2 valid hashes of the same type

      * with valid comparison functions.

      * Without valid comparison functions, a binary comparison

      * of the hash values will yield random results on machines

      * with 64-bit pointers and 32-bit integer hashes.

      * A valueComparator is normally optional.

      */

     if (hash1==NULL || hash2==NULL ||

         hash1->keyComparator != hash2->keyComparator ||

         hash1->valueComparator != hash2->valueComparator ||

         hash1->valueComparator == NULL)

     {

         /*

         Normally we would return an error here about incompatible hash tables,

         but we return FALSE instead.

         */

         return FALSE;

     }

     count1 = uhash_count(hash1);

     count2 = uhash_count(hash2);

     if(count1!=count2){

         return FALSE;

     }

     pos=-1;

     for(i=0; i<count1; i++){

         const UHashElement* elem1 = uhash_nextElement(hash1, &pos);

         const UHashTok key1 = elem1->key;

         const UHashTok val1 = elem1->value;

         /* here the keys are not compared, instead the key form hash1 is used to fetch

          * value from hash2. If the hashes are equal then then both hashes should 

          * contain equal values for the same key!

          */

         const UHashElement* elem2 = _uhash_find(hash2, key1, hash2->keyHasher(key1));

         const UHashTok val2 = elem2->value;

         if(hash1->valueComparator(val1, val2)==FALSE){

             return FALSE;

         }

     }

     return TRUE;

 }

 /********************************************************************

  * PUBLIC Comparator Functions

  ********************************************************************/

 U_CAPI UBool U_EXPORT2

 uhash_compareUChars(const UHashTok key1, const UHashTok key2) {

     const UChar *p1 = (const UChar*) key1.pointer;

     const UChar *p2 = (const UChar*) key2.pointer;

     if (p1 == p2) {

         return TRUE;

     }

     if (p1 == NULL || p2 == NULL) {

         return FALSE;

     }

     while (*p1 != 0 && *p1 == *p2) {

         ++p1;

         ++p2;

     }

     return (UBool)(*p1 == *p2);

 }

 U_CAPI UBool U_EXPORT2

 uhash_compareChars(const UHashTok key1, const UHashTok key2) {

     const char *p1 = (const char*) key1.pointer;

     const char *p2 = (const char*) key2.pointer;

     if (p1 == p2) {

         return TRUE;

     }

     if (p1 == NULL || p2 == NULL) {

         return FALSE;

     }

     while (*p1 != 0 && *p1 == *p2) {

         ++p1;

         ++p2;

     }

     return (UBool)(*p1 == *p2);

 }

 U_CAPI UBool U_EXPORT2

 uhash_compareIChars(const UHashTok key1, const UHashTok key2) {

     const char *p1 = (const char*) key1.pointer;

     const char *p2 = (const char*) key2.pointer;

     if (p1 == p2) {

         return TRUE;

     }

     if (p1 == NULL || p2 == NULL) {

         return FALSE;

     }

     while (*p1 != 0 && uprv_tolower(*p1) == uprv_tolower(*p2)) {

         ++p1;

         ++p2;

     }

     return (UBool)(*p1 == *p2);

 }

 /********************************************************************

  * PUBLIC int32_t Support Functions

  ********************************************************************/

 U_CAPI int32_t U_EXPORT2

 uhash_hashLong(const UHashTok key) {

     return key.integer;

 }

 U_CAPI UBool U_EXPORT2

 uhash_compareLong(const UHashTok key1, const UHashTok key2) {

     return (UBool)(key1.integer == key2.integer);

 }