1 /* 2 ****************************************************************************** 3 * Copyright (C) 1997-2011, 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 ****************************************************************************** 11 */ 12 13 #ifndef UHASH_H 14 #define UHASH_H 15 16 #include "unicode/utypes.h" 17 #include "cmemory.h" 18 #include "uelement.h" 19 20 /** 21 * UHashtable stores key-value pairs and does moderately fast lookup 22 * based on keys. It provides a good tradeoff between access time and 23 * storage space. As elements are added to it, it grows to accomodate 24 * them. By default, the table never shrinks, even if all elements 25 * are removed from it. 26 * 27 * Keys and values are stored as void* pointers. These void* pointers 28 * may be actual pointers to strings, objects, or any other structure 29 * in memory, or they may simply be integral values cast to void*. 30 * UHashtable doesn't care and manipulates them via user-supplied 31 * functions. These functions hash keys, compare keys, delete keys, 32 * and delete values. Some function pointers are optional (may be 33 * NULL); others must be supplied. Several prebuilt functions exist 34 * to handle common key types. 35 * 36 * UHashtable ownership of keys and values is flexible, and controlled 37 * by whether or not the key deleter and value deleter functions are 38 * set. If a void* key is actually a pointer to a deletable object, 39 * then UHashtable can be made to delete that object by setting the 40 * key deleter function pointer to a non-NULL value. If this is done, 41 * then keys passed to uhash_put() are owned by the hashtable and will 42 * be deleted by it at some point, either as keys are replaced, or 43 * when uhash_close() is finally called. The same is true of values 44 * and the value deleter function pointer. Keys passed to methods 45 * other than uhash_put() are never owned by the hashtable. 46 * 47 * NULL values are not allowed. uhash_get() returns NULL to indicate 48 * a key that is not in the table, and having a NULL value in the 49 * table would generate an ambiguous result. If a key and a NULL 50 * value is passed to uhash_put(), this has the effect of doing a 51 * uhash_remove() on that key. This keeps uhash_get(), uhash_count(), 52 * and uhash_nextElement() consistent with one another. 53 * 54 * To see everything in a hashtable, use uhash_nextElement() to 55 * iterate through its contents. Each call to this function returns a 56 * UHashElement pointer. A hash element contains a key, value, and 57 * hashcode. During iteration an element may be deleted by calling 58 * uhash_removeElement(); iteration may safely continue thereafter. 59 * The uhash_remove() function may also be safely called in 60 * mid-iteration. However, if uhash_put() is called during iteration 61 * then the iteration will be out of sync. Under no circumstances 62 * should the UHashElement returned by uhash_nextElement be modified 63 * directly. 64 * 65 * By default, the hashtable grows when necessary, but never shrinks, 66 * even if all items are removed. For most applications this is 67 * optimal. However, in a highly dynamic usage where memory is at a 68 * premium, the table can be set to both grow and shrink by calling 69 * uhash_setResizePolicy() with the policy U_GROW_AND_SHRINK. In a 70 * situation where memory is critical and the client wants a table 71 * that does not grow at all, the constant U_FIXED can be used. 72 */ 73 74 /******************************************************************** 75 * Data Structures 76 ********************************************************************/ 77 78 U_CDECL_BEGIN 79 80 /** 81 * A key or value within a UHashtable. 82 * The hashing and comparison functions take a pointer to a 83 * UHashTok, but the deleter receives the void* pointer within it. 84 */ 85 typedef UElement UHashTok; 86 87 /** 88 * This is a single hash element. 89 */ 90 struct UHashElement { 91 /* Reorder these elements to pack nicely if necessary */ 92 int32_t hashcode; 93 UHashTok value; 94 UHashTok key; 95 }; 96 typedef struct UHashElement UHashElement; 97 98 /** 99 * A hashing function. 100 * @param key A key stored in a hashtable 101 * @return A NON-NEGATIVE hash code for parm. 102 */ 103 typedef int32_t U_CALLCONV UHashFunction(const UHashTok key); 104 105 /** 106 * A key equality (boolean) comparison function. 107 */ 108 typedef UElementsAreEqual UKeyComparator; 109 110 /** 111 * A value equality (boolean) comparison function. 112 */ 113 typedef UElementsAreEqual UValueComparator; 114 115 /* see cmemory.h for UObjectDeleter and uprv_deleteUObject() */ 116 117 /** 118 * This specifies whether or not, and how, the hastable resizes itself. 119 * See uhash_setResizePolicy(). 120 */ 121 enum UHashResizePolicy { 122 U_GROW, /* Grow on demand, do not shrink */ 123 U_GROW_AND_SHRINK, /* Grow and shrink on demand */ 124 U_FIXED /* Never change size */ 125 }; 126 127 /** 128 * The UHashtable struct. Clients should treat this as an opaque data 129 * type and manipulate it only through the uhash_... API. 130 */ 131 struct UHashtable { 132 133 /* Main key-value pair storage array */ 134 135 UHashElement *elements; 136 137 /* Function pointers */ 138 139 UHashFunction *keyHasher; /* Computes hash from key. 140 * Never null. */ 141 UKeyComparator *keyComparator; /* Compares keys for equality. 142 * Never null. */ 143 UValueComparator *valueComparator; /* Compares the values for equality */ 144 145 UObjectDeleter *keyDeleter; /* Deletes keys when required. 146 * If NULL won't do anything */ 147 UObjectDeleter *valueDeleter; /* Deletes values when required. 148 * If NULL won't do anything */ 149 150 /* Size parameters */ 151 152 int32_t count; /* The number of key-value pairs in this table. 153 * 0 <= count <= length. In practice we 154 * never let count == length (see code). */ 155 int32_t length; /* The physical size of the arrays hashes, keys 156 * and values. Must be prime. */ 157 158 /* Rehashing thresholds */ 159 160 int32_t highWaterMark; /* If count > highWaterMark, rehash */ 161 int32_t lowWaterMark; /* If count < lowWaterMark, rehash */ 162 float highWaterRatio; /* 0..1; high water as a fraction of length */ 163 float lowWaterRatio; /* 0..1; low water as a fraction of length */ 164 165 int8_t primeIndex; /* Index into our prime table for length. 166 * length == PRIMES[primeIndex] */ 167 UBool allocated; /* Was this UHashtable allocated? */ 168 }; 169 typedef struct UHashtable UHashtable; 170 171 U_CDECL_END 172 173 /******************************************************************** 174 * API 175 ********************************************************************/ 176 177 /** 178 * Initialize a new UHashtable. 179 * @param keyHash A pointer to the key hashing function. Must not be 180 * NULL. 181 * @param keyComp A pointer to the function that compares keys. Must 182 * not be NULL. 183 * @param status A pointer to an UErrorCode to receive any errors. 184 * @return A pointer to a UHashtable, or 0 if an error occurred. 185 * @see uhash_openSize 186 */ 187 U_CAPI UHashtable* U_EXPORT2 188 uhash_open(UHashFunction *keyHash, 189 UKeyComparator *keyComp, 190 UValueComparator *valueComp, 191 UErrorCode *status); 192 193 /** 194 * Initialize a new UHashtable with a given initial size. 195 * @param keyHash A pointer to the key hashing function. Must not be 196 * NULL. 197 * @param keyComp A pointer to the function that compares keys. Must 198 * not be NULL. 199 * @param size The initial capacity of this hash table. 200 * @param status A pointer to an UErrorCode to receive any errors. 201 * @return A pointer to a UHashtable, or 0 if an error occurred. 202 * @see uhash_open 203 */ 204 U_CAPI UHashtable* U_EXPORT2 205 uhash_openSize(UHashFunction *keyHash, 206 UKeyComparator *keyComp, 207 UValueComparator *valueComp, 208 int32_t size, 209 UErrorCode *status); 210 211 /** 212 * Initialize an existing UHashtable. 213 * @param keyHash A pointer to the key hashing function. Must not be 214 * NULL. 215 * @param keyComp A pointer to the function that compares keys. Must 216 * not be NULL. 217 * @param status A pointer to an UErrorCode to receive any errors. 218 * @return A pointer to a UHashtable, or 0 if an error occurred. 219 * @see uhash_openSize 220 */ 221 U_CAPI UHashtable* U_EXPORT2 222 uhash_init(UHashtable *hash, 223 UHashFunction *keyHash, 224 UKeyComparator *keyComp, 225 UValueComparator *valueComp, 226 UErrorCode *status); 227 228 /** 229 * Close a UHashtable, releasing the memory used. 230 * @param hash The UHashtable to close. If hash is NULL no operation is performed. 231 */ 232 U_CAPI void U_EXPORT2 233 uhash_close(UHashtable *hash); 234 235 236 237 /** 238 * Set the function used to hash keys. 239 * @param hash The UHashtable to set 240 * @param fn the function to be used hash keys; must not be NULL 241 * @return the previous key hasher; non-NULL 242 */ 243 U_CAPI UHashFunction *U_EXPORT2 244 uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn); 245 246 /** 247 * Set the function used to compare keys. The default comparison is a 248 * void* pointer comparison. 249 * @param hash The UHashtable to set 250 * @param fn the function to be used compare keys; must not be NULL 251 * @return the previous key comparator; non-NULL 252 */ 253 U_CAPI UKeyComparator *U_EXPORT2 254 uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn); 255 256 /** 257 * Set the function used to compare values. The default comparison is a 258 * void* pointer comparison. 259 * @param hash The UHashtable to set 260 * @param fn the function to be used compare keys; must not be NULL 261 * @return the previous key comparator; non-NULL 262 */ 263 U_CAPI UValueComparator *U_EXPORT2 264 uhash_setValueComparator(UHashtable *hash, UValueComparator *fn); 265 266 /** 267 * Set the function used to delete keys. If this function pointer is 268 * NULL, this hashtable does not delete keys. If it is non-NULL, this 269 * hashtable does delete keys. This function should be set once 270 * before any elements are added to the hashtable and should not be 271 * changed thereafter. 272 * @param hash The UHashtable to set 273 * @param fn the function to be used delete keys, or NULL 274 * @return the previous key deleter; may be NULL 275 */ 276 U_CAPI UObjectDeleter *U_EXPORT2 277 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn); 278 279 /** 280 * Set the function used to delete values. If this function pointer 281 * is NULL, this hashtable does not delete values. If it is non-NULL, 282 * this hashtable does delete values. This function should be set 283 * once before any elements are added to the hashtable and should not 284 * be changed thereafter. 285 * @param hash The UHashtable to set 286 * @param fn the function to be used delete values, or NULL 287 * @return the previous value deleter; may be NULL 288 */ 289 U_CAPI UObjectDeleter *U_EXPORT2 290 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn); 291 292 /** 293 * Specify whether or not, and how, the hastable resizes itself. 294 * By default, tables grow but do not shrink (policy U_GROW). 295 * See enum UHashResizePolicy. 296 * @param hash The UHashtable to set 297 * @param policy The way the hashtable resizes itself, {U_GROW, U_GROW_AND_SHRINK, U_FIXED} 298 */ 299 U_CAPI void U_EXPORT2 300 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy); 301 302 /** 303 * Get the number of key-value pairs stored in a UHashtable. 304 * @param hash The UHashtable to query. 305 * @return The number of key-value pairs stored in hash. 306 */ 307 U_CAPI int32_t U_EXPORT2 308 uhash_count(const UHashtable *hash); 309 310 /** 311 * Put a (key=pointer, value=pointer) item in a UHashtable. If the 312 * keyDeleter is non-NULL, then the hashtable owns 'key' after this 313 * call. If the valueDeleter is non-NULL, then the hashtable owns 314 * 'value' after this call. Storing a NULL value is the same as 315 * calling uhash_remove(). 316 * @param hash The target UHashtable. 317 * @param key The key to store. 318 * @param value The value to store, may be NULL (see above). 319 * @param status A pointer to an UErrorCode to receive any errors. 320 * @return The previous value, or NULL if none. 321 * @see uhash_get 322 */ 323 U_CAPI void* U_EXPORT2 324 uhash_put(UHashtable *hash, 325 void *key, 326 void *value, 327 UErrorCode *status); 328 329 /** 330 * Put a (key=integer, value=pointer) item in a UHashtable. 331 * keyDeleter must be NULL. If the valueDeleter is non-NULL, then the 332 * hashtable owns 'value' after this call. Storing a NULL value is 333 * the same as calling uhash_remove(). 334 * @param hash The target UHashtable. 335 * @param key The integer key to store. 336 * @param value The value to store, may be NULL (see above). 337 * @param status A pointer to an UErrorCode to receive any errors. 338 * @return The previous value, or NULL if none. 339 * @see uhash_get 340 */ 341 U_CAPI void* U_EXPORT2 342 uhash_iput(UHashtable *hash, 343 int32_t key, 344 void* value, 345 UErrorCode *status); 346 347 /** 348 * Put a (key=pointer, value=integer) item in a UHashtable. If the 349 * keyDeleter is non-NULL, then the hashtable owns 'key' after this 350 * call. valueDeleter must be NULL. Storing a 0 value is the same as 351 * calling uhash_remove(). 352 * @param hash The target UHashtable. 353 * @param key The key to store. 354 * @param value The integer value to store. 355 * @param status A pointer to an UErrorCode to receive any errors. 356 * @return The previous value, or 0 if none. 357 * @see uhash_get 358 */ 359 U_CAPI int32_t U_EXPORT2 360 uhash_puti(UHashtable *hash, 361 void* key, 362 int32_t value, 363 UErrorCode *status); 364 365 /** 366 * Put a (key=integer, value=integer) item in a UHashtable. If the 367 * keyDeleter is non-NULL, then the hashtable owns 'key' after this 368 * call. valueDeleter must be NULL. Storing a 0 value is the same as 369 * calling uhash_remove(). 370 * @param hash The target UHashtable. 371 * @param key The key to store. 372 * @param value The integer value to store. 373 * @param status A pointer to an UErrorCode to receive any errors. 374 * @return The previous value, or 0 if none. 375 * @see uhash_get 376 */ 377 U_CAPI int32_t U_EXPORT2 378 uhash_iputi(UHashtable *hash, 379 int32_t key, 380 int32_t value, 381 UErrorCode *status); 382 383 /** 384 * Retrieve a pointer value from a UHashtable using a pointer key, 385 * as previously stored by uhash_put(). 386 * @param hash The target UHashtable. 387 * @param key A pointer key stored in a hashtable 388 * @return The requested item, or NULL if not found. 389 */ 390 U_CAPI void* U_EXPORT2 391 uhash_get(const UHashtable *hash, 392 const void *key); 393 394 /** 395 * Retrieve a pointer value from a UHashtable using a integer key, 396 * as previously stored by uhash_iput(). 397 * @param hash The target UHashtable. 398 * @param key An integer key stored in a hashtable 399 * @return The requested item, or NULL if not found. 400 */ 401 U_CAPI void* U_EXPORT2 402 uhash_iget(const UHashtable *hash, 403 int32_t key); 404 405 /** 406 * Retrieve an integer value from a UHashtable using a pointer key, 407 * as previously stored by uhash_puti(). 408 * @param hash The target UHashtable. 409 * @param key A pointer key stored in a hashtable 410 * @return The requested item, or 0 if not found. 411 */ 412 U_CAPI int32_t U_EXPORT2 413 uhash_geti(const UHashtable *hash, 414 const void* key); 415 /** 416 * Retrieve an integer value from a UHashtable using an integer key, 417 * as previously stored by uhash_iputi(). 418 * @param hash The target UHashtable. 419 * @param key An integer key stored in a hashtable 420 * @return The requested item, or 0 if not found. 421 */ 422 U_CAPI int32_t U_EXPORT2 423 uhash_igeti(const UHashtable *hash, 424 int32_t key); 425 426 /** 427 * Remove an item from a UHashtable stored by uhash_put(). 428 * @param hash The target UHashtable. 429 * @param key A key stored in a hashtable 430 * @return The item removed, or NULL if not found. 431 */ 432 U_CAPI void* U_EXPORT2 433 uhash_remove(UHashtable *hash, 434 const void *key); 435 436 /** 437 * Remove an item from a UHashtable stored by uhash_iput(). 438 * @param hash The target UHashtable. 439 * @param key An integer key stored in a hashtable 440 * @return The item removed, or NULL if not found. 441 */ 442 U_CAPI void* U_EXPORT2 443 uhash_iremove(UHashtable *hash, 444 int32_t key); 445 446 /** 447 * Remove an item from a UHashtable stored by uhash_puti(). 448 * @param hash The target UHashtable. 449 * @param key An key stored in a hashtable 450 * @return The item removed, or 0 if not found. 451 */ 452 U_CAPI int32_t U_EXPORT2 453 uhash_removei(UHashtable *hash, 454 const void* key); 455 456 /** 457 * Remove an item from a UHashtable stored by uhash_iputi(). 458 * @param hash The target UHashtable. 459 * @param key An integer key stored in a hashtable 460 * @return The item removed, or 0 if not found. 461 */ 462 U_CAPI int32_t U_EXPORT2 463 uhash_iremovei(UHashtable *hash, 464 int32_t key); 465 466 /** 467 * Remove all items from a UHashtable. 468 * @param hash The target UHashtable. 469 */ 470 U_CAPI void U_EXPORT2 471 uhash_removeAll(UHashtable *hash); 472 473 /** 474 * Locate an element of a UHashtable. The caller must not modify the 475 * returned object. The primary use of this function is to obtain the 476 * stored key when it may not be identical to the search key. For 477 * example, if the compare function is a case-insensitive string 478 * compare, then the hash key may be desired in order to obtain the 479 * canonical case corresponding to a search key. 480 * @param hash The target UHashtable. 481 * @param key A key stored in a hashtable 482 * @return a hash element, or NULL if the key is not found. 483 */ 484 U_CAPI const UHashElement* U_EXPORT2 485 uhash_find(const UHashtable *hash, const void* key); 486 487 /** 488 * Iterate through the elements of a UHashtable. The caller must not 489 * modify the returned object. However, uhash_removeElement() may be 490 * called during iteration to remove an element from the table. 491 * Iteration may safely be resumed afterwards. If uhash_put() is 492 * called during iteration the iteration will then be out of sync and 493 * should be restarted. 494 * @param hash The target UHashtable. 495 * @param pos This should be set to -1 initially, and left untouched 496 * thereafter. 497 * @return a hash element, or NULL if no further key-value pairs 498 * exist in the table. 499 */ 500 U_CAPI const UHashElement* U_EXPORT2 501 uhash_nextElement(const UHashtable *hash, 502 int32_t *pos); 503 504 /** 505 * Remove an element, returned by uhash_nextElement(), from the table. 506 * Iteration may be safely continued afterwards. 507 * @param hash The hashtable 508 * @param e The element, returned by uhash_nextElement(), to remove. 509 * Must not be NULL. Must not be an empty or deleted element (as long 510 * as this was returned by uhash_nextElement() it will not be empty or 511 * deleted). Note: Although this parameter is const, it will be 512 * modified. 513 * @return the value that was removed. 514 */ 515 U_CAPI void* U_EXPORT2 516 uhash_removeElement(UHashtable *hash, const UHashElement* e); 517 518 /******************************************************************** 519 * UHashTok convenience 520 ********************************************************************/ 521 522 /** 523 * Return a UHashTok for an integer. 524 * @param i The given integer 525 * @return a UHashTok for an integer. 526 */ 527 /*U_CAPI UHashTok U_EXPORT2 528 uhash_toki(int32_t i);*/ 529 530 /** 531 * Return a UHashTok for a pointer. 532 * @param p The given pointer 533 * @return a UHashTok for a pointer. 534 */ 535 /*U_CAPI UHashTok U_EXPORT2 536 uhash_tokp(void* p);*/ 537 538 /******************************************************************** 539 * UChar* and char* Support Functions 540 ********************************************************************/ 541 542 /** 543 * Generate a hash code for a null-terminated UChar* string. If the 544 * string is not null-terminated do not use this function. Use 545 * together with uhash_compareUChars. 546 * @param key The string (const UChar*) to hash. 547 * @return A hash code for the key. 548 */ 549 U_CAPI int32_t U_EXPORT2 550 uhash_hashUChars(const UHashTok key); 551 552 /** 553 * Generate a hash code for a null-terminated char* string. If the 554 * string is not null-terminated do not use this function. Use 555 * together with uhash_compareChars. 556 * @param key The string (const char*) to hash. 557 * @return A hash code for the key. 558 */ 559 U_CAPI int32_t U_EXPORT2 560 uhash_hashChars(const UHashTok key); 561 562 /** 563 * Generate a case-insensitive hash code for a null-terminated char* 564 * string. If the string is not null-terminated do not use this 565 * function. Use together with uhash_compareIChars. 566 * @param key The string (const char*) to hash. 567 * @return A hash code for the key. 568 */ 569 U_CAPI int32_t U_EXPORT2 570 uhash_hashIChars(const UHashTok key); 571 572 /** 573 * Comparator for null-terminated UChar* strings. Use together with 574 * uhash_hashUChars. 575 * @param key1 The string for comparison 576 * @param key2 The string for comparison 577 * @return true if key1 and key2 are equal, return false otherwise. 578 */ 579 U_CAPI UBool U_EXPORT2 580 uhash_compareUChars(const UHashTok key1, const UHashTok key2); 581 582 /** 583 * Comparator for null-terminated char* strings. Use together with 584 * uhash_hashChars. 585 * @param key1 The string for comparison 586 * @param key2 The string for comparison 587 * @return true if key1 and key2 are equal, return false otherwise. 588 */ 589 U_CAPI UBool U_EXPORT2 590 uhash_compareChars(const UHashTok key1, const UHashTok key2); 591 592 /** 593 * Case-insensitive comparator for null-terminated char* strings. Use 594 * together with uhash_hashIChars. 595 * @param key1 The string for comparison 596 * @param key2 The string for comparison 597 * @return true if key1 and key2 are equal, return false otherwise. 598 */ 599 U_CAPI UBool U_EXPORT2 600 uhash_compareIChars(const UHashTok key1, const UHashTok key2); 601 602 /******************************************************************** 603 * UnicodeString Support Functions 604 ********************************************************************/ 605 606 /** 607 * Hash function for UnicodeString* keys. 608 * @param key The string (const char*) to hash. 609 * @return A hash code for the key. 610 */ 611 U_CAPI int32_t U_EXPORT2 612 uhash_hashUnicodeString(const UElement key); 613 614 /** 615 * Hash function for UnicodeString* keys (case insensitive). 616 * Make sure to use together with uhash_compareCaselessUnicodeString. 617 * @param key The string (const char*) to hash. 618 * @return A hash code for the key. 619 */ 620 U_CAPI int32_t U_EXPORT2 621 uhash_hashCaselessUnicodeString(const UElement key); 622 623 /******************************************************************** 624 * int32_t Support Functions 625 ********************************************************************/ 626 627 /** 628 * Hash function for 32-bit integer keys. 629 * @param key The string (const char*) to hash. 630 * @return A hash code for the key. 631 */ 632 U_CAPI int32_t U_EXPORT2 633 uhash_hashLong(const UHashTok key); 634 635 /** 636 * Comparator function for 32-bit integer keys. 637 * @param key1 The integer for comparison 638 * @param Key2 The integer for comparison 639 * @return true if key1 and key2 are equal, return false otherwise 640 */ 641 U_CAPI UBool U_EXPORT2 642 uhash_compareLong(const UHashTok key1, const UHashTok key2); 643 644 /******************************************************************** 645 * Other Support Functions 646 ********************************************************************/ 647 648 /** 649 * Deleter for Hashtable objects. 650 * @param obj The object to be deleted 651 */ 652 U_CAPI void U_EXPORT2 653 uhash_deleteHashtable(void *obj); 654 655 /* Use uprv_free() itself as a deleter for any key or value allocated using uprv_malloc. */ 656 657 /** 658 * Checks if the given hash tables are equal or not. 659 * @param hash1 660 * @param hash2 661 * @return true if the hashtables are equal and false if not. 662 */ 663 U_CAPI UBool U_EXPORT2 664 uhash_equals(const UHashtable* hash1, const UHashtable* hash2); 665 666 #endif 667