1 // Copyright (C) 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
4 ******************************************************************************
5 * Copyright (C) 1997-2015, 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 ******************************************************************************
18 #include "unicode/utypes.h"
21 #include "unicode/localpointer.h"
24 * UHashtable stores key-value pairs and does moderately fast lookup
25 * based on keys. It provides a good tradeoff between access time and
26 * storage space. As elements are added to it, it grows to accomodate
27 * them. By default, the table never shrinks, even if all elements
28 * are removed from it.
30 * Keys and values are stored as void* pointers. These void* pointers
31 * may be actual pointers to strings, objects, or any other structure
32 * in memory, or they may simply be integral values cast to void*.
33 * UHashtable doesn't care and manipulates them via user-supplied
34 * functions. These functions hash keys, compare keys, delete keys,
35 * and delete values. Some function pointers are optional (may be
36 * NULL); others must be supplied. Several prebuilt functions exist
37 * to handle common key types.
39 * UHashtable ownership of keys and values is flexible, and controlled
40 * by whether or not the key deleter and value deleter functions are
41 * set. If a void* key is actually a pointer to a deletable object,
42 * then UHashtable can be made to delete that object by setting the
43 * key deleter function pointer to a non-NULL value. If this is done,
44 * then keys passed to uhash_put() are owned by the hashtable and will
45 * be deleted by it at some point, either as keys are replaced, or
46 * when uhash_close() is finally called. The same is true of values
47 * and the value deleter function pointer. Keys passed to methods
48 * other than uhash_put() are never owned by the hashtable.
50 * NULL values are not allowed. uhash_get() returns NULL to indicate
51 * a key that is not in the table, and having a NULL value in the
52 * table would generate an ambiguous result. If a key and a NULL
53 * value is passed to uhash_put(), this has the effect of doing a
54 * uhash_remove() on that key. This keeps uhash_get(), uhash_count(),
55 * and uhash_nextElement() consistent with one another.
57 * To see everything in a hashtable, use uhash_nextElement() to
58 * iterate through its contents. Each call to this function returns a
59 * UHashElement pointer. A hash element contains a key, value, and
60 * hashcode. During iteration an element may be deleted by calling
61 * uhash_removeElement(); iteration may safely continue thereafter.
62 * The uhash_remove() function may also be safely called in
63 * mid-iteration. If uhash_put() is called during iteration,
64 * the iteration is still guaranteed to terminate reasonably, but
65 * there is no guarantee that every element will be returned or that
66 * some won't be returned more than once.
68 * Under no circumstances should the UHashElement returned by
69 * uhash_nextElement be modified directly.
71 * By default, the hashtable grows when necessary, but never shrinks,
72 * even if all items are removed. For most applications this is
73 * optimal. However, in a highly dynamic usage where memory is at a
74 * premium, the table can be set to both grow and shrink by calling
75 * uhash_setResizePolicy() with the policy U_GROW_AND_SHRINK. In a
76 * situation where memory is critical and the client wants a table
77 * that does not grow at all, the constant U_FIXED can be used.
80 /********************************************************************
82 ********************************************************************/
87 * A key or value within a UHashtable.
88 * The hashing and comparison functions take a pointer to a
89 * UHashTok, but the deleter receives the void* pointer within it.
91 typedef UElement UHashTok;
94 * This is a single hash element.
97 /* Reorder these elements to pack nicely if necessary */
102 typedef struct UHashElement UHashElement;
105 * A hashing function.
106 * @param key A key stored in a hashtable
107 * @return A NON-NEGATIVE hash code for parm.
109 typedef int32_t U_CALLCONV UHashFunction(const UHashTok key);
112 * A key equality (boolean) comparison function.
114 typedef UElementsAreEqual UKeyComparator;
117 * A value equality (boolean) comparison function.
119 typedef UElementsAreEqual UValueComparator;
121 /* see cmemory.h for UObjectDeleter and uprv_deleteUObject() */
124 * This specifies whether or not, and how, the hastable resizes itself.
125 * See uhash_setResizePolicy().
127 enum UHashResizePolicy {
128 U_GROW, /* Grow on demand, do not shrink */
129 U_GROW_AND_SHRINK, /* Grow and shrink on demand */
130 U_FIXED /* Never change size */
134 * The UHashtable struct. Clients should treat this as an opaque data
135 * type and manipulate it only through the uhash_... API.
139 /* Main key-value pair storage array */
141 UHashElement *elements;
143 /* Function pointers */
145 UHashFunction *keyHasher; /* Computes hash from key.
147 UKeyComparator *keyComparator; /* Compares keys for equality.
149 UValueComparator *valueComparator; /* Compares the values for equality */
151 UObjectDeleter *keyDeleter; /* Deletes keys when required.
152 * If NULL won't do anything */
153 UObjectDeleter *valueDeleter; /* Deletes values when required.
154 * If NULL won't do anything */
156 /* Size parameters */
158 int32_t count; /* The number of key-value pairs in this table.
159 * 0 <= count <= length. In practice we
160 * never let count == length (see code). */
161 int32_t length; /* The physical size of the arrays hashes, keys
162 * and values. Must be prime. */
164 /* Rehashing thresholds */
166 int32_t highWaterMark; /* If count > highWaterMark, rehash */
167 int32_t lowWaterMark; /* If count < lowWaterMark, rehash */
168 float highWaterRatio; /* 0..1; high water as a fraction of length */
169 float lowWaterRatio; /* 0..1; low water as a fraction of length */
171 int8_t primeIndex; /* Index into our prime table for length.
172 * length == PRIMES[primeIndex] */
173 UBool allocated; /* Was this UHashtable allocated? */
175 typedef struct UHashtable UHashtable;
179 /********************************************************************
181 ********************************************************************/
184 * Initialize a new UHashtable.
185 * @param keyHash A pointer to the key hashing function. Must not be
187 * @param keyComp A pointer to the function that compares keys. Must
189 * @param status A pointer to an UErrorCode to receive any errors.
190 * @return A pointer to a UHashtable, or 0 if an error occurred.
191 * @see uhash_openSize
193 U_CAPI UHashtable* U_EXPORT2
194 uhash_open(UHashFunction *keyHash,
195 UKeyComparator *keyComp,
196 UValueComparator *valueComp,
200 * Initialize a new UHashtable with a given initial size.
201 * @param keyHash A pointer to the key hashing function. Must not be
203 * @param keyComp A pointer to the function that compares keys. Must
205 * @param size The initial capacity of this hash table.
206 * @param status A pointer to an UErrorCode to receive any errors.
207 * @return A pointer to a UHashtable, or 0 if an error occurred.
210 U_CAPI UHashtable* U_EXPORT2
211 uhash_openSize(UHashFunction *keyHash,
212 UKeyComparator *keyComp,
213 UValueComparator *valueComp,
218 * Initialize an existing UHashtable.
219 * @param keyHash A pointer to the key hashing function. Must not be
221 * @param keyComp A pointer to the function that compares keys. Must
223 * @param status A pointer to an UErrorCode to receive any errors.
224 * @return A pointer to a UHashtable, or 0 if an error occurred.
225 * @see uhash_openSize
227 U_CAPI UHashtable* U_EXPORT2
228 uhash_init(UHashtable *hash,
229 UHashFunction *keyHash,
230 UKeyComparator *keyComp,
231 UValueComparator *valueComp,
235 * Close a UHashtable, releasing the memory used.
236 * @param hash The UHashtable to close. If hash is NULL no operation is performed.
238 U_CAPI void U_EXPORT2
239 uhash_close(UHashtable *hash);
244 * Set the function used to hash keys.
245 * @param hash The UHashtable to set
246 * @param fn the function to be used hash keys; must not be NULL
247 * @return the previous key hasher; non-NULL
249 U_CAPI UHashFunction *U_EXPORT2
250 uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn);
253 * Set the function used to compare keys. The default comparison is a
254 * void* pointer comparison.
255 * @param hash The UHashtable to set
256 * @param fn the function to be used compare keys; must not be NULL
257 * @return the previous key comparator; non-NULL
259 U_CAPI UKeyComparator *U_EXPORT2
260 uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn);
263 * Set the function used to compare values. The default comparison is a
264 * void* pointer comparison.
265 * @param hash The UHashtable to set
266 * @param fn the function to be used compare keys; must not be NULL
267 * @return the previous key comparator; non-NULL
269 U_CAPI UValueComparator *U_EXPORT2
270 uhash_setValueComparator(UHashtable *hash, UValueComparator *fn);
273 * Set the function used to delete keys. If this function pointer is
274 * NULL, this hashtable does not delete keys. If it is non-NULL, this
275 * hashtable does delete keys. This function should be set once
276 * before any elements are added to the hashtable and should not be
277 * changed thereafter.
278 * @param hash The UHashtable to set
279 * @param fn the function to be used delete keys, or NULL
280 * @return the previous key deleter; may be NULL
282 U_CAPI UObjectDeleter *U_EXPORT2
283 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn);
286 * Set the function used to delete values. If this function pointer
287 * is NULL, this hashtable does not delete values. If it is non-NULL,
288 * this hashtable does delete values. This function should be set
289 * once before any elements are added to the hashtable and should not
290 * be changed thereafter.
291 * @param hash The UHashtable to set
292 * @param fn the function to be used delete values, or NULL
293 * @return the previous value deleter; may be NULL
295 U_CAPI UObjectDeleter *U_EXPORT2
296 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn);
299 * Specify whether or not, and how, the hastable resizes itself.
300 * By default, tables grow but do not shrink (policy U_GROW).
301 * See enum UHashResizePolicy.
302 * @param hash The UHashtable to set
303 * @param policy The way the hashtable resizes itself, {U_GROW, U_GROW_AND_SHRINK, U_FIXED}
305 U_CAPI void U_EXPORT2
306 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy);
309 * Get the number of key-value pairs stored in a UHashtable.
310 * @param hash The UHashtable to query.
311 * @return The number of key-value pairs stored in hash.
313 U_CAPI int32_t U_EXPORT2
314 uhash_count(const UHashtable *hash);
317 * Put a (key=pointer, value=pointer) item in a UHashtable. If the
318 * keyDeleter is non-NULL, then the hashtable owns 'key' after this
319 * call. If the valueDeleter is non-NULL, then the hashtable owns
320 * 'value' after this call. Storing a NULL value is the same as
321 * calling uhash_remove().
322 * @param hash The target UHashtable.
323 * @param key The key to store.
324 * @param value The value to store, may be NULL (see above).
325 * @param status A pointer to an UErrorCode to receive any errors.
326 * @return The previous value, or NULL if none.
329 U_CAPI void* U_EXPORT2
330 uhash_put(UHashtable *hash,
336 * Put a (key=integer, value=pointer) item in a UHashtable.
337 * keyDeleter must be NULL. If the valueDeleter is non-NULL, then the
338 * hashtable owns 'value' after this call. Storing a NULL value is
339 * the same as calling uhash_remove().
340 * @param hash The target UHashtable.
341 * @param key The integer key to store.
342 * @param value The value to store, may be NULL (see above).
343 * @param status A pointer to an UErrorCode to receive any errors.
344 * @return The previous value, or NULL if none.
347 U_CAPI void* U_EXPORT2
348 uhash_iput(UHashtable *hash,
354 * Put a (key=pointer, value=integer) item in a UHashtable. If the
355 * keyDeleter is non-NULL, then the hashtable owns 'key' after this
356 * call. valueDeleter must be NULL. Storing a 0 value is the same as
357 * calling uhash_remove().
358 * @param hash The target UHashtable.
359 * @param key The key to store.
360 * @param value The integer value to store.
361 * @param status A pointer to an UErrorCode to receive any errors.
362 * @return The previous value, or 0 if none.
365 U_CAPI int32_t U_EXPORT2
366 uhash_puti(UHashtable *hash,
372 * Put a (key=integer, value=integer) item in a UHashtable. If the
373 * keyDeleter is non-NULL, then the hashtable owns 'key' after this
374 * call. valueDeleter must be NULL. Storing a 0 value is the same as
375 * calling uhash_remove().
376 * @param hash The target UHashtable.
377 * @param key The key to store.
378 * @param value The integer value to store.
379 * @param status A pointer to an UErrorCode to receive any errors.
380 * @return The previous value, or 0 if none.
383 U_CAPI int32_t U_EXPORT2
384 uhash_iputi(UHashtable *hash,
390 * Retrieve a pointer value from a UHashtable using a pointer key,
391 * as previously stored by uhash_put().
392 * @param hash The target UHashtable.
393 * @param key A pointer key stored in a hashtable
394 * @return The requested item, or NULL if not found.
396 U_CAPI void* U_EXPORT2
397 uhash_get(const UHashtable *hash,
401 * Retrieve a pointer value from a UHashtable using a integer key,
402 * as previously stored by uhash_iput().
403 * @param hash The target UHashtable.
404 * @param key An integer key stored in a hashtable
405 * @return The requested item, or NULL if not found.
407 U_CAPI void* U_EXPORT2
408 uhash_iget(const UHashtable *hash,
412 * Retrieve an integer value from a UHashtable using a pointer key,
413 * as previously stored by uhash_puti().
414 * @param hash The target UHashtable.
415 * @param key A pointer key stored in a hashtable
416 * @return The requested item, or 0 if not found.
418 U_CAPI int32_t U_EXPORT2
419 uhash_geti(const UHashtable *hash,
422 * Retrieve an integer value from a UHashtable using an integer key,
423 * as previously stored by uhash_iputi().
424 * @param hash The target UHashtable.
425 * @param key An integer key stored in a hashtable
426 * @return The requested item, or 0 if not found.
428 U_CAPI int32_t U_EXPORT2
429 uhash_igeti(const UHashtable *hash,
433 * Remove an item from a UHashtable stored by uhash_put().
434 * @param hash The target UHashtable.
435 * @param key A key stored in a hashtable
436 * @return The item removed, or NULL if not found.
438 U_CAPI void* U_EXPORT2
439 uhash_remove(UHashtable *hash,
443 * Remove an item from a UHashtable stored by uhash_iput().
444 * @param hash The target UHashtable.
445 * @param key An integer key stored in a hashtable
446 * @return The item removed, or NULL if not found.
448 U_CAPI void* U_EXPORT2
449 uhash_iremove(UHashtable *hash,
453 * Remove an item from a UHashtable stored by uhash_puti().
454 * @param hash The target UHashtable.
455 * @param key An key stored in a hashtable
456 * @return The item removed, or 0 if not found.
458 U_CAPI int32_t U_EXPORT2
459 uhash_removei(UHashtable *hash,
463 * Remove an item from a UHashtable stored by uhash_iputi().
464 * @param hash The target UHashtable.
465 * @param key An integer key stored in a hashtable
466 * @return The item removed, or 0 if not found.
468 U_CAPI int32_t U_EXPORT2
469 uhash_iremovei(UHashtable *hash,
473 * Remove all items from a UHashtable.
474 * @param hash The target UHashtable.
476 U_CAPI void U_EXPORT2
477 uhash_removeAll(UHashtable *hash);
480 * Locate an element of a UHashtable. The caller must not modify the
481 * returned object. The primary use of this function is to obtain the
482 * stored key when it may not be identical to the search key. For
483 * example, if the compare function is a case-insensitive string
484 * compare, then the hash key may be desired in order to obtain the
485 * canonical case corresponding to a search key.
486 * @param hash The target UHashtable.
487 * @param key A key stored in a hashtable
488 * @return a hash element, or NULL if the key is not found.
490 U_CAPI const UHashElement* U_EXPORT2
491 uhash_find(const UHashtable *hash, const void* key);
495 * Constant for use with uhash_nextElement
496 * @see uhash_nextElement
498 #define UHASH_FIRST (-1)
501 * Iterate through the elements of a UHashtable. The caller must not
502 * modify the returned object. However, uhash_removeElement() may be
503 * called during iteration to remove an element from the table.
504 * Iteration may safely be resumed afterwards. If uhash_put() is
505 * called during iteration the iteration will then be out of sync and
506 * should be restarted.
507 * @param hash The target UHashtable.
508 * @param pos This should be set to UHASH_FIRST initially, and left untouched
510 * @return a hash element, or NULL if no further key-value pairs
511 * exist in the table.
513 U_CAPI const UHashElement* U_EXPORT2
514 uhash_nextElement(const UHashtable *hash,
518 * Remove an element, returned by uhash_nextElement(), from the table.
519 * Iteration may be safely continued afterwards.
520 * @param hash The hashtable
521 * @param e The element, returned by uhash_nextElement(), to remove.
522 * Must not be NULL. Must not be an empty or deleted element (as long
523 * as this was returned by uhash_nextElement() it will not be empty or
524 * deleted). Note: Although this parameter is const, it will be
526 * @return the value that was removed.
528 U_CAPI void* U_EXPORT2
529 uhash_removeElement(UHashtable *hash, const UHashElement* e);
531 /********************************************************************
532 * UHashTok convenience
533 ********************************************************************/
536 * Return a UHashTok for an integer.
537 * @param i The given integer
538 * @return a UHashTok for an integer.
540 /*U_CAPI UHashTok U_EXPORT2
541 uhash_toki(int32_t i);*/
544 * Return a UHashTok for a pointer.
545 * @param p The given pointer
546 * @return a UHashTok for a pointer.
548 /*U_CAPI UHashTok U_EXPORT2
549 uhash_tokp(void* p);*/
551 /********************************************************************
552 * UChar* and char* Support Functions
553 ********************************************************************/
556 * Generate a hash code for a null-terminated UChar* string. If the
557 * string is not null-terminated do not use this function. Use
558 * together with uhash_compareUChars.
559 * @param key The string (const UChar*) to hash.
560 * @return A hash code for the key.
562 U_CAPI int32_t U_EXPORT2
563 uhash_hashUChars(const UHashTok key);
566 * Generate a hash code for a null-terminated char* string. If the
567 * string is not null-terminated do not use this function. Use
568 * together with uhash_compareChars.
569 * @param key The string (const char*) to hash.
570 * @return A hash code for the key.
572 U_CAPI int32_t U_EXPORT2
573 uhash_hashChars(const UHashTok key);
576 * Generate a case-insensitive hash code for a null-terminated char*
577 * string. If the string is not null-terminated do not use this
578 * function. Use together with uhash_compareIChars.
579 * @param key The string (const char*) to hash.
580 * @return A hash code for the key.
582 U_CAPI int32_t U_EXPORT2
583 uhash_hashIChars(const UHashTok key);
586 * Comparator for null-terminated UChar* strings. Use together with
588 * @param key1 The string for comparison
589 * @param key2 The string for comparison
590 * @return true if key1 and key2 are equal, return false otherwise.
592 U_CAPI UBool U_EXPORT2
593 uhash_compareUChars(const UHashTok key1, const UHashTok key2);
596 * Comparator for null-terminated char* strings. Use together with
598 * @param key1 The string for comparison
599 * @param key2 The string for comparison
600 * @return true if key1 and key2 are equal, return false otherwise.
602 U_CAPI UBool U_EXPORT2
603 uhash_compareChars(const UHashTok key1, const UHashTok key2);
606 * Case-insensitive comparator for null-terminated char* strings. Use
607 * together with uhash_hashIChars.
608 * @param key1 The string for comparison
609 * @param key2 The string for comparison
610 * @return true if key1 and key2 are equal, return false otherwise.
612 U_CAPI UBool U_EXPORT2
613 uhash_compareIChars(const UHashTok key1, const UHashTok key2);
615 /********************************************************************
616 * UnicodeString Support Functions
617 ********************************************************************/
620 * Hash function for UnicodeString* keys.
621 * @param key The string (const char*) to hash.
622 * @return A hash code for the key.
624 U_CAPI int32_t U_EXPORT2
625 uhash_hashUnicodeString(const UElement key);
628 * Hash function for UnicodeString* keys (case insensitive).
629 * Make sure to use together with uhash_compareCaselessUnicodeString.
630 * @param key The string (const char*) to hash.
631 * @return A hash code for the key.
633 U_CAPI int32_t U_EXPORT2
634 uhash_hashCaselessUnicodeString(const UElement key);
636 /********************************************************************
637 * int32_t Support Functions
638 ********************************************************************/
641 * Hash function for 32-bit integer keys.
642 * @param key The string (const char*) to hash.
643 * @return A hash code for the key.
645 U_CAPI int32_t U_EXPORT2
646 uhash_hashLong(const UHashTok key);
649 * Comparator function for 32-bit integer keys.
650 * @param key1 The integer for comparison
651 * @param Key2 The integer for comparison
652 * @return true if key1 and key2 are equal, return false otherwise
654 U_CAPI UBool U_EXPORT2
655 uhash_compareLong(const UHashTok key1, const UHashTok key2);
657 /********************************************************************
658 * Other Support Functions
659 ********************************************************************/
662 * Deleter for Hashtable objects.
663 * @param obj The object to be deleted
665 U_CAPI void U_EXPORT2
666 uhash_deleteHashtable(void *obj);
668 /* Use uprv_free() itself as a deleter for any key or value allocated using uprv_malloc. */
671 * Checks if the given hash tables are equal or not.
674 * @return true if the hashtables are equal and false if not.
676 U_CAPI UBool U_EXPORT2
677 uhash_equals(const UHashtable* hash1, const UHashtable* hash2);
680 #if U_SHOW_CPLUSPLUS_API
685 * \class LocalUHashtablePointer
686 * "Smart pointer" class, closes a UHashtable via uhash_close().
687 * For most methods see the LocalPointerBase base class.
689 * @see LocalPointerBase
693 U_DEFINE_LOCAL_OPEN_POINTER(LocalUHashtablePointer, UHashtable, uhash_close);