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