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