Restoring authorship annotation for <mcheshkov@yandex-team.ru>. Commit 1 of 2.

1 files changed, 991 insertions, 991 deletions

diff --git a/contrib/libs/icu/common/uhash.cpp b/contrib/libs/icu/common/uhash.cpp
index 86311ceb0b..16c4f2dc21 100644
--- a/contrib/libs/icu/common/uhash.cpp
+++ b/contrib/libs/icu/common/uhash.cpp
@@ -1,991 +1,991 @@
-// © 2016 and later: Unicode, Inc. and others.
-// License & terms of use: http://www.unicode.org/copyright.html
-/*
-******************************************************************************
-*   Copyright (C) 1997-2016, 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[] = {
-    7, 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 UPRV_LENGTHOF(PRIMES)
-#define DEFAULT_PRIME_INDEX 4
-
-/* 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) UPRV_BLOCK_MACRO_BEGIN { \
-    if (hash->keyDeleter != NULL && keypointer != NULL) { \
-        (*hash->keyDeleter)(keypointer); \
-    } \
-    if (hash->valueDeleter != NULL && valuepointer != NULL) { \
-        (*hash->valueDeleter)(valuepointer); \
-    } \
-} UPRV_BLOCK_MACRO_END
-
-/*
- * 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 = static_cast<int8_t>(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.
-         */
-        UPRV_UNREACHABLE;
-    }
-    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 UHashtable* U_EXPORT2
-uhash_initSize(UHashtable *fillinResult,
-               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_init(fillinResult, keyHash, keyComp, valueComp, i, 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=UHASH_FIRST;
-            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 = UHASH_FIRST;
-    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 : static_cast<int32_t>(ustr_hashCharsN(s, static_cast<int32_t>(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, static_cast<int32_t>(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=UHASH_FIRST;
-    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);
-}
+// © 2016 and later: Unicode, Inc. and others. 
+// License & terms of use: http://www.unicode.org/copyright.html 
+/* 
+****************************************************************************** 
+*   Copyright (C) 1997-2016, 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[] = { 
+    7, 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 UPRV_LENGTHOF(PRIMES) 
+#define DEFAULT_PRIME_INDEX 4 
+ 
+/* 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) UPRV_BLOCK_MACRO_BEGIN { \ 
+    if (hash->keyDeleter != NULL && keypointer != NULL) { \ 
+        (*hash->keyDeleter)(keypointer); \ 
+    } \ 
+    if (hash->valueDeleter != NULL && valuepointer != NULL) { \ 
+        (*hash->valueDeleter)(valuepointer); \ 
+    } \ 
+} UPRV_BLOCK_MACRO_END 
+ 
+/* 
+ * 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 = static_cast<int8_t>(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. 
+         */ 
+        UPRV_UNREACHABLE; 
+    } 
+    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 UHashtable* U_EXPORT2 
+uhash_initSize(UHashtable *fillinResult, 
+               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_init(fillinResult, keyHash, keyComp, valueComp, i, 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=UHASH_FIRST; 
+            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 = UHASH_FIRST; 
+    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 : static_cast<int32_t>(ustr_hashCharsN(s, static_cast<int32_t>(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, static_cast<int32_t>(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=UHASH_FIRST; 
+    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); 
+}