Line data Source code
1 : // © 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
143 9 : _uhash_setElement(UHashtable *hash, UHashElement* e,
144 : int32_t hashcode,
145 : UHashTok key, UHashTok value, int8_t hint) {
146 :
147 9 : UHashTok oldValue = e->value;
148 9 : if (hash->keyDeleter != NULL && e->key.pointer != NULL &&
149 0 : e->key.pointer != key.pointer) { /* Avoid double deletion */
150 0 : (*hash->keyDeleter)(e->key.pointer);
151 : }
152 9 : if (hash->valueDeleter != NULL) {
153 8 : if (oldValue.pointer != NULL &&
154 0 : oldValue.pointer != value.pointer) { /* Avoid double deletion */
155 0 : (*hash->valueDeleter)(oldValue.pointer);
156 : }
157 8 : 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 9 : if (hint & HINT_KEY_POINTER) {
166 9 : e->key.pointer = key.pointer;
167 : } else {
168 0 : e->key = key;
169 : }
170 9 : if (hint & HINT_VALUE_POINTER) {
171 9 : e->value.pointer = value.pointer;
172 : } else {
173 0 : e->value = value;
174 : }
175 9 : e->hashcode = hashcode;
176 9 : return oldValue;
177 : }
178 :
179 : /**
180 : * Assumes that the given element is not empty or deleted.
181 : */
182 : static UHashTok
183 0 : _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) {
184 : UHashTok empty;
185 0 : U_ASSERT(!IS_EMPTY_OR_DELETED(e->hashcode));
186 0 : --hash->count;
187 0 : empty.pointer = NULL; empty.integer = 0;
188 0 : return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0);
189 : }
190 :
191 : static void
192 9 : _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
193 9 : U_ASSERT(hash != NULL);
194 9 : U_ASSERT(((int32_t)policy) >= 0);
195 9 : U_ASSERT(((int32_t)policy) < 3);
196 9 : hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2];
197 9 : hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1];
198 9 : }
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
210 9 : _uhash_allocate(UHashtable *hash,
211 : int32_t primeIndex,
212 : UErrorCode *status) {
213 :
214 : UHashElement *p, *limit;
215 : UHashTok emptytok;
216 :
217 9 : if (U_FAILURE(*status)) return;
218 :
219 9 : U_ASSERT(primeIndex >= 0 && primeIndex < PRIMES_LENGTH);
220 :
221 9 : hash->primeIndex = primeIndex;
222 9 : hash->length = PRIMES[primeIndex];
223 :
224 9 : p = hash->elements = (UHashElement*)
225 9 : uprv_malloc(sizeof(UHashElement) * hash->length);
226 :
227 9 : if (hash->elements == NULL) {
228 0 : *status = U_MEMORY_ALLOCATION_ERROR;
229 0 : return;
230 : }
231 :
232 9 : emptytok.pointer = NULL; /* Only one of these two is needed */
233 9 : emptytok.integer = 0; /* but we don't know which one. */
234 :
235 9 : limit = p + hash->length;
236 2295 : while (p < limit) {
237 1143 : p->key = emptytok;
238 1143 : p->value = emptytok;
239 1143 : p->hashcode = HASH_EMPTY;
240 1143 : ++p;
241 : }
242 :
243 9 : hash->count = 0;
244 9 : hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
245 9 : hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
246 : }
247 :
248 : static UHashtable*
249 9 : _uhash_init(UHashtable *result,
250 : UHashFunction *keyHash,
251 : UKeyComparator *keyComp,
252 : UValueComparator *valueComp,
253 : int32_t primeIndex,
254 : UErrorCode *status)
255 : {
256 9 : if (U_FAILURE(*status)) return NULL;
257 9 : U_ASSERT(keyHash != NULL);
258 9 : U_ASSERT(keyComp != NULL);
259 :
260 9 : result->keyHasher = keyHash;
261 9 : result->keyComparator = keyComp;
262 9 : result->valueComparator = valueComp;
263 9 : result->keyDeleter = NULL;
264 9 : result->valueDeleter = NULL;
265 9 : result->allocated = FALSE;
266 9 : _uhash_internalSetResizePolicy(result, U_GROW);
267 :
268 9 : _uhash_allocate(result, primeIndex, status);
269 :
270 9 : if (U_FAILURE(*status)) {
271 0 : return NULL;
272 : }
273 :
274 9 : return result;
275 : }
276 :
277 : static UHashtable*
278 9 : _uhash_create(UHashFunction *keyHash,
279 : UKeyComparator *keyComp,
280 : UValueComparator *valueComp,
281 : int32_t primeIndex,
282 : UErrorCode *status) {
283 : UHashtable *result;
284 :
285 9 : if (U_FAILURE(*status)) return NULL;
286 :
287 9 : result = (UHashtable*) uprv_malloc(sizeof(UHashtable));
288 9 : if (result == NULL) {
289 0 : *status = U_MEMORY_ALLOCATION_ERROR;
290 0 : return NULL;
291 : }
292 :
293 9 : _uhash_init(result, keyHash, keyComp, valueComp, primeIndex, status);
294 9 : result->allocated = TRUE;
295 :
296 9 : if (U_FAILURE(*status)) {
297 0 : uprv_free(result);
298 0 : return NULL;
299 : }
300 :
301 9 : 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*
333 28 : _uhash_find(const UHashtable *hash, UHashTok key,
334 : int32_t hashcode) {
335 :
336 28 : int32_t firstDeleted = -1; /* assume invalid index */
337 : int32_t theIndex, startIndex;
338 28 : int32_t jump = 0; /* lazy evaluate */
339 : int32_t tableHash;
340 28 : UHashElement *elements = hash->elements;
341 :
342 28 : hashcode &= 0x7FFFFFFF; /* must be positive */
343 28 : startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length;
344 :
345 0 : do {
346 28 : tableHash = elements[theIndex].hashcode;
347 28 : if (tableHash == hashcode) { /* quick check */
348 6 : if ((*hash->keyComparator)(key, elements[theIndex].key)) {
349 6 : return &(elements[theIndex]);
350 : }
351 22 : } 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 22 : } else if (tableHash == HASH_EMPTY) { /* empty, end o' the line */
357 22 : break;
358 0 : } else if (firstDeleted < 0) { /* remember first deleted */
359 0 : firstDeleted = theIndex;
360 : }
361 0 : 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 0 : jump = (hashcode % (hash->length - 1)) + 1;
367 : }
368 0 : theIndex = (theIndex + jump) % hash->length;
369 0 : } while (theIndex != startIndex);
370 :
371 22 : if (firstDeleted >= 0) {
372 0 : theIndex = firstDeleted; /* reset if had deleted slot */
373 22 : } 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 0 : U_ASSERT(FALSE);
380 : return NULL; /* Never happens if uhash_put() behaves */
381 : }
382 22 : 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
395 0 : _uhash_rehash(UHashtable *hash, UErrorCode *status) {
396 :
397 0 : UHashElement *old = hash->elements;
398 0 : int32_t oldLength = hash->length;
399 0 : int32_t newPrimeIndex = hash->primeIndex;
400 : int32_t i;
401 :
402 0 : if (hash->count > hash->highWaterMark) {
403 0 : if (++newPrimeIndex >= PRIMES_LENGTH) {
404 0 : return;
405 : }
406 0 : } else if (hash->count < hash->lowWaterMark) {
407 0 : if (--newPrimeIndex < 0) {
408 0 : return;
409 : }
410 : } else {
411 0 : return;
412 : }
413 :
414 0 : _uhash_allocate(hash, newPrimeIndex, status);
415 :
416 0 : if (U_FAILURE(*status)) {
417 0 : hash->elements = old;
418 0 : hash->length = oldLength;
419 0 : return;
420 : }
421 :
422 0 : for (i = oldLength - 1; i >= 0; --i) {
423 0 : if (!IS_EMPTY_OR_DELETED(old[i].hashcode)) {
424 0 : UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode);
425 0 : U_ASSERT(e != NULL);
426 0 : U_ASSERT(e->hashcode == HASH_EMPTY);
427 0 : e->key = old[i].key;
428 0 : e->value = old[i].value;
429 0 : e->hashcode = old[i].hashcode;
430 0 : ++hash->count;
431 : }
432 : }
433 :
434 0 : uprv_free(old);
435 : }
436 :
437 : static UHashTok
438 0 : _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 0 : UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key));
449 0 : U_ASSERT(e != NULL);
450 0 : result.pointer = NULL;
451 0 : result.integer = 0;
452 0 : if (!IS_EMPTY_OR_DELETED(e->hashcode)) {
453 0 : result = _uhash_internalRemoveElement(hash, e);
454 0 : if (hash->count < hash->lowWaterMark) {
455 0 : UErrorCode status = U_ZERO_ERROR;
456 0 : _uhash_rehash(hash, &status);
457 : }
458 : }
459 0 : return result;
460 : }
461 :
462 : static UHashTok
463 9 : _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 9 : if (U_FAILURE(*status)) {
479 0 : goto err;
480 : }
481 9 : U_ASSERT(hash != NULL);
482 : /* Cannot always check pointer here or iSeries sees NULL every time. */
483 9 : 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 0 : return _uhash_remove(hash, key);
488 : }
489 9 : if (hash->count > hash->highWaterMark) {
490 0 : _uhash_rehash(hash, status);
491 0 : if (U_FAILURE(*status)) {
492 0 : goto err;
493 : }
494 : }
495 :
496 9 : hashcode = (*hash->keyHasher)(key);
497 9 : e = _uhash_find(hash, key, hashcode);
498 9 : U_ASSERT(e != NULL);
499 :
500 9 : 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 9 : ++hash->count;
509 9 : if (hash->count == hash->length) {
510 : /* Don't allow count to reach length */
511 0 : --hash->count;
512 0 : *status = U_MEMORY_ALLOCATION_ERROR;
513 0 : 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 9 : 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 0 : HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer);
529 0 : emptytok.pointer = NULL; emptytok.integer = 0;
530 0 : return emptytok;
531 : }
532 :
533 :
534 : /********************************************************************
535 : * PUBLIC API
536 : ********************************************************************/
537 :
538 : U_CAPI UHashtable* U_EXPORT2
539 9 : uhash_open(UHashFunction *keyHash,
540 : UKeyComparator *keyComp,
541 : UValueComparator *valueComp,
542 : UErrorCode *status) {
543 :
544 9 : return _uhash_create(keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status);
545 : }
546 :
547 : U_CAPI UHashtable* U_EXPORT2
548 0 : 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 0 : int32_t i = 0;
556 0 : while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) {
557 0 : ++i;
558 : }
559 :
560 0 : return _uhash_create(keyHash, keyComp, valueComp, i, status);
561 : }
562 :
563 : U_CAPI UHashtable* U_EXPORT2
564 0 : uhash_init(UHashtable *fillinResult,
565 : UHashFunction *keyHash,
566 : UKeyComparator *keyComp,
567 : UValueComparator *valueComp,
568 : UErrorCode *status) {
569 :
570 0 : return _uhash_init(fillinResult, keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status);
571 : }
572 :
573 : U_CAPI void U_EXPORT2
574 0 : uhash_close(UHashtable *hash) {
575 0 : if (hash == NULL) {
576 0 : return;
577 : }
578 0 : if (hash->elements != NULL) {
579 0 : if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) {
580 0 : int32_t pos=UHASH_FIRST;
581 : UHashElement *e;
582 0 : while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) {
583 0 : HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer);
584 : }
585 : }
586 0 : uprv_free(hash->elements);
587 0 : hash->elements = NULL;
588 : }
589 0 : if (hash->allocated) {
590 0 : uprv_free(hash);
591 : }
592 : }
593 :
594 : U_CAPI UHashFunction *U_EXPORT2
595 0 : uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) {
596 0 : UHashFunction *result = hash->keyHasher;
597 0 : hash->keyHasher = fn;
598 0 : return result;
599 : }
600 :
601 : U_CAPI UKeyComparator *U_EXPORT2
602 0 : uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) {
603 0 : UKeyComparator *result = hash->keyComparator;
604 0 : hash->keyComparator = fn;
605 0 : return result;
606 : }
607 : U_CAPI UValueComparator *U_EXPORT2
608 0 : uhash_setValueComparator(UHashtable *hash, UValueComparator *fn){
609 0 : UValueComparator *result = hash->valueComparator;
610 0 : hash->valueComparator = fn;
611 0 : return result;
612 : }
613 :
614 : U_CAPI UObjectDeleter *U_EXPORT2
615 3 : uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) {
616 3 : UObjectDeleter *result = hash->keyDeleter;
617 3 : hash->keyDeleter = fn;
618 3 : return result;
619 : }
620 :
621 : U_CAPI UObjectDeleter *U_EXPORT2
622 8 : uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) {
623 8 : UObjectDeleter *result = hash->valueDeleter;
624 8 : hash->valueDeleter = fn;
625 8 : return result;
626 : }
627 :
628 : U_CAPI void U_EXPORT2
629 0 : uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
630 0 : UErrorCode status = U_ZERO_ERROR;
631 0 : _uhash_internalSetResizePolicy(hash, policy);
632 0 : hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
633 0 : hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
634 0 : _uhash_rehash(hash, &status);
635 0 : }
636 :
637 : U_CAPI int32_t U_EXPORT2
638 0 : uhash_count(const UHashtable *hash) {
639 0 : return hash->count;
640 : }
641 :
642 : U_CAPI void* U_EXPORT2
643 19 : uhash_get(const UHashtable *hash,
644 : const void* key) {
645 : UHashTok keyholder;
646 19 : keyholder.pointer = (void*) key;
647 19 : return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;
648 : }
649 :
650 : U_CAPI void* U_EXPORT2
651 0 : uhash_iget(const UHashtable *hash,
652 : int32_t key) {
653 : UHashTok keyholder;
654 0 : keyholder.integer = key;
655 0 : return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;
656 : }
657 :
658 : U_CAPI int32_t U_EXPORT2
659 0 : uhash_geti(const UHashtable *hash,
660 : const void* key) {
661 : UHashTok keyholder;
662 0 : keyholder.pointer = (void*) key;
663 0 : return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;
664 : }
665 :
666 : U_CAPI int32_t U_EXPORT2
667 0 : uhash_igeti(const UHashtable *hash,
668 : int32_t key) {
669 : UHashTok keyholder;
670 0 : keyholder.integer = key;
671 0 : return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;
672 : }
673 :
674 : U_CAPI void* U_EXPORT2
675 9 : uhash_put(UHashtable *hash,
676 : void* key,
677 : void* value,
678 : UErrorCode *status) {
679 : UHashTok keyholder, valueholder;
680 9 : keyholder.pointer = key;
681 9 : valueholder.pointer = value;
682 9 : return _uhash_put(hash, keyholder, valueholder,
683 : HINT_KEY_POINTER | HINT_VALUE_POINTER,
684 9 : status).pointer;
685 : }
686 :
687 : U_CAPI void* U_EXPORT2
688 0 : uhash_iput(UHashtable *hash,
689 : int32_t key,
690 : void* value,
691 : UErrorCode *status) {
692 : UHashTok keyholder, valueholder;
693 0 : keyholder.integer = key;
694 0 : valueholder.pointer = value;
695 0 : return _uhash_put(hash, keyholder, valueholder,
696 : HINT_VALUE_POINTER,
697 0 : status).pointer;
698 : }
699 :
700 : U_CAPI int32_t U_EXPORT2
701 0 : uhash_puti(UHashtable *hash,
702 : void* key,
703 : int32_t value,
704 : UErrorCode *status) {
705 : UHashTok keyholder, valueholder;
706 0 : keyholder.pointer = key;
707 0 : valueholder.integer = value;
708 0 : return _uhash_put(hash, keyholder, valueholder,
709 : HINT_KEY_POINTER,
710 0 : status).integer;
711 : }
712 :
713 :
714 : U_CAPI int32_t U_EXPORT2
715 0 : uhash_iputi(UHashtable *hash,
716 : int32_t key,
717 : int32_t value,
718 : UErrorCode *status) {
719 : UHashTok keyholder, valueholder;
720 0 : keyholder.integer = key;
721 0 : valueholder.integer = value;
722 0 : return _uhash_put(hash, keyholder, valueholder,
723 : 0, /* neither is a ptr */
724 0 : status).integer;
725 : }
726 :
727 : U_CAPI void* U_EXPORT2
728 0 : uhash_remove(UHashtable *hash,
729 : const void* key) {
730 : UHashTok keyholder;
731 0 : keyholder.pointer = (void*) key;
732 0 : return _uhash_remove(hash, keyholder).pointer;
733 : }
734 :
735 : U_CAPI void* U_EXPORT2
736 0 : uhash_iremove(UHashtable *hash,
737 : int32_t key) {
738 : UHashTok keyholder;
739 0 : keyholder.integer = key;
740 0 : return _uhash_remove(hash, keyholder).pointer;
741 : }
742 :
743 : U_CAPI int32_t U_EXPORT2
744 0 : uhash_removei(UHashtable *hash,
745 : const void* key) {
746 : UHashTok keyholder;
747 0 : keyholder.pointer = (void*) key;
748 0 : return _uhash_remove(hash, keyholder).integer;
749 : }
750 :
751 : U_CAPI int32_t U_EXPORT2
752 0 : uhash_iremovei(UHashtable *hash,
753 : int32_t key) {
754 : UHashTok keyholder;
755 0 : keyholder.integer = key;
756 0 : return _uhash_remove(hash, keyholder).integer;
757 : }
758 :
759 : U_CAPI void U_EXPORT2
760 0 : uhash_removeAll(UHashtable *hash) {
761 0 : int32_t pos = UHASH_FIRST;
762 : const UHashElement *e;
763 0 : U_ASSERT(hash != NULL);
764 0 : if (hash->count != 0) {
765 0 : while ((e = uhash_nextElement(hash, &pos)) != NULL) {
766 0 : uhash_removeElement(hash, e);
767 : }
768 : }
769 0 : U_ASSERT(hash->count == 0);
770 0 : }
771 :
772 : U_CAPI const UHashElement* U_EXPORT2
773 0 : uhash_find(const UHashtable *hash, const void* key) {
774 : UHashTok keyholder;
775 : const UHashElement *e;
776 0 : keyholder.pointer = (void*) key;
777 0 : e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));
778 0 : return IS_EMPTY_OR_DELETED(e->hashcode) ? NULL : e;
779 : }
780 :
781 : U_CAPI const UHashElement* U_EXPORT2
782 0 : 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 0 : U_ASSERT(hash != NULL);
788 0 : for (i = *pos + 1; i < hash->length; ++i) {
789 0 : if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) {
790 0 : *pos = i;
791 0 : return &(hash->elements[i]);
792 : }
793 : }
794 :
795 : /* No more elements */
796 0 : return NULL;
797 : }
798 :
799 : U_CAPI void* U_EXPORT2
800 0 : uhash_removeElement(UHashtable *hash, const UHashElement* e) {
801 0 : U_ASSERT(hash != NULL);
802 0 : U_ASSERT(e != NULL);
803 0 : if (!IS_EMPTY_OR_DELETED(e->hashcode)) {
804 0 : UHashElement *nce = (UHashElement *)e;
805 0 : return _uhash_internalRemoveElement(hash, nce).pointer;
806 : }
807 0 : 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
839 0 : uhash_hashUChars(const UHashTok key) {
840 0 : const UChar *s = (const UChar *)key.pointer;
841 0 : return s == NULL ? 0 : ustr_hashUCharsN(s, u_strlen(s));
842 : }
843 :
844 : U_CAPI int32_t U_EXPORT2
845 34 : uhash_hashChars(const UHashTok key) {
846 34 : const char *s = (const char *)key.pointer;
847 34 : return s == NULL ? 0 : ustr_hashCharsN(s, uprv_strlen(s));
848 : }
849 :
850 : U_CAPI int32_t U_EXPORT2
851 0 : uhash_hashIChars(const UHashTok key) {
852 0 : const char *s = (const char *)key.pointer;
853 0 : return s == NULL ? 0 : ustr_hashICharsN(s, uprv_strlen(s));
854 : }
855 :
856 : U_CAPI UBool U_EXPORT2
857 0 : uhash_equals(const UHashtable* hash1, const UHashtable* hash2){
858 : int32_t count1, count2, pos, i;
859 :
860 0 : if(hash1==hash2){
861 0 : 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 0 : if (hash1==NULL || hash2==NULL ||
873 0 : hash1->keyComparator != hash2->keyComparator ||
874 0 : hash1->valueComparator != hash2->valueComparator ||
875 0 : 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 0 : return FALSE;
882 : }
883 :
884 0 : count1 = uhash_count(hash1);
885 0 : count2 = uhash_count(hash2);
886 0 : if(count1!=count2){
887 0 : return FALSE;
888 : }
889 :
890 0 : pos=UHASH_FIRST;
891 0 : for(i=0; i<count1; i++){
892 0 : const UHashElement* elem1 = uhash_nextElement(hash1, &pos);
893 0 : const UHashTok key1 = elem1->key;
894 0 : 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 0 : const UHashElement* elem2 = _uhash_find(hash2, key1, hash2->keyHasher(key1));
900 0 : const UHashTok val2 = elem2->value;
901 0 : if(hash1->valueComparator(val1, val2)==FALSE){
902 0 : return FALSE;
903 : }
904 : }
905 0 : return TRUE;
906 : }
907 :
908 : /********************************************************************
909 : * PUBLIC Comparator Functions
910 : ********************************************************************/
911 :
912 : U_CAPI UBool U_EXPORT2
913 0 : uhash_compareUChars(const UHashTok key1, const UHashTok key2) {
914 0 : const UChar *p1 = (const UChar*) key1.pointer;
915 0 : const UChar *p2 = (const UChar*) key2.pointer;
916 0 : if (p1 == p2) {
917 0 : return TRUE;
918 : }
919 0 : if (p1 == NULL || p2 == NULL) {
920 0 : return FALSE;
921 : }
922 0 : while (*p1 != 0 && *p1 == *p2) {
923 0 : ++p1;
924 0 : ++p2;
925 : }
926 0 : return (UBool)(*p1 == *p2);
927 : }
928 :
929 : U_CAPI UBool U_EXPORT2
930 9 : uhash_compareChars(const UHashTok key1, const UHashTok key2) {
931 9 : const char *p1 = (const char*) key1.pointer;
932 9 : const char *p2 = (const char*) key2.pointer;
933 9 : if (p1 == p2) {
934 3 : return TRUE;
935 : }
936 6 : if (p1 == NULL || p2 == NULL) {
937 0 : return FALSE;
938 : }
939 132 : while (*p1 != 0 && *p1 == *p2) {
940 63 : ++p1;
941 63 : ++p2;
942 : }
943 6 : return (UBool)(*p1 == *p2);
944 : }
945 :
946 : U_CAPI UBool U_EXPORT2
947 0 : uhash_compareIChars(const UHashTok key1, const UHashTok key2) {
948 0 : const char *p1 = (const char*) key1.pointer;
949 0 : const char *p2 = (const char*) key2.pointer;
950 0 : if (p1 == p2) {
951 0 : return TRUE;
952 : }
953 0 : if (p1 == NULL || p2 == NULL) {
954 0 : return FALSE;
955 : }
956 0 : while (*p1 != 0 && uprv_tolower(*p1) == uprv_tolower(*p2)) {
957 0 : ++p1;
958 0 : ++p2;
959 : }
960 0 : return (UBool)(*p1 == *p2);
961 : }
962 :
963 : /********************************************************************
964 : * PUBLIC int32_t Support Functions
965 : ********************************************************************/
966 :
967 : U_CAPI int32_t U_EXPORT2
968 0 : uhash_hashLong(const UHashTok key) {
969 0 : return key.integer;
970 : }
971 :
972 : U_CAPI UBool U_EXPORT2
973 0 : uhash_compareLong(const UHashTok key1, const UHashTok key2) {
974 0 : return (UBool)(key1.integer == key2.integer);
975 : }
|
