diff options
Diffstat (limited to 'intl/icu/source/common/uhash.c')
| -rw-r--r-- | intl/icu/source/common/uhash.c | 975 |
1 files changed, 975 insertions, 0 deletions
diff --git a/intl/icu/source/common/uhash.c b/intl/icu/source/common/uhash.c new file mode 100644 index 000000000..282f89fe2 --- /dev/null +++ b/intl/icu/source/common/uhash.c @@ -0,0 +1,975 @@ +// Copyright (C) 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[] = { + 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 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=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 : 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=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); +} |