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 unsigned int string_hash (const char *str);
00235 static void rebuild_table (DBusHashTable *table);
00236 static DBusHashEntry* alloc_entry (DBusHashTable *table);
00237 static void remove_entry (DBusHashTable *table,
00238 DBusHashEntry **bucket,
00239 DBusHashEntry *entry);
00240 static void free_entry (DBusHashTable *table,
00241 DBusHashEntry *entry);
00242 static void free_entry_data (DBusHashTable *table,
00243 DBusHashEntry *entry);
00244
00245
00281 DBusHashTable*
00282 _dbus_hash_table_new (DBusHashType type,
00283 DBusFreeFunction key_free_function,
00284 DBusFreeFunction value_free_function)
00285 {
00286 DBusHashTable *table;
00287 DBusMemPool *entry_pool;
00288
00289 table = dbus_new0 (DBusHashTable, 1);
00290 if (table == NULL)
00291 return NULL;
00292
00293 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00294 if (entry_pool == NULL)
00295 {
00296 dbus_free (table);
00297 return NULL;
00298 }
00299
00300 table->refcount = 1;
00301 table->entry_pool = entry_pool;
00302
00303 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00304
00305 table->buckets = table->static_buckets;
00306 table->n_buckets = DBUS_SMALL_HASH_TABLE;
00307 table->n_entries = 0;
00308 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00309 table->lo_rebuild_size = 0;
00310 table->down_shift = 28;
00311 table->mask = 3;
00312 table->key_type = type;
00313
00314 _dbus_assert (table->mask < table->n_buckets);
00315
00316 switch (table->key_type)
00317 {
00318 case DBUS_HASH_INT:
00319 case DBUS_HASH_POINTER:
00320 case DBUS_HASH_ULONG:
00321 table->find_function = find_direct_function;
00322 break;
00323 case DBUS_HASH_STRING:
00324 table->find_function = find_string_function;
00325 break;
00326 default:
00327 _dbus_assert_not_reached ("Unknown hash table type");
00328 break;
00329 }
00330
00331 table->free_key_function = key_free_function;
00332 table->free_value_function = value_free_function;
00333
00334 return table;
00335 }
00336
00337
00343 void
00344 _dbus_hash_table_ref (DBusHashTable *table)
00345 {
00346 table->refcount += 1;
00347 }
00348
00355 void
00356 _dbus_hash_table_unref (DBusHashTable *table)
00357 {
00358 table->refcount -= 1;
00359
00360 if (table->refcount == 0)
00361 {
00362 #if 0
00363 DBusHashEntry *entry;
00364 DBusHashEntry *next;
00365 int i;
00366
00367
00368 for (i = 0; i < table->n_buckets; i++)
00369 {
00370 entry = table->buckets[i];
00371 while (entry != NULL)
00372 {
00373 next = entry->next;
00374
00375 free_entry (table, entry);
00376
00377 entry = next;
00378 }
00379 }
00380 #else
00381 DBusHashEntry *entry;
00382 int i;
00383
00384
00385 for (i = 0; i < table->n_buckets; i++)
00386 {
00387 entry = table->buckets[i];
00388 while (entry != NULL)
00389 {
00390 free_entry_data (table, entry);
00391
00392 entry = entry->next;
00393 }
00394 }
00395
00396 _dbus_mem_pool_free (table->entry_pool);
00397 #endif
00398
00399
00400 if (table->buckets != table->static_buckets)
00401 dbus_free (table->buckets);
00402
00403 dbus_free (table);
00404 }
00405 }
00406
00407 static DBusHashEntry*
00408 alloc_entry (DBusHashTable *table)
00409 {
00410 DBusHashEntry *entry;
00411
00412 entry = _dbus_mem_pool_alloc (table->entry_pool);
00413
00414 return entry;
00415 }
00416
00417 static void
00418 free_entry_data (DBusHashTable *table,
00419 DBusHashEntry *entry)
00420 {
00421 if (table->free_key_function)
00422 (* table->free_key_function) (entry->key);
00423 if (table->free_value_function)
00424 (* table->free_value_function) (entry->value);
00425 }
00426
00427 static void
00428 free_entry (DBusHashTable *table,
00429 DBusHashEntry *entry)
00430 {
00431 free_entry_data (table, entry);
00432 _dbus_mem_pool_dealloc (table->entry_pool, entry);
00433 }
00434
00435 static void
00436 remove_entry (DBusHashTable *table,
00437 DBusHashEntry **bucket,
00438 DBusHashEntry *entry)
00439 {
00440 _dbus_assert (table != NULL);
00441 _dbus_assert (bucket != NULL);
00442 _dbus_assert (*bucket != NULL);
00443 _dbus_assert (entry != NULL);
00444
00445 if (*bucket == entry)
00446 *bucket = entry->next;
00447 else
00448 {
00449 DBusHashEntry *prev;
00450 prev = *bucket;
00451
00452 while (prev->next != entry)
00453 prev = prev->next;
00454
00455 _dbus_assert (prev != NULL);
00456
00457 prev->next = entry->next;
00458 }
00459
00460 table->n_entries -= 1;
00461 free_entry (table, entry);
00462 }
00463
00495 void
00496 _dbus_hash_iter_init (DBusHashTable *table,
00497 DBusHashIter *iter)
00498 {
00499 DBusRealHashIter *real;
00500
00501 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00502
00503 real = (DBusRealHashIter*) iter;
00504
00505 real->table = table;
00506 real->bucket = NULL;
00507 real->entry = NULL;
00508 real->next_entry = NULL;
00509 real->next_bucket = 0;
00510 real->n_entries_on_init = table->n_entries;
00511 }
00512
00521 dbus_bool_t
00522 _dbus_hash_iter_next (DBusHashIter *iter)
00523 {
00524 DBusRealHashIter *real;
00525
00526 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00527
00528 real = (DBusRealHashIter*) iter;
00529
00530
00531
00532
00533 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00534
00535
00536
00537 while (real->next_entry == NULL)
00538 {
00539 if (real->next_bucket >= real->table->n_buckets)
00540 {
00541
00542 real->entry = NULL;
00543 real->table = NULL;
00544 real->bucket = NULL;
00545 return FALSE;
00546 }
00547
00548 real->bucket = &(real->table->buckets[real->next_bucket]);
00549 real->next_entry = *(real->bucket);
00550 real->next_bucket += 1;
00551 }
00552
00553 _dbus_assert (real->next_entry != NULL);
00554 _dbus_assert (real->bucket != NULL);
00555
00556 real->entry = real->next_entry;
00557 real->next_entry = real->entry->next;
00558
00559 return TRUE;
00560 }
00561
00570 void
00571 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
00572 {
00573 DBusRealHashIter *real;
00574
00575 real = (DBusRealHashIter*) iter;
00576
00577 _dbus_assert (real->table != NULL);
00578 _dbus_assert (real->entry != NULL);
00579 _dbus_assert (real->bucket != NULL);
00580
00581 remove_entry (real->table, real->bucket, real->entry);
00582
00583 real->entry = NULL;
00584 }
00585
00591 void*
00592 _dbus_hash_iter_get_value (DBusHashIter *iter)
00593 {
00594 DBusRealHashIter *real;
00595
00596 real = (DBusRealHashIter*) iter;
00597
00598 _dbus_assert (real->table != NULL);
00599 _dbus_assert (real->entry != NULL);
00600
00601 return real->entry->value;
00602 }
00603
00614 void
00615 _dbus_hash_iter_set_value (DBusHashIter *iter,
00616 void *value)
00617 {
00618 DBusRealHashIter *real;
00619
00620 real = (DBusRealHashIter*) iter;
00621
00622 _dbus_assert (real->table != NULL);
00623 _dbus_assert (real->entry != NULL);
00624
00625 if (real->table->free_value_function && value != real->entry->value)
00626 (* real->table->free_value_function) (real->entry->value);
00627
00628 real->entry->value = value;
00629 }
00630
00637 int
00638 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00639 {
00640 DBusRealHashIter *real;
00641
00642 real = (DBusRealHashIter*) iter;
00643
00644 _dbus_assert (real->table != NULL);
00645 _dbus_assert (real->entry != NULL);
00646
00647 return _DBUS_POINTER_TO_INT (real->entry->key);
00648 }
00649
00656 unsigned long
00657 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
00658 {
00659 DBusRealHashIter *real;
00660
00661 real = (DBusRealHashIter*) iter;
00662
00663 _dbus_assert (real->table != NULL);
00664 _dbus_assert (real->entry != NULL);
00665
00666 return (unsigned long) real->entry->key;
00667 }
00668
00674 const char*
00675 _dbus_hash_iter_get_string_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 real->entry->key;
00685 }
00686
00718 dbus_bool_t
00719 _dbus_hash_iter_lookup (DBusHashTable *table,
00720 void *key,
00721 dbus_bool_t create_if_not_found,
00722 DBusHashIter *iter)
00723 {
00724 DBusRealHashIter *real;
00725 DBusHashEntry *entry;
00726 DBusHashEntry **bucket;
00727
00728 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00729
00730 real = (DBusRealHashIter*) iter;
00731
00732 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00733
00734 if (entry == NULL)
00735 return FALSE;
00736
00737 real->table = table;
00738 real->bucket = bucket;
00739 real->entry = entry;
00740 real->next_entry = entry->next;
00741 real->next_bucket = (bucket - table->buckets) + 1;
00742 real->n_entries_on_init = table->n_entries;
00743
00744 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00745
00746 return TRUE;
00747 }
00748
00749 static void
00750 add_allocated_entry (DBusHashTable *table,
00751 DBusHashEntry *entry,
00752 unsigned int idx,
00753 void *key,
00754 DBusHashEntry ***bucket)
00755 {
00756 DBusHashEntry **b;
00757
00758 entry->key = key;
00759
00760 b = &(table->buckets[idx]);
00761 entry->next = *b;
00762 *b = entry;
00763
00764 if (bucket)
00765 *bucket = b;
00766
00767 table->n_entries += 1;
00768
00769
00770
00771
00772 if (table->n_entries >= table->hi_rebuild_size ||
00773 table->n_entries < table->lo_rebuild_size)
00774 rebuild_table (table);
00775 }
00776
00777 static DBusHashEntry*
00778 add_entry (DBusHashTable *table,
00779 unsigned int idx,
00780 void *key,
00781 DBusHashEntry ***bucket,
00782 DBusPreallocatedHash *preallocated)
00783 {
00784 DBusHashEntry *entry;
00785
00786 if (preallocated == NULL)
00787 {
00788 entry = alloc_entry (table);
00789 if (entry == NULL)
00790 {
00791 if (bucket)
00792 *bucket = NULL;
00793 return NULL;
00794 }
00795 }
00796 else
00797 {
00798 entry = (DBusHashEntry*) preallocated;
00799 }
00800
00801 add_allocated_entry (table, entry, idx, key, bucket);
00802
00803 return entry;
00804 }
00805
00806 static unsigned int
00807 string_hash (const char *str)
00808 {
00809 register unsigned int result;
00810 register int c;
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824
00825
00826
00827
00828
00829
00830 result = 0;
00831 while (TRUE)
00832 {
00833 c = *str;
00834 str++;
00835 if (c == 0)
00836 break;
00837
00838 result += (result << 3) + c;
00839 }
00840
00841 return result;
00842 }
00843
00844 static DBusHashEntry*
00845 find_string_function (DBusHashTable *table,
00846 void *key,
00847 dbus_bool_t create_if_not_found,
00848 DBusHashEntry ***bucket,
00849 DBusPreallocatedHash *preallocated)
00850 {
00851 DBusHashEntry *entry;
00852 unsigned int idx;
00853
00854 if (bucket)
00855 *bucket = NULL;
00856
00857 idx = string_hash (key) & table->mask;
00858
00859
00860 entry = table->buckets[idx];
00861 while (entry != NULL)
00862 {
00863 if (strcmp (key, entry->key) == 0)
00864 {
00865 if (bucket)
00866 *bucket = &(table->buckets[idx]);
00867
00868 if (preallocated)
00869 _dbus_hash_table_free_preallocated_entry (table, preallocated);
00870
00871 return entry;
00872 }
00873
00874 entry = entry->next;
00875 }
00876
00877 if (create_if_not_found)
00878 entry = add_entry (table, idx, key, bucket, preallocated);
00879 else if (preallocated)
00880 _dbus_hash_table_free_preallocated_entry (table, preallocated);
00881
00882 return entry;
00883 }
00884
00885 static DBusHashEntry*
00886 find_direct_function (DBusHashTable *table,
00887 void *key,
00888 dbus_bool_t create_if_not_found,
00889 DBusHashEntry ***bucket,
00890 DBusPreallocatedHash *preallocated)
00891 {
00892 DBusHashEntry *entry;
00893 unsigned int idx;
00894
00895 if (bucket)
00896 *bucket = NULL;
00897
00898 idx = RANDOM_INDEX (table, key) & table->mask;
00899
00900
00901 entry = table->buckets[idx];
00902 while (entry != NULL)
00903 {
00904 if (key == entry->key)
00905 {
00906 if (bucket)
00907 *bucket = &(table->buckets[idx]);
00908
00909 if (preallocated)
00910 _dbus_hash_table_free_preallocated_entry (table, preallocated);
00911
00912 return entry;
00913 }
00914
00915 entry = entry->next;
00916 }
00917
00918
00919 if (create_if_not_found)
00920 entry = add_entry (table, idx, key, bucket, preallocated);
00921 else if (preallocated)
00922 _dbus_hash_table_free_preallocated_entry (table, preallocated);
00923
00924 return entry;
00925 }
00926
00927 static void
00928 rebuild_table (DBusHashTable *table)
00929 {
00930 int old_size;
00931 int new_buckets;
00932 DBusHashEntry **old_buckets;
00933 DBusHashEntry **old_chain;
00934 DBusHashEntry *entry;
00935 dbus_bool_t growing;
00936
00937
00938
00939
00940
00941
00942 growing = table->n_entries >= table->hi_rebuild_size;
00943
00944 old_size = table->n_buckets;
00945 old_buckets = table->buckets;
00946
00947 if (growing)
00948 {
00949
00950 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
00951 table->down_shift >= 0)
00952 new_buckets = table->n_buckets * 4;
00953 else
00954 return;
00955 }
00956 else
00957 {
00958 new_buckets = table->n_buckets / 4;
00959 if (new_buckets < DBUS_SMALL_HASH_TABLE)
00960 return;
00961 }
00962
00963 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
00964 if (table->buckets == NULL)
00965 {
00966
00967
00968
00969 table->buckets = old_buckets;
00970 return;
00971 }
00972
00973 table->n_buckets = new_buckets;
00974
00975 if (growing)
00976 {
00977 table->lo_rebuild_size = table->hi_rebuild_size;
00978 table->hi_rebuild_size *= 4;
00979
00980 table->down_shift -= 2;
00981 table->mask = (table->mask << 2) + 3;
00982 }
00983 else
00984 {
00985 table->hi_rebuild_size = table->lo_rebuild_size;
00986 table->lo_rebuild_size /= 4;
00987
00988 table->down_shift += 2;
00989 table->mask = table->mask >> 2;
00990 }
00991
00992 #if 0
00993 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
00994 growing ? "GROW" : "SHRINK",
00995 table->lo_rebuild_size,
00996 table->hi_rebuild_size,
00997 table->down_shift,
00998 table->mask);
00999 #endif
01000
01001 _dbus_assert (table->lo_rebuild_size >= 0);
01002 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
01003 _dbus_assert (table->mask != 0);
01004
01005 _dbus_assert (table->mask < table->n_buckets);
01006
01007
01008
01009
01010
01011 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01012 {
01013 for (entry = *old_chain; entry != NULL; entry = *old_chain)
01014 {
01015 unsigned int idx;
01016 DBusHashEntry **bucket;
01017
01018 *old_chain = entry->next;
01019 switch (table->key_type)
01020 {
01021 case DBUS_HASH_STRING:
01022 idx = string_hash (entry->key) & table->mask;
01023 break;
01024 case DBUS_HASH_INT:
01025 case DBUS_HASH_ULONG:
01026 case DBUS_HASH_POINTER:
01027 idx = RANDOM_INDEX (table, entry->key);
01028 break;
01029 default:
01030 idx = 0;
01031 _dbus_assert_not_reached ("Unknown hash table type");
01032 break;
01033 }
01034
01035 bucket = &(table->buckets[idx]);
01036 entry->next = *bucket;
01037 *bucket = entry;
01038 }
01039 }
01040
01041
01042
01043 if (old_buckets != table->static_buckets)
01044 dbus_free (old_buckets);
01045 }
01046
01056 void*
01057 _dbus_hash_table_lookup_string (DBusHashTable *table,
01058 const char *key)
01059 {
01060 DBusHashEntry *entry;
01061
01062 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01063
01064 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01065
01066 if (entry)
01067 return entry->value;
01068 else
01069 return NULL;
01070 }
01071
01081 void*
01082 _dbus_hash_table_lookup_int (DBusHashTable *table,
01083 int key)
01084 {
01085 DBusHashEntry *entry;
01086
01087 _dbus_assert (table->key_type == DBUS_HASH_INT);
01088
01089 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01090
01091 if (entry)
01092 return entry->value;
01093 else
01094 return NULL;
01095 }
01096
01097 #ifdef DBUS_BUILD_TESTS
01098
01108 void*
01109 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
01110 void *key)
01111 {
01112 DBusHashEntry *entry;
01113
01114 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01115
01116 entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
01117
01118 if (entry)
01119 return entry->value;
01120 else
01121 return NULL;
01122 }
01123 #endif
01124
01134 void*
01135 _dbus_hash_table_lookup_ulong (DBusHashTable *table,
01136 unsigned long key)
01137 {
01138 DBusHashEntry *entry;
01139
01140 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01141
01142 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01143
01144 if (entry)
01145 return entry->value;
01146 else
01147 return NULL;
01148 }
01149
01158 dbus_bool_t
01159 _dbus_hash_table_remove_string (DBusHashTable *table,
01160 const char *key)
01161 {
01162 DBusHashEntry *entry;
01163 DBusHashEntry **bucket;
01164
01165 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01166
01167 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01168
01169 if (entry)
01170 {
01171 remove_entry (table, bucket, entry);
01172 return TRUE;
01173 }
01174 else
01175 return FALSE;
01176 }
01177
01186 dbus_bool_t
01187 _dbus_hash_table_remove_int (DBusHashTable *table,
01188 int key)
01189 {
01190 DBusHashEntry *entry;
01191 DBusHashEntry **bucket;
01192
01193 _dbus_assert (table->key_type == DBUS_HASH_INT);
01194
01195 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01196
01197 if (entry)
01198 {
01199 remove_entry (table, bucket, entry);
01200 return TRUE;
01201 }
01202 else
01203 return FALSE;
01204 }
01205
01206 #ifdef DBUS_BUILD_TESTS
01207
01216 dbus_bool_t
01217 _dbus_hash_table_remove_pointer (DBusHashTable *table,
01218 void *key)
01219 {
01220 DBusHashEntry *entry;
01221 DBusHashEntry **bucket;
01222
01223 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01224
01225 entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
01226
01227 if (entry)
01228 {
01229 remove_entry (table, bucket, entry);
01230 return TRUE;
01231 }
01232 else
01233 return FALSE;
01234 }
01235 #endif
01236
01245 dbus_bool_t
01246 _dbus_hash_table_remove_ulong (DBusHashTable *table,
01247 unsigned long key)
01248 {
01249 DBusHashEntry *entry;
01250 DBusHashEntry **bucket;
01251
01252 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01253
01254 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01255
01256 if (entry)
01257 {
01258 remove_entry (table, bucket, entry);
01259 return TRUE;
01260 }
01261 else
01262 return FALSE;
01263 }
01264
01280 dbus_bool_t
01281 _dbus_hash_table_insert_string (DBusHashTable *table,
01282 char *key,
01283 void *value)
01284 {
01285 DBusPreallocatedHash *preallocated;
01286
01287 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01288
01289 preallocated = _dbus_hash_table_preallocate_entry (table);
01290 if (preallocated == NULL)
01291 return FALSE;
01292
01293 _dbus_hash_table_insert_string_preallocated (table, preallocated,
01294 key, value);
01295
01296 return TRUE;
01297 }
01298
01314 dbus_bool_t
01315 _dbus_hash_table_insert_int (DBusHashTable *table,
01316 int key,
01317 void *value)
01318 {
01319 DBusHashEntry *entry;
01320
01321 _dbus_assert (table->key_type == DBUS_HASH_INT);
01322
01323 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01324
01325 if (entry == NULL)
01326 return FALSE;
01327
01328 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01329 (* table->free_key_function) (entry->key);
01330
01331 if (table->free_value_function && entry->value != value)
01332 (* table->free_value_function) (entry->value);
01333
01334 entry->key = _DBUS_INT_TO_POINTER (key);
01335 entry->value = value;
01336
01337 return TRUE;
01338 }
01339
01340 #ifdef DBUS_BUILD_TESTS
01341
01357 dbus_bool_t
01358 _dbus_hash_table_insert_pointer (DBusHashTable *table,
01359 void *key,
01360 void *value)
01361 {
01362 DBusHashEntry *entry;
01363
01364 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
01365
01366 entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
01367
01368 if (entry == NULL)
01369 return FALSE;
01370
01371 if (table->free_key_function && entry->key != key)
01372 (* table->free_key_function) (entry->key);
01373
01374 if (table->free_value_function && entry->value != value)
01375 (* table->free_value_function) (entry->value);
01376
01377 entry->key = key;
01378 entry->value = value;
01379
01380 return TRUE;
01381 }
01382 #endif
01383
01399 dbus_bool_t
01400 _dbus_hash_table_insert_ulong (DBusHashTable *table,
01401 unsigned long key,
01402 void *value)
01403 {
01404 DBusHashEntry *entry;
01405
01406 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
01407
01408 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01409
01410 if (entry == NULL)
01411 return FALSE;
01412
01413 if (table->free_key_function && entry->key != (void*) key)
01414 (* table->free_key_function) (entry->key);
01415
01416 if (table->free_value_function && entry->value != value)
01417 (* table->free_value_function) (entry->value);
01418
01419 entry->key = (void*) key;
01420 entry->value = value;
01421
01422 return TRUE;
01423 }
01424
01432 DBusPreallocatedHash*
01433 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01434 {
01435 DBusHashEntry *entry;
01436
01437 entry = alloc_entry (table);
01438
01439 return (DBusPreallocatedHash*) entry;
01440 }
01441
01449 void
01450 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table,
01451 DBusPreallocatedHash *preallocated)
01452 {
01453 DBusHashEntry *entry;
01454
01455 _dbus_assert (preallocated != NULL);
01456
01457 entry = (DBusHashEntry*) preallocated;
01458
01459
01460 _dbus_mem_pool_dealloc (table->entry_pool, entry);
01461 }
01462
01476 void
01477 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table,
01478 DBusPreallocatedHash *preallocated,
01479 char *key,
01480 void *value)
01481 {
01482 DBusHashEntry *entry;
01483
01484 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01485 _dbus_assert (preallocated != NULL);
01486
01487 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01488
01489 _dbus_assert (entry != NULL);
01490
01491 if (table->free_key_function && entry->key != key)
01492 (* table->free_key_function) (entry->key);
01493
01494 if (table->free_value_function && entry->value != value)
01495 (* table->free_value_function) (entry->value);
01496
01497 entry->key = key;
01498 entry->value = value;
01499 }
01500
01507 int
01508 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01509 {
01510 return table->n_entries;
01511 }
01512
01515 #ifdef DBUS_BUILD_TESTS
01516 #include "dbus-test.h"
01517 #include <stdio.h>
01518
01519
01520
01521
01522
01523 static int
01524 count_entries (DBusHashTable *table)
01525 {
01526 DBusHashIter iter;
01527 int count;
01528
01529 count = 0;
01530 _dbus_hash_iter_init (table, &iter);
01531 while (_dbus_hash_iter_next (&iter))
01532 ++count;
01533
01534 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01535
01536 return count;
01537 }
01538
01544 dbus_bool_t
01545 _dbus_hash_test (void)
01546 {
01547 int i;
01548 DBusHashTable *table1;
01549 DBusHashTable *table2;
01550 DBusHashTable *table3;
01551 DBusHashIter iter;
01552 #define N_HASH_KEYS 5000
01553 char **keys;
01554 dbus_bool_t ret = FALSE;
01555
01556 keys = dbus_new (char *, N_HASH_KEYS);
01557 if (keys == NULL)
01558 _dbus_assert_not_reached ("no memory");
01559
01560 for (i = 0; i < N_HASH_KEYS; i++)
01561 {
01562 keys[i] = dbus_malloc (128);
01563
01564 if (keys[i] == NULL)
01565 _dbus_assert_not_reached ("no memory");
01566 }
01567
01568 printf ("Computing test hash keys...\n");
01569 i = 0;
01570 while (i < N_HASH_KEYS)
01571 {
01572 sprintf (keys[i], "Hash key %d", i);
01573 ++i;
01574 }
01575 printf ("... done.\n");
01576
01577 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01578 dbus_free, dbus_free);
01579 if (table1 == NULL)
01580 goto out;
01581
01582 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01583 NULL, dbus_free);
01584 if (table2 == NULL)
01585 goto out;
01586
01587 table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
01588 NULL, dbus_free);
01589 if (table3 == NULL)
01590 goto out;
01591
01592
01593
01594
01595 i = 0;
01596 while (i < 3000)
01597 {
01598 void *value;
01599 char *key;
01600
01601 key = _dbus_strdup (keys[i]);
01602 if (key == NULL)
01603 goto out;
01604 value = _dbus_strdup ("Value!");
01605 if (value == NULL)
01606 goto out;
01607
01608 if (!_dbus_hash_table_insert_string (table1,
01609 key, value))
01610 goto out;
01611
01612 value = _dbus_strdup (keys[i]);
01613 if (value == NULL)
01614 goto out;
01615
01616 if (!_dbus_hash_table_insert_int (table2,
01617 i, value))
01618 goto out;
01619
01620 value = _dbus_strdup (keys[i]);
01621 if (value == NULL)
01622 goto out;
01623
01624 if (!_dbus_hash_table_insert_ulong (table3,
01625 i, value))
01626 goto out;
01627
01628 _dbus_assert (count_entries (table1) == i + 1);
01629 _dbus_assert (count_entries (table2) == i + 1);
01630 _dbus_assert (count_entries (table3) == i + 1);
01631
01632 value = _dbus_hash_table_lookup_string (table1, keys[i]);
01633 _dbus_assert (value != NULL);
01634 _dbus_assert (strcmp (value, "Value!") == 0);
01635
01636 value = _dbus_hash_table_lookup_int (table2, i);
01637 _dbus_assert (value != NULL);
01638 _dbus_assert (strcmp (value, keys[i]) == 0);
01639
01640 value = _dbus_hash_table_lookup_ulong (table3, i);
01641 _dbus_assert (value != NULL);
01642 _dbus_assert (strcmp (value, keys[i]) == 0);
01643
01644 ++i;
01645 }
01646
01647 --i;
01648 while (i >= 0)
01649 {
01650 _dbus_hash_table_remove_string (table1,
01651 keys[i]);
01652
01653 _dbus_hash_table_remove_int (table2, i);
01654
01655 _dbus_hash_table_remove_ulong (table3, i);
01656
01657 _dbus_assert (count_entries (table1) == i);
01658 _dbus_assert (count_entries (table2) == i);
01659 _dbus_assert (count_entries (table3) == i);
01660
01661 --i;
01662 }
01663
01664 _dbus_hash_table_ref (table1);
01665 _dbus_hash_table_ref (table2);
01666 _dbus_hash_table_ref (table3);
01667 _dbus_hash_table_unref (table1);
01668 _dbus_hash_table_unref (table2);
01669 _dbus_hash_table_unref (table3);
01670 _dbus_hash_table_unref (table1);
01671 _dbus_hash_table_unref (table2);
01672 _dbus_hash_table_unref (table3);
01673 table3 = NULL;
01674
01675
01676
01677
01678
01679 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01680 dbus_free, dbus_free);
01681 if (table1 == NULL)
01682 goto out;
01683
01684 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01685 NULL, dbus_free);
01686 if (table2 == NULL)
01687 goto out;
01688
01689 i = 0;
01690 while (i < 5000)
01691 {
01692 char *key;
01693 void *value;
01694
01695 key = _dbus_strdup (keys[i]);
01696 if (key == NULL)
01697 goto out;
01698 value = _dbus_strdup ("Value!");
01699 if (value == NULL)
01700 goto out;
01701
01702 if (!_dbus_hash_table_insert_string (table1,
01703 key, value))
01704 goto out;
01705
01706 value = _dbus_strdup (keys[i]);
01707 if (value == NULL)
01708 goto out;
01709
01710 if (!_dbus_hash_table_insert_int (table2,
01711 i, value))
01712 goto out;
01713
01714 _dbus_assert (count_entries (table1) == i + 1);
01715 _dbus_assert (count_entries (table2) == i + 1);
01716
01717 ++i;
01718 }
01719
01720 _dbus_hash_iter_init (table1, &iter);
01721 while (_dbus_hash_iter_next (&iter))
01722 {
01723 const char *key;
01724 void *value;
01725
01726 key = _dbus_hash_iter_get_string_key (&iter);
01727 value = _dbus_hash_iter_get_value (&iter);
01728
01729 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01730
01731 value = _dbus_strdup ("Different value!");
01732 if (value == NULL)
01733 goto out;
01734
01735 _dbus_hash_iter_set_value (&iter, value);
01736
01737 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01738 }
01739
01740 _dbus_hash_iter_init (table1, &iter);
01741 while (_dbus_hash_iter_next (&iter))
01742 {
01743 _dbus_hash_iter_remove_entry (&iter);
01744 _dbus_assert (count_entries (table1) == i - 1);
01745 --i;
01746 }
01747
01748 _dbus_hash_iter_init (table2, &iter);
01749 while (_dbus_hash_iter_next (&iter))
01750 {
01751 int key;
01752 void *value;
01753
01754 key = _dbus_hash_iter_get_int_key (&iter);
01755 value = _dbus_hash_iter_get_value (&iter);
01756
01757 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01758
01759 value = _dbus_strdup ("Different value!");
01760 if (value == NULL)
01761 goto out;
01762
01763 _dbus_hash_iter_set_value (&iter, value);
01764
01765 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01766 }
01767
01768 i = count_entries (table2);
01769 _dbus_hash_iter_init (table2, &iter);
01770 while (_dbus_hash_iter_next (&iter))
01771 {
01772 _dbus_hash_iter_remove_entry (&iter);
01773 _dbus_assert (count_entries (table2) + 1 == i);
01774 --i;
01775 }
01776
01777
01778
01779
01780 i = 0;
01781 while (i < 1000)
01782 {
01783 char *key;
01784 void *value;
01785
01786 key = _dbus_strdup (keys[i]);
01787 if (key == NULL)
01788 goto out;
01789
01790 value = _dbus_strdup ("Value!");
01791 if (value == NULL)
01792 goto out;
01793
01794 if (!_dbus_hash_table_insert_string (table1,
01795 key, value))
01796 goto out;
01797
01798 ++i;
01799 }
01800
01801 --i;
01802 while (i >= 0)
01803 {
01804 char *key;
01805 void *value;
01806
01807 key = _dbus_strdup (keys[i]);
01808 if (key == NULL)
01809 goto out;
01810 value = _dbus_strdup ("Value!");
01811 if (value == NULL)
01812 goto out;
01813
01814 if (!_dbus_hash_table_remove_string (table1, keys[i]))
01815 goto out;
01816
01817 if (!_dbus_hash_table_insert_string (table1,
01818 key, value))
01819 goto out;
01820
01821 if (!_dbus_hash_table_remove_string (table1, keys[i]))
01822 goto out;
01823
01824 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
01825
01826 --i;
01827 }
01828
01829
01830 _dbus_hash_table_unref (table1);
01831 _dbus_hash_table_unref (table2);
01832
01833
01834
01835
01836
01837 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01838 dbus_free, dbus_free);
01839 if (table1 == NULL)
01840 goto out;
01841
01842 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01843 NULL, dbus_free);
01844 if (table2 == NULL)
01845 goto out;
01846
01847 i = 0;
01848 while (i < 3000)
01849 {
01850 void *value;
01851 char *key;
01852
01853 key = _dbus_strdup (keys[i]);
01854 if (key == NULL)
01855 goto out;
01856 value = _dbus_strdup ("Value!");
01857 if (value == NULL)
01858 goto out;
01859
01860 if (!_dbus_hash_iter_lookup (table1,
01861 key, TRUE, &iter))
01862 goto out;
01863 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
01864 _dbus_hash_iter_set_value (&iter, value);
01865
01866 value = _dbus_strdup (keys[i]);
01867 if (value == NULL)
01868 goto out;
01869
01870 if (!_dbus_hash_iter_lookup (table2,
01871 _DBUS_INT_TO_POINTER (i), TRUE, &iter))
01872 goto out;
01873 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
01874 _dbus_hash_iter_set_value (&iter, value);
01875
01876 _dbus_assert (count_entries (table1) == i + 1);
01877 _dbus_assert (count_entries (table2) == i + 1);
01878
01879 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
01880 goto out;
01881
01882 value = _dbus_hash_iter_get_value (&iter);
01883 _dbus_assert (value != NULL);
01884 _dbus_assert (strcmp (value, "Value!") == 0);
01885
01886
01887
01888
01889 while (_dbus_hash_iter_next (&iter))
01890 ;
01891
01892 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
01893 goto out;
01894
01895 value = _dbus_hash_iter_get_value (&iter);
01896 _dbus_assert (value != NULL);
01897 _dbus_assert (strcmp (value, keys[i]) == 0);
01898
01899
01900
01901
01902 while (_dbus_hash_iter_next (&iter))
01903 ;
01904
01905 ++i;
01906 }
01907
01908 --i;
01909 while (i >= 0)
01910 {
01911 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
01912 _dbus_assert_not_reached ("hash entry should have existed");
01913 _dbus_hash_iter_remove_entry (&iter);
01914
01915 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
01916 _dbus_assert_not_reached ("hash entry should have existed");
01917 _dbus_hash_iter_remove_entry (&iter);
01918
01919 _dbus_assert (count_entries (table1) == i);
01920 _dbus_assert (count_entries (table2) == i);
01921
01922 --i;
01923 }
01924
01925 _dbus_hash_table_unref (table1);
01926 _dbus_hash_table_unref (table2);
01927
01928 ret = TRUE;
01929
01930 out:
01931 for (i = 0; i < N_HASH_KEYS; i++)
01932 dbus_free (keys[i]);
01933
01934 dbus_free (keys);
01935
01936 return ret;
01937 }
01938
01939 #endif