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