16f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 26f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org****************************************************************************** 36f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Copyright (C) 1997-2011, International Business Machines 46f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Corporation and others. All Rights Reserved. 56f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org****************************************************************************** 66f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Date Name Description 76f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* 03/22/00 aliu Adapted from original C++ ICU Hashtable. 86f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* 07/06/01 aliu Modified to support int32_t keys on 96f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* platforms with sizeof(void*) < 32. 106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org****************************************************************************** 116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org*/ 126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "uhash.h" 146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/ustring.h" 156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "cstring.h" 166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "cmemory.h" 176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "uassert.h" 186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "ustr_imp.h" 196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* This hashtable is implemented as a double hash. All elements are 216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * stored in a single array with no secondary storage for collision 226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * resolution (no linked list, etc.). When there is a hash collision 236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * (when two unequal keys have the same hashcode) we resolve this by 246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * using a secondary hash. The secondary hash is an increment 256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * computed as a hash function (a different one) of the primary 266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * hashcode. This increment is added to the initial hash value to 276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * obtain further slots assigned to the same hash code. For this to 286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * work, the length of the array and the increment must be relatively 296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * prime. The easiest way to achieve this is to have the length of 306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * the array be prime, and the increment be any value from 316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 1..length-1. 326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Hashcodes are 32-bit integers. We make sure all hashcodes are 346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * non-negative by masking off the top bit. This has two effects: (1) 356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * modulo arithmetic is simplified. If we allowed negative hashcodes, 366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * then when we computed hashcode % length, we could get a negative 376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * result, which we would then have to adjust back into range. It's 386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * simpler to just make hashcodes non-negative. (2) It makes it easy 396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * to check for empty vs. occupied slots in the table. We just mark 406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * empty or deleted slots with a negative hashcode. 416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * The central function is _uhash_find(). This function looks for a 436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * slot matching the given key and hashcode. If one is found, it 446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * returns a pointer to that slot. If the table is full, and no match 456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * is found, it returns NULL -- in theory. This would make the code 466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * more complicated, since all callers of _uhash_find() would then 476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * have to check for a NULL result. To keep this from happening, we 486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * don't allow the table to fill. When there is only one 496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * empty/deleted slot left, uhash_put() will refuse to increase the 506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * count, and fail. This simplifies the code. In practice, one will 516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * seldom encounter this using default UHashtables. However, if a 526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * hashtable is set to a U_FIXED resize policy, or if memory is 536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * exhausted, then the table may fill. 546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * High and low water ratios control rehashing. They establish levels 566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * of fullness (from 0 to 1) outside of which the data array is 576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * reallocated and repopulated. Setting the low water ratio to zero 586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * means the table will never shrink. Setting the high water ratio to 596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * one means the table will never grow. The ratios should be 606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * coordinated with the ratio between successive elements of the 616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * PRIMES table, so that when the primeIndex is incremented or 626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * decremented during rehashing, it brings the ratio of count / length 636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * back into the desired range (between low and high water ratios). 646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/******************************************************************** 676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * PRIVATE Constants, Macros 686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ********************************************************************/ 696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* This is a list of non-consecutive primes chosen such that 716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * PRIMES[i+1] ~ 2*PRIMES[i]. (Currently, the ratio ranges from 1.81 726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * to 2.18; the inverse ratio ranges from 0.459 to 0.552.) If this 736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * ratio is changed, the low and high water ratios should also be 746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * adjusted to suit. 756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * These prime numbers were also chosen so that they are the largest 776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * prime number while being less than a power of two. 786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic const int32_t PRIMES[] = { 806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1073741789, 2147483647 /*, 4294967291 */ 846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org}; 856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#define PRIMES_LENGTH (sizeof(PRIMES) / sizeof(PRIMES[0])) 876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#define DEFAULT_PRIME_INDEX 3 886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* These ratios are tuned to the PRIMES array such that a resize 906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * places the table back into the zone of non-resizing. That is, 916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * after a call to _uhash_rehash(), a subsequent call to 926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * _uhash_rehash() should do nothing (should not churn). This is only 936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * a potential problem with U_GROW_AND_SHRINK. 946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic const float RESIZE_POLICY_RATIO_TABLE[6] = { 966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* low, high water ratio */ 976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 0.0F, 0.5F, /* U_GROW: Grow on demand, do not shrink */ 986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 0.1F, 0.5F, /* U_GROW_AND_SHRINK: Grow and shrink on demand */ 996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 0.0F, 1.0F /* U_FIXED: Never change size */ 1006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org}; 1016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 1036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Invariants for hashcode values: 1046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * DELETED < 0 1066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * EMPTY < 0 1076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Real hashes >= 0 1086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Hashcodes may not start out this way, but internally they are 1106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org adjusted so that they are always positive. We assume 32-bit 1116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hashcodes; adjust these constants for other hashcode sizes. 1126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org*/ 1136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#define HASH_DELETED ((int32_t) 0x80000000) 1146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#define HASH_EMPTY ((int32_t) HASH_DELETED + 1) 1156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#define IS_EMPTY_OR_DELETED(x) ((x) < 0) 1176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* This macro expects a UHashTok.pointer as its keypointer and 1196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valuepointer parameters */ 1206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) \ 1216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->keyDeleter != NULL && keypointer != NULL) { \ 1226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org (*hash->keyDeleter)(keypointer); \ 1236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } \ 1246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->valueDeleter != NULL && valuepointer != NULL) { \ 1256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org (*hash->valueDeleter)(valuepointer); \ 1266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 1296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Constants for hinting whether a key or value is an integer 1306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * or a pointer. If a hint bit is zero, then the associated 1316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * token is assumed to be an integer. 1326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 1336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#define HINT_KEY_POINTER (1) 1346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#define HINT_VALUE_POINTER (2) 1356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/******************************************************************** 1376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * PRIVATE Implementation 1386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ********************************************************************/ 1396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic UHashTok 1416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_setElement(UHashtable *hash, UHashElement* e, 1426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t hashcode, 1436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok key, UHashTok value, int8_t hint) { 1446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok oldValue = e->value; 1466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->keyDeleter != NULL && e->key.pointer != NULL && 1476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->key.pointer != key.pointer) { /* Avoid double deletion */ 1486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org (*hash->keyDeleter)(e->key.pointer); 1496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->valueDeleter != NULL) { 1516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (oldValue.pointer != NULL && 1526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org oldValue.pointer != value.pointer) { /* Avoid double deletion */ 1536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org (*hash->valueDeleter)(oldValue.pointer); 1546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org oldValue.pointer = NULL; 1566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Compilers should copy the UHashTok union correctly, but even if 1586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * they do, memory heap tools (e.g. BoundsChecker) can get 1596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * confused when a pointer is cloaked in a union and then copied. 1606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * TO ALLEVIATE THIS, we use hints (based on what API the user is 1616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * calling) to copy pointers when we know the user thinks 1626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * something is a pointer. */ 1636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hint & HINT_KEY_POINTER) { 1646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->key.pointer = key.pointer; 1656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->key = key; 1676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hint & HINT_VALUE_POINTER) { 1696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->value.pointer = value.pointer; 1706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->value = value; 1726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->hashcode = hashcode; 1746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return oldValue; 1756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/** 1786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Assumes that the given element is not empty or deleted. 1796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 1806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic UHashTok 1816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) { 1826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok empty; 1836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(!IS_EMPTY_OR_DELETED(e->hashcode)); 1846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --hash->count; 1856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org empty.pointer = NULL; empty.integer = 0; 1866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0); 1876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic void 1906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) { 1916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(hash != NULL); 1926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(((int32_t)policy) >= 0); 1936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(((int32_t)policy) < 3); 1946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2]; 1956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1]; 1966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/** 1996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Allocate internal data array of a size determined by the given 2006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * prime index. If the index is out of range it is pinned into range. 2016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * If the allocation fails the status is set to 2026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * U_MEMORY_ALLOCATION_ERROR and all array storage is freed. In 2036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * either case the previous array pointer is overwritten. 2046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 2056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Caller must ensure primeIndex is in range 0..PRIME_LENGTH-1. 2066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 2076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic void 2086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_allocate(UHashtable *hash, 2096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t primeIndex, 2106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 2116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashElement *p, *limit; 2136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok emptytok; 2146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (U_FAILURE(*status)) return; 2166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(primeIndex >= 0 && primeIndex < PRIMES_LENGTH); 2186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->primeIndex = primeIndex; 2206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->length = PRIMES[primeIndex]; 2216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org p = hash->elements = (UHashElement*) 2236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_malloc(sizeof(UHashElement) * hash->length); 2246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->elements == NULL) { 2266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *status = U_MEMORY_ALLOCATION_ERROR; 2276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 2286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org emptytok.pointer = NULL; /* Only one of these two is needed */ 2316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org emptytok.integer = 0; /* but we don't know which one. */ 2326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org limit = p + hash->length; 2346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while (p < limit) { 2356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org p->key = emptytok; 2366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org p->value = emptytok; 2376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org p->hashcode = HASH_EMPTY; 2386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++p; 2396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->count = 0; 2426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio); 2436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio); 2446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 2456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic UHashtable* 2476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_init(UHashtable *result, 2486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashFunction *keyHash, 2496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UKeyComparator *keyComp, 2506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UValueComparator *valueComp, 2516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t primeIndex, 2526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) 2536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 2546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (U_FAILURE(*status)) return NULL; 2556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(keyHash != NULL); 2566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(keyComp != NULL); 2576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result->keyHasher = keyHash; 2596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result->keyComparator = keyComp; 2606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result->valueComparator = valueComp; 2616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result->keyDeleter = NULL; 2626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result->valueDeleter = NULL; 2636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result->allocated = FALSE; 2646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org _uhash_internalSetResizePolicy(result, U_GROW); 2656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org _uhash_allocate(result, primeIndex, status); 2676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (U_FAILURE(*status)) { 2696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 2706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 2736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 2746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic UHashtable* 2766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_create(UHashFunction *keyHash, 2776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UKeyComparator *keyComp, 2786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UValueComparator *valueComp, 2796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t primeIndex, 2806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 2816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashtable *result; 2826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (U_FAILURE(*status)) return NULL; 2846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result = (UHashtable*) uprv_malloc(sizeof(UHashtable)); 2866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (result == NULL) { 2876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *status = U_MEMORY_ALLOCATION_ERROR; 2886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 2896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org _uhash_init(result, keyHash, keyComp, valueComp, primeIndex, status); 2926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result->allocated = TRUE; 2936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (U_FAILURE(*status)) { 2956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_free(result); 2966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 2976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 3006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/** 3036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Look for a key in the table, or if no such key exists, the first 3046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * empty slot matching the given hashcode. Keys are compared using 3056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * the keyComparator function. 3066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 3076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * First find the start position, which is the hashcode modulo 3086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * the length. Test it to see if it is: 3096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 3106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * a. identical: First check the hash values for a quick check, 3116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * then compare keys for equality using keyComparator. 3126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * b. deleted 3136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * c. empty 3146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 3156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Stop if it is identical or empty, otherwise continue by adding a 3166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * "jump" value (moduloing by the length again to keep it within 3176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * range) and retesting. For efficiency, there need enough empty 3186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * values so that the searchs stop within a reasonable amount of time. 3196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * This can be changed by changing the high/low water marks. 3206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 3216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * In theory, this function can return NULL, if it is full (no empty 3226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * or deleted slots) and if no matching key is found. In practice, we 3236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * prevent this elsewhere (in uhash_put) by making sure the last slot 3246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * in the table is never filled. 3256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 3266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * The size of the table should be prime for this algorithm to work; 3276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * otherwise we are not guaranteed that the jump value (the secondary 3286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * hash) is relatively prime to the table length. 3296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 3306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic UHashElement* 3316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_find(const UHashtable *hash, UHashTok key, 3326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t hashcode) { 3336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t firstDeleted = -1; /* assume invalid index */ 3356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t theIndex, startIndex; 3366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t jump = 0; /* lazy evaluate */ 3376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t tableHash; 3386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashElement *elements = hash->elements; 3396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hashcode &= 0x7FFFFFFF; /* must be positive */ 3416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length; 3426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 3446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org tableHash = elements[theIndex].hashcode; 3456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (tableHash == hashcode) { /* quick check */ 3466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if ((*hash->keyComparator)(key, elements[theIndex].key)) { 3476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return &(elements[theIndex]); 3486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if (!IS_EMPTY_OR_DELETED(tableHash)) { 3506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* We have hit a slot which contains a key-value pair, 3516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * but for which the hash code does not match. Keep 3526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * looking. 3536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 3546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if (tableHash == HASH_EMPTY) { /* empty, end o' the line */ 3556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 3566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if (firstDeleted < 0) { /* remember first deleted */ 3576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org firstDeleted = theIndex; 3586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (jump == 0) { /* lazy compute jump */ 3606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* The jump value must be relatively prime to the table 3616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * length. As long as the length is prime, then any value 3626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 1..length-1 will be relatively prime to it. 3636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 3646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org jump = (hashcode % (hash->length - 1)) + 1; 3656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org theIndex = (theIndex + jump) % hash->length; 3676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while (theIndex != startIndex); 3686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (firstDeleted >= 0) { 3706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org theIndex = firstDeleted; /* reset if had deleted slot */ 3716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if (tableHash != HASH_EMPTY) { 3726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* We get to this point if the hashtable is full (no empty or 3736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * deleted slots), and we've failed to find a match. THIS 3746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * WILL NEVER HAPPEN as long as uhash_put() makes sure that 3756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * count is always < length. 3766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 3776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(FALSE); 3786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; /* Never happens if uhash_put() behaves */ 3796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return &(elements[theIndex]); 3816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/** 3846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Attempt to grow or shrink the data arrays in order to make the 3856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * count fit between the high and low water marks. hash_put() and 3866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * hash_remove() call this method when the count exceeds the high or 3876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * low water marks. This method may do nothing, if memory allocation 3886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * fails, or if the count is already in range, or if the length is 3896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * already at the low or high limit. In any case, upon return the 3906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * arrays will be valid. 3916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 3926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic void 3936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_rehash(UHashtable *hash, UErrorCode *status) { 3946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashElement *old = hash->elements; 3966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t oldLength = hash->length; 3976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t newPrimeIndex = hash->primeIndex; 3986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i; 3996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->count > hash->highWaterMark) { 4016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (++newPrimeIndex >= PRIMES_LENGTH) { 4026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 4036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if (hash->count < hash->lowWaterMark) { 4056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (--newPrimeIndex < 0) { 4066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 4076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 4096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 4106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org _uhash_allocate(hash, newPrimeIndex, status); 4136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (U_FAILURE(*status)) { 4156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->elements = old; 4166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->length = oldLength; 4176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 4186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for (i = oldLength - 1; i >= 0; --i) { 4216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!IS_EMPTY_OR_DELETED(old[i].hashcode)) { 4226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode); 4236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(e != NULL); 4246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(e->hashcode == HASH_EMPTY); 4256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->key = old[i].key; 4266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->value = old[i].value; 4276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e->hashcode = old[i].hashcode; 4286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++hash->count; 4296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_free(old); 4336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic UHashTok 4366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_remove(UHashtable *hash, 4376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok key) { 4386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* First find the position of the key in the table. If the object 4396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * has not been removed already, remove it. If the user wanted 4406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * keys deleted, then delete it also. We have to put a special 4416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * hashcode in that position that means that something has been 4426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * deleted, since when we do a find, we have to continue PAST any 4436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * deleted values. 4446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 4456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok result; 4466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key)); 4476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(e != NULL); 4486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result.pointer = NULL; 4496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result.integer = 0; 4506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!IS_EMPTY_OR_DELETED(e->hashcode)) { 4516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result = _uhash_internalRemoveElement(hash, e); 4526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->count < hash->lowWaterMark) { 4536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode status = U_ZERO_ERROR; 4546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org _uhash_rehash(hash, &status); 4556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 4586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic UHashTok 4616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org_uhash_put(UHashtable *hash, 4626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok key, 4636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok value, 4646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int8_t hint, 4656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 4666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Put finds the position in the table for the new value. If the 4686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * key is already in the table, it is deleted, if there is a 4696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * non-NULL keyDeleter. Then the key, the hash and the value are 4706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * all put at the position in their respective arrays. 4716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 4726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t hashcode; 4736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashElement* e; 4746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok emptytok; 4756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (U_FAILURE(*status)) { 4776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org goto err; 4786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(hash != NULL); 4806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Cannot always check pointer here or iSeries sees NULL every time. */ 4816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if ((hint & HINT_VALUE_POINTER) && value.pointer == NULL) { 4826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Disallow storage of NULL values, since NULL is returned by 4836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * get() to indicate an absent key. Storing NULL == removing. 4846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 4856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_remove(hash, key); 4866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->count > hash->highWaterMark) { 4886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org _uhash_rehash(hash, status); 4896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (U_FAILURE(*status)) { 4906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org goto err; 4916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hashcode = (*hash->keyHasher)(key); 4956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e = _uhash_find(hash, key, hashcode); 4966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(e != NULL); 4976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (IS_EMPTY_OR_DELETED(e->hashcode)) { 4996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Important: We must never actually fill the table up. If we 5006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * do so, then _uhash_find() will return NULL, and we'll have 5016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * to check for NULL after every call to _uhash_find(). To 5026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * avoid this we make sure there is always at least one empty 5036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * or deleted slot in the table. This only is a problem if we 5046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * are out of memory and rehash isn't working. 5056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 5066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++hash->count; 5076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->count == hash->length) { 5086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Don't allow count to reach length */ 5096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --hash->count; 5106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *status = U_MEMORY_ALLOCATION_ERROR; 5116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org goto err; 5126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* We must in all cases handle storage properly. If there was an 5166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * old key, then it must be deleted (if the deleter != NULL). 5176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Make hashcodes stored in table positive. 5186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 5196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value, hint); 5206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org err: 5226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* If the deleters are non-NULL, this method adopts its key and/or 5236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * value arguments, and we must be sure to delete the key and/or 5246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * value in all cases, even upon failure. 5256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 5266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer); 5276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org emptytok.pointer = NULL; emptytok.integer = 0; 5286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return emptytok; 5296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/******************************************************************** 5336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * PUBLIC API 5346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ********************************************************************/ 5356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UHashtable* U_EXPORT2 5376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_open(UHashFunction *keyHash, 5386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UKeyComparator *keyComp, 5396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UValueComparator *valueComp, 5406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 5416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_create(keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status); 5436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UHashtable* U_EXPORT2 5466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_openSize(UHashFunction *keyHash, 5476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UKeyComparator *keyComp, 5486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UValueComparator *valueComp, 5496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t size, 5506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 5516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Find the smallest index i for which PRIMES[i] >= size. */ 5536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i = 0; 5546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) { 5556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++i; 5566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_create(keyHash, keyComp, valueComp, i, status); 5596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UHashtable* U_EXPORT2 5626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_init(UHashtable *fillinResult, 5636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashFunction *keyHash, 5646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UKeyComparator *keyComp, 5656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UValueComparator *valueComp, 5666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 5676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_init(fillinResult, keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status); 5696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void U_EXPORT2 5726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_close(UHashtable *hash) { 5736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash == NULL) { 5746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 5756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->elements != NULL) { 5776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) { 5786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t pos=-1; 5796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashElement *e; 5806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) { 5816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer); 5826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_free(hash->elements); 5856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->elements = NULL; 5866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->allocated) { 5886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_free(hash); 5896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UHashFunction *U_EXPORT2 5936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) { 5946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashFunction *result = hash->keyHasher; 5956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->keyHasher = fn; 5966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 5976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UKeyComparator *U_EXPORT2 6006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) { 6016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UKeyComparator *result = hash->keyComparator; 6026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->keyComparator = fn; 6036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 6046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UValueComparator *U_EXPORT2 6066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_setValueComparator(UHashtable *hash, UValueComparator *fn){ 6076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UValueComparator *result = hash->valueComparator; 6086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->valueComparator = fn; 6096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 6106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UObjectDeleter *U_EXPORT2 6136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) { 6146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UObjectDeleter *result = hash->keyDeleter; 6156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->keyDeleter = fn; 6166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 6176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UObjectDeleter *U_EXPORT2 6206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) { 6216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UObjectDeleter *result = hash->valueDeleter; 6226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->valueDeleter = fn; 6236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 6246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void U_EXPORT2 6276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) { 6286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode status = U_ZERO_ERROR; 6296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org _uhash_internalSetResizePolicy(hash, policy); 6306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio); 6316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio); 6326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org _uhash_rehash(hash, &status); 6336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 6366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_count(const UHashtable *hash) { 6376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return hash->count; 6386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void* U_EXPORT2 6416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_get(const UHashtable *hash, 6426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const void* key) { 6436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 6446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.pointer = (void*) key; 6456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer; 6466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void* U_EXPORT2 6496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_iget(const UHashtable *hash, 6506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t key) { 6516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 6526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.integer = key; 6536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer; 6546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 6576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_geti(const UHashtable *hash, 6586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const void* key) { 6596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 6606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.pointer = (void*) key; 6616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer; 6626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 6656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_igeti(const UHashtable *hash, 6666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t key) { 6676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 6686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.integer = key; 6696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer; 6706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void* U_EXPORT2 6736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_put(UHashtable *hash, 6746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void* key, 6756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void* value, 6766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 6776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder, valueholder; 6786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.pointer = key; 6796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueholder.pointer = value; 6806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_put(hash, keyholder, valueholder, 6816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org HINT_KEY_POINTER | HINT_VALUE_POINTER, 6826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org status).pointer; 6836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void* U_EXPORT2 6866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_iput(UHashtable *hash, 6876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t key, 6886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void* value, 6896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 6906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder, valueholder; 6916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.integer = key; 6926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueholder.pointer = value; 6936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_put(hash, keyholder, valueholder, 6946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org HINT_VALUE_POINTER, 6956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org status).pointer; 6966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 6996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_puti(UHashtable *hash, 7006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void* key, 7016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value, 7026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 7036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder, valueholder; 7046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.pointer = key; 7056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueholder.integer = value; 7066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_put(hash, keyholder, valueholder, 7076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org HINT_KEY_POINTER, 7086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org status).integer; 7096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 7136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_iputi(UHashtable *hash, 7146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t key, 7156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value, 7166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode *status) { 7176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder, valueholder; 7186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.integer = key; 7196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueholder.integer = value; 7206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_put(hash, keyholder, valueholder, 7216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 0, /* neither is a ptr */ 7226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org status).integer; 7236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void* U_EXPORT2 7266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_remove(UHashtable *hash, 7276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const void* key) { 7286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 7296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.pointer = (void*) key; 7306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_remove(hash, keyholder).pointer; 7316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void* U_EXPORT2 7346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_iremove(UHashtable *hash, 7356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t key) { 7366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 7376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.integer = key; 7386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_remove(hash, keyholder).pointer; 7396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 7426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_removei(UHashtable *hash, 7436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const void* key) { 7446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 7456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.pointer = (void*) key; 7466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_remove(hash, keyholder).integer; 7476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 7506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_iremovei(UHashtable *hash, 7516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t key) { 7526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 7536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.integer = key; 7546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_remove(hash, keyholder).integer; 7556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void U_EXPORT2 7586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_removeAll(UHashtable *hash) { 7596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t pos = -1; 7606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashElement *e; 7616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(hash != NULL); 7626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash->count != 0) { 7636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while ((e = uhash_nextElement(hash, &pos)) != NULL) { 7646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uhash_removeElement(hash, e); 7656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 7666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 7676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(hash->count == 0); 7686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI const UHashElement* U_EXPORT2 7716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_find(const UHashtable *hash, const void* key) { 7726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok keyholder; 7736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashElement *e; 7746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org keyholder.pointer = (void*) key; 7756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder)); 7766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return IS_EMPTY_OR_DELETED(e->hashcode) ? NULL : e; 7776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI const UHashElement* U_EXPORT2 7806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_nextElement(const UHashtable *hash, int32_t *pos) { 7816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Walk through the array until we find an element that is not 7826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * EMPTY and not DELETED. 7836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 7846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i; 7856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(hash != NULL); 7866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for (i = *pos + 1; i < hash->length; ++i) { 7876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) { 7886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *pos = i; 7896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return &(hash->elements[i]); 7906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 7916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 7926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* No more elements */ 7946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 7956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 7966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 7976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void* U_EXPORT2 7986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_removeElement(UHashtable *hash, const UHashElement* e) { 7996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(hash != NULL); 8006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(e != NULL); 8016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!IS_EMPTY_OR_DELETED(e->hashcode)) { 8026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashElement *nce = (UHashElement *)e; 8036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return _uhash_internalRemoveElement(hash, nce).pointer; 8046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 8056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 8066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 8076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/******************************************************************** 8096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * UHashTok convenience 8106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ********************************************************************/ 8116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/** 8136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Return a UHashTok for an integer. 8146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 8156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/*U_CAPI UHashTok U_EXPORT2 8166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_toki(int32_t i) { 8176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok tok; 8186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org tok.integer = i; 8196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return tok; 8206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org}*/ 8216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/** 8236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Return a UHashTok for a pointer. 8246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 8256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/*U_CAPI UHashTok U_EXPORT2 8266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_tokp(void* p) { 8276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UHashTok tok; 8286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org tok.pointer = p; 8296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return tok; 8306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org}*/ 8316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/******************************************************************** 8336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * PUBLIC Key Hash Functions 8346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ********************************************************************/ 8356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 8376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_hashUChars(const UHashTok key) { 8386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UChar *s = (const UChar *)key.pointer; 8396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return s == NULL ? 0 : ustr_hashUCharsN(s, u_strlen(s)); 8406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 8416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 8436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_hashChars(const UHashTok key) { 8446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const char *s = (const char *)key.pointer; 8456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return s == NULL ? 0 : ustr_hashCharsN(s, uprv_strlen(s)); 8466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 8476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 8496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_hashIChars(const UHashTok key) { 8506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const char *s = (const char *)key.pointer; 8516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return s == NULL ? 0 : ustr_hashICharsN(s, uprv_strlen(s)); 8526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 8536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UBool U_EXPORT2 8556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_equals(const UHashtable* hash1, const UHashtable* hash2){ 8566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t count1, count2, pos, i; 8576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(hash1==hash2){ 8596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 8606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 8616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* 8636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Make sure that we are comparing 2 valid hashes of the same type 8646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * with valid comparison functions. 8656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Without valid comparison functions, a binary comparison 8666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * of the hash values will yield random results on machines 8676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * with 64-bit pointers and 32-bit integer hashes. 8686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * A valueComparator is normally optional. 8696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 8706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (hash1==NULL || hash2==NULL || 8716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash1->keyComparator != hash2->keyComparator || 8726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash1->valueComparator != hash2->valueComparator || 8736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hash1->valueComparator == NULL) 8746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org { 8756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* 8766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Normally we would return an error here about incompatible hash tables, 8776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org but we return FALSE instead. 8786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 8796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 8806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 8816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org count1 = uhash_count(hash1); 8836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org count2 = uhash_count(hash2); 8846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(count1!=count2){ 8856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 8866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 8876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 8886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=-1; 8896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(i=0; i<count1; i++){ 8906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashElement* elem1 = uhash_nextElement(hash1, &pos); 8916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashTok key1 = elem1->key; 8926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashTok val1 = elem1->value; 8936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* here the keys are not compared, instead the key form hash1 is used to fetch 8946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * value from hash2. If the hashes are equal then then both hashes should 8956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * contain equal values for the same key! 8966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 8976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashElement* elem2 = _uhash_find(hash2, key1, hash2->keyHasher(key1)); 8986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashTok val2 = elem2->value; 8996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(hash1->valueComparator(val1, val2)==FALSE){ 9006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 9016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 9046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 9056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 9066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/******************************************************************** 9076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * PUBLIC Comparator Functions 9086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ********************************************************************/ 9096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 9106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UBool U_EXPORT2 9116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_compareUChars(const UHashTok key1, const UHashTok key2) { 9126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UChar *p1 = (const UChar*) key1.pointer; 9136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UChar *p2 = (const UChar*) key2.pointer; 9146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (p1 == p2) { 9156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 9166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (p1 == NULL || p2 == NULL) { 9186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 9196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while (*p1 != 0 && *p1 == *p2) { 9216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++p1; 9226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++p2; 9236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (UBool)(*p1 == *p2); 9256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 9266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 9276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UBool U_EXPORT2 9286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_compareChars(const UHashTok key1, const UHashTok key2) { 9296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const char *p1 = (const char*) key1.pointer; 9306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const char *p2 = (const char*) key2.pointer; 9316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (p1 == p2) { 9326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 9336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (p1 == NULL || p2 == NULL) { 9356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 9366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while (*p1 != 0 && *p1 == *p2) { 9386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++p1; 9396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++p2; 9406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (UBool)(*p1 == *p2); 9426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 9436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 9446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UBool U_EXPORT2 9456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_compareIChars(const UHashTok key1, const UHashTok key2) { 9466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const char *p1 = (const char*) key1.pointer; 9476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const char *p2 = (const char*) key2.pointer; 9486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (p1 == p2) { 9496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 9506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (p1 == NULL || p2 == NULL) { 9526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 9536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while (*p1 != 0 && uprv_tolower(*p1) == uprv_tolower(*p2)) { 9556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++p1; 9566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++p2; 9576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 9586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (UBool)(*p1 == *p2); 9596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 9606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 9616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/******************************************************************** 9626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * PUBLIC int32_t Support Functions 9636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ********************************************************************/ 9646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 9656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 9666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_hashLong(const UHashTok key) { 9676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return key.integer; 9686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 9696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 9706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI UBool U_EXPORT2 9716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguhash_compareLong(const UHashTok key1, const UHashTok key2) { 9726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (UBool)(key1.integer == key2.integer); 9736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 974