D-Bus 1.4.20
|
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 _DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter)); 00226 00227 static DBusHashEntry* find_direct_function (DBusHashTable *table, 00228 void *key, 00229 dbus_bool_t create_if_not_found, 00230 DBusHashEntry ***bucket, 00231 DBusPreallocatedHash *preallocated); 00232 static DBusHashEntry* find_string_function (DBusHashTable *table, 00233 void *key, 00234 dbus_bool_t create_if_not_found, 00235 DBusHashEntry ***bucket, 00236 DBusPreallocatedHash *preallocated); 00237 #ifdef DBUS_BUILD_TESTS 00238 static DBusHashEntry* find_two_strings_function (DBusHashTable *table, 00239 void *key, 00240 dbus_bool_t create_if_not_found, 00241 DBusHashEntry ***bucket, 00242 DBusPreallocatedHash *preallocated); 00243 #endif 00244 static unsigned int string_hash (const char *str); 00245 #ifdef DBUS_BUILD_TESTS 00246 static unsigned int two_strings_hash (const char *str); 00247 #endif 00248 static void rebuild_table (DBusHashTable *table); 00249 static DBusHashEntry* alloc_entry (DBusHashTable *table); 00250 static void remove_entry (DBusHashTable *table, 00251 DBusHashEntry **bucket, 00252 DBusHashEntry *entry); 00253 static void free_entry (DBusHashTable *table, 00254 DBusHashEntry *entry); 00255 static void free_entry_data (DBusHashTable *table, 00256 DBusHashEntry *entry); 00257 00258 00294 DBusHashTable* 00295 _dbus_hash_table_new (DBusHashType type, 00296 DBusFreeFunction key_free_function, 00297 DBusFreeFunction value_free_function) 00298 { 00299 DBusHashTable *table; 00300 DBusMemPool *entry_pool; 00301 00302 table = dbus_new0 (DBusHashTable, 1); 00303 if (table == NULL) 00304 return NULL; 00305 00306 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE); 00307 if (entry_pool == NULL) 00308 { 00309 dbus_free (table); 00310 return NULL; 00311 } 00312 00313 table->refcount = 1; 00314 table->entry_pool = entry_pool; 00315 00316 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets)); 00317 00318 table->buckets = table->static_buckets; 00319 table->n_buckets = DBUS_SMALL_HASH_TABLE; 00320 table->n_entries = 0; 00321 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER; 00322 table->lo_rebuild_size = 0; 00323 table->down_shift = 28; 00324 table->mask = 3; 00325 table->key_type = type; 00326 00327 _dbus_assert (table->mask < table->n_buckets); 00328 00329 switch (table->key_type) 00330 { 00331 case DBUS_HASH_INT: 00332 case DBUS_HASH_POINTER: 00333 case DBUS_HASH_UINTPTR: 00334 table->find_function = find_direct_function; 00335 break; 00336 case DBUS_HASH_STRING: 00337 table->find_function = find_string_function; 00338 break; 00339 case DBUS_HASH_TWO_STRINGS: 00340 #ifdef DBUS_BUILD_TESTS 00341 table->find_function = find_two_strings_function; 00342 #endif 00343 break; 00344 default: 00345 _dbus_assert_not_reached ("Unknown hash table type"); 00346 break; 00347 } 00348 00349 table->free_key_function = key_free_function; 00350 table->free_value_function = value_free_function; 00351 00352 return table; 00353 } 00354 00355 00362 DBusHashTable * 00363 _dbus_hash_table_ref (DBusHashTable *table) 00364 { 00365 table->refcount += 1; 00366 00367 return table; 00368 } 00369 00376 void 00377 _dbus_hash_table_unref (DBusHashTable *table) 00378 { 00379 table->refcount -= 1; 00380 00381 if (table->refcount == 0) 00382 { 00383 #if 0 00384 DBusHashEntry *entry; 00385 DBusHashEntry *next; 00386 int i; 00387 00388 /* Free the entries in the table. */ 00389 for (i = 0; i < table->n_buckets; i++) 00390 { 00391 entry = table->buckets[i]; 00392 while (entry != NULL) 00393 { 00394 next = entry->next; 00395 00396 free_entry (table, entry); 00397 00398 entry = next; 00399 } 00400 } 00401 #else 00402 DBusHashEntry *entry; 00403 int i; 00404 00405 /* Free the entries in the table. */ 00406 for (i = 0; i < table->n_buckets; i++) 00407 { 00408 entry = table->buckets[i]; 00409 while (entry != NULL) 00410 { 00411 free_entry_data (table, entry); 00412 00413 entry = entry->next; 00414 } 00415 } 00416 /* We can do this very quickly with memory pools ;-) */ 00417 _dbus_mem_pool_free (table->entry_pool); 00418 #endif 00419 00420 /* Free the bucket array, if it was dynamically allocated. */ 00421 if (table->buckets != table->static_buckets) 00422 dbus_free (table->buckets); 00423 00424 dbus_free (table); 00425 } 00426 } 00427 00433 void 00434 _dbus_hash_table_remove_all (DBusHashTable *table) 00435 { 00436 DBusHashIter iter; 00437 _dbus_hash_iter_init (table, &iter); 00438 while (_dbus_hash_iter_next (&iter)) 00439 { 00440 _dbus_hash_iter_remove_entry(&iter); 00441 } 00442 } 00443 00444 static DBusHashEntry* 00445 alloc_entry (DBusHashTable *table) 00446 { 00447 DBusHashEntry *entry; 00448 00449 entry = _dbus_mem_pool_alloc (table->entry_pool); 00450 00451 return entry; 00452 } 00453 00454 static void 00455 free_entry_data (DBusHashTable *table, 00456 DBusHashEntry *entry) 00457 { 00458 if (table->free_key_function) 00459 (* table->free_key_function) (entry->key); 00460 if (table->free_value_function) 00461 (* table->free_value_function) (entry->value); 00462 } 00463 00464 static void 00465 free_entry (DBusHashTable *table, 00466 DBusHashEntry *entry) 00467 { 00468 free_entry_data (table, entry); 00469 _dbus_mem_pool_dealloc (table->entry_pool, entry); 00470 } 00471 00472 static void 00473 remove_entry (DBusHashTable *table, 00474 DBusHashEntry **bucket, 00475 DBusHashEntry *entry) 00476 { 00477 _dbus_assert (table != NULL); 00478 _dbus_assert (bucket != NULL); 00479 _dbus_assert (*bucket != NULL); 00480 _dbus_assert (entry != NULL); 00481 00482 if (*bucket == entry) 00483 *bucket = entry->next; 00484 else 00485 { 00486 DBusHashEntry *prev; 00487 prev = *bucket; 00488 00489 while (prev->next != entry) 00490 prev = prev->next; 00491 00492 _dbus_assert (prev != NULL); 00493 00494 prev->next = entry->next; 00495 } 00496 00497 table->n_entries -= 1; 00498 free_entry (table, entry); 00499 } 00500 00532 void 00533 _dbus_hash_iter_init (DBusHashTable *table, 00534 DBusHashIter *iter) 00535 { 00536 DBusRealHashIter *real; 00537 00538 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00539 00540 real = (DBusRealHashIter*) iter; 00541 00542 real->table = table; 00543 real->bucket = NULL; 00544 real->entry = NULL; 00545 real->next_entry = NULL; 00546 real->next_bucket = 0; 00547 real->n_entries_on_init = table->n_entries; 00548 } 00549 00558 dbus_bool_t 00559 _dbus_hash_iter_next (DBusHashIter *iter) 00560 { 00561 DBusRealHashIter *real; 00562 00563 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00564 00565 real = (DBusRealHashIter*) iter; 00566 00567 /* if this assertion failed someone probably added hash entries 00568 * during iteration, which is bad. 00569 */ 00570 _dbus_assert (real->n_entries_on_init >= real->table->n_entries); 00571 00572 /* Remember that real->entry may have been deleted */ 00573 00574 while (real->next_entry == NULL) 00575 { 00576 if (real->next_bucket >= real->table->n_buckets) 00577 { 00578 /* invalidate iter and return false */ 00579 real->entry = NULL; 00580 real->table = NULL; 00581 real->bucket = NULL; 00582 return FALSE; 00583 } 00584 00585 real->bucket = &(real->table->buckets[real->next_bucket]); 00586 real->next_entry = *(real->bucket); 00587 real->next_bucket += 1; 00588 } 00589 00590 _dbus_assert (real->next_entry != NULL); 00591 _dbus_assert (real->bucket != NULL); 00592 00593 real->entry = real->next_entry; 00594 real->next_entry = real->entry->next; 00595 00596 return TRUE; 00597 } 00598 00607 void 00608 _dbus_hash_iter_remove_entry (DBusHashIter *iter) 00609 { 00610 DBusRealHashIter *real; 00611 00612 real = (DBusRealHashIter*) iter; 00613 00614 _dbus_assert (real->table != NULL); 00615 _dbus_assert (real->entry != NULL); 00616 _dbus_assert (real->bucket != NULL); 00617 00618 remove_entry (real->table, real->bucket, real->entry); 00619 00620 real->entry = NULL; /* make it crash if you try to use this entry */ 00621 } 00622 00628 void* 00629 _dbus_hash_iter_get_value (DBusHashIter *iter) 00630 { 00631 DBusRealHashIter *real; 00632 00633 real = (DBusRealHashIter*) iter; 00634 00635 _dbus_assert (real->table != NULL); 00636 _dbus_assert (real->entry != NULL); 00637 00638 return real->entry->value; 00639 } 00640 00651 void 00652 _dbus_hash_iter_set_value (DBusHashIter *iter, 00653 void *value) 00654 { 00655 DBusRealHashIter *real; 00656 00657 real = (DBusRealHashIter*) iter; 00658 00659 _dbus_assert (real->table != NULL); 00660 _dbus_assert (real->entry != NULL); 00661 00662 if (real->table->free_value_function && value != real->entry->value) 00663 (* real->table->free_value_function) (real->entry->value); 00664 00665 real->entry->value = value; 00666 } 00667 00674 int 00675 _dbus_hash_iter_get_int_key (DBusHashIter *iter) 00676 { 00677 DBusRealHashIter *real; 00678 00679 real = (DBusRealHashIter*) iter; 00680 00681 _dbus_assert (real->table != NULL); 00682 _dbus_assert (real->entry != NULL); 00683 00684 return _DBUS_POINTER_TO_INT (real->entry->key); 00685 } 00686 00693 uintptr_t 00694 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter) 00695 { 00696 DBusRealHashIter *real; 00697 00698 real = (DBusRealHashIter*) iter; 00699 00700 _dbus_assert (real->table != NULL); 00701 _dbus_assert (real->entry != NULL); 00702 00703 return (uintptr_t) real->entry->key; 00704 } 00705 00711 const char* 00712 _dbus_hash_iter_get_string_key (DBusHashIter *iter) 00713 { 00714 DBusRealHashIter *real; 00715 00716 real = (DBusRealHashIter*) iter; 00717 00718 _dbus_assert (real->table != NULL); 00719 _dbus_assert (real->entry != NULL); 00720 00721 return real->entry->key; 00722 } 00723 00724 #ifdef DBUS_BUILD_TESTS 00725 00730 const char* 00731 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter) 00732 { 00733 DBusRealHashIter *real; 00734 00735 real = (DBusRealHashIter*) iter; 00736 00737 _dbus_assert (real->table != NULL); 00738 _dbus_assert (real->entry != NULL); 00739 00740 return real->entry->key; 00741 } 00742 #endif /* DBUS_BUILD_TESTS */ 00743 00775 dbus_bool_t 00776 _dbus_hash_iter_lookup (DBusHashTable *table, 00777 void *key, 00778 dbus_bool_t create_if_not_found, 00779 DBusHashIter *iter) 00780 { 00781 DBusRealHashIter *real; 00782 DBusHashEntry *entry; 00783 DBusHashEntry **bucket; 00784 00785 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00786 00787 real = (DBusRealHashIter*) iter; 00788 00789 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL); 00790 00791 if (entry == NULL) 00792 return FALSE; 00793 00794 real->table = table; 00795 real->bucket = bucket; 00796 real->entry = entry; 00797 real->next_entry = entry->next; 00798 real->next_bucket = (bucket - table->buckets) + 1; 00799 real->n_entries_on_init = table->n_entries; 00800 00801 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket); 00802 00803 return TRUE; 00804 } 00805 00806 static void 00807 add_allocated_entry (DBusHashTable *table, 00808 DBusHashEntry *entry, 00809 unsigned int idx, 00810 void *key, 00811 DBusHashEntry ***bucket) 00812 { 00813 DBusHashEntry **b; 00814 00815 entry->key = key; 00816 00817 b = &(table->buckets[idx]); 00818 entry->next = *b; 00819 *b = entry; 00820 00821 if (bucket) 00822 *bucket = b; 00823 00824 table->n_entries += 1; 00825 00826 /* note we ONLY rebuild when ADDING - because you can iterate over a 00827 * table and remove entries safely. 00828 */ 00829 if (table->n_entries >= table->hi_rebuild_size || 00830 table->n_entries < table->lo_rebuild_size) 00831 rebuild_table (table); 00832 } 00833 00834 static DBusHashEntry* 00835 add_entry (DBusHashTable *table, 00836 unsigned int idx, 00837 void *key, 00838 DBusHashEntry ***bucket, 00839 DBusPreallocatedHash *preallocated) 00840 { 00841 DBusHashEntry *entry; 00842 00843 if (preallocated == NULL) 00844 { 00845 entry = alloc_entry (table); 00846 if (entry == NULL) 00847 { 00848 if (bucket) 00849 *bucket = NULL; 00850 return NULL; 00851 } 00852 } 00853 else 00854 { 00855 entry = (DBusHashEntry*) preallocated; 00856 } 00857 00858 add_allocated_entry (table, entry, idx, key, bucket); 00859 00860 return entry; 00861 } 00862 00863 /* This is g_str_hash from GLib which was 00864 * extensively discussed/tested/profiled 00865 */ 00866 static unsigned int 00867 string_hash (const char *str) 00868 { 00869 const char *p = str; 00870 unsigned int h = *p; 00871 00872 if (h) 00873 for (p += 1; *p != '\0'; p++) 00874 h = (h << 5) - h + *p; 00875 00876 return h; 00877 } 00878 00879 #ifdef DBUS_BUILD_TESTS 00880 /* This hashes a memory block with two nul-terminated strings 00881 * in it, used in dbus-object-registry.c at the moment. 00882 */ 00883 static unsigned int 00884 two_strings_hash (const char *str) 00885 { 00886 const char *p = str; 00887 unsigned int h = *p; 00888 00889 if (h) 00890 for (p += 1; *p != '\0'; p++) 00891 h = (h << 5) - h + *p; 00892 00893 for (p += 1; *p != '\0'; p++) 00894 h = (h << 5) - h + *p; 00895 00896 return h; 00897 } 00898 #endif /* DBUS_BUILD_TESTS */ 00899 00901 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b); 00902 00903 static DBusHashEntry* 00904 find_generic_function (DBusHashTable *table, 00905 void *key, 00906 unsigned int idx, 00907 KeyCompareFunc compare_func, 00908 dbus_bool_t create_if_not_found, 00909 DBusHashEntry ***bucket, 00910 DBusPreallocatedHash *preallocated) 00911 { 00912 DBusHashEntry *entry; 00913 00914 if (bucket) 00915 *bucket = NULL; 00916 00917 /* Search all of the entries in this bucket. */ 00918 entry = table->buckets[idx]; 00919 while (entry != NULL) 00920 { 00921 if ((compare_func == NULL && key == entry->key) || 00922 (compare_func != NULL && (* compare_func) (key, entry->key) == 0)) 00923 { 00924 if (bucket) 00925 *bucket = &(table->buckets[idx]); 00926 00927 if (preallocated) 00928 _dbus_hash_table_free_preallocated_entry (table, preallocated); 00929 00930 return entry; 00931 } 00932 00933 entry = entry->next; 00934 } 00935 00936 if (create_if_not_found) 00937 entry = add_entry (table, idx, key, bucket, preallocated); 00938 else if (preallocated) 00939 _dbus_hash_table_free_preallocated_entry (table, preallocated); 00940 00941 return entry; 00942 } 00943 00944 static DBusHashEntry* 00945 find_string_function (DBusHashTable *table, 00946 void *key, 00947 dbus_bool_t create_if_not_found, 00948 DBusHashEntry ***bucket, 00949 DBusPreallocatedHash *preallocated) 00950 { 00951 unsigned int idx; 00952 00953 idx = string_hash (key) & table->mask; 00954 00955 return find_generic_function (table, key, idx, 00956 (KeyCompareFunc) strcmp, create_if_not_found, bucket, 00957 preallocated); 00958 } 00959 00960 #ifdef DBUS_BUILD_TESTS 00961 static int 00962 two_strings_cmp (const char *a, 00963 const char *b) 00964 { 00965 size_t len_a; 00966 size_t len_b; 00967 int res; 00968 00969 res = strcmp (a, b); 00970 if (res != 0) 00971 return res; 00972 00973 len_a = strlen (a); 00974 len_b = strlen (b); 00975 00976 return strcmp (a + len_a + 1, b + len_b + 1); 00977 } 00978 #endif 00979 00980 #ifdef DBUS_BUILD_TESTS 00981 static DBusHashEntry* 00982 find_two_strings_function (DBusHashTable *table, 00983 void *key, 00984 dbus_bool_t create_if_not_found, 00985 DBusHashEntry ***bucket, 00986 DBusPreallocatedHash *preallocated) 00987 { 00988 unsigned int idx; 00989 00990 idx = two_strings_hash (key) & table->mask; 00991 00992 return find_generic_function (table, key, idx, 00993 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket, 00994 preallocated); 00995 } 00996 #endif /* DBUS_BUILD_TESTS */ 00997 00998 static DBusHashEntry* 00999 find_direct_function (DBusHashTable *table, 01000 void *key, 01001 dbus_bool_t create_if_not_found, 01002 DBusHashEntry ***bucket, 01003 DBusPreallocatedHash *preallocated) 01004 { 01005 unsigned int idx; 01006 01007 idx = RANDOM_INDEX (table, key) & table->mask; 01008 01009 01010 return find_generic_function (table, key, idx, 01011 NULL, create_if_not_found, bucket, 01012 preallocated); 01013 } 01014 01015 static void 01016 rebuild_table (DBusHashTable *table) 01017 { 01018 int old_size; 01019 int new_buckets; 01020 DBusHashEntry **old_buckets; 01021 DBusHashEntry **old_chain; 01022 DBusHashEntry *entry; 01023 dbus_bool_t growing; 01024 01025 /* 01026 * Allocate and initialize the new bucket array, and set up 01027 * hashing constants for new array size. 01028 */ 01029 01030 growing = table->n_entries >= table->hi_rebuild_size; 01031 01032 old_size = table->n_buckets; 01033 old_buckets = table->buckets; 01034 01035 if (growing) 01036 { 01037 /* overflow paranoia */ 01038 if (table->n_buckets < _DBUS_INT_MAX / 4 && 01039 table->down_shift >= 0) 01040 new_buckets = table->n_buckets * 4; 01041 else 01042 return; /* can't grow anymore */ 01043 } 01044 else 01045 { 01046 new_buckets = table->n_buckets / 4; 01047 if (new_buckets < DBUS_SMALL_HASH_TABLE) 01048 return; /* don't bother shrinking this far */ 01049 } 01050 01051 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets); 01052 if (table->buckets == NULL) 01053 { 01054 /* out of memory, yay - just don't reallocate, the table will 01055 * still work, albeit more slowly. 01056 */ 01057 table->buckets = old_buckets; 01058 return; 01059 } 01060 01061 table->n_buckets = new_buckets; 01062 01063 if (growing) 01064 { 01065 table->lo_rebuild_size = table->hi_rebuild_size; 01066 table->hi_rebuild_size *= 4; 01067 01068 table->down_shift -= 2; /* keep 2 more high bits */ 01069 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */ 01070 } 01071 else 01072 { 01073 table->hi_rebuild_size = table->lo_rebuild_size; 01074 table->lo_rebuild_size /= 4; 01075 01076 table->down_shift += 2; /* keep 2 fewer high bits */ 01077 table->mask = table->mask >> 2; /* keep 2 fewer high bits */ 01078 } 01079 01080 #if 0 01081 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", 01082 growing ? "GROW" : "SHRINK", 01083 table->lo_rebuild_size, 01084 table->hi_rebuild_size, 01085 table->down_shift, 01086 table->mask); 01087 #endif 01088 01089 _dbus_assert (table->lo_rebuild_size >= 0); 01090 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size); 01091 _dbus_assert (table->mask != 0); 01092 /* the mask is essentially the max index */ 01093 _dbus_assert (table->mask < table->n_buckets); 01094 01095 /* 01096 * Rehash all of the existing entries into the new bucket array. 01097 */ 01098 01099 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++) 01100 { 01101 for (entry = *old_chain; entry != NULL; entry = *old_chain) 01102 { 01103 unsigned int idx; 01104 DBusHashEntry **bucket; 01105 01106 *old_chain = entry->next; 01107 switch (table->key_type) 01108 { 01109 case DBUS_HASH_STRING: 01110 idx = string_hash (entry->key) & table->mask; 01111 break; 01112 case DBUS_HASH_TWO_STRINGS: 01113 #ifdef DBUS_BUILD_TESTS 01114 idx = two_strings_hash (entry->key) & table->mask; 01115 #else 01116 idx = 0; 01117 _dbus_assert_not_reached ("two-strings is not enabled"); 01118 #endif 01119 break; 01120 case DBUS_HASH_INT: 01121 case DBUS_HASH_UINTPTR: 01122 case DBUS_HASH_POINTER: 01123 idx = RANDOM_INDEX (table, entry->key); 01124 break; 01125 default: 01126 idx = 0; 01127 _dbus_assert_not_reached ("Unknown hash table type"); 01128 break; 01129 } 01130 01131 bucket = &(table->buckets[idx]); 01132 entry->next = *bucket; 01133 *bucket = entry; 01134 } 01135 } 01136 01137 /* Free the old bucket array, if it was dynamically allocated. */ 01138 01139 if (old_buckets != table->static_buckets) 01140 dbus_free (old_buckets); 01141 } 01142 01152 void* 01153 _dbus_hash_table_lookup_string (DBusHashTable *table, 01154 const char *key) 01155 { 01156 DBusHashEntry *entry; 01157 01158 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01159 01160 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 01161 01162 if (entry) 01163 return entry->value; 01164 else 01165 return NULL; 01166 } 01167 01168 #ifdef DBUS_BUILD_TESTS 01169 01178 void* 01179 _dbus_hash_table_lookup_two_strings (DBusHashTable *table, 01180 const char *key) 01181 { 01182 DBusHashEntry *entry; 01183 01184 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01185 01186 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 01187 01188 if (entry) 01189 return entry->value; 01190 else 01191 return NULL; 01192 } 01193 #endif /* DBUS_BUILD_TESTS */ 01194 01204 void* 01205 _dbus_hash_table_lookup_int (DBusHashTable *table, 01206 int key) 01207 { 01208 DBusHashEntry *entry; 01209 01210 _dbus_assert (table->key_type == DBUS_HASH_INT); 01211 01212 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL); 01213 01214 if (entry) 01215 return entry->value; 01216 else 01217 return NULL; 01218 } 01219 01220 #ifdef DBUS_BUILD_TESTS 01221 /* disabled since it's only used for testing */ 01231 void* 01232 _dbus_hash_table_lookup_pointer (DBusHashTable *table, 01233 void *key) 01234 { 01235 DBusHashEntry *entry; 01236 01237 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01238 01239 entry = (* table->find_function) (table, key, FALSE, NULL, NULL); 01240 01241 if (entry) 01242 return entry->value; 01243 else 01244 return NULL; 01245 } 01246 #endif /* DBUS_BUILD_TESTS */ 01247 01257 void* 01258 _dbus_hash_table_lookup_uintptr (DBusHashTable *table, 01259 uintptr_t key) 01260 { 01261 DBusHashEntry *entry; 01262 01263 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01264 01265 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL); 01266 01267 if (entry) 01268 return entry->value; 01269 else 01270 return NULL; 01271 } 01272 01281 dbus_bool_t 01282 _dbus_hash_table_remove_string (DBusHashTable *table, 01283 const char *key) 01284 { 01285 DBusHashEntry *entry; 01286 DBusHashEntry **bucket; 01287 01288 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01289 01290 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 01291 01292 if (entry) 01293 { 01294 remove_entry (table, bucket, entry); 01295 return TRUE; 01296 } 01297 else 01298 return FALSE; 01299 } 01300 01301 #ifdef DBUS_BUILD_TESTS 01302 01310 dbus_bool_t 01311 _dbus_hash_table_remove_two_strings (DBusHashTable *table, 01312 const char *key) 01313 { 01314 DBusHashEntry *entry; 01315 DBusHashEntry **bucket; 01316 01317 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01318 01319 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 01320 01321 if (entry) 01322 { 01323 remove_entry (table, bucket, entry); 01324 return TRUE; 01325 } 01326 else 01327 return FALSE; 01328 } 01329 #endif /* DBUS_BUILD_TESTS */ 01330 01339 dbus_bool_t 01340 _dbus_hash_table_remove_int (DBusHashTable *table, 01341 int key) 01342 { 01343 DBusHashEntry *entry; 01344 DBusHashEntry **bucket; 01345 01346 _dbus_assert (table->key_type == DBUS_HASH_INT); 01347 01348 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL); 01349 01350 if (entry) 01351 { 01352 remove_entry (table, bucket, entry); 01353 return TRUE; 01354 } 01355 else 01356 return FALSE; 01357 } 01358 01359 #ifdef DBUS_BUILD_TESTS 01360 /* disabled since it's only used for testing */ 01369 dbus_bool_t 01370 _dbus_hash_table_remove_pointer (DBusHashTable *table, 01371 void *key) 01372 { 01373 DBusHashEntry *entry; 01374 DBusHashEntry **bucket; 01375 01376 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01377 01378 entry = (* table->find_function) (table, key, FALSE, &bucket, NULL); 01379 01380 if (entry) 01381 { 01382 remove_entry (table, bucket, entry); 01383 return TRUE; 01384 } 01385 else 01386 return FALSE; 01387 } 01388 #endif /* DBUS_BUILD_TESTS */ 01389 01398 dbus_bool_t 01399 _dbus_hash_table_remove_uintptr (DBusHashTable *table, 01400 uintptr_t key) 01401 { 01402 DBusHashEntry *entry; 01403 DBusHashEntry **bucket; 01404 01405 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01406 01407 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL); 01408 01409 if (entry) 01410 { 01411 remove_entry (table, bucket, entry); 01412 return TRUE; 01413 } 01414 else 01415 return FALSE; 01416 } 01417 01433 dbus_bool_t 01434 _dbus_hash_table_insert_string (DBusHashTable *table, 01435 char *key, 01436 void *value) 01437 { 01438 DBusPreallocatedHash *preallocated; 01439 01440 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01441 01442 preallocated = _dbus_hash_table_preallocate_entry (table); 01443 if (preallocated == NULL) 01444 return FALSE; 01445 01446 _dbus_hash_table_insert_string_preallocated (table, preallocated, 01447 key, value); 01448 01449 return TRUE; 01450 } 01451 01452 #ifdef DBUS_BUILD_TESTS 01453 01468 dbus_bool_t 01469 _dbus_hash_table_insert_two_strings (DBusHashTable *table, 01470 char *key, 01471 void *value) 01472 { 01473 DBusHashEntry *entry; 01474 01475 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01476 01477 entry = (* table->find_function) (table, key, TRUE, NULL, NULL); 01478 01479 if (entry == NULL) 01480 return FALSE; /* no memory */ 01481 01482 if (table->free_key_function && entry->key != key) 01483 (* table->free_key_function) (entry->key); 01484 01485 if (table->free_value_function && entry->value != value) 01486 (* table->free_value_function) (entry->value); 01487 01488 entry->key = key; 01489 entry->value = value; 01490 01491 return TRUE; 01492 } 01493 #endif /* DBUS_BUILD_TESTS */ 01494 01510 dbus_bool_t 01511 _dbus_hash_table_insert_int (DBusHashTable *table, 01512 int key, 01513 void *value) 01514 { 01515 DBusHashEntry *entry; 01516 01517 _dbus_assert (table->key_type == DBUS_HASH_INT); 01518 01519 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL); 01520 01521 if (entry == NULL) 01522 return FALSE; /* no memory */ 01523 01524 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key)) 01525 (* table->free_key_function) (entry->key); 01526 01527 if (table->free_value_function && entry->value != value) 01528 (* table->free_value_function) (entry->value); 01529 01530 entry->key = _DBUS_INT_TO_POINTER (key); 01531 entry->value = value; 01532 01533 return TRUE; 01534 } 01535 01536 #ifdef DBUS_BUILD_TESTS 01537 /* disabled since it's only used for testing */ 01553 dbus_bool_t 01554 _dbus_hash_table_insert_pointer (DBusHashTable *table, 01555 void *key, 01556 void *value) 01557 { 01558 DBusHashEntry *entry; 01559 01560 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01561 01562 entry = (* table->find_function) (table, key, TRUE, NULL, NULL); 01563 01564 if (entry == NULL) 01565 return FALSE; /* no memory */ 01566 01567 if (table->free_key_function && entry->key != key) 01568 (* table->free_key_function) (entry->key); 01569 01570 if (table->free_value_function && entry->value != value) 01571 (* table->free_value_function) (entry->value); 01572 01573 entry->key = key; 01574 entry->value = value; 01575 01576 return TRUE; 01577 } 01578 #endif /* DBUS_BUILD_TESTS */ 01579 01595 dbus_bool_t 01596 _dbus_hash_table_insert_uintptr (DBusHashTable *table, 01597 uintptr_t key, 01598 void *value) 01599 { 01600 DBusHashEntry *entry; 01601 01602 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01603 01604 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL); 01605 01606 if (entry == NULL) 01607 return FALSE; /* no memory */ 01608 01609 if (table->free_key_function && entry->key != (void*) key) 01610 (* table->free_key_function) (entry->key); 01611 01612 if (table->free_value_function && entry->value != value) 01613 (* table->free_value_function) (entry->value); 01614 01615 entry->key = (void*) key; 01616 entry->value = value; 01617 01618 return TRUE; 01619 } 01620 01628 DBusPreallocatedHash* 01629 _dbus_hash_table_preallocate_entry (DBusHashTable *table) 01630 { 01631 DBusHashEntry *entry; 01632 01633 entry = alloc_entry (table); 01634 01635 return (DBusPreallocatedHash*) entry; 01636 } 01637 01645 void 01646 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table, 01647 DBusPreallocatedHash *preallocated) 01648 { 01649 DBusHashEntry *entry; 01650 01651 _dbus_assert (preallocated != NULL); 01652 01653 entry = (DBusHashEntry*) preallocated; 01654 01655 /* Don't use free_entry(), since this entry has no key/data */ 01656 _dbus_mem_pool_dealloc (table->entry_pool, entry); 01657 } 01658 01672 void 01673 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table, 01674 DBusPreallocatedHash *preallocated, 01675 char *key, 01676 void *value) 01677 { 01678 DBusHashEntry *entry; 01679 01680 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01681 _dbus_assert (preallocated != NULL); 01682 01683 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated); 01684 01685 _dbus_assert (entry != NULL); 01686 01687 if (table->free_key_function && entry->key != key) 01688 (* table->free_key_function) (entry->key); 01689 01690 if (table->free_value_function && entry->value != value) 01691 (* table->free_value_function) (entry->value); 01692 01693 entry->key = key; 01694 entry->value = value; 01695 } 01696 01703 int 01704 _dbus_hash_table_get_n_entries (DBusHashTable *table) 01705 { 01706 return table->n_entries; 01707 } 01708 01711 #ifdef DBUS_BUILD_TESTS 01712 #include "dbus-test.h" 01713 #include <stdio.h> 01714 01715 /* If you're wondering why the hash table test takes 01716 * forever to run, it's because we call this function 01717 * in inner loops thus making things quadratic. 01718 */ 01719 static int 01720 count_entries (DBusHashTable *table) 01721 { 01722 DBusHashIter iter; 01723 int count; 01724 01725 count = 0; 01726 _dbus_hash_iter_init (table, &iter); 01727 while (_dbus_hash_iter_next (&iter)) 01728 ++count; 01729 01730 _dbus_assert (count == _dbus_hash_table_get_n_entries (table)); 01731 01732 return count; 01733 } 01734 01735 /* Copy the foo\0bar\0 double string thing */ 01736 static char* 01737 _dbus_strdup2 (const char *str) 01738 { 01739 size_t len; 01740 char *copy; 01741 01742 if (str == NULL) 01743 return NULL; 01744 01745 len = strlen (str); 01746 len += strlen ((str + len + 1)); 01747 01748 copy = dbus_malloc (len + 2); 01749 if (copy == NULL) 01750 return NULL; 01751 01752 memcpy (copy, str, len + 2); 01753 01754 return copy; 01755 } 01756 01762 dbus_bool_t 01763 _dbus_hash_test (void) 01764 { 01765 int i; 01766 DBusHashTable *table1; 01767 DBusHashTable *table2; 01768 DBusHashTable *table3; 01769 DBusHashTable *table4; 01770 DBusHashIter iter; 01771 #define N_HASH_KEYS 5000 01772 char **keys; 01773 dbus_bool_t ret = FALSE; 01774 01775 keys = dbus_new (char *, N_HASH_KEYS); 01776 if (keys == NULL) 01777 _dbus_assert_not_reached ("no memory"); 01778 01779 for (i = 0; i < N_HASH_KEYS; i++) 01780 { 01781 keys[i] = dbus_malloc (128); 01782 01783 if (keys[i] == NULL) 01784 _dbus_assert_not_reached ("no memory"); 01785 } 01786 01787 printf ("Computing test hash keys...\n"); 01788 i = 0; 01789 while (i < N_HASH_KEYS) 01790 { 01791 int len; 01792 01793 /* all the hash keys are TWO_STRINGS, but 01794 * then we can also use those as regular strings. 01795 */ 01796 01797 len = sprintf (keys[i], "Hash key %d", i); 01798 sprintf (keys[i] + len + 1, "Two string %d", i); 01799 _dbus_assert (*(keys[i] + len) == '\0'); 01800 _dbus_assert (*(keys[i] + len + 1) != '\0'); 01801 ++i; 01802 } 01803 printf ("... done.\n"); 01804 01805 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01806 dbus_free, dbus_free); 01807 if (table1 == NULL) 01808 goto out; 01809 01810 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01811 NULL, dbus_free); 01812 if (table2 == NULL) 01813 goto out; 01814 01815 table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR, 01816 NULL, dbus_free); 01817 if (table3 == NULL) 01818 goto out; 01819 01820 table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS, 01821 dbus_free, dbus_free); 01822 if (table4 == NULL) 01823 goto out; 01824 01825 01826 /* Insert and remove a bunch of stuff, counting the table in between 01827 * to be sure it's not broken and that iteration works 01828 */ 01829 i = 0; 01830 while (i < 3000) 01831 { 01832 void *value; 01833 char *key; 01834 01835 key = _dbus_strdup (keys[i]); 01836 if (key == NULL) 01837 goto out; 01838 value = _dbus_strdup ("Value!"); 01839 if (value == NULL) 01840 goto out; 01841 01842 if (!_dbus_hash_table_insert_string (table1, 01843 key, value)) 01844 goto out; 01845 01846 value = _dbus_strdup (keys[i]); 01847 if (value == NULL) 01848 goto out; 01849 01850 if (!_dbus_hash_table_insert_int (table2, 01851 i, value)) 01852 goto out; 01853 01854 value = _dbus_strdup (keys[i]); 01855 if (value == NULL) 01856 goto out; 01857 01858 if (!_dbus_hash_table_insert_uintptr (table3, 01859 i, value)) 01860 goto out; 01861 01862 key = _dbus_strdup2 (keys[i]); 01863 if (key == NULL) 01864 goto out; 01865 value = _dbus_strdup ("Value!"); 01866 if (value == NULL) 01867 goto out; 01868 01869 if (!_dbus_hash_table_insert_two_strings (table4, 01870 key, value)) 01871 goto out; 01872 01873 _dbus_assert (count_entries (table1) == i + 1); 01874 _dbus_assert (count_entries (table2) == i + 1); 01875 _dbus_assert (count_entries (table3) == i + 1); 01876 _dbus_assert (count_entries (table4) == i + 1); 01877 01878 value = _dbus_hash_table_lookup_string (table1, keys[i]); 01879 _dbus_assert (value != NULL); 01880 _dbus_assert (strcmp (value, "Value!") == 0); 01881 01882 value = _dbus_hash_table_lookup_int (table2, i); 01883 _dbus_assert (value != NULL); 01884 _dbus_assert (strcmp (value, keys[i]) == 0); 01885 01886 value = _dbus_hash_table_lookup_uintptr (table3, i); 01887 _dbus_assert (value != NULL); 01888 _dbus_assert (strcmp (value, keys[i]) == 0); 01889 01890 value = _dbus_hash_table_lookup_two_strings (table4, keys[i]); 01891 _dbus_assert (value != NULL); 01892 _dbus_assert (strcmp (value, "Value!") == 0); 01893 01894 ++i; 01895 } 01896 01897 --i; 01898 while (i >= 0) 01899 { 01900 _dbus_hash_table_remove_string (table1, 01901 keys[i]); 01902 01903 _dbus_hash_table_remove_int (table2, i); 01904 01905 _dbus_hash_table_remove_uintptr (table3, i); 01906 01907 _dbus_hash_table_remove_two_strings (table4, 01908 keys[i]); 01909 01910 _dbus_assert (count_entries (table1) == i); 01911 _dbus_assert (count_entries (table2) == i); 01912 _dbus_assert (count_entries (table3) == i); 01913 _dbus_assert (count_entries (table4) == i); 01914 01915 --i; 01916 } 01917 01918 _dbus_hash_table_ref (table1); 01919 _dbus_hash_table_ref (table2); 01920 _dbus_hash_table_ref (table3); 01921 _dbus_hash_table_ref (table4); 01922 _dbus_hash_table_unref (table1); 01923 _dbus_hash_table_unref (table2); 01924 _dbus_hash_table_unref (table3); 01925 _dbus_hash_table_unref (table4); 01926 _dbus_hash_table_unref (table1); 01927 _dbus_hash_table_unref (table2); 01928 _dbus_hash_table_unref (table3); 01929 _dbus_hash_table_unref (table4); 01930 table3 = NULL; 01931 01932 /* Insert a bunch of stuff then check 01933 * that iteration works correctly (finds the right 01934 * values, iter_set_value works, etc.) 01935 */ 01936 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01937 dbus_free, dbus_free); 01938 if (table1 == NULL) 01939 goto out; 01940 01941 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01942 NULL, dbus_free); 01943 if (table2 == NULL) 01944 goto out; 01945 01946 i = 0; 01947 while (i < 5000) 01948 { 01949 char *key; 01950 void *value; 01951 01952 key = _dbus_strdup (keys[i]); 01953 if (key == NULL) 01954 goto out; 01955 value = _dbus_strdup ("Value!"); 01956 if (value == NULL) 01957 goto out; 01958 01959 if (!_dbus_hash_table_insert_string (table1, 01960 key, value)) 01961 goto out; 01962 01963 value = _dbus_strdup (keys[i]); 01964 if (value == NULL) 01965 goto out; 01966 01967 if (!_dbus_hash_table_insert_int (table2, 01968 i, value)) 01969 goto out; 01970 01971 _dbus_assert (count_entries (table1) == i + 1); 01972 _dbus_assert (count_entries (table2) == i + 1); 01973 01974 ++i; 01975 } 01976 01977 _dbus_hash_iter_init (table1, &iter); 01978 while (_dbus_hash_iter_next (&iter)) 01979 { 01980 const char *key; 01981 void *value; 01982 01983 key = _dbus_hash_iter_get_string_key (&iter); 01984 value = _dbus_hash_iter_get_value (&iter); 01985 01986 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 01987 01988 value = _dbus_strdup ("Different value!"); 01989 if (value == NULL) 01990 goto out; 01991 01992 _dbus_hash_iter_set_value (&iter, value); 01993 01994 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 01995 } 01996 01997 _dbus_hash_iter_init (table1, &iter); 01998 while (_dbus_hash_iter_next (&iter)) 01999 { 02000 _dbus_hash_iter_remove_entry (&iter); 02001 _dbus_assert (count_entries (table1) == i - 1); 02002 --i; 02003 } 02004 02005 _dbus_hash_iter_init (table2, &iter); 02006 while (_dbus_hash_iter_next (&iter)) 02007 { 02008 int key; 02009 void *value; 02010 02011 key = _dbus_hash_iter_get_int_key (&iter); 02012 value = _dbus_hash_iter_get_value (&iter); 02013 02014 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 02015 02016 value = _dbus_strdup ("Different value!"); 02017 if (value == NULL) 02018 goto out; 02019 02020 _dbus_hash_iter_set_value (&iter, value); 02021 02022 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 02023 } 02024 02025 i = count_entries (table2); 02026 _dbus_hash_iter_init (table2, &iter); 02027 while (_dbus_hash_iter_next (&iter)) 02028 { 02029 _dbus_hash_iter_remove_entry (&iter); 02030 _dbus_assert (count_entries (table2) + 1 == i); 02031 --i; 02032 } 02033 02034 /* add/remove interleaved, to check that we grow/shrink the table 02035 * appropriately 02036 */ 02037 i = 0; 02038 while (i < 1000) 02039 { 02040 char *key; 02041 void *value; 02042 02043 key = _dbus_strdup (keys[i]); 02044 if (key == NULL) 02045 goto out; 02046 02047 value = _dbus_strdup ("Value!"); 02048 if (value == NULL) 02049 goto out; 02050 02051 if (!_dbus_hash_table_insert_string (table1, 02052 key, value)) 02053 goto out; 02054 02055 ++i; 02056 } 02057 02058 --i; 02059 while (i >= 0) 02060 { 02061 char *key; 02062 void *value; 02063 02064 key = _dbus_strdup (keys[i]); 02065 if (key == NULL) 02066 goto out; 02067 value = _dbus_strdup ("Value!"); 02068 if (value == NULL) 02069 goto out; 02070 02071 if (!_dbus_hash_table_remove_string (table1, keys[i])) 02072 goto out; 02073 02074 if (!_dbus_hash_table_insert_string (table1, 02075 key, value)) 02076 goto out; 02077 02078 if (!_dbus_hash_table_remove_string (table1, keys[i])) 02079 goto out; 02080 02081 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i); 02082 02083 --i; 02084 } 02085 02086 /* nuke these tables */ 02087 _dbus_hash_table_unref (table1); 02088 _dbus_hash_table_unref (table2); 02089 02090 02091 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to 02092 * be sure that interface works. 02093 */ 02094 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 02095 dbus_free, dbus_free); 02096 if (table1 == NULL) 02097 goto out; 02098 02099 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 02100 NULL, dbus_free); 02101 if (table2 == NULL) 02102 goto out; 02103 02104 i = 0; 02105 while (i < 3000) 02106 { 02107 void *value; 02108 char *key; 02109 02110 key = _dbus_strdup (keys[i]); 02111 if (key == NULL) 02112 goto out; 02113 value = _dbus_strdup ("Value!"); 02114 if (value == NULL) 02115 goto out; 02116 02117 if (!_dbus_hash_iter_lookup (table1, 02118 key, TRUE, &iter)) 02119 goto out; 02120 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 02121 _dbus_hash_iter_set_value (&iter, value); 02122 02123 value = _dbus_strdup (keys[i]); 02124 if (value == NULL) 02125 goto out; 02126 02127 if (!_dbus_hash_iter_lookup (table2, 02128 _DBUS_INT_TO_POINTER (i), TRUE, &iter)) 02129 goto out; 02130 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 02131 _dbus_hash_iter_set_value (&iter, value); 02132 02133 _dbus_assert (count_entries (table1) == i + 1); 02134 _dbus_assert (count_entries (table2) == i + 1); 02135 02136 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 02137 goto out; 02138 02139 value = _dbus_hash_iter_get_value (&iter); 02140 _dbus_assert (value != NULL); 02141 _dbus_assert (strcmp (value, "Value!") == 0); 02142 02143 /* Iterate just to be sure it works, though 02144 * it's a stupid thing to do 02145 */ 02146 while (_dbus_hash_iter_next (&iter)) 02147 ; 02148 02149 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 02150 goto out; 02151 02152 value = _dbus_hash_iter_get_value (&iter); 02153 _dbus_assert (value != NULL); 02154 _dbus_assert (strcmp (value, keys[i]) == 0); 02155 02156 /* Iterate just to be sure it works, though 02157 * it's a stupid thing to do 02158 */ 02159 while (_dbus_hash_iter_next (&iter)) 02160 ; 02161 02162 ++i; 02163 } 02164 02165 --i; 02166 while (i >= 0) 02167 { 02168 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 02169 _dbus_assert_not_reached ("hash entry should have existed"); 02170 _dbus_hash_iter_remove_entry (&iter); 02171 02172 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 02173 _dbus_assert_not_reached ("hash entry should have existed"); 02174 _dbus_hash_iter_remove_entry (&iter); 02175 02176 _dbus_assert (count_entries (table1) == i); 02177 _dbus_assert (count_entries (table2) == i); 02178 02179 --i; 02180 } 02181 02182 _dbus_hash_table_unref (table1); 02183 _dbus_hash_table_unref (table2); 02184 02185 ret = TRUE; 02186 02187 out: 02188 for (i = 0; i < N_HASH_KEYS; i++) 02189 dbus_free (keys[i]); 02190 02191 dbus_free (keys); 02192 02193 return ret; 02194 } 02195 02196 #endif /* DBUS_BUILD_TESTS */