2
******************************************************************************
3
* Copyright (C) 1997-2001, 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
******************************************************************************
16
#include "unicode/utypes.h"
19
* UHashtable stores key-value pairs and does moderately fast lookup
20
* based on keys. It provides a good tradeoff between access time and
21
* storage space. As elements are added to it, it grows to accomodate
22
* them. By default, the table never shrinks, even if all elements
23
* are removed from it.
25
* Keys and values are stored as void* pointers. These void* pointers
26
* may be actual pointers to strings, objects, or any other structure
27
* in memory, or they may simply be integral values cast to void*.
28
* UHashtable doesn't care and manipulates them via user-supplied
29
* functions. These functions hash keys, compare keys, delete keys,
30
* and delete values. Some function pointers are optional (may be
31
* NULL); others must be supplied. Several prebuilt functions exist
32
* to handle common key types.
34
* UHashtable ownership of keys and values is flexible, and controlled
35
* by whether or not the key deleter and value deleter functions are
36
* set. If a void* key is actually a pointer to a deletable object,
37
* then UHashtable can be made to delete that object by setting the
38
* key deleter function pointer to a non-NULL value. If this is done,
39
* then keys passed to uhash_put() are owned by the hashtable and will
40
* be deleted by it at some point, either as keys are replaced, or
41
* when uhash_close() is finally called. The same is true of values
42
* and the value deleter function pointer. Keys passed to methods
43
* other than uhash_put() are never owned by the hashtable.
45
* NULL values are not allowed. uhash_get() returns NULL to indicate
46
* a key that is not in the table, and having a NULL value in the
47
* table would generate an ambiguous result. If a key and a NULL
48
* value is passed to uhash_put(), this has the effect of doing a
49
* uhash_remove() on that key. This keeps uhash_get(), uhash_count(),
50
* and uhash_nextElement() consistent with one another.
52
* To see everything in a hashtable, use uhash_nextElement() to
53
* iterate through its contents. Each call to this function returns a
54
* UHashElement pointer. A hash element contains a key, value, and
55
* hashcode. During iteration an element may be deleted by calling
56
* uhash_removeElement(); iteration may safely continue thereafter.
57
* The uhash_remove() function may also be safely called in
58
* mid-iteration. However, if uhash_put() is called during iteration
59
* then the iteration will be out of sync. Under no circumstances
60
* should the UHashElement returned by uhash_nextElement be modified
63
* By default, the hashtable grows when necessary, but never shrinks,
64
* even if all items are removed. For most applications this is
65
* optimal. However, in a highly dynamic usage where memory is at a
66
* premium, the table can be set to both grow and shrink by calling
67
* uhash_setResizePolicy() with the policy U_GROW_AND_SHRINK. In a
68
* situation where memory is critical and the client wants a table
69
* that does not grow at all, the constant U_FIXED can be used.
72
/********************************************************************
74
********************************************************************/
79
* A key or value within the hashtable. It may be either a 32-bit
80
* integral value or an opaque void* pointer. The void* pointer may
81
* be smaller than 32 bits (e.g. 24 bits) or may be larger (e.g. 64
82
* bits). The hashing and comparison functions take a pointer to a
83
* UHashTok, but the deleter receives the void* pointer within it.
85
* Because a UHashTok is the size of a native pointer or a 32-bit
86
* integer, we pass it around by value.
92
typedef union UHashTok UHashTok;
95
* This is a single hash element.
98
/* Reorder these elements to pack nicely if necessary */
103
typedef struct UHashElement UHashElement;
106
* A hashing function.
107
* @param key A key stored in a hashtable
108
* @return A NON-NEGATIVE hash code for parm.
110
typedef int32_t (U_EXPORT2 * U_CALLCONV UHashFunction)(const UHashTok key);
113
* A key comparison function.
114
* @param key1 A key stored in a hashtable
115
* @param key2 A key stored in a hashtable
116
* @return TRUE if the two keys are equal.
118
typedef UBool (U_EXPORT2 * U_CALLCONV UKeyComparator)(const UHashTok key1,
119
const UHashTok key2);
122
* A function called by <TT>uhash_remove</TT>,
123
* <TT>uhash_close</TT>, or <TT>uhash_put</TT> to delete
124
* an existing key or value.
125
* @param obj A key or value stored in a hashtable
127
typedef void (U_EXPORT2 * U_CALLCONV UObjectDeleter)(void* obj);
130
* This specifies whether or not, and how, the hastable resizes itself.
131
* See uhash_setResizePolicy().
133
enum UHashResizePolicy {
134
U_GROW, /* Grow on demand, do not shrink */
135
U_GROW_AND_SHRINK, /* Grow and shrink on demand */
136
U_FIXED /* Never change size */
140
* The UHashtable struct. Clients should treat this as an opaque data
141
* type and manipulate it only through the uhash_... API.
145
/* Main key-value pair storage array */
147
UHashElement *elements;
149
/* Size parameters */
151
int32_t count; /* The number of key-value pairs in this table.
152
* 0 <= count <= length. In practice we
153
* never let count == length (see code). */
154
int32_t length; /* The physical size of the arrays hashes, keys
155
* and values. Must be prime. */
156
int32_t primeIndex; /* Index into our prime table for length.
157
* length == PRIMES[primeIndex] */
159
/* Rehashing thresholds */
161
int32_t highWaterMark; /* If count > highWaterMark, rehash */
162
int32_t lowWaterMark; /* If count < lowWaterMark, rehash */
163
float highWaterRatio; /* 0..1; high water as a fraction of length */
164
float lowWaterRatio; /* 0..1; low water as a fraction of length */
166
/* Function pointers */
168
UHashFunction keyHasher; /* Computes hash from key.
170
UKeyComparator keyComparator; /* Compares keys for equality.
172
UObjectDeleter keyDeleter; /* Deletes keys when required.
173
* If NULL won't do anything */
174
UObjectDeleter valueDeleter; /* Deletes values when required.
175
* If NULL won't do anything */
177
typedef struct UHashtable UHashtable;
181
/********************************************************************
183
********************************************************************/
186
* Initialize a new UHashtable.
187
* @param keyHash A pointer to the key hashing function. Must not be
189
* @param keyComp A pointer to the function that compares keys. Must
191
* @param status A pointer to an UErrorCode to receive any errors.
192
* @return A pointer to a UHashtable, or 0 if an error occurred.
193
* @see uhash_openSize
195
U_CAPI UHashtable* U_EXPORT2
196
uhash_open(UHashFunction keyHash,
197
UKeyComparator keyComp,
201
* Initialize a new UHashtable with a given initial size.
202
* @param keyHash A pointer to the key hashing function. Must not be
204
* @param keyComp A pointer to the function that compares keys. Must
206
* @param size The initial capacity of this hash table.
207
* @param status A pointer to an UErrorCode to receive any errors.
208
* @return A pointer to a UHashtable, or 0 if an error occurred.
211
U_CAPI UHashtable* U_EXPORT2
212
uhash_openSize(UHashFunction keyHash,
213
UKeyComparator keyComp,
218
* Close a UHashtable, releasing the memory used.
219
* @param hash The UHashtable to close.
221
U_CAPI void U_EXPORT2
222
uhash_close(UHashtable *hash);
227
* Set the function used to hash keys.
228
* @param fn the function to be used hash keys; must not be NULL
229
* @return the previous key hasher; non-NULL
231
U_CAPI UHashFunction U_EXPORT2
232
uhash_setKeyHasher(UHashtable *hash, UHashFunction fn);
235
* Set the function used to compare keys. The default comparison is a
236
* void* pointer comparison.
237
* @param fn the function to be used compare keys; must not be NULL
238
* @return the previous key comparator; non-NULL
240
U_CAPI UKeyComparator U_EXPORT2
241
uhash_setKeyComparator(UHashtable *hash, UKeyComparator fn);
244
* Set the function used to delete keys. If this function pointer is
245
* NULL, this hashtable does not delete keys. If it is non-NULL, this
246
* hashtable does delete keys. This function should be set once
247
* before any elements are added to the hashtable and should not be
248
* changed thereafter.
249
* @param fn the function to be used delete keys, or NULL
250
* @return the previous key deleter; may be NULL
252
U_CAPI UObjectDeleter U_EXPORT2
253
uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter fn);
256
* Set the function used to delete values. If this function pointer
257
* is NULL, this hashtable does not delete values. If it is non-NULL,
258
* this hashtable does delete values. This function should be set
259
* once before any elements are added to the hashtable and should not
260
* be changed thereafter.
261
* @param fn the function to be used delete values, or NULL
262
* @return the previous value deleter; may be NULL
264
U_CAPI UObjectDeleter U_EXPORT2
265
uhash_setValueDeleter(UHashtable *hash, UObjectDeleter fn);
268
* Specify whether or not, and how, the hastable resizes itself.
269
* By default, tables grow but do not shrink (policy U_GROW).
270
* See enum UHashResizePolicy.
272
U_CAPI void U_EXPORT2
273
uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy);
276
* Get the number of key-value pairs stored in a UHashtable.
277
* @param hash The UHashtable to query.
278
* @return The number of key-value pairs stored in hash.
280
U_CAPI int32_t U_EXPORT2
281
uhash_count(const UHashtable *hash);
284
* Put a (key=pointer, value=pointer) item in a UHashtable. If the
285
* keyDeleter is non-NULL, then the hashtable owns 'key' after this
286
* call. If the valueDeleter is non-NULL, then the hashtable owns
287
* 'value' after this call. Storing a NULL value is the same as
288
* calling uhash_remove().
289
* @param hash The target UHashtable.
290
* @param key The key to store.
291
* @param value The value to store, may be NULL (see above).
292
* @param status A pointer to an UErrorCode to receive any errors.
293
* @return The previous value, or NULL if none.
296
U_CAPI void* U_EXPORT2
297
uhash_put(UHashtable *hash,
303
* Put a (key=integer, value=pointer) item in a UHashtable.
304
* keyDeleter must be NULL. If the valueDeleter is non-NULL, then the
305
* hashtable owns 'value' after this call. Storing a NULL value is
306
* the same as calling uhash_remove().
307
* @param hash The target UHashtable.
308
* @param key The integer key to store.
309
* @param value The value to store, may be NULL (see above).
310
* @param status A pointer to an UErrorCode to receive any errors.
311
* @return The previous value, or NULL if none.
314
U_CAPI void* U_EXPORT2
315
uhash_iput(UHashtable *hash,
321
* Put a (key=pointer, value=integer) item in a UHashtable. If the
322
* keyDeleter is non-NULL, then the hashtable owns 'key' after this
323
* call. valueDeleter must be NULL. Storing a 0 value is the same as
324
* calling uhash_remove().
325
* @param hash The target UHashtable.
326
* @param key The key to store.
327
* @param value The integer value to store.
328
* @param status A pointer to an UErrorCode to receive any errors.
329
* @return The previous value, or 0 if none.
332
U_CAPI int32_t U_EXPORT2
333
uhash_puti(UHashtable *hash,
339
* Retrieve a pointer value from a UHashtable using a pointer key,
340
* as previously stored by uhash_put().
341
* @param hash The target UHashtable.
342
* @param key A pointer key stored in a hashtable
343
* @return The requested item, or NULL if not found.
345
U_CAPI void* U_EXPORT2
346
uhash_get(const UHashtable *hash,
350
* Retrieve a pointer value from a UHashtable using a integer key,
351
* as previously stored by uhash_iput().
352
* @param hash The target UHashtable.
353
* @param key An integer key stored in a hashtable
354
* @return The requested item, or NULL if not found.
356
U_CAPI void* U_EXPORT2
357
uhash_iget(const UHashtable *hash,
361
* Retrieve an integer value from a UHashtable using a pointer key,
362
* as previously stored by uhash_puti().
363
* @param hash The target UHashtable.
364
* @param key A pointer key stored in a hashtable
365
* @return The requested item, or 0 if not found.
367
U_CAPI int32_t U_EXPORT2
368
uhash_geti(const UHashtable *hash,
372
* Remove an item from a UHashtable stored by uhash_put().
373
* @param hash The target UHashtable.
374
* @param key A key stored in a hashtable
375
* @return The item removed, or NULL if not found.
377
U_CAPI void* U_EXPORT2
378
uhash_remove(UHashtable *hash,
382
* Remove an item from a UHashtable stored by uhash_iput().
383
* @param hash The target UHashtable.
384
* @param key An integer key stored in a hashtable
385
* @return The item removed, or NULL if not found.
387
U_CAPI void* U_EXPORT2
388
uhash_iremove(UHashtable *hash,
392
* Remove an item from a UHashtable stored by uhash_puti().
393
* @param hash The target UHashtable.
394
* @param key An key stored in a hashtable
395
* @return The item removed, or 0 if not found.
397
U_CAPI int32_t U_EXPORT2
398
uhash_removei(UHashtable *hash,
402
* Remove all items from a UHashtable.
403
* @param hash The target UHashtable.
405
U_CAPI void U_EXPORT2
406
uhash_removeAll(UHashtable *hash);
409
* Locate an element of a UHashtable. The caller must not modify the
410
* returned object. The primary use of this function is to obtain the
411
* stored key when it may not be identical to the search key. For
412
* example, if the compare function is a case-insensitive string
413
* compare, then the hash key may be desired in order to obtain the
414
* canonical case corresponding to a search key.
415
* @param hash The target UHashtable.
416
* @param key A key stored in a hashtable
417
* @return a hash element, or NULL if the key is not found.
419
U_CAPI const UHashElement* U_EXPORT2
420
uhash_find(const UHashtable *hash, const void* key);
423
* Iterate through the elements of a UHashtable. The caller must not
424
* modify the returned object. However, uhash_removeElement() may be
425
* called during iteration to remove an element from the table.
426
* Iteration may safely be resumed afterwards. If uhash_put() is
427
* called during iteration the iteration will then be out of sync and
428
* should be restarted.
429
* @param hash The target UHashtable.
430
* @param pos This should be set to -1 initially, and left untouched
432
* @return a hash element, or NULL if no further key-value pairs
433
* exist in the table.
435
U_CAPI const UHashElement* U_EXPORT2
436
uhash_nextElement(const UHashtable *hash,
440
* Remove an element, returned by uhash_nextElement(), from the table.
441
* Iteration may be safely continued afterwards.
442
* @param hash The hashtable
443
* @param e The element, returned by uhash_nextElement(), to remove.
444
* Must not be NULL. Must not be an empty or deleted element (as long
445
* as this was returned by uhash_nextElement() it will not be empty or
446
* deleted). Note: Although this parameter is const, it will be
448
* @return the value that was removed.
450
U_CAPI void* U_EXPORT2
451
uhash_removeElement(UHashtable *hash, const UHashElement* e);
453
/********************************************************************
454
* UHashTok convenience
455
********************************************************************/
458
* Return a UHashTok for an integer.
460
U_CAPI UHashTok U_EXPORT2
461
uhash_toki(int32_t i);
464
* Return a UHashTok for a pointer.
466
U_CAPI UHashTok U_EXPORT2
469
/********************************************************************
470
* UChar* and char* Support Functions
471
********************************************************************/
474
* Generate a hash code for a null-terminated UChar* string. If the
475
* string is not null-terminated do not use this function. Use
476
* together with uhash_compareUChars.
477
* @param key The string (const UChar*) to hash.
478
* @return A hash code for the key.
480
U_CAPI int32_t U_EXPORT2
481
uhash_hashUChars(const UHashTok key);
484
* Generate a hash code for a null-terminated char* string. If the
485
* string is not null-terminated do not use this function. Use
486
* together with uhash_compareChars.
487
* @param key The string (const char*) to hash.
488
* @return A hash code for the key.
490
U_CAPI int32_t U_EXPORT2
491
uhash_hashChars(const UHashTok key);
493
/* Used by UnicodeString to compute its hashcode - Not public API. */
494
U_CAPI int32_t U_EXPORT2
495
uhash_hashUCharsN(const UChar *key, int32_t length);
498
* Generate a case-insensitive hash code for a null-terminated char*
499
* string. If the string is not null-terminated do not use this
500
* function. Use together with uhash_compareIChars.
501
* @param key The string (const char*) to hash.
502
* @return A hash code for the key.
504
U_CAPI int32_t U_EXPORT2
505
uhash_hashIChars(const UHashTok key);
508
* Comparator for null-terminated UChar* strings. Use together with
511
U_CAPI UBool U_EXPORT2
512
uhash_compareUChars(const UHashTok key1, const UHashTok key2);
515
* Comparator for null-terminated char* strings. Use together with
518
U_CAPI UBool U_EXPORT2
519
uhash_compareChars(const UHashTok key1, const UHashTok key2);
522
* Case-insensitive comparator for null-terminated char* strings. Use
523
* together with uhash_hashIChars.
525
U_CAPI UBool U_EXPORT2
526
uhash_compareIChars(const UHashTok key1, const UHashTok key2);
528
/********************************************************************
529
* UnicodeString Support Functions
530
********************************************************************/
533
* Hash function for UnicodeString* keys.
535
U_CAPI int32_t U_EXPORT2
536
uhash_hashUnicodeString(const UHashTok key);
539
* Hash function for UnicodeString* keys (case insensitive).
540
* Make sure to use together with uhash_compareCaselessUnicodeString.
542
U_CAPI int32_t U_EXPORT2
543
uhash_hashCaselessUnicodeString(const UHashTok key);
546
* Comparator function for UnicodeString* keys.
548
U_CAPI UBool U_EXPORT2
549
uhash_compareUnicodeString(const UHashTok key1, const UHashTok key2);
552
* Comparator function for UnicodeString* keys (case insensitive).
553
* Make sure to use together with uhash_hashCaselessUnicodeString.
555
U_CAPI UBool U_EXPORT2
556
uhash_compareCaselessUnicodeString(const UHashTok key1, const UHashTok key2);
559
* Deleter function for UnicodeString* keys or values.
561
U_CAPI void U_EXPORT2
562
uhash_deleteUnicodeString(void *obj);
564
/********************************************************************
565
* int32_t Support Functions
566
********************************************************************/
569
* Hash function for 32-bit integer keys.
571
U_CAPI int32_t U_EXPORT2
572
uhash_hashLong(const UHashTok key);
575
* Comparator function for 32-bit integer keys.
577
U_CAPI UBool U_EXPORT2
578
uhash_compareLong(const UHashTok key1, const UHashTok key2);
580
/********************************************************************
581
* Other Support Functions
582
********************************************************************/
585
* Deleter for Hashtable objects.
587
U_CAPI void U_EXPORT2
588
uhash_deleteHashtable(void *obj);
591
* Deleter for UVector objects.
593
U_CAPI void U_EXPORT2
594
uhash_deleteUVector(void *obj);
597
* Deleter for any key or value allocated using uprv_malloc. Calls
600
U_CAPI void U_EXPORT2
601
uhash_freeBlock(void *obj);
added
removed
source/common/uhash.h
