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