Coverage Report

Created: 2025-06-13 06:34

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