00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077 #include <config.h>
00078 #include "dbus-hash.h"
00079 #include "dbus-internals.h"
00080 #include "dbus-mempool.h"
00081
00104 #define REBUILD_MULTIPLIER 3
00105
00122 #define RANDOM_INDEX(table, i) \
00123 (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
00124
00130 #define DBUS_SMALL_HASH_TABLE 4
00131
00135 typedef struct DBusHashEntry DBusHashEntry;
00136
00143 struct DBusHashEntry
00144 {
00145 DBusHashEntry *next;
00149 void *key;
00150 void *value;
00151 };
00152
00156 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
00157 void *key,
00158 dbus_bool_t create_if_not_found,
00159 DBusHashEntry ***bucket,
00160 DBusPreallocatedHash *preallocated);
00161
00168 struct DBusHashTable {
00169 int refcount;
00171 DBusHashEntry **buckets;
00175 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
00179 int n_buckets;
00182 int n_entries;
00185 int hi_rebuild_size;
00188 int lo_rebuild_size;
00191 int down_shift;
00195 int mask;
00198 DBusHashType key_type;
00201 DBusFindEntryFunction find_function;
00203 DBusFreeFunction free_key_function;
00204 DBusFreeFunction free_value_function;
00206 DBusMemPool *entry_pool;
00207 };
00208
00212 typedef struct
00213 {
00214 DBusHashTable *table;
00215 DBusHashEntry **bucket;
00219 DBusHashEntry *entry;
00220 DBusHashEntry *next_entry;
00221 int next_bucket;
00222 int n_entries_on_init;
00223 } DBusRealHashIter;
00224
00225 _DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
00226
00227 static DBusHashEntry* find_direct_function (DBusHashTable *table,
00228 void *key,
00229 dbus_bool_t create_if_not_found,
00230 DBusHashEntry ***bucket,
00231 DBusPreallocatedHash *preallocated);
00232 static DBusHashEntry* find_string_function (DBusHashTable *table,
00233 void *key,
00234 dbus_bool_t create_if_not_found,
00235 DBusHashEntry ***bucket,
00236 DBusPreallocatedHash *preallocated);
00237 static unsigned int string_hash (const char *str);
00238 static void rebuild_table (DBusHashTable *table);
00239 static DBusHashEntry* alloc_entry (DBusHashTable *table);
00240 static void remove_entry (DBusHashTable *table,
00241 DBusHashEntry **bucket,
00242 DBusHashEntry *entry);
00243 static void free_entry (DBusHashTable *table,
00244 DBusHashEntry *entry);
00245 static void free_entry_data (DBusHashTable *table,
00246 DBusHashEntry *entry);
00247
00248
00284 DBusHashTable*
00285 _dbus_hash_table_new (DBusHashType type,
00286 DBusFreeFunction key_free_function,
00287 DBusFreeFunction value_free_function)
00288 {
00289 DBusHashTable *table;
00290 DBusMemPool *entry_pool;
00291
00292 table = dbus_new0 (DBusHashTable, 1);
00293 if (table == NULL)
00294 return NULL;
00295
00296 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
00297 if (entry_pool == NULL)
00298 {
00299 dbus_free (table);
00300 return NULL;
00301 }
00302
00303 table->refcount = 1;
00304 table->entry_pool = entry_pool;
00305
00306 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
00307
00308 table->buckets = table->static_buckets;
00309 table->n_buckets = DBUS_SMALL_HASH_TABLE;
00310 table->n_entries = 0;
00311 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
00312 table->lo_rebuild_size = 0;
00313 table->down_shift = 28;
00314 table->mask = 3;
00315 table->key_type = type;
00316
00317 _dbus_assert (table->mask < table->n_buckets);
00318
00319 switch (table->key_type)
00320 {
00321 case DBUS_HASH_INT:
00322 case DBUS_HASH_UINTPTR:
00323 table->find_function = find_direct_function;
00324 break;
00325 case DBUS_HASH_STRING:
00326 table->find_function = find_string_function;
00327 break;
00328 default:
00329 _dbus_assert_not_reached ("Unknown hash table type");
00330 break;
00331 }
00332
00333 table->free_key_function = key_free_function;
00334 table->free_value_function = value_free_function;
00335
00336 return table;
00337 }
00338
00339
00346 DBusHashTable *
00347 _dbus_hash_table_ref (DBusHashTable *table)
00348 {
00349 table->refcount += 1;
00350
00351 return table;
00352 }
00353
00360 void
00361 _dbus_hash_table_unref (DBusHashTable *table)
00362 {
00363 table->refcount -= 1;
00364
00365 if (table->refcount == 0)
00366 {
00367 #if 0
00368 DBusHashEntry *entry;
00369 DBusHashEntry *next;
00370 int i;
00371
00372
00373 for (i = 0; i < table->n_buckets; i++)
00374 {
00375 entry = table->buckets[i];
00376 while (entry != NULL)
00377 {
00378 next = entry->next;
00379
00380 free_entry (table, entry);
00381
00382 entry = next;
00383 }
00384 }
00385 #else
00386 DBusHashEntry *entry;
00387 int i;
00388
00389
00390 for (i = 0; i < table->n_buckets; i++)
00391 {
00392 entry = table->buckets[i];
00393 while (entry != NULL)
00394 {
00395 free_entry_data (table, entry);
00396
00397 entry = entry->next;
00398 }
00399 }
00400
00401 _dbus_mem_pool_free (table->entry_pool);
00402 #endif
00403
00404
00405 if (table->buckets != table->static_buckets)
00406 dbus_free (table->buckets);
00407
00408 dbus_free (table);
00409 }
00410 }
00411
00417 void
00418 _dbus_hash_table_remove_all (DBusHashTable *table)
00419 {
00420 DBusHashIter iter;
00421 _dbus_hash_iter_init (table, &iter);
00422 while (_dbus_hash_iter_next (&iter))
00423 {
00424 _dbus_hash_iter_remove_entry(&iter);
00425 }
00426 }
00427
00428 static DBusHashEntry*
00429 alloc_entry (DBusHashTable *table)
00430 {
00431 DBusHashEntry *entry;
00432
00433 entry = _dbus_mem_pool_alloc (table->entry_pool);
00434
00435 return entry;
00436 }
00437
00438 static void
00439 free_entry_data (DBusHashTable *table,
00440 DBusHashEntry *entry)
00441 {
00442 if (table->free_key_function)
00443 (* table->free_key_function) (entry->key);
00444 if (table->free_value_function)
00445 (* table->free_value_function) (entry->value);
00446 }
00447
00448 static void
00449 free_entry (DBusHashTable *table,
00450 DBusHashEntry *entry)
00451 {
00452 free_entry_data (table, entry);
00453 _dbus_mem_pool_dealloc (table->entry_pool, entry);
00454 }
00455
00456 static void
00457 remove_entry (DBusHashTable *table,
00458 DBusHashEntry **bucket,
00459 DBusHashEntry *entry)
00460 {
00461 _dbus_assert (table != NULL);
00462 _dbus_assert (bucket != NULL);
00463 _dbus_assert (*bucket != NULL);
00464 _dbus_assert (entry != NULL);
00465
00466 if (*bucket == entry)
00467 *bucket = entry->next;
00468 else
00469 {
00470 DBusHashEntry *prev;
00471 prev = *bucket;
00472
00473 while (prev->next != entry)
00474 prev = prev->next;
00475
00476 _dbus_assert (prev != NULL);
00477
00478 prev->next = entry->next;
00479 }
00480
00481 table->n_entries -= 1;
00482 free_entry (table, entry);
00483 }
00484
00516 void
00517 _dbus_hash_iter_init (DBusHashTable *table,
00518 DBusHashIter *iter)
00519 {
00520 DBusRealHashIter *real;
00521
00522 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00523
00524 real = (DBusRealHashIter*) iter;
00525
00526 real->table = table;
00527 real->bucket = NULL;
00528 real->entry = NULL;
00529 real->next_entry = NULL;
00530 real->next_bucket = 0;
00531 real->n_entries_on_init = table->n_entries;
00532 }
00533
00542 dbus_bool_t
00543 _dbus_hash_iter_next (DBusHashIter *iter)
00544 {
00545 DBusRealHashIter *real;
00546
00547 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00548
00549 real = (DBusRealHashIter*) iter;
00550
00551
00552
00553
00554 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
00555
00556
00557
00558 while (real->next_entry == NULL)
00559 {
00560 if (real->next_bucket >= real->table->n_buckets)
00561 {
00562
00563 real->entry = NULL;
00564 real->table = NULL;
00565 real->bucket = NULL;
00566 return FALSE;
00567 }
00568
00569 real->bucket = &(real->table->buckets[real->next_bucket]);
00570 real->next_entry = *(real->bucket);
00571 real->next_bucket += 1;
00572 }
00573
00574 _dbus_assert (real->next_entry != NULL);
00575 _dbus_assert (real->bucket != NULL);
00576
00577 real->entry = real->next_entry;
00578 real->next_entry = real->entry->next;
00579
00580 return TRUE;
00581 }
00582
00591 void
00592 _dbus_hash_iter_remove_entry (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 _dbus_assert (real->bucket != NULL);
00601
00602 remove_entry (real->table, real->bucket, real->entry);
00603
00604 real->entry = NULL;
00605 }
00606
00612 void*
00613 _dbus_hash_iter_get_value (DBusHashIter *iter)
00614 {
00615 DBusRealHashIter *real;
00616
00617 real = (DBusRealHashIter*) iter;
00618
00619 _dbus_assert (real->table != NULL);
00620 _dbus_assert (real->entry != NULL);
00621
00622 return real->entry->value;
00623 }
00624
00635 void
00636 _dbus_hash_iter_set_value (DBusHashIter *iter,
00637 void *value)
00638 {
00639 DBusRealHashIter *real;
00640
00641 real = (DBusRealHashIter*) iter;
00642
00643 _dbus_assert (real->table != NULL);
00644 _dbus_assert (real->entry != NULL);
00645
00646 if (real->table->free_value_function && value != real->entry->value)
00647 (* real->table->free_value_function) (real->entry->value);
00648
00649 real->entry->value = value;
00650 }
00651
00658 int
00659 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
00660 {
00661 DBusRealHashIter *real;
00662
00663 real = (DBusRealHashIter*) iter;
00664
00665 _dbus_assert (real->table != NULL);
00666 _dbus_assert (real->entry != NULL);
00667
00668 return _DBUS_POINTER_TO_INT (real->entry->key);
00669 }
00670
00677 uintptr_t
00678 _dbus_hash_iter_get_uintptr_key (DBusHashIter *iter)
00679 {
00680 DBusRealHashIter *real;
00681
00682 real = (DBusRealHashIter*) iter;
00683
00684 _dbus_assert (real->table != NULL);
00685 _dbus_assert (real->entry != NULL);
00686
00687 return (uintptr_t) real->entry->key;
00688 }
00689
00695 const char*
00696 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
00697 {
00698 DBusRealHashIter *real;
00699
00700 real = (DBusRealHashIter*) iter;
00701
00702 _dbus_assert (real->table != NULL);
00703 _dbus_assert (real->entry != NULL);
00704
00705 return real->entry->key;
00706 }
00707
00739 dbus_bool_t
00740 _dbus_hash_iter_lookup (DBusHashTable *table,
00741 void *key,
00742 dbus_bool_t create_if_not_found,
00743 DBusHashIter *iter)
00744 {
00745 DBusRealHashIter *real;
00746 DBusHashEntry *entry;
00747 DBusHashEntry **bucket;
00748
00749 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
00750
00751 real = (DBusRealHashIter*) iter;
00752
00753 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
00754
00755 if (entry == NULL)
00756 return FALSE;
00757
00758 real->table = table;
00759 real->bucket = bucket;
00760 real->entry = entry;
00761 real->next_entry = entry->next;
00762 real->next_bucket = (bucket - table->buckets) + 1;
00763 real->n_entries_on_init = table->n_entries;
00764
00765 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
00766
00767 return TRUE;
00768 }
00769
00770 static void
00771 add_allocated_entry (DBusHashTable *table,
00772 DBusHashEntry *entry,
00773 unsigned int idx,
00774 void *key,
00775 DBusHashEntry ***bucket)
00776 {
00777 DBusHashEntry **b;
00778
00779 entry->key = key;
00780
00781 b = &(table->buckets[idx]);
00782 entry->next = *b;
00783 *b = entry;
00784
00785 if (bucket)
00786 *bucket = b;
00787
00788 table->n_entries += 1;
00789
00790
00791
00792
00793 if (table->n_entries >= table->hi_rebuild_size ||
00794 table->n_entries < table->lo_rebuild_size)
00795 rebuild_table (table);
00796 }
00797
00798 static DBusHashEntry*
00799 add_entry (DBusHashTable *table,
00800 unsigned int idx,
00801 void *key,
00802 DBusHashEntry ***bucket,
00803 DBusPreallocatedHash *preallocated)
00804 {
00805 DBusHashEntry *entry;
00806
00807 if (preallocated == NULL)
00808 {
00809 entry = alloc_entry (table);
00810 if (entry == NULL)
00811 {
00812 if (bucket)
00813 *bucket = NULL;
00814 return NULL;
00815 }
00816 }
00817 else
00818 {
00819 entry = (DBusHashEntry*) preallocated;
00820 }
00821
00822 add_allocated_entry (table, entry, idx, key, bucket);
00823
00824 return entry;
00825 }
00826
00827
00828
00829
00830 static unsigned int
00831 string_hash (const char *str)
00832 {
00833 const char *p = str;
00834 unsigned int h = *p;
00835
00836 if (h)
00837 for (p += 1; *p != '\0'; p++)
00838 h = (h << 5) - h + *p;
00839
00840 return h;
00841 }
00842
00844 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
00845
00846 static DBusHashEntry*
00847 find_generic_function (DBusHashTable *table,
00848 void *key,
00849 unsigned int idx,
00850 KeyCompareFunc compare_func,
00851 dbus_bool_t create_if_not_found,
00852 DBusHashEntry ***bucket,
00853 DBusPreallocatedHash *preallocated)
00854 {
00855 DBusHashEntry *entry;
00856
00857 if (bucket)
00858 *bucket = NULL;
00859
00860
00861 entry = table->buckets[idx];
00862 while (entry != NULL)
00863 {
00864 if ((compare_func == NULL && key == entry->key) ||
00865 (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
00866 {
00867 if (bucket)
00868 *bucket = &(table->buckets[idx]);
00869
00870 if (preallocated)
00871 _dbus_hash_table_free_preallocated_entry (table, preallocated);
00872
00873 return entry;
00874 }
00875
00876 entry = entry->next;
00877 }
00878
00879 if (create_if_not_found)
00880 entry = add_entry (table, idx, key, bucket, preallocated);
00881 else if (preallocated)
00882 _dbus_hash_table_free_preallocated_entry (table, preallocated);
00883
00884 return entry;
00885 }
00886
00887 static DBusHashEntry*
00888 find_string_function (DBusHashTable *table,
00889 void *key,
00890 dbus_bool_t create_if_not_found,
00891 DBusHashEntry ***bucket,
00892 DBusPreallocatedHash *preallocated)
00893 {
00894 unsigned int idx;
00895
00896 idx = string_hash (key) & table->mask;
00897
00898 return find_generic_function (table, key, idx,
00899 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
00900 preallocated);
00901 }
00902
00903 static DBusHashEntry*
00904 find_direct_function (DBusHashTable *table,
00905 void *key,
00906 dbus_bool_t create_if_not_found,
00907 DBusHashEntry ***bucket,
00908 DBusPreallocatedHash *preallocated)
00909 {
00910 unsigned int idx;
00911
00912 idx = RANDOM_INDEX (table, key) & table->mask;
00913
00914
00915 return find_generic_function (table, key, idx,
00916 NULL, create_if_not_found, bucket,
00917 preallocated);
00918 }
00919
00920 static void
00921 rebuild_table (DBusHashTable *table)
00922 {
00923 int old_size;
00924 int new_buckets;
00925 DBusHashEntry **old_buckets;
00926 DBusHashEntry **old_chain;
00927 DBusHashEntry *entry;
00928 dbus_bool_t growing;
00929
00930
00931
00932
00933
00934
00935 growing = table->n_entries >= table->hi_rebuild_size;
00936
00937 old_size = table->n_buckets;
00938 old_buckets = table->buckets;
00939
00940 if (growing)
00941 {
00942
00943 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
00944 table->down_shift >= 0)
00945 new_buckets = table->n_buckets * 4;
00946 else
00947 return;
00948 }
00949 else
00950 {
00951 new_buckets = table->n_buckets / 4;
00952 if (new_buckets < DBUS_SMALL_HASH_TABLE)
00953 return;
00954 }
00955
00956 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
00957 if (table->buckets == NULL)
00958 {
00959
00960
00961
00962 table->buckets = old_buckets;
00963 return;
00964 }
00965
00966 table->n_buckets = new_buckets;
00967
00968 if (growing)
00969 {
00970 table->lo_rebuild_size = table->hi_rebuild_size;
00971 table->hi_rebuild_size *= 4;
00972
00973 table->down_shift -= 2;
00974 table->mask = (table->mask << 2) + 3;
00975 }
00976 else
00977 {
00978 table->hi_rebuild_size = table->lo_rebuild_size;
00979 table->lo_rebuild_size /= 4;
00980
00981 table->down_shift += 2;
00982 table->mask = table->mask >> 2;
00983 }
00984
00985 #if 0
00986 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
00987 growing ? "GROW" : "SHRINK",
00988 table->lo_rebuild_size,
00989 table->hi_rebuild_size,
00990 table->down_shift,
00991 table->mask);
00992 #endif
00993
00994 _dbus_assert (table->lo_rebuild_size >= 0);
00995 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
00996 _dbus_assert (table->mask != 0);
00997
00998 _dbus_assert (table->mask < table->n_buckets);
00999
01000
01001
01002
01003
01004 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01005 {
01006 for (entry = *old_chain; entry != NULL; entry = *old_chain)
01007 {
01008 unsigned int idx;
01009 DBusHashEntry **bucket;
01010
01011 *old_chain = entry->next;
01012 switch (table->key_type)
01013 {
01014 case DBUS_HASH_STRING:
01015 idx = string_hash (entry->key) & table->mask;
01016 break;
01017 case DBUS_HASH_INT:
01018 case DBUS_HASH_UINTPTR:
01019 idx = RANDOM_INDEX (table, entry->key);
01020 break;
01021 default:
01022 idx = 0;
01023 _dbus_assert_not_reached ("Unknown hash table type");
01024 break;
01025 }
01026
01027 bucket = &(table->buckets[idx]);
01028 entry->next = *bucket;
01029 *bucket = entry;
01030 }
01031 }
01032
01033
01034
01035 if (old_buckets != table->static_buckets)
01036 dbus_free (old_buckets);
01037 }
01038
01048 void*
01049 _dbus_hash_table_lookup_string (DBusHashTable *table,
01050 const char *key)
01051 {
01052 DBusHashEntry *entry;
01053
01054 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01055
01056 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
01057
01058 if (entry)
01059 return entry->value;
01060 else
01061 return NULL;
01062 }
01063
01073 void*
01074 _dbus_hash_table_lookup_int (DBusHashTable *table,
01075 int key)
01076 {
01077 DBusHashEntry *entry;
01078
01079 _dbus_assert (table->key_type == DBUS_HASH_INT);
01080
01081 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
01082
01083 if (entry)
01084 return entry->value;
01085 else
01086 return NULL;
01087 }
01088
01098 void*
01099 _dbus_hash_table_lookup_uintptr (DBusHashTable *table,
01100 uintptr_t key)
01101 {
01102 DBusHashEntry *entry;
01103
01104 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01105
01106 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
01107
01108 if (entry)
01109 return entry->value;
01110 else
01111 return NULL;
01112 }
01113
01122 dbus_bool_t
01123 _dbus_hash_table_remove_string (DBusHashTable *table,
01124 const char *key)
01125 {
01126 DBusHashEntry *entry;
01127 DBusHashEntry **bucket;
01128
01129 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01130
01131 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
01132
01133 if (entry)
01134 {
01135 remove_entry (table, bucket, entry);
01136 return TRUE;
01137 }
01138 else
01139 return FALSE;
01140 }
01141
01150 dbus_bool_t
01151 _dbus_hash_table_remove_int (DBusHashTable *table,
01152 int key)
01153 {
01154 DBusHashEntry *entry;
01155 DBusHashEntry **bucket;
01156
01157 _dbus_assert (table->key_type == DBUS_HASH_INT);
01158
01159 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
01160
01161 if (entry)
01162 {
01163 remove_entry (table, bucket, entry);
01164 return TRUE;
01165 }
01166 else
01167 return FALSE;
01168 }
01169
01178 dbus_bool_t
01179 _dbus_hash_table_remove_uintptr (DBusHashTable *table,
01180 uintptr_t key)
01181 {
01182 DBusHashEntry *entry;
01183 DBusHashEntry **bucket;
01184
01185 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01186
01187 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
01188
01189 if (entry)
01190 {
01191 remove_entry (table, bucket, entry);
01192 return TRUE;
01193 }
01194 else
01195 return FALSE;
01196 }
01197
01213 dbus_bool_t
01214 _dbus_hash_table_insert_string (DBusHashTable *table,
01215 char *key,
01216 void *value)
01217 {
01218 DBusPreallocatedHash *preallocated;
01219
01220 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01221
01222 preallocated = _dbus_hash_table_preallocate_entry (table);
01223 if (preallocated == NULL)
01224 return FALSE;
01225
01226 _dbus_hash_table_insert_string_preallocated (table, preallocated,
01227 key, value);
01228
01229 return TRUE;
01230 }
01231
01247 dbus_bool_t
01248 _dbus_hash_table_insert_int (DBusHashTable *table,
01249 int key,
01250 void *value)
01251 {
01252 DBusHashEntry *entry;
01253
01254 _dbus_assert (table->key_type == DBUS_HASH_INT);
01255
01256 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
01257
01258 if (entry == NULL)
01259 return FALSE;
01260
01261 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
01262 (* table->free_key_function) (entry->key);
01263
01264 if (table->free_value_function && entry->value != value)
01265 (* table->free_value_function) (entry->value);
01266
01267 entry->key = _DBUS_INT_TO_POINTER (key);
01268 entry->value = value;
01269
01270 return TRUE;
01271 }
01272
01288 dbus_bool_t
01289 _dbus_hash_table_insert_uintptr (DBusHashTable *table,
01290 uintptr_t key,
01291 void *value)
01292 {
01293 DBusHashEntry *entry;
01294
01295 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
01296
01297 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
01298
01299 if (entry == NULL)
01300 return FALSE;
01301
01302 if (table->free_key_function && entry->key != (void*) key)
01303 (* table->free_key_function) (entry->key);
01304
01305 if (table->free_value_function && entry->value != value)
01306 (* table->free_value_function) (entry->value);
01307
01308 entry->key = (void*) key;
01309 entry->value = value;
01310
01311 return TRUE;
01312 }
01313
01321 DBusPreallocatedHash*
01322 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
01323 {
01324 DBusHashEntry *entry;
01325
01326 entry = alloc_entry (table);
01327
01328 return (DBusPreallocatedHash*) entry;
01329 }
01330
01338 void
01339 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table,
01340 DBusPreallocatedHash *preallocated)
01341 {
01342 DBusHashEntry *entry;
01343
01344 _dbus_assert (preallocated != NULL);
01345
01346 entry = (DBusHashEntry*) preallocated;
01347
01348
01349 _dbus_mem_pool_dealloc (table->entry_pool, entry);
01350 }
01351
01365 void
01366 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table,
01367 DBusPreallocatedHash *preallocated,
01368 char *key,
01369 void *value)
01370 {
01371 DBusHashEntry *entry;
01372
01373 _dbus_assert (table->key_type == DBUS_HASH_STRING);
01374 _dbus_assert (preallocated != NULL);
01375
01376 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
01377
01378 _dbus_assert (entry != NULL);
01379
01380 if (table->free_key_function && entry->key != key)
01381 (* table->free_key_function) (entry->key);
01382
01383 if (table->free_value_function && entry->value != value)
01384 (* table->free_value_function) (entry->value);
01385
01386 entry->key = key;
01387 entry->value = value;
01388 }
01389
01396 int
01397 _dbus_hash_table_get_n_entries (DBusHashTable *table)
01398 {
01399 return table->n_entries;
01400 }
01401
01404 #ifdef DBUS_BUILD_TESTS
01405 #include "dbus-test.h"
01406 #include <stdio.h>
01407
01408
01409
01410
01411
01412 static int
01413 count_entries (DBusHashTable *table)
01414 {
01415 DBusHashIter iter;
01416 int count;
01417
01418 count = 0;
01419 _dbus_hash_iter_init (table, &iter);
01420 while (_dbus_hash_iter_next (&iter))
01421 ++count;
01422
01423 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
01424
01425 return count;
01426 }
01427
01433 dbus_bool_t
01434 _dbus_hash_test (void)
01435 {
01436 int i;
01437 DBusHashTable *table1;
01438 DBusHashTable *table2;
01439 DBusHashTable *table3;
01440 DBusHashIter iter;
01441 #define N_HASH_KEYS 5000
01442 char **keys;
01443 dbus_bool_t ret = FALSE;
01444
01445 keys = dbus_new (char *, N_HASH_KEYS);
01446 if (keys == NULL)
01447 _dbus_assert_not_reached ("no memory");
01448
01449 for (i = 0; i < N_HASH_KEYS; i++)
01450 {
01451 keys[i] = dbus_malloc (128);
01452
01453 if (keys[i] == NULL)
01454 _dbus_assert_not_reached ("no memory");
01455 }
01456
01457 printf ("Computing test hash keys...\n");
01458 i = 0;
01459 while (i < N_HASH_KEYS)
01460 {
01461 int len;
01462
01463 len = sprintf (keys[i], "Hash key %d", i);
01464 _dbus_assert (*(keys[i] + len) == '\0');
01465 ++i;
01466 }
01467 printf ("... done.\n");
01468
01469 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01470 dbus_free, dbus_free);
01471 if (table1 == NULL)
01472 goto out;
01473
01474 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01475 NULL, dbus_free);
01476 if (table2 == NULL)
01477 goto out;
01478
01479 table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR,
01480 NULL, dbus_free);
01481 if (table3 == NULL)
01482 goto out;
01483
01484
01485
01486
01487 i = 0;
01488 while (i < 3000)
01489 {
01490 void *value;
01491 char *key;
01492
01493 key = _dbus_strdup (keys[i]);
01494 if (key == NULL)
01495 goto out;
01496 value = _dbus_strdup ("Value!");
01497 if (value == NULL)
01498 goto out;
01499
01500 if (!_dbus_hash_table_insert_string (table1,
01501 key, value))
01502 goto out;
01503
01504 value = _dbus_strdup (keys[i]);
01505 if (value == NULL)
01506 goto out;
01507
01508 if (!_dbus_hash_table_insert_int (table2,
01509 i, value))
01510 goto out;
01511
01512 value = _dbus_strdup (keys[i]);
01513 if (value == NULL)
01514 goto out;
01515
01516 if (!_dbus_hash_table_insert_uintptr (table3,
01517 i, value))
01518 goto out;
01519
01520 _dbus_assert (count_entries (table1) == i + 1);
01521 _dbus_assert (count_entries (table2) == i + 1);
01522 _dbus_assert (count_entries (table3) == i + 1);
01523
01524 value = _dbus_hash_table_lookup_string (table1, keys[i]);
01525 _dbus_assert (value != NULL);
01526 _dbus_assert (strcmp (value, "Value!") == 0);
01527
01528 value = _dbus_hash_table_lookup_int (table2, i);
01529 _dbus_assert (value != NULL);
01530 _dbus_assert (strcmp (value, keys[i]) == 0);
01531
01532 value = _dbus_hash_table_lookup_uintptr (table3, i);
01533 _dbus_assert (value != NULL);
01534 _dbus_assert (strcmp (value, keys[i]) == 0);
01535
01536 ++i;
01537 }
01538
01539 --i;
01540 while (i >= 0)
01541 {
01542 _dbus_hash_table_remove_string (table1,
01543 keys[i]);
01544
01545 _dbus_hash_table_remove_int (table2, i);
01546
01547 _dbus_hash_table_remove_uintptr (table3, i);
01548
01549 _dbus_assert (count_entries (table1) == i);
01550 _dbus_assert (count_entries (table2) == i);
01551 _dbus_assert (count_entries (table3) == i);
01552
01553 --i;
01554 }
01555
01556 _dbus_hash_table_ref (table1);
01557 _dbus_hash_table_ref (table2);
01558 _dbus_hash_table_ref (table3);
01559 _dbus_hash_table_unref (table1);
01560 _dbus_hash_table_unref (table2);
01561 _dbus_hash_table_unref (table3);
01562 _dbus_hash_table_unref (table1);
01563 _dbus_hash_table_unref (table2);
01564 _dbus_hash_table_unref (table3);
01565 table3 = NULL;
01566
01567
01568
01569
01570
01571 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01572 dbus_free, dbus_free);
01573 if (table1 == NULL)
01574 goto out;
01575
01576 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01577 NULL, dbus_free);
01578 if (table2 == NULL)
01579 goto out;
01580
01581 i = 0;
01582 while (i < 5000)
01583 {
01584 char *key;
01585 void *value;
01586
01587 key = _dbus_strdup (keys[i]);
01588 if (key == NULL)
01589 goto out;
01590 value = _dbus_strdup ("Value!");
01591 if (value == NULL)
01592 goto out;
01593
01594 if (!_dbus_hash_table_insert_string (table1,
01595 key, value))
01596 goto out;
01597
01598 value = _dbus_strdup (keys[i]);
01599 if (value == NULL)
01600 goto out;
01601
01602 if (!_dbus_hash_table_insert_int (table2,
01603 i, value))
01604 goto out;
01605
01606 _dbus_assert (count_entries (table1) == i + 1);
01607 _dbus_assert (count_entries (table2) == i + 1);
01608
01609 ++i;
01610 }
01611
01612 _dbus_hash_iter_init (table1, &iter);
01613 while (_dbus_hash_iter_next (&iter))
01614 {
01615 const char *key;
01616 void *value;
01617
01618 key = _dbus_hash_iter_get_string_key (&iter);
01619 value = _dbus_hash_iter_get_value (&iter);
01620
01621 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01622
01623 value = _dbus_strdup ("Different value!");
01624 if (value == NULL)
01625 goto out;
01626
01627 _dbus_hash_iter_set_value (&iter, value);
01628
01629 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
01630 }
01631
01632 _dbus_hash_iter_init (table1, &iter);
01633 while (_dbus_hash_iter_next (&iter))
01634 {
01635 _dbus_hash_iter_remove_entry (&iter);
01636 _dbus_assert (count_entries (table1) == i - 1);
01637 --i;
01638 }
01639
01640 _dbus_hash_iter_init (table2, &iter);
01641 while (_dbus_hash_iter_next (&iter))
01642 {
01643 int key;
01644 void *value;
01645
01646 key = _dbus_hash_iter_get_int_key (&iter);
01647 value = _dbus_hash_iter_get_value (&iter);
01648
01649 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01650
01651 value = _dbus_strdup ("Different value!");
01652 if (value == NULL)
01653 goto out;
01654
01655 _dbus_hash_iter_set_value (&iter, value);
01656
01657 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
01658 }
01659
01660 i = count_entries (table2);
01661 _dbus_hash_iter_init (table2, &iter);
01662 while (_dbus_hash_iter_next (&iter))
01663 {
01664 _dbus_hash_iter_remove_entry (&iter);
01665 _dbus_assert (count_entries (table2) + 1 == i);
01666 --i;
01667 }
01668
01669
01670
01671
01672 i = 0;
01673 while (i < 1000)
01674 {
01675 char *key;
01676 void *value;
01677
01678 key = _dbus_strdup (keys[i]);
01679 if (key == NULL)
01680 goto out;
01681
01682 value = _dbus_strdup ("Value!");
01683 if (value == NULL)
01684 goto out;
01685
01686 if (!_dbus_hash_table_insert_string (table1,
01687 key, value))
01688 goto out;
01689
01690 ++i;
01691 }
01692
01693 --i;
01694 while (i >= 0)
01695 {
01696 char *key;
01697 void *value;
01698
01699 key = _dbus_strdup (keys[i]);
01700 if (key == NULL)
01701 goto out;
01702 value = _dbus_strdup ("Value!");
01703 if (value == NULL)
01704 goto out;
01705
01706 if (!_dbus_hash_table_remove_string (table1, keys[i]))
01707 goto out;
01708
01709 if (!_dbus_hash_table_insert_string (table1,
01710 key, value))
01711 goto out;
01712
01713 if (!_dbus_hash_table_remove_string (table1, keys[i]))
01714 goto out;
01715
01716 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
01717
01718 --i;
01719 }
01720
01721
01722 _dbus_hash_table_unref (table1);
01723 _dbus_hash_table_unref (table2);
01724
01725
01726
01727
01728
01729 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
01730 dbus_free, dbus_free);
01731 if (table1 == NULL)
01732 goto out;
01733
01734 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
01735 NULL, dbus_free);
01736 if (table2 == NULL)
01737 goto out;
01738
01739 i = 0;
01740 while (i < 3000)
01741 {
01742 void *value;
01743 char *key;
01744
01745 key = _dbus_strdup (keys[i]);
01746 if (key == NULL)
01747 goto out;
01748 value = _dbus_strdup ("Value!");
01749 if (value == NULL)
01750 goto out;
01751
01752 if (!_dbus_hash_iter_lookup (table1,
01753 key, TRUE, &iter))
01754 goto out;
01755 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
01756 _dbus_hash_iter_set_value (&iter, value);
01757
01758 value = _dbus_strdup (keys[i]);
01759 if (value == NULL)
01760 goto out;
01761
01762 if (!_dbus_hash_iter_lookup (table2,
01763 _DBUS_INT_TO_POINTER (i), TRUE, &iter))
01764 goto out;
01765 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
01766 _dbus_hash_iter_set_value (&iter, value);
01767
01768 _dbus_assert (count_entries (table1) == i + 1);
01769 _dbus_assert (count_entries (table2) == i + 1);
01770
01771 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
01772 goto out;
01773
01774 value = _dbus_hash_iter_get_value (&iter);
01775 _dbus_assert (value != NULL);
01776 _dbus_assert (strcmp (value, "Value!") == 0);
01777
01778
01779
01780
01781 while (_dbus_hash_iter_next (&iter))
01782 ;
01783
01784 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
01785 goto out;
01786
01787 value = _dbus_hash_iter_get_value (&iter);
01788 _dbus_assert (value != NULL);
01789 _dbus_assert (strcmp (value, keys[i]) == 0);
01790
01791
01792
01793
01794 while (_dbus_hash_iter_next (&iter))
01795 ;
01796
01797 ++i;
01798 }
01799
01800 --i;
01801 while (i >= 0)
01802 {
01803 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
01804 _dbus_assert_not_reached ("hash entry should have existed");
01805 _dbus_hash_iter_remove_entry (&iter);
01806
01807 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
01808 _dbus_assert_not_reached ("hash entry should have existed");
01809 _dbus_hash_iter_remove_entry (&iter);
01810
01811 _dbus_assert (count_entries (table1) == i);
01812 _dbus_assert (count_entries (table2) == i);
01813
01814 --i;
01815 }
01816
01817 _dbus_hash_table_unref (table1);
01818 _dbus_hash_table_unref (table2);
01819
01820 ret = TRUE;
01821
01822 out:
01823 for (i = 0; i < N_HASH_KEYS; i++)
01824 dbus_free (keys[i]);
01825
01826 dbus_free (keys);
01827
01828 return ret;
01829 }
01830
01831 #endif