Main Page | Modules | Data Structures | File List | Data Fields | Related Pages

dbus-hash.c

00001 /* -*- mode: C; c-file-style: "gnu" -*- */ 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 static DBusHashEntry* find_two_strings_function (DBusHashTable *table, 00235 void *key, 00236 dbus_bool_t create_if_not_found, 00237 DBusHashEntry ***bucket, 00238 DBusPreallocatedHash *preallocated); 00239 static unsigned int string_hash (const char *str); 00240 static unsigned int two_strings_hash (const char *str); 00241 static void rebuild_table (DBusHashTable *table); 00242 static DBusHashEntry* alloc_entry (DBusHashTable *table); 00243 static void remove_entry (DBusHashTable *table, 00244 DBusHashEntry **bucket, 00245 DBusHashEntry *entry); 00246 static void free_entry (DBusHashTable *table, 00247 DBusHashEntry *entry); 00248 static void free_entry_data (DBusHashTable *table, 00249 DBusHashEntry *entry); 00250 00251 00287 DBusHashTable* 00288 _dbus_hash_table_new (DBusHashType type, 00289 DBusFreeFunction key_free_function, 00290 DBusFreeFunction value_free_function) 00291 { 00292 DBusHashTable *table; 00293 DBusMemPool *entry_pool; 00294 00295 table = dbus_new0 (DBusHashTable, 1); 00296 if (table == NULL) 00297 return NULL; 00298 00299 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE); 00300 if (entry_pool == NULL) 00301 { 00302 dbus_free (table); 00303 return NULL; 00304 } 00305 00306 table->refcount = 1; 00307 table->entry_pool = entry_pool; 00308 00309 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets)); 00310 00311 table->buckets = table->static_buckets; 00312 table->n_buckets = DBUS_SMALL_HASH_TABLE; 00313 table->n_entries = 0; 00314 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER; 00315 table->lo_rebuild_size = 0; 00316 table->down_shift = 28; 00317 table->mask = 3; 00318 table->key_type = type; 00319 00320 _dbus_assert (table->mask < table->n_buckets); 00321 00322 switch (table->key_type) 00323 { 00324 case DBUS_HASH_INT: 00325 case DBUS_HASH_POINTER: 00326 case DBUS_HASH_ULONG: 00327 table->find_function = find_direct_function; 00328 break; 00329 case DBUS_HASH_STRING: 00330 table->find_function = find_string_function; 00331 break; 00332 case DBUS_HASH_TWO_STRINGS: 00333 table->find_function = find_two_strings_function; 00334 break; 00335 default: 00336 _dbus_assert_not_reached ("Unknown hash table type"); 00337 break; 00338 } 00339 00340 table->free_key_function = key_free_function; 00341 table->free_value_function = value_free_function; 00342 00343 return table; 00344 } 00345 00346 00353 DBusHashTable * 00354 _dbus_hash_table_ref (DBusHashTable *table) 00355 { 00356 table->refcount += 1; 00357 00358 return table; 00359 } 00360 00367 void 00368 _dbus_hash_table_unref (DBusHashTable *table) 00369 { 00370 table->refcount -= 1; 00371 00372 if (table->refcount == 0) 00373 { 00374 #if 0 00375 DBusHashEntry *entry; 00376 DBusHashEntry *next; 00377 int i; 00378 00379 /* Free the entries in the table. */ 00380 for (i = 0; i < table->n_buckets; i++) 00381 { 00382 entry = table->buckets[i]; 00383 while (entry != NULL) 00384 { 00385 next = entry->next; 00386 00387 free_entry (table, entry); 00388 00389 entry = next; 00390 } 00391 } 00392 #else 00393 DBusHashEntry *entry; 00394 int i; 00395 00396 /* Free the entries in the table. */ 00397 for (i = 0; i < table->n_buckets; i++) 00398 { 00399 entry = table->buckets[i]; 00400 while (entry != NULL) 00401 { 00402 free_entry_data (table, entry); 00403 00404 entry = entry->next; 00405 } 00406 } 00407 /* We can do this very quickly with memory pools ;-) */ 00408 _dbus_mem_pool_free (table->entry_pool); 00409 #endif 00410 00411 /* Free the bucket array, if it was dynamically allocated. */ 00412 if (table->buckets != table->static_buckets) 00413 dbus_free (table->buckets); 00414 00415 dbus_free (table); 00416 } 00417 } 00418 00419 static DBusHashEntry* 00420 alloc_entry (DBusHashTable *table) 00421 { 00422 DBusHashEntry *entry; 00423 00424 entry = _dbus_mem_pool_alloc (table->entry_pool); 00425 00426 return entry; 00427 } 00428 00429 static void 00430 free_entry_data (DBusHashTable *table, 00431 DBusHashEntry *entry) 00432 { 00433 if (table->free_key_function) 00434 (* table->free_key_function) (entry->key); 00435 if (table->free_value_function) 00436 (* table->free_value_function) (entry->value); 00437 } 00438 00439 static void 00440 free_entry (DBusHashTable *table, 00441 DBusHashEntry *entry) 00442 { 00443 free_entry_data (table, entry); 00444 _dbus_mem_pool_dealloc (table->entry_pool, entry); 00445 } 00446 00447 static void 00448 remove_entry (DBusHashTable *table, 00449 DBusHashEntry **bucket, 00450 DBusHashEntry *entry) 00451 { 00452 _dbus_assert (table != NULL); 00453 _dbus_assert (bucket != NULL); 00454 _dbus_assert (*bucket != NULL); 00455 _dbus_assert (entry != NULL); 00456 00457 if (*bucket == entry) 00458 *bucket = entry->next; 00459 else 00460 { 00461 DBusHashEntry *prev; 00462 prev = *bucket; 00463 00464 while (prev->next != entry) 00465 prev = prev->next; 00466 00467 _dbus_assert (prev != NULL); 00468 00469 prev->next = entry->next; 00470 } 00471 00472 table->n_entries -= 1; 00473 free_entry (table, entry); 00474 } 00475 00507 void 00508 _dbus_hash_iter_init (DBusHashTable *table, 00509 DBusHashIter *iter) 00510 { 00511 DBusRealHashIter *real; 00512 00513 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00514 00515 real = (DBusRealHashIter*) iter; 00516 00517 real->table = table; 00518 real->bucket = NULL; 00519 real->entry = NULL; 00520 real->next_entry = NULL; 00521 real->next_bucket = 0; 00522 real->n_entries_on_init = table->n_entries; 00523 } 00524 00533 dbus_bool_t 00534 _dbus_hash_iter_next (DBusHashIter *iter) 00535 { 00536 DBusRealHashIter *real; 00537 00538 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00539 00540 real = (DBusRealHashIter*) iter; 00541 00542 /* if this assertion failed someone probably added hash entries 00543 * during iteration, which is bad. 00544 */ 00545 _dbus_assert (real->n_entries_on_init >= real->table->n_entries); 00546 00547 /* Remember that real->entry may have been deleted */ 00548 00549 while (real->next_entry == NULL) 00550 { 00551 if (real->next_bucket >= real->table->n_buckets) 00552 { 00553 /* invalidate iter and return false */ 00554 real->entry = NULL; 00555 real->table = NULL; 00556 real->bucket = NULL; 00557 return FALSE; 00558 } 00559 00560 real->bucket = &(real->table->buckets[real->next_bucket]); 00561 real->next_entry = *(real->bucket); 00562 real->next_bucket += 1; 00563 } 00564 00565 _dbus_assert (real->next_entry != NULL); 00566 _dbus_assert (real->bucket != NULL); 00567 00568 real->entry = real->next_entry; 00569 real->next_entry = real->entry->next; 00570 00571 return TRUE; 00572 } 00573 00582 void 00583 _dbus_hash_iter_remove_entry (DBusHashIter *iter) 00584 { 00585 DBusRealHashIter *real; 00586 00587 real = (DBusRealHashIter*) iter; 00588 00589 _dbus_assert (real->table != NULL); 00590 _dbus_assert (real->entry != NULL); 00591 _dbus_assert (real->bucket != NULL); 00592 00593 remove_entry (real->table, real->bucket, real->entry); 00594 00595 real->entry = NULL; /* make it crash if you try to use this entry */ 00596 } 00597 00603 void* 00604 _dbus_hash_iter_get_value (DBusHashIter *iter) 00605 { 00606 DBusRealHashIter *real; 00607 00608 real = (DBusRealHashIter*) iter; 00609 00610 _dbus_assert (real->table != NULL); 00611 _dbus_assert (real->entry != NULL); 00612 00613 return real->entry->value; 00614 } 00615 00626 void 00627 _dbus_hash_iter_set_value (DBusHashIter *iter, 00628 void *value) 00629 { 00630 DBusRealHashIter *real; 00631 00632 real = (DBusRealHashIter*) iter; 00633 00634 _dbus_assert (real->table != NULL); 00635 _dbus_assert (real->entry != NULL); 00636 00637 if (real->table->free_value_function && value != real->entry->value) 00638 (* real->table->free_value_function) (real->entry->value); 00639 00640 real->entry->value = value; 00641 } 00642 00649 int 00650 _dbus_hash_iter_get_int_key (DBusHashIter *iter) 00651 { 00652 DBusRealHashIter *real; 00653 00654 real = (DBusRealHashIter*) iter; 00655 00656 _dbus_assert (real->table != NULL); 00657 _dbus_assert (real->entry != NULL); 00658 00659 return _DBUS_POINTER_TO_INT (real->entry->key); 00660 } 00661 00668 unsigned long 00669 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter) 00670 { 00671 DBusRealHashIter *real; 00672 00673 real = (DBusRealHashIter*) iter; 00674 00675 _dbus_assert (real->table != NULL); 00676 _dbus_assert (real->entry != NULL); 00677 00678 return (unsigned long) real->entry->key; 00679 } 00680 00686 const char* 00687 _dbus_hash_iter_get_string_key (DBusHashIter *iter) 00688 { 00689 DBusRealHashIter *real; 00690 00691 real = (DBusRealHashIter*) iter; 00692 00693 _dbus_assert (real->table != NULL); 00694 _dbus_assert (real->entry != NULL); 00695 00696 return real->entry->key; 00697 } 00698 00704 const char* 00705 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter) 00706 { 00707 DBusRealHashIter *real; 00708 00709 real = (DBusRealHashIter*) iter; 00710 00711 _dbus_assert (real->table != NULL); 00712 _dbus_assert (real->entry != NULL); 00713 00714 return real->entry->key; 00715 } 00716 00748 dbus_bool_t 00749 _dbus_hash_iter_lookup (DBusHashTable *table, 00750 void *key, 00751 dbus_bool_t create_if_not_found, 00752 DBusHashIter *iter) 00753 { 00754 DBusRealHashIter *real; 00755 DBusHashEntry *entry; 00756 DBusHashEntry **bucket; 00757 00758 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00759 00760 real = (DBusRealHashIter*) iter; 00761 00762 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL); 00763 00764 if (entry == NULL) 00765 return FALSE; 00766 00767 real->table = table; 00768 real->bucket = bucket; 00769 real->entry = entry; 00770 real->next_entry = entry->next; 00771 real->next_bucket = (bucket - table->buckets) + 1; 00772 real->n_entries_on_init = table->n_entries; 00773 00774 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket); 00775 00776 return TRUE; 00777 } 00778 00779 static void 00780 add_allocated_entry (DBusHashTable *table, 00781 DBusHashEntry *entry, 00782 unsigned int idx, 00783 void *key, 00784 DBusHashEntry ***bucket) 00785 { 00786 DBusHashEntry **b; 00787 00788 entry->key = key; 00789 00790 b = &(table->buckets[idx]); 00791 entry->next = *b; 00792 *b = entry; 00793 00794 if (bucket) 00795 *bucket = b; 00796 00797 table->n_entries += 1; 00798 00799 /* note we ONLY rebuild when ADDING - because you can iterate over a 00800 * table and remove entries safely. 00801 */ 00802 if (table->n_entries >= table->hi_rebuild_size || 00803 table->n_entries < table->lo_rebuild_size) 00804 rebuild_table (table); 00805 } 00806 00807 static DBusHashEntry* 00808 add_entry (DBusHashTable *table, 00809 unsigned int idx, 00810 void *key, 00811 DBusHashEntry ***bucket, 00812 DBusPreallocatedHash *preallocated) 00813 { 00814 DBusHashEntry *entry; 00815 00816 if (preallocated == NULL) 00817 { 00818 entry = alloc_entry (table); 00819 if (entry == NULL) 00820 { 00821 if (bucket) 00822 *bucket = NULL; 00823 return NULL; 00824 } 00825 } 00826 else 00827 { 00828 entry = (DBusHashEntry*) preallocated; 00829 } 00830 00831 add_allocated_entry (table, entry, idx, key, bucket); 00832 00833 return entry; 00834 } 00835 00836 /* This is g_str_hash from GLib which was 00837 * extensively discussed/tested/profiled 00838 */ 00839 static unsigned int 00840 string_hash (const char *str) 00841 { 00842 const char *p = str; 00843 unsigned int h = *p; 00844 00845 if (h) 00846 for (p += 1; *p != '\0'; p++) 00847 h = (h << 5) - h + *p; 00848 00849 return h; 00850 } 00851 00852 /* This hashes a memory block with two nul-terminated strings 00853 * in it, used in dbus-object-registry.c at the moment. 00854 */ 00855 static unsigned int 00856 two_strings_hash (const char *str) 00857 { 00858 const char *p = str; 00859 unsigned int h = *p; 00860 00861 if (h) 00862 for (p += 1; *p != '\0'; p++) 00863 h = (h << 5) - h + *p; 00864 00865 for (p += 1; *p != '\0'; p++) 00866 h = (h << 5) - h + *p; 00867 00868 return h; 00869 } 00870 00872 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b); 00873 00874 static DBusHashEntry* 00875 find_generic_function (DBusHashTable *table, 00876 void *key, 00877 unsigned int idx, 00878 KeyCompareFunc compare_func, 00879 dbus_bool_t create_if_not_found, 00880 DBusHashEntry ***bucket, 00881 DBusPreallocatedHash *preallocated) 00882 { 00883 DBusHashEntry *entry; 00884 00885 if (bucket) 00886 *bucket = NULL; 00887 00888 /* Search all of the entries in this bucket. */ 00889 entry = table->buckets[idx]; 00890 while (entry != NULL) 00891 { 00892 if ((compare_func == NULL && key == entry->key) || 00893 (compare_func != NULL && (* compare_func) (key, entry->key) == 0)) 00894 { 00895 if (bucket) 00896 *bucket = &(table->buckets[idx]); 00897 00898 if (preallocated) 00899 _dbus_hash_table_free_preallocated_entry (table, preallocated); 00900 00901 return entry; 00902 } 00903 00904 entry = entry->next; 00905 } 00906 00907 if (create_if_not_found) 00908 entry = add_entry (table, idx, key, bucket, preallocated); 00909 else if (preallocated) 00910 _dbus_hash_table_free_preallocated_entry (table, preallocated); 00911 00912 return entry; 00913 } 00914 00915 static DBusHashEntry* 00916 find_string_function (DBusHashTable *table, 00917 void *key, 00918 dbus_bool_t create_if_not_found, 00919 DBusHashEntry ***bucket, 00920 DBusPreallocatedHash *preallocated) 00921 { 00922 unsigned int idx; 00923 00924 idx = string_hash (key) & table->mask; 00925 00926 return find_generic_function (table, key, idx, 00927 (KeyCompareFunc) strcmp, create_if_not_found, bucket, 00928 preallocated); 00929 } 00930 00931 static int 00932 two_strings_cmp (const char *a, 00933 const char *b) 00934 { 00935 size_t len_a; 00936 size_t len_b; 00937 int res; 00938 00939 res = strcmp (a, b); 00940 if (res != 0) 00941 return res; 00942 00943 len_a = strlen (a); 00944 len_b = strlen (b); 00945 00946 return strcmp (a + len_a + 1, b + len_b + 1); 00947 } 00948 00949 static DBusHashEntry* 00950 find_two_strings_function (DBusHashTable *table, 00951 void *key, 00952 dbus_bool_t create_if_not_found, 00953 DBusHashEntry ***bucket, 00954 DBusPreallocatedHash *preallocated) 00955 { 00956 unsigned int idx; 00957 00958 idx = two_strings_hash (key) & table->mask; 00959 00960 return find_generic_function (table, key, idx, 00961 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket, 00962 preallocated); 00963 } 00964 00965 static DBusHashEntry* 00966 find_direct_function (DBusHashTable *table, 00967 void *key, 00968 dbus_bool_t create_if_not_found, 00969 DBusHashEntry ***bucket, 00970 DBusPreallocatedHash *preallocated) 00971 { 00972 unsigned int idx; 00973 00974 idx = RANDOM_INDEX (table, key) & table->mask; 00975 00976 00977 return find_generic_function (table, key, idx, 00978 NULL, create_if_not_found, bucket, 00979 preallocated); 00980 } 00981 00982 static void 00983 rebuild_table (DBusHashTable *table) 00984 { 00985 int old_size; 00986 int new_buckets; 00987 DBusHashEntry **old_buckets; 00988 DBusHashEntry **old_chain; 00989 DBusHashEntry *entry; 00990 dbus_bool_t growing; 00991 00992 /* 00993 * Allocate and initialize the new bucket array, and set up 00994 * hashing constants for new array size. 00995 */ 00996 00997 growing = table->n_entries >= table->hi_rebuild_size; 00998 00999 old_size = table->n_buckets; 01000 old_buckets = table->buckets; 01001 01002 if (growing) 01003 { 01004 /* overflow paranoia */ 01005 if (table->n_buckets < _DBUS_INT_MAX / 4 && 01006 table->down_shift >= 0) 01007 new_buckets = table->n_buckets * 4; 01008 else 01009 return; /* can't grow anymore */ 01010 } 01011 else 01012 { 01013 new_buckets = table->n_buckets / 4; 01014 if (new_buckets < DBUS_SMALL_HASH_TABLE) 01015 return; /* don't bother shrinking this far */ 01016 } 01017 01018 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets); 01019 if (table->buckets == NULL) 01020 { 01021 /* out of memory, yay - just don't reallocate, the table will 01022 * still work, albeit more slowly. 01023 */ 01024 table->buckets = old_buckets; 01025 return; 01026 } 01027 01028 table->n_buckets = new_buckets; 01029 01030 if (growing) 01031 { 01032 table->lo_rebuild_size = table->hi_rebuild_size; 01033 table->hi_rebuild_size *= 4; 01034 01035 table->down_shift -= 2; /* keep 2 more high bits */ 01036 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */ 01037 } 01038 else 01039 { 01040 table->hi_rebuild_size = table->lo_rebuild_size; 01041 table->lo_rebuild_size /= 4; 01042 01043 table->down_shift += 2; /* keep 2 fewer high bits */ 01044 table->mask = table->mask >> 2; /* keep 2 fewer high bits */ 01045 } 01046 01047 #if 0 01048 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", 01049 growing ? "GROW" : "SHRINK", 01050 table->lo_rebuild_size, 01051 table->hi_rebuild_size, 01052 table->down_shift, 01053 table->mask); 01054 #endif 01055 01056 _dbus_assert (table->lo_rebuild_size >= 0); 01057 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size); 01058 _dbus_assert (table->mask != 0); 01059 /* the mask is essentially the max index */ 01060 _dbus_assert (table->mask < table->n_buckets); 01061 01062 /* 01063 * Rehash all of the existing entries into the new bucket array. 01064 */ 01065 01066 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++) 01067 { 01068 for (entry = *old_chain; entry != NULL; entry = *old_chain) 01069 { 01070 unsigned int idx; 01071 DBusHashEntry **bucket; 01072 01073 *old_chain = entry->next; 01074 switch (table->key_type) 01075 { 01076 case DBUS_HASH_STRING: 01077 idx = string_hash (entry->key) & table->mask; 01078 break; 01079 case DBUS_HASH_TWO_STRINGS: 01080 idx = two_strings_hash (entry->key) & table->mask; 01081 break; 01082 case DBUS_HASH_INT: 01083 case DBUS_HASH_ULONG: 01084 case DBUS_HASH_POINTER: 01085 idx = RANDOM_INDEX (table, entry->key); 01086 break; 01087 default: 01088 idx = 0; 01089 _dbus_assert_not_reached ("Unknown hash table type"); 01090 break; 01091 } 01092 01093 bucket = &(table->buckets[idx]); 01094 entry->next = *bucket; 01095 *bucket = entry; 01096 } 01097 } 01098 01099 /* Free the old bucket array, if it was dynamically allocated. */ 01100 01101 if (old_buckets != table->static_buckets) 01102 dbus_free (old_buckets); 01103 } 01104 01114 void* 01115 _dbus_hash_table_lookup_string (DBusHashTable *table, 01116 const char *key) 01117 { 01118 DBusHashEntry *entry; 01119 01120 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01121 01122 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 01123 01124 if (entry) 01125 return entry->value; 01126 else 01127 return NULL; 01128 } 01129 01139 void* 01140 _dbus_hash_table_lookup_two_strings (DBusHashTable *table, 01141 const char *key) 01142 { 01143 DBusHashEntry *entry; 01144 01145 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01146 01147 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 01148 01149 if (entry) 01150 return entry->value; 01151 else 01152 return NULL; 01153 } 01154 01164 void* 01165 _dbus_hash_table_lookup_int (DBusHashTable *table, 01166 int key) 01167 { 01168 DBusHashEntry *entry; 01169 01170 _dbus_assert (table->key_type == DBUS_HASH_INT); 01171 01172 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL); 01173 01174 if (entry) 01175 return entry->value; 01176 else 01177 return NULL; 01178 } 01179 01180 #ifdef DBUS_BUILD_TESTS 01181 /* disabled since it's only used for testing */ 01191 void* 01192 _dbus_hash_table_lookup_pointer (DBusHashTable *table, 01193 void *key) 01194 { 01195 DBusHashEntry *entry; 01196 01197 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01198 01199 entry = (* table->find_function) (table, key, FALSE, NULL, NULL); 01200 01201 if (entry) 01202 return entry->value; 01203 else 01204 return NULL; 01205 } 01206 #endif /* DBUS_BUILD_TESTS */ 01207 01217 void* 01218 _dbus_hash_table_lookup_ulong (DBusHashTable *table, 01219 unsigned long key) 01220 { 01221 DBusHashEntry *entry; 01222 01223 _dbus_assert (table->key_type == DBUS_HASH_ULONG); 01224 01225 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL); 01226 01227 if (entry) 01228 return entry->value; 01229 else 01230 return NULL; 01231 } 01232 01241 dbus_bool_t 01242 _dbus_hash_table_remove_string (DBusHashTable *table, 01243 const char *key) 01244 { 01245 DBusHashEntry *entry; 01246 DBusHashEntry **bucket; 01247 01248 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01249 01250 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 01251 01252 if (entry) 01253 { 01254 remove_entry (table, bucket, entry); 01255 return TRUE; 01256 } 01257 else 01258 return FALSE; 01259 } 01260 01269 dbus_bool_t 01270 _dbus_hash_table_remove_two_strings (DBusHashTable *table, 01271 const char *key) 01272 { 01273 DBusHashEntry *entry; 01274 DBusHashEntry **bucket; 01275 01276 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01277 01278 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 01279 01280 if (entry) 01281 { 01282 remove_entry (table, bucket, entry); 01283 return TRUE; 01284 } 01285 else 01286 return FALSE; 01287 } 01288 01297 dbus_bool_t 01298 _dbus_hash_table_remove_int (DBusHashTable *table, 01299 int key) 01300 { 01301 DBusHashEntry *entry; 01302 DBusHashEntry **bucket; 01303 01304 _dbus_assert (table->key_type == DBUS_HASH_INT); 01305 01306 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL); 01307 01308 if (entry) 01309 { 01310 remove_entry (table, bucket, entry); 01311 return TRUE; 01312 } 01313 else 01314 return FALSE; 01315 } 01316 01317 #ifdef DBUS_BUILD_TESTS 01318 /* disabled since it's only used for testing */ 01327 dbus_bool_t 01328 _dbus_hash_table_remove_pointer (DBusHashTable *table, 01329 void *key) 01330 { 01331 DBusHashEntry *entry; 01332 DBusHashEntry **bucket; 01333 01334 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01335 01336 entry = (* table->find_function) (table, key, FALSE, &bucket, NULL); 01337 01338 if (entry) 01339 { 01340 remove_entry (table, bucket, entry); 01341 return TRUE; 01342 } 01343 else 01344 return FALSE; 01345 } 01346 #endif /* DBUS_BUILD_TESTS */ 01347 01356 dbus_bool_t 01357 _dbus_hash_table_remove_ulong (DBusHashTable *table, 01358 unsigned long key) 01359 { 01360 DBusHashEntry *entry; 01361 DBusHashEntry **bucket; 01362 01363 _dbus_assert (table->key_type == DBUS_HASH_ULONG); 01364 01365 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL); 01366 01367 if (entry) 01368 { 01369 remove_entry (table, bucket, entry); 01370 return TRUE; 01371 } 01372 else 01373 return FALSE; 01374 } 01375 01391 dbus_bool_t 01392 _dbus_hash_table_insert_string (DBusHashTable *table, 01393 char *key, 01394 void *value) 01395 { 01396 DBusPreallocatedHash *preallocated; 01397 01398 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01399 01400 preallocated = _dbus_hash_table_preallocate_entry (table); 01401 if (preallocated == NULL) 01402 return FALSE; 01403 01404 _dbus_hash_table_insert_string_preallocated (table, preallocated, 01405 key, value); 01406 01407 return TRUE; 01408 } 01409 01425 dbus_bool_t 01426 _dbus_hash_table_insert_two_strings (DBusHashTable *table, 01427 char *key, 01428 void *value) 01429 { 01430 DBusHashEntry *entry; 01431 01432 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS); 01433 01434 entry = (* table->find_function) (table, key, TRUE, NULL, NULL); 01435 01436 if (entry == NULL) 01437 return FALSE; /* no memory */ 01438 01439 if (table->free_key_function && entry->key != key) 01440 (* table->free_key_function) (entry->key); 01441 01442 if (table->free_value_function && entry->value != value) 01443 (* table->free_value_function) (entry->value); 01444 01445 entry->key = key; 01446 entry->value = value; 01447 01448 return TRUE; 01449 } 01450 01466 dbus_bool_t 01467 _dbus_hash_table_insert_int (DBusHashTable *table, 01468 int key, 01469 void *value) 01470 { 01471 DBusHashEntry *entry; 01472 01473 _dbus_assert (table->key_type == DBUS_HASH_INT); 01474 01475 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL); 01476 01477 if (entry == NULL) 01478 return FALSE; /* no memory */ 01479 01480 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key)) 01481 (* table->free_key_function) (entry->key); 01482 01483 if (table->free_value_function && entry->value != value) 01484 (* table->free_value_function) (entry->value); 01485 01486 entry->key = _DBUS_INT_TO_POINTER (key); 01487 entry->value = value; 01488 01489 return TRUE; 01490 } 01491 01492 #ifdef DBUS_BUILD_TESTS 01493 /* disabled since it's only used for testing */ 01509 dbus_bool_t 01510 _dbus_hash_table_insert_pointer (DBusHashTable *table, 01511 void *key, 01512 void *value) 01513 { 01514 DBusHashEntry *entry; 01515 01516 _dbus_assert (table->key_type == DBUS_HASH_POINTER); 01517 01518 entry = (* table->find_function) (table, key, TRUE, NULL, NULL); 01519 01520 if (entry == NULL) 01521 return FALSE; /* no memory */ 01522 01523 if (table->free_key_function && entry->key != key) 01524 (* table->free_key_function) (entry->key); 01525 01526 if (table->free_value_function && entry->value != value) 01527 (* table->free_value_function) (entry->value); 01528 01529 entry->key = key; 01530 entry->value = value; 01531 01532 return TRUE; 01533 } 01534 #endif /* DBUS_BUILD_TESTS */ 01535 01551 dbus_bool_t 01552 _dbus_hash_table_insert_ulong (DBusHashTable *table, 01553 unsigned long key, 01554 void *value) 01555 { 01556 DBusHashEntry *entry; 01557 01558 _dbus_assert (table->key_type == DBUS_HASH_ULONG); 01559 01560 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL); 01561 01562 if (entry == NULL) 01563 return FALSE; /* no memory */ 01564 01565 if (table->free_key_function && entry->key != (void*) key) 01566 (* table->free_key_function) (entry->key); 01567 01568 if (table->free_value_function && entry->value != value) 01569 (* table->free_value_function) (entry->value); 01570 01571 entry->key = (void*) key; 01572 entry->value = value; 01573 01574 return TRUE; 01575 } 01576 01584 DBusPreallocatedHash* 01585 _dbus_hash_table_preallocate_entry (DBusHashTable *table) 01586 { 01587 DBusHashEntry *entry; 01588 01589 entry = alloc_entry (table); 01590 01591 return (DBusPreallocatedHash*) entry; 01592 } 01593 01601 void 01602 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table, 01603 DBusPreallocatedHash *preallocated) 01604 { 01605 DBusHashEntry *entry; 01606 01607 _dbus_assert (preallocated != NULL); 01608 01609 entry = (DBusHashEntry*) preallocated; 01610 01611 /* Don't use free_entry(), since this entry has no key/data */ 01612 _dbus_mem_pool_dealloc (table->entry_pool, entry); 01613 } 01614 01628 void 01629 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table, 01630 DBusPreallocatedHash *preallocated, 01631 char *key, 01632 void *value) 01633 { 01634 DBusHashEntry *entry; 01635 01636 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01637 _dbus_assert (preallocated != NULL); 01638 01639 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated); 01640 01641 _dbus_assert (entry != NULL); 01642 01643 if (table->free_key_function && entry->key != key) 01644 (* table->free_key_function) (entry->key); 01645 01646 if (table->free_value_function && entry->value != value) 01647 (* table->free_value_function) (entry->value); 01648 01649 entry->key = key; 01650 entry->value = value; 01651 } 01652 01659 int 01660 _dbus_hash_table_get_n_entries (DBusHashTable *table) 01661 { 01662 return table->n_entries; 01663 } 01664 01667 #ifdef DBUS_BUILD_TESTS 01668 #include "dbus-test.h" 01669 #include <stdio.h> 01670 01671 /* If you're wondering why the hash table test takes 01672 * forever to run, it's because we call this function 01673 * in inner loops thus making things quadratic. 01674 */ 01675 static int 01676 count_entries (DBusHashTable *table) 01677 { 01678 DBusHashIter iter; 01679 int count; 01680 01681 count = 0; 01682 _dbus_hash_iter_init (table, &iter); 01683 while (_dbus_hash_iter_next (&iter)) 01684 ++count; 01685 01686 _dbus_assert (count == _dbus_hash_table_get_n_entries (table)); 01687 01688 return count; 01689 } 01690 01691 /* Copy the foo\0bar\0 double string thing */ 01692 static char* 01693 _dbus_strdup2 (const char *str) 01694 { 01695 size_t len; 01696 char *copy; 01697 01698 if (str == NULL) 01699 return NULL; 01700 01701 len = strlen (str); 01702 len += strlen ((str + len + 1)); 01703 01704 copy = dbus_malloc (len + 2); 01705 if (copy == NULL) 01706 return NULL; 01707 01708 memcpy (copy, str, len + 2); 01709 01710 return copy; 01711 } 01712 01718 dbus_bool_t 01719 _dbus_hash_test (void) 01720 { 01721 int i; 01722 DBusHashTable *table1; 01723 DBusHashTable *table2; 01724 DBusHashTable *table3; 01725 DBusHashTable *table4; 01726 DBusHashIter iter; 01727 #define N_HASH_KEYS 5000 01728 char **keys; 01729 dbus_bool_t ret = FALSE; 01730 01731 keys = dbus_new (char *, N_HASH_KEYS); 01732 if (keys == NULL) 01733 _dbus_assert_not_reached ("no memory"); 01734 01735 for (i = 0; i < N_HASH_KEYS; i++) 01736 { 01737 keys[i] = dbus_malloc (128); 01738 01739 if (keys[i] == NULL) 01740 _dbus_assert_not_reached ("no memory"); 01741 } 01742 01743 printf ("Computing test hash keys...\n"); 01744 i = 0; 01745 while (i < N_HASH_KEYS) 01746 { 01747 int len; 01748 01749 /* all the hash keys are TWO_STRINGS, but 01750 * then we can also use those as regular strings. 01751 */ 01752 01753 len = sprintf (keys[i], "Hash key %d", i); 01754 sprintf (keys[i] + len + 1, "Two string %d", i); 01755 _dbus_assert (*(keys[i] + len) == '\0'); 01756 _dbus_assert (*(keys[i] + len + 1) != '\0'); 01757 ++i; 01758 } 01759 printf ("... done.\n"); 01760 01761 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01762 dbus_free, dbus_free); 01763 if (table1 == NULL) 01764 goto out; 01765 01766 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01767 NULL, dbus_free); 01768 if (table2 == NULL) 01769 goto out; 01770 01771 table3 = _dbus_hash_table_new (DBUS_HASH_ULONG, 01772 NULL, dbus_free); 01773 if (table3 == NULL) 01774 goto out; 01775 01776 table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS, 01777 dbus_free, dbus_free); 01778 if (table4 == NULL) 01779 goto out; 01780 01781 01782 /* Insert and remove a bunch of stuff, counting the table in between 01783 * to be sure it's not broken and that iteration works 01784 */ 01785 i = 0; 01786 while (i < 3000) 01787 { 01788 void *value; 01789 char *key; 01790 01791 key = _dbus_strdup (keys[i]); 01792 if (key == NULL) 01793 goto out; 01794 value = _dbus_strdup ("Value!"); 01795 if (value == NULL) 01796 goto out; 01797 01798 if (!_dbus_hash_table_insert_string (table1, 01799 key, value)) 01800 goto out; 01801 01802 value = _dbus_strdup (keys[i]); 01803 if (value == NULL) 01804 goto out; 01805 01806 if (!_dbus_hash_table_insert_int (table2, 01807 i, value)) 01808 goto out; 01809 01810 value = _dbus_strdup (keys[i]); 01811 if (value == NULL) 01812 goto out; 01813 01814 if (!_dbus_hash_table_insert_ulong (table3, 01815 i, value)) 01816 goto out; 01817 01818 key = _dbus_strdup2 (keys[i]); 01819 if (key == NULL) 01820 goto out; 01821 value = _dbus_strdup ("Value!"); 01822 if (value == NULL) 01823 goto out; 01824 01825 if (!_dbus_hash_table_insert_two_strings (table4, 01826 key, value)) 01827 goto out; 01828 01829 _dbus_assert (count_entries (table1) == i + 1); 01830 _dbus_assert (count_entries (table2) == i + 1); 01831 _dbus_assert (count_entries (table3) == i + 1); 01832 _dbus_assert (count_entries (table4) == i + 1); 01833 01834 value = _dbus_hash_table_lookup_string (table1, keys[i]); 01835 _dbus_assert (value != NULL); 01836 _dbus_assert (strcmp (value, "Value!") == 0); 01837 01838 value = _dbus_hash_table_lookup_int (table2, i); 01839 _dbus_assert (value != NULL); 01840 _dbus_assert (strcmp (value, keys[i]) == 0); 01841 01842 value = _dbus_hash_table_lookup_ulong (table3, i); 01843 _dbus_assert (value != NULL); 01844 _dbus_assert (strcmp (value, keys[i]) == 0); 01845 01846 value = _dbus_hash_table_lookup_two_strings (table4, keys[i]); 01847 _dbus_assert (value != NULL); 01848 _dbus_assert (strcmp (value, "Value!") == 0); 01849 01850 ++i; 01851 } 01852 01853 --i; 01854 while (i >= 0) 01855 { 01856 _dbus_hash_table_remove_string (table1, 01857 keys[i]); 01858 01859 _dbus_hash_table_remove_int (table2, i); 01860 01861 _dbus_hash_table_remove_ulong (table3, i); 01862 01863 _dbus_hash_table_remove_two_strings (table4, 01864 keys[i]); 01865 01866 _dbus_assert (count_entries (table1) == i); 01867 _dbus_assert (count_entries (table2) == i); 01868 _dbus_assert (count_entries (table3) == i); 01869 _dbus_assert (count_entries (table4) == i); 01870 01871 --i; 01872 } 01873 01874 _dbus_hash_table_ref (table1); 01875 _dbus_hash_table_ref (table2); 01876 _dbus_hash_table_ref (table3); 01877 _dbus_hash_table_ref (table4); 01878 _dbus_hash_table_unref (table1); 01879 _dbus_hash_table_unref (table2); 01880 _dbus_hash_table_unref (table3); 01881 _dbus_hash_table_unref (table4); 01882 _dbus_hash_table_unref (table1); 01883 _dbus_hash_table_unref (table2); 01884 _dbus_hash_table_unref (table3); 01885 _dbus_hash_table_unref (table4); 01886 table3 = NULL; 01887 01888 /* Insert a bunch of stuff then check 01889 * that iteration works correctly (finds the right 01890 * values, iter_set_value works, etc.) 01891 */ 01892 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01893 dbus_free, dbus_free); 01894 if (table1 == NULL) 01895 goto out; 01896 01897 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01898 NULL, dbus_free); 01899 if (table2 == NULL) 01900 goto out; 01901 01902 i = 0; 01903 while (i < 5000) 01904 { 01905 char *key; 01906 void *value; 01907 01908 key = _dbus_strdup (keys[i]); 01909 if (key == NULL) 01910 goto out; 01911 value = _dbus_strdup ("Value!"); 01912 if (value == NULL) 01913 goto out; 01914 01915 if (!_dbus_hash_table_insert_string (table1, 01916 key, value)) 01917 goto out; 01918 01919 value = _dbus_strdup (keys[i]); 01920 if (value == NULL) 01921 goto out; 01922 01923 if (!_dbus_hash_table_insert_int (table2, 01924 i, value)) 01925 goto out; 01926 01927 _dbus_assert (count_entries (table1) == i + 1); 01928 _dbus_assert (count_entries (table2) == i + 1); 01929 01930 ++i; 01931 } 01932 01933 _dbus_hash_iter_init (table1, &iter); 01934 while (_dbus_hash_iter_next (&iter)) 01935 { 01936 const char *key; 01937 void *value; 01938 01939 key = _dbus_hash_iter_get_string_key (&iter); 01940 value = _dbus_hash_iter_get_value (&iter); 01941 01942 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 01943 01944 value = _dbus_strdup ("Different value!"); 01945 if (value == NULL) 01946 goto out; 01947 01948 _dbus_hash_iter_set_value (&iter, value); 01949 01950 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 01951 } 01952 01953 _dbus_hash_iter_init (table1, &iter); 01954 while (_dbus_hash_iter_next (&iter)) 01955 { 01956 _dbus_hash_iter_remove_entry (&iter); 01957 _dbus_assert (count_entries (table1) == i - 1); 01958 --i; 01959 } 01960 01961 _dbus_hash_iter_init (table2, &iter); 01962 while (_dbus_hash_iter_next (&iter)) 01963 { 01964 int key; 01965 void *value; 01966 01967 key = _dbus_hash_iter_get_int_key (&iter); 01968 value = _dbus_hash_iter_get_value (&iter); 01969 01970 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 01971 01972 value = _dbus_strdup ("Different value!"); 01973 if (value == NULL) 01974 goto out; 01975 01976 _dbus_hash_iter_set_value (&iter, value); 01977 01978 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 01979 } 01980 01981 i = count_entries (table2); 01982 _dbus_hash_iter_init (table2, &iter); 01983 while (_dbus_hash_iter_next (&iter)) 01984 { 01985 _dbus_hash_iter_remove_entry (&iter); 01986 _dbus_assert (count_entries (table2) + 1 == i); 01987 --i; 01988 } 01989 01990 /* add/remove interleaved, to check that we grow/shrink the table 01991 * appropriately 01992 */ 01993 i = 0; 01994 while (i < 1000) 01995 { 01996 char *key; 01997 void *value; 01998 01999 key = _dbus_strdup (keys[i]); 02000 if (key == NULL) 02001 goto out; 02002 02003 value = _dbus_strdup ("Value!"); 02004 if (value == NULL) 02005 goto out; 02006 02007 if (!_dbus_hash_table_insert_string (table1, 02008 key, value)) 02009 goto out; 02010 02011 ++i; 02012 } 02013 02014 --i; 02015 while (i >= 0) 02016 { 02017 char *key; 02018 void *value; 02019 02020 key = _dbus_strdup (keys[i]); 02021 if (key == NULL) 02022 goto out; 02023 value = _dbus_strdup ("Value!"); 02024 if (value == NULL) 02025 goto out; 02026 02027 if (!_dbus_hash_table_remove_string (table1, keys[i])) 02028 goto out; 02029 02030 if (!_dbus_hash_table_insert_string (table1, 02031 key, value)) 02032 goto out; 02033 02034 if (!_dbus_hash_table_remove_string (table1, keys[i])) 02035 goto out; 02036 02037 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i); 02038 02039 --i; 02040 } 02041 02042 /* nuke these tables */ 02043 _dbus_hash_table_unref (table1); 02044 _dbus_hash_table_unref (table2); 02045 02046 02047 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to 02048 * be sure that interface works. 02049 */ 02050 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 02051 dbus_free, dbus_free); 02052 if (table1 == NULL) 02053 goto out; 02054 02055 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 02056 NULL, dbus_free); 02057 if (table2 == NULL) 02058 goto out; 02059 02060 i = 0; 02061 while (i < 3000) 02062 { 02063 void *value; 02064 char *key; 02065 02066 key = _dbus_strdup (keys[i]); 02067 if (key == NULL) 02068 goto out; 02069 value = _dbus_strdup ("Value!"); 02070 if (value == NULL) 02071 goto out; 02072 02073 if (!_dbus_hash_iter_lookup (table1, 02074 key, TRUE, &iter)) 02075 goto out; 02076 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 02077 _dbus_hash_iter_set_value (&iter, value); 02078 02079 value = _dbus_strdup (keys[i]); 02080 if (value == NULL) 02081 goto out; 02082 02083 if (!_dbus_hash_iter_lookup (table2, 02084 _DBUS_INT_TO_POINTER (i), TRUE, &iter)) 02085 goto out; 02086 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 02087 _dbus_hash_iter_set_value (&iter, value); 02088 02089 _dbus_assert (count_entries (table1) == i + 1); 02090 _dbus_assert (count_entries (table2) == i + 1); 02091 02092 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 02093 goto out; 02094 02095 value = _dbus_hash_iter_get_value (&iter); 02096 _dbus_assert (value != NULL); 02097 _dbus_assert (strcmp (value, "Value!") == 0); 02098 02099 /* Iterate just to be sure it works, though 02100 * it's a stupid thing to do 02101 */ 02102 while (_dbus_hash_iter_next (&iter)) 02103 ; 02104 02105 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 02106 goto out; 02107 02108 value = _dbus_hash_iter_get_value (&iter); 02109 _dbus_assert (value != NULL); 02110 _dbus_assert (strcmp (value, keys[i]) == 0); 02111 02112 /* Iterate just to be sure it works, though 02113 * it's a stupid thing to do 02114 */ 02115 while (_dbus_hash_iter_next (&iter)) 02116 ; 02117 02118 ++i; 02119 } 02120 02121 --i; 02122 while (i >= 0) 02123 { 02124 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 02125 _dbus_assert_not_reached ("hash entry should have existed"); 02126 _dbus_hash_iter_remove_entry (&iter); 02127 02128 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 02129 _dbus_assert_not_reached ("hash entry should have existed"); 02130 _dbus_hash_iter_remove_entry (&iter); 02131 02132 _dbus_assert (count_entries (table1) == i); 02133 _dbus_assert (count_entries (table2) == i); 02134 02135 --i; 02136 } 02137 02138 _dbus_hash_table_unref (table1); 02139 _dbus_hash_table_unref (table2); 02140 02141 ret = TRUE; 02142 02143 out: 02144 for (i = 0; i < N_HASH_KEYS; i++) 02145 dbus_free (keys[i]); 02146 02147 dbus_free (keys); 02148 02149 return ret; 02150 } 02151 02152 #endif /* DBUS_BUILD_TESTS */

Generated on Mon Aug 16 17:40:08 2004 for D-BUS by doxygen 1.3.8