--- /dev/null
+// © 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 = 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 : 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);
+}
projects / apple / icu.git / blobdiff