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 */ 135typedef 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 */ 143struct 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 */ 156typedef 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 */ 168struct 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 */ 212typedef 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_DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter)); 226 227static DBusHashEntry* find_direct_function (DBusHashTable *table, 228 void *key, 229 dbus_bool_t create_if_not_found, 230 DBusHashEntry ***bucket, 231 DBusPreallocatedHash *preallocated); 232static DBusHashEntry* find_string_function (DBusHashTable *table, 233 void *key, 234 dbus_bool_t create_if_not_found, 235 DBusHashEntry ***bucket, 236 DBusPreallocatedHash *preallocated); 237static unsigned int string_hash (const char *str); 238static void rebuild_table (DBusHashTable *table); 239static DBusHashEntry* alloc_entry (DBusHashTable *table); 240static void remove_entry (DBusHashTable *table, 241 DBusHashEntry **bucket, 242 DBusHashEntry *entry); 243static void free_entry (DBusHashTable *table, 244 DBusHashEntry *entry); 245static void free_entry_data (DBusHashTable *table, 246 DBusHashEntry *entry); 247 248 249/** @} */ 250 251/** 252 * @addtogroup DBusHashTable 253 * @{ 254 */ 255 256/** 257 * @typedef DBusHashIter 258 * 259 * Public opaque hash table iterator object. 260 */ 261 262/** 263 * @typedef DBusHashTable 264 * 265 * Public opaque hash table object. 266 */ 267 268/** 269 * @typedef DBusHashType 270 * 271 * Indicates the type of a key in the hash table. 272 */ 273 274/** 275 * Constructs a new hash table. Should be freed with 276 * _dbus_hash_table_unref(). If memory cannot be 277 * allocated for the hash table, returns #NULL. 278 * 279 * @param type the type of hash key to use. 280 * @param key_free_function function to free hash keys. 281 * @param value_free_function function to free hash values. 282 * @returns a new DBusHashTable or #NULL if no memory. 283 */ 284DBusHashTable* 285_dbus_hash_table_new (DBusHashType type, 286 DBusFreeFunction key_free_function, 287 DBusFreeFunction value_free_function) 288{ 289 DBusHashTable *table; 290 DBusMemPool *entry_pool; 291 292 table = dbus_new0 (DBusHashTable, 1); 293 if (table == NULL) 294 return NULL; 295 296 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE); 297 if (entry_pool == NULL) 298 { 299 dbus_free (table); 300 return NULL; 301 } 302 303 table->refcount = 1; 304 table->entry_pool = entry_pool; 305 306 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets)); 307 308 table->buckets = table->static_buckets; 309 table->n_buckets = DBUS_SMALL_HASH_TABLE; 310 table->n_entries = 0; 311 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER; 312 table->lo_rebuild_size = 0; 313 table->down_shift = 28; 314 table->mask = 3; 315 table->key_type = type; 316 317 _dbus_assert (table->mask < table->n_buckets); 318 319 switch (table->key_type) 320 { 321 case DBUS_HASH_INT: 322 case DBUS_HASH_UINTPTR: 323 table->find_function = find_direct_function; 324 break; 325 case DBUS_HASH_STRING: 326 table->find_function = find_string_function; 327 break; 328 default: 329 _dbus_assert_not_reached ("Unknown hash table type"); 330 break; 331 } 332 333 table->free_key_function = key_free_function; 334 table->free_value_function = value_free_function; 335 336 return table; 337} 338 339 340/** 341 * Increments the reference count for a hash table. 342 * 343 * @param table the hash table to add a reference to. 344 * @returns the hash table. 345 */ 346DBusHashTable * 347_dbus_hash_table_ref (DBusHashTable *table) 348{ 349 table->refcount += 1; 350 351 return table; 352} 353 354/** 355 * Decrements the reference count for a hash table, 356 * freeing the hash table if the count reaches zero. 357 * 358 * @param table the hash table to remove a reference from. 359 */ 360void 361_dbus_hash_table_unref (DBusHashTable *table) 362{ 363 table->refcount -= 1; 364 365 if (table->refcount == 0) 366 { 367#if 0 368 DBusHashEntry *entry; 369 DBusHashEntry *next; 370 int i; 371 372 /* Free the entries in the table. */ 373 for (i = 0; i < table->n_buckets; i++) 374 { 375 entry = table->buckets[i]; 376 while (entry != NULL) 377 { 378 next = entry->next; 379 380 free_entry (table, entry); 381 382 entry = next; 383 } 384 } 385#else 386 DBusHashEntry *entry; 387 int i; 388 389 /* Free the entries in the table. */ 390 for (i = 0; i < table->n_buckets; i++) 391 { 392 entry = table->buckets[i]; 393 while (entry != NULL) 394 { 395 free_entry_data (table, entry); 396 397 entry = entry->next; 398 } 399 } 400 /* We can do this very quickly with memory pools ;-) */ 401 _dbus_mem_pool_free (table->entry_pool); 402#endif 403 404 /* Free the bucket array, if it was dynamically allocated. */ 405 if (table->buckets != table->static_buckets) 406 dbus_free (table->buckets); 407 408 dbus_free (table); 409 } 410} 411 412/** 413 * Removed all entries from a hash table. 414 * 415 * @param table the hash table to remove all entries from. 416 */ 417void 418_dbus_hash_table_remove_all (DBusHashTable *table) 419{ 420 DBusHashIter iter; 421 _dbus_hash_iter_init (table, &iter); 422 while (_dbus_hash_iter_next (&iter)) 423 { 424 _dbus_hash_iter_remove_entry(&iter); 425 } 426} 427 428static DBusHashEntry* 429alloc_entry (DBusHashTable *table) 430{ 431 DBusHashEntry *entry; 432 433 entry = _dbus_mem_pool_alloc (table->entry_pool); 434 435 return entry; 436} 437 438static void 439free_entry_data (DBusHashTable *table, 440 DBusHashEntry *entry) 441{ 442 if (table->free_key_function) 443 (* table->free_key_function) (entry->key); 444 if (table->free_value_function) 445 (* table->free_value_function) (entry->value); 446} 447 448static void 449free_entry (DBusHashTable *table, 450 DBusHashEntry *entry) 451{ 452 free_entry_data (table, entry); 453 _dbus_mem_pool_dealloc (table->entry_pool, entry); 454} 455 456static void 457remove_entry (DBusHashTable *table, 458 DBusHashEntry **bucket, 459 DBusHashEntry *entry) 460{ 461 _dbus_assert (table != NULL); 462 _dbus_assert (bucket != NULL); 463 _dbus_assert (*bucket != NULL); 464 _dbus_assert (entry != NULL); 465 466 if (*bucket == entry) 467 *bucket = entry->next; 468 else 469 { 470 DBusHashEntry *prev; 471 prev = *bucket; 472 473 while (prev->next != entry) 474 prev = prev->next; 475 476 _dbus_assert (prev != NULL); 477 478 prev->next = entry->next; 479 } 480 481 table->n_entries -= 1; 482 free_entry (table, entry); 483} 484 485/** 486 * Initializes a hash table iterator. To iterate over all entries in a 487 * hash table, use the following code (the printf assumes a hash 488 * from strings to strings obviously): 489 * 490 * @code 491 * DBusHashIter iter; 492 * 493 * _dbus_hash_iter_init (table, &iter); 494 * while (_dbus_hash_iter_next (&iter)) 495 * { 496 * printf ("The first key is %s and value is %s\n", 497 * _dbus_hash_iter_get_string_key (&iter), 498 * _dbus_hash_iter_get_value (&iter)); 499 * } 500 * 501 * 502 * @endcode 503 * 504 * The iterator is initialized pointing "one before" the first hash 505 * entry. The first call to _dbus_hash_iter_next() moves it onto 506 * the first valid entry or returns #FALSE if the hash table is 507 * empty. Subsequent calls move to the next valid entry or return 508 * #FALSE if there are no more entries. 509 * 510 * Note that it is guaranteed to be safe to remove a hash entry during 511 * iteration, but it is not safe to add a hash entry. 512 * 513 * @param table the hash table to iterate over. 514 * @param iter the iterator to initialize. 515 */ 516void 517_dbus_hash_iter_init (DBusHashTable *table, 518 DBusHashIter *iter) 519{ 520 DBusRealHashIter *real; 521 522 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 523 524 real = (DBusRealHashIter*) iter; 525 526 real->table = table; 527 real->bucket = NULL; 528 real->entry = NULL; 529 real->next_entry = NULL; 530 real->next_bucket = 0; 531 real->n_entries_on_init = table->n_entries; 532} 533 534/** 535 * Move the hash iterator forward one step, to the next hash entry. 536 * The documentation for _dbus_hash_iter_init() explains in more 537 * detail. 538 * 539 * @param iter the iterator to move forward. 540 * @returns #FALSE if there are no more entries to move to. 541 */ 542dbus_bool_t 543_dbus_hash_iter_next (DBusHashIter *iter) 544{ 545 DBusRealHashIter *real; 546 547 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 548 549 real = (DBusRealHashIter*) iter; 550 551 /* if this assertion failed someone probably added hash entries 552 * during iteration, which is bad. 553 */ 554 _dbus_assert (real->n_entries_on_init >= real->table->n_entries); 555 556 /* Remember that real->entry may have been deleted */ 557 558 while (real->next_entry == NULL) 559 { 560 if (real->next_bucket >= real->table->n_buckets) 561 { 562 /* invalidate iter and return false */ 563 real->entry = NULL; 564 real->table = NULL; 565 real->bucket = NULL; 566 return FALSE; 567 } 568 569 real->bucket = &(real->table->buckets[real->next_bucket]); 570 real->next_entry = *(real->bucket); 571 real->next_bucket += 1; 572 } 573 574 _dbus_assert (real->next_entry != NULL); 575 _dbus_assert (real->bucket != NULL); 576 577 real->entry = real->next_entry; 578 real->next_entry = real->entry->next; 579 580 return TRUE; 581} 582 583/** 584 * Removes the current entry from the hash table. 585 * If a key_free_function or value_free_function 586 * was provided to _dbus_hash_table_new(), 587 * frees the key and/or value for this entry. 588 * 589 * @param iter the hash table iterator. 590 */ 591void 592_dbus_hash_iter_remove_entry (DBusHashIter *iter) 593{ 594 DBusRealHashIter *real; 595 596 real = (DBusRealHashIter*) iter; 597 598 _dbus_assert (real->table != NULL); 599 _dbus_assert (real->entry != NULL); 600 _dbus_assert (real->bucket != NULL); 601 602 remove_entry (real->table, real->bucket, real->entry); 603 604 real->entry = NULL; /* make it crash if you try to use this entry */ 605} 606 607/** 608 * Gets the value of the current entry. 609 * 610 * @param iter the hash table iterator. 611 */ 612void* 613_dbus_hash_iter_get_value (DBusHashIter *iter) 614{ 615 DBusRealHashIter *real; 616 617 real = (DBusRealHashIter*) iter; 618 619 _dbus_assert (real->table != NULL); 620 _dbus_assert (real->entry != NULL); 621 622 return real->entry->value; 623} 624 625/** 626 * Sets the value of the current entry. 627 * If the hash table has a value_free_function 628 * it will be used to free the previous value. 629 * The hash table will own the passed-in value 630 * (it will not be copied). 631 * 632 * @param iter the hash table iterator. 633 * @param value the new value. 634 */ 635void 636_dbus_hash_iter_set_value (DBusHashIter *iter, 637 void *value) 638{ 639 DBusRealHashIter *real; 640 641 real = (DBusRealHashIter*) iter; 642 643 _dbus_assert (real->table != NULL); 644 _dbus_assert (real->entry != NULL); 645 646 if (real->table->free_value_function && value != real->entry->value) 647 (* real->table->free_value_function) (real->entry->value); 648 649 real->entry->value = value; 650} 651 652/** 653 * Gets the key for the current entry. 654 * Only works for hash tables of type #DBUS_HASH_INT. 655 * 656 * @param iter the hash table iterator. 657 */ 658int 659_dbus_hash_iter_get_int_key (DBusHashIter *iter) 660{ 661 DBusRealHashIter *real; 662 663 real = (DBusRealHashIter*) iter; 664 665 _dbus_assert (real->table != NULL); 666 _dbus_assert (real->entry != NULL); 667 668 return _DBUS_POINTER_TO_INT (real->entry->key); 669} 670 671/** 672 * Gets the key for the current entry. 673 * Only works for hash tables of type #DBUS_HASH_UINTPTR. 674 * 675 * @param iter the hash table iterator. 676 */ 677uintptr_t 678_dbus_hash_iter_get_uintptr_key (DBusHashIter *iter) 679{ 680 DBusRealHashIter *real; 681 682 real = (DBusRealHashIter*) iter; 683 684 _dbus_assert (real->table != NULL); 685 _dbus_assert (real->entry != NULL); 686 687 return (uintptr_t) real->entry->key; 688} 689 690/** 691 * Gets the key for the current entry. 692 * Only works for hash tables of type #DBUS_HASH_STRING 693 * @param iter the hash table iterator. 694 */ 695const char* 696_dbus_hash_iter_get_string_key (DBusHashIter *iter) 697{ 698 DBusRealHashIter *real; 699 700 real = (DBusRealHashIter*) iter; 701 702 _dbus_assert (real->table != NULL); 703 _dbus_assert (real->entry != NULL); 704 705 return real->entry->key; 706} 707 708/** 709 * A low-level but efficient interface for manipulating the hash 710 * table. It's efficient because you can get, set, and optionally 711 * create the hash entry while only running the hash function one 712 * time. 713 * 714 * Note that while calling _dbus_hash_iter_next() on the iterator 715 * filled in by this function may work, it's completely 716 * undefined which entries are after this iter and which 717 * are before it. So it would be silly to iterate using this 718 * iterator. 719 * 720 * If the hash entry is created, its value will be initialized 721 * to all bits zero. 722 * 723 * #FALSE may be returned due to memory allocation failure, or 724 * because create_if_not_found was #FALSE and the entry 725 * did not exist. 726 * 727 * If create_if_not_found is #TRUE and the entry is created, the hash 728 * table takes ownership of the key that's passed in. 729 * 730 * For a hash table of type #DBUS_HASH_INT, cast the int 731 * key to the key parameter using #_DBUS_INT_TO_POINTER(). 732 * 733 * @param table the hash table. 734 * @param key the hash key. 735 * @param create_if_not_found if #TRUE, create the entry if it didn't exist. 736 * @param iter the iterator to initialize. 737 * @returns #TRUE if the hash entry now exists (and the iterator is thus valid). 738 */ 739dbus_bool_t 740_dbus_hash_iter_lookup (DBusHashTable *table, 741 void *key, 742 dbus_bool_t create_if_not_found, 743 DBusHashIter *iter) 744{ 745 DBusRealHashIter *real; 746 DBusHashEntry *entry; 747 DBusHashEntry **bucket; 748 749 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 750 751 real = (DBusRealHashIter*) iter; 752 753 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL); 754 755 if (entry == NULL) 756 return FALSE; 757 758 real->table = table; 759 real->bucket = bucket; 760 real->entry = entry; 761 real->next_entry = entry->next; 762 real->next_bucket = (bucket - table->buckets) + 1; 763 real->n_entries_on_init = table->n_entries; 764 765 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket); 766 767 return TRUE; 768} 769 770static void 771add_allocated_entry (DBusHashTable *table, 772 DBusHashEntry *entry, 773 unsigned int idx, 774 void *key, 775 DBusHashEntry ***bucket) 776{ 777 DBusHashEntry **b; 778 779 entry->key = key; 780 781 b = &(table->buckets[idx]); 782 entry->next = *b; 783 *b = entry; 784 785 if (bucket) 786 *bucket = b; 787 788 table->n_entries += 1; 789 790 /* note we ONLY rebuild when ADDING - because you can iterate over a 791 * table and remove entries safely. 792 */ 793 if (table->n_entries >= table->hi_rebuild_size || 794 table->n_entries < table->lo_rebuild_size) 795 rebuild_table (table); 796} 797 798static DBusHashEntry* 799add_entry (DBusHashTable *table, 800 unsigned int idx, 801 void *key, 802 DBusHashEntry ***bucket, 803 DBusPreallocatedHash *preallocated) 804{ 805 DBusHashEntry *entry; 806 807 if (preallocated == NULL) 808 { 809 entry = alloc_entry (table); 810 if (entry == NULL) 811 { 812 if (bucket) 813 *bucket = NULL; 814 return NULL; 815 } 816 } 817 else 818 { 819 entry = (DBusHashEntry*) preallocated; 820 } 821 822 add_allocated_entry (table, entry, idx, key, bucket); 823 824 return entry; 825} 826 827/* This is g_str_hash from GLib which was 828 * extensively discussed/tested/profiled 829 */ 830static unsigned int 831string_hash (const char *str) 832{ 833 const char *p = str; 834 unsigned int h = *p; 835 836 if (h) 837 for (p += 1; *p != '\0'; p++) 838 h = (h << 5) - h + *p; 839 840 return h; 841} 842 843/** Key comparison function */ 844typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b); 845 846static DBusHashEntry* 847find_generic_function (DBusHashTable *table, 848 void *key, 849 unsigned int idx, 850 KeyCompareFunc compare_func, 851 dbus_bool_t create_if_not_found, 852 DBusHashEntry ***bucket, 853 DBusPreallocatedHash *preallocated) 854{ 855 DBusHashEntry *entry; 856 857 if (bucket) 858 *bucket = NULL; 859 860 /* Search all of the entries in this bucket. */ 861 entry = table->buckets[idx]; 862 while (entry != NULL) 863 { 864 if ((compare_func == NULL && key == entry->key) || 865 (compare_func != NULL && (* compare_func) (key, entry->key) == 0)) 866 { 867 if (bucket) 868 *bucket = &(table->buckets[idx]); 869 870 if (preallocated) 871 _dbus_hash_table_free_preallocated_entry (table, preallocated); 872 873 return entry; 874 } 875 876 entry = entry->next; 877 } 878 879 if (create_if_not_found) 880 entry = add_entry (table, idx, key, bucket, preallocated); 881 else if (preallocated) 882 _dbus_hash_table_free_preallocated_entry (table, preallocated); 883 884 return entry; 885} 886 887static DBusHashEntry* 888find_string_function (DBusHashTable *table, 889 void *key, 890 dbus_bool_t create_if_not_found, 891 DBusHashEntry ***bucket, 892 DBusPreallocatedHash *preallocated) 893{ 894 unsigned int idx; 895 896 idx = string_hash (key) & table->mask; 897 898 return find_generic_function (table, key, idx, 899 (KeyCompareFunc) strcmp, create_if_not_found, bucket, 900 preallocated); 901} 902 903static DBusHashEntry* 904find_direct_function (DBusHashTable *table, 905 void *key, 906 dbus_bool_t create_if_not_found, 907 DBusHashEntry ***bucket, 908 DBusPreallocatedHash *preallocated) 909{ 910 unsigned int idx; 911 912 idx = RANDOM_INDEX (table, key) & table->mask; 913 914 915 return find_generic_function (table, key, idx, 916 NULL, create_if_not_found, bucket, 917 preallocated); 918} 919 920static void 921rebuild_table (DBusHashTable *table) 922{ 923 int old_size; 924 int new_buckets; 925 DBusHashEntry **old_buckets; 926 DBusHashEntry **old_chain; 927 DBusHashEntry *entry; 928 dbus_bool_t growing; 929 930 /* 931 * Allocate and initialize the new bucket array, and set up 932 * hashing constants for new array size. 933 */ 934 935 growing = table->n_entries >= table->hi_rebuild_size; 936 937 old_size = table->n_buckets; 938 old_buckets = table->buckets; 939 940 if (growing) 941 { 942 /* overflow paranoia */ 943 if (table->n_buckets < _DBUS_INT_MAX / 4 && 944 table->down_shift >= 0) 945 new_buckets = table->n_buckets * 4; 946 else 947 return; /* can't grow anymore */ 948 } 949 else 950 { 951 new_buckets = table->n_buckets / 4; 952 if (new_buckets < DBUS_SMALL_HASH_TABLE) 953 return; /* don't bother shrinking this far */ 954 } 955 956 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets); 957 if (table->buckets == NULL) 958 { 959 /* out of memory, yay - just don't reallocate, the table will 960 * still work, albeit more slowly. 961 */ 962 table->buckets = old_buckets; 963 return; 964 } 965 966 table->n_buckets = new_buckets; 967 968 if (growing) 969 { 970 table->lo_rebuild_size = table->hi_rebuild_size; 971 table->hi_rebuild_size *= 4; 972 973 table->down_shift -= 2; /* keep 2 more high bits */ 974 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */ 975 } 976 else 977 { 978 table->hi_rebuild_size = table->lo_rebuild_size; 979 table->lo_rebuild_size /= 4; 980 981 table->down_shift += 2; /* keep 2 fewer high bits */ 982 table->mask = table->mask >> 2; /* keep 2 fewer high bits */ 983 } 984 985#if 0 986 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", 987 growing ? "GROW" : "SHRINK", 988 table->lo_rebuild_size, 989 table->hi_rebuild_size, 990 table->down_shift, 991 table->mask); 992#endif 993 994 _dbus_assert (table->lo_rebuild_size >= 0); 995 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size); 996 _dbus_assert (table->mask != 0); 997 /* the mask is essentially the max index */ 998 _dbus_assert (table->mask < table->n_buckets); 999 1000 /* 1001 * Rehash all of the existing entries into the new bucket array. 1002 */ 1003 1004 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++) 1005 { 1006 for (entry = *old_chain; entry != NULL; entry = *old_chain) 1007 { 1008 unsigned int idx; 1009 DBusHashEntry **bucket; 1010 1011 *old_chain = entry->next; 1012 switch (table->key_type) 1013 { 1014 case DBUS_HASH_STRING: 1015 idx = string_hash (entry->key) & table->mask; 1016 break; 1017 case DBUS_HASH_INT: 1018 case DBUS_HASH_UINTPTR: 1019 idx = RANDOM_INDEX (table, entry->key); 1020 break; 1021 default: 1022 idx = 0; 1023 _dbus_assert_not_reached ("Unknown hash table type"); 1024 break; 1025 } 1026 1027 bucket = &(table->buckets[idx]); 1028 entry->next = *bucket; 1029 *bucket = entry; 1030 } 1031 } 1032 1033 /* Free the old bucket array, if it was dynamically allocated. */ 1034 1035 if (old_buckets != table->static_buckets) 1036 dbus_free (old_buckets); 1037} 1038 1039/** 1040 * Looks up the value for a given string in a hash table 1041 * of type #DBUS_HASH_STRING. Returns %NULL if the value 1042 * is not present. (A not-present entry is indistinguishable 1043 * from an entry with a value of %NULL.) 1044 * @param table the hash table. 1045 * @param key the string to look up. 1046 * @returns the value of the hash entry. 1047 */ 1048void* 1049_dbus_hash_table_lookup_string (DBusHashTable *table, 1050 const char *key) 1051{ 1052 DBusHashEntry *entry; 1053 1054 _dbus_assert (table->key_type == DBUS_HASH_STRING); 1055 1056 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 1057 1058 if (entry) 1059 return entry->value; 1060 else 1061 return NULL; 1062} 1063 1064/** 1065 * Looks up the value for a given integer in a hash table 1066 * of type #DBUS_HASH_INT. Returns %NULL if the value 1067 * is not present. (A not-present entry is indistinguishable 1068 * from an entry with a value of %NULL.) 1069 * @param table the hash table. 1070 * @param key the integer to look up. 1071 * @returns the value of the hash entry. 1072 */ 1073void* 1074_dbus_hash_table_lookup_int (DBusHashTable *table, 1075 int key) 1076{ 1077 DBusHashEntry *entry; 1078 1079 _dbus_assert (table->key_type == DBUS_HASH_INT); 1080 1081 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL); 1082 1083 if (entry) 1084 return entry->value; 1085 else 1086 return NULL; 1087} 1088 1089/** 1090 * Looks up the value for a given integer in a hash table 1091 * of type #DBUS_HASH_UINTPTR. Returns %NULL if the value 1092 * is not present. (A not-present entry is indistinguishable 1093 * from an entry with a value of %NULL.) 1094 * @param table the hash table. 1095 * @param key the integer to look up. 1096 * @returns the value of the hash entry. 1097 */ 1098void* 1099_dbus_hash_table_lookup_uintptr (DBusHashTable *table, 1100 uintptr_t key) 1101{ 1102 DBusHashEntry *entry; 1103 1104 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 1105 1106 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL); 1107 1108 if (entry) 1109 return entry->value; 1110 else 1111 return NULL; 1112} 1113 1114/** 1115 * Removes the hash entry for the given key. If no hash entry 1116 * for the key exists, does nothing. 1117 * 1118 * @param table the hash table. 1119 * @param key the hash key. 1120 * @returns #TRUE if the entry existed 1121 */ 1122dbus_bool_t 1123_dbus_hash_table_remove_string (DBusHashTable *table, 1124 const char *key) 1125{ 1126 DBusHashEntry *entry; 1127 DBusHashEntry **bucket; 1128 1129 _dbus_assert (table->key_type == DBUS_HASH_STRING); 1130 1131 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 1132 1133 if (entry) 1134 { 1135 remove_entry (table, bucket, entry); 1136 return TRUE; 1137 } 1138 else 1139 return FALSE; 1140} 1141 1142/** 1143 * Removes the hash entry for the given key. If no hash entry 1144 * for the key exists, does nothing. 1145 * 1146 * @param table the hash table. 1147 * @param key the hash key. 1148 * @returns #TRUE if the entry existed 1149 */ 1150dbus_bool_t 1151_dbus_hash_table_remove_int (DBusHashTable *table, 1152 int key) 1153{ 1154 DBusHashEntry *entry; 1155 DBusHashEntry **bucket; 1156 1157 _dbus_assert (table->key_type == DBUS_HASH_INT); 1158 1159 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL); 1160 1161 if (entry) 1162 { 1163 remove_entry (table, bucket, entry); 1164 return TRUE; 1165 } 1166 else 1167 return FALSE; 1168} 1169 1170/** 1171 * Removes the hash entry for the given key. If no hash entry 1172 * for the key exists, does nothing. 1173 * 1174 * @param table the hash table. 1175 * @param key the hash key. 1176 * @returns #TRUE if the entry existed 1177 */ 1178dbus_bool_t 1179_dbus_hash_table_remove_uintptr (DBusHashTable *table, 1180 uintptr_t key) 1181{ 1182 DBusHashEntry *entry; 1183 DBusHashEntry **bucket; 1184 1185 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 1186 1187 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL); 1188 1189 if (entry) 1190 { 1191 remove_entry (table, bucket, entry); 1192 return TRUE; 1193 } 1194 else 1195 return FALSE; 1196} 1197 1198/** 1199 * Creates a hash entry with the given key and value. 1200 * The key and value are not copied; they are stored 1201 * in the hash table by reference. If an entry with the 1202 * given key already exists, the previous key and value 1203 * are overwritten (and freed if the hash table has 1204 * a key_free_function and/or value_free_function). 1205 * 1206 * Returns #FALSE if memory for the new hash entry 1207 * can't be allocated. 1208 * 1209 * @param table the hash table. 1210 * @param key the hash entry key. 1211 * @param value the hash entry value. 1212 */ 1213dbus_bool_t 1214_dbus_hash_table_insert_string (DBusHashTable *table, 1215 char *key, 1216 void *value) 1217{ 1218 DBusPreallocatedHash *preallocated; 1219 1220 _dbus_assert (table->key_type == DBUS_HASH_STRING); 1221 1222 preallocated = _dbus_hash_table_preallocate_entry (table); 1223 if (preallocated == NULL) 1224 return FALSE; 1225 1226 _dbus_hash_table_insert_string_preallocated (table, preallocated, 1227 key, value); 1228 1229 return TRUE; 1230} 1231 1232/** 1233 * Creates a hash entry with the given key and value. 1234 * The key and value are not copied; they are stored 1235 * in the hash table by reference. If an entry with the 1236 * given key already exists, the previous key and value 1237 * are overwritten (and freed if the hash table has 1238 * a key_free_function and/or value_free_function). 1239 * 1240 * Returns #FALSE if memory for the new hash entry 1241 * can't be allocated. 1242 * 1243 * @param table the hash table. 1244 * @param key the hash entry key. 1245 * @param value the hash entry value. 1246 */ 1247dbus_bool_t 1248_dbus_hash_table_insert_int (DBusHashTable *table, 1249 int key, 1250 void *value) 1251{ 1252 DBusHashEntry *entry; 1253 1254 _dbus_assert (table->key_type == DBUS_HASH_INT); 1255 1256 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL); 1257 1258 if (entry == NULL) 1259 return FALSE; /* no memory */ 1260 1261 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key)) 1262 (* table->free_key_function) (entry->key); 1263 1264 if (table->free_value_function && entry->value != value) 1265 (* table->free_value_function) (entry->value); 1266 1267 entry->key = _DBUS_INT_TO_POINTER (key); 1268 entry->value = value; 1269 1270 return TRUE; 1271} 1272 1273/** 1274 * Creates a hash entry with the given key and value. 1275 * The key and value are not copied; they are stored 1276 * in the hash table by reference. If an entry with the 1277 * given key already exists, the previous key and value 1278 * are overwritten (and freed if the hash table has 1279 * a key_free_function and/or value_free_function). 1280 * 1281 * Returns #FALSE if memory for the new hash entry 1282 * can't be allocated. 1283 * 1284 * @param table the hash table. 1285 * @param key the hash entry key. 1286 * @param value the hash entry value. 1287 */ 1288dbus_bool_t 1289_dbus_hash_table_insert_uintptr (DBusHashTable *table, 1290 uintptr_t key, 1291 void *value) 1292{ 1293 DBusHashEntry *entry; 1294 1295 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 1296 1297 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL); 1298 1299 if (entry == NULL) 1300 return FALSE; /* no memory */ 1301 1302 if (table->free_key_function && entry->key != (void*) key) 1303 (* table->free_key_function) (entry->key); 1304 1305 if (table->free_value_function && entry->value != value) 1306 (* table->free_value_function) (entry->value); 1307 1308 entry->key = (void*) key; 1309 entry->value = value; 1310 1311 return TRUE; 1312} 1313 1314/** 1315 * Preallocate an opaque data blob that allows us to insert into the 1316 * hash table at a later time without allocating any memory. 1317 * 1318 * @param table the hash table 1319 * @returns the preallocated data, or #NULL if no memory 1320 */ 1321DBusPreallocatedHash* 1322_dbus_hash_table_preallocate_entry (DBusHashTable *table) 1323{ 1324 DBusHashEntry *entry; 1325 1326 entry = alloc_entry (table); 1327 1328 return (DBusPreallocatedHash*) entry; 1329} 1330 1331/** 1332 * Frees an opaque DBusPreallocatedHash that was *not* used 1333 * in order to insert into the hash table. 1334 * 1335 * @param table the hash table 1336 * @param preallocated the preallocated data 1337 */ 1338void 1339_dbus_hash_table_free_preallocated_entry (DBusHashTable *table, 1340 DBusPreallocatedHash *preallocated) 1341{ 1342 DBusHashEntry *entry; 1343 1344 _dbus_assert (preallocated != NULL); 1345 1346 entry = (DBusHashEntry*) preallocated; 1347 1348 /* Don't use free_entry(), since this entry has no key/data */ 1349 _dbus_mem_pool_dealloc (table->entry_pool, entry); 1350} 1351 1352/** 1353 * Inserts a string-keyed entry into the hash table, using a 1354 * preallocated data block from 1355 * _dbus_hash_table_preallocate_entry(). This function cannot fail due 1356 * to lack of memory. The DBusPreallocatedHash object is consumed and 1357 * should not be reused or freed. Otherwise this function works 1358 * just like _dbus_hash_table_insert_string(). 1359 * 1360 * @param table the hash table 1361 * @param preallocated the preallocated data 1362 * @param key the hash key 1363 * @param value the value 1364 */ 1365void 1366_dbus_hash_table_insert_string_preallocated (DBusHashTable *table, 1367 DBusPreallocatedHash *preallocated, 1368 char *key, 1369 void *value) 1370{ 1371 DBusHashEntry *entry; 1372 1373 _dbus_assert (table->key_type == DBUS_HASH_STRING); 1374 _dbus_assert (preallocated != NULL); 1375 1376 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated); 1377 1378 _dbus_assert (entry != NULL); 1379 1380 if (table->free_key_function && entry->key != key) 1381 (* table->free_key_function) (entry->key); 1382 1383 if (table->free_value_function && entry->value != value) 1384 (* table->free_value_function) (entry->value); 1385 1386 entry->key = key; 1387 entry->value = value; 1388} 1389 1390/** 1391 * Gets the number of hash entries in a hash table. 1392 * 1393 * @param table the hash table. 1394 * @returns the number of entries in the table. 1395 */ 1396int 1397_dbus_hash_table_get_n_entries (DBusHashTable *table) 1398{ 1399 return table->n_entries; 1400} 1401 1402/** @} */ 1403 1404#ifdef DBUS_BUILD_TESTS 1405#include "dbus-test.h" 1406#include <stdio.h> 1407 1408/* If you're wondering why the hash table test takes 1409 * forever to run, it's because we call this function 1410 * in inner loops thus making things quadratic. 1411 */ 1412static int 1413count_entries (DBusHashTable *table) 1414{ 1415 DBusHashIter iter; 1416 int count; 1417 1418 count = 0; 1419 _dbus_hash_iter_init (table, &iter); 1420 while (_dbus_hash_iter_next (&iter)) 1421 ++count; 1422 1423 _dbus_assert (count == _dbus_hash_table_get_n_entries (table)); 1424 1425 return count; 1426} 1427 1428/** 1429 * @ingroup DBusHashTableInternals 1430 * Unit test for DBusHashTable 1431 * @returns #TRUE on success. 1432 */ 1433dbus_bool_t 1434_dbus_hash_test (void) 1435{ 1436 int i; 1437 DBusHashTable *table1; 1438 DBusHashTable *table2; 1439 DBusHashTable *table3; 1440 DBusHashIter iter; 1441#define N_HASH_KEYS 5000 1442 char **keys; 1443 dbus_bool_t ret = FALSE; 1444 1445 keys = dbus_new (char *, N_HASH_KEYS); 1446 if (keys == NULL) 1447 _dbus_assert_not_reached ("no memory"); 1448 1449 for (i = 0; i < N_HASH_KEYS; i++) 1450 { 1451 keys[i] = dbus_malloc (128); 1452 1453 if (keys[i] == NULL) 1454 _dbus_assert_not_reached ("no memory"); 1455 } 1456 1457 printf ("Computing test hash keys...\n"); 1458 i = 0; 1459 while (i < N_HASH_KEYS) 1460 { 1461 int len; 1462 1463 len = sprintf (keys[i], "Hash key %d", i); 1464 _dbus_assert (*(keys[i] + len) == '\0'); 1465 ++i; 1466 } 1467 printf ("... done.\n"); 1468 1469 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 1470 dbus_free, dbus_free); 1471 if (table1 == NULL) 1472 goto out; 1473 1474 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 1475 NULL, dbus_free); 1476 if (table2 == NULL) 1477 goto out; 1478 1479 table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR, 1480 NULL, dbus_free); 1481 if (table3 == NULL) 1482 goto out; 1483 1484 /* Insert and remove a bunch of stuff, counting the table in between 1485 * to be sure it's not broken and that iteration works 1486 */ 1487 i = 0; 1488 while (i < 3000) 1489 { 1490 void *value; 1491 char *key; 1492 1493 key = _dbus_strdup (keys[i]); 1494 if (key == NULL) 1495 goto out; 1496 value = _dbus_strdup ("Value!"); 1497 if (value == NULL) 1498 goto out; 1499 1500 if (!_dbus_hash_table_insert_string (table1, 1501 key, value)) 1502 goto out; 1503 1504 value = _dbus_strdup (keys[i]); 1505 if (value == NULL) 1506 goto out; 1507 1508 if (!_dbus_hash_table_insert_int (table2, 1509 i, value)) 1510 goto out; 1511 1512 value = _dbus_strdup (keys[i]); 1513 if (value == NULL) 1514 goto out; 1515 1516 if (!_dbus_hash_table_insert_uintptr (table3, 1517 i, value)) 1518 goto out; 1519 1520 _dbus_assert (count_entries (table1) == i + 1); 1521 _dbus_assert (count_entries (table2) == i + 1); 1522 _dbus_assert (count_entries (table3) == i + 1); 1523 1524 value = _dbus_hash_table_lookup_string (table1, keys[i]); 1525 _dbus_assert (value != NULL); 1526 _dbus_assert (strcmp (value, "Value!") == 0); 1527 1528 value = _dbus_hash_table_lookup_int (table2, i); 1529 _dbus_assert (value != NULL); 1530 _dbus_assert (strcmp (value, keys[i]) == 0); 1531 1532 value = _dbus_hash_table_lookup_uintptr (table3, i); 1533 _dbus_assert (value != NULL); 1534 _dbus_assert (strcmp (value, keys[i]) == 0); 1535 1536 ++i; 1537 } 1538 1539 --i; 1540 while (i >= 0) 1541 { 1542 _dbus_hash_table_remove_string (table1, 1543 keys[i]); 1544 1545 _dbus_hash_table_remove_int (table2, i); 1546 1547 _dbus_hash_table_remove_uintptr (table3, i); 1548 1549 _dbus_assert (count_entries (table1) == i); 1550 _dbus_assert (count_entries (table2) == i); 1551 _dbus_assert (count_entries (table3) == i); 1552 1553 --i; 1554 } 1555 1556 _dbus_hash_table_ref (table1); 1557 _dbus_hash_table_ref (table2); 1558 _dbus_hash_table_ref (table3); 1559 _dbus_hash_table_unref (table1); 1560 _dbus_hash_table_unref (table2); 1561 _dbus_hash_table_unref (table3); 1562 _dbus_hash_table_unref (table1); 1563 _dbus_hash_table_unref (table2); 1564 _dbus_hash_table_unref (table3); 1565 table3 = NULL; 1566 1567 /* Insert a bunch of stuff then check 1568 * that iteration works correctly (finds the right 1569 * values, iter_set_value works, etc.) 1570 */ 1571 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 1572 dbus_free, dbus_free); 1573 if (table1 == NULL) 1574 goto out; 1575 1576 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 1577 NULL, dbus_free); 1578 if (table2 == NULL) 1579 goto out; 1580 1581 i = 0; 1582 while (i < 5000) 1583 { 1584 char *key; 1585 void *value; 1586 1587 key = _dbus_strdup (keys[i]); 1588 if (key == NULL) 1589 goto out; 1590 value = _dbus_strdup ("Value!"); 1591 if (value == NULL) 1592 goto out; 1593 1594 if (!_dbus_hash_table_insert_string (table1, 1595 key, value)) 1596 goto out; 1597 1598 value = _dbus_strdup (keys[i]); 1599 if (value == NULL) 1600 goto out; 1601 1602 if (!_dbus_hash_table_insert_int (table2, 1603 i, value)) 1604 goto out; 1605 1606 _dbus_assert (count_entries (table1) == i + 1); 1607 _dbus_assert (count_entries (table2) == i + 1); 1608 1609 ++i; 1610 } 1611 1612 _dbus_hash_iter_init (table1, &iter); 1613 while (_dbus_hash_iter_next (&iter)) 1614 { 1615 const char *key; 1616 void *value; 1617 1618 key = _dbus_hash_iter_get_string_key (&iter); 1619 value = _dbus_hash_iter_get_value (&iter); 1620 1621 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 1622 1623 value = _dbus_strdup ("Different value!"); 1624 if (value == NULL) 1625 goto out; 1626 1627 _dbus_hash_iter_set_value (&iter, value); 1628 1629 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 1630 } 1631 1632 _dbus_hash_iter_init (table1, &iter); 1633 while (_dbus_hash_iter_next (&iter)) 1634 { 1635 _dbus_hash_iter_remove_entry (&iter); 1636 _dbus_assert (count_entries (table1) == i - 1); 1637 --i; 1638 } 1639 1640 _dbus_hash_iter_init (table2, &iter); 1641 while (_dbus_hash_iter_next (&iter)) 1642 { 1643 int key; 1644 void *value; 1645 1646 key = _dbus_hash_iter_get_int_key (&iter); 1647 value = _dbus_hash_iter_get_value (&iter); 1648 1649 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 1650 1651 value = _dbus_strdup ("Different value!"); 1652 if (value == NULL) 1653 goto out; 1654 1655 _dbus_hash_iter_set_value (&iter, value); 1656 1657 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 1658 } 1659 1660 i = count_entries (table2); 1661 _dbus_hash_iter_init (table2, &iter); 1662 while (_dbus_hash_iter_next (&iter)) 1663 { 1664 _dbus_hash_iter_remove_entry (&iter); 1665 _dbus_assert (count_entries (table2) + 1 == i); 1666 --i; 1667 } 1668 1669 /* add/remove interleaved, to check that we grow/shrink the table 1670 * appropriately 1671 */ 1672 i = 0; 1673 while (i < 1000) 1674 { 1675 char *key; 1676 void *value; 1677 1678 key = _dbus_strdup (keys[i]); 1679 if (key == NULL) 1680 goto out; 1681 1682 value = _dbus_strdup ("Value!"); 1683 if (value == NULL) 1684 goto out; 1685 1686 if (!_dbus_hash_table_insert_string (table1, 1687 key, value)) 1688 goto out; 1689 1690 ++i; 1691 } 1692 1693 --i; 1694 while (i >= 0) 1695 { 1696 char *key; 1697 void *value; 1698 1699 key = _dbus_strdup (keys[i]); 1700 if (key == NULL) 1701 goto out; 1702 value = _dbus_strdup ("Value!"); 1703 if (value == NULL) 1704 goto out; 1705 1706 if (!_dbus_hash_table_remove_string (table1, keys[i])) 1707 goto out; 1708 1709 if (!_dbus_hash_table_insert_string (table1, 1710 key, value)) 1711 goto out; 1712 1713 if (!_dbus_hash_table_remove_string (table1, keys[i])) 1714 goto out; 1715 1716 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i); 1717 1718 --i; 1719 } 1720 1721 /* nuke these tables */ 1722 _dbus_hash_table_unref (table1); 1723 _dbus_hash_table_unref (table2); 1724 1725 1726 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to 1727 * be sure that interface works. 1728 */ 1729 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 1730 dbus_free, dbus_free); 1731 if (table1 == NULL) 1732 goto out; 1733 1734 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 1735 NULL, dbus_free); 1736 if (table2 == NULL) 1737 goto out; 1738 1739 i = 0; 1740 while (i < 3000) 1741 { 1742 void *value; 1743 char *key; 1744 1745 key = _dbus_strdup (keys[i]); 1746 if (key == NULL) 1747 goto out; 1748 value = _dbus_strdup ("Value!"); 1749 if (value == NULL) 1750 goto out; 1751 1752 if (!_dbus_hash_iter_lookup (table1, 1753 key, TRUE, &iter)) 1754 goto out; 1755 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 1756 _dbus_hash_iter_set_value (&iter, value); 1757 1758 value = _dbus_strdup (keys[i]); 1759 if (value == NULL) 1760 goto out; 1761 1762 if (!_dbus_hash_iter_lookup (table2, 1763 _DBUS_INT_TO_POINTER (i), TRUE, &iter)) 1764 goto out; 1765 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 1766 _dbus_hash_iter_set_value (&iter, value); 1767 1768 _dbus_assert (count_entries (table1) == i + 1); 1769 _dbus_assert (count_entries (table2) == i + 1); 1770 1771 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 1772 goto out; 1773 1774 value = _dbus_hash_iter_get_value (&iter); 1775 _dbus_assert (value != NULL); 1776 _dbus_assert (strcmp (value, "Value!") == 0); 1777 1778 /* Iterate just to be sure it works, though 1779 * it's a stupid thing to do 1780 */ 1781 while (_dbus_hash_iter_next (&iter)) 1782 ; 1783 1784 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 1785 goto out; 1786 1787 value = _dbus_hash_iter_get_value (&iter); 1788 _dbus_assert (value != NULL); 1789 _dbus_assert (strcmp (value, keys[i]) == 0); 1790 1791 /* Iterate just to be sure it works, though 1792 * it's a stupid thing to do 1793 */ 1794 while (_dbus_hash_iter_next (&iter)) 1795 ; 1796 1797 ++i; 1798 } 1799 1800 --i; 1801 while (i >= 0) 1802 { 1803 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 1804 _dbus_assert_not_reached ("hash entry should have existed"); 1805 _dbus_hash_iter_remove_entry (&iter); 1806 1807 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 1808 _dbus_assert_not_reached ("hash entry should have existed"); 1809 _dbus_hash_iter_remove_entry (&iter); 1810 1811 _dbus_assert (count_entries (table1) == i); 1812 _dbus_assert (count_entries (table2) == i); 1813 1814 --i; 1815 } 1816 1817 _dbus_hash_table_unref (table1); 1818 _dbus_hash_table_unref (table2); 1819 1820 ret = TRUE; 1821 1822 out: 1823 for (i = 0; i < N_HASH_KEYS; i++) 1824 dbus_free (keys[i]); 1825 1826 dbus_free (keys); 1827 1828 return ret; 1829} 1830 1831#endif /* DBUS_BUILD_TESTS */ 1832