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