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 "dbus-hash.h"
00078 #include "dbus-internals.h"
00079 #include "dbus-mempool.h"
00080
00103 #define REBUILD_MULTIPLIER 3
00104
00121 #define RANDOM_INDEX(table, i) \
00122 (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
00123
00129 #define DBUS_SMALL_HASH_TABLE 4
00130
00134 typedef struct DBusHashEntry DBusHashEntry;
00135
00142 struct DBusHashEntry
00143 {
00144 DBusHashEntry *next;
00148 void *key;
00149 void *value;
00150 };
00151
00155 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
00156 void *key,
00157 dbus_bool_t create_if_not_found,
00158 DBusHashEntry ***bucket,
00159 DBusPreallocatedHash *preallocated);
00160
00167 struct DBusHashTable {
00168 int refcount;
00170 DBusHashEntry **buckets;
00174 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
00178 int n_buckets;
00181 int n_entries;
00184 int hi_rebuild_size;
00187 int lo_rebuild_size;
00190 int down_shift;
00194 int mask;
00197 DBusHashType key_type;
00200 DBusFindEntryFunction find_function;
00202 DBusFreeFunction free_key_function;
00203 DBusFreeFunction free_value_function;
00205 DBusMemPool *entry_pool;
00206 };
00207
00211 typedef struct
00212 {
00213 DBusHashTable *table;
00214 DBusHashEntry **bucket;
00218 DBusHashEntry *entry;
00219 DBusHashEntry *next_entry;
00220 int next_bucket;
00221 int n_entries_on_init;
00222 } DBusRealHashIter;
00223
00224 static DBusHashEntry* find_direct_function (DBusHashTable *table,
00225 void *key,
00226 dbus_bool_t create_if_not_found,
00227 DBusHashEntry ***bucket,
00228 DBusPreallocatedHash *preallocated);
00229 static DBusHashEntry* find_string_function (DBusHashTable *table,
00230 void *key,
00231 dbus_bool_t create_if_not_found,
00232 DBusHashEntry ***bucket,
00233 DBusPreallocatedHash *preallocated);
00234 #ifdef DBUS_BUILD_TESTS
00235 static DBusHashEntry* find_two_strings_function (DBusHashTable *table,
00236 void *key,
00237 dbus_bool_t create_if_not_found,
00238 DBusHashEntry ***bucket,
00239 DBusPreallocatedHash *preallocated);
00240 #endif
00241 static unsigned int string_hash (const char *str);
00242 #ifdef DBUS_BUILD_TESTS
00243 static unsigned int two_strings_hash (const char *str);
00244 #endif
00245 static void rebuild_table (DBusHashTable *table);
00246 static DBusHashEntry* alloc_entry (DBusHashTable *table);
00247 static void remove_entry (DBusHashTable *table,
00248 DBusHashEntry **bucket,
00249 DBusHashEntry *entry);
00250 static void free_entry (DBusHashTable *table,
00251 DBusHashEntry *entry);
00252 static void free_entry_data (DBusHashTable *table,
00253 DBusHashEntry *entry);
00254
00255
00291 DBusHashTable*
00292 _dbus_hash_table_new (DBusHashType type,
00293 DBusFreeFunction key_free_function,
00294 DBusFreeFunction value_free_function)
00295 {
00296 DBusHashTable *table;
00297 DBusMemPool *entry_pool;
00298
00299 table = dbus_new0 (DBusHashTable, 1);
00300 if (table == NULL)
00301 return NULL;
00302
00303 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00304 if (entry_pool == NULL)
00305 {
00306 dbus_free (table);
00307 return NULL;
00308 }
00309
00310 table->refcount = 1;
00311 table->entry_pool = entry_pool;
00312
00313 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00314
00315 table->buckets = table->static_buckets;
00316 table->n_buckets = DBUS_SMALL_HASH_TABLE;
00317 table->n_entries = 0;
00318 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00319 table->lo_rebuild_size = 0;
00320 table->down_shift = 28;
00321 table->mask = 3;
00322 table->key_type = type;
00323
00324 _dbus_assert (table->mask < table->n_buckets);
00325
00326 switch (table->key_type)
00327 {
00328 case DBUS_HASH_INT:
00329 case DBUS_HASH_POINTER:
00330 case DBUS_HASH_ULONG:
00331 table->find_function = find_direct_function;
00332 break;
00333 case DBUS_HASH_STRING:
00334 table->find_function = find_string_function;
00335 break;
00336 case DBUS_HASH_TWO_STRINGS:
00337 #ifdef DBUS_BUILD_TESTS
00338 table->find_function = find_two_strings_function;
00339 #endif
00340 break;
00341 default:
00342 _dbus_assert_not_reached ("Unknown hash table type");
00343 break;
00344 }
00345
00346 table->free_key_function = key_free_function;
00347 table->free_value_function = value_free_function;
00348
00349 return table;
00350 }
00351
00352
00359 DBusHashTable *
00360 _dbus_hash_table_ref (DBusHashTable *table)
00361 {
00362 table->refcount += 1;
00363
00364 return table;
00365 }
00366
00373 void
00374 _dbus_hash_table_unref (DBusHashTable *table)
00375 {
00376 table->refcount -= 1;
00377
00378 if (table->refcount == 0)
00379 {
00380 #if 0
00381 DBusHashEntry *entry;
00382 DBusHashEntry *next;
00383 int i;
00384
00385
00386 for (i = 0; i < table->n_buckets; i++)
00387 {
00388 entry = table->buckets[i];
00389 while (entry != NULL)
00390 {
00391 next = entry->next;
00392
00393 free_entry (table, entry);
00394
00395 entry = next;
00396 }
00397 }
00398 #else
00399 DBusHashEntry *entry;
00400 int i;
00401
00402
00403 for (i = 0; i < table->n_buckets; i++)
00404 {
00405 entry = table->buckets[i];
00406 while (entry != NULL)
00407 {
00408 free_entry_data (table, entry);
00409
00410 entry = entry->next;
00411 }
00412 }
00413
00414 _dbus_mem_pool_free (table->entry_pool);
00415 #endif
00416
00417
00418 if (table->buckets != table->static_buckets)
00419 dbus_free (table->buckets);
00420
00421 dbus_free (table);
00422 }
00423 }
00424
00425 static DBusHashEntry*
00426 alloc_entry (DBusHashTable *table)
00427 {
00428 DBusHashEntry *entry;
00429
00430 entry = _dbus_mem_pool_alloc (table->entry_pool);
00431
00432 return entry;
00433 }
00434
00435 static void
00436 free_entry_data (DBusHashTable *table,
00437 DBusHashEntry *entry)
00438 {
00439 if (table->free_key_function)
00440 (* table->free_key_function) (entry->key);
00441 if (table->free_value_function)
00442 (* table->free_value_function) (entry->value);
00443 }
00444
00445 static void
00446 free_entry (DBusHashTable *table,
00447 DBusHashEntry *entry)
00448 {
00449 free_entry_data (table, entry);
00450 _dbus_mem_pool_dealloc (table->entry_pool, entry);
00451 }
00452
00453 static void
00454 remove_entry (DBusHashTable *table,
00455 DBusHashEntry **bucket,
00456 DBusHashEntry *entry)
00457 {
00458 _dbus_assert (table != NULL);
00459 _dbus_assert (bucket != NULL);
00460 _dbus_assert (*bucket != NULL);
00461 _dbus_assert (entry != NULL);
00462
00463 if (*bucket == entry)
00464 *bucket = entry->next;
00465 else
00466 {
00467 DBusHashEntry *prev;
00468 prev = *bucket;
00469
00470 while (prev->next != entry)
00471 prev = prev->next;
00472
00473 _dbus_assert (prev != NULL);
00474
00475 prev->next = entry->next;
00476 }
00477
00478 table->n_entries -= 1;
00479 free_entry (table, entry);
00480 }
00481
00513 void
00514 _dbus_hash_iter_init (DBusHashTable *table,
00515 DBusHashIter *iter)
00516 {
00517 DBusRealHashIter *real;
00518
00519 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00520
00521 real = (DBusRealHashIter*) iter;
00522
00523 real->table = table;
00524 real->bucket = NULL;
00525 real->entry = NULL;
00526 real->next_entry = NULL;
00527 real->next_bucket = 0;
00528 real->n_entries_on_init = table->n_entries;
00529 }
00530
00539 dbus_bool_t
00540 _dbus_hash_iter_next (DBusHashIter *iter)
00541 {
00542 DBusRealHashIter *real;
00543
00544 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00545
00546 real = (DBusRealHashIter*) iter;
00547
00548
00549
00550
00551 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00552
00553
00554
00555 while (real->next_entry == NULL)
00556 {
00557 if (real->next_bucket >= real->table->n_buckets)
00558 {
00559
00560 real->entry = NULL;
00561 real->table = NULL;
00562 real->bucket = NULL;
00563 return FALSE;
00564 }
00565
00566 real->bucket = &(real->table->buckets[real->next_bucket]);
00567 real->next_entry = *(real->bucket);
00568 real->next_bucket += 1;
00569 }
00570
00571 _dbus_assert (real->next_entry != NULL);
00572 _dbus_assert (real->bucket != NULL);
00573
00574 real->entry = real->next_entry;
00575 real->next_entry = real->entry->next;
00576
00577 return TRUE;
00578 }
00579
00588 void
00589 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00590 {
00591 DBusRealHashIter *real;
00592
00593 real = (DBusRealHashIter*) iter;
00594
00595 _dbus_assert (real->table != NULL);
00596 _dbus_assert (real->entry != NULL);
00597 _dbus_assert (real->bucket != NULL);
00598
00599 remove_entry (real->table, real->bucket, real->entry);
00600
00601 real->entry = NULL;
00602 }
00603
00609 void*
00610 _dbus_hash_iter_get_value (DBusHashIter *iter)
00611 {
00612 DBusRealHashIter *real;
00613
00614 real = (DBusRealHashIter*) iter;
00615
00616 _dbus_assert (real->table != NULL);
00617 _dbus_assert (real->entry != NULL);
00618
00619 return real->entry->value;
00620 }
00621
00632 void
00633 _dbus_hash_iter_set_value (DBusHashIter *iter,
00634 void *value)
00635 {
00636 DBusRealHashIter *real;
00637
00638 real = (DBusRealHashIter*) iter;
00639
00640 _dbus_assert (real->table != NULL);
00641 _dbus_assert (real->entry != NULL);
00642
00643 if (real->table->free_value_function && value != real->entry->value)
00644 (* real->table->free_value_function) (real->entry->value);
00645
00646 real->entry->value = value;
00647 }
00648
00655 int
00656 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00657 {
00658 DBusRealHashIter *real;
00659
00660 real = (DBusRealHashIter*) iter;
00661
00662 _dbus_assert (real->table != NULL);
00663 _dbus_assert (real->entry != NULL);
00664
00665 return _DBUS_POINTER_TO_INT (real->entry->key);
00666 }
00667
00674 unsigned long
00675 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
00676 {
00677 DBusRealHashIter *real;
00678
00679 real = (DBusRealHashIter*) iter;
00680
00681 _dbus_assert (real->table != NULL);
00682 _dbus_assert (real->entry != NULL);
00683
00684 return (unsigned long) real->entry->key;
00685 }
00686
00692 const char*
00693 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00694 {
00695 DBusRealHashIter *real;
00696
00697 real = (DBusRealHashIter*) iter;
00698
00699 _dbus_assert (real->table != NULL);
00700 _dbus_assert (real->entry != NULL);
00701
00702 return real->entry->key;
00703 }
00704
00705 #ifdef DBUS_BUILD_TESTS
00706
00711 const char*
00712 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
00713 {
00714 DBusRealHashIter *real;
00715
00716 real = (DBusRealHashIter*) iter;
00717
00718 _dbus_assert (real->table != NULL);
00719 _dbus_assert (real->entry != NULL);
00720
00721 return real->entry->key;
00722 }
00723 #endif
00724
00756 dbus_bool_t
00757 _dbus_hash_iter_lookup (DBusHashTable *table,
00758 void *key,
00759 dbus_bool_t create_if_not_found,
00760 DBusHashIter *iter)
00761 {
00762 DBusRealHashIter *real;
00763 DBusHashEntry *entry;
00764 DBusHashEntry **bucket;
00765
00766 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00767
00768 real = (DBusRealHashIter*) iter;
00769
00770 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00771
00772 if (entry == NULL)
00773 return FALSE;
00774
00775 real->table = table;
00776 real->bucket = bucket;
00777 real->entry = entry;
00778 real->next_entry = entry->next;
00779 real->next_bucket = (bucket - table->buckets) + 1;
00780 real->n_entries_on_init = table->n_entries;
00781
00782 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00783
00784 return TRUE;
00785 }
00786
00787 static void
00788 add_allocated_entry (DBusHashTable *table,
00789 DBusHashEntry *entry,
00790 unsigned int idx,
00791 void *key,
00792 DBusHashEntry ***bucket)
00793 {
00794 DBusHashEntry **b;
00795
00796 entry->key = key;
00797
00798 b = &(table->buckets[idx]);
00799 entry->next = *b;
00800 *b = entry;
00801
00802 if (bucket)
00803 *bucket = b;
00804
00805 table->n_entries += 1;
00806
00807
00808
00809
00810 if (table->n_entries >= table->hi_rebuild_size ||
00811 table->n_entries < table->lo_rebuild_size)
00812 rebuild_table (table);
00813 }
00814
00815 static DBusHashEntry*
00816 add_entry (DBusHashTable *table,
00817 unsigned int idx,
00818 void *key,
00819 DBusHashEntry ***bucket,
00820 DBusPreallocatedHash *preallocated)
00821 {
00822 DBusHashEntry *entry;
00823
00824 if (preallocated == NULL)
00825 {
00826 entry = alloc_entry (table);
00827 if (entry == NULL)
00828 {
00829 if (bucket)
00830 *bucket = NULL;
00831 return NULL;
00832 }
00833 }
00834 else
00835 {
00836 entry = (DBusHashEntry*) preallocated;
00837 }
00838
00839 add_allocated_entry (table, entry, idx, key, bucket);
00840
00841 return entry;
00842 }
00843
00844
00845
00846
00847 static unsigned int
00848 string_hash (const char *str)
00849 {
00850 const char *p = str;
00851 unsigned int h = *p;
00852
00853 if (h)
00854 for (p += 1; *p != '\0'; p++)
00855 h = (h << 5) - h + *p;
00856
00857 return h;
00858 }
00859
00860 #ifdef DBUS_BUILD_TESTS
00861
00862
00863
00864 static unsigned int
00865 two_strings_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 for (p += 1; *p != '\0'; p++)
00875 h = (h << 5) - h + *p;
00876
00877 return h;
00878 }
00879 #endif
00880
00882 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
00883
00884 static DBusHashEntry*
00885 find_generic_function (DBusHashTable *table,
00886 void *key,
00887 unsigned int idx,
00888 KeyCompareFunc compare_func,
00889 dbus_bool_t create_if_not_found,
00890 DBusHashEntry ***bucket,
00891 DBusPreallocatedHash *preallocated)
00892 {
00893 DBusHashEntry *entry;
00894
00895 if (bucket)
00896 *bucket = NULL;
00897
00898
00899 entry = table->buckets[idx];
00900 while (entry != NULL)
00901 {
00902 if ((compare_func == NULL && key == entry->key) ||
00903 (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
00904 {
00905 if (bucket)
00906 *bucket = &(table->buckets[idx]);
00907
00908 if (preallocated)
00909 _dbus_hash_table_free_preallocated_entry (table, preallocated);
00910
00911 return entry;
00912 }
00913
00914 entry = entry->next;
00915 }
00916
00917 if (create_if_not_found)
00918 entry = add_entry (table, idx, key, bucket, preallocated);
00919 else if (preallocated)
00920 _dbus_hash_table_free_preallocated_entry (table, preallocated);
00921
00922 return entry;
00923 }
00924
00925 static DBusHashEntry*
00926 find_string_function (DBusHashTable *table,
00927 void *key,
00928 dbus_bool_t create_if_not_found,
00929 DBusHashEntry ***bucket,
00930 DBusPreallocatedHash *preallocated)
00931 {
00932 unsigned int idx;
00933
00934 idx = string_hash (key) & table->mask;
00935
00936 return find_generic_function (table, key, idx,
00937 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
00938 preallocated);
00939 }
00940
00941 #ifdef DBUS_BUILD_TESTS
00942 static int
00943 two_strings_cmp (const char *a,
00944 const char *b)
00945 {
00946 size_t len_a;
00947 size_t len_b;
00948 int res;
00949
00950 res = strcmp (a, b);
00951 if (res != 0)
00952 return res;
00953
00954 len_a = strlen (a);
00955 len_b = strlen (b);
00956
00957 return strcmp (a + len_a + 1, b + len_b + 1);
00958 }
00959 #endif
00960
00961 #ifdef DBUS_BUILD_TESTS
00962 static DBusHashEntry*
00963 find_two_strings_function (DBusHashTable *table,
00964 void *key,
00965 dbus_bool_t create_if_not_found,
00966 DBusHashEntry ***bucket,
00967 DBusPreallocatedHash *preallocated)
00968 {
00969 unsigned int idx;
00970
00971 idx = two_strings_hash (key) & table->mask;
00972
00973 return find_generic_function (table, key, idx,
00974 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
00975 preallocated);
00976 }
00977 #endif
00978
00979 static DBusHashEntry*
00980 find_direct_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 = RANDOM_INDEX (table, key) & table->mask;
00989
00990
00991 return find_generic_function (table, key, idx,
00992 NULL, create_if_not_found, bucket,
00993 preallocated);
00994 }
00995
00996 static void
00997 rebuild_table (DBusHashTable *table)
00998 {
00999 int old_size;
01000 int new_buckets;
01001 DBusHashEntry **old_buckets;
01002 DBusHashEntry **old_chain;
01003 DBusHashEntry *entry;
01004 dbus_bool_t growing;
01005
01006
01007
01008
01009
01010
01011 growing = table->n_entries >= table->hi_rebuild_size;
01012
01013 old_size = table->n_buckets;
01014 old_buckets = table->buckets;
01015
01016 if (growing)
01017 {
01018
01019 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
01020 table->down_shift >= 0)
01021 new_buckets = table->n_buckets * 4;
01022 else
01023 return;
01024 }
01025 else
01026 {
01027 new_buckets = table->n_buckets / 4;
01028 if (new_buckets < DBUS_SMALL_HASH_TABLE)
01029 return;
01030 }
01031
01032 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
01033 if (table->buckets == NULL)
01034 {
01035
01036
01037
01038 table->buckets = old_buckets;
01039 return;
01040 }
01041
01042 table->n_buckets = new_buckets;
01043
01044 if (growing)
01045 {
01046 table->lo_rebuild_size = table->hi_rebuild_size;
01047 table->hi_rebuild_size *= 4;
01048
01049 table->down_shift -= 2;
01050 table->mask = (table->mask << 2) + 3;
01051 }
01052 else
01053 {
01054 table->hi_rebuild_size = table->lo_rebuild_size;
01055 table->lo_rebuild_size /= 4;
01056
01057 table->down_shift += 2;
01058 table->mask = table->mask >> 2;
01059 }
01060
01061 #if 0
01062 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
01063 growing ? "GROW" : "SHRINK",
01064 table->lo_rebuild_size,
01065 table->hi_rebuild_size,
01066 table->down_shift,
01067 table->mask);
01068 #endif
01069
01070 _dbus_assert (table->lo_rebuild_size >= 0);
01071 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
01072 _dbus_assert (table->mask != 0);
01073
01074 _dbus_assert (table->mask < table->n_buckets);
01075
01076
01077
01078
01079
01080 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01081 {
01082 for (entry = *old_chain; entry != NULL; entry = *old_chain)
01083 {
01084 unsigned int idx;
01085 DBusHashEntry **bucket;
01086
01087 *old_chain = entry->next;
01088 switch (table->key_type)
01089 {
01090 case DBUS_HASH_STRING:
01091 idx = string_hash (entry->key) & table->mask;
01092 break;
01093 case DBUS_HASH_TWO_STRINGS:
01094 #ifdef DBUS_BUILD_TESTS
01095 idx = two_strings_hash (entry->key) & table->mask;
01096 #else
01097 idx = 0;
01098 _dbus_assert_not_reached ("two-strings is not enabled");
01099 #endif
01100 break;
01101 case DBUS_HASH_INT:
01102 case DBUS_HASH_ULONG:
01103 case DBUS_HASH_POINTER:
01104 idx = RANDOM_INDEX (table, entry->key);
01105 break;
01106 default:
01107 idx = 0;
01108 _dbus_assert_not_reached ("Unknown hash table type");
01109 break;
01110 }
01111
01112 bucket = &(table->buckets[idx]);
01113 entry->next = *bucket;
01114 *bucket = entry;
01115 }
01116 }
01117
01118
01119
01120 if (old_buckets != table->static_buckets)
01121 dbus_free (old_buckets);
01122 }
01123
01133 void*
01134 _dbus_hash_table_lookup_string (DBusHashTable *table,
01135 const char *key)
01136 {
01137 DBusHashEntry *entry;
01138
01139 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01140
01141 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01142
01143 if (entry)
01144 return entry->value;
01145 else
01146 return NULL;
01147 }
01148
01149 #ifdef DBUS_BUILD_TESTS
01150
01159 void*
01160 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
01161 const char *key)
01162 {
01163 DBusHashEntry *entry;
01164
01165 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01166
01167 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01168
01169 if (entry)
01170 return entry->value;
01171 else
01172 return NULL;
01173 }
01174 #endif
01175
01185 void*
01186 _dbus_hash_table_lookup_int (DBusHashTable *table,
01187 int key)
01188 {
01189 DBusHashEntry *entry;
01190
01191 _dbus_assert (table->key_type == DBUS_HASH_INT);
01192
01193 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01194
01195 if (entry)
01196 return entry->value;
01197 else
01198 return NULL;
01199 }
01200
01201 #ifdef DBUS_BUILD_TESTS
01202
01212 void*
01213 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
01214 void *key)
01215 {
01216 DBusHashEntry *entry;
01217
01218 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01219
01220 entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
01221
01222 if (entry)
01223 return entry->value;
01224 else
01225 return NULL;
01226 }
01227 #endif
01228
01238 void*
01239 _dbus_hash_table_lookup_ulong (DBusHashTable *table,
01240 unsigned long key)
01241 {
01242 DBusHashEntry *entry;
01243
01244 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01245
01246 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01247
01248 if (entry)
01249 return entry->value;
01250 else
01251 return NULL;
01252 }
01253
01262 dbus_bool_t
01263 _dbus_hash_table_remove_string (DBusHashTable *table,
01264 const char *key)
01265 {
01266 DBusHashEntry *entry;
01267 DBusHashEntry **bucket;
01268
01269 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01270
01271 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01272
01273 if (entry)
01274 {
01275 remove_entry (table, bucket, entry);
01276 return TRUE;
01277 }
01278 else
01279 return FALSE;
01280 }
01281
01282 #ifdef DBUS_BUILD_TESTS
01283
01291 dbus_bool_t
01292 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
01293 const char *key)
01294 {
01295 DBusHashEntry *entry;
01296 DBusHashEntry **bucket;
01297
01298 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01299
01300 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01301
01302 if (entry)
01303 {
01304 remove_entry (table, bucket, entry);
01305 return TRUE;
01306 }
01307 else
01308 return FALSE;
01309 }
01310 #endif
01311
01320 dbus_bool_t
01321 _dbus_hash_table_remove_int (DBusHashTable *table,
01322 int key)
01323 {
01324 DBusHashEntry *entry;
01325 DBusHashEntry **bucket;
01326
01327 _dbus_assert (table->key_type == DBUS_HASH_INT);
01328
01329 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01330
01331 if (entry)
01332 {
01333 remove_entry (table, bucket, entry);
01334 return TRUE;
01335 }
01336 else
01337 return FALSE;
01338 }
01339
01340 #ifdef DBUS_BUILD_TESTS
01341
01350 dbus_bool_t
01351 _dbus_hash_table_remove_pointer (DBusHashTable *table,
01352 void *key)
01353 {
01354 DBusHashEntry *entry;
01355 DBusHashEntry **bucket;
01356
01357 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01358
01359 entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
01360
01361 if (entry)
01362 {
01363 remove_entry (table, bucket, entry);
01364 return TRUE;
01365 }
01366 else
01367 return FALSE;
01368 }
01369 #endif
01370
01379 dbus_bool_t
01380 _dbus_hash_table_remove_ulong (DBusHashTable *table,
01381 unsigned long key)
01382 {
01383 DBusHashEntry *entry;
01384 DBusHashEntry **bucket;
01385
01386 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01387
01388 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01389
01390 if (entry)
01391 {
01392 remove_entry (table, bucket, entry);
01393 return TRUE;
01394 }
01395 else
01396 return FALSE;
01397 }
01398
01414 dbus_bool_t
01415 _dbus_hash_table_insert_string (DBusHashTable *table,
01416 char *key,
01417 void *value)
01418 {
01419 DBusPreallocatedHash *preallocated;
01420
01421 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01422
01423 preallocated = _dbus_hash_table_preallocate_entry (table);
01424 if (preallocated == NULL)
01425 return FALSE;
01426
01427 _dbus_hash_table_insert_string_preallocated (table, preallocated,
01428 key, value);
01429
01430 return TRUE;
01431 }
01432
01433 #ifdef DBUS_BUILD_TESTS
01434
01449 dbus_bool_t
01450 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
01451 char *key,
01452 void *value)
01453 {
01454 DBusHashEntry *entry;
01455
01456 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
01457
01458 entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01459
01460 if (entry == NULL)
01461 return FALSE;
01462
01463 if (table->free_key_function && entry->key != key)
01464 (* table->free_key_function) (entry->key);
01465
01466 if (table->free_value_function && entry->value != value)
01467 (* table->free_value_function) (entry->value);
01468
01469 entry->key = key;
01470 entry->value = value;
01471
01472 return TRUE;
01473 }
01474 #endif
01475
01491 dbus_bool_t
01492 _dbus_hash_table_insert_int (DBusHashTable *table,
01493 int key,
01494 void *value)
01495 {
01496 DBusHashEntry *entry;
01497
01498 _dbus_assert (table->key_type == DBUS_HASH_INT);
01499
01500 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01501
01502 if (entry == NULL)
01503 return FALSE;
01504
01505 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01506 (* table->free_key_function) (entry->key);
01507
01508 if (table->free_value_function && entry->value != value)
01509 (* table->free_value_function) (entry->value);
01510
01511 entry->key = _DBUS_INT_TO_POINTER (key);
01512 entry->value = value;
01513
01514 return TRUE;
01515 }
01516
01517 #ifdef DBUS_BUILD_TESTS
01518
01534 dbus_bool_t
01535 _dbus_hash_table_insert_pointer (DBusHashTable *table,
01536 void *key,
01537 void *value)
01538 {
01539 DBusHashEntry *entry;
01540
01541 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01542
01543 entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01544
01545 if (entry == NULL)
01546 return FALSE;
01547
01548 if (table->free_key_function && entry->key != key)
01549 (* table->free_key_function) (entry->key);
01550
01551 if (table->free_value_function && entry->value != value)
01552 (* table->free_value_function) (entry->value);
01553
01554 entry->key = key;
01555 entry->value = value;
01556
01557 return TRUE;
01558 }
01559 #endif
01560
01576 dbus_bool_t
01577 _dbus_hash_table_insert_ulong (DBusHashTable *table,
01578 unsigned long key,
01579 void *value)
01580 {
01581 DBusHashEntry *entry;
01582
01583 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01584
01585 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01586
01587 if (entry == NULL)
01588 return FALSE;
01589
01590 if (table->free_key_function && entry->key != (void*) key)
01591 (* table->free_key_function) (entry->key);
01592
01593 if (table->free_value_function && entry->value != value)
01594 (* table->free_value_function) (entry->value);
01595
01596 entry->key = (void*) key;
01597 entry->value = value;
01598
01599 return TRUE;
01600 }
01601
01609 DBusPreallocatedHash*
01610 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01611 {
01612 DBusHashEntry *entry;
01613
01614 entry = alloc_entry (table);
01615
01616 return (DBusPreallocatedHash*) entry;
01617 }
01618
01626 void
01627 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table,
01628 DBusPreallocatedHash *preallocated)
01629 {
01630 DBusHashEntry *entry;
01631
01632 _dbus_assert (preallocated != NULL);
01633
01634 entry = (DBusHashEntry*) preallocated;
01635
01636
01637 _dbus_mem_pool_dealloc (table->entry_pool, entry);
01638 }
01639
01653 void
01654 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table,
01655 DBusPreallocatedHash *preallocated,
01656 char *key,
01657 void *value)
01658 {
01659 DBusHashEntry *entry;
01660
01661 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01662 _dbus_assert (preallocated != NULL);
01663
01664 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01665
01666 _dbus_assert (entry != NULL);
01667
01668 if (table->free_key_function && entry->key != key)
01669 (* table->free_key_function) (entry->key);
01670
01671 if (table->free_value_function && entry->value != value)
01672 (* table->free_value_function) (entry->value);
01673
01674 entry->key = key;
01675 entry->value = value;
01676 }
01677
01684 int
01685 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01686 {
01687 return table->n_entries;
01688 }
01689
01692 #ifdef DBUS_BUILD_TESTS
01693 #include "dbus-test.h"
01694 #include <stdio.h>
01695
01696
01697
01698
01699
01700 static int
01701 count_entries (DBusHashTable *table)
01702 {
01703 DBusHashIter iter;
01704 int count;
01705
01706 count = 0;
01707 _dbus_hash_iter_init (table, &iter);
01708 while (_dbus_hash_iter_next (&iter))
01709 ++count;
01710
01711 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01712
01713 return count;
01714 }
01715
01716
01717 static char*
01718 _dbus_strdup2 (const char *str)
01719 {
01720 size_t len;
01721 char *copy;
01722
01723 if (str == NULL)
01724 return NULL;
01725
01726 len = strlen (str);
01727 len += strlen ((str + len + 1));
01728
01729 copy = dbus_malloc (len + 2);
01730 if (copy == NULL)
01731 return NULL;
01732
01733 memcpy (copy, str, len + 2);
01734
01735 return copy;
01736 }
01737
01743 dbus_bool_t
01744 _dbus_hash_test (void)
01745 {
01746 int i;
01747 DBusHashTable *table1;
01748 DBusHashTable *table2;
01749 DBusHashTable *table3;
01750 DBusHashTable *table4;
01751 DBusHashIter iter;
01752 #define N_HASH_KEYS 5000
01753 char **keys;
01754 dbus_bool_t ret = FALSE;
01755
01756 keys = dbus_new (char *, N_HASH_KEYS);
01757 if (keys == NULL)
01758 _dbus_assert_not_reached ("no memory");
01759
01760 for (i = 0; i < N_HASH_KEYS; i++)
01761 {
01762 keys[i] = dbus_malloc (128);
01763
01764 if (keys[i] == NULL)
01765 _dbus_assert_not_reached ("no memory");
01766 }
01767
01768 printf ("Computing test hash keys...\n");
01769 i = 0;
01770 while (i < N_HASH_KEYS)
01771 {
01772 int len;
01773
01774
01775
01776
01777
01778 len = sprintf (keys[i], "Hash key %d", i);
01779 sprintf (keys[i] + len + 1, "Two string %d", i);
01780 _dbus_assert (*(keys[i] + len) == '\0');
01781 _dbus_assert (*(keys[i] + len + 1) != '\0');
01782 ++i;
01783 }
01784 printf ("... done.\n");
01785
01786 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01787 dbus_free, dbus_free);
01788 if (table1 == NULL)
01789 goto out;
01790
01791 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01792 NULL, dbus_free);
01793 if (table2 == NULL)
01794 goto out;
01795
01796 table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
01797 NULL, dbus_free);
01798 if (table3 == NULL)
01799 goto out;
01800
01801 table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
01802 dbus_free, dbus_free);
01803 if (table4 == NULL)
01804 goto out;
01805
01806
01807
01808
01809
01810 i = 0;
01811 while (i < 3000)
01812 {
01813 void *value;
01814 char *key;
01815
01816 key = _dbus_strdup (keys[i]);
01817 if (key == NULL)
01818 goto out;
01819 value = _dbus_strdup ("Value!");
01820 if (value == NULL)
01821 goto out;
01822
01823 if (!_dbus_hash_table_insert_string (table1,
01824 key, value))
01825 goto out;
01826
01827 value = _dbus_strdup (keys[i]);
01828 if (value == NULL)
01829 goto out;
01830
01831 if (!_dbus_hash_table_insert_int (table2,
01832 i, value))
01833 goto out;
01834
01835 value = _dbus_strdup (keys[i]);
01836 if (value == NULL)
01837 goto out;
01838
01839 if (!_dbus_hash_table_insert_ulong (table3,
01840 i, value))
01841 goto out;
01842
01843 key = _dbus_strdup2 (keys[i]);
01844 if (key == NULL)
01845 goto out;
01846 value = _dbus_strdup ("Value!");
01847 if (value == NULL)
01848 goto out;
01849
01850 if (!_dbus_hash_table_insert_two_strings (table4,
01851 key, value))
01852 goto out;
01853
01854 _dbus_assert (count_entries (table1) == i + 1);
01855 _dbus_assert (count_entries (table2) == i + 1);
01856 _dbus_assert (count_entries (table3) == i + 1);
01857 _dbus_assert (count_entries (table4) == i + 1);
01858
01859 value = _dbus_hash_table_lookup_string (table1, keys[i]);
01860 _dbus_assert (value != NULL);
01861 _dbus_assert (strcmp (value, "Value!") == 0);
01862
01863 value = _dbus_hash_table_lookup_int (table2, i);
01864 _dbus_assert (value != NULL);
01865 _dbus_assert (strcmp (value, keys[i]) == 0);
01866
01867 value = _dbus_hash_table_lookup_ulong (table3, i);
01868 _dbus_assert (value != NULL);
01869 _dbus_assert (strcmp (value, keys[i]) == 0);
01870
01871 value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
01872 _dbus_assert (value != NULL);
01873 _dbus_assert (strcmp (value, "Value!") == 0);
01874
01875 ++i;
01876 }
01877
01878 --i;
01879 while (i >= 0)
01880 {
01881 _dbus_hash_table_remove_string (table1,
01882 keys[i]);
01883
01884 _dbus_hash_table_remove_int (table2, i);
01885
01886 _dbus_hash_table_remove_ulong (table3, i);
01887
01888 _dbus_hash_table_remove_two_strings (table4,
01889 keys[i]);
01890
01891 _dbus_assert (count_entries (table1) == i);
01892 _dbus_assert (count_entries (table2) == i);
01893 _dbus_assert (count_entries (table3) == i);
01894 _dbus_assert (count_entries (table4) == i);
01895
01896 --i;
01897 }
01898
01899 _dbus_hash_table_ref (table1);
01900 _dbus_hash_table_ref (table2);
01901 _dbus_hash_table_ref (table3);
01902 _dbus_hash_table_ref (table4);
01903 _dbus_hash_table_unref (table1);
01904 _dbus_hash_table_unref (table2);
01905 _dbus_hash_table_unref (table3);
01906 _dbus_hash_table_unref (table4);
01907 _dbus_hash_table_unref (table1);
01908 _dbus_hash_table_unref (table2);
01909 _dbus_hash_table_unref (table3);
01910 _dbus_hash_table_unref (table4);
01911 table3 = NULL;
01912
01913
01914
01915
01916
01917 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01918 dbus_free, dbus_free);
01919 if (table1 == NULL)
01920 goto out;
01921
01922 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01923 NULL, dbus_free);
01924 if (table2 == NULL)
01925 goto out;
01926
01927 i = 0;
01928 while (i < 5000)
01929 {
01930 char *key;
01931 void *value;
01932
01933 key = _dbus_strdup (keys[i]);
01934 if (key == NULL)
01935 goto out;
01936 value = _dbus_strdup ("Value!");
01937 if (value == NULL)
01938 goto out;
01939
01940 if (!_dbus_hash_table_insert_string (table1,
01941 key, value))
01942 goto out;
01943
01944 value = _dbus_strdup (keys[i]);
01945 if (value == NULL)
01946 goto out;
01947
01948 if (!_dbus_hash_table_insert_int (table2,
01949 i, value))
01950 goto out;
01951
01952 _dbus_assert (count_entries (table1) == i + 1);
01953 _dbus_assert (count_entries (table2) == i + 1);
01954
01955 ++i;
01956 }
01957
01958 _dbus_hash_iter_init (table1, &iter);
01959 while (_dbus_hash_iter_next (&iter))
01960 {
01961 const char *key;
01962 void *value;
01963
01964 key = _dbus_hash_iter_get_string_key (&iter);
01965 value = _dbus_hash_iter_get_value (&iter);
01966
01967 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01968
01969 value = _dbus_strdup ("Different value!");
01970 if (value == NULL)
01971 goto out;
01972
01973 _dbus_hash_iter_set_value (&iter, value);
01974
01975 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01976 }
01977
01978 _dbus_hash_iter_init (table1, &iter);
01979 while (_dbus_hash_iter_next (&iter))
01980 {
01981 _dbus_hash_iter_remove_entry (&iter);
01982 _dbus_assert (count_entries (table1) == i - 1);
01983 --i;
01984 }
01985
01986 _dbus_hash_iter_init (table2, &iter);
01987 while (_dbus_hash_iter_next (&iter))
01988 {
01989 int key;
01990 void *value;
01991
01992 key = _dbus_hash_iter_get_int_key (&iter);
01993 value = _dbus_hash_iter_get_value (&iter);
01994
01995 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01996
01997 value = _dbus_strdup ("Different value!");
01998 if (value == NULL)
01999 goto out;
02000
02001 _dbus_hash_iter_set_value (&iter, value);
02002
02003 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
02004 }
02005
02006 i = count_entries (table2);
02007 _dbus_hash_iter_init (table2, &iter);
02008 while (_dbus_hash_iter_next (&iter))
02009 {
02010 _dbus_hash_iter_remove_entry (&iter);
02011 _dbus_assert (count_entries (table2) + 1 == i);
02012 --i;
02013 }
02014
02015
02016
02017
02018 i = 0;
02019 while (i < 1000)
02020 {
02021 char *key;
02022 void *value;
02023
02024 key = _dbus_strdup (keys[i]);
02025 if (key == NULL)
02026 goto out;
02027
02028 value = _dbus_strdup ("Value!");
02029 if (value == NULL)
02030 goto out;
02031
02032 if (!_dbus_hash_table_insert_string (table1,
02033 key, value))
02034 goto out;
02035
02036 ++i;
02037 }
02038
02039 --i;
02040 while (i >= 0)
02041 {
02042 char *key;
02043 void *value;
02044
02045 key = _dbus_strdup (keys[i]);
02046 if (key == NULL)
02047 goto out;
02048 value = _dbus_strdup ("Value!");
02049 if (value == NULL)
02050 goto out;
02051
02052 if (!_dbus_hash_table_remove_string (table1, keys[i]))
02053 goto out;
02054
02055 if (!_dbus_hash_table_insert_string (table1,
02056 key, value))
02057 goto out;
02058
02059 if (!_dbus_hash_table_remove_string (table1, keys[i]))
02060 goto out;
02061
02062 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
02063
02064 --i;
02065 }
02066
02067
02068 _dbus_hash_table_unref (table1);
02069 _dbus_hash_table_unref (table2);
02070
02071
02072
02073
02074
02075 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
02076 dbus_free, dbus_free);
02077 if (table1 == NULL)
02078 goto out;
02079
02080 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
02081 NULL, dbus_free);
02082 if (table2 == NULL)
02083 goto out;
02084
02085 i = 0;
02086 while (i < 3000)
02087 {
02088 void *value;
02089 char *key;
02090
02091 key = _dbus_strdup (keys[i]);
02092 if (key == NULL)
02093 goto out;
02094 value = _dbus_strdup ("Value!");
02095 if (value == NULL)
02096 goto out;
02097
02098 if (!_dbus_hash_iter_lookup (table1,
02099 key, TRUE, &iter))
02100 goto out;
02101 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02102 _dbus_hash_iter_set_value (&iter, value);
02103
02104 value = _dbus_strdup (keys[i]);
02105 if (value == NULL)
02106 goto out;
02107
02108 if (!_dbus_hash_iter_lookup (table2,
02109 _DBUS_INT_TO_POINTER (i), TRUE, &iter))
02110 goto out;
02111 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
02112 _dbus_hash_iter_set_value (&iter, value);
02113
02114 _dbus_assert (count_entries (table1) == i + 1);
02115 _dbus_assert (count_entries (table2) == i + 1);
02116
02117 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02118 goto out;
02119
02120 value = _dbus_hash_iter_get_value (&iter);
02121 _dbus_assert (value != NULL);
02122 _dbus_assert (strcmp (value, "Value!") == 0);
02123
02124
02125
02126
02127 while (_dbus_hash_iter_next (&iter))
02128 ;
02129
02130 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02131 goto out;
02132
02133 value = _dbus_hash_iter_get_value (&iter);
02134 _dbus_assert (value != NULL);
02135 _dbus_assert (strcmp (value, keys[i]) == 0);
02136
02137
02138
02139
02140 while (_dbus_hash_iter_next (&iter))
02141 ;
02142
02143 ++i;
02144 }
02145
02146 --i;
02147 while (i >= 0)
02148 {
02149 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
02150 _dbus_assert_not_reached ("hash entry should have existed");
02151 _dbus_hash_iter_remove_entry (&iter);
02152
02153 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
02154 _dbus_assert_not_reached ("hash entry should have existed");
02155 _dbus_hash_iter_remove_entry (&iter);
02156
02157 _dbus_assert (count_entries (table1) == i);
02158 _dbus_assert (count_entries (table2) == i);
02159
02160 --i;
02161 }
02162
02163 _dbus_hash_table_unref (table1);
02164 _dbus_hash_table_unref (table2);
02165
02166 ret = TRUE;
02167
02168 out:
02169 for (i = 0; i < N_HASH_KEYS; i++)
02170 dbus_free (keys[i]);
02171
02172 dbus_free (keys);
02173
02174 return ret;
02175 }
02176
02177 #endif