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