1 /* -*- mode: C; c-file-style: "gnu" -*- */ 2 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation) 3 * 4 * Copyright (C) 2002 Red Hat, Inc. 5 * Copyright (c) 1991-1993 The Regents of the University of California. 6 * Copyright (c) 1994 Sun Microsystems, Inc. 7 * 8 * Hash table implementation based on generic/tclHash.c from the Tcl 9 * source code. The original Tcl license applies to portions of the 10 * code from tclHash.c; the Tcl license follows this standad D-Bus 11 * license information. 12 * 13 * Licensed under the Academic Free License version 2.1 14 * 15 * This program is free software; you can redistribute it and/or modify 16 * it under the terms of the GNU General Public License as published by 17 * the Free Software Foundation; either version 2 of the License, or 18 * (at your option) any later version. 19 * 20 * This program is distributed in the hope that it will be useful, 21 * but WITHOUT ANY WARRANTY; without even the implied warranty of 22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 23 * GNU General Public License for more details. 24 * 25 * You should have received a copy of the GNU General Public License 26 * along with this program; if not, write to the Free Software 27 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 28 * 29 */ 30 /* 31 * The following copyright applies to code from the Tcl distribution. 32 * 33 * Copyright (c) 1991-1993 The Regents of the University of California. 34 * Copyright (c) 1994 Sun Microsystems, Inc. 35 * 36 * This software is copyrighted by the Regents of the University of 37 * California, Sun Microsystems, Inc., Scriptics Corporation, and 38 * other parties. The following terms apply to all files associated 39 * with the software unless explicitly disclaimed in individual files. 40 * 41 * The authors hereby grant permission to use, copy, modify, 42 * distribute, and license this software and its documentation for any 43 * purpose, provided that existing copyright notices are retained in 44 * all copies and that this notice is included verbatim in any 45 * distributions. No written agreement, license, or royalty fee is 46 * required for any of the authorized uses. Modifications to this 47 * software may be copyrighted by their authors and need not follow 48 * the licensing terms described here, provided that the new terms are 49 * clearly indicated on the first page of each file where they apply. 50 * 51 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY 52 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL 53 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, 54 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED 55 * OF THE POSSIBILITY OF SUCH DAMAGE. 56 * 57 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, 58 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 59 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND 60 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, 61 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE 62 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 63 * 64 * GOVERNMENT USE: If you are acquiring this software on behalf of the 65 * U.S. government, the Government shall have only "Restricted Rights" 66 * in the software and related documentation as defined in the Federal 67 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you 68 * are acquiring the software on behalf of the Department of Defense, 69 * the software shall be classified as "Commercial Computer Software" 70 * and the Government shall have only "Restricted Rights" as defined 71 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the 72 * foregoing, the authors grant the U.S. Government and others acting 73 * in its behalf permission to use and distribute the software in 74 * accordance with the terms specified in this license. 75 */ 76 77 #include "dbus-hash.h" 78 #include "dbus-internals.h" 79 #include "dbus-mempool.h" 80 81 /** 82 * @defgroup DBusHashTable Hash table 83 * @ingroup DBusInternals 84 * @brief DBusHashTable data structure 85 * 86 * Types and functions related to DBusHashTable. 87 */ 88 89 /** 90 * @defgroup DBusHashTableInternals Hash table implementation details 91 * @ingroup DBusInternals 92 * @brief DBusHashTable implementation details 93 * 94 * The guts of DBusHashTable. 95 * 96 * @{ 97 */ 98 99 /** 100 * When there are this many entries per bucket, on average, rebuild 101 * the hash table to make it larger. 102 */ 103 #define REBUILD_MULTIPLIER 3 104 105 /** 106 * Takes a preliminary integer hash value and produces an index into a 107 * hash tables bucket list. The idea is to make it so that 108 * preliminary values that are arbitrarily similar will end up in 109 * different buckets. The hash function was taken from a 110 * random-number generator. (This is used to hash integers.) 111 * 112 * The down_shift drops off the high bits of the hash index, and 113 * decreases as we increase the number of hash buckets (to keep more 114 * range in the hash index). The mask also strips high bits and strips 115 * fewer high bits as the number of hash buckets increases. 116 * I don't understand two things: why is the initial downshift 28 117 * to keep 4 bits when the initial mask is 011 to keep 2 bits, 118 * and why do we have both a mask and a downshift? 119 * 120 */ 121 #define RANDOM_INDEX(table, i) \ 122 (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask) 123 124 /** 125 * Initial number of buckets in hash table (hash table statically 126 * allocates its buckets for this size and below). 127 * The initial mask has to be synced to this. 128 */ 129 #define DBUS_SMALL_HASH_TABLE 4 130 131 /** 132 * Typedef for DBusHashEntry 133 */ 134 typedef struct DBusHashEntry DBusHashEntry; 135 136 /** 137 * @brief Internal representation of a hash entry. 138 * 139 * A single entry (key-value pair) in the hash table. 140 * Internal to hash table implementation. 141 */ 142 struct DBusHashEntry 143 { 144 DBusHashEntry *next; /**< Pointer to next entry in this 145 * hash bucket, or #NULL for end of 146 * chain. 147 */ 148 void *key; /**< Hash key */ 149 void *value; /**< Hash value */ 150 }; 151 152 /** 153 * Function used to find and optionally create a hash entry. 154 */ 155 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table, 156 void *key, 157 dbus_bool_t create_if_not_found, 158 DBusHashEntry ***bucket, 159 DBusPreallocatedHash *preallocated); 160 161 /** 162 * @brief Internals of DBusHashTable. 163 * 164 * Hash table internals. Hash tables are opaque objects, they must be 165 * used via accessor functions. 166 */ 167 struct DBusHashTable { 168 int refcount; /**< Reference count */ 169 170 DBusHashEntry **buckets; /**< Pointer to bucket array. Each 171 * element points to first entry in 172 * bucket's hash chain, or #NULL. 173 */ 174 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE]; 175 /**< Bucket array used for small tables 176 * (to avoid mallocs and frees). 177 */ 178 int n_buckets; /**< Total number of buckets allocated 179 * at **buckets. 180 */ 181 int n_entries; /**< Total number of entries present 182 * in table. 183 */ 184 int hi_rebuild_size; /**< Enlarge table when n_entries gets 185 * to be this large. 186 */ 187 int lo_rebuild_size; /**< Shrink table when n_entries gets 188 * below this. 189 */ 190 int down_shift; /**< Shift count used in hashing 191 * function. Designed to use high- 192 * order bits of randomized keys. 193 */ 194 int mask; /**< Mask value used in hashing 195 * function. 196 */ 197 DBusHashType key_type; /**< Type of keys used in this table */ 198 199 200 DBusFindEntryFunction find_function; /**< Function for finding entries */ 201 202 DBusFreeFunction free_key_function; /**< Function to free keys */ 203 DBusFreeFunction free_value_function; /**< Function to free values */ 204 205 DBusMemPool *entry_pool; /**< Memory pool for hash entries */ 206 }; 207 208 /** 209 * @brief Internals of DBusHashIter. 210 */ 211 typedef struct 212 { 213 DBusHashTable *table; /**< Pointer to table containing entry. */ 214 DBusHashEntry **bucket; /**< Pointer to bucket that points to 215 * first entry in this entry's chain: 216 * used for deleting the entry. 217 */ 218 DBusHashEntry *entry; /**< Current hash entry */ 219 DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */ 220 int next_bucket; /**< index of next bucket */ 221 int n_entries_on_init; /**< used to detect table resize since initialization */ 222 } DBusRealHashIter; 223 224 static DBusHashEntry* find_direct_function (DBusHashTable *table, 225 void *key, 226 dbus_bool_t create_if_not_found, 227 DBusHashEntry ***bucket, 228 DBusPreallocatedHash *preallocated); 229 static DBusHashEntry* find_string_function (DBusHashTable *table, 230 void *key, 231 dbus_bool_t create_if_not_found, 232 DBusHashEntry ***bucket, 233 DBusPreallocatedHash *preallocated); 234 #ifdef DBUS_BUILD_TESTS 235 static DBusHashEntry* find_two_strings_function (DBusHashTable *table, 236 void *key, 237 dbus_bool_t create_if_not_found, 238 DBusHashEntry ***bucket, 239 DBusPreallocatedHash *preallocated); 240 #endif 241 static unsigned int string_hash (const char *str); 242 #ifdef DBUS_BUILD_TESTS 243 static unsigned int two_strings_hash (const char *str); 244 #endif 245 static void rebuild_table (DBusHashTable *table); 246 static DBusHashEntry* alloc_entry (DBusHashTable *table); 247 static void remove_entry (DBusHashTable *table, 248 DBusHashEntry **bucket, 249 DBusHashEntry *entry); 250 static void free_entry (DBusHashTable *table, 251 DBusHashEntry *entry); 252 static void free_entry_data (DBusHashTable *table, 253 DBusHashEntry *entry); 254 255 256 /** @} */ 257 258 /** 259 * @addtogroup DBusHashTable 260 * @{ 261 */ 262 263 /** 264 * @typedef DBusHashIter 265 * 266 * Public opaque hash table iterator object. 267 */ 268 269 /** 270 * @typedef DBusHashTable 271 * 272 * Public opaque hash table object. 273 */ 274 275 /** 276 * @typedef DBusHashType 277 * 278 * Indicates the type of a key in the hash table. 279 */ 280 281 /** 282 * Constructs a new hash table. Should be freed with 283 * _dbus_hash_table_unref(). If memory cannot be 284 * allocated for the hash table, returns #NULL. 285 * 286 * @param type the type of hash key to use. 287 * @param key_free_function function to free hash keys. 288 * @param value_free_function function to free hash values. 289 * @returns a new DBusHashTable or #NULL if no memory. 290 */ 291 DBusHashTable* 292 _dbus_hash_table_new (DBusHashType type, 293 DBusFreeFunction key_free_function, 294 DBusFreeFunction value_free_function) 295 { 296 DBusHashTable *table; 297 DBusMemPool *entry_pool; 298 299 table = dbus_new0 (DBusHashTable, 1); 300 if (table == NULL) 301 return NULL; 302 303 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE); 304 if (entry_pool == NULL) 305 { 306 dbus_free (table); 307 return NULL; 308 } 309 310 table->refcount = 1; 311 table->entry_pool = entry_pool; 312 313 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets)); 314 315 table->buckets = table->static_buckets; 316 table->n_buckets = DBUS_SMALL_HASH_TABLE; 317 table->n_entries = 0; 318 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER; 319 table->lo_rebuild_size = 0; 320 table->down_shift = 28; 321 table->mask = 3; 322 table->key_type = type; 323 324 _dbus_assert (table->mask < table->n_buckets); 325 326 switch (table->key_type) 327 { 328 case DBUS_HASH_INT: 329 case DBUS_HASH_POINTER: 330 case DBUS_HASH_ULONG: 331 table->find_function = find_direct_function; 332 break; 333 case DBUS_HASH_STRING: 334 table->find_function = find_string_function; 335 break; 336 case DBUS_HASH_TWO_STRINGS: 337 #ifdef DBUS_BUILD_TESTS 338 table->find_function = find_two_strings_function; 339 #endif 340 break; 341 default: 342 _dbus_assert_not_reached ("Unknown hash table type"); 343 break; 344 } 345 346 table->free_key_function = key_free_function; 347 table->free_value_function = value_free_function; 348 349 return table; 350 } 351 352 353 /** 354 * Increments the reference count for a hash table. 355 * 356 * @param table the hash table to add a reference to. 357 * @returns the hash table. 358 */ 359 DBusHashTable * 360 _dbus_hash_table_ref (DBusHashTable *table) 361 { 362 table->refcount += 1; 363 364 return table; 365 } 366 367 /** 368 * Decrements the reference count for a hash table, 369 * freeing the hash table if the count reaches zero. 370 * 371 * @param table the hash table to remove a reference from. 372 */ 373 void 374 _dbus_hash_table_unref (DBusHashTable *table) 375 { 376 table->refcount -= 1; 377 378 if (table->refcount == 0) 379 { 380 #if 0 381 DBusHashEntry *entry; 382 DBusHashEntry *next; 383 int i; 384 385 /* Free the entries in the table. */ 386 for (i = 0; i < table->n_buckets; i++) 387 { 388 entry = table->buckets[i]; 389 while (entry != NULL) 390 { 391 next = entry->next; 392 393 free_entry (table, entry); 394 395 entry = next; 396 } 397 } 398 #else 399 DBusHashEntry *entry; 400 int i; 401 402 /* Free the entries in the table. */ 403 for (i = 0; i < table->n_buckets; i++) 404 { 405 entry = table->buckets[i]; 406 while (entry != NULL) 407 { 408 free_entry_data (table, entry); 409 410 entry = entry->next; 411 } 412 } 413 /* We can do this very quickly with memory pools ;-) */ 414 _dbus_mem_pool_free (table->entry_pool); 415 #endif 416 417 /* Free the bucket array, if it was dynamically allocated. */ 418 if (table->buckets != table->static_buckets) 419 dbus_free (table->buckets); 420 421 dbus_free (table); 422 } 423 } 424 425 /** 426 * Removed all entries from a hash table. 427 * 428 * @param table the hash table to remove all entries from. 429 */ 430 void 431 _dbus_hash_table_remove_all (DBusHashTable *table) 432 { 433 DBusHashIter iter; 434 _dbus_hash_iter_init (table, &iter); 435 while (_dbus_hash_iter_next (&iter)) 436 { 437 _dbus_hash_iter_remove_entry(&iter); 438 } 439 } 440 441 static DBusHashEntry* 442 alloc_entry (DBusHashTable *table) 443 { 444 DBusHashEntry *entry; 445 446 entry = _dbus_mem_pool_alloc (table->entry_pool); 447 448 return entry; 449 } 450 451 static void 452 free_entry_data (DBusHashTable *table, 453 DBusHashEntry *entry) 454 { 455 if (table->free_key_function) 456 (* table->free_key_function) (entry->key); 457 if (table->free_value_function) 458 (* table->free_value_function) (entry->value); 459 } 460 461 static void 462 free_entry (DBusHashTable *table, 463 DBusHashEntry *entry) 464 { 465 free_entry_data (table, entry); 466 _dbus_mem_pool_dealloc (table->entry_pool, entry); 467 } 468 469 static void 470 remove_entry (DBusHashTable *table, 471 DBusHashEntry **bucket, 472 DBusHashEntry *entry) 473 { 474 _dbus_assert (table != NULL); 475 _dbus_assert (bucket != NULL); 476 _dbus_assert (*bucket != NULL); 477 _dbus_assert (entry != NULL); 478 479 if (*bucket == entry) 480 *bucket = entry->next; 481 else 482 { 483 DBusHashEntry *prev; 484 prev = *bucket; 485 486 while (prev->next != entry) 487 prev = prev->next; 488 489 _dbus_assert (prev != NULL); 490 491 prev->next = entry->next; 492 } 493 494 table->n_entries -= 1; 495 free_entry (table, entry); 496 } 497 498 /** 499 * Initializes a hash table iterator. To iterate over all entries in a 500 * hash table, use the following code (the printf assumes a hash 501 * from strings to strings obviously): 502 * 503 * @code 504 * DBusHashIter iter; 505 * 506 * _dbus_hash_iter_init (table, &iter); 507 * while (_dbus_hash_iter_next (&iter)) 508 * { 509 * printf ("The first key is %s and value is %s\n", 510 * _dbus_hash_iter_get_string_key (&iter), 511 * _dbus_hash_iter_get_value (&iter)); 512 * } 513 * 514 * 515 * @endcode 516 * 517 * The iterator is initialized pointing "one before" the first hash 518 * entry. The first call to _dbus_hash_iter_next() moves it onto 519 * the first valid entry or returns #FALSE if the hash table is 520 * empty. Subsequent calls move to the next valid entry or return 521 * #FALSE if there are no more entries. 522 * 523 * Note that it is guaranteed to be safe to remove a hash entry during 524 * iteration, but it is not safe to add a hash entry. 525 * 526 * @param table the hash table to iterate over. 527 * @param iter the iterator to initialize. 528 */ 529 void 530 _dbus_hash_iter_init (DBusHashTable *table, 531 DBusHashIter *iter) 532 { 533 DBusRealHashIter *real; 534 535 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 536 537 real = (DBusRealHashIter*) iter; 538 539 real->table = table; 540 real->bucket = NULL; 541 real->entry = NULL; 542 real->next_entry = NULL; 543 real->next_bucket = 0; 544 real->n_entries_on_init = table->n_entries; 545 } 546 547 /** 548 * Move the hash iterator forward one step, to the next hash entry. 549 * The documentation for _dbus_hash_iter_init() explains in more 550 * detail. 551 * 552 * @param iter the iterator to move forward. 553 * @returns #FALSE if there are no more entries to move to. 554 */ 555 dbus_bool_t 556 _dbus_hash_iter_next (DBusHashIter *iter) 557 { 558 DBusRealHashIter *real; 559 560 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 561 562 real = (DBusRealHashIter*) iter; 563 564 /* if this assertion failed someone probably added hash entries 565 * during iteration, which is bad. 566 */ 567 _dbus_assert (real->n_entries_on_init >= real->table->n_entries); 568 569 /* Remember that real->entry may have been deleted */ 570 571 while (real->next_entry == NULL) 572 { 573 if (real->next_bucket >= real->table->n_buckets) 574 { 575 /* invalidate iter and return false */ 576 real->entry = NULL; 577 real->table = NULL; 578 real->bucket = NULL; 579 return FALSE; 580 } 581 582 real->bucket = &(real->table->buckets[real->next_bucket]); 583 real->next_entry = *(real->bucket); 584 real->next_bucket += 1; 585 } 586 587 _dbus_assert (real->next_entry != NULL); 588 _dbus_assert (real->bucket != NULL); 589 590 real->entry = real->next_entry; 591 real->next_entry = real->entry->next; 592 593 return TRUE; 594 } 595 596 /** 597 * Removes the current entry from the hash table. 598 * If a key_free_function or value_free_function 599 * was provided to _dbus_hash_table_new(), 600 * frees the key and/or value for this entry. 601 * 602 * @param iter the hash table iterator. 603 */ 604 void 605 _dbus_hash_iter_remove_entry (DBusHashIter *iter) 606 { 607 DBusRealHashIter *real; 608 609 real = (DBusRealHashIter*) iter; 610 611 _dbus_assert (real->table != NULL); 612 _dbus_assert (real->entry != NULL); 613 _dbus_assert (real->bucket != NULL); 614 615 remove_entry (real->table, real->bucket, real->entry); 616 617 real->entry = NULL; /* make it crash if you try to use this entry */ 618 } 619 620 /** 621 * Gets the value of the current entry. 622 * 623 * @param iter the hash table iterator. 624 */ 625 void* 626 _dbus_hash_iter_get_value (DBusHashIter *iter) 627 { 628 DBusRealHashIter *real; 629 630 real = (DBusRealHashIter*) iter; 631 632 _dbus_assert (real->table != NULL); 633 _dbus_assert (real->entry != NULL); 634 635 return real->entry->value; 636 } 637 638 /** 639 * Sets the value of the current entry. 640 * If the hash table has a value_free_function 641 * it will be used to free the previous value. 642 * The hash table will own the passed-in value 643 * (it will not be copied). 644 * 645 * @param iter the hash table iterator. 646 * @param value the new value. 647 */ 648 void 649 _dbus_hash_iter_set_value (DBusHashIter *iter, 650 void *value) 651 { 652 DBusRealHashIter *real; 653 654 real = (DBusRealHashIter*) iter; 655 656 _dbus_assert (real->table != NULL); 657 _dbus_assert (real->entry != NULL); 658 659 if (real->table->free_value_function && value != real->entry->value) 660 (* real->table->free_value_function) (real->entry->value); 661 662 real->entry->value = value; 663 } 664 665 /** 666 * Gets the key for the current entry. 667 * Only works for hash tables of type #DBUS_HASH_INT. 668 * 669 * @param iter the hash table iterator. 670 */ 671 int 672 _dbus_hash_iter_get_int_key (DBusHashIter *iter) 673 { 674 DBusRealHashIter *real; 675 676 real = (DBusRealHashIter*) iter; 677 678 _dbus_assert (real->table != NULL); 679 _dbus_assert (real->entry != NULL); 680 681 return _DBUS_POINTER_TO_INT (real->entry->key); 682 } 683 684 /** 685 * Gets the key for the current entry. 686 * Only works for hash tables of type #DBUS_HASH_ULONG. 687 * 688 * @param iter the hash table iterator. 689 */ 690 unsigned long 691 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter) 692 { 693 DBusRealHashIter *real; 694 695 real = (DBusRealHashIter*) iter; 696 697 _dbus_assert (real->table != NULL); 698 _dbus_assert (real->entry != NULL); 699 700 return (unsigned long) real->entry->key; 701 } 702 703 /** 704 * Gets the key for the current entry. 705 * Only works for hash tables of type #DBUS_HASH_STRING 706 * @param iter the hash table iterator. 707 */ 708 const char* 709 _dbus_hash_iter_get_string_key (DBusHashIter *iter) 710 { 711 DBusRealHashIter *real; 712 713 real = (DBusRealHashIter*) iter; 714 715 _dbus_assert (real->table != NULL); 716 _dbus_assert (real->entry != NULL); 717 718 return real->entry->key; 719 } 720 721 #ifdef DBUS_BUILD_TESTS 722 /** 723 * Gets the key for the current entry. 724 * Only works for hash tables of type #DBUS_HASH_TWO_STRINGS 725 * @param iter the hash table iterator. 726 */ 727 const char* 728 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter) 729 { 730 DBusRealHashIter *real; 731 732 real = (DBusRealHashIter*) iter; 733 734 _dbus_assert (real->table != NULL); 735 _dbus_assert (real->entry != NULL); 736 737 return real->entry->key; 738 } 739 #endif /* DBUS_BUILD_TESTS */ 740 741 /** 742 * A low-level but efficient interface for manipulating the hash 743 * table. It's efficient because you can get, set, and optionally 744 * create the hash entry while only running the hash function one 745 * time. 746 * 747 * Note that while calling _dbus_hash_iter_next() on the iterator 748 * filled in by this function may work, it's completely 749 * undefined which entries are after this iter and which 750 * are before it. So it would be silly to iterate using this 751 * iterator. 752 * 753 * If the hash entry is created, its value will be initialized 754 * to all bits zero. 755 * 756 * #FALSE may be returned due to memory allocation failure, or 757 * because create_if_not_found was #FALSE and the entry 758 * did not exist. 759 * 760 * If create_if_not_found is #TRUE and the entry is created, the hash 761 * table takes ownership of the key that's passed in. 762 * 763 * For a hash table of type #DBUS_HASH_INT, cast the int 764 * key to the key parameter using #_DBUS_INT_TO_POINTER(). 765 * 766 * @param table the hash table. 767 * @param key the hash key. 768 * @param create_if_not_found if #TRUE, create the entry if it didn't exist. 769 * @param iter the iterator to initialize. 770 * @returns #TRUE if the hash entry now exists (and the iterator is thus valid). 771 */ 772 dbus_bool_t 773 _dbus_hash_iter_lookup (DBusHashTable *table, 774 void *key, 775 dbus_bool_t create_if_not_found, 776 DBusHashIter *iter) 777 { 778 DBusRealHashIter *real; 779 DBusHashEntry *entry; 780 DBusHashEntry **bucket; 781 782 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 783 784 real = (DBusRealHashIter*) iter; 785 786 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL); 787 788 if (entry == NULL) 789 return FALSE; 790 791 real->table = table; 792 real->bucket = bucket; 793 real->entry = entry; 794 real->next_entry = entry->next; 795 real->next_bucket = (bucket - table->buckets) + 1; 796 real->n_entries_on_init = table->n_entries; 797 798 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket); 799 800 return TRUE; 801 } 802 803 static void 804 add_allocated_entry (DBusHashTable *table, 805 DBusHashEntry *entry, 806 unsigned int idx, 807 void *key, 808 DBusHashEntry ***bucket) 809 { 810 DBusHashEntry **b; 811 812 entry->key = key; 813 814 b = &(table->buckets[idx]); 815 entry->next = *b; 816 *b = entry; 817 818 if (bucket) 819 *bucket = b; 820 821 table->n_entries += 1; 822 823 /* note we ONLY rebuild when ADDING - because you can iterate over a 824 * table and remove entries safely. 825 */ 826 if (table->n_entries >= table->hi_rebuild_size || 827 table->n_entries < table->lo_rebuild_size) 828 rebuild_table (table); 829 } 830 831 static DBusHashEntry* 832 add_entry (DBusHashTable *table, 833 unsigned int idx, 834 void *key, 835 DBusHashEntry ***bucket, 836 DBusPreallocatedHash *preallocated) 837 { 838 DBusHashEntry *entry; 839 840 if (preallocated == NULL) 841 { 842 entry = alloc_entry (table); 843 if (entry == NULL) 844 { 845 if (bucket) 846 *bucket = NULL; 847 return NULL; 848 } 849 } 850 else 851 { 852 entry = (DBusHashEntry*) preallocated; 853 } 854 855 add_allocated_entry (table, entry, idx, key, bucket); 856 857 return entry; 858 } 859 860 /* This is g_str_hash from GLib which was 861 * extensively discussed/tested/profiled 862 */ 863 static unsigned int 864 string_hash (const char *str) 865 { 866 const char *p = str; 867 unsigned int h = *p; 868 869 if (h) 870 for (p += 1; *p != '\0'; p++) 871 h = (h << 5) - h + *p; 872 873 return h; 874 } 875 876 #ifdef DBUS_BUILD_TESTS 877 /* This hashes a memory block with two nul-terminated strings 878 * in it, used in dbus-object-registry.c at the moment. 879 */ 880 static unsigned int 881 two_strings_hash (const char *str) 882 { 883 const char *p = str; 884 unsigned int h = *p; 885 886 if (h) 887 for (p += 1; *p != '\0'; p++) 888 h = (h << 5) - h + *p; 889 890 for (p += 1; *p != '\0'; p++) 891 h = (h << 5) - h + *p; 892 893 return h; 894 } 895 #endif /* DBUS_BUILD_TESTS */ 896 897 /** Key comparison function */ 898 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b); 899 900 static DBusHashEntry* 901 find_generic_function (DBusHashTable *table, 902 void *key, 903 unsigned int idx, 904 KeyCompareFunc compare_func, 905 dbus_bool_t create_if_not_found, 906 DBusHashEntry ***bucket, 907 DBusPreallocatedHash *preallocated) 908 { 909 DBusHashEntry *entry; 910 911 if (bucket) 912 *bucket = NULL; 913 914 /* Search all of the entries in this bucket. */ 915 entry = table->buckets[idx]; 916 while (entry != NULL) 917 { 918 if ((compare_func == NULL && key == entry->key) || 919 (compare_func != NULL && (* compare_func) (key, entry->key) == 0)) 920 { 921 if (bucket) 922 *bucket = &(table->buckets[idx]); 923 924 if (preallocated) 925 _dbus_hash_table_free_preallocated_entry (table, preallocated); 926 927 return entry; 928 } 929 930 entry = entry->next; 931 } 932 933 if (create_if_not_found) 934 entry = add_entry (table, idx, key, bucket, preallocated); 935 else if (preallocated) 936 _dbus_hash_table_free_preallocated_entry (table, preallocated); 937 938 return entry; 939 } 940 941 static DBusHashEntry* 942 find_string_function (DBusHashTable *table, 943 void *key, 944 dbus_bool_t create_if_not_found, 945 DBusHashEntry ***bucket, 946 DBusPreallocatedHash *preallocated) 947 { 948 unsigned int idx; 949 950 idx = string_hash (key) & table->mask; 951 952 return find_generic_function (table, key, idx, 953 (KeyCompareFunc) strcmp, create_if_not_found, bucket, 954 preallocated); 955 } 956 957 #ifdef DBUS_BUILD_TESTS 958 static int 959 two_strings_cmp (const char *a, 960 const char *b) 961 { 962 size_t len_a; 963 size_t len_b; 964 int res; 965 966 res = strcmp (a, b); 967 if (res != 0) 968 return res; 969 970 len_a = strlen (a); 971 len_b = strlen (b); 972 973 return strcmp (a + len_a + 1, b + len_b + 1); 974 } 975 #endif 976 977 #ifdef DBUS_BUILD_TESTS 978 static DBusHashEntry* 979 find_two_strings_function (DBusHashTable *table, 980 void *key, 981 dbus_bool_t create_if_not_found, 982 DBusHashEntry ***bucket, 983 DBusPreallocatedHash *preallocated) 984 { 985 unsigned int idx; 986 987 idx = two_strings_hash (key) & table->mask; 988 989 return find_generic_function (table, key, idx, 990 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket, 991 preallocated); 992 } 993 #endif /* DBUS_BUILD_TESTS */ 994 995 static DBusHashEntry* 996 find_direct_function (DBusHashTable *table, 997 void *key, 998 dbus_bool_t create_if_not_found, 999 DBusHashEntry ***bucket, 1000 DBusPreallocatedHash *preallocated) 1001 { 1002 unsigned int idx; 1003 1004 idx = RANDOM_INDEX (table, key) & table->mask; 1005 1006 1007 return find_generic_function (table, key, idx, 1008 NULL, create_if_not_found, bucket, 1009 preallocated); 1010 } 1011 1012 static void 1013 rebuild_table (DBusHashTable *table) 1014 { 1015 int old_size; 1016 int new_buckets; 1017 DBusHashEntry **old_buckets; 1018 DBusHashEntry **old_chain; 1019 DBusHashEntry *entry; 1020 dbus_bool_t growing; 1021 1022 /* 1023 * Allocate and initialize the new bucket array, and set up 1024 * hashing constants for new array size. 1025 */ 1026 1027 growing = table->n_entries >= table->hi_rebuild_size; 1028 1029 old_size = table->n_buckets; 1030 old_buckets = table->buckets; 1031 1032 if (growing) 1033 { 1034 /* overflow paranoia */ 1035 if (table->n_buckets < _DBUS_INT_MAX / 4 && 1036 table->down_shift >= 0) 1037 new_buckets = table->n_buckets * 4; 1038 else 1039 return; /* can't grow anymore */ 1040 } 1041 else 1042 { 1043 new_buckets = table->n_buckets / 4; 1044 if (new_buckets < DBUS_SMALL_HASH_TABLE) 1045 return; /* don't bother shrinking this far */ 1046 } 1047 1048 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets); 1049 if (table->buckets == NULL) 1050 { 1051 /* out of memory, yay - just don't reallocate, the table will 1052 * still work, albeit more slowly. 1053 */ 1054 table->buckets = old_buckets; 1055 return; 1056 } 1057 1058 table->n_buckets = new_buckets; 1059 1060 if (growing) 1061 { 1062 table->lo_rebuild_size = table->hi_rebuild_size; 1063 table->hi_rebuild_size *= 4; 1064 1065 table->down_shift -= 2; /* keep 2 more high bits */ 1066 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */ 1067 } 1068 else 1069 { 1070 table->hi_rebuild_size = table->lo_rebuild_size; 1071 table->lo_rebuild_size /= 4; 1072 1073 table->down_shift += 2; /* keep 2 fewer high bits */ 1074 table->mask = table->mask >> 2; /* keep 2 fewer high bits */ 1075 } 1076 1077 #if 0 1078 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", 1079 growing ? "GROW" : "SHRINK", 1080 table->lo_rebuild_size, 1081 table->hi_rebuild_size, 1082 table->down_shift, 1083 table->mask); 1084 #endif 1085 1086 _dbus_assert (table->lo_rebuild_size >= 0); 1087 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size); 1088 _dbus_assert (table->mask != 0); 1089 /* the mask is essentially the max index */ 1090 _dbus_assert (table->mask < table->n_buckets); 1091 1092 /* 1093 * Rehash all of the existing entries into the new bucket array. 1094 */ 1095 1096 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++) 1097 { 1098 for (entry = *old_chain; entry != NULL; entry = *old_chain) 1099 { 1100 unsigned int idx; 1101 DBusHashEntry **bucket; 1102 1103 *old_chain = entry->next; 1104 switch (table->key_type) 1105 { 1106 case DBUS_HASH_STRING: 1107 idx = string_hash (entry->key) & table->mask; 1108 break; 1109 case DBUS_HASH_TWO_STRINGS: 1110 #ifdef DBUS_BUILD_TESTS 1111 idx = two_strings_hash (entry->key) & table->mask; 1112 #else 1113 idx = 0; 1114 _dbus_assert_not_reached ("two-strings is not enabled"); 1115 #endif 1116 break; 1117 case DBUS_HASH_INT: 1118 case DBUS_HASH_ULONG: 1119 case DBUS_HASH_POINTER: 1120 idx = RANDOM_INDEX (table, entry->key); 1121 break; 1122 default: 1123 idx = 0; 1124 _dbus_assert_not_reached ("Unknown hash table type"); 1125 break; 1126 } 1127 1128 bucket = &(table->buckets[idx]); 1129 entry->next = *bucket; 1130 *bucket = entry; 1131 } 1132 } 1133 1134 /* Free the old bucket array, if it was dynamically allocated. */ 1135 1136 if (old_buckets != table->static_buckets) 1137 dbus_free (old_buckets); 1138 } 1139 1140 /** 1141 * Looks up the value for a given string in a hash table 1142 * of type #DBUS_HASH_STRING. Returns %NULL if the value 1143 * is not present. (A not-present entry is indistinguishable 1144 * from an entry with a value of %NULL.) 1145 * @param table the hash table. 1146 * @param key the string to look up. 1147 * @returns the value of the hash entry. 1148 */ 1149 void* 1150 _dbus_hash_table_lookup_string (DBusHashTable *table, 1151 const char *key) 1152 { 1153 DBusHashEntry *entry; 1154 1155 _dbus_assert (table->key_type == DBUS_HASH_STRING); 1156 1157 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 1158 1159 if (entry) 1160 return entry->value; 1161 else 1162 return NULL; 1163 } 1164 1165 #ifdef DBUS_BUILD_TESTS 1166 /** 1167 * Looks up the value for a given string in a hash table 1168 * of type #DBUS_HASH_TWO_STRINGS. Returns %NULL if the value 1169 * is not present. (A not-present entry is indistinguishable 1170 * from an entry with a value of %NULL.) 1171 * @param table the hash table. 1172 * @param key the string to look up. 1173 * @returns the value of the hash entry. 1174 */ 1175 void* 1176 _dbus_hash_table_lookup_two_strings (DBusHashTable *table, 1177 const char *key) 1178 { 1179 DBusHashEntry *entry; 1180 1181 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 1182 1183 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 1184 1185 if (entry) 1186 return entry->value; 1187 else 1188 return NULL; 1189 } 1190 #endif /* DBUS_BUILD_TESTS */ 1191 1192 /** 1193 * Looks up the value for a given integer in a hash table 1194 * of type #DBUS_HASH_INT. Returns %NULL if the value 1195 * is not present. (A not-present entry is indistinguishable 1196 * from an entry with a value of %NULL.) 1197 * @param table the hash table. 1198 * @param key the integer to look up. 1199 * @returns the value of the hash entry. 1200 */ 1201 void* 1202 _dbus_hash_table_lookup_int (DBusHashTable *table, 1203 int key) 1204 { 1205 DBusHashEntry *entry; 1206 1207 _dbus_assert (table->key_type == DBUS_HASH_INT); 1208 1209 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL); 1210 1211 if (entry) 1212 return entry->value; 1213 else 1214 return NULL; 1215 } 1216 1217 #ifdef DBUS_BUILD_TESTS 1218 /* disabled since it's only used for testing */ 1219 /** 1220 * Looks up the value for a given integer in a hash table 1221 * of type #DBUS_HASH_POINTER. Returns %NULL if the value 1222 * is not present. (A not-present entry is indistinguishable 1223 * from an entry with a value of %NULL.) 1224 * @param table the hash table. 1225 * @param key the integer to look up. 1226 * @returns the value of the hash entry. 1227 */ 1228 void* 1229 _dbus_hash_table_lookup_pointer (DBusHashTable *table, 1230 void *key) 1231 { 1232 DBusHashEntry *entry; 1233 1234 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 1235 1236 entry = (* table->find_function) (table, key, FALSE, NULL, NULL); 1237 1238 if (entry) 1239 return entry->value; 1240 else 1241 return NULL; 1242 } 1243 #endif /* DBUS_BUILD_TESTS */ 1244 1245 /** 1246 * Looks up the value for a given integer in a hash table 1247 * of type #DBUS_HASH_ULONG. Returns %NULL if the value 1248 * is not present. (A not-present entry is indistinguishable 1249 * from an entry with a value of %NULL.) 1250 * @param table the hash table. 1251 * @param key the integer to look up. 1252 * @returns the value of the hash entry. 1253 */ 1254 void* 1255 _dbus_hash_table_lookup_ulong (DBusHashTable *table, 1256 unsigned long key) 1257 { 1258 DBusHashEntry *entry; 1259 1260 _dbus_assert (table->key_type == DBUS_HASH_ULONG); 1261 1262 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL); 1263 1264 if (entry) 1265 return entry->value; 1266 else 1267 return NULL; 1268 } 1269 1270 /** 1271 * Removes the hash entry for the given key. If no hash entry 1272 * for the key exists, does nothing. 1273 * 1274 * @param table the hash table. 1275 * @param key the hash key. 1276 * @returns #TRUE if the entry existed 1277 */ 1278 dbus_bool_t 1279 _dbus_hash_table_remove_string (DBusHashTable *table, 1280 const char *key) 1281 { 1282 DBusHashEntry *entry; 1283 DBusHashEntry **bucket; 1284 1285 _dbus_assert (table->key_type == DBUS_HASH_STRING); 1286 1287 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 1288 1289 if (entry) 1290 { 1291 remove_entry (table, bucket, entry); 1292 return TRUE; 1293 } 1294 else 1295 return FALSE; 1296 } 1297 1298 #ifdef DBUS_BUILD_TESTS 1299 /** 1300 * Removes the hash entry for the given key. If no hash entry 1301 * for the key exists, does nothing. 1302 * 1303 * @param table the hash table. 1304 * @param key the hash key. 1305 * @returns #TRUE if the entry existed 1306 */ 1307 dbus_bool_t 1308 _dbus_hash_table_remove_two_strings (DBusHashTable *table, 1309 const char *key) 1310 { 1311 DBusHashEntry *entry; 1312 DBusHashEntry **bucket; 1313 1314 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 1315 1316 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 1317 1318 if (entry) 1319 { 1320 remove_entry (table, bucket, entry); 1321 return TRUE; 1322 } 1323 else 1324 return FALSE; 1325 } 1326 #endif /* DBUS_BUILD_TESTS */ 1327 1328 /** 1329 * Removes the hash entry for the given key. If no hash entry 1330 * for the key exists, does nothing. 1331 * 1332 * @param table the hash table. 1333 * @param key the hash key. 1334 * @returns #TRUE if the entry existed 1335 */ 1336 dbus_bool_t 1337 _dbus_hash_table_remove_int (DBusHashTable *table, 1338 int key) 1339 { 1340 DBusHashEntry *entry; 1341 DBusHashEntry **bucket; 1342 1343 _dbus_assert (table->key_type == DBUS_HASH_INT); 1344 1345 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL); 1346 1347 if (entry) 1348 { 1349 remove_entry (table, bucket, entry); 1350 return TRUE; 1351 } 1352 else 1353 return FALSE; 1354 } 1355 1356 #ifdef DBUS_BUILD_TESTS 1357 /* disabled since it's only used for testing */ 1358 /** 1359 * Removes the hash entry for the given key. If no hash entry 1360 * for the key exists, does nothing. 1361 * 1362 * @param table the hash table. 1363 * @param key the hash key. 1364 * @returns #TRUE if the entry existed 1365 */ 1366 dbus_bool_t 1367 _dbus_hash_table_remove_pointer (DBusHashTable *table, 1368 void *key) 1369 { 1370 DBusHashEntry *entry; 1371 DBusHashEntry **bucket; 1372 1373 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 1374 1375 entry = (* table->find_function) (table, key, FALSE, &bucket, NULL); 1376 1377 if (entry) 1378 { 1379 remove_entry (table, bucket, entry); 1380 return TRUE; 1381 } 1382 else 1383 return FALSE; 1384 } 1385 #endif /* DBUS_BUILD_TESTS */ 1386 1387 /** 1388 * Removes the hash entry for the given key. If no hash entry 1389 * for the key exists, does nothing. 1390 * 1391 * @param table the hash table. 1392 * @param key the hash key. 1393 * @returns #TRUE if the entry existed 1394 */ 1395 dbus_bool_t 1396 _dbus_hash_table_remove_ulong (DBusHashTable *table, 1397 unsigned long key) 1398 { 1399 DBusHashEntry *entry; 1400 DBusHashEntry **bucket; 1401 1402 _dbus_assert (table->key_type == DBUS_HASH_ULONG); 1403 1404 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL); 1405 1406 if (entry) 1407 { 1408 remove_entry (table, bucket, entry); 1409 return TRUE; 1410 } 1411 else 1412 return FALSE; 1413 } 1414 1415 /** 1416 * Creates a hash entry with the given key and value. 1417 * The key and value are not copied; they are stored 1418 * in the hash table by reference. If an entry with the 1419 * given key already exists, the previous key and value 1420 * are overwritten (and freed if the hash table has 1421 * a key_free_function and/or value_free_function). 1422 * 1423 * Returns #FALSE if memory for the new hash entry 1424 * can't be allocated. 1425 * 1426 * @param table the hash table. 1427 * @param key the hash entry key. 1428 * @param value the hash entry value. 1429 */ 1430 dbus_bool_t 1431 _dbus_hash_table_insert_string (DBusHashTable *table, 1432 char *key, 1433 void *value) 1434 { 1435 DBusPreallocatedHash *preallocated; 1436 1437 _dbus_assert (table->key_type == DBUS_HASH_STRING); 1438 1439 preallocated = _dbus_hash_table_preallocate_entry (table); 1440 if (preallocated == NULL) 1441 return FALSE; 1442 1443 _dbus_hash_table_insert_string_preallocated (table, preallocated, 1444 key, value); 1445 1446 return TRUE; 1447 } 1448 1449 #ifdef DBUS_BUILD_TESTS 1450 /** 1451 * Creates a hash entry with the given key and value. 1452 * The key and value are not copied; they are stored 1453 * in the hash table by reference. If an entry with the 1454 * given key already exists, the previous key and value 1455 * are overwritten (and freed if the hash table has 1456 * a key_free_function and/or value_free_function). 1457 * 1458 * Returns #FALSE if memory for the new hash entry 1459 * can't be allocated. 1460 * 1461 * @param table the hash table. 1462 * @param key the hash entry key. 1463 * @param value the hash entry value. 1464 */ 1465 dbus_bool_t 1466 _dbus_hash_table_insert_two_strings (DBusHashTable *table, 1467 char *key, 1468 void *value) 1469 { 1470 DBusHashEntry *entry; 1471 1472 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 1473 1474 entry = (* table->find_function) (table, key, TRUE, NULL, NULL); 1475 1476 if (entry == NULL) 1477 return FALSE; /* no memory */ 1478 1479 if (table->free_key_function && entry->key != key) 1480 (* table->free_key_function) (entry->key); 1481 1482 if (table->free_value_function && entry->value != value) 1483 (* table->free_value_function) (entry->value); 1484 1485 entry->key = key; 1486 entry->value = value; 1487 1488 return TRUE; 1489 } 1490 #endif /* DBUS_BUILD_TESTS */ 1491 1492 /** 1493 * Creates a hash entry with the given key and value. 1494 * The key and value are not copied; they are stored 1495 * in the hash table by reference. If an entry with the 1496 * given key already exists, the previous key and value 1497 * are overwritten (and freed if the hash table has 1498 * a key_free_function and/or value_free_function). 1499 * 1500 * Returns #FALSE if memory for the new hash entry 1501 * can't be allocated. 1502 * 1503 * @param table the hash table. 1504 * @param key the hash entry key. 1505 * @param value the hash entry value. 1506 */ 1507 dbus_bool_t 1508 _dbus_hash_table_insert_int (DBusHashTable *table, 1509 int key, 1510 void *value) 1511 { 1512 DBusHashEntry *entry; 1513 1514 _dbus_assert (table->key_type == DBUS_HASH_INT); 1515 1516 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL); 1517 1518 if (entry == NULL) 1519 return FALSE; /* no memory */ 1520 1521 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key)) 1522 (* table->free_key_function) (entry->key); 1523 1524 if (table->free_value_function && entry->value != value) 1525 (* table->free_value_function) (entry->value); 1526 1527 entry->key = _DBUS_INT_TO_POINTER (key); 1528 entry->value = value; 1529 1530 return TRUE; 1531 } 1532 1533 #ifdef DBUS_BUILD_TESTS 1534 /* disabled since it's only used for testing */ 1535 /** 1536 * Creates a hash entry with the given key and value. 1537 * The key and value are not copied; they are stored 1538 * in the hash table by reference. If an entry with the 1539 * given key already exists, the previous key and value 1540 * are overwritten (and freed if the hash table has 1541 * a key_free_function and/or value_free_function). 1542 * 1543 * Returns #FALSE if memory for the new hash entry 1544 * can't be allocated. 1545 * 1546 * @param table the hash table. 1547 * @param key the hash entry key. 1548 * @param value the hash entry value. 1549 */ 1550 dbus_bool_t 1551 _dbus_hash_table_insert_pointer (DBusHashTable *table, 1552 void *key, 1553 void *value) 1554 { 1555 DBusHashEntry *entry; 1556 1557 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 1558 1559 entry = (* table->find_function) (table, key, TRUE, NULL, NULL); 1560 1561 if (entry == NULL) 1562 return FALSE; /* no memory */ 1563 1564 if (table->free_key_function && entry->key != key) 1565 (* table->free_key_function) (entry->key); 1566 1567 if (table->free_value_function && entry->value != value) 1568 (* table->free_value_function) (entry->value); 1569 1570 entry->key = key; 1571 entry->value = value; 1572 1573 return TRUE; 1574 } 1575 #endif /* DBUS_BUILD_TESTS */ 1576 1577 /** 1578 * Creates a hash entry with the given key and value. 1579 * The key and value are not copied; they are stored 1580 * in the hash table by reference. If an entry with the 1581 * given key already exists, the previous key and value 1582 * are overwritten (and freed if the hash table has 1583 * a key_free_function and/or value_free_function). 1584 * 1585 * Returns #FALSE if memory for the new hash entry 1586 * can't be allocated. 1587 * 1588 * @param table the hash table. 1589 * @param key the hash entry key. 1590 * @param value the hash entry value. 1591 */ 1592 dbus_bool_t 1593 _dbus_hash_table_insert_ulong (DBusHashTable *table, 1594 unsigned long key, 1595 void *value) 1596 { 1597 DBusHashEntry *entry; 1598 1599 _dbus_assert (table->key_type == DBUS_HASH_ULONG); 1600 1601 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL); 1602 1603 if (entry == NULL) 1604 return FALSE; /* no memory */ 1605 1606 if (table->free_key_function && entry->key != (void*) key) 1607 (* table->free_key_function) (entry->key); 1608 1609 if (table->free_value_function && entry->value != value) 1610 (* table->free_value_function) (entry->value); 1611 1612 entry->key = (void*) key; 1613 entry->value = value; 1614 1615 return TRUE; 1616 } 1617 1618 /** 1619 * Preallocate an opaque data blob that allows us to insert into the 1620 * hash table at a later time without allocating any memory. 1621 * 1622 * @param table the hash table 1623 * @returns the preallocated data, or #NULL if no memory 1624 */ 1625 DBusPreallocatedHash* 1626 _dbus_hash_table_preallocate_entry (DBusHashTable *table) 1627 { 1628 DBusHashEntry *entry; 1629 1630 entry = alloc_entry (table); 1631 1632 return (DBusPreallocatedHash*) entry; 1633 } 1634 1635 /** 1636 * Frees an opaque DBusPreallocatedHash that was *not* used 1637 * in order to insert into the hash table. 1638 * 1639 * @param table the hash table 1640 * @param preallocated the preallocated data 1641 */ 1642 void 1643 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table, 1644 DBusPreallocatedHash *preallocated) 1645 { 1646 DBusHashEntry *entry; 1647 1648 _dbus_assert (preallocated != NULL); 1649 1650 entry = (DBusHashEntry*) preallocated; 1651 1652 /* Don't use free_entry(), since this entry has no key/data */ 1653 _dbus_mem_pool_dealloc (table->entry_pool, entry); 1654 } 1655 1656 /** 1657 * Inserts a string-keyed entry into the hash table, using a 1658 * preallocated data block from 1659 * _dbus_hash_table_preallocate_entry(). This function cannot fail due 1660 * to lack of memory. The DBusPreallocatedHash object is consumed and 1661 * should not be reused or freed. Otherwise this function works 1662 * just like _dbus_hash_table_insert_string(). 1663 * 1664 * @param table the hash table 1665 * @param preallocated the preallocated data 1666 * @param key the hash key 1667 * @param value the value 1668 */ 1669 void 1670 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table, 1671 DBusPreallocatedHash *preallocated, 1672 char *key, 1673 void *value) 1674 { 1675 DBusHashEntry *entry; 1676 1677 _dbus_assert (table->key_type == DBUS_HASH_STRING); 1678 _dbus_assert (preallocated != NULL); 1679 1680 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated); 1681 1682 _dbus_assert (entry != NULL); 1683 1684 if (table->free_key_function && entry->key != key) 1685 (* table->free_key_function) (entry->key); 1686 1687 if (table->free_value_function && entry->value != value) 1688 (* table->free_value_function) (entry->value); 1689 1690 entry->key = key; 1691 entry->value = value; 1692 } 1693 1694 /** 1695 * Gets the number of hash entries in a hash table. 1696 * 1697 * @param table the hash table. 1698 * @returns the number of entries in the table. 1699 */ 1700 int 1701 _dbus_hash_table_get_n_entries (DBusHashTable *table) 1702 { 1703 return table->n_entries; 1704 } 1705 1706 /** @} */ 1707 1708 #ifdef DBUS_BUILD_TESTS 1709 #include "dbus-test.h" 1710 #include <stdio.h> 1711 1712 /* If you're wondering why the hash table test takes 1713 * forever to run, it's because we call this function 1714 * in inner loops thus making things quadratic. 1715 */ 1716 static int 1717 count_entries (DBusHashTable *table) 1718 { 1719 DBusHashIter iter; 1720 int count; 1721 1722 count = 0; 1723 _dbus_hash_iter_init (table, &iter); 1724 while (_dbus_hash_iter_next (&iter)) 1725 ++count; 1726 1727 _dbus_assert (count == _dbus_hash_table_get_n_entries (table)); 1728 1729 return count; 1730 } 1731 1732 /* Copy the foo\0bar\0 double string thing */ 1733 static char* 1734 _dbus_strdup2 (const char *str) 1735 { 1736 size_t len; 1737 char *copy; 1738 1739 if (str == NULL) 1740 return NULL; 1741 1742 len = strlen (str); 1743 len += strlen ((str + len + 1)); 1744 1745 copy = dbus_malloc (len + 2); 1746 if (copy == NULL) 1747 return NULL; 1748 1749 memcpy (copy, str, len + 2); 1750 1751 return copy; 1752 } 1753 1754 /** 1755 * @ingroup DBusHashTableInternals 1756 * Unit test for DBusHashTable 1757 * @returns #TRUE on success. 1758 */ 1759 dbus_bool_t 1760 _dbus_hash_test (void) 1761 { 1762 int i; 1763 DBusHashTable *table1; 1764 DBusHashTable *table2; 1765 DBusHashTable *table3; 1766 DBusHashTable *table4; 1767 DBusHashIter iter; 1768 #define N_HASH_KEYS 5000 1769 char **keys; 1770 dbus_bool_t ret = FALSE; 1771 1772 keys = dbus_new (char *, N_HASH_KEYS); 1773 if (keys == NULL) 1774 _dbus_assert_not_reached ("no memory"); 1775 1776 for (i = 0; i < N_HASH_KEYS; i++) 1777 { 1778 keys[i] = dbus_malloc (128); 1779 1780 if (keys[i] == NULL) 1781 _dbus_assert_not_reached ("no memory"); 1782 } 1783 1784 printf ("Computing test hash keys...\n"); 1785 i = 0; 1786 while (i < N_HASH_KEYS) 1787 { 1788 int len; 1789 1790 /* all the hash keys are TWO_STRINGS, but 1791 * then we can also use those as regular strings. 1792 */ 1793 1794 len = sprintf (keys[i], "Hash key %d", i); 1795 sprintf (keys[i] + len + 1, "Two string %d", i); 1796 _dbus_assert (*(keys[i] + len) == '\0'); 1797 _dbus_assert (*(keys[i] + len + 1) != '\0'); 1798 ++i; 1799 } 1800 printf ("... done.\n"); 1801 1802 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 1803 dbus_free, dbus_free); 1804 if (table1 == NULL) 1805 goto out; 1806 1807 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 1808 NULL, dbus_free); 1809 if (table2 == NULL) 1810 goto out; 1811 1812 table3 = _dbus_hash_table_new (DBUS_HASH_ULONG, 1813 NULL, dbus_free); 1814 if (table3 == NULL) 1815 goto out; 1816 1817 table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS, 1818 dbus_free, dbus_free); 1819 if (table4 == NULL) 1820 goto out; 1821 1822 1823 /* Insert and remove a bunch of stuff, counting the table in between 1824 * to be sure it's not broken and that iteration works 1825 */ 1826 i = 0; 1827 while (i < 3000) 1828 { 1829 void *value; 1830 char *key; 1831 1832 key = _dbus_strdup (keys[i]); 1833 if (key == NULL) 1834 goto out; 1835 value = _dbus_strdup ("Value!"); 1836 if (value == NULL) 1837 goto out; 1838 1839 if (!_dbus_hash_table_insert_string (table1, 1840 key, value)) 1841 goto out; 1842 1843 value = _dbus_strdup (keys[i]); 1844 if (value == NULL) 1845 goto out; 1846 1847 if (!_dbus_hash_table_insert_int (table2, 1848 i, value)) 1849 goto out; 1850 1851 value = _dbus_strdup (keys[i]); 1852 if (value == NULL) 1853 goto out; 1854 1855 if (!_dbus_hash_table_insert_ulong (table3, 1856 i, value)) 1857 goto out; 1858 1859 key = _dbus_strdup2 (keys[i]); 1860 if (key == NULL) 1861 goto out; 1862 value = _dbus_strdup ("Value!"); 1863 if (value == NULL) 1864 goto out; 1865 1866 if (!_dbus_hash_table_insert_two_strings (table4, 1867 key, value)) 1868 goto out; 1869 1870 _dbus_assert (count_entries (table1) == i + 1); 1871 _dbus_assert (count_entries (table2) == i + 1); 1872 _dbus_assert (count_entries (table3) == i + 1); 1873 _dbus_assert (count_entries (table4) == i + 1); 1874 1875 value = _dbus_hash_table_lookup_string (table1, keys[i]); 1876 _dbus_assert (value != NULL); 1877 _dbus_assert (strcmp (value, "Value!") == 0); 1878 1879 value = _dbus_hash_table_lookup_int (table2, i); 1880 _dbus_assert (value != NULL); 1881 _dbus_assert (strcmp (value, keys[i]) == 0); 1882 1883 value = _dbus_hash_table_lookup_ulong (table3, i); 1884 _dbus_assert (value != NULL); 1885 _dbus_assert (strcmp (value, keys[i]) == 0); 1886 1887 value = _dbus_hash_table_lookup_two_strings (table4, keys[i]); 1888 _dbus_assert (value != NULL); 1889 _dbus_assert (strcmp (value, "Value!") == 0); 1890 1891 ++i; 1892 } 1893 1894 --i; 1895 while (i >= 0) 1896 { 1897 _dbus_hash_table_remove_string (table1, 1898 keys[i]); 1899 1900 _dbus_hash_table_remove_int (table2, i); 1901 1902 _dbus_hash_table_remove_ulong (table3, i); 1903 1904 _dbus_hash_table_remove_two_strings (table4, 1905 keys[i]); 1906 1907 _dbus_assert (count_entries (table1) == i); 1908 _dbus_assert (count_entries (table2) == i); 1909 _dbus_assert (count_entries (table3) == i); 1910 _dbus_assert (count_entries (table4) == i); 1911 1912 --i; 1913 } 1914 1915 _dbus_hash_table_ref (table1); 1916 _dbus_hash_table_ref (table2); 1917 _dbus_hash_table_ref (table3); 1918 _dbus_hash_table_ref (table4); 1919 _dbus_hash_table_unref (table1); 1920 _dbus_hash_table_unref (table2); 1921 _dbus_hash_table_unref (table3); 1922 _dbus_hash_table_unref (table4); 1923 _dbus_hash_table_unref (table1); 1924 _dbus_hash_table_unref (table2); 1925 _dbus_hash_table_unref (table3); 1926 _dbus_hash_table_unref (table4); 1927 table3 = NULL; 1928 1929 /* Insert a bunch of stuff then check 1930 * that iteration works correctly (finds the right 1931 * values, iter_set_value works, etc.) 1932 */ 1933 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 1934 dbus_free, dbus_free); 1935 if (table1 == NULL) 1936 goto out; 1937 1938 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 1939 NULL, dbus_free); 1940 if (table2 == NULL) 1941 goto out; 1942 1943 i = 0; 1944 while (i < 5000) 1945 { 1946 char *key; 1947 void *value; 1948 1949 key = _dbus_strdup (keys[i]); 1950 if (key == NULL) 1951 goto out; 1952 value = _dbus_strdup ("Value!"); 1953 if (value == NULL) 1954 goto out; 1955 1956 if (!_dbus_hash_table_insert_string (table1, 1957 key, value)) 1958 goto out; 1959 1960 value = _dbus_strdup (keys[i]); 1961 if (value == NULL) 1962 goto out; 1963 1964 if (!_dbus_hash_table_insert_int (table2, 1965 i, value)) 1966 goto out; 1967 1968 _dbus_assert (count_entries (table1) == i + 1); 1969 _dbus_assert (count_entries (table2) == i + 1); 1970 1971 ++i; 1972 } 1973 1974 _dbus_hash_iter_init (table1, &iter); 1975 while (_dbus_hash_iter_next (&iter)) 1976 { 1977 const char *key; 1978 void *value; 1979 1980 key = _dbus_hash_iter_get_string_key (&iter); 1981 value = _dbus_hash_iter_get_value (&iter); 1982 1983 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 1984 1985 value = _dbus_strdup ("Different value!"); 1986 if (value == NULL) 1987 goto out; 1988 1989 _dbus_hash_iter_set_value (&iter, value); 1990 1991 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 1992 } 1993 1994 _dbus_hash_iter_init (table1, &iter); 1995 while (_dbus_hash_iter_next (&iter)) 1996 { 1997 _dbus_hash_iter_remove_entry (&iter); 1998 _dbus_assert (count_entries (table1) == i - 1); 1999 --i; 2000 } 2001 2002 _dbus_hash_iter_init (table2, &iter); 2003 while (_dbus_hash_iter_next (&iter)) 2004 { 2005 int key; 2006 void *value; 2007 2008 key = _dbus_hash_iter_get_int_key (&iter); 2009 value = _dbus_hash_iter_get_value (&iter); 2010 2011 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 2012 2013 value = _dbus_strdup ("Different value!"); 2014 if (value == NULL) 2015 goto out; 2016 2017 _dbus_hash_iter_set_value (&iter, value); 2018 2019 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 2020 } 2021 2022 i = count_entries (table2); 2023 _dbus_hash_iter_init (table2, &iter); 2024 while (_dbus_hash_iter_next (&iter)) 2025 { 2026 _dbus_hash_iter_remove_entry (&iter); 2027 _dbus_assert (count_entries (table2) + 1 == i); 2028 --i; 2029 } 2030 2031 /* add/remove interleaved, to check that we grow/shrink the table 2032 * appropriately 2033 */ 2034 i = 0; 2035 while (i < 1000) 2036 { 2037 char *key; 2038 void *value; 2039 2040 key = _dbus_strdup (keys[i]); 2041 if (key == NULL) 2042 goto out; 2043 2044 value = _dbus_strdup ("Value!"); 2045 if (value == NULL) 2046 goto out; 2047 2048 if (!_dbus_hash_table_insert_string (table1, 2049 key, value)) 2050 goto out; 2051 2052 ++i; 2053 } 2054 2055 --i; 2056 while (i >= 0) 2057 { 2058 char *key; 2059 void *value; 2060 2061 key = _dbus_strdup (keys[i]); 2062 if (key == NULL) 2063 goto out; 2064 value = _dbus_strdup ("Value!"); 2065 if (value == NULL) 2066 goto out; 2067 2068 if (!_dbus_hash_table_remove_string (table1, keys[i])) 2069 goto out; 2070 2071 if (!_dbus_hash_table_insert_string (table1, 2072 key, value)) 2073 goto out; 2074 2075 if (!_dbus_hash_table_remove_string (table1, keys[i])) 2076 goto out; 2077 2078 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i); 2079 2080 --i; 2081 } 2082 2083 /* nuke these tables */ 2084 _dbus_hash_table_unref (table1); 2085 _dbus_hash_table_unref (table2); 2086 2087 2088 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to 2089 * be sure that interface works. 2090 */ 2091 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 2092 dbus_free, dbus_free); 2093 if (table1 == NULL) 2094 goto out; 2095 2096 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 2097 NULL, dbus_free); 2098 if (table2 == NULL) 2099 goto out; 2100 2101 i = 0; 2102 while (i < 3000) 2103 { 2104 void *value; 2105 char *key; 2106 2107 key = _dbus_strdup (keys[i]); 2108 if (key == NULL) 2109 goto out; 2110 value = _dbus_strdup ("Value!"); 2111 if (value == NULL) 2112 goto out; 2113 2114 if (!_dbus_hash_iter_lookup (table1, 2115 key, TRUE, &iter)) 2116 goto out; 2117 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 2118 _dbus_hash_iter_set_value (&iter, value); 2119 2120 value = _dbus_strdup (keys[i]); 2121 if (value == NULL) 2122 goto out; 2123 2124 if (!_dbus_hash_iter_lookup (table2, 2125 _DBUS_INT_TO_POINTER (i), TRUE, &iter)) 2126 goto out; 2127 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 2128 _dbus_hash_iter_set_value (&iter, value); 2129 2130 _dbus_assert (count_entries (table1) == i + 1); 2131 _dbus_assert (count_entries (table2) == i + 1); 2132 2133 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 2134 goto out; 2135 2136 value = _dbus_hash_iter_get_value (&iter); 2137 _dbus_assert (value != NULL); 2138 _dbus_assert (strcmp (value, "Value!") == 0); 2139 2140 /* Iterate just to be sure it works, though 2141 * it's a stupid thing to do 2142 */ 2143 while (_dbus_hash_iter_next (&iter)) 2144 ; 2145 2146 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 2147 goto out; 2148 2149 value = _dbus_hash_iter_get_value (&iter); 2150 _dbus_assert (value != NULL); 2151 _dbus_assert (strcmp (value, keys[i]) == 0); 2152 2153 /* Iterate just to be sure it works, though 2154 * it's a stupid thing to do 2155 */ 2156 while (_dbus_hash_iter_next (&iter)) 2157 ; 2158 2159 ++i; 2160 } 2161 2162 --i; 2163 while (i >= 0) 2164 { 2165 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 2166 _dbus_assert_not_reached ("hash entry should have existed"); 2167 _dbus_hash_iter_remove_entry (&iter); 2168 2169 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 2170 _dbus_assert_not_reached ("hash entry should have existed"); 2171 _dbus_hash_iter_remove_entry (&iter); 2172 2173 _dbus_assert (count_entries (table1) == i); 2174 _dbus_assert (count_entries (table2) == i); 2175 2176 --i; 2177 } 2178 2179 _dbus_hash_table_unref (table1); 2180 _dbus_hash_table_unref (table2); 2181 2182 ret = TRUE; 2183 2184 out: 2185 for (i = 0; i < N_HASH_KEYS; i++) 2186 dbus_free (keys[i]); 2187 2188 dbus_free (keys); 2189 2190 return ret; 2191 } 2192 2193 #endif /* DBUS_BUILD_TESTS */ 2194
