2 ******************************************************************************
3 * Copyright (C) 1997-2006, International Business Machines
4 * Corporation and others. All Rights Reserved.
5 ******************************************************************************
6 * Date Name Description
7 * 03/22/00 aliu Adapted from original C++ ICU Hashtable.
8 * 07/06/01 aliu Modified to support int32_t keys on
9 * platforms with sizeof(void*) < 32.
10 ******************************************************************************
14 #include "unicode/ustring.h"
19 /* This hashtable is implemented as a double hash. All elements are
20 * stored in a single array with no secondary storage for collision
21 * resolution (no linked list, etc.). When there is a hash collision
22 * (when two unequal keys have the same hashcode) we resolve this by
23 * using a secondary hash. The secondary hash is an increment
24 * computed as a hash function (a different one) of the primary
25 * hashcode. This increment is added to the initial hash value to
26 * obtain further slots assigned to the same hash code. For this to
27 * work, the length of the array and the increment must be relatively
28 * prime. The easiest way to achieve this is to have the length of
29 * the array be prime, and the increment be any value from
32 * Hashcodes are 32-bit integers. We make sure all hashcodes are
33 * non-negative by masking off the top bit. This has two effects: (1)
34 * modulo arithmetic is simplified. If we allowed negative hashcodes,
35 * then when we computed hashcode % length, we could get a negative
36 * result, which we would then have to adjust back into range. It's
37 * simpler to just make hashcodes non-negative. (2) It makes it easy
38 * to check for empty vs. occupied slots in the table. We just mark
39 * empty or deleted slots with a negative hashcode.
41 * The central function is _uhash_find(). This function looks for a
42 * slot matching the given key and hashcode. If one is found, it
43 * returns a pointer to that slot. If the table is full, and no match
44 * is found, it returns NULL -- in theory. This would make the code
45 * more complicated, since all callers of _uhash_find() would then
46 * have to check for a NULL result. To keep this from happening, we
47 * don't allow the table to fill. When there is only one
48 * empty/deleted slot left, uhash_put() will refuse to increase the
49 * count, and fail. This simplifies the code. In practice, one will
50 * seldom encounter this using default UHashtables. However, if a
51 * hashtable is set to a U_FIXED resize policy, or if memory is
52 * exhausted, then the table may fill.
54 * High and low water ratios control rehashing. They establish levels
55 * of fullness (from 0 to 1) outside of which the data array is
56 * reallocated and repopulated. Setting the low water ratio to zero
57 * means the table will never shrink. Setting the high water ratio to
58 * one means the table will never grow. The ratios should be
59 * coordinated with the ratio between successive elements of the
60 * PRIMES table, so that when the primeIndex is incremented or
61 * decremented during rehashing, it brings the ratio of count / length
62 * back into the desired range (between low and high water ratios).
65 /********************************************************************
66 * PRIVATE Constants, Macros
67 ********************************************************************/
69 /* This is a list of non-consecutive primes chosen such that
70 * PRIMES[i+1] ~ 2*PRIMES[i]. (Currently, the ratio ranges from 1.81
71 * to 2.18; the inverse ratio ranges from 0.459 to 0.552.) If this
72 * ratio is changed, the low and high water ratios should also be
75 * These prime numbers were also chosen so that they are the largest
76 * prime number while being less than a power of two.
78 static const int32_t PRIMES
[] = {
79 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749,
80 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593,
81 16777213, 33554393, 67108859, 134217689, 268435399, 536870909,
82 1073741789, 2147483647 /*, 4294967291 */
85 #define PRIMES_LENGTH (sizeof(PRIMES) / sizeof(PRIMES[0]))
86 #define DEFAULT_PRIME_INDEX 3
88 /* These ratios are tuned to the PRIMES array such that a resize
89 * places the table back into the zone of non-resizing. That is,
90 * after a call to _uhash_rehash(), a subsequent call to
91 * _uhash_rehash() should do nothing (should not churn). This is only
92 * a potential problem with U_GROW_AND_SHRINK.
94 static const float RESIZE_POLICY_RATIO_TABLE
[6] = {
95 /* low, high water ratio */
96 0.0F
, 0.5F
, /* U_GROW: Grow on demand, do not shrink */
97 0.1F
, 0.5F
, /* U_GROW_AND_SHRINK: Grow and shrink on demand */
98 0.0F
, 1.0F
/* U_FIXED: Never change size */
102 Invariants for hashcode values:
108 Hashcodes may not start out this way, but internally they are
109 adjusted so that they are always positive. We assume 32-bit
110 hashcodes; adjust these constants for other hashcode sizes.
112 #define HASH_DELETED ((int32_t) 0x80000000)
113 #define HASH_EMPTY ((int32_t) HASH_DELETED + 1)
115 #define IS_EMPTY_OR_DELETED(x) ((x) < 0)
117 /* This macro expects a UHashTok.pointer as its keypointer and
118 valuepointer parameters */
119 #define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) \
120 if (hash->keyDeleter != NULL && keypointer != NULL) { \
121 (*hash->keyDeleter)(keypointer); \
123 if (hash->valueDeleter != NULL && valuepointer != NULL) { \
124 (*hash->valueDeleter)(valuepointer); \
128 * Constants for hinting whether a key or value is an integer
129 * or a pointer. If a hint bit is zero, then the associated
130 * token is assumed to be an integer.
132 #define HINT_KEY_POINTER (1)
133 #define HINT_VALUE_POINTER (2)
135 /********************************************************************
136 * PRIVATE Implementation
137 ********************************************************************/
140 _uhash_setElement(UHashtable
*hash
, UHashElement
* e
,
142 UHashTok key
, UHashTok value
, int8_t hint
) {
144 UHashTok oldValue
= e
->value
;
145 if (hash
->keyDeleter
!= NULL
&& e
->key
.pointer
!= NULL
&&
146 e
->key
.pointer
!= key
.pointer
) { /* Avoid double deletion */
147 (*hash
->keyDeleter
)(e
->key
.pointer
);
149 if (hash
->valueDeleter
!= NULL
) {
150 if (oldValue
.pointer
!= NULL
&&
151 oldValue
.pointer
!= value
.pointer
) { /* Avoid double deletion */
152 (*hash
->valueDeleter
)(oldValue
.pointer
);
154 oldValue
.pointer
= NULL
;
156 /* Compilers should copy the UHashTok union correctly, but even if
157 * they do, memory heap tools (e.g. BoundsChecker) can get
158 * confused when a pointer is cloaked in a union and then copied.
159 * TO ALLEVIATE THIS, we use hints (based on what API the user is
160 * calling) to copy pointers when we know the user thinks
161 * something is a pointer. */
162 if (hint
& HINT_KEY_POINTER
) {
163 e
->key
.pointer
= key
.pointer
;
167 if (hint
& HINT_VALUE_POINTER
) {
168 e
->value
.pointer
= value
.pointer
;
172 e
->hashcode
= hashcode
;
177 * Assumes that the given element is not empty or deleted.
180 _uhash_internalRemoveElement(UHashtable
*hash
, UHashElement
* e
) {
182 U_ASSERT(!IS_EMPTY_OR_DELETED(e
->hashcode
));
184 empty
.pointer
= NULL
; empty
.integer
= 0;
185 return _uhash_setElement(hash
, e
, HASH_DELETED
, empty
, empty
, 0);
189 _uhash_internalSetResizePolicy(UHashtable
*hash
, enum UHashResizePolicy policy
) {
190 U_ASSERT(hash
!= NULL
);
191 U_ASSERT(((int32_t)policy
) >= 0);
192 U_ASSERT(((int32_t)policy
) < 3);
193 hash
->lowWaterRatio
= RESIZE_POLICY_RATIO_TABLE
[policy
* 2];
194 hash
->highWaterRatio
= RESIZE_POLICY_RATIO_TABLE
[policy
* 2 + 1];
198 * Allocate internal data array of a size determined by the given
199 * prime index. If the index is out of range it is pinned into range.
200 * If the allocation fails the status is set to
201 * U_MEMORY_ALLOCATION_ERROR and all array storage is freed. In
202 * either case the previous array pointer is overwritten.
204 * Caller must ensure primeIndex is in range 0..PRIME_LENGTH-1.
207 _uhash_allocate(UHashtable
*hash
,
209 UErrorCode
*status
) {
211 UHashElement
*p
, *limit
;
214 if (U_FAILURE(*status
)) return;
216 U_ASSERT(primeIndex
>= 0 && primeIndex
< PRIMES_LENGTH
);
218 hash
->primeIndex
= primeIndex
;
219 hash
->length
= PRIMES
[primeIndex
];
221 p
= hash
->elements
= (UHashElement
*)
222 uprv_malloc(sizeof(UHashElement
) * hash
->length
);
224 if (hash
->elements
== NULL
) {
225 *status
= U_MEMORY_ALLOCATION_ERROR
;
229 emptytok
.pointer
= NULL
; /* Only one of these two is needed */
230 emptytok
.integer
= 0; /* but we don't know which one. */
232 limit
= p
+ hash
->length
;
236 p
->hashcode
= HASH_EMPTY
;
241 hash
->lowWaterMark
= (int32_t)(hash
->length
* hash
->lowWaterRatio
);
242 hash
->highWaterMark
= (int32_t)(hash
->length
* hash
->highWaterRatio
);
246 _uhash_init(UHashtable
*result
,
247 UHashFunction
*keyHash
,
248 UKeyComparator
*keyComp
,
249 UValueComparator
*valueComp
,
253 if (U_FAILURE(*status
)) return NULL
;
254 U_ASSERT(keyHash
!= NULL
);
255 U_ASSERT(keyComp
!= NULL
);
257 result
->keyHasher
= keyHash
;
258 result
->keyComparator
= keyComp
;
259 result
->valueComparator
= valueComp
;
260 result
->keyDeleter
= NULL
;
261 result
->valueDeleter
= NULL
;
262 result
->allocated
= FALSE
;
263 _uhash_internalSetResizePolicy(result
, U_GROW
);
265 _uhash_allocate(result
, primeIndex
, status
);
267 if (U_FAILURE(*status
)) {
275 _uhash_create(UHashFunction
*keyHash
,
276 UKeyComparator
*keyComp
,
277 UValueComparator
*valueComp
,
279 UErrorCode
*status
) {
282 if (U_FAILURE(*status
)) return NULL
;
284 result
= (UHashtable
*) uprv_malloc(sizeof(UHashtable
));
285 if (result
== NULL
) {
286 *status
= U_MEMORY_ALLOCATION_ERROR
;
290 _uhash_init(result
, keyHash
, keyComp
, valueComp
, primeIndex
, status
);
291 result
->allocated
= TRUE
;
293 if (U_FAILURE(*status
)) {
302 * Look for a key in the table, or if no such key exists, the first
303 * empty slot matching the given hashcode. Keys are compared using
304 * the keyComparator function.
306 * First find the start position, which is the hashcode modulo
307 * the length. Test it to see if it is:
309 * a. identical: First check the hash values for a quick check,
310 * then compare keys for equality using keyComparator.
314 * Stop if it is identical or empty, otherwise continue by adding a
315 * "jump" value (moduloing by the length again to keep it within
316 * range) and retesting. For efficiency, there need enough empty
317 * values so that the searchs stop within a reasonable amount of time.
318 * This can be changed by changing the high/low water marks.
320 * In theory, this function can return NULL, if it is full (no empty
321 * or deleted slots) and if no matching key is found. In practice, we
322 * prevent this elsewhere (in uhash_put) by making sure the last slot
323 * in the table is never filled.
325 * The size of the table should be prime for this algorithm to work;
326 * otherwise we are not guaranteed that the jump value (the secondary
327 * hash) is relatively prime to the table length.
330 _uhash_find(const UHashtable
*hash
, UHashTok key
,
333 int32_t firstDeleted
= -1; /* assume invalid index */
334 int32_t theIndex
, startIndex
;
335 int32_t jump
= 0; /* lazy evaluate */
337 UHashElement
*elements
= hash
->elements
;
339 hashcode
&= 0x7FFFFFFF; /* must be positive */
340 startIndex
= theIndex
= (hashcode
^ 0x4000000) % hash
->length
;
343 tableHash
= elements
[theIndex
].hashcode
;
344 if (tableHash
== hashcode
) { /* quick check */
345 if ((*hash
->keyComparator
)(key
, elements
[theIndex
].key
)) {
346 return &(elements
[theIndex
]);
348 } else if (!IS_EMPTY_OR_DELETED(tableHash
)) {
349 /* We have hit a slot which contains a key-value pair,
350 * but for which the hash code does not match. Keep
353 } else if (tableHash
== HASH_EMPTY
) { /* empty, end o' the line */
355 } else if (firstDeleted
< 0) { /* remember first deleted */
356 firstDeleted
= theIndex
;
358 if (jump
== 0) { /* lazy compute jump */
359 /* The jump value must be relatively prime to the table
360 * length. As long as the length is prime, then any value
361 * 1..length-1 will be relatively prime to it.
363 jump
= (hashcode
% (hash
->length
- 1)) + 1;
365 theIndex
= (theIndex
+ jump
) % hash
->length
;
366 } while (theIndex
!= startIndex
);
368 if (firstDeleted
>= 0) {
369 theIndex
= firstDeleted
; /* reset if had deleted slot */
370 } else if (tableHash
!= HASH_EMPTY
) {
371 /* We get to this point if the hashtable is full (no empty or
372 * deleted slots), and we've failed to find a match. THIS
373 * WILL NEVER HAPPEN as long as uhash_put() makes sure that
374 * count is always < length.
377 return NULL
; /* Never happens if uhash_put() behaves */
379 return &(elements
[theIndex
]);
383 * Attempt to grow or shrink the data arrays in order to make the
384 * count fit between the high and low water marks. hash_put() and
385 * hash_remove() call this method when the count exceeds the high or
386 * low water marks. This method may do nothing, if memory allocation
387 * fails, or if the count is already in range, or if the length is
388 * already at the low or high limit. In any case, upon return the
389 * arrays will be valid.
392 _uhash_rehash(UHashtable
*hash
) {
394 UHashElement
*old
= hash
->elements
;
395 int32_t oldLength
= hash
->length
;
396 int32_t newPrimeIndex
= hash
->primeIndex
;
398 UErrorCode status
= U_ZERO_ERROR
;
400 if (hash
->count
> hash
->highWaterMark
) {
401 if (++newPrimeIndex
>= PRIMES_LENGTH
) {
404 } else if (hash
->count
< hash
->lowWaterMark
) {
405 if (--newPrimeIndex
< 0) {
412 _uhash_allocate(hash
, newPrimeIndex
, &status
);
414 if (U_FAILURE(status
)) {
415 hash
->elements
= old
;
416 hash
->length
= oldLength
;
420 for (i
= oldLength
- 1; i
>= 0; --i
) {
421 if (!IS_EMPTY_OR_DELETED(old
[i
].hashcode
)) {
422 UHashElement
*e
= _uhash_find(hash
, old
[i
].key
, old
[i
].hashcode
);
424 U_ASSERT(e
->hashcode
== HASH_EMPTY
);
426 e
->value
= old
[i
].value
;
427 e
->hashcode
= old
[i
].hashcode
;
436 _uhash_remove(UHashtable
*hash
,
438 /* First find the position of the key in the table. If the object
439 * has not been removed already, remove it. If the user wanted
440 * keys deleted, then delete it also. We have to put a special
441 * hashcode in that position that means that something has been
442 * deleted, since when we do a find, we have to continue PAST any
446 UHashElement
* e
= _uhash_find(hash
, key
, hash
->keyHasher(key
));
448 result
.pointer
= NULL
; result
.integer
= 0;
449 if (!IS_EMPTY_OR_DELETED(e
->hashcode
)) {
450 result
= _uhash_internalRemoveElement(hash
, e
);
451 if (hash
->count
< hash
->lowWaterMark
) {
459 _uhash_put(UHashtable
*hash
,
463 UErrorCode
*status
) {
465 /* Put finds the position in the table for the new value. If the
466 * key is already in the table, it is deleted, if there is a
467 * non-NULL keyDeleter. Then the key, the hash and the value are
468 * all put at the position in their respective arrays.
474 if (U_FAILURE(*status
)) {
477 U_ASSERT(hash
!= NULL
);
478 /* Cannot always check pointer here or iSeries sees NULL every time. */
479 if ((hint
& HINT_VALUE_POINTER
) && value
.pointer
== NULL
) {
480 /* Disallow storage of NULL values, since NULL is returned by
481 * get() to indicate an absent key. Storing NULL == removing.
483 return _uhash_remove(hash
, key
);
485 if (hash
->count
> hash
->highWaterMark
) {
489 hashcode
= (*hash
->keyHasher
)(key
);
490 e
= _uhash_find(hash
, key
, hashcode
);
493 if (IS_EMPTY_OR_DELETED(e
->hashcode
)) {
494 /* Important: We must never actually fill the table up. If we
495 * do so, then _uhash_find() will return NULL, and we'll have
496 * to check for NULL after every call to _uhash_find(). To
497 * avoid this we make sure there is always at least one empty
498 * or deleted slot in the table. This only is a problem if we
499 * are out of memory and rehash isn't working.
502 if (hash
->count
== hash
->length
) {
503 /* Don't allow count to reach length */
505 *status
= U_MEMORY_ALLOCATION_ERROR
;
510 /* We must in all cases handle storage properly. If there was an
511 * old key, then it must be deleted (if the deleter != NULL).
512 * Make hashcodes stored in table positive.
514 return _uhash_setElement(hash
, e
, hashcode
& 0x7FFFFFFF, key
, value
, hint
);
517 /* If the deleters are non-NULL, this method adopts its key and/or
518 * value arguments, and we must be sure to delete the key and/or
519 * value in all cases, even upon failure.
521 HASH_DELETE_KEY_VALUE(hash
, key
.pointer
, value
.pointer
);
522 emptytok
.pointer
= NULL
; emptytok
.integer
= 0;
527 /********************************************************************
529 ********************************************************************/
531 U_CAPI UHashtable
* U_EXPORT2
532 uhash_open(UHashFunction
*keyHash
,
533 UKeyComparator
*keyComp
,
534 UValueComparator
*valueComp
,
535 UErrorCode
*status
) {
537 return _uhash_create(keyHash
, keyComp
, valueComp
, DEFAULT_PRIME_INDEX
, status
);
540 U_CAPI UHashtable
* U_EXPORT2
541 uhash_openSize(UHashFunction
*keyHash
,
542 UKeyComparator
*keyComp
,
543 UValueComparator
*valueComp
,
545 UErrorCode
*status
) {
547 /* Find the smallest index i for which PRIMES[i] >= size. */
549 while (i
<(PRIMES_LENGTH
-1) && PRIMES
[i
]<size
) {
553 return _uhash_create(keyHash
, keyComp
, valueComp
, i
, status
);
556 U_CAPI UHashtable
* U_EXPORT2
557 uhash_init(UHashtable
*fillinResult
,
558 UHashFunction
*keyHash
,
559 UKeyComparator
*keyComp
,
560 UValueComparator
*valueComp
,
561 UErrorCode
*status
) {
563 return _uhash_init(fillinResult
, keyHash
, keyComp
, valueComp
, DEFAULT_PRIME_INDEX
, status
);
566 U_CAPI
void U_EXPORT2
567 uhash_close(UHashtable
*hash
) {
568 U_ASSERT(hash
!= NULL
);
569 if (hash
->elements
!= NULL
) {
570 if (hash
->keyDeleter
!= NULL
|| hash
->valueDeleter
!= NULL
) {
573 while ((e
= (UHashElement
*) uhash_nextElement(hash
, &pos
)) != NULL
) {
574 HASH_DELETE_KEY_VALUE(hash
, e
->key
.pointer
, e
->value
.pointer
);
577 uprv_free(hash
->elements
);
578 hash
->elements
= NULL
;
580 if (hash
->allocated
) {
585 U_CAPI UHashFunction
*U_EXPORT2
586 uhash_setKeyHasher(UHashtable
*hash
, UHashFunction
*fn
) {
587 UHashFunction
*result
= hash
->keyHasher
;
588 hash
->keyHasher
= fn
;
592 U_CAPI UKeyComparator
*U_EXPORT2
593 uhash_setKeyComparator(UHashtable
*hash
, UKeyComparator
*fn
) {
594 UKeyComparator
*result
= hash
->keyComparator
;
595 hash
->keyComparator
= fn
;
598 U_CAPI UValueComparator
*U_EXPORT2
599 uhash_setValueComparator(UHashtable
*hash
, UValueComparator
*fn
){
600 UValueComparator
*result
= hash
->valueComparator
;
601 hash
->valueComparator
= fn
;
605 U_CAPI UObjectDeleter
*U_EXPORT2
606 uhash_setKeyDeleter(UHashtable
*hash
, UObjectDeleter
*fn
) {
607 UObjectDeleter
*result
= hash
->keyDeleter
;
608 hash
->keyDeleter
= fn
;
612 U_CAPI UObjectDeleter
*U_EXPORT2
613 uhash_setValueDeleter(UHashtable
*hash
, UObjectDeleter
*fn
) {
614 UObjectDeleter
*result
= hash
->valueDeleter
;
615 hash
->valueDeleter
= fn
;
619 U_CAPI
void U_EXPORT2
620 uhash_setResizePolicy(UHashtable
*hash
, enum UHashResizePolicy policy
) {
621 _uhash_internalSetResizePolicy(hash
, policy
);
622 hash
->lowWaterMark
= (int32_t)(hash
->length
* hash
->lowWaterRatio
);
623 hash
->highWaterMark
= (int32_t)(hash
->length
* hash
->highWaterRatio
);
627 U_CAPI
int32_t U_EXPORT2
628 uhash_count(const UHashtable
*hash
) {
632 U_CAPI
void* U_EXPORT2
633 uhash_get(const UHashtable
*hash
,
636 keyholder
.pointer
= (void*) key
;
637 return _uhash_find(hash
, keyholder
, hash
->keyHasher(keyholder
))->value
.pointer
;
640 U_CAPI
void* U_EXPORT2
641 uhash_iget(const UHashtable
*hash
,
644 keyholder
.integer
= key
;
645 return _uhash_find(hash
, keyholder
, hash
->keyHasher(keyholder
))->value
.pointer
;
648 U_CAPI
int32_t U_EXPORT2
649 uhash_geti(const UHashtable
*hash
,
652 keyholder
.pointer
= (void*) key
;
653 return _uhash_find(hash
, keyholder
, hash
->keyHasher(keyholder
))->value
.integer
;
656 U_CAPI
int32_t U_EXPORT2
657 uhash_igeti(const UHashtable
*hash
,
660 keyholder
.integer
= key
;
661 return _uhash_find(hash
, keyholder
, hash
->keyHasher(keyholder
))->value
.integer
;
664 U_CAPI
void* U_EXPORT2
665 uhash_put(UHashtable
*hash
,
668 UErrorCode
*status
) {
669 UHashTok keyholder
, valueholder
;
670 keyholder
.pointer
= key
;
671 valueholder
.pointer
= value
;
672 return _uhash_put(hash
, keyholder
, valueholder
,
673 HINT_KEY_POINTER
| HINT_VALUE_POINTER
,
677 U_CAPI
void* U_EXPORT2
678 uhash_iput(UHashtable
*hash
,
681 UErrorCode
*status
) {
682 UHashTok keyholder
, valueholder
;
683 keyholder
.integer
= key
;
684 valueholder
.pointer
= value
;
685 return _uhash_put(hash
, keyholder
, valueholder
,
690 U_CAPI
int32_t U_EXPORT2
691 uhash_puti(UHashtable
*hash
,
694 UErrorCode
*status
) {
695 UHashTok keyholder
, valueholder
;
696 keyholder
.pointer
= key
;
697 valueholder
.integer
= value
;
698 return _uhash_put(hash
, keyholder
, valueholder
,
704 U_CAPI
int32_t U_EXPORT2
705 uhash_iputi(UHashtable
*hash
,
708 UErrorCode
*status
) {
709 UHashTok keyholder
, valueholder
;
710 keyholder
.integer
= key
;
711 valueholder
.integer
= value
;
712 return _uhash_put(hash
, keyholder
, valueholder
,
713 0, /* neither is a ptr */
717 U_CAPI
void* U_EXPORT2
718 uhash_remove(UHashtable
*hash
,
721 keyholder
.pointer
= (void*) key
;
722 return _uhash_remove(hash
, keyholder
).pointer
;
725 U_CAPI
void* U_EXPORT2
726 uhash_iremove(UHashtable
*hash
,
729 keyholder
.integer
= key
;
730 return _uhash_remove(hash
, keyholder
).pointer
;
733 U_CAPI
int32_t U_EXPORT2
734 uhash_removei(UHashtable
*hash
,
737 keyholder
.pointer
= (void*) key
;
738 return _uhash_remove(hash
, keyholder
).integer
;
741 U_CAPI
int32_t U_EXPORT2
742 uhash_iremovei(UHashtable
*hash
,
745 keyholder
.integer
= key
;
746 return _uhash_remove(hash
, keyholder
).integer
;
749 U_CAPI
void U_EXPORT2
750 uhash_removeAll(UHashtable
*hash
) {
752 const UHashElement
*e
;
753 U_ASSERT(hash
!= NULL
);
754 if (hash
->count
!= 0) {
755 while ((e
= uhash_nextElement(hash
, &pos
)) != NULL
) {
756 uhash_removeElement(hash
, e
);
759 U_ASSERT(hash
->count
== 0);
762 U_CAPI
const UHashElement
* U_EXPORT2
763 uhash_find(const UHashtable
*hash
, const void* key
) {
765 const UHashElement
*e
;
766 keyholder
.pointer
= (void*) key
;
767 e
= _uhash_find(hash
, keyholder
, hash
->keyHasher(keyholder
));
768 return IS_EMPTY_OR_DELETED(e
->hashcode
) ? NULL
: e
;
771 U_CAPI
const UHashElement
* U_EXPORT2
772 uhash_nextElement(const UHashtable
*hash
, int32_t *pos
) {
773 /* Walk through the array until we find an element that is not
774 * EMPTY and not DELETED.
777 U_ASSERT(hash
!= NULL
);
778 for (i
= *pos
+ 1; i
< hash
->length
; ++i
) {
779 if (!IS_EMPTY_OR_DELETED(hash
->elements
[i
].hashcode
)) {
781 return &(hash
->elements
[i
]);
785 /* No more elements */
789 U_CAPI
void* U_EXPORT2
790 uhash_removeElement(UHashtable
*hash
, const UHashElement
* e
) {
791 U_ASSERT(hash
!= NULL
);
793 if (!IS_EMPTY_OR_DELETED(e
->hashcode
)) {
794 return _uhash_internalRemoveElement(hash
, (UHashElement
*) e
).pointer
;
799 /********************************************************************
800 * UHashTok convenience
801 ********************************************************************/
804 * Return a UHashTok for an integer.
806 /*U_CAPI UHashTok U_EXPORT2
807 uhash_toki(int32_t i) {
814 * Return a UHashTok for a pointer.
816 /*U_CAPI UHashTok U_EXPORT2
817 uhash_tokp(void* p) {
823 /********************************************************************
824 * PUBLIC Key Hash Functions
825 ********************************************************************/
828 Compute the hash by iterating sparsely over about 32 (up to 63)
829 characters spaced evenly through the string. For each character,
830 multiply the previous hash value by a prime number and add the new
831 character in, like a linear congruential random number generator,
832 producing a pseudorandom deterministic value well distributed over
833 the output range. [LIU]
836 #define STRING_HASH(TYPE, STR, STRLEN, DEREF) \
838 const TYPE *p = (const TYPE*) STR; \
840 int32_t len = (int32_t)(STRLEN); \
841 int32_t inc = ((len - 32) / 32) + 1; \
842 const TYPE *limit = p + len; \
844 hash = (hash * 37) + DEREF; \
850 U_CAPI
int32_t U_EXPORT2
851 uhash_hashUChars(const UHashTok key
) {
852 STRING_HASH(UChar
, key
.pointer
, u_strlen(p
), *p
);
855 /* Used by UnicodeString to compute its hashcode - Not public API. */
856 U_CAPI
int32_t U_EXPORT2
857 uhash_hashUCharsN(const UChar
*str
, int32_t length
) {
858 STRING_HASH(UChar
, str
, length
, *p
);
861 U_CAPI
int32_t U_EXPORT2
862 uhash_hashChars(const UHashTok key
) {
863 STRING_HASH(uint8_t, key
.pointer
, uprv_strlen((char*)p
), *p
);
866 U_CAPI
int32_t U_EXPORT2
867 uhash_hashIChars(const UHashTok key
) {
868 STRING_HASH(uint8_t, key
.pointer
, uprv_strlen((char*)p
), uprv_tolower(*p
));
871 U_CAPI UBool U_EXPORT2
872 uhash_equals(const UHashtable
* hash1
, const UHashtable
* hash2
){
874 int32_t count1
, count2
, pos
, i
;
881 * Make sure that we are comparing 2 valid hashes of the same type
882 * with valid comparison functions.
883 * Without valid comparison functions, a binary comparison
884 * of the hash values will yield random results on machines
885 * with 64-bit pointers and 32-bit integer hashes.
886 * A valueComparator is normally optional.
888 if (hash1
==NULL
|| hash2
==NULL
||
889 hash1
->keyComparator
!= hash2
->keyComparator
||
890 hash1
->valueComparator
!= hash2
->valueComparator
||
891 hash1
->valueComparator
== NULL
)
894 Normally we would return an error here about incompatible hash tables,
895 but we return FALSE instead.
900 count1
= uhash_count(hash1
);
901 count2
= uhash_count(hash2
);
907 for(i
=0; i
<count1
; i
++){
908 const UHashElement
* elem1
= uhash_nextElement(hash1
, &pos
);
909 const UHashTok key1
= elem1
->key
;
910 const UHashTok val1
= elem1
->value
;
911 /* here the keys are not compared, instead the key form hash1 is used to fetch
912 * value from hash2. If the hashes are equal then then both hashes should
913 * contain equal values for the same key!
915 const UHashElement
* elem2
= _uhash_find(hash2
, key1
, hash2
->keyHasher(key1
));
916 const UHashTok val2
= elem2
->value
;
917 if(hash1
->valueComparator(val1
, val2
)==FALSE
){
924 /********************************************************************
925 * PUBLIC Comparator Functions
926 ********************************************************************/
928 U_CAPI UBool U_EXPORT2
929 uhash_compareUChars(const UHashTok key1
, const UHashTok key2
) {
930 const UChar
*p1
= (const UChar
*) key1
.pointer
;
931 const UChar
*p2
= (const UChar
*) key2
.pointer
;
935 if (p1
== NULL
|| p2
== NULL
) {
938 while (*p1
!= 0 && *p1
== *p2
) {
942 return (UBool
)(*p1
== *p2
);
945 U_CAPI UBool U_EXPORT2
946 uhash_compareChars(const UHashTok key1
, const UHashTok key2
) {
947 const char *p1
= (const char*) key1
.pointer
;
948 const char *p2
= (const char*) key2
.pointer
;
952 if (p1
== NULL
|| p2
== NULL
) {
955 while (*p1
!= 0 && *p1
== *p2
) {
959 return (UBool
)(*p1
== *p2
);
962 U_CAPI UBool U_EXPORT2
963 uhash_compareIChars(const UHashTok key1
, const UHashTok key2
) {
964 const char *p1
= (const char*) key1
.pointer
;
965 const char *p2
= (const char*) key2
.pointer
;
969 if (p1
== NULL
|| p2
== NULL
) {
972 while (*p1
!= 0 && uprv_tolower(*p1
) == uprv_tolower(*p2
)) {
976 return (UBool
)(*p1
== *p2
);
979 /********************************************************************
980 * PUBLIC int32_t Support Functions
981 ********************************************************************/
983 U_CAPI
int32_t U_EXPORT2
984 uhash_hashLong(const UHashTok key
) {
988 U_CAPI UBool U_EXPORT2
989 uhash_compareLong(const UHashTok key1
, const UHashTok key2
) {
990 return (UBool
)(key1
.integer
== key2
.integer
);
993 /********************************************************************
994 * PUBLIC Deleter Functions
995 ********************************************************************/
997 U_CAPI
void U_EXPORT2
998 uhash_freeBlock(void *obj
) {