11145ef852a4e230e1f642eecd8de155f2b26bc53jkummerow@chromium.org/* 29e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org****************************************************************************** 39e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org* Copyright (C) 1997-2011, International Business Machines 49e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org* Corporation and others. All Rights Reserved. 59e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org****************************************************************************** 69e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org* Date Name Description 79e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org* 03/22/00 aliu Adapted from original C++ ICU Hashtable. 89e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org* 07/06/01 aliu Modified to support int32_t keys on 99e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org* platforms with sizeof(void*) < 32. 109e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org****************************************************************************** 119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org*/ 129e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 139e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#include "uhash.h" 149e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#include "unicode/ustring.h" 159e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#include "cstring.h" 169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#include "cmemory.h" 179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#include "uassert.h" 189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#include "ustr_imp.h" 199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/* This hashtable is implemented as a double hash. All elements are 219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * stored in a single array with no secondary storage for collision 229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * resolution (no linked list, etc.). When there is a hash collision 239e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * (when two unequal keys have the same hashcode) we resolve this by 249e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * using a secondary hash. The secondary hash is an increment 259e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * computed as a hash function (a different one) of the primary 269e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * hashcode. This increment is added to the initial hash value to 279e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * obtain further slots assigned to the same hash code. For this to 289e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * work, the length of the array and the increment must be relatively 299e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * prime. The easiest way to achieve this is to have the length of 309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * the array be prime, and the increment be any value from 319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 1..length-1. 329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 339e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Hashcodes are 32-bit integers. We make sure all hashcodes are 349e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * non-negative by masking off the top bit. This has two effects: (1) 359e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * modulo arithmetic is simplified. If we allowed negative hashcodes, 369e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * then when we computed hashcode % length, we could get a negative 379e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * result, which we would then have to adjust back into range. It's 389e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * simpler to just make hashcodes non-negative. (2) It makes it easy 399e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * to check for empty vs. occupied slots in the table. We just mark 409e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * empty or deleted slots with a negative hashcode. 419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 429e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * The central function is _uhash_find(). This function looks for a 439e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * slot matching the given key and hashcode. If one is found, it 449e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * returns a pointer to that slot. If the table is full, and no match 459e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * is found, it returns NULL -- in theory. This would make the code 469e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * more complicated, since all callers of _uhash_find() would then 479e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * have to check for a NULL result. To keep this from happening, we 489e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * don't allow the table to fill. When there is only one 499e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * empty/deleted slot left, uhash_put() will refuse to increase the 509e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * count, and fail. This simplifies the code. In practice, one will 519e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * seldom encounter this using default UHashtables. However, if a 529e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * hashtable is set to a U_FIXED resize policy, or if memory is 539e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * exhausted, then the table may fill. 549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * High and low water ratios control rehashing. They establish levels 569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * of fullness (from 0 to 1) outside of which the data array is 579e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * reallocated and repopulated. Setting the low water ratio to zero 589e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * means the table will never shrink. Setting the high water ratio to 599e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * one means the table will never grow. The ratios should be 609e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * coordinated with the ratio between successive elements of the 619e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * PRIMES table, so that when the primeIndex is incremented or 629e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * decremented during rehashing, it brings the ratio of count / length 639e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * back into the desired range (between low and high water ratios). 649e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 659e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 669e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/******************************************************************** 679e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * PRIVATE Constants, Macros 689e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ********************************************************************/ 699e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 709e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/* This is a list of non-consecutive primes chosen such that 719e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * PRIMES[i+1] ~ 2*PRIMES[i]. (Currently, the ratio ranges from 1.81 729e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * to 2.18; the inverse ratio ranges from 0.459 to 0.552.) If this 739e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * ratio is changed, the low and high water ratios should also be 749e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * adjusted to suit. 759e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 769e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * These prime numbers were also chosen so that they are the largest 779e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * prime number while being less than a power of two. 789e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 799e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgstatic const int32_t PRIMES[] = { 809e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 819e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 829e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 839e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1073741789, 2147483647 /*, 4294967291 */ 849e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org}; 85c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 86c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com#define PRIMES_LENGTH (sizeof(PRIMES) / sizeof(PRIMES[0])) 87c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com#define DEFAULT_PRIME_INDEX 3 889e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 899e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/* These ratios are tuned to the PRIMES array such that a resize 909e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * places the table back into the zone of non-resizing. That is, 919e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * after a call to _uhash_rehash(), a subsequent call to 929e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * _uhash_rehash() should do nothing (should not churn). This is only 939e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * a potential problem with U_GROW_AND_SHRINK. 94c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com */ 95c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.comstatic const float RESIZE_POLICY_RATIO_TABLE[6] = { 96c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com /* low, high water ratio */ 974d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org 0.0F, 0.5F, /* U_GROW: Grow on demand, do not shrink */ 984d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org 0.1F, 0.5F, /* U_GROW_AND_SHRINK: Grow and shrink on demand */ 999e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 0.0F, 1.0F /* U_FIXED: Never change size */ 1009e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org}; 1019e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1029e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/* 1039e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org Invariants for hashcode values: 1049e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1059e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * DELETED < 0 1069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * EMPTY < 0 1079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Real hashes >= 0 1089e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1099e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org Hashcodes may not start out this way, but internally they are 1109e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org adjusted so that they are always positive. We assume 32-bit 1119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hashcodes; adjust these constants for other hashcode sizes. 1129e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org*/ 1139e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#define HASH_DELETED ((int32_t) 0x80000000) 1149e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#define HASH_EMPTY ((int32_t) HASH_DELETED + 1) 1159e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#define IS_EMPTY_OR_DELETED(x) ((x) < 0) 1179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/* This macro expects a UHashTok.pointer as its keypointer and 1199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org valuepointer parameters */ 1209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) \ 1219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash->keyDeleter != NULL && keypointer != NULL) { \ 1229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org (*hash->keyDeleter)(keypointer); \ 1233847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com } \ 1243847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com if (hash->valueDeleter != NULL && valuepointer != NULL) { \ 1253847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com (*hash->valueDeleter)(valuepointer); \ 1269e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 1279e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1289e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/* 1299e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Constants for hinting whether a key or value is an integer 1309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * or a pointer. If a hint bit is zero, then the associated 1319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * token is assumed to be an integer. 1329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 1339e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#define HINT_KEY_POINTER (1) 1349e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org#define HINT_VALUE_POINTER (2) 1359e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1369e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/******************************************************************** 1379e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * PRIVATE Implementation 1389e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ********************************************************************/ 1399e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1409e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgstatic UHashTok 1419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org_uhash_setElement(UHashtable *hash, UHashElement* e, 1429e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t hashcode, 1439e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok key, UHashTok value, int8_t hint) { 1449e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1459e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok oldValue = e->value; 1469e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash->keyDeleter != NULL && e->key.pointer != NULL && 1479e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org e->key.pointer != key.pointer) { /* Avoid double deletion */ 1489e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org (*hash->keyDeleter)(e->key.pointer); 1499e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 1509e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash->valueDeleter != NULL) { 1519e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (oldValue.pointer != NULL && 1529e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org oldValue.pointer != value.pointer) { /* Avoid double deletion */ 1539e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org (*hash->valueDeleter)(oldValue.pointer); 1549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 1559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org oldValue.pointer = NULL; 1569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 1577304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org /* Compilers should copy the UHashTok union correctly, but even if 1587304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org * they do, memory heap tools (e.g. BoundsChecker) can get 1597304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org * confused when a pointer is cloaked in a union and then copied. 16034e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org * TO ALLEVIATE THIS, we use hints (based on what API the user is 16134e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org * calling) to copy pointers when we know the user thinks 16234e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org * something is a pointer. */ 1637c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org if (hint & HINT_KEY_POINTER) { 1647c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org e->key.pointer = key.pointer; 1657c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org } else { 166ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.org e->key = key; 167ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.org } 1689e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hint & HINT_VALUE_POINTER) { 1699e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org e->value.pointer = value.pointer; 1709e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } else { 1719e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org e->value = value; 17231b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org } 17331b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org e->hashcode = hashcode; 17431b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org return oldValue; 1759e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 1769e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1779e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/** 1789e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Assumes that the given element is not empty or deleted. 1799e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 1809e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgstatic UHashTok 1819e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org_uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) { 1829e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok empty; 1839e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(!IS_EMPTY_OR_DELETED(e->hashcode)); 1849e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org --hash->count; 1859e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org empty.pointer = NULL; empty.integer = 0; 1869e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0); 1879e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 1889e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 1899e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgstatic void 1909e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org_uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) { 1919e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(hash != NULL); 1929e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(((int32_t)policy) >= 0); 1939e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(((int32_t)policy) < 3); 1949e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2]; 1959e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1]; 1969e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 1979e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 198c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com/** 199c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com * Allocate internal data array of a size determined by the given 200c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com * prime index. If the index is out of range it is pinned into range. 201c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com * If the allocation fails the status is set to 202c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com * U_MEMORY_ALLOCATION_ERROR and all array storage is freed. In 2034d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org * either case the previous array pointer is overwritten. 2044d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org * 2059e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Caller must ensure primeIndex is in range 0..PRIME_LENGTH-1. 2069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 2079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgstatic void 2089e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org_uhash_allocate(UHashtable *hash, 2099e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t primeIndex, 2109e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode *status) { 2119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2129e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashElement *p, *limit; 2139e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok emptytok; 2149e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2159e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (U_FAILURE(*status)) return; 2169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(primeIndex >= 0 && primeIndex < PRIMES_LENGTH); 2189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->primeIndex = primeIndex; 2209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->length = PRIMES[primeIndex]; 2219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org p = hash->elements = (UHashElement*) 2239e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org uprv_malloc(sizeof(UHashElement) * hash->length); 2249e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2259e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash->elements == NULL) { 2269e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org *status = U_MEMORY_ALLOCATION_ERROR; 2279e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return; 2289e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 2299e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org emptytok.pointer = NULL; /* Only one of these two is needed */ 2319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org emptytok.integer = 0; /* but we don't know which one. */ 2329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2339e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org limit = p + hash->length; 2349e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org while (p < limit) { 2359e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org p->key = emptytok; 2369e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org p->value = emptytok; 2379e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org p->hashcode = HASH_EMPTY; 2389e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++p; 2399e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 2409e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->count = 0; 2429e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio); 2433847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio); 2443847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com} 2453847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com 2463847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.comstatic UHashtable* 2473847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com_uhash_init(UHashtable *result, 2489e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashFunction *keyHash, 2499e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UKeyComparator *keyComp, 2509e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UValueComparator *valueComp, 2519e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t primeIndex, 2529e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode *status) 2539e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org{ 2549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (U_FAILURE(*status)) return NULL; 2559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(keyHash != NULL); 2569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(keyComp != NULL); 2579e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2589e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org result->keyHasher = keyHash; 2599e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org result->keyComparator = keyComp; 2609e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org result->valueComparator = valueComp; 2619e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org result->keyDeleter = NULL; 2629e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org result->valueDeleter = NULL; 2639e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org result->allocated = FALSE; 2649e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org _uhash_internalSetResizePolicy(result, U_GROW); 2659e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2669e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org _uhash_allocate(result, primeIndex, status); 2679e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 2689e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (U_FAILURE(*status)) { 2699e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return NULL; 270c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com } 271c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 272c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com return result; 273c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com} 274c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 275c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.comstatic UHashtable* 276c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com_uhash_create(UHashFunction *keyHash, 277c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com UKeyComparator *keyComp, 278c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com UValueComparator *valueComp, 279c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com int32_t primeIndex, 280c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com UErrorCode *status) { 281c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com UHashtable *result; 282c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 283c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com if (U_FAILURE(*status)) return NULL; 284c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 285c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com result = (UHashtable*) uprv_malloc(sizeof(UHashtable)); 286c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com if (result == NULL) { 287c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com *status = U_MEMORY_ALLOCATION_ERROR; 288c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com return NULL; 2899e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 290c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 2919e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org _uhash_init(result, keyHash, keyComp, valueComp, primeIndex, status); 2929e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org result->allocated = TRUE; 293c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 2949e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (U_FAILURE(*status)) { 2959e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org uprv_free(result); 296c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com return NULL; 2979e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 298c612e0211bdb8821cbd7886e15b0273ed82d2e9edanno@chromium.org 299c612e0211bdb8821cbd7886e15b0273ed82d2e9edanno@chromium.org return result; 300c612e0211bdb8821cbd7886e15b0273ed82d2e9edanno@chromium.org} 3019e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 3029e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/** 3039e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Look for a key in the table, or if no such key exists, the first 3049e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * empty slot matching the given hashcode. Keys are compared using 3059e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * the keyComparator function. 3069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 3079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * First find the start position, which is the hashcode modulo 3089e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * the length. Test it to see if it is: 3099e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 3109e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * a. identical: First check the hash values for a quick check, 3119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * then compare keys for equality using keyComparator. 312c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com * b. deleted 313c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com * c. empty 314c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com * 315c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com * Stop if it is identical or empty, otherwise continue by adding a 3169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * "jump" value (moduloing by the length again to keep it within 3179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * range) and retesting. For efficiency, there need enough empty 3189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * values so that the searchs stop within a reasonable amount of time. 3199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * This can be changed by changing the high/low water marks. 3209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 3219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * In theory, this function can return NULL, if it is full (no empty 3229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * or deleted slots) and if no matching key is found. In practice, we 3239e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * prevent this elsewhere (in uhash_put) by making sure the last slot 3249e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * in the table is never filled. 3259e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 3269fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org * The size of the table should be prime for this algorithm to work; 3279fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org * otherwise we are not guaranteed that the jump value (the secondary 3289fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org * hash) is relatively prime to the table length. 3299fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org */ 3309fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.orgstatic UHashElement* 3319fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org_uhash_find(const UHashtable *hash, UHashTok key, 3329fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org int32_t hashcode) { 3337c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org 3349fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org int32_t firstDeleted = -1; /* assume invalid index */ 3359fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org int32_t theIndex, startIndex; 3369fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org int32_t jump = 0; /* lazy evaluate */ 3379fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org int32_t tableHash; 3389fa09679c31dd1fc79a07ed24431b6951227240aricow@chromium.org UHashElement *elements = hash->elements; 3394d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org 3404d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org hashcode &= 0x7FFFFFFF; /* must be positive */ 3419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length; 3427c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org 3439e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org do { 3449e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org tableHash = elements[theIndex].hashcode; 3459e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (tableHash == hashcode) { /* quick check */ 3469e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if ((*hash->keyComparator)(key, elements[theIndex].key)) { 3479e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return &(elements[theIndex]); 3489e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 3497c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org } else if (!IS_EMPTY_OR_DELETED(tableHash)) { 3509e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* We have hit a slot which contains a key-value pair, 3519e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * but for which the hash code does not match. Keep 3529e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * looking. 3539e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 3549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } else if (tableHash == HASH_EMPTY) { /* empty, end o' the line */ 3559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org break; 3569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } else if (firstDeleted < 0) { /* remember first deleted */ 3577c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org firstDeleted = theIndex; 3589e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 3599e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (jump == 0) { /* lazy compute jump */ 3609e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* The jump value must be relatively prime to the table 3619e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * length. As long as the length is prime, then any value 3629e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * 1..length-1 will be relatively prime to it. 3639e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 3647c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org jump = (hashcode % (hash->length - 1)) + 1; 3659e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 3669e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org theIndex = (theIndex + jump) % hash->length; 3679e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } while (theIndex != startIndex); 3689e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 3699e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (firstDeleted >= 0) { 3709e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org theIndex = firstDeleted; /* reset if had deleted slot */ 3719e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } else if (tableHash != HASH_EMPTY) { 3727c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org /* We get to this point if the hashtable is full (no empty or 3739e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * deleted slots), and we've failed to find a match. THIS 3749e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * WILL NEVER HAPPEN as long as uhash_put() makes sure that 3759e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * count is always < length. 3769e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 3779e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(FALSE); 3789e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return NULL; /* Never happens if uhash_put() behaves */ 3797c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org } 3809e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return &(elements[theIndex]); 3819e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 3829e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 3839e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/** 3849e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Attempt to grow or shrink the data arrays in order to make the 3859e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * count fit between the high and low water marks. hash_put() and 3869e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * hash_remove() call this method when the count exceeds the high or 3877c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org * low water marks. This method may do nothing, if memory allocation 3889e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * fails, or if the count is already in range, or if the length is 3899e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * already at the low or high limit. In any case, upon return the 3909e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * arrays will be valid. 3919e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 3929e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgstatic void 3939e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org_uhash_rehash(UHashtable *hash, UErrorCode *status) { 3947c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org 3959e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashElement *old = hash->elements; 3969e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t oldLength = hash->length; 3979e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t newPrimeIndex = hash->primeIndex; 3983847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com int32_t i; 3993847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com 4003847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com if (hash->count > hash->highWaterMark) { 4017c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org if (++newPrimeIndex >= PRIMES_LENGTH) { 4023847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com return; 4033847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com } 4043847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com } else if (hash->count < hash->lowWaterMark) { 4059e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (--newPrimeIndex < 0) { 4069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return; 4079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 4087b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org } else { 4097b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org return; 4107b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org } 4117b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org 4127b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org _uhash_allocate(hash, newPrimeIndex, status); 4137b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org 4147b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org if (U_FAILURE(*status)) { 4157b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org hash->elements = old; 4167b26015ac58e54e88f4214e248f772ad4f055477whesse@chromium.org hash->length = oldLength; 4179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return; 4189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 4199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 4209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org for (i = oldLength - 1; i >= 0; --i) { 4219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (!IS_EMPTY_OR_DELETED(old[i].hashcode)) { 4229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode); 423c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com U_ASSERT(e != NULL); 424c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com U_ASSERT(e->hashcode == HASH_EMPTY); 425c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com e->key = old[i].key; 426c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com e->value = old[i].value; 427c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com e->hashcode = old[i].hashcode; 428c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com ++hash->count; 429c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com } 4309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 4319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 4329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org uprv_free(old); 4339e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 4349e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 4359e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgstatic UHashTok 4369e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org_uhash_remove(UHashtable *hash, 4379e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok key) { 4389e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* First find the position of the key in the table. If the object 4399e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * has not been removed already, remove it. If the user wanted 4409e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * keys deleted, then delete it also. We have to put a special 4419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * hashcode in that position that means that something has been 4429e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * deleted, since when we do a find, we have to continue PAST any 4439e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * deleted values. 4449e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 4459e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok result; 4469e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key)); 4479e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(e != NULL); 4489e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org result.pointer = NULL; 4491b3afd1cab9087ca3c4e585d3da77d374d65c082mstarzinger@chromium.org result.integer = 0; 4501b3afd1cab9087ca3c4e585d3da77d374d65c082mstarzinger@chromium.org if (!IS_EMPTY_OR_DELETED(e->hashcode)) { 4511b3afd1cab9087ca3c4e585d3da77d374d65c082mstarzinger@chromium.org result = _uhash_internalRemoveElement(hash, e); 4529e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash->count < hash->lowWaterMark) { 4539e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode status = U_ZERO_ERROR; 4549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org _uhash_rehash(hash, &status); 4559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 4569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 4579e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return result; 4589e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 4591b3afd1cab9087ca3c4e585d3da77d374d65c082mstarzinger@chromium.org 4601b3afd1cab9087ca3c4e585d3da77d374d65c082mstarzinger@chromium.orgstatic UHashTok 4611b3afd1cab9087ca3c4e585d3da77d374d65c082mstarzinger@chromium.org_uhash_put(UHashtable *hash, 4629e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok key, 4639e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok value, 464c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com int8_t hint, 4654d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org UErrorCode *status) { 4669e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 4679e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* Put finds the position in the table for the new value. If the 4689e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * key is already in the table, it is deleted, if there is a 4699e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * non-NULL keyDeleter. Then the key, the hash and the value are 4709e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * all put at the position in their respective arrays. 4719e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 4729e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t hashcode; 4739e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashElement* e; 4749e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok emptytok; 4759e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 4763847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com if (U_FAILURE(*status)) { 4779e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org goto err; 4789e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 4799e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(hash != NULL); 4809e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* Cannot always check pointer here or iSeries sees NULL every time. */ 4819e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if ((hint & HINT_VALUE_POINTER) && value.pointer == NULL) { 4829e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* Disallow storage of NULL values, since NULL is returned by 4839e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * get() to indicate an absent key. Storing NULL == removing. 4849e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 4859e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_remove(hash, key); 4867304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org } 4877c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org if (hash->count > hash->highWaterMark) { 4889e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org _uhash_rehash(hash, status); 4899e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (U_FAILURE(*status)) { 4909e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org goto err; 4919e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 4929e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 493ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.org 49431b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org hashcode = (*hash->keyHasher)(key); 4959e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org e = _uhash_find(hash, key, hashcode); 4969e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(e != NULL); 4979e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 4983847bd5ff857259e945a01d75fdb383e2351d166erik.corry@gmail.com if (IS_EMPTY_OR_DELETED(e->hashcode)) { 4999e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* Important: We must never actually fill the table up. If we 5009e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * do so, then _uhash_find() will return NULL, and we'll have 5019e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * to check for NULL after every call to _uhash_find(). To 5029e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * avoid this we make sure there is always at least one empty 5039e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * or deleted slot in the table. This only is a problem if we 5049e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * are out of memory and rehash isn't working. 5059e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 5069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++hash->count; 5079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash->count == hash->length) { 508c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com /* Don't allow count to reach length */ 509c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com --hash->count; 510c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com *status = U_MEMORY_ALLOCATION_ERROR; 5119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org goto err; 5129e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 5139e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 5149e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5159e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* We must in all cases handle storage properly. If there was an 5169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * old key, then it must be deleted (if the deleter != NULL). 5179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Make hashcodes stored in table positive. 5189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 5199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value, hint); 5209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org err: 5229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* If the deleters are non-NULL, this method adopts its key and/or 5239e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * value arguments, and we must be sure to delete the key and/or 5249e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * value in all cases, even upon failure. 5259e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 5269e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer); 5279e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org emptytok.pointer = NULL; emptytok.integer = 0; 5289e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return emptytok; 5299e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 5309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/******************************************************************** 5339e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * PUBLIC API 5349e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ********************************************************************/ 5359e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5369e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UHashtable* U_EXPORT2 5379e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_open(UHashFunction *keyHash, 5389e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UKeyComparator *keyComp, 5399e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UValueComparator *valueComp, 5409e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode *status) { 5419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5429e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_create(keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status); 5439e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 5449e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5459e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UHashtable* U_EXPORT2 5469e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_openSize(UHashFunction *keyHash, 547e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org UKeyComparator *keyComp, 548e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org UValueComparator *valueComp, 549e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org int32_t size, 550e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org UErrorCode *status) { 551e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org 552e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org /* Find the smallest index i for which PRIMES[i] >= size. */ 553e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org int32_t i = 0; 5549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) { 5559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++i; 5569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 5579e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5589e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_create(keyHash, keyComp, valueComp, i, status); 5599e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 5609e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 5619e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UHashtable* U_EXPORT2 5629e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_init(UHashtable *fillinResult, 5639e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashFunction *keyHash, 5649e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UKeyComparator *keyComp, 5659e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UValueComparator *valueComp, 5669e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode *status) { 5679e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 568c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com return _uhash_init(fillinResult, keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status); 569c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com} 570c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 571c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.comU_CAPI void U_EXPORT2 5721145ef852a4e230e1f642eecd8de155f2b26bc53jkummerow@chromium.orguhash_close(UHashtable *hash) { 5731145ef852a4e230e1f642eecd8de155f2b26bc53jkummerow@chromium.org if (hash == NULL) { 5741145ef852a4e230e1f642eecd8de155f2b26bc53jkummerow@chromium.org return; 5751145ef852a4e230e1f642eecd8de155f2b26bc53jkummerow@chromium.org } 5761145ef852a4e230e1f642eecd8de155f2b26bc53jkummerow@chromium.org if (hash->elements != NULL) { 577c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) { 578c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com int32_t pos=-1; 579c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com UHashElement *e; 580c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) { 581c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer); 5829e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 5839e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 5849e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org uprv_free(hash->elements); 5859e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->elements = NULL; 5869e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 5879e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash->allocated) { 58831b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org uprv_free(hash); 58931b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org } 59031b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org} 59131b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org 59231b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.orgU_CAPI UHashFunction *U_EXPORT2 59331b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.orguhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) { 59431b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org UHashFunction *result = hash->keyHasher; 59531b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org hash->keyHasher = fn; 59631b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org return result; 59731b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org} 59831b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org 59931b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.orgU_CAPI UKeyComparator *U_EXPORT2 60031b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.orguhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) { 60131b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org UKeyComparator *result = hash->keyComparator; 60231b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org hash->keyComparator = fn; 60331b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org return result; 60431b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org} 60531b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.orgU_CAPI UValueComparator *U_EXPORT2 6069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_setValueComparator(UHashtable *hash, UValueComparator *fn){ 6079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UValueComparator *result = hash->valueComparator; 6089e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->valueComparator = fn; 6099e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return result; 6109e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 6119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 6129e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UObjectDeleter *U_EXPORT2 6139e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) { 6149e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UObjectDeleter *result = hash->keyDeleter; 6159e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->keyDeleter = fn; 6169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return result; 6179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 6189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 6199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UObjectDeleter *U_EXPORT2 6209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) { 6219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UObjectDeleter *result = hash->valueDeleter; 6229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->valueDeleter = fn; 6239e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return result; 6249e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 6259e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 6269e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI void U_EXPORT2 6279e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) { 6289e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode status = U_ZERO_ERROR; 6299e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org _uhash_internalSetResizePolicy(hash, policy); 6309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio); 6319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio); 6329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org _uhash_rehash(hash, &status); 6337943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org} 6342efb900e7350b14be905abdeab077f3a64c583cfulan@chromium.org 6357943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.orgU_CAPI int32_t U_EXPORT2 6367943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.orguhash_count(const UHashtable *hash) { 6377943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org return hash->count; 6387943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org} 6397943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org 6407943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.orgU_CAPI void* U_EXPORT2 6417943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.orguhash_get(const UHashtable *hash, 6427943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org const void* key) { 6437943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org UHashTok keyholder; 6447943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org keyholder.pointer = (void*) key; 6457943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer; 6467943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org} 6477943d46751aa94f2738bef3002bd6675b520f3b5vegorov@chromium.org 6487304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.orgU_CAPI void* U_EXPORT2 6497304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.orguhash_iget(const UHashtable *hash, 6507304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org int32_t key) { 6517304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org UHashTok keyholder; 6527304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org keyholder.integer = key; 653c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer; 654c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com} 6557304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org 6567304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.orgU_CAPI int32_t U_EXPORT2 6577304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.orguhash_geti(const UHashtable *hash, 6587304bcac06a6a63b9f3dcebac2eeceada87ca146vegorov@chromium.org const void* key) { 65934e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org UHashTok keyholder; 66034e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org keyholder.pointer = (void*) key; 66134e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer; 66234e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org} 66334e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 66434e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.orgU_CAPI int32_t U_EXPORT2 66534e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.orguhash_igeti(const UHashtable *hash, 66634e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org int32_t key) { 66734e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org UHashTok keyholder; 66834e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org keyholder.integer = key; 66934e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer; 67034e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org} 67134e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 6727c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.orgU_CAPI void* U_EXPORT2 6737c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.orguhash_put(UHashtable *hash, 6747c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org void* key, 6757c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org void* value, 6767c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org UErrorCode *status) { 6777c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org UHashTok keyholder, valueholder; 6787c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org keyholder.pointer = key; 6797c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org valueholder.pointer = value; 6807c2628c3f0353f0558760c3ca442f934263ea766kmillikin@chromium.org return _uhash_put(hash, keyholder, valueholder, 6819e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org HINT_KEY_POINTER | HINT_VALUE_POINTER, 6829e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org status).pointer; 6839e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 6849e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 6859e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI void* U_EXPORT2 6869e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_iput(UHashtable *hash, 6879e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t key, 6889e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org void* value, 6899e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode *status) { 6909e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok keyholder, valueholder; 6919e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org keyholder.integer = key; 6929e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org valueholder.pointer = value; 6939e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_put(hash, keyholder, valueholder, 6949e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org HINT_VALUE_POINTER, 6959e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org status).pointer; 6969e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 6979e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 6989e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI int32_t U_EXPORT2 6999e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_puti(UHashtable *hash, 7009e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org void* key, 7019e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t value, 7029e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode *status) { 7039e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok keyholder, valueholder; 7049e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org keyholder.pointer = key; 7059e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org valueholder.integer = value; 7069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_put(hash, keyholder, valueholder, 7079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org HINT_KEY_POINTER, 7089e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org status).integer; 7099e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 7109e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7129e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI int32_t U_EXPORT2 7139e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_iputi(UHashtable *hash, 7149e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t key, 7159e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t value, 7169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UErrorCode *status) { 7179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok keyholder, valueholder; 7189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org keyholder.integer = key; 7199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org valueholder.integer = value; 7209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_put(hash, keyholder, valueholder, 7219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 0, /* neither is a ptr */ 7229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org status).integer; 7239e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 7249e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7259e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI void* U_EXPORT2 7269e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_remove(UHashtable *hash, 7279e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const void* key) { 7289e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok keyholder; 7299e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org keyholder.pointer = (void*) key; 7309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_remove(hash, keyholder).pointer; 7319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 7329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7339e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI void* U_EXPORT2 7349e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_iremove(UHashtable *hash, 7359e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t key) { 7369e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok keyholder; 7379e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org keyholder.integer = key; 7389e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_remove(hash, keyholder).pointer; 7399e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 7409e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI int32_t U_EXPORT2 7429e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_removei(UHashtable *hash, 7439e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const void* key) { 7449e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok keyholder; 7459e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org keyholder.pointer = (void*) key; 7469e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_remove(hash, keyholder).integer; 7479e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 7489e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7499e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI int32_t U_EXPORT2 7509e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_iremovei(UHashtable *hash, 7519e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t key) { 7529e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok keyholder; 7539e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org keyholder.integer = key; 7549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_remove(hash, keyholder).integer; 7559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 7569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7579e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI void U_EXPORT2 7589e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_removeAll(UHashtable *hash) { 7599e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t pos = -1; 7609e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UHashElement *e; 7619e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(hash != NULL); 7629e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash->count != 0) { 7639e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org while ((e = uhash_nextElement(hash, &pos)) != NULL) { 7649e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org uhash_removeElement(hash, e); 7659e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 7669e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 7679e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(hash->count == 0); 7689e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 7699e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7709e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI const UHashElement* U_EXPORT2 7719e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_find(const UHashtable *hash, const void* key) { 7729e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok keyholder; 773ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.org const UHashElement *e; 774c3b37129d6387b2db313f9100256d2d5f60dd9a8jkummerow@chromium.org keyholder.pointer = (void*) key; 7759e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder)); 7769e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return IS_EMPTY_OR_DELETED(e->hashcode) ? NULL : e; 7779e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 7789e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 7799e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI const UHashElement* U_EXPORT2 7809e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_nextElement(const UHashtable *hash, int32_t *pos) { 7819e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* Walk through the array until we find an element that is not 7829e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * EMPTY and not DELETED. 7839e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 7849e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t i; 7859e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org U_ASSERT(hash != NULL); 7869e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org for (i = *pos + 1; i < hash->length; ++i) { 7879e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) { 7889e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org *pos = i; 7899e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return &(hash->elements[i]); 7909e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 7919e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 7929e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 793f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.com /* No more elements */ 794f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.com return NULL; 795f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.com} 796f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.com 797f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.comU_CAPI void* U_EXPORT2 798f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.comuhash_removeElement(UHashtable *hash, const UHashElement* e) { 799f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.com U_ASSERT(hash != NULL); 800f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.com U_ASSERT(e != NULL); 801f2038fb01417bcf7698b87a5dfaa4a861539618aerik.corry@gmail.com if (!IS_EMPTY_OR_DELETED(e->hashcode)) { 8029e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashElement *nce = (UHashElement *)e; 8039e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return _uhash_internalRemoveElement(hash, nce).pointer; 8049e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 8059e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return NULL; 8069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 8079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8089e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/******************************************************************** 8099e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * UHashTok convenience 8109e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ********************************************************************/ 8119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8129e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/** 8139e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Return a UHashTok for an integer. 8149e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 8159e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/*U_CAPI UHashTok U_EXPORT2 8169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_toki(int32_t i) { 8179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok tok; 8189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org tok.integer = i; 8199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return tok; 8209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org}*/ 8219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/** 8239e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Return a UHashTok for a pointer. 8249e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 8259e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/*U_CAPI UHashTok U_EXPORT2 8269e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_tokp(void* p) { 8279e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org UHashTok tok; 8289e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org tok.pointer = p; 8299e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return tok; 8309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org}*/ 8319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/******************************************************************** 8339e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * PUBLIC Key Hash Functions 8349e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ********************************************************************/ 8359e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8369e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI int32_t U_EXPORT2 8379e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_hashUChars(const UHashTok key) { 8389e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UChar *s = (const UChar *)key.pointer; 8399e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return s == NULL ? 0 : ustr_hashUCharsN(s, u_strlen(s)); 8409e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 8419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8429e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI int32_t U_EXPORT2 8439e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_hashChars(const UHashTok key) { 8449e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const char *s = (const char *)key.pointer; 8459e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return s == NULL ? 0 : ustr_hashCharsN(s, uprv_strlen(s)); 8469e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 8479e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8489e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI int32_t U_EXPORT2 8499e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_hashIChars(const UHashTok key) { 8509e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const char *s = (const char *)key.pointer; 8519e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return s == NULL ? 0 : ustr_hashICharsN(s, uprv_strlen(s)); 8529e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 8539e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UBool U_EXPORT2 8559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_equals(const UHashtable* hash1, const UHashtable* hash2){ 8569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org int32_t count1, count2, pos, i; 8579e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8589e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if(hash1==hash2){ 8599e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return TRUE; 8609e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 8619e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8629e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* 8639e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Make sure that we are comparing 2 valid hashes of the same type 8649e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * with valid comparison functions. 8659e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * Without valid comparison functions, a binary comparison 8669e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * of the hash values will yield random results on machines 8679e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * with 64-bit pointers and 32-bit integer hashes. 8689e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * A valueComparator is normally optional. 8699e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 8709e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (hash1==NULL || hash2==NULL || 8719e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash1->keyComparator != hash2->keyComparator || 8729e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash1->valueComparator != hash2->valueComparator || 8739e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org hash1->valueComparator == NULL) 8749e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org { 8759e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* 8769e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org Normally we would return an error here about incompatible hash tables, 8779e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org but we return FALSE instead. 878c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com */ 879c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com return FALSE; 880c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com } 881c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com 8829e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org count1 = uhash_count(hash1); 8839e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org count2 = uhash_count(hash2); 8849e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if(count1!=count2){ 8859e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return FALSE; 886c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com } 8879e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 8889e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org pos=-1; 8899e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org for(i=0; i<count1; i++){ 8909e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UHashElement* elem1 = uhash_nextElement(hash1, &pos); 8919e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UHashTok key1 = elem1->key; 8929e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UHashTok val1 = elem1->value; 8939e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org /* here the keys are not compared, instead the key form hash1 is used to fetch 8949e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * value from hash2. If the hashes are equal then then both hashes should 8959e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * contain equal values for the same key! 8969e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org */ 8979e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UHashElement* elem2 = _uhash_find(hash2, key1, hash2->keyHasher(key1)); 8989e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UHashTok val2 = elem2->value; 8999e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if(hash1->valueComparator(val1, val2)==FALSE){ 9009e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return FALSE; 9019e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9029e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9039e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return TRUE; 9049e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 9059e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 9069e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/******************************************************************** 9079e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * PUBLIC Comparator Functions 9089e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ********************************************************************/ 9099e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 9109e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UBool U_EXPORT2 9119e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_compareUChars(const UHashTok key1, const UHashTok key2) { 9129e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UChar *p1 = (const UChar*) key1.pointer; 9139e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const UChar *p2 = (const UChar*) key2.pointer; 9149e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (p1 == p2) { 9159e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return TRUE; 9169e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9179e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (p1 == NULL || p2 == NULL) { 9189e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return FALSE; 9199e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9209e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org while (*p1 != 0 && *p1 == *p2) { 9219e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++p1; 9229e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++p2; 9239e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9249e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return (UBool)(*p1 == *p2); 9259e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 9269e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 9279e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UBool U_EXPORT2 9289e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_compareChars(const UHashTok key1, const UHashTok key2) { 9299e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const char *p1 = (const char*) key1.pointer; 9309e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const char *p2 = (const char*) key2.pointer; 9319e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (p1 == p2) { 9329e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return TRUE; 9339e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9349e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (p1 == NULL || p2 == NULL) { 9359e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return FALSE; 9369e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9379e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org while (*p1 != 0 && *p1 == *p2) { 9389e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++p1; 9399e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++p2; 9409e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9419e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return (UBool)(*p1 == *p2); 9429e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 9439e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 9449e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UBool U_EXPORT2 9459e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_compareIChars(const UHashTok key1, const UHashTok key2) { 9469e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const char *p1 = (const char*) key1.pointer; 9479e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org const char *p2 = (const char*) key2.pointer; 9489e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (p1 == p2) { 9499e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return TRUE; 9509e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9519e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org if (p1 == NULL || p2 == NULL) { 9529e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return FALSE; 9539e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9549e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org while (*p1 != 0 && uprv_tolower(*p1) == uprv_tolower(*p2)) { 9559e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++p1; 9569e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ++p2; 9579e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org } 9589e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return (UBool)(*p1 == *p2); 9599e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 9609e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 9619e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org/******************************************************************** 9629e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org * PUBLIC int32_t Support Functions 9639e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org ********************************************************************/ 9649e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 9659e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI int32_t U_EXPORT2 9669e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_hashLong(const UHashTok key) { 9679e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return key.integer; 9689e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 9699e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org 9709e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orgU_CAPI UBool U_EXPORT2 9719e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.orguhash_compareLong(const UHashTok key1, const UHashTok key2) { 9729e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org return (UBool)(key1.integer == key2.integer); 9739e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org} 9749e3e0b618a14a05efd7d66f20bac4423dd3a1a2ffschneider@chromium.org