D-Bus 1.4.6
|
00001 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */ 00002 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation) 00003 * 00004 * Copyright (C) 2002 Red Hat, Inc. 00005 * Copyright (c) 1991-1993 The Regents of the University of California. 00006 * Copyright (c) 1994 Sun Microsystems, Inc. 00007 * 00008 * Hash table implementation based on generic/tclHash.c from the Tcl 00009 * source code. The original Tcl license applies to portions of the 00010 * code from tclHash.c; the Tcl license follows this standad D-Bus 00011 * license information. 00012 * 00013 * Licensed under the Academic Free License version 2.1 00014 * 00015 * This program is free software; you can redistribute it and/or modify 00016 * it under the terms of the GNU General Public License as published by 00017 * the Free Software Foundation; either version 2 of the License, or 00018 * (at your option) any later version. 00019 * 00020 * This program is distributed in the hope that it will be useful, 00021 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00022 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00023 * GNU General Public License for more details. 00024 * 00025 * You should have received a copy of the GNU General Public License 00026 * along with this program; if not, write to the Free Software 00027 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00028 * 00029 */ 00030 /* 00031 * The following copyright applies to code from the Tcl distribution. 00032 * 00033 * Copyright (c) 1991-1993 The Regents of the University of California. 00034 * Copyright (c) 1994 Sun Microsystems, Inc. 00035 * 00036 * This software is copyrighted by the Regents of the University of 00037 * California, Sun Microsystems, Inc., Scriptics Corporation, and 00038 * other parties. The following terms apply to all files associated 00039 * with the software unless explicitly disclaimed in individual files. 00040 * 00041 * The authors hereby grant permission to use, copy, modify, 00042 * distribute, and license this software and its documentation for any 00043 * purpose, provided that existing copyright notices are retained in 00044 * all copies and that this notice is included verbatim in any 00045 * distributions. No written agreement, license, or royalty fee is 00046 * required for any of the authorized uses. Modifications to this 00047 * software may be copyrighted by their authors and need not follow 00048 * the licensing terms described here, provided that the new terms are 00049 * clearly indicated on the first page of each file where they apply. 00050 * 00051 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY 00052 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL 00053 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, 00054 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED 00055 * OF THE POSSIBILITY OF SUCH DAMAGE. 00056 * 00057 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, 00058 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 00059 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND 00060 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, 00061 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE 00062 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 00063 * 00064 * GOVERNMENT USE: If you are acquiring this software on behalf of the 00065 * U.S. government, the Government shall have only "Restricted Rights" 00066 * in the software and related documentation as defined in the Federal 00067 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you 00068 * are acquiring the software on behalf of the Department of Defense, 00069 * the software shall be classified as "Commercial Computer Software" 00070 * and the Government shall have only "Restricted Rights" as defined 00071 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the 00072 * foregoing, the authors grant the U.S. Government and others acting 00073 * in its behalf permission to use and distribute the software in 00074 * accordance with the terms specified in this license. 00075 */ 00076 00077 #include <config.h> 00078 #include "dbus-hash.h" 00079 #include "dbus-internals.h" 00080 #include "dbus-mempool.h" 00081 00104 #define REBUILD_MULTIPLIER 3 00105 00122 #define RANDOM_INDEX(table, i) \ 00123 (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask) 00124 00130 #define DBUS_SMALL_HASH_TABLE 4 00131 00135 typedef struct DBusHashEntry DBusHashEntry; 00136 00143 struct DBusHashEntry 00144 { 00145 DBusHashEntry *next; 00149 void *key; 00150 void *value; 00151 }; 00152 00156 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table, 00157 void *key, 00158 dbus_bool_t create_if_not_found, 00159 DBusHashEntry ***bucket, 00160 DBusPreallocatedHash *preallocated); 00161 00168 struct DBusHashTable { 00169 int refcount; 00171 DBusHashEntry **buckets; 00175 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE]; 00179 int n_buckets; 00182 int n_entries; 00185 int hi_rebuild_size; 00188 int lo_rebuild_size; 00191 int down_shift; 00195 int mask; 00198 DBusHashType key_type; 00201 DBusFindEntryFunction find_function; 00203 DBusFreeFunction free_key_function; 00204 DBusFreeFunction free_value_function; 00206 DBusMemPool *entry_pool; 00207 }; 00208 00212 typedef struct 00213 { 00214 DBusHashTable *table; 00215 DBusHashEntry **bucket; 00219 DBusHashEntry *entry; 00220 DBusHashEntry *next_entry; 00221 int next_bucket; 00222 int n_entries_on_init; 00223 } DBusRealHashIter; 00224 00225 static DBusHashEntry* find_direct_function (DBusHashTable *table, 00226 void *key, 00227 dbus_bool_t create_if_not_found, 00228 DBusHashEntry ***bucket, 00229 DBusPreallocatedHash *preallocated); 00230 static DBusHashEntry* find_string_function (DBusHashTable *table, 00231 void *key, 00232 dbus_bool_t create_if_not_found, 00233 DBusHashEntry ***bucket, 00234 DBusPreallocatedHash *preallocated); 00235 #ifdef DBUS_BUILD_TESTS 00236 static DBusHashEntry* find_two_strings_function (DBusHashTable *table, 00237 void *key, 00238 dbus_bool_t create_if_not_found, 00239 DBusHashEntry ***bucket, 00240 DBusPreallocatedHash *preallocated); 00241 #endif 00242 static unsigned int string_hash (const char *str); 00243 #ifdef DBUS_BUILD_TESTS 00244 static unsigned int two_strings_hash (const char *str); 00245 #endif 00246 static void rebuild_table (DBusHashTable *table); 00247 static DBusHashEntry* alloc_entry (DBusHashTable *table); 00248 static void remove_entry (DBusHashTable *table, 00249 DBusHashEntry **bucket, 00250 DBusHashEntry *entry); 00251 static void free_entry (DBusHashTable *table, 00252 DBusHashEntry *entry); 00253 static void free_entry_data (DBusHashTable *table, 00254 DBusHashEntry *entry); 00255 00256 00292 DBusHashTable* 00293 _dbus_hash_table_new (DBusHashType type, 00294 DBusFreeFunction key_free_function, 00295 DBusFreeFunction value_free_function) 00296 { 00297 DBusHashTable *table; 00298 DBusMemPool *entry_pool; 00299 00300 table = dbus_new0 (DBusHashTable, 1); 00301 if (table == NULL) 00302 return NULL; 00303 00304 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE); 00305 if (entry_pool == NULL) 00306 { 00307 dbus_free (table); 00308 return NULL; 00309 } 00310 00311 table->refcount = 1; 00312 table->entry_pool = entry_pool; 00313 00314 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets)); 00315 00316 table->buckets = table->static_buckets; 00317 table->n_buckets = DBUS_SMALL_HASH_TABLE; 00318 table->n_entries = 0; 00319 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER; 00320 table->lo_rebuild_size = 0; 00321 table->down_shift = 28; 00322 table->mask = 3; 00323 table->key_type = type; 00324 00325 _dbus_assert (table->mask < table->n_buckets); 00326 00327 switch (table->key_type) 00328 { 00329 case DBUS_HASH_INT: 00330 case DBUS_HASH_POINTER: 00331 case DBUS_HASH_UINTPTR: 00332 table->find_function = find_direct_function; 00333 break; 00334 case DBUS_HASH_STRING: 00335 table->find_function = find_string_function; 00336 break; 00337 case DBUS_HASH_TWO_STRINGS: 00338 #ifdef DBUS_BUILD_TESTS 00339 table->find_function = find_two_strings_function; 00340 #endif 00341 break; 00342 default: 00343 _dbus_assert_not_reached ("Unknown hash table type"); 00344 break; 00345 } 00346 00347 table->free_key_function = key_free_function; 00348 table->free_value_function = value_free_function; 00349 00350 return table; 00351 } 00352 00353 00360 DBusHashTable * 00361 _dbus_hash_table_ref (DBusHashTable *table) 00362 { 00363 table->refcount += 1; 00364 00365 return table; 00366 } 00367 00374 void 00375 _dbus_hash_table_unref (DBusHashTable *table) 00376 { 00377 table->refcount -= 1; 00378 00379 if (table->refcount == 0) 00380 { 00381 #if 0 00382 DBusHashEntry *entry; 00383 DBusHashEntry *next; 00384 int i; 00385 00386 /* Free the entries in the table. */ 00387 for (i = 0; i < table->n_buckets; i++) 00388 { 00389 entry = table->buckets[i]; 00390 while (entry != NULL) 00391 { 00392 next = entry->next; 00393 00394 free_entry (table, entry); 00395 00396 entry = next; 00397 } 00398 } 00399 #else 00400 DBusHashEntry *entry; 00401 int i; 00402 00403 /* Free the entries in the table. */ 00404 for (i = 0; i < table->n_buckets; i++) 00405 { 00406 entry = table->buckets[i]; 00407 while (entry != NULL) 00408 { 00409 free_entry_data (table, entry); 00410 00411 entry = entry->next; 00412 } 00413 } 00414 /* We can do this very quickly with memory pools ;-) */ 00415 _dbus_mem_pool_free (table->entry_pool); 00416 #endif 00417 00418 /* Free the bucket array, if it was dynamically allocated. */ 00419 if (table->buckets != table->static_buckets) 00420 dbus_free (table->buckets); 00421 00422 dbus_free (table); 00423 } 00424 } 00425 00431 void 00432 _dbus_hash_table_remove_all (DBusHashTable *table) 00433 { 00434 DBusHashIter iter; 00435 _dbus_hash_iter_init (table, &iter); 00436 while (_dbus_hash_iter_next (&iter)) 00437 { 00438 _dbus_hash_iter_remove_entry(&iter); 00439 } 00440 } 00441 00442 static DBusHashEntry* 00443 alloc_entry (DBusHashTable *table) 00444 { 00445 DBusHashEntry *entry; 00446 00447 entry = _dbus_mem_pool_alloc (table->entry_pool); 00448 00449 return entry; 00450 } 00451 00452 static void 00453 free_entry_data (DBusHashTable *table, 00454 DBusHashEntry *entry) 00455 { 00456 if (table->free_key_function) 00457 (* table->free_key_function) (entry->key); 00458 if (table->free_value_function) 00459 (* table->free_value_function) (entry->value); 00460 } 00461 00462 static void 00463 free_entry (DBusHashTable *table, 00464 DBusHashEntry *entry) 00465 { 00466 free_entry_data (table, entry); 00467 _dbus_mem_pool_dealloc (table->entry_pool, entry); 00468 } 00469 00470 static void 00471 remove_entry (DBusHashTable *table, 00472 DBusHashEntry **bucket, 00473 DBusHashEntry *entry) 00474 { 00475 _dbus_assert (table != NULL); 00476 _dbus_assert (bucket != NULL); 00477 _dbus_assert (*bucket != NULL); 00478 _dbus_assert (entry != NULL); 00479 00480 if (*bucket == entry) 00481 *bucket = entry->next; 00482 else 00483 { 00484 DBusHashEntry *prev; 00485 prev = *bucket; 00486 00487 while (prev->next != entry) 00488 prev = prev->next; 00489 00490 _dbus_assert (prev != NULL); 00491 00492 prev->next = entry->next; 00493 } 00494 00495 table->n_entries -= 1; 00496 free_entry (table, entry); 00497 } 00498 00530 void 00531 _dbus_hash_iter_init (DBusHashTable *table, 00532 DBusHashIter *iter) 00533 { 00534 DBusRealHashIter *real; 00535 00536 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00537 00538 real = (DBusRealHashIter*) iter; 00539 00540 real->table = table; 00541 real->bucket = NULL; 00542 real->entry = NULL; 00543 real->next_entry = NULL; 00544 real->next_bucket = 0; 00545 real->n_entries_on_init = table->n_entries; 00546 } 00547 00556 dbus_bool_t 00557 _dbus_hash_iter_next (DBusHashIter *iter) 00558 { 00559 DBusRealHashIter *real; 00560 00561 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00562 00563 real = (DBusRealHashIter*) iter; 00564 00565 /* if this assertion failed someone probably added hash entries 00566 * during iteration, which is bad. 00567 */ 00568 _dbus_assert (real->n_entries_on_init >= real->table->n_entries); 00569 00570 /* Remember that real->entry may have been deleted */ 00571 00572 while (real->next_entry == NULL) 00573 { 00574 if (real->next_bucket >= real->table->n_buckets) 00575 { 00576 /* invalidate iter and return false */ 00577 real->entry = NULL; 00578 real->table = NULL; 00579 real->bucket = NULL; 00580 return FALSE; 00581 } 00582 00583 real->bucket = &(real->table->buckets[real->next_bucket]); 00584 real->next_entry = *(real->bucket); 00585 real->next_bucket += 1; 00586 } 00587 00588 _dbus_assert (real->next_entry != NULL); 00589 _dbus_assert (real->bucket != NULL); 00590 00591 real->entry = real->next_entry; 00592 real->next_entry = real->entry->next; 00593 00594 return TRUE; 00595 } 00596 00605 void 00606 _dbus_hash_iter_remove_entry (DBusHashIter *iter) 00607 { 00608 DBusRealHashIter *real; 00609 00610 real = (DBusRealHashIter*) iter; 00611 00612 _dbus_assert (real->table != NULL); 00613 _dbus_assert (real->entry != NULL); 00614 _dbus_assert (real->bucket != NULL); 00615 00616 remove_entry (real->table, real->bucket, real->entry); 00617 00618 real->entry = NULL; /* make it crash if you try to use this entry */ 00619 } 00620 00626 void* 00627 _dbus_hash_iter_get_value (DBusHashIter *iter) 00628 { 00629 DBusRealHashIter *real; 00630 00631 real = (DBusRealHashIter*) iter; 00632 00633 _dbus_assert (real->table != NULL); 00634 _dbus_assert (real->entry != NULL); 00635 00636 return real->entry->value; 00637 } 00638 00649 void 00650 _dbus_hash_iter_set_value (DBusHashIter *iter, 00651 void *value) 00652 { 00653 DBusRealHashIter *real; 00654 00655 real = (DBusRealHashIter*) iter; 00656 00657 _dbus_assert (real->table != NULL); 00658 _dbus_assert (real->entry != NULL); 00659 00660 if (real->table->free_value_function && value != real->entry->value) 00661 (* real->table->free_value_function) (real->entry->value); 00662 00663 real->entry->value = value; 00664 } 00665 00672 int 00673 _dbus_hash_iter_get_int_key (DBusHashIter *iter) 00674 { 00675 DBusRealHashIter *real; 00676 00677 real = (DBusRealHashIter*) iter; 00678 00679 _dbus_assert (real->table != NULL); 00680 _dbus_assert (real->entry != NULL); 00681 00682 return _DBUS_POINTER_TO_INT (real->entry->key); 00683 } 00684 00691 uintptr_t 00692 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter) 00693 { 00694 DBusRealHashIter *real; 00695 00696 real = (DBusRealHashIter*) iter; 00697 00698 _dbus_assert (real->table != NULL); 00699 _dbus_assert (real->entry != NULL); 00700 00701 return (uintptr_t) real->entry->key; 00702 } 00703 00709 const char* 00710 _dbus_hash_iter_get_string_key (DBusHashIter *iter) 00711 { 00712 DBusRealHashIter *real; 00713 00714 real = (DBusRealHashIter*) iter; 00715 00716 _dbus_assert (real->table != NULL); 00717 _dbus_assert (real->entry != NULL); 00718 00719 return real->entry->key; 00720 } 00721 00722 #ifdef DBUS_BUILD_TESTS 00723 00728 const char* 00729 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter) 00730 { 00731 DBusRealHashIter *real; 00732 00733 real = (DBusRealHashIter*) iter; 00734 00735 _dbus_assert (real->table != NULL); 00736 _dbus_assert (real->entry != NULL); 00737 00738 return real->entry->key; 00739 } 00740 #endif /* DBUS_BUILD_TESTS */ 00741 00773 dbus_bool_t 00774 _dbus_hash_iter_lookup (DBusHashTable *table, 00775 void *key, 00776 dbus_bool_t create_if_not_found, 00777 DBusHashIter *iter) 00778 { 00779 DBusRealHashIter *real; 00780 DBusHashEntry *entry; 00781 DBusHashEntry **bucket; 00782 00783 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00784 00785 real = (DBusRealHashIter*) iter; 00786 00787 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL); 00788 00789 if (entry == NULL) 00790 return FALSE; 00791 00792 real->table = table; 00793 real->bucket = bucket; 00794 real->entry = entry; 00795 real->next_entry = entry->next; 00796 real->next_bucket = (bucket - table->buckets) + 1; 00797 real->n_entries_on_init = table->n_entries; 00798 00799 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket); 00800 00801 return TRUE; 00802 } 00803 00804 static void 00805 add_allocated_entry (DBusHashTable *table, 00806 DBusHashEntry *entry, 00807 unsigned int idx, 00808 void *key, 00809 DBusHashEntry ***bucket) 00810 { 00811 DBusHashEntry **b; 00812 00813 entry->key = key; 00814 00815 b = &(table->buckets[idx]); 00816 entry->next = *b; 00817 *b = entry; 00818 00819 if (bucket) 00820 *bucket = b; 00821 00822 table->n_entries += 1; 00823 00824 /* note we ONLY rebuild when ADDING - because you can iterate over a 00825 * table and remove entries safely. 00826 */ 00827 if (table->n_entries >= table->hi_rebuild_size || 00828 table->n_entries < table->lo_rebuild_size) 00829 rebuild_table (table); 00830 } 00831 00832 static DBusHashEntry* 00833 add_entry (DBusHashTable *table, 00834 unsigned int idx, 00835 void *key, 00836 DBusHashEntry ***bucket, 00837 DBusPreallocatedHash *preallocated) 00838 { 00839 DBusHashEntry *entry; 00840 00841 if (preallocated == NULL) 00842 { 00843 entry = alloc_entry (table); 00844 if (entry == NULL) 00845 { 00846 if (bucket) 00847 *bucket = NULL; 00848 return NULL; 00849 } 00850 } 00851 else 00852 { 00853 entry = (DBusHashEntry*) preallocated; 00854 } 00855 00856 add_allocated_entry (table, entry, idx, key, bucket); 00857 00858 return entry; 00859 } 00860 00861 /* This is g_str_hash from GLib which was 00862 * extensively discussed/tested/profiled 00863 */ 00864 static unsigned int 00865 string_hash (const char *str) 00866 { 00867 const char *p = str; 00868 unsigned int h = *p; 00869 00870 if (h) 00871 for (p += 1; *p != '\0'; p++) 00872 h = (h << 5) - h + *p; 00873 00874 return h; 00875 } 00876 00877 #ifdef DBUS_BUILD_TESTS 00878 /* This hashes a memory block with two nul-terminated strings 00879 * in it, used in dbus-object-registry.c at the moment. 00880 */ 00881 static unsigned int 00882 two_strings_hash (const char *str) 00883 { 00884 const char *p = str; 00885 unsigned int h = *p; 00886 00887 if (h) 00888 for (p += 1; *p != '\0'; p++) 00889 h = (h << 5) - h + *p; 00890 00891 for (p += 1; *p != '\0'; p++) 00892 h = (h << 5) - h + *p; 00893 00894 return h; 00895 } 00896 #endif /* DBUS_BUILD_TESTS */ 00897 00899 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b); 00900 00901 static DBusHashEntry* 00902 find_generic_function (DBusHashTable *table, 00903 void *key, 00904 unsigned int idx, 00905 KeyCompareFunc compare_func, 00906 dbus_bool_t create_if_not_found, 00907 DBusHashEntry ***bucket, 00908 DBusPreallocatedHash *preallocated) 00909 { 00910 DBusHashEntry *entry; 00911 00912 if (bucket) 00913 *bucket = NULL; 00914 00915 /* Search all of the entries in this bucket. */ 00916 entry = table->buckets[idx]; 00917 while (entry != NULL) 00918 { 00919 if ((compare_func == NULL && key == entry->key) || 00920 (compare_func != NULL && (* compare_func) (key, entry->key) == 0)) 00921 { 00922 if (bucket) 00923 *bucket = &(table->buckets[idx]); 00924 00925 if (preallocated) 00926 _dbus_hash_table_free_preallocated_entry (table, preallocated); 00927 00928 return entry; 00929 } 00930 00931 entry = entry->next; 00932 } 00933 00934 if (create_if_not_found) 00935 entry = add_entry (table, idx, key, bucket, preallocated); 00936 else if (preallocated) 00937 _dbus_hash_table_free_preallocated_entry (table, preallocated); 00938 00939 return entry; 00940 } 00941 00942 static DBusHashEntry* 00943 find_string_function (DBusHashTable *table, 00944 void *key, 00945 dbus_bool_t create_if_not_found, 00946 DBusHashEntry ***bucket, 00947 DBusPreallocatedHash *preallocated) 00948 { 00949 unsigned int idx; 00950 00951 idx = string_hash (key) & table->mask; 00952 00953 return find_generic_function (table, key, idx, 00954 (KeyCompareFunc) strcmp, create_if_not_found, bucket, 00955 preallocated); 00956 } 00957 00958 #ifdef DBUS_BUILD_TESTS 00959 static int 00960 two_strings_cmp (const char *a, 00961 const char *b) 00962 { 00963 size_t len_a; 00964 size_t len_b; 00965 int res; 00966 00967 res = strcmp (a, b); 00968 if (res != 0) 00969 return res; 00970 00971 len_a = strlen (a); 00972 len_b = strlen (b); 00973 00974 return strcmp (a + len_a + 1, b + len_b + 1); 00975 } 00976 #endif 00977 00978 #ifdef DBUS_BUILD_TESTS 00979 static DBusHashEntry* 00980 find_two_strings_function (DBusHashTable *table, 00981 void *key, 00982 dbus_bool_t create_if_not_found, 00983 DBusHashEntry ***bucket, 00984 DBusPreallocatedHash *preallocated) 00985 { 00986 unsigned int idx; 00987 00988 idx = two_strings_hash (key) & table->mask; 00989 00990 return find_generic_function (table, key, idx, 00991 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket, 00992 preallocated); 00993 } 00994 #endif /* DBUS_BUILD_TESTS */ 00995 00996 static DBusHashEntry* 00997 find_direct_function (DBusHashTable *table, 00998 void *key, 00999 dbus_bool_t create_if_not_found, 01000 DBusHashEntry ***bucket, 01001 DBusPreallocatedHash *preallocated) 01002 { 01003 unsigned int idx; 01004 01005 idx = RANDOM_INDEX (table, key) & table->mask; 01006 01007 01008 return find_generic_function (table, key, idx, 01009 NULL, create_if_not_found, bucket, 01010 preallocated); 01011 } 01012 01013 static void 01014 rebuild_table (DBusHashTable *table) 01015 { 01016 int old_size; 01017 int new_buckets; 01018 DBusHashEntry **old_buckets; 01019 DBusHashEntry **old_chain; 01020 DBusHashEntry *entry; 01021 dbus_bool_t growing; 01022 01023 /* 01024 * Allocate and initialize the new bucket array, and set up 01025 * hashing constants for new array size. 01026 */ 01027 01028 growing = table->n_entries >= table->hi_rebuild_size; 01029 01030 old_size = table->n_buckets; 01031 old_buckets = table->buckets; 01032 01033 if (growing) 01034 { 01035 /* overflow paranoia */ 01036 if (table->n_buckets < _DBUS_INT_MAX / 4 && 01037 table->down_shift >= 0) 01038 new_buckets = table->n_buckets * 4; 01039 else 01040 return; /* can't grow anymore */ 01041 } 01042 else 01043 { 01044 new_buckets = table->n_buckets / 4; 01045 if (new_buckets < DBUS_SMALL_HASH_TABLE) 01046 return; /* don't bother shrinking this far */ 01047 } 01048 01049 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets); 01050 if (table->buckets == NULL) 01051 { 01052 /* out of memory, yay - just don't reallocate, the table will 01053 * still work, albeit more slowly. 01054 */ 01055 table->buckets = old_buckets; 01056 return; 01057 } 01058 01059 table->n_buckets = new_buckets; 01060 01061 if (growing) 01062 { 01063 table->lo_rebuild_size = table->hi_rebuild_size; 01064 table->hi_rebuild_size *= 4; 01065 01066 table->down_shift -= 2; /* keep 2 more high bits */ 01067 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */ 01068 } 01069 else 01070 { 01071 table->hi_rebuild_size = table->lo_rebuild_size; 01072 table->lo_rebuild_size /= 4; 01073 01074 table->down_shift += 2; /* keep 2 fewer high bits */ 01075 table->mask = table->mask >> 2; /* keep 2 fewer high bits */ 01076 } 01077 01078 #if 0 01079 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", 01080 growing ? "GROW" : "SHRINK", 01081 table->lo_rebuild_size, 01082 table->hi_rebuild_size, 01083 table->down_shift, 01084 table->mask); 01085 #endif 01086 01087 _dbus_assert (table->lo_rebuild_size >= 0); 01088 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size); 01089 _dbus_assert (table->mask != 0); 01090 /* the mask is essentially the max index */ 01091 _dbus_assert (table->mask < table->n_buckets); 01092 01093 /* 01094 * Rehash all of the existing entries into the new bucket array. 01095 */ 01096 01097 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++) 01098 { 01099 for (entry = *old_chain; entry != NULL; entry = *old_chain) 01100 { 01101 unsigned int idx; 01102 DBusHashEntry **bucket; 01103 01104 *old_chain = entry->next; 01105 switch (table->key_type) 01106 { 01107 case DBUS_HASH_STRING: 01108 idx = string_hash (entry->key) & table->mask; 01109 break; 01110 case DBUS_HASH_TWO_STRINGS: 01111 #ifdef DBUS_BUILD_TESTS 01112 idx = two_strings_hash (entry->key) & table->mask; 01113 #else 01114 idx = 0; 01115 _dbus_assert_not_reached ("two-strings is not enabled"); 01116 #endif 01117 break; 01118 case DBUS_HASH_INT: 01119 case DBUS_HASH_UINTPTR: 01120 case DBUS_HASH_POINTER: 01121 idx = RANDOM_INDEX (table, entry->key); 01122 break; 01123 default: 01124 idx = 0; 01125 _dbus_assert_not_reached ("Unknown hash table type"); 01126 break; 01127 } 01128 01129 bucket = &(table->buckets[idx]); 01130 entry->next = *bucket; 01131 *bucket = entry; 01132 } 01133 } 01134 01135 /* Free the old bucket array, if it was dynamically allocated. */ 01136 01137 if (old_buckets != table->static_buckets) 01138 dbus_free (old_buckets); 01139 } 01140 01150 void* 01151 _dbus_hash_table_lookup_string (DBusHashTable *table, 01152 const char *key) 01153 { 01154 DBusHashEntry *entry; 01155 01156 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01157 01158 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 01159 01160 if (entry) 01161 return entry->value; 01162 else 01163 return NULL; 01164 } 01165 01166 #ifdef DBUS_BUILD_TESTS 01167 01176 void* 01177 _dbus_hash_table_lookup_two_strings (DBusHashTable *table, 01178 const char *key) 01179 { 01180 DBusHashEntry *entry; 01181 01182 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01183 01184 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 01185 01186 if (entry) 01187 return entry->value; 01188 else 01189 return NULL; 01190 } 01191 #endif /* DBUS_BUILD_TESTS */ 01192 01202 void* 01203 _dbus_hash_table_lookup_int (DBusHashTable *table, 01204 int key) 01205 { 01206 DBusHashEntry *entry; 01207 01208 _dbus_assert (table->key_type == DBUS_HASH_INT); 01209 01210 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL); 01211 01212 if (entry) 01213 return entry->value; 01214 else 01215 return NULL; 01216 } 01217 01218 #ifdef DBUS_BUILD_TESTS 01219 /* disabled since it's only used for testing */ 01229 void* 01230 _dbus_hash_table_lookup_pointer (DBusHashTable *table, 01231 void *key) 01232 { 01233 DBusHashEntry *entry; 01234 01235 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01236 01237 entry = (* table->find_function) (table, key, FALSE, NULL, NULL); 01238 01239 if (entry) 01240 return entry->value; 01241 else 01242 return NULL; 01243 } 01244 #endif /* DBUS_BUILD_TESTS */ 01245 01255 void* 01256 _dbus_hash_table_lookup_uintptr (DBusHashTable *table, 01257 uintptr_t key) 01258 { 01259 DBusHashEntry *entry; 01260 01261 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01262 01263 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL); 01264 01265 if (entry) 01266 return entry->value; 01267 else 01268 return NULL; 01269 } 01270 01279 dbus_bool_t 01280 _dbus_hash_table_remove_string (DBusHashTable *table, 01281 const char *key) 01282 { 01283 DBusHashEntry *entry; 01284 DBusHashEntry **bucket; 01285 01286 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01287 01288 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 01289 01290 if (entry) 01291 { 01292 remove_entry (table, bucket, entry); 01293 return TRUE; 01294 } 01295 else 01296 return FALSE; 01297 } 01298 01299 #ifdef DBUS_BUILD_TESTS 01300 01308 dbus_bool_t 01309 _dbus_hash_table_remove_two_strings (DBusHashTable *table, 01310 const char *key) 01311 { 01312 DBusHashEntry *entry; 01313 DBusHashEntry **bucket; 01314 01315 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01316 01317 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 01318 01319 if (entry) 01320 { 01321 remove_entry (table, bucket, entry); 01322 return TRUE; 01323 } 01324 else 01325 return FALSE; 01326 } 01327 #endif /* DBUS_BUILD_TESTS */ 01328 01337 dbus_bool_t 01338 _dbus_hash_table_remove_int (DBusHashTable *table, 01339 int key) 01340 { 01341 DBusHashEntry *entry; 01342 DBusHashEntry **bucket; 01343 01344 _dbus_assert (table->key_type == DBUS_HASH_INT); 01345 01346 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL); 01347 01348 if (entry) 01349 { 01350 remove_entry (table, bucket, entry); 01351 return TRUE; 01352 } 01353 else 01354 return FALSE; 01355 } 01356 01357 #ifdef DBUS_BUILD_TESTS 01358 /* disabled since it's only used for testing */ 01367 dbus_bool_t 01368 _dbus_hash_table_remove_pointer (DBusHashTable *table, 01369 void *key) 01370 { 01371 DBusHashEntry *entry; 01372 DBusHashEntry **bucket; 01373 01374 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01375 01376 entry = (* table->find_function) (table, key, FALSE, &bucket, NULL); 01377 01378 if (entry) 01379 { 01380 remove_entry (table, bucket, entry); 01381 return TRUE; 01382 } 01383 else 01384 return FALSE; 01385 } 01386 #endif /* DBUS_BUILD_TESTS */ 01387 01396 dbus_bool_t 01397 _dbus_hash_table_remove_uintptr (DBusHashTable *table, 01398 uintptr_t key) 01399 { 01400 DBusHashEntry *entry; 01401 DBusHashEntry **bucket; 01402 01403 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01404 01405 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL); 01406 01407 if (entry) 01408 { 01409 remove_entry (table, bucket, entry); 01410 return TRUE; 01411 } 01412 else 01413 return FALSE; 01414 } 01415 01431 dbus_bool_t 01432 _dbus_hash_table_insert_string (DBusHashTable *table, 01433 char *key, 01434 void *value) 01435 { 01436 DBusPreallocatedHash *preallocated; 01437 01438 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01439 01440 preallocated = _dbus_hash_table_preallocate_entry (table); 01441 if (preallocated == NULL) 01442 return FALSE; 01443 01444 _dbus_hash_table_insert_string_preallocated (table, preallocated, 01445 key, value); 01446 01447 return TRUE; 01448 } 01449 01450 #ifdef DBUS_BUILD_TESTS 01451 01466 dbus_bool_t 01467 _dbus_hash_table_insert_two_strings (DBusHashTable *table, 01468 char *key, 01469 void *value) 01470 { 01471 DBusHashEntry *entry; 01472 01473 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01474 01475 entry = (* table->find_function) (table, key, TRUE, NULL, NULL); 01476 01477 if (entry == NULL) 01478 return FALSE; /* no memory */ 01479 01480 if (table->free_key_function && entry->key != key) 01481 (* table->free_key_function) (entry->key); 01482 01483 if (table->free_value_function && entry->value != value) 01484 (* table->free_value_function) (entry->value); 01485 01486 entry->key = key; 01487 entry->value = value; 01488 01489 return TRUE; 01490 } 01491 #endif /* DBUS_BUILD_TESTS */ 01492 01508 dbus_bool_t 01509 _dbus_hash_table_insert_int (DBusHashTable *table, 01510 int key, 01511 void *value) 01512 { 01513 DBusHashEntry *entry; 01514 01515 _dbus_assert (table->key_type == DBUS_HASH_INT); 01516 01517 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL); 01518 01519 if (entry == NULL) 01520 return FALSE; /* no memory */ 01521 01522 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key)) 01523 (* table->free_key_function) (entry->key); 01524 01525 if (table->free_value_function && entry->value != value) 01526 (* table->free_value_function) (entry->value); 01527 01528 entry->key = _DBUS_INT_TO_POINTER (key); 01529 entry->value = value; 01530 01531 return TRUE; 01532 } 01533 01534 #ifdef DBUS_BUILD_TESTS 01535 /* disabled since it's only used for testing */ 01551 dbus_bool_t 01552 _dbus_hash_table_insert_pointer (DBusHashTable *table, 01553 void *key, 01554 void *value) 01555 { 01556 DBusHashEntry *entry; 01557 01558 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01559 01560 entry = (* table->find_function) (table, key, TRUE, NULL, NULL); 01561 01562 if (entry == NULL) 01563 return FALSE; /* no memory */ 01564 01565 if (table->free_key_function && entry->key != key) 01566 (* table->free_key_function) (entry->key); 01567 01568 if (table->free_value_function && entry->value != value) 01569 (* table->free_value_function) (entry->value); 01570 01571 entry->key = key; 01572 entry->value = value; 01573 01574 return TRUE; 01575 } 01576 #endif /* DBUS_BUILD_TESTS */ 01577 01593 dbus_bool_t 01594 _dbus_hash_table_insert_uintptr (DBusHashTable *table, 01595 uintptr_t key, 01596 void *value) 01597 { 01598 DBusHashEntry *entry; 01599 01600 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01601 01602 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL); 01603 01604 if (entry == NULL) 01605 return FALSE; /* no memory */ 01606 01607 if (table->free_key_function && entry->key != (void*) key) 01608 (* table->free_key_function) (entry->key); 01609 01610 if (table->free_value_function && entry->value != value) 01611 (* table->free_value_function) (entry->value); 01612 01613 entry->key = (void*) key; 01614 entry->value = value; 01615 01616 return TRUE; 01617 } 01618 01626 DBusPreallocatedHash* 01627 _dbus_hash_table_preallocate_entry (DBusHashTable *table) 01628 { 01629 DBusHashEntry *entry; 01630 01631 entry = alloc_entry (table); 01632 01633 return (DBusPreallocatedHash*) entry; 01634 } 01635 01643 void 01644 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table, 01645 DBusPreallocatedHash *preallocated) 01646 { 01647 DBusHashEntry *entry; 01648 01649 _dbus_assert (preallocated != NULL); 01650 01651 entry = (DBusHashEntry*) preallocated; 01652 01653 /* Don't use free_entry(), since this entry has no key/data */ 01654 _dbus_mem_pool_dealloc (table->entry_pool, entry); 01655 } 01656 01670 void 01671 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table, 01672 DBusPreallocatedHash *preallocated, 01673 char *key, 01674 void *value) 01675 { 01676 DBusHashEntry *entry; 01677 01678 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01679 _dbus_assert (preallocated != NULL); 01680 01681 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated); 01682 01683 _dbus_assert (entry != NULL); 01684 01685 if (table->free_key_function && entry->key != key) 01686 (* table->free_key_function) (entry->key); 01687 01688 if (table->free_value_function && entry->value != value) 01689 (* table->free_value_function) (entry->value); 01690 01691 entry->key = key; 01692 entry->value = value; 01693 } 01694 01701 int 01702 _dbus_hash_table_get_n_entries (DBusHashTable *table) 01703 { 01704 return table->n_entries; 01705 } 01706 01709 #ifdef DBUS_BUILD_TESTS 01710 #include "dbus-test.h" 01711 #include <stdio.h> 01712 01713 /* If you're wondering why the hash table test takes 01714 * forever to run, it's because we call this function 01715 * in inner loops thus making things quadratic. 01716 */ 01717 static int 01718 count_entries (DBusHashTable *table) 01719 { 01720 DBusHashIter iter; 01721 int count; 01722 01723 count = 0; 01724 _dbus_hash_iter_init (table, &iter); 01725 while (_dbus_hash_iter_next (&iter)) 01726 ++count; 01727 01728 _dbus_assert (count == _dbus_hash_table_get_n_entries (table)); 01729 01730 return count; 01731 } 01732 01733 /* Copy the foo\0bar\0 double string thing */ 01734 static char* 01735 _dbus_strdup2 (const char *str) 01736 { 01737 size_t len; 01738 char *copy; 01739 01740 if (str == NULL) 01741 return NULL; 01742 01743 len = strlen (str); 01744 len += strlen ((str + len + 1)); 01745 01746 copy = dbus_malloc (len + 2); 01747 if (copy == NULL) 01748 return NULL; 01749 01750 memcpy (copy, str, len + 2); 01751 01752 return copy; 01753 } 01754 01760 dbus_bool_t 01761 _dbus_hash_test (void) 01762 { 01763 int i; 01764 DBusHashTable *table1; 01765 DBusHashTable *table2; 01766 DBusHashTable *table3; 01767 DBusHashTable *table4; 01768 DBusHashIter iter; 01769 #define N_HASH_KEYS 5000 01770 char **keys; 01771 dbus_bool_t ret = FALSE; 01772 01773 keys = dbus_new (char *, N_HASH_KEYS); 01774 if (keys == NULL) 01775 _dbus_assert_not_reached ("no memory"); 01776 01777 for (i = 0; i < N_HASH_KEYS; i++) 01778 { 01779 keys[i] = dbus_malloc (128); 01780 01781 if (keys[i] == NULL) 01782 _dbus_assert_not_reached ("no memory"); 01783 } 01784 01785 printf ("Computing test hash keys...\n"); 01786 i = 0; 01787 while (i < N_HASH_KEYS) 01788 { 01789 int len; 01790 01791 /* all the hash keys are TWO_STRINGS, but 01792 * then we can also use those as regular strings. 01793 */ 01794 01795 len = sprintf (keys[i], "Hash key %d", i); 01796 sprintf (keys[i] + len + 1, "Two string %d", i); 01797 _dbus_assert (*(keys[i] + len) == '\0'); 01798 _dbus_assert (*(keys[i] + len + 1) != '\0'); 01799 ++i; 01800 } 01801 printf ("... done.\n"); 01802 01803 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01804 dbus_free, dbus_free); 01805 if (table1 == NULL) 01806 goto out; 01807 01808 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01809 NULL, dbus_free); 01810 if (table2 == NULL) 01811 goto out; 01812 01813 table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR, 01814 NULL, dbus_free); 01815 if (table3 == NULL) 01816 goto out; 01817 01818 table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS, 01819 dbus_free, dbus_free); 01820 if (table4 == NULL) 01821 goto out; 01822 01823 01824 /* Insert and remove a bunch of stuff, counting the table in between 01825 * to be sure it's not broken and that iteration works 01826 */ 01827 i = 0; 01828 while (i < 3000) 01829 { 01830 void *value; 01831 char *key; 01832 01833 key = _dbus_strdup (keys[i]); 01834 if (key == NULL) 01835 goto out; 01836 value = _dbus_strdup ("Value!"); 01837 if (value == NULL) 01838 goto out; 01839 01840 if (!_dbus_hash_table_insert_string (table1, 01841 key, value)) 01842 goto out; 01843 01844 value = _dbus_strdup (keys[i]); 01845 if (value == NULL) 01846 goto out; 01847 01848 if (!_dbus_hash_table_insert_int (table2, 01849 i, value)) 01850 goto out; 01851 01852 value = _dbus_strdup (keys[i]); 01853 if (value == NULL) 01854 goto out; 01855 01856 if (!_dbus_hash_table_insert_uintptr (table3, 01857 i, value)) 01858 goto out; 01859 01860 key = _dbus_strdup2 (keys[i]); 01861 if (key == NULL) 01862 goto out; 01863 value = _dbus_strdup ("Value!"); 01864 if (value == NULL) 01865 goto out; 01866 01867 if (!_dbus_hash_table_insert_two_strings (table4, 01868 key, value)) 01869 goto out; 01870 01871 _dbus_assert (count_entries (table1) == i + 1); 01872 _dbus_assert (count_entries (table2) == i + 1); 01873 _dbus_assert (count_entries (table3) == i + 1); 01874 _dbus_assert (count_entries (table4) == i + 1); 01875 01876 value = _dbus_hash_table_lookup_string (table1, keys[i]); 01877 _dbus_assert (value != NULL); 01878 _dbus_assert (strcmp (value, "Value!") == 0); 01879 01880 value = _dbus_hash_table_lookup_int (table2, i); 01881 _dbus_assert (value != NULL); 01882 _dbus_assert (strcmp (value, keys[i]) == 0); 01883 01884 value = _dbus_hash_table_lookup_uintptr (table3, i); 01885 _dbus_assert (value != NULL); 01886 _dbus_assert (strcmp (value, keys[i]) == 0); 01887 01888 value = _dbus_hash_table_lookup_two_strings (table4, keys[i]); 01889 _dbus_assert (value != NULL); 01890 _dbus_assert (strcmp (value, "Value!") == 0); 01891 01892 ++i; 01893 } 01894 01895 --i; 01896 while (i >= 0) 01897 { 01898 _dbus_hash_table_remove_string (table1, 01899 keys[i]); 01900 01901 _dbus_hash_table_remove_int (table2, i); 01902 01903 _dbus_hash_table_remove_uintptr (table3, i); 01904 01905 _dbus_hash_table_remove_two_strings (table4, 01906 keys[i]); 01907 01908 _dbus_assert (count_entries (table1) == i); 01909 _dbus_assert (count_entries (table2) == i); 01910 _dbus_assert (count_entries (table3) == i); 01911 _dbus_assert (count_entries (table4) == i); 01912 01913 --i; 01914 } 01915 01916 _dbus_hash_table_ref (table1); 01917 _dbus_hash_table_ref (table2); 01918 _dbus_hash_table_ref (table3); 01919 _dbus_hash_table_ref (table4); 01920 _dbus_hash_table_unref (table1); 01921 _dbus_hash_table_unref (table2); 01922 _dbus_hash_table_unref (table3); 01923 _dbus_hash_table_unref (table4); 01924 _dbus_hash_table_unref (table1); 01925 _dbus_hash_table_unref (table2); 01926 _dbus_hash_table_unref (table3); 01927 _dbus_hash_table_unref (table4); 01928 table3 = NULL; 01929 01930 /* Insert a bunch of stuff then check 01931 * that iteration works correctly (finds the right 01932 * values, iter_set_value works, etc.) 01933 */ 01934 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01935 dbus_free, dbus_free); 01936 if (table1 == NULL) 01937 goto out; 01938 01939 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01940 NULL, dbus_free); 01941 if (table2 == NULL) 01942 goto out; 01943 01944 i = 0; 01945 while (i < 5000) 01946 { 01947 char *key; 01948 void *value; 01949 01950 key = _dbus_strdup (keys[i]); 01951 if (key == NULL) 01952 goto out; 01953 value = _dbus_strdup ("Value!"); 01954 if (value == NULL) 01955 goto out; 01956 01957 if (!_dbus_hash_table_insert_string (table1, 01958 key, value)) 01959 goto out; 01960 01961 value = _dbus_strdup (keys[i]); 01962 if (value == NULL) 01963 goto out; 01964 01965 if (!_dbus_hash_table_insert_int (table2, 01966 i, value)) 01967 goto out; 01968 01969 _dbus_assert (count_entries (table1) == i + 1); 01970 _dbus_assert (count_entries (table2) == i + 1); 01971 01972 ++i; 01973 } 01974 01975 _dbus_hash_iter_init (table1, &iter); 01976 while (_dbus_hash_iter_next (&iter)) 01977 { 01978 const char *key; 01979 void *value; 01980 01981 key = _dbus_hash_iter_get_string_key (&iter); 01982 value = _dbus_hash_iter_get_value (&iter); 01983 01984 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 01985 01986 value = _dbus_strdup ("Different value!"); 01987 if (value == NULL) 01988 goto out; 01989 01990 _dbus_hash_iter_set_value (&iter, value); 01991 01992 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 01993 } 01994 01995 _dbus_hash_iter_init (table1, &iter); 01996 while (_dbus_hash_iter_next (&iter)) 01997 { 01998 _dbus_hash_iter_remove_entry (&iter); 01999 _dbus_assert (count_entries (table1) == i - 1); 02000 --i; 02001 } 02002 02003 _dbus_hash_iter_init (table2, &iter); 02004 while (_dbus_hash_iter_next (&iter)) 02005 { 02006 int key; 02007 void *value; 02008 02009 key = _dbus_hash_iter_get_int_key (&iter); 02010 value = _dbus_hash_iter_get_value (&iter); 02011 02012 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 02013 02014 value = _dbus_strdup ("Different value!"); 02015 if (value == NULL) 02016 goto out; 02017 02018 _dbus_hash_iter_set_value (&iter, value); 02019 02020 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 02021 } 02022 02023 i = count_entries (table2); 02024 _dbus_hash_iter_init (table2, &iter); 02025 while (_dbus_hash_iter_next (&iter)) 02026 { 02027 _dbus_hash_iter_remove_entry (&iter); 02028 _dbus_assert (count_entries (table2) + 1 == i); 02029 --i; 02030 } 02031 02032 /* add/remove interleaved, to check that we grow/shrink the table 02033 * appropriately 02034 */ 02035 i = 0; 02036 while (i < 1000) 02037 { 02038 char *key; 02039 void *value; 02040 02041 key = _dbus_strdup (keys[i]); 02042 if (key == NULL) 02043 goto out; 02044 02045 value = _dbus_strdup ("Value!"); 02046 if (value == NULL) 02047 goto out; 02048 02049 if (!_dbus_hash_table_insert_string (table1, 02050 key, value)) 02051 goto out; 02052 02053 ++i; 02054 } 02055 02056 --i; 02057 while (i >= 0) 02058 { 02059 char *key; 02060 void *value; 02061 02062 key = _dbus_strdup (keys[i]); 02063 if (key == NULL) 02064 goto out; 02065 value = _dbus_strdup ("Value!"); 02066 if (value == NULL) 02067 goto out; 02068 02069 if (!_dbus_hash_table_remove_string (table1, keys[i])) 02070 goto out; 02071 02072 if (!_dbus_hash_table_insert_string (table1, 02073 key, value)) 02074 goto out; 02075 02076 if (!_dbus_hash_table_remove_string (table1, keys[i])) 02077 goto out; 02078 02079 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i); 02080 02081 --i; 02082 } 02083 02084 /* nuke these tables */ 02085 _dbus_hash_table_unref (table1); 02086 _dbus_hash_table_unref (table2); 02087 02088 02089 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to 02090 * be sure that interface works. 02091 */ 02092 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 02093 dbus_free, dbus_free); 02094 if (table1 == NULL) 02095 goto out; 02096 02097 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 02098 NULL, dbus_free); 02099 if (table2 == NULL) 02100 goto out; 02101 02102 i = 0; 02103 while (i < 3000) 02104 { 02105 void *value; 02106 char *key; 02107 02108 key = _dbus_strdup (keys[i]); 02109 if (key == NULL) 02110 goto out; 02111 value = _dbus_strdup ("Value!"); 02112 if (value == NULL) 02113 goto out; 02114 02115 if (!_dbus_hash_iter_lookup (table1, 02116 key, TRUE, &iter)) 02117 goto out; 02118 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 02119 _dbus_hash_iter_set_value (&iter, value); 02120 02121 value = _dbus_strdup (keys[i]); 02122 if (value == NULL) 02123 goto out; 02124 02125 if (!_dbus_hash_iter_lookup (table2, 02126 _DBUS_INT_TO_POINTER (i), TRUE, &iter)) 02127 goto out; 02128 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 02129 _dbus_hash_iter_set_value (&iter, value); 02130 02131 _dbus_assert (count_entries (table1) == i + 1); 02132 _dbus_assert (count_entries (table2) == i + 1); 02133 02134 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 02135 goto out; 02136 02137 value = _dbus_hash_iter_get_value (&iter); 02138 _dbus_assert (value != NULL); 02139 _dbus_assert (strcmp (value, "Value!") == 0); 02140 02141 /* Iterate just to be sure it works, though 02142 * it's a stupid thing to do 02143 */ 02144 while (_dbus_hash_iter_next (&iter)) 02145 ; 02146 02147 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 02148 goto out; 02149 02150 value = _dbus_hash_iter_get_value (&iter); 02151 _dbus_assert (value != NULL); 02152 _dbus_assert (strcmp (value, keys[i]) == 0); 02153 02154 /* Iterate just to be sure it works, though 02155 * it's a stupid thing to do 02156 */ 02157 while (_dbus_hash_iter_next (&iter)) 02158 ; 02159 02160 ++i; 02161 } 02162 02163 --i; 02164 while (i >= 0) 02165 { 02166 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 02167 _dbus_assert_not_reached ("hash entry should have existed"); 02168 _dbus_hash_iter_remove_entry (&iter); 02169 02170 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 02171 _dbus_assert_not_reached ("hash entry should have existed"); 02172 _dbus_hash_iter_remove_entry (&iter); 02173 02174 _dbus_assert (count_entries (table1) == i); 02175 _dbus_assert (count_entries (table2) == i); 02176 02177 --i; 02178 } 02179 02180 _dbus_hash_table_unref (table1); 02181 _dbus_hash_table_unref (table2); 02182 02183 ret = TRUE; 02184 02185 out: 02186 for (i = 0; i < N_HASH_KEYS; i++) 02187 dbus_free (keys[i]); 02188 02189 dbus_free (keys); 02190 02191 return ret; 02192 } 02193 02194 #endif /* DBUS_BUILD_TESTS */