diff options
Diffstat (limited to 'deps/node/deps/icu-small/source/common/uhash.cpp')
| -rw-r--r-- | deps/node/deps/icu-small/source/common/uhash.cpp | 991 |
1 files changed, 0 insertions, 991 deletions
diff --git a/deps/node/deps/icu-small/source/common/uhash.cpp b/deps/node/deps/icu-small/source/common/uhash.cpp deleted file mode 100644 index 239997d0..00000000 --- a/deps/node/deps/icu-small/source/common/uhash.cpp +++ /dev/null @@ -1,991 +0,0 @@ -// © 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) \ - 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 = 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. - */ - 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 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); -} |