D-Bus 1.6.12
|
00001 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */ 00002 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation) 00003 * 00004 * Copyright (C) 2002 Red Hat, Inc. 00005 * Copyright (c) 1991-1993 The Regents of the University of California. 00006 * Copyright (c) 1994 Sun Microsystems, Inc. 00007 * 00008 * Hash table implementation based on generic/tclHash.c from the Tcl 00009 * source code. The original Tcl license applies to portions of the 00010 * code from tclHash.c; the Tcl license follows this standad D-Bus 00011 * license information. 00012 * 00013 * Licensed under the Academic Free License version 2.1 00014 * 00015 * This program is free software; you can redistribute it and/or modify 00016 * it under the terms of the GNU General Public License as published by 00017 * the Free Software Foundation; either version 2 of the License, or 00018 * (at your option) any later version. 00019 * 00020 * This program is distributed in the hope that it will be useful, 00021 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00022 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00023 * GNU General Public License for more details. 00024 * 00025 * You should have received a copy of the GNU General Public License 00026 * along with this program; if not, write to the Free Software 00027 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00028 * 00029 */ 00030 /* 00031 * The following copyright applies to code from the Tcl distribution. 00032 * 00033 * Copyright (c) 1991-1993 The Regents of the University of California. 00034 * Copyright (c) 1994 Sun Microsystems, Inc. 00035 * 00036 * This software is copyrighted by the Regents of the University of 00037 * California, Sun Microsystems, Inc., Scriptics Corporation, and 00038 * other parties. The following terms apply to all files associated 00039 * with the software unless explicitly disclaimed in individual files. 00040 * 00041 * The authors hereby grant permission to use, copy, modify, 00042 * distribute, and license this software and its documentation for any 00043 * purpose, provided that existing copyright notices are retained in 00044 * all copies and that this notice is included verbatim in any 00045 * distributions. No written agreement, license, or royalty fee is 00046 * required for any of the authorized uses. Modifications to this 00047 * software may be copyrighted by their authors and need not follow 00048 * the licensing terms described here, provided that the new terms are 00049 * clearly indicated on the first page of each file where they apply. 00050 * 00051 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY 00052 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL 00053 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, 00054 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED 00055 * OF THE POSSIBILITY OF SUCH DAMAGE. 00056 * 00057 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, 00058 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 00059 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND 00060 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, 00061 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE 00062 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 00063 * 00064 * GOVERNMENT USE: If you are acquiring this software on behalf of the 00065 * U.S. government, the Government shall have only "Restricted Rights" 00066 * in the software and related documentation as defined in the Federal 00067 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you 00068 * are acquiring the software on behalf of the Department of Defense, 00069 * the software shall be classified as "Commercial Computer Software" 00070 * and the Government shall have only "Restricted Rights" as defined 00071 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the 00072 * foregoing, the authors grant the U.S. Government and others acting 00073 * in its behalf permission to use and distribute the software in 00074 * accordance with the terms specified in this license. 00075 */ 00076 00077 #include <config.h> 00078 #include "dbus-hash.h" 00079 #include "dbus-internals.h" 00080 #include "dbus-mempool.h" 00081 00104 #define REBUILD_MULTIPLIER 3 00105 00122 #define RANDOM_INDEX(table, i) \ 00123 (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask) 00124 00130 #define DBUS_SMALL_HASH_TABLE 4 00131 00135 typedef struct DBusHashEntry DBusHashEntry; 00136 00143 struct DBusHashEntry 00144 { 00145 DBusHashEntry *next; 00149 void *key; 00150 void *value; 00151 }; 00152 00156 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table, 00157 void *key, 00158 dbus_bool_t create_if_not_found, 00159 DBusHashEntry ***bucket, 00160 DBusPreallocatedHash *preallocated); 00161 00168 struct DBusHashTable { 00169 int refcount; 00171 DBusHashEntry **buckets; 00175 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE]; 00179 int n_buckets; 00182 int n_entries; 00185 int hi_rebuild_size; 00188 int lo_rebuild_size; 00191 int down_shift; 00195 int mask; 00198 DBusHashType key_type; 00201 DBusFindEntryFunction find_function; 00203 DBusFreeFunction free_key_function; 00204 DBusFreeFunction free_value_function; 00206 DBusMemPool *entry_pool; 00207 }; 00208 00212 typedef struct 00213 { 00214 DBusHashTable *table; 00215 DBusHashEntry **bucket; 00219 DBusHashEntry *entry; 00220 DBusHashEntry *next_entry; 00221 int next_bucket; 00222 int n_entries_on_init; 00223 } DBusRealHashIter; 00224 00225 _DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter)); 00226 00227 static DBusHashEntry* find_direct_function (DBusHashTable *table, 00228 void *key, 00229 dbus_bool_t create_if_not_found, 00230 DBusHashEntry ***bucket, 00231 DBusPreallocatedHash *preallocated); 00232 static DBusHashEntry* find_string_function (DBusHashTable *table, 00233 void *key, 00234 dbus_bool_t create_if_not_found, 00235 DBusHashEntry ***bucket, 00236 DBusPreallocatedHash *preallocated); 00237 static unsigned int string_hash (const char *str); 00238 static void rebuild_table (DBusHashTable *table); 00239 static DBusHashEntry* alloc_entry (DBusHashTable *table); 00240 static void remove_entry (DBusHashTable *table, 00241 DBusHashEntry **bucket, 00242 DBusHashEntry *entry); 00243 static void free_entry (DBusHashTable *table, 00244 DBusHashEntry *entry); 00245 static void free_entry_data (DBusHashTable *table, 00246 DBusHashEntry *entry); 00247 00248 00284 DBusHashTable* 00285 _dbus_hash_table_new (DBusHashType type, 00286 DBusFreeFunction key_free_function, 00287 DBusFreeFunction value_free_function) 00288 { 00289 DBusHashTable *table; 00290 DBusMemPool *entry_pool; 00291 00292 table = dbus_new0 (DBusHashTable, 1); 00293 if (table == NULL) 00294 return NULL; 00295 00296 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE); 00297 if (entry_pool == NULL) 00298 { 00299 dbus_free (table); 00300 return NULL; 00301 } 00302 00303 table->refcount = 1; 00304 table->entry_pool = entry_pool; 00305 00306 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets)); 00307 00308 table->buckets = table->static_buckets; 00309 table->n_buckets = DBUS_SMALL_HASH_TABLE; 00310 table->n_entries = 0; 00311 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER; 00312 table->lo_rebuild_size = 0; 00313 table->down_shift = 28; 00314 table->mask = 3; 00315 table->key_type = type; 00316 00317 _dbus_assert (table->mask < table->n_buckets); 00318 00319 switch (table->key_type) 00320 { 00321 case DBUS_HASH_INT: 00322 case DBUS_HASH_UINTPTR: 00323 table->find_function = find_direct_function; 00324 break; 00325 case DBUS_HASH_STRING: 00326 table->find_function = find_string_function; 00327 break; 00328 default: 00329 _dbus_assert_not_reached ("Unknown hash table type"); 00330 break; 00331 } 00332 00333 table->free_key_function = key_free_function; 00334 table->free_value_function = value_free_function; 00335 00336 return table; 00337 } 00338 00339 00346 DBusHashTable * 00347 _dbus_hash_table_ref (DBusHashTable *table) 00348 { 00349 table->refcount += 1; 00350 00351 return table; 00352 } 00353 00360 void 00361 _dbus_hash_table_unref (DBusHashTable *table) 00362 { 00363 table->refcount -= 1; 00364 00365 if (table->refcount == 0) 00366 { 00367 #if 0 00368 DBusHashEntry *entry; 00369 DBusHashEntry *next; 00370 int i; 00371 00372 /* Free the entries in the table. */ 00373 for (i = 0; i < table->n_buckets; i++) 00374 { 00375 entry = table->buckets[i]; 00376 while (entry != NULL) 00377 { 00378 next = entry->next; 00379 00380 free_entry (table, entry); 00381 00382 entry = next; 00383 } 00384 } 00385 #else 00386 DBusHashEntry *entry; 00387 int i; 00388 00389 /* Free the entries in the table. */ 00390 for (i = 0; i < table->n_buckets; i++) 00391 { 00392 entry = table->buckets[i]; 00393 while (entry != NULL) 00394 { 00395 free_entry_data (table, entry); 00396 00397 entry = entry->next; 00398 } 00399 } 00400 /* We can do this very quickly with memory pools ;-) */ 00401 _dbus_mem_pool_free (table->entry_pool); 00402 #endif 00403 00404 /* Free the bucket array, if it was dynamically allocated. */ 00405 if (table->buckets != table->static_buckets) 00406 dbus_free (table->buckets); 00407 00408 dbus_free (table); 00409 } 00410 } 00411 00417 void 00418 _dbus_hash_table_remove_all (DBusHashTable *table) 00419 { 00420 DBusHashIter iter; 00421 _dbus_hash_iter_init (table, &iter); 00422 while (_dbus_hash_iter_next (&iter)) 00423 { 00424 _dbus_hash_iter_remove_entry(&iter); 00425 } 00426 } 00427 00428 static DBusHashEntry* 00429 alloc_entry (DBusHashTable *table) 00430 { 00431 DBusHashEntry *entry; 00432 00433 entry = _dbus_mem_pool_alloc (table->entry_pool); 00434 00435 return entry; 00436 } 00437 00438 static void 00439 free_entry_data (DBusHashTable *table, 00440 DBusHashEntry *entry) 00441 { 00442 if (table->free_key_function) 00443 (* table->free_key_function) (entry->key); 00444 if (table->free_value_function) 00445 (* table->free_value_function) (entry->value); 00446 } 00447 00448 static void 00449 free_entry (DBusHashTable *table, 00450 DBusHashEntry *entry) 00451 { 00452 free_entry_data (table, entry); 00453 _dbus_mem_pool_dealloc (table->entry_pool, entry); 00454 } 00455 00456 static void 00457 remove_entry (DBusHashTable *table, 00458 DBusHashEntry **bucket, 00459 DBusHashEntry *entry) 00460 { 00461 _dbus_assert (table != NULL); 00462 _dbus_assert (bucket != NULL); 00463 _dbus_assert (*bucket != NULL); 00464 _dbus_assert (entry != NULL); 00465 00466 if (*bucket == entry) 00467 *bucket = entry->next; 00468 else 00469 { 00470 DBusHashEntry *prev; 00471 prev = *bucket; 00472 00473 while (prev->next != entry) 00474 prev = prev->next; 00475 00476 _dbus_assert (prev != NULL); 00477 00478 prev->next = entry->next; 00479 } 00480 00481 table->n_entries -= 1; 00482 free_entry (table, entry); 00483 } 00484 00516 void 00517 _dbus_hash_iter_init (DBusHashTable *table, 00518 DBusHashIter *iter) 00519 { 00520 DBusRealHashIter *real; 00521 00522 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00523 00524 real = (DBusRealHashIter*) iter; 00525 00526 real->table = table; 00527 real->bucket = NULL; 00528 real->entry = NULL; 00529 real->next_entry = NULL; 00530 real->next_bucket = 0; 00531 real->n_entries_on_init = table->n_entries; 00532 } 00533 00542 dbus_bool_t 00543 _dbus_hash_iter_next (DBusHashIter *iter) 00544 { 00545 DBusRealHashIter *real; 00546 00547 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00548 00549 real = (DBusRealHashIter*) iter; 00550 00551 /* if this assertion failed someone probably added hash entries 00552 * during iteration, which is bad. 00553 */ 00554 _dbus_assert (real->n_entries_on_init >= real->table->n_entries); 00555 00556 /* Remember that real->entry may have been deleted */ 00557 00558 while (real->next_entry == NULL) 00559 { 00560 if (real->next_bucket >= real->table->n_buckets) 00561 { 00562 /* invalidate iter and return false */ 00563 real->entry = NULL; 00564 real->table = NULL; 00565 real->bucket = NULL; 00566 return FALSE; 00567 } 00568 00569 real->bucket = &(real->table->buckets[real->next_bucket]); 00570 real->next_entry = *(real->bucket); 00571 real->next_bucket += 1; 00572 } 00573 00574 _dbus_assert (real->next_entry != NULL); 00575 _dbus_assert (real->bucket != NULL); 00576 00577 real->entry = real->next_entry; 00578 real->next_entry = real->entry->next; 00579 00580 return TRUE; 00581 } 00582 00591 void 00592 _dbus_hash_iter_remove_entry (DBusHashIter *iter) 00593 { 00594 DBusRealHashIter *real; 00595 00596 real = (DBusRealHashIter*) iter; 00597 00598 _dbus_assert (real->table != NULL); 00599 _dbus_assert (real->entry != NULL); 00600 _dbus_assert (real->bucket != NULL); 00601 00602 remove_entry (real->table, real->bucket, real->entry); 00603 00604 real->entry = NULL; /* make it crash if you try to use this entry */ 00605 } 00606 00612 void* 00613 _dbus_hash_iter_get_value (DBusHashIter *iter) 00614 { 00615 DBusRealHashIter *real; 00616 00617 real = (DBusRealHashIter*) iter; 00618 00619 _dbus_assert (real->table != NULL); 00620 _dbus_assert (real->entry != NULL); 00621 00622 return real->entry->value; 00623 } 00624 00635 void 00636 _dbus_hash_iter_set_value (DBusHashIter *iter, 00637 void *value) 00638 { 00639 DBusRealHashIter *real; 00640 00641 real = (DBusRealHashIter*) iter; 00642 00643 _dbus_assert (real->table != NULL); 00644 _dbus_assert (real->entry != NULL); 00645 00646 if (real->table->free_value_function && value != real->entry->value) 00647 (* real->table->free_value_function) (real->entry->value); 00648 00649 real->entry->value = value; 00650 } 00651 00658 int 00659 _dbus_hash_iter_get_int_key (DBusHashIter *iter) 00660 { 00661 DBusRealHashIter *real; 00662 00663 real = (DBusRealHashIter*) iter; 00664 00665 _dbus_assert (real->table != NULL); 00666 _dbus_assert (real->entry != NULL); 00667 00668 return _DBUS_POINTER_TO_INT (real->entry->key); 00669 } 00670 00677 uintptr_t 00678 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter) 00679 { 00680 DBusRealHashIter *real; 00681 00682 real = (DBusRealHashIter*) iter; 00683 00684 _dbus_assert (real->table != NULL); 00685 _dbus_assert (real->entry != NULL); 00686 00687 return (uintptr_t) real->entry->key; 00688 } 00689 00695 const char* 00696 _dbus_hash_iter_get_string_key (DBusHashIter *iter) 00697 { 00698 DBusRealHashIter *real; 00699 00700 real = (DBusRealHashIter*) iter; 00701 00702 _dbus_assert (real->table != NULL); 00703 _dbus_assert (real->entry != NULL); 00704 00705 return real->entry->key; 00706 } 00707 00739 dbus_bool_t 00740 _dbus_hash_iter_lookup (DBusHashTable *table, 00741 void *key, 00742 dbus_bool_t create_if_not_found, 00743 DBusHashIter *iter) 00744 { 00745 DBusRealHashIter *real; 00746 DBusHashEntry *entry; 00747 DBusHashEntry **bucket; 00748 00749 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter)); 00750 00751 real = (DBusRealHashIter*) iter; 00752 00753 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL); 00754 00755 if (entry == NULL) 00756 return FALSE; 00757 00758 real->table = table; 00759 real->bucket = bucket; 00760 real->entry = entry; 00761 real->next_entry = entry->next; 00762 real->next_bucket = (bucket - table->buckets) + 1; 00763 real->n_entries_on_init = table->n_entries; 00764 00765 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket); 00766 00767 return TRUE; 00768 } 00769 00770 static void 00771 add_allocated_entry (DBusHashTable *table, 00772 DBusHashEntry *entry, 00773 unsigned int idx, 00774 void *key, 00775 DBusHashEntry ***bucket) 00776 { 00777 DBusHashEntry **b; 00778 00779 entry->key = key; 00780 00781 b = &(table->buckets[idx]); 00782 entry->next = *b; 00783 *b = entry; 00784 00785 if (bucket) 00786 *bucket = b; 00787 00788 table->n_entries += 1; 00789 00790 /* note we ONLY rebuild when ADDING - because you can iterate over a 00791 * table and remove entries safely. 00792 */ 00793 if (table->n_entries >= table->hi_rebuild_size || 00794 table->n_entries < table->lo_rebuild_size) 00795 rebuild_table (table); 00796 } 00797 00798 static DBusHashEntry* 00799 add_entry (DBusHashTable *table, 00800 unsigned int idx, 00801 void *key, 00802 DBusHashEntry ***bucket, 00803 DBusPreallocatedHash *preallocated) 00804 { 00805 DBusHashEntry *entry; 00806 00807 if (preallocated == NULL) 00808 { 00809 entry = alloc_entry (table); 00810 if (entry == NULL) 00811 { 00812 if (bucket) 00813 *bucket = NULL; 00814 return NULL; 00815 } 00816 } 00817 else 00818 { 00819 entry = (DBusHashEntry*) preallocated; 00820 } 00821 00822 add_allocated_entry (table, entry, idx, key, bucket); 00823 00824 return entry; 00825 } 00826 00827 /* This is g_str_hash from GLib which was 00828 * extensively discussed/tested/profiled 00829 */ 00830 static unsigned int 00831 string_hash (const char *str) 00832 { 00833 const char *p = str; 00834 unsigned int h = *p; 00835 00836 if (h) 00837 for (p += 1; *p != '\0'; p++) 00838 h = (h << 5) - h + *p; 00839 00840 return h; 00841 } 00842 00844 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b); 00845 00846 static DBusHashEntry* 00847 find_generic_function (DBusHashTable *table, 00848 void *key, 00849 unsigned int idx, 00850 KeyCompareFunc compare_func, 00851 dbus_bool_t create_if_not_found, 00852 DBusHashEntry ***bucket, 00853 DBusPreallocatedHash *preallocated) 00854 { 00855 DBusHashEntry *entry; 00856 00857 if (bucket) 00858 *bucket = NULL; 00859 00860 /* Search all of the entries in this bucket. */ 00861 entry = table->buckets[idx]; 00862 while (entry != NULL) 00863 { 00864 if ((compare_func == NULL && key == entry->key) || 00865 (compare_func != NULL && (* compare_func) (key, entry->key) == 0)) 00866 { 00867 if (bucket) 00868 *bucket = &(table->buckets[idx]); 00869 00870 if (preallocated) 00871 _dbus_hash_table_free_preallocated_entry (table, preallocated); 00872 00873 return entry; 00874 } 00875 00876 entry = entry->next; 00877 } 00878 00879 if (create_if_not_found) 00880 entry = add_entry (table, idx, key, bucket, preallocated); 00881 else if (preallocated) 00882 _dbus_hash_table_free_preallocated_entry (table, preallocated); 00883 00884 return entry; 00885 } 00886 00887 static DBusHashEntry* 00888 find_string_function (DBusHashTable *table, 00889 void *key, 00890 dbus_bool_t create_if_not_found, 00891 DBusHashEntry ***bucket, 00892 DBusPreallocatedHash *preallocated) 00893 { 00894 unsigned int idx; 00895 00896 idx = string_hash (key) & table->mask; 00897 00898 return find_generic_function (table, key, idx, 00899 (KeyCompareFunc) strcmp, create_if_not_found, bucket, 00900 preallocated); 00901 } 00902 00903 static DBusHashEntry* 00904 find_direct_function (DBusHashTable *table, 00905 void *key, 00906 dbus_bool_t create_if_not_found, 00907 DBusHashEntry ***bucket, 00908 DBusPreallocatedHash *preallocated) 00909 { 00910 unsigned int idx; 00911 00912 idx = RANDOM_INDEX (table, key) & table->mask; 00913 00914 00915 return find_generic_function (table, key, idx, 00916 NULL, create_if_not_found, bucket, 00917 preallocated); 00918 } 00919 00920 static void 00921 rebuild_table (DBusHashTable *table) 00922 { 00923 int old_size; 00924 int new_buckets; 00925 DBusHashEntry **old_buckets; 00926 DBusHashEntry **old_chain; 00927 DBusHashEntry *entry; 00928 dbus_bool_t growing; 00929 00930 /* 00931 * Allocate and initialize the new bucket array, and set up 00932 * hashing constants for new array size. 00933 */ 00934 00935 growing = table->n_entries >= table->hi_rebuild_size; 00936 00937 old_size = table->n_buckets; 00938 old_buckets = table->buckets; 00939 00940 if (growing) 00941 { 00942 /* overflow paranoia */ 00943 if (table->n_buckets < _DBUS_INT_MAX / 4 && 00944 table->down_shift >= 0) 00945 new_buckets = table->n_buckets * 4; 00946 else 00947 return; /* can't grow anymore */ 00948 } 00949 else 00950 { 00951 new_buckets = table->n_buckets / 4; 00952 if (new_buckets < DBUS_SMALL_HASH_TABLE) 00953 return; /* don't bother shrinking this far */ 00954 } 00955 00956 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets); 00957 if (table->buckets == NULL) 00958 { 00959 /* out of memory, yay - just don't reallocate, the table will 00960 * still work, albeit more slowly. 00961 */ 00962 table->buckets = old_buckets; 00963 return; 00964 } 00965 00966 table->n_buckets = new_buckets; 00967 00968 if (growing) 00969 { 00970 table->lo_rebuild_size = table->hi_rebuild_size; 00971 table->hi_rebuild_size *= 4; 00972 00973 table->down_shift -= 2; /* keep 2 more high bits */ 00974 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */ 00975 } 00976 else 00977 { 00978 table->hi_rebuild_size = table->lo_rebuild_size; 00979 table->lo_rebuild_size /= 4; 00980 00981 table->down_shift += 2; /* keep 2 fewer high bits */ 00982 table->mask = table->mask >> 2; /* keep 2 fewer high bits */ 00983 } 00984 00985 #if 0 00986 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", 00987 growing ? "GROW" : "SHRINK", 00988 table->lo_rebuild_size, 00989 table->hi_rebuild_size, 00990 table->down_shift, 00991 table->mask); 00992 #endif 00993 00994 _dbus_assert (table->lo_rebuild_size >= 0); 00995 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size); 00996 _dbus_assert (table->mask != 0); 00997 /* the mask is essentially the max index */ 00998 _dbus_assert (table->mask < table->n_buckets); 00999 01000 /* 01001 * Rehash all of the existing entries into the new bucket array. 01002 */ 01003 01004 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++) 01005 { 01006 for (entry = *old_chain; entry != NULL; entry = *old_chain) 01007 { 01008 unsigned int idx; 01009 DBusHashEntry **bucket; 01010 01011 *old_chain = entry->next; 01012 switch (table->key_type) 01013 { 01014 case DBUS_HASH_STRING: 01015 idx = string_hash (entry->key) & table->mask; 01016 break; 01017 case DBUS_HASH_INT: 01018 case DBUS_HASH_UINTPTR: 01019 idx = RANDOM_INDEX (table, entry->key); 01020 break; 01021 default: 01022 idx = 0; 01023 _dbus_assert_not_reached ("Unknown hash table type"); 01024 break; 01025 } 01026 01027 bucket = &(table->buckets[idx]); 01028 entry->next = *bucket; 01029 *bucket = entry; 01030 } 01031 } 01032 01033 /* Free the old bucket array, if it was dynamically allocated. */ 01034 01035 if (old_buckets != table->static_buckets) 01036 dbus_free (old_buckets); 01037 } 01038 01048 void* 01049 _dbus_hash_table_lookup_string (DBusHashTable *table, 01050 const char *key) 01051 { 01052 DBusHashEntry *entry; 01053 01054 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01055 01056 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL); 01057 01058 if (entry) 01059 return entry->value; 01060 else 01061 return NULL; 01062 } 01063 01073 void* 01074 _dbus_hash_table_lookup_int (DBusHashTable *table, 01075 int key) 01076 { 01077 DBusHashEntry *entry; 01078 01079 _dbus_assert (table->key_type == DBUS_HASH_INT); 01080 01081 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL); 01082 01083 if (entry) 01084 return entry->value; 01085 else 01086 return NULL; 01087 } 01088 01098 void* 01099 _dbus_hash_table_lookup_uintptr (DBusHashTable *table, 01100 uintptr_t key) 01101 { 01102 DBusHashEntry *entry; 01103 01104 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01105 01106 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL); 01107 01108 if (entry) 01109 return entry->value; 01110 else 01111 return NULL; 01112 } 01113 01122 dbus_bool_t 01123 _dbus_hash_table_remove_string (DBusHashTable *table, 01124 const char *key) 01125 { 01126 DBusHashEntry *entry; 01127 DBusHashEntry **bucket; 01128 01129 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01130 01131 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL); 01132 01133 if (entry) 01134 { 01135 remove_entry (table, bucket, entry); 01136 return TRUE; 01137 } 01138 else 01139 return FALSE; 01140 } 01141 01150 dbus_bool_t 01151 _dbus_hash_table_remove_int (DBusHashTable *table, 01152 int key) 01153 { 01154 DBusHashEntry *entry; 01155 DBusHashEntry **bucket; 01156 01157 _dbus_assert (table->key_type == DBUS_HASH_INT); 01158 01159 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL); 01160 01161 if (entry) 01162 { 01163 remove_entry (table, bucket, entry); 01164 return TRUE; 01165 } 01166 else 01167 return FALSE; 01168 } 01169 01178 dbus_bool_t 01179 _dbus_hash_table_remove_uintptr (DBusHashTable *table, 01180 uintptr_t key) 01181 { 01182 DBusHashEntry *entry; 01183 DBusHashEntry **bucket; 01184 01185 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01186 01187 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL); 01188 01189 if (entry) 01190 { 01191 remove_entry (table, bucket, entry); 01192 return TRUE; 01193 } 01194 else 01195 return FALSE; 01196 } 01197 01213 dbus_bool_t 01214 _dbus_hash_table_insert_string (DBusHashTable *table, 01215 char *key, 01216 void *value) 01217 { 01218 DBusPreallocatedHash *preallocated; 01219 01220 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01221 01222 preallocated = _dbus_hash_table_preallocate_entry (table); 01223 if (preallocated == NULL) 01224 return FALSE; 01225 01226 _dbus_hash_table_insert_string_preallocated (table, preallocated, 01227 key, value); 01228 01229 return TRUE; 01230 } 01231 01247 dbus_bool_t 01248 _dbus_hash_table_insert_int (DBusHashTable *table, 01249 int key, 01250 void *value) 01251 { 01252 DBusHashEntry *entry; 01253 01254 _dbus_assert (table->key_type == DBUS_HASH_INT); 01255 01256 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL); 01257 01258 if (entry == NULL) 01259 return FALSE; /* no memory */ 01260 01261 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key)) 01262 (* table->free_key_function) (entry->key); 01263 01264 if (table->free_value_function && entry->value != value) 01265 (* table->free_value_function) (entry->value); 01266 01267 entry->key = _DBUS_INT_TO_POINTER (key); 01268 entry->value = value; 01269 01270 return TRUE; 01271 } 01272 01288 dbus_bool_t 01289 _dbus_hash_table_insert_uintptr (DBusHashTable *table, 01290 uintptr_t key, 01291 void *value) 01292 { 01293 DBusHashEntry *entry; 01294 01295 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR); 01296 01297 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL); 01298 01299 if (entry == NULL) 01300 return FALSE; /* no memory */ 01301 01302 if (table->free_key_function && entry->key != (void*) key) 01303 (* table->free_key_function) (entry->key); 01304 01305 if (table->free_value_function && entry->value != value) 01306 (* table->free_value_function) (entry->value); 01307 01308 entry->key = (void*) key; 01309 entry->value = value; 01310 01311 return TRUE; 01312 } 01313 01321 DBusPreallocatedHash* 01322 _dbus_hash_table_preallocate_entry (DBusHashTable *table) 01323 { 01324 DBusHashEntry *entry; 01325 01326 entry = alloc_entry (table); 01327 01328 return (DBusPreallocatedHash*) entry; 01329 } 01330 01338 void 01339 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table, 01340 DBusPreallocatedHash *preallocated) 01341 { 01342 DBusHashEntry *entry; 01343 01344 _dbus_assert (preallocated != NULL); 01345 01346 entry = (DBusHashEntry*) preallocated; 01347 01348 /* Don't use free_entry(), since this entry has no key/data */ 01349 _dbus_mem_pool_dealloc (table->entry_pool, entry); 01350 } 01351 01365 void 01366 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table, 01367 DBusPreallocatedHash *preallocated, 01368 char *key, 01369 void *value) 01370 { 01371 DBusHashEntry *entry; 01372 01373 _dbus_assert (table->key_type == DBUS_HASH_STRING); 01374 _dbus_assert (preallocated != NULL); 01375 01376 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated); 01377 01378 _dbus_assert (entry != NULL); 01379 01380 if (table->free_key_function && entry->key != key) 01381 (* table->free_key_function) (entry->key); 01382 01383 if (table->free_value_function && entry->value != value) 01384 (* table->free_value_function) (entry->value); 01385 01386 entry->key = key; 01387 entry->value = value; 01388 } 01389 01396 int 01397 _dbus_hash_table_get_n_entries (DBusHashTable *table) 01398 { 01399 return table->n_entries; 01400 } 01401 01404 #ifdef DBUS_BUILD_TESTS 01405 #include "dbus-test.h" 01406 #include <stdio.h> 01407 01408 /* If you're wondering why the hash table test takes 01409 * forever to run, it's because we call this function 01410 * in inner loops thus making things quadratic. 01411 */ 01412 static int 01413 count_entries (DBusHashTable *table) 01414 { 01415 DBusHashIter iter; 01416 int count; 01417 01418 count = 0; 01419 _dbus_hash_iter_init (table, &iter); 01420 while (_dbus_hash_iter_next (&iter)) 01421 ++count; 01422 01423 _dbus_assert (count == _dbus_hash_table_get_n_entries (table)); 01424 01425 return count; 01426 } 01427 01433 dbus_bool_t 01434 _dbus_hash_test (void) 01435 { 01436 int i; 01437 DBusHashTable *table1; 01438 DBusHashTable *table2; 01439 DBusHashTable *table3; 01440 DBusHashIter iter; 01441 #define N_HASH_KEYS 5000 01442 char **keys; 01443 dbus_bool_t ret = FALSE; 01444 01445 keys = dbus_new (char *, N_HASH_KEYS); 01446 if (keys == NULL) 01447 _dbus_assert_not_reached ("no memory"); 01448 01449 for (i = 0; i < N_HASH_KEYS; i++) 01450 { 01451 keys[i] = dbus_malloc (128); 01452 01453 if (keys[i] == NULL) 01454 _dbus_assert_not_reached ("no memory"); 01455 } 01456 01457 printf ("Computing test hash keys...\n"); 01458 i = 0; 01459 while (i < N_HASH_KEYS) 01460 { 01461 int len; 01462 01463 len = sprintf (keys[i], "Hash key %d", i); 01464 _dbus_assert (*(keys[i] + len) == '\0'); 01465 ++i; 01466 } 01467 printf ("... done.\n"); 01468 01469 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01470 dbus_free, dbus_free); 01471 if (table1 == NULL) 01472 goto out; 01473 01474 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01475 NULL, dbus_free); 01476 if (table2 == NULL) 01477 goto out; 01478 01479 table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR, 01480 NULL, dbus_free); 01481 if (table3 == NULL) 01482 goto out; 01483 01484 /* Insert and remove a bunch of stuff, counting the table in between 01485 * to be sure it's not broken and that iteration works 01486 */ 01487 i = 0; 01488 while (i < 3000) 01489 { 01490 void *value; 01491 char *key; 01492 01493 key = _dbus_strdup (keys[i]); 01494 if (key == NULL) 01495 goto out; 01496 value = _dbus_strdup ("Value!"); 01497 if (value == NULL) 01498 goto out; 01499 01500 if (!_dbus_hash_table_insert_string (table1, 01501 key, value)) 01502 goto out; 01503 01504 value = _dbus_strdup (keys[i]); 01505 if (value == NULL) 01506 goto out; 01507 01508 if (!_dbus_hash_table_insert_int (table2, 01509 i, value)) 01510 goto out; 01511 01512 value = _dbus_strdup (keys[i]); 01513 if (value == NULL) 01514 goto out; 01515 01516 if (!_dbus_hash_table_insert_uintptr (table3, 01517 i, value)) 01518 goto out; 01519 01520 _dbus_assert (count_entries (table1) == i + 1); 01521 _dbus_assert (count_entries (table2) == i + 1); 01522 _dbus_assert (count_entries (table3) == i + 1); 01523 01524 value = _dbus_hash_table_lookup_string (table1, keys[i]); 01525 _dbus_assert (value != NULL); 01526 _dbus_assert (strcmp (value, "Value!") == 0); 01527 01528 value = _dbus_hash_table_lookup_int (table2, i); 01529 _dbus_assert (value != NULL); 01530 _dbus_assert (strcmp (value, keys[i]) == 0); 01531 01532 value = _dbus_hash_table_lookup_uintptr (table3, i); 01533 _dbus_assert (value != NULL); 01534 _dbus_assert (strcmp (value, keys[i]) == 0); 01535 01536 ++i; 01537 } 01538 01539 --i; 01540 while (i >= 0) 01541 { 01542 _dbus_hash_table_remove_string (table1, 01543 keys[i]); 01544 01545 _dbus_hash_table_remove_int (table2, i); 01546 01547 _dbus_hash_table_remove_uintptr (table3, i); 01548 01549 _dbus_assert (count_entries (table1) == i); 01550 _dbus_assert (count_entries (table2) == i); 01551 _dbus_assert (count_entries (table3) == i); 01552 01553 --i; 01554 } 01555 01556 _dbus_hash_table_ref (table1); 01557 _dbus_hash_table_ref (table2); 01558 _dbus_hash_table_ref (table3); 01559 _dbus_hash_table_unref (table1); 01560 _dbus_hash_table_unref (table2); 01561 _dbus_hash_table_unref (table3); 01562 _dbus_hash_table_unref (table1); 01563 _dbus_hash_table_unref (table2); 01564 _dbus_hash_table_unref (table3); 01565 table3 = NULL; 01566 01567 /* Insert a bunch of stuff then check 01568 * that iteration works correctly (finds the right 01569 * values, iter_set_value works, etc.) 01570 */ 01571 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01572 dbus_free, dbus_free); 01573 if (table1 == NULL) 01574 goto out; 01575 01576 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01577 NULL, dbus_free); 01578 if (table2 == NULL) 01579 goto out; 01580 01581 i = 0; 01582 while (i < 5000) 01583 { 01584 char *key; 01585 void *value; 01586 01587 key = _dbus_strdup (keys[i]); 01588 if (key == NULL) 01589 goto out; 01590 value = _dbus_strdup ("Value!"); 01591 if (value == NULL) 01592 goto out; 01593 01594 if (!_dbus_hash_table_insert_string (table1, 01595 key, value)) 01596 goto out; 01597 01598 value = _dbus_strdup (keys[i]); 01599 if (value == NULL) 01600 goto out; 01601 01602 if (!_dbus_hash_table_insert_int (table2, 01603 i, value)) 01604 goto out; 01605 01606 _dbus_assert (count_entries (table1) == i + 1); 01607 _dbus_assert (count_entries (table2) == i + 1); 01608 01609 ++i; 01610 } 01611 01612 _dbus_hash_iter_init (table1, &iter); 01613 while (_dbus_hash_iter_next (&iter)) 01614 { 01615 const char *key; 01616 void *value; 01617 01618 key = _dbus_hash_iter_get_string_key (&iter); 01619 value = _dbus_hash_iter_get_value (&iter); 01620 01621 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 01622 01623 value = _dbus_strdup ("Different value!"); 01624 if (value == NULL) 01625 goto out; 01626 01627 _dbus_hash_iter_set_value (&iter, value); 01628 01629 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value); 01630 } 01631 01632 _dbus_hash_iter_init (table1, &iter); 01633 while (_dbus_hash_iter_next (&iter)) 01634 { 01635 _dbus_hash_iter_remove_entry (&iter); 01636 _dbus_assert (count_entries (table1) == i - 1); 01637 --i; 01638 } 01639 01640 _dbus_hash_iter_init (table2, &iter); 01641 while (_dbus_hash_iter_next (&iter)) 01642 { 01643 int key; 01644 void *value; 01645 01646 key = _dbus_hash_iter_get_int_key (&iter); 01647 value = _dbus_hash_iter_get_value (&iter); 01648 01649 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 01650 01651 value = _dbus_strdup ("Different value!"); 01652 if (value == NULL) 01653 goto out; 01654 01655 _dbus_hash_iter_set_value (&iter, value); 01656 01657 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value); 01658 } 01659 01660 i = count_entries (table2); 01661 _dbus_hash_iter_init (table2, &iter); 01662 while (_dbus_hash_iter_next (&iter)) 01663 { 01664 _dbus_hash_iter_remove_entry (&iter); 01665 _dbus_assert (count_entries (table2) + 1 == i); 01666 --i; 01667 } 01668 01669 /* add/remove interleaved, to check that we grow/shrink the table 01670 * appropriately 01671 */ 01672 i = 0; 01673 while (i < 1000) 01674 { 01675 char *key; 01676 void *value; 01677 01678 key = _dbus_strdup (keys[i]); 01679 if (key == NULL) 01680 goto out; 01681 01682 value = _dbus_strdup ("Value!"); 01683 if (value == NULL) 01684 goto out; 01685 01686 if (!_dbus_hash_table_insert_string (table1, 01687 key, value)) 01688 goto out; 01689 01690 ++i; 01691 } 01692 01693 --i; 01694 while (i >= 0) 01695 { 01696 char *key; 01697 void *value; 01698 01699 key = _dbus_strdup (keys[i]); 01700 if (key == NULL) 01701 goto out; 01702 value = _dbus_strdup ("Value!"); 01703 if (value == NULL) 01704 goto out; 01705 01706 if (!_dbus_hash_table_remove_string (table1, keys[i])) 01707 goto out; 01708 01709 if (!_dbus_hash_table_insert_string (table1, 01710 key, value)) 01711 goto out; 01712 01713 if (!_dbus_hash_table_remove_string (table1, keys[i])) 01714 goto out; 01715 01716 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i); 01717 01718 --i; 01719 } 01720 01721 /* nuke these tables */ 01722 _dbus_hash_table_unref (table1); 01723 _dbus_hash_table_unref (table2); 01724 01725 01726 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to 01727 * be sure that interface works. 01728 */ 01729 table1 = _dbus_hash_table_new (DBUS_HASH_STRING, 01730 dbus_free, dbus_free); 01731 if (table1 == NULL) 01732 goto out; 01733 01734 table2 = _dbus_hash_table_new (DBUS_HASH_INT, 01735 NULL, dbus_free); 01736 if (table2 == NULL) 01737 goto out; 01738 01739 i = 0; 01740 while (i < 3000) 01741 { 01742 void *value; 01743 char *key; 01744 01745 key = _dbus_strdup (keys[i]); 01746 if (key == NULL) 01747 goto out; 01748 value = _dbus_strdup ("Value!"); 01749 if (value == NULL) 01750 goto out; 01751 01752 if (!_dbus_hash_iter_lookup (table1, 01753 key, TRUE, &iter)) 01754 goto out; 01755 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 01756 _dbus_hash_iter_set_value (&iter, value); 01757 01758 value = _dbus_strdup (keys[i]); 01759 if (value == NULL) 01760 goto out; 01761 01762 if (!_dbus_hash_iter_lookup (table2, 01763 _DBUS_INT_TO_POINTER (i), TRUE, &iter)) 01764 goto out; 01765 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL); 01766 _dbus_hash_iter_set_value (&iter, value); 01767 01768 _dbus_assert (count_entries (table1) == i + 1); 01769 _dbus_assert (count_entries (table2) == i + 1); 01770 01771 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 01772 goto out; 01773 01774 value = _dbus_hash_iter_get_value (&iter); 01775 _dbus_assert (value != NULL); 01776 _dbus_assert (strcmp (value, "Value!") == 0); 01777 01778 /* Iterate just to be sure it works, though 01779 * it's a stupid thing to do 01780 */ 01781 while (_dbus_hash_iter_next (&iter)) 01782 ; 01783 01784 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 01785 goto out; 01786 01787 value = _dbus_hash_iter_get_value (&iter); 01788 _dbus_assert (value != NULL); 01789 _dbus_assert (strcmp (value, keys[i]) == 0); 01790 01791 /* Iterate just to be sure it works, though 01792 * it's a stupid thing to do 01793 */ 01794 while (_dbus_hash_iter_next (&iter)) 01795 ; 01796 01797 ++i; 01798 } 01799 01800 --i; 01801 while (i >= 0) 01802 { 01803 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter)) 01804 _dbus_assert_not_reached ("hash entry should have existed"); 01805 _dbus_hash_iter_remove_entry (&iter); 01806 01807 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter)) 01808 _dbus_assert_not_reached ("hash entry should have existed"); 01809 _dbus_hash_iter_remove_entry (&iter); 01810 01811 _dbus_assert (count_entries (table1) == i); 01812 _dbus_assert (count_entries (table2) == i); 01813 01814 --i; 01815 } 01816 01817 _dbus_hash_table_unref (table1); 01818 _dbus_hash_table_unref (table2); 01819 01820 ret = TRUE; 01821 01822 out: 01823 for (i = 0; i < N_HASH_KEYS; i++) 01824 dbus_free (keys[i]); 01825 01826 dbus_free (keys); 01827 01828 return ret; 01829 } 01830 01831 #endif /* DBUS_BUILD_TESTS */