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