1b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* 2b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru****************************************************************************** 3b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* Copyright (C) 1997-2010, International Business Machines 4b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* Corporation and others. All Rights Reserved. 5b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru****************************************************************************** 6b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* Date Name Description 7b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* 03/22/00 aliu Adapted from original C++ ICU Hashtable. 8b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* 07/06/01 aliu Modified to support int32_t keys on 9b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* platforms with sizeof(void*) < 32. 10b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru****************************************************************************** 11b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru*/ 12b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 13b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "uhash.h" 14b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "unicode/ustring.h" 15b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "cstring.h" 16b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "cmemory.h" 17b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "uassert.h" 18b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 19b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* This hashtable is implemented as a double hash. All elements are 20b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * stored in a single array with no secondary storage for collision 21b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * resolution (no linked list, etc.). When there is a hash collision 22b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * (when two unequal keys have the same hashcode) we resolve this by 23b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * using a secondary hash. The secondary hash is an increment 24b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * computed as a hash function (a different one) of the primary 25b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * hashcode. This increment is added to the initial hash value to 26b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * obtain further slots assigned to the same hash code. For this to 27b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * work, the length of the array and the increment must be relatively 28b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * prime. The easiest way to achieve this is to have the length of 29b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * the array be prime, and the increment be any value from 30b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 1..length-1. 31b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 32b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Hashcodes are 32-bit integers. We make sure all hashcodes are 33b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * non-negative by masking off the top bit. This has two effects: (1) 34b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * modulo arithmetic is simplified. If we allowed negative hashcodes, 35b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * then when we computed hashcode % length, we could get a negative 36b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * result, which we would then have to adjust back into range. It's 37b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * simpler to just make hashcodes non-negative. (2) It makes it easy 38b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * to check for empty vs. occupied slots in the table. We just mark 39b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * empty or deleted slots with a negative hashcode. 40b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 41b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * The central function is _uhash_find(). This function looks for a 42b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * slot matching the given key and hashcode. If one is found, it 43b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * returns a pointer to that slot. If the table is full, and no match 44b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * is found, it returns NULL -- in theory. This would make the code 45b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * more complicated, since all callers of _uhash_find() would then 46b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * have to check for a NULL result. To keep this from happening, we 47b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * don't allow the table to fill. When there is only one 48b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * empty/deleted slot left, uhash_put() will refuse to increase the 49b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * count, and fail. This simplifies the code. In practice, one will 50b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * seldom encounter this using default UHashtables. However, if a 51b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * hashtable is set to a U_FIXED resize policy, or if memory is 52b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * exhausted, then the table may fill. 53b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 54b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * High and low water ratios control rehashing. They establish levels 55b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * of fullness (from 0 to 1) outside of which the data array is 56b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * reallocated and repopulated. Setting the low water ratio to zero 57b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * means the table will never shrink. Setting the high water ratio to 58b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * one means the table will never grow. The ratios should be 59b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * coordinated with the ratio between successive elements of the 60b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PRIMES table, so that when the primeIndex is incremented or 61b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * decremented during rehashing, it brings the ratio of count / length 62b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * back into the desired range (between low and high water ratios). 63b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 64b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 65b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/******************************************************************** 66b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PRIVATE Constants, Macros 67b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 68b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 69b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* This is a list of non-consecutive primes chosen such that 70b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PRIMES[i+1] ~ 2*PRIMES[i]. (Currently, the ratio ranges from 1.81 71b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * to 2.18; the inverse ratio ranges from 0.459 to 0.552.) If this 72b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * ratio is changed, the low and high water ratios should also be 73b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * adjusted to suit. 74b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 75b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * These prime numbers were also chosen so that they are the largest 76b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * prime number while being less than a power of two. 77b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 78b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic const int32_t PRIMES[] = { 79b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 80b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 81b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 82b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1073741789, 2147483647 /*, 4294967291 */ 83b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}; 84b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 85b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define PRIMES_LENGTH (sizeof(PRIMES) / sizeof(PRIMES[0])) 86b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define DEFAULT_PRIME_INDEX 3 87b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 88b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* These ratios are tuned to the PRIMES array such that a resize 89b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * places the table back into the zone of non-resizing. That is, 90b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * after a call to _uhash_rehash(), a subsequent call to 91b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * _uhash_rehash() should do nothing (should not churn). This is only 92b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * a potential problem with U_GROW_AND_SHRINK. 93b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 94b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic const float RESIZE_POLICY_RATIO_TABLE[6] = { 95b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* low, high water ratio */ 96b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 0.0F, 0.5F, /* U_GROW: Grow on demand, do not shrink */ 97b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 0.1F, 0.5F, /* U_GROW_AND_SHRINK: Grow and shrink on demand */ 98b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 0.0F, 1.0F /* U_FIXED: Never change size */ 99b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}; 100b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 101b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* 102b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Invariants for hashcode values: 103b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 104b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * DELETED < 0 105b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * EMPTY < 0 106b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Real hashes >= 0 107b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 108b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Hashcodes may not start out this way, but internally they are 109b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru adjusted so that they are always positive. We assume 32-bit 110b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hashcodes; adjust these constants for other hashcode sizes. 111b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru*/ 112b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define HASH_DELETED ((int32_t) 0x80000000) 113b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define HASH_EMPTY ((int32_t) HASH_DELETED + 1) 114b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 115b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define IS_EMPTY_OR_DELETED(x) ((x) < 0) 116b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 117b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* This macro expects a UHashTok.pointer as its keypointer and 118b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru valuepointer parameters */ 119b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) \ 120b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->keyDeleter != NULL && keypointer != NULL) { \ 121b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru (*hash->keyDeleter)(keypointer); \ 122b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } \ 123b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->valueDeleter != NULL && valuepointer != NULL) { \ 124b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru (*hash->valueDeleter)(valuepointer); \ 125b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 126b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 127b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* 128b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Constants for hinting whether a key or value is an integer 129b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * or a pointer. If a hint bit is zero, then the associated 130b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * token is assumed to be an integer. 131b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 132b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define HINT_KEY_POINTER (1) 133b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define HINT_VALUE_POINTER (2) 134b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 135b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/******************************************************************** 136b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PRIVATE Implementation 137b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 138b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 139b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic UHashTok 140b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_setElement(UHashtable *hash, UHashElement* e, 141b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t hashcode, 142b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok key, UHashTok value, int8_t hint) { 143b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 144b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok oldValue = e->value; 145b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->keyDeleter != NULL && e->key.pointer != NULL && 146b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->key.pointer != key.pointer) { /* Avoid double deletion */ 147b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru (*hash->keyDeleter)(e->key.pointer); 148b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 149b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->valueDeleter != NULL) { 150b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (oldValue.pointer != NULL && 151b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru oldValue.pointer != value.pointer) { /* Avoid double deletion */ 152b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru (*hash->valueDeleter)(oldValue.pointer); 153b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 154b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru oldValue.pointer = NULL; 155b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 156b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Compilers should copy the UHashTok union correctly, but even if 157b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * they do, memory heap tools (e.g. BoundsChecker) can get 158b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * confused when a pointer is cloaked in a union and then copied. 159b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * TO ALLEVIATE THIS, we use hints (based on what API the user is 160b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * calling) to copy pointers when we know the user thinks 161b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * something is a pointer. */ 162b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hint & HINT_KEY_POINTER) { 163b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->key.pointer = key.pointer; 164b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 165b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->key = key; 166b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 167b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hint & HINT_VALUE_POINTER) { 168b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->value.pointer = value.pointer; 169b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 170b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->value = value; 171b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 172b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->hashcode = hashcode; 173b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return oldValue; 174b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 175b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 176b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 177b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Assumes that the given element is not empty or deleted. 178b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 179b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic UHashTok 180b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) { 181b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok empty; 182b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(!IS_EMPTY_OR_DELETED(e->hashcode)); 183b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru --hash->count; 184b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru empty.pointer = NULL; empty.integer = 0; 185b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0); 186b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 187b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 188b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic void 189b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) { 190b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(hash != NULL); 191b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(((int32_t)policy) >= 0); 192b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(((int32_t)policy) < 3); 193b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2]; 194b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1]; 195b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 196b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 197b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 198b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Allocate internal data array of a size determined by the given 199b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * prime index. If the index is out of range it is pinned into range. 200b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * If the allocation fails the status is set to 201b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * U_MEMORY_ALLOCATION_ERROR and all array storage is freed. In 202b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * either case the previous array pointer is overwritten. 203b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 204b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Caller must ensure primeIndex is in range 0..PRIME_LENGTH-1. 205b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 206b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic void 207b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_allocate(UHashtable *hash, 208b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t primeIndex, 209b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 210b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 211b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashElement *p, *limit; 212b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok emptytok; 213b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 214b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_FAILURE(*status)) return; 215b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 216b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(primeIndex >= 0 && primeIndex < PRIMES_LENGTH); 217b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 218b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->primeIndex = primeIndex; 219b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->length = PRIMES[primeIndex]; 220b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 221b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru p = hash->elements = (UHashElement*) 222b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uprv_malloc(sizeof(UHashElement) * hash->length); 223b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 224b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->elements == NULL) { 225b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru *status = U_MEMORY_ALLOCATION_ERROR; 226b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 227b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 228b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 229b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru emptytok.pointer = NULL; /* Only one of these two is needed */ 230b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru emptytok.integer = 0; /* but we don't know which one. */ 231b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 232b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru limit = p + hash->length; 233b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while (p < limit) { 234b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru p->key = emptytok; 235b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru p->value = emptytok; 236b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru p->hashcode = HASH_EMPTY; 237b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++p; 238b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 239b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 240b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->count = 0; 241b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio); 242b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio); 243b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 244b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 245b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic UHashtable* 246b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_init(UHashtable *result, 247b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashFunction *keyHash, 248b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UKeyComparator *keyComp, 249b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UValueComparator *valueComp, 250b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t primeIndex, 251b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) 252b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru{ 253b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_FAILURE(*status)) return NULL; 254b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(keyHash != NULL); 255b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(keyComp != NULL); 256b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 257b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result->keyHasher = keyHash; 258b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result->keyComparator = keyComp; 259b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result->valueComparator = valueComp; 260b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result->keyDeleter = NULL; 261b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result->valueDeleter = NULL; 262b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result->allocated = FALSE; 263b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru _uhash_internalSetResizePolicy(result, U_GROW); 264b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 265b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru _uhash_allocate(result, primeIndex, status); 266b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 267b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_FAILURE(*status)) { 268b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return NULL; 269b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 270b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 271b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 272b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 273b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 274b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic UHashtable* 275b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_create(UHashFunction *keyHash, 276b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UKeyComparator *keyComp, 277b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UValueComparator *valueComp, 278b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t primeIndex, 279b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 280b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashtable *result; 281b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 282b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_FAILURE(*status)) return NULL; 283b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 284b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result = (UHashtable*) uprv_malloc(sizeof(UHashtable)); 285b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (result == NULL) { 286b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru *status = U_MEMORY_ALLOCATION_ERROR; 287b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return NULL; 288b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 289b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 290b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru _uhash_init(result, keyHash, keyComp, valueComp, primeIndex, status); 291b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result->allocated = TRUE; 292b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 293b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_FAILURE(*status)) { 294b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uprv_free(result); 295b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return NULL; 296b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 297b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 298b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 299b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 300b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 301b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 302b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Look for a key in the table, or if no such key exists, the first 303b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * empty slot matching the given hashcode. Keys are compared using 304b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * the keyComparator function. 305b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 306b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * First find the start position, which is the hashcode modulo 307b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * the length. Test it to see if it is: 308b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 309b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * a. identical: First check the hash values for a quick check, 310b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * then compare keys for equality using keyComparator. 311b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * b. deleted 312b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * c. empty 313b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 314b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Stop if it is identical or empty, otherwise continue by adding a 315b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * "jump" value (moduloing by the length again to keep it within 316b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * range) and retesting. For efficiency, there need enough empty 317b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * values so that the searchs stop within a reasonable amount of time. 318b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * This can be changed by changing the high/low water marks. 319b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 320b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * In theory, this function can return NULL, if it is full (no empty 321b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * or deleted slots) and if no matching key is found. In practice, we 322b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * prevent this elsewhere (in uhash_put) by making sure the last slot 323b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * in the table is never filled. 324b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 325b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * The size of the table should be prime for this algorithm to work; 326b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * otherwise we are not guaranteed that the jump value (the secondary 327b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * hash) is relatively prime to the table length. 328b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 329b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic UHashElement* 330b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_find(const UHashtable *hash, UHashTok key, 331b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t hashcode) { 332b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 333b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t firstDeleted = -1; /* assume invalid index */ 334b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t theIndex, startIndex; 335b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t jump = 0; /* lazy evaluate */ 336b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t tableHash; 337b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashElement *elements = hash->elements; 338b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 339b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hashcode &= 0x7FFFFFFF; /* must be positive */ 340b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length; 341b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 342b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru do { 343b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru tableHash = elements[theIndex].hashcode; 344b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (tableHash == hashcode) { /* quick check */ 345b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if ((*hash->keyComparator)(key, elements[theIndex].key)) { 346b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return &(elements[theIndex]); 347b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 348b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else if (!IS_EMPTY_OR_DELETED(tableHash)) { 349b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* We have hit a slot which contains a key-value pair, 350b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * but for which the hash code does not match. Keep 351b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * looking. 352b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 353b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else if (tableHash == HASH_EMPTY) { /* empty, end o' the line */ 354b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru break; 355b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else if (firstDeleted < 0) { /* remember first deleted */ 356b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru firstDeleted = theIndex; 357b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 358b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (jump == 0) { /* lazy compute jump */ 359b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* The jump value must be relatively prime to the table 360b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * length. As long as the length is prime, then any value 361b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 1..length-1 will be relatively prime to it. 362b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 363b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru jump = (hashcode % (hash->length - 1)) + 1; 364b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 365b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru theIndex = (theIndex + jump) % hash->length; 366b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } while (theIndex != startIndex); 367b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 368b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (firstDeleted >= 0) { 369b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru theIndex = firstDeleted; /* reset if had deleted slot */ 370b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else if (tableHash != HASH_EMPTY) { 371b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* We get to this point if the hashtable is full (no empty or 372b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * deleted slots), and we've failed to find a match. THIS 373b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * WILL NEVER HAPPEN as long as uhash_put() makes sure that 374b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * count is always < length. 375b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 376b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(FALSE); 377b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return NULL; /* Never happens if uhash_put() behaves */ 378b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 379b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return &(elements[theIndex]); 380b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 381b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 382b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 383b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Attempt to grow or shrink the data arrays in order to make the 384b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * count fit between the high and low water marks. hash_put() and 385b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * hash_remove() call this method when the count exceeds the high or 386b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * low water marks. This method may do nothing, if memory allocation 387b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * fails, or if the count is already in range, or if the length is 388b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * already at the low or high limit. In any case, upon return the 389b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * arrays will be valid. 390b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 391b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic void 392c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru_uhash_rehash(UHashtable *hash, UErrorCode *status) { 393b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 394b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashElement *old = hash->elements; 395b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t oldLength = hash->length; 396b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t newPrimeIndex = hash->primeIndex; 397b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t i; 398b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 399b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->count > hash->highWaterMark) { 400b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (++newPrimeIndex >= PRIMES_LENGTH) { 401b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 402b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 403b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else if (hash->count < hash->lowWaterMark) { 404b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (--newPrimeIndex < 0) { 405b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 406b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 407b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 408b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 409b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 410b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 411c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru _uhash_allocate(hash, newPrimeIndex, status); 412b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 413c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (U_FAILURE(*status)) { 414b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->elements = old; 415b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->length = oldLength; 416b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 417b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 418b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 419b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i = oldLength - 1; i >= 0; --i) { 420b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!IS_EMPTY_OR_DELETED(old[i].hashcode)) { 421b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode); 422b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(e != NULL); 423b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(e->hashcode == HASH_EMPTY); 424b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->key = old[i].key; 425b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->value = old[i].value; 426b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e->hashcode = old[i].hashcode; 427b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++hash->count; 428b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 429b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 430b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 431b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uprv_free(old); 432b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 433b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 434b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic UHashTok 435b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_remove(UHashtable *hash, 436b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok key) { 437b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* First find the position of the key in the table. If the object 438b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * has not been removed already, remove it. If the user wanted 439b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * keys deleted, then delete it also. We have to put a special 440b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * hashcode in that position that means that something has been 441b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * deleted, since when we do a find, we have to continue PAST any 442b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * deleted values. 443b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 444b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok result; 445b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key)); 446b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(e != NULL); 447c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru result.pointer = NULL; 448c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru result.integer = 0; 449b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!IS_EMPTY_OR_DELETED(e->hashcode)) { 450b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru result = _uhash_internalRemoveElement(hash, e); 451b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->count < hash->lowWaterMark) { 452c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru UErrorCode status = U_ZERO_ERROR; 453c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru _uhash_rehash(hash, &status); 454b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 455b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 456b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 457b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 458b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 459b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic UHashTok 460b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru_uhash_put(UHashtable *hash, 461b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok key, 462b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok value, 463b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int8_t hint, 464b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 465b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 466b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Put finds the position in the table for the new value. If the 467b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * key is already in the table, it is deleted, if there is a 468b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * non-NULL keyDeleter. Then the key, the hash and the value are 469b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * all put at the position in their respective arrays. 470b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 471b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t hashcode; 472b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashElement* e; 473b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok emptytok; 474b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 475b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_FAILURE(*status)) { 476b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru goto err; 477b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 478b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(hash != NULL); 479b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Cannot always check pointer here or iSeries sees NULL every time. */ 480b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if ((hint & HINT_VALUE_POINTER) && value.pointer == NULL) { 481b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Disallow storage of NULL values, since NULL is returned by 482b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * get() to indicate an absent key. Storing NULL == removing. 483b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 484b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_remove(hash, key); 485b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 486b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->count > hash->highWaterMark) { 487c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru _uhash_rehash(hash, status); 488c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (U_FAILURE(*status)) { 489c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru goto err; 490c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru } 491b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 492b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 493b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hashcode = (*hash->keyHasher)(key); 494b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e = _uhash_find(hash, key, hashcode); 495b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(e != NULL); 496b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 497b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (IS_EMPTY_OR_DELETED(e->hashcode)) { 498b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Important: We must never actually fill the table up. If we 499b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * do so, then _uhash_find() will return NULL, and we'll have 500b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * to check for NULL after every call to _uhash_find(). To 501b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * avoid this we make sure there is always at least one empty 502b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * or deleted slot in the table. This only is a problem if we 503b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * are out of memory and rehash isn't working. 504b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 505b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++hash->count; 506b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->count == hash->length) { 507b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Don't allow count to reach length */ 508b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru --hash->count; 509b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru *status = U_MEMORY_ALLOCATION_ERROR; 510b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru goto err; 511b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 512b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 513b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 514b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* We must in all cases handle storage properly. If there was an 515b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * old key, then it must be deleted (if the deleter != NULL). 516b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Make hashcodes stored in table positive. 517b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 518b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value, hint); 519b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 520b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru err: 521b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* If the deleters are non-NULL, this method adopts its key and/or 522b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * value arguments, and we must be sure to delete the key and/or 523b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * value in all cases, even upon failure. 524b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 525b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer); 526b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru emptytok.pointer = NULL; emptytok.integer = 0; 527b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return emptytok; 528b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 529b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 530b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 531b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/******************************************************************** 532b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PUBLIC API 533b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 534b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 535b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UHashtable* U_EXPORT2 536b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_open(UHashFunction *keyHash, 537b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UKeyComparator *keyComp, 538b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UValueComparator *valueComp, 539b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 540b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 541b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_create(keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status); 542b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 543b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 544b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UHashtable* U_EXPORT2 545b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_openSize(UHashFunction *keyHash, 546b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UKeyComparator *keyComp, 547b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UValueComparator *valueComp, 548b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t size, 549b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 550b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 551b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Find the smallest index i for which PRIMES[i] >= size. */ 552b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t i = 0; 553b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) { 554b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++i; 555b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 556b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 557b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_create(keyHash, keyComp, valueComp, i, status); 558b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 559b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 560b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UHashtable* U_EXPORT2 561b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_init(UHashtable *fillinResult, 562b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashFunction *keyHash, 563b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UKeyComparator *keyComp, 564b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UValueComparator *valueComp, 565b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 566b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 567b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_init(fillinResult, keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status); 568b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 569b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 570b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void U_EXPORT2 571b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_close(UHashtable *hash) { 572b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru if (hash == NULL) { 573b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru return; 574b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru } 575b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->elements != NULL) { 576b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) { 577b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t pos=-1; 578b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashElement *e; 579b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) { 580b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer); 581b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 582b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 583b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uprv_free(hash->elements); 584b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->elements = NULL; 585b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 586b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->allocated) { 587b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uprv_free(hash); 588b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 589b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 590b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 591b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UHashFunction *U_EXPORT2 592b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) { 593b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashFunction *result = hash->keyHasher; 594b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->keyHasher = fn; 595b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 596b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 597b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 598b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UKeyComparator *U_EXPORT2 599b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) { 600b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UKeyComparator *result = hash->keyComparator; 601b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->keyComparator = fn; 602b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 603b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 604b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UValueComparator *U_EXPORT2 605b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_setValueComparator(UHashtable *hash, UValueComparator *fn){ 606b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UValueComparator *result = hash->valueComparator; 607b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->valueComparator = fn; 608b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 609b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 610b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 611b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UObjectDeleter *U_EXPORT2 612b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) { 613b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UObjectDeleter *result = hash->keyDeleter; 614b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->keyDeleter = fn; 615b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 616b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 617b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 618b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UObjectDeleter *U_EXPORT2 619b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) { 620b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UObjectDeleter *result = hash->valueDeleter; 621b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->valueDeleter = fn; 622b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 623b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 624b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 625b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void U_EXPORT2 626b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) { 627c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru UErrorCode status = U_ZERO_ERROR; 628b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru _uhash_internalSetResizePolicy(hash, policy); 629b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio); 630b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio); 631c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru _uhash_rehash(hash, &status); 632b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 633b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 634b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 635b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_count(const UHashtable *hash) { 636b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return hash->count; 637b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 638b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 639b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void* U_EXPORT2 640b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_get(const UHashtable *hash, 641b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const void* key) { 642b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 643b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.pointer = (void*) key; 644b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer; 645b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 646b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 647b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void* U_EXPORT2 648b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_iget(const UHashtable *hash, 649b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t key) { 650b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 651b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.integer = key; 652b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer; 653b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 654b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 655b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 656b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_geti(const UHashtable *hash, 657b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const void* key) { 658b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 659b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.pointer = (void*) key; 660b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer; 661b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 662b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 663b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 664b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_igeti(const UHashtable *hash, 665b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t key) { 666b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 667b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.integer = key; 668b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer; 669b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 670b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 671b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void* U_EXPORT2 672b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_put(UHashtable *hash, 673b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* key, 674b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* value, 675b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 676b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder, valueholder; 677b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.pointer = key; 678b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru valueholder.pointer = value; 679b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_put(hash, keyholder, valueholder, 680b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru HINT_KEY_POINTER | HINT_VALUE_POINTER, 681b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru status).pointer; 682b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 683b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 684b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void* U_EXPORT2 685b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_iput(UHashtable *hash, 686b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t key, 687b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* value, 688b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 689b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder, valueholder; 690b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.integer = key; 691b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru valueholder.pointer = value; 692b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_put(hash, keyholder, valueholder, 693b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru HINT_VALUE_POINTER, 694b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru status).pointer; 695b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 696b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 697b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 698b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_puti(UHashtable *hash, 699b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* key, 700b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t value, 701b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 702b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder, valueholder; 703b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.pointer = key; 704b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru valueholder.integer = value; 705b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_put(hash, keyholder, valueholder, 706b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru HINT_KEY_POINTER, 707b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru status).integer; 708b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 709b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 710b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 711b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 712b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_iputi(UHashtable *hash, 713b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t key, 714b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t value, 715b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode *status) { 716b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder, valueholder; 717b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.integer = key; 718b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru valueholder.integer = value; 719b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_put(hash, keyholder, valueholder, 720b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 0, /* neither is a ptr */ 721b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru status).integer; 722b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 723b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 724b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void* U_EXPORT2 725b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_remove(UHashtable *hash, 726b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const void* key) { 727b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 728b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.pointer = (void*) key; 729b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_remove(hash, keyholder).pointer; 730b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 731b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 732b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void* U_EXPORT2 733b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_iremove(UHashtable *hash, 734b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t key) { 735b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 736b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.integer = key; 737b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_remove(hash, keyholder).pointer; 738b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 739b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 740b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 741b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_removei(UHashtable *hash, 742b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const void* key) { 743b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 744b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.pointer = (void*) key; 745b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_remove(hash, keyholder).integer; 746b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 747b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 748b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 749b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_iremovei(UHashtable *hash, 750b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t key) { 751b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 752b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.integer = key; 753b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return _uhash_remove(hash, keyholder).integer; 754b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 755b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 756b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void U_EXPORT2 757b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_removeAll(UHashtable *hash) { 758b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t pos = -1; 759b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashElement *e; 760b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(hash != NULL); 761b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash->count != 0) { 762b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while ((e = uhash_nextElement(hash, &pos)) != NULL) { 763b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uhash_removeElement(hash, e); 764b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 765b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 766b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(hash->count == 0); 767b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 768b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 769b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI const UHashElement* U_EXPORT2 770b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_find(const UHashtable *hash, const void* key) { 771b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok keyholder; 772b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashElement *e; 773b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru keyholder.pointer = (void*) key; 774b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder)); 775b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return IS_EMPTY_OR_DELETED(e->hashcode) ? NULL : e; 776b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 777b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 778b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI const UHashElement* U_EXPORT2 779b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_nextElement(const UHashtable *hash, int32_t *pos) { 780b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Walk through the array until we find an element that is not 781b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * EMPTY and not DELETED. 782b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 783b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t i; 784b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(hash != NULL); 785b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i = *pos + 1; i < hash->length; ++i) { 786b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) { 787b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru *pos = i; 788b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return &(hash->elements[i]); 789b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 790b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 791b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 792b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* No more elements */ 793b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return NULL; 794b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 795b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 796b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void* U_EXPORT2 797b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_removeElement(UHashtable *hash, const UHashElement* e) { 798b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(hash != NULL); 799b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru U_ASSERT(e != NULL); 800b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!IS_EMPTY_OR_DELETED(e->hashcode)) { 80150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho UHashElement *nce = (UHashElement *)e; 80250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return _uhash_internalRemoveElement(hash, nce).pointer; 803b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 804b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return NULL; 805b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 806b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 807b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/******************************************************************** 808b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * UHashTok convenience 809b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 810b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 811b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 812b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Return a UHashTok for an integer. 813b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 814b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/*U_CAPI UHashTok U_EXPORT2 815b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_toki(int32_t i) { 816b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok tok; 817b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru tok.integer = i; 818b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return tok; 819b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}*/ 820b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 821b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 822b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Return a UHashTok for a pointer. 823b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 824b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/*U_CAPI UHashTok U_EXPORT2 825b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_tokp(void* p) { 826b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok tok; 827b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru tok.pointer = p; 828b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return tok; 829b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}*/ 830b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 831b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/******************************************************************** 832b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PUBLIC Key Hash Functions 833b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 834b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 835b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* 836b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Compute the hash by iterating sparsely over about 32 (up to 63) 837b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru characters spaced evenly through the string. For each character, 838b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru multiply the previous hash value by a prime number and add the new 839b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru character in, like a linear congruential random number generator, 840b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru producing a pseudorandom deterministic value well distributed over 841b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru the output range. [LIU] 842b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru*/ 843b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 844b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define STRING_HASH(TYPE, STR, STRLEN, DEREF) \ 845b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t hash = 0; \ 846b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const TYPE *p = (const TYPE*) STR; \ 847b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (p != NULL) { \ 848b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t len = (int32_t)(STRLEN); \ 849b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t inc = ((len - 32) / 32) + 1; \ 850b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const TYPE *limit = p + len; \ 851b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while (p<limit) { \ 852b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash = (hash * 37) + DEREF; \ 853b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru p += inc; \ 854b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } \ 855b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } \ 856b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return hash 857b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 858b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 859b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_hashUChars(const UHashTok key) { 860b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru STRING_HASH(UChar, key.pointer, u_strlen(p), *p); 861b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 862b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 863b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* Used by UnicodeString to compute its hashcode - Not public API. */ 864b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 865b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_hashUCharsN(const UChar *str, int32_t length) { 866b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru STRING_HASH(UChar, str, length, *p); 867b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 868b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 869b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 870b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehouhash_hashCharsN(const char *str, int32_t length) { 871b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho STRING_HASH(char, str, length, *p); 872b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 873b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 874b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_CAPI int32_t U_EXPORT2 875b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_hashChars(const UHashTok key) { 876b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru STRING_HASH(uint8_t, key.pointer, uprv_strlen((char*)p), *p); 877b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 878b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 879b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 880b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_hashIChars(const UHashTok key) { 881b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru STRING_HASH(uint8_t, key.pointer, uprv_strlen((char*)p), uprv_tolower(*p)); 882b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 883b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 884b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UBool U_EXPORT2 885b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_equals(const UHashtable* hash1, const UHashtable* hash2){ 886b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 887b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t count1, count2, pos, i; 888b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 889b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if(hash1==hash2){ 890b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 891b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 892b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 893b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* 894b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Make sure that we are comparing 2 valid hashes of the same type 895b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * with valid comparison functions. 896b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Without valid comparison functions, a binary comparison 897b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * of the hash values will yield random results on machines 898b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * with 64-bit pointers and 32-bit integer hashes. 899b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * A valueComparator is normally optional. 900b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 901b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash1==NULL || hash2==NULL || 902b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash1->keyComparator != hash2->keyComparator || 903b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash1->valueComparator != hash2->valueComparator || 904b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash1->valueComparator == NULL) 905b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru { 906b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* 907b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Normally we would return an error here about incompatible hash tables, 908b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru but we return FALSE instead. 909b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 910b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 911b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 912b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 913b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count1 = uhash_count(hash1); 914b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count2 = uhash_count(hash2); 915b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if(count1!=count2){ 916b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 917b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 918b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 919b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru pos=-1; 920b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for(i=0; i<count1; i++){ 921b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashElement* elem1 = uhash_nextElement(hash1, &pos); 922b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashTok key1 = elem1->key; 923b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashTok val1 = elem1->value; 924b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* here the keys are not compared, instead the key form hash1 is used to fetch 925b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * value from hash2. If the hashes are equal then then both hashes should 926b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * contain equal values for the same key! 927b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 928b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashElement* elem2 = _uhash_find(hash2, key1, hash2->keyHasher(key1)); 929b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashTok val2 = elem2->value; 930b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if(hash1->valueComparator(val1, val2)==FALSE){ 931b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 932b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 933b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 934b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 935b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 936b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 937b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/******************************************************************** 938b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PUBLIC Comparator Functions 939b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 940b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 941b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UBool U_EXPORT2 942b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_compareUChars(const UHashTok key1, const UHashTok key2) { 943b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UChar *p1 = (const UChar*) key1.pointer; 944b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UChar *p2 = (const UChar*) key2.pointer; 945b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (p1 == p2) { 946b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 947b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 948b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (p1 == NULL || p2 == NULL) { 949b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 950b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 951b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while (*p1 != 0 && *p1 == *p2) { 952b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++p1; 953b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++p2; 954b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 955b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return (UBool)(*p1 == *p2); 956b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 957b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 958b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UBool U_EXPORT2 959b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_compareChars(const UHashTok key1, const UHashTok key2) { 960b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const char *p1 = (const char*) key1.pointer; 961b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const char *p2 = (const char*) key2.pointer; 962b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (p1 == p2) { 963b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 964b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 965b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (p1 == NULL || p2 == NULL) { 966b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 967b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 968b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while (*p1 != 0 && *p1 == *p2) { 969b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++p1; 970b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++p2; 971b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 972b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return (UBool)(*p1 == *p2); 973b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 974b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 975b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UBool U_EXPORT2 976b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_compareIChars(const UHashTok key1, const UHashTok key2) { 977b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const char *p1 = (const char*) key1.pointer; 978b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const char *p2 = (const char*) key2.pointer; 979b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (p1 == p2) { 980b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 981b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 982b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (p1 == NULL || p2 == NULL) { 983b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 984b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 985b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while (*p1 != 0 && uprv_tolower(*p1) == uprv_tolower(*p2)) { 986b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++p1; 987b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++p2; 988b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 989b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return (UBool)(*p1 == *p2); 990b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 991b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 992b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/******************************************************************** 993b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PUBLIC int32_t Support Functions 994b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 995b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 996b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI int32_t U_EXPORT2 997b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_hashLong(const UHashTok key) { 998b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return key.integer; 999b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 1000b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1001b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI UBool U_EXPORT2 1002b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_compareLong(const UHashTok key1, const UHashTok key2) { 1003b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return (UBool)(key1.integer == key2.integer); 1004b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 1005b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1006b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/******************************************************************** 1007b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * PUBLIC Deleter Functions 1008b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 1009b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1010b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_CAPI void U_EXPORT2 1011b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruuhash_freeBlock(void *obj) { 1012b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uprv_free(obj); 1013b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 1014b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1015