1 /* -*- mode: C; c-file-style: "gnu" -*- */
2 /* dbus-hash.c Generic hash table utility (internal to D-BUS implementation)
4 * Copyright (C) 2002 Red Hat, Inc.
5 * Copyright (c) 1991-1993 The Regents of the University of California.
6 * Copyright (c) 1994 Sun Microsystems, Inc.
8 * Hash table implementation based on generic/tclHash.c from the Tcl
9 * source code. The original Tcl license applies to portions of the
10 * code from tclHash.c; the Tcl license follows this standad D-BUS
11 * license information.
13 * Licensed under the Academic Free License version 1.2
15 * This program is free software; you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation; either version 2 of the License, or
18 * (at your option) any later version.
20 * This program is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
25 * You should have received a copy of the GNU General Public License
26 * along with this program; if not, write to the Free Software
27 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
31 * The following copyright applies to code from the Tcl distribution.
33 * Copyright (c) 1991-1993 The Regents of the University of California.
34 * Copyright (c) 1994 Sun Microsystems, Inc.
36 * This software is copyrighted by the Regents of the University of
37 * California, Sun Microsystems, Inc., Scriptics Corporation, and
38 * other parties. The following terms apply to all files associated
39 * with the software unless explicitly disclaimed in individual files.
41 * The authors hereby grant permission to use, copy, modify,
42 * distribute, and license this software and its documentation for any
43 * purpose, provided that existing copyright notices are retained in
44 * all copies and that this notice is included verbatim in any
45 * distributions. No written agreement, license, or royalty fee is
46 * required for any of the authorized uses. Modifications to this
47 * software may be copyrighted by their authors and need not follow
48 * the licensing terms described here, provided that the new terms are
49 * clearly indicated on the first page of each file where they apply.
51 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
52 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
53 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
54 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
55 * OF THE POSSIBILITY OF SUCH DAMAGE.
57 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
58 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
59 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
60 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
61 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
62 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
64 * GOVERNMENT USE: If you are acquiring this software on behalf of the
65 * U.S. government, the Government shall have only "Restricted Rights"
66 * in the software and related documentation as defined in the Federal
67 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you
68 * are acquiring the software on behalf of the Department of Defense,
69 * the software shall be classified as "Commercial Computer Software"
70 * and the Government shall have only "Restricted Rights" as defined
71 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the
72 * foregoing, the authors grant the U.S. Government and others acting
73 * in its behalf permission to use and distribute the software in
74 * accordance with the terms specified in this license.
77 #include "dbus-hash.h"
78 #include "dbus-internals.h"
79 #include "dbus-mempool.h"
82 * @defgroup DBusHashTable Hash table
83 * @ingroup DBusInternals
84 * @brief DBusHashTable data structure
86 * Types and functions related to DBusHashTable.
90 * @defgroup DBusHashTableInternals Hash table implementation details
91 * @ingroup DBusInternals
92 * @brief DBusHashTable implementation details
94 * The guts of DBusHashTable.
100 * When there are this many entries per bucket, on average, rebuild
101 * the hash table to make it larger.
103 #define REBUILD_MULTIPLIER 3
106 * Takes a preliminary integer hash value and produces an index into a
107 * hash tables bucket list. The idea is to make it so that
108 * preliminary values that are arbitrarily similar will end up in
109 * different buckets. The hash function was taken from a
110 * random-number generator. (This is used to hash integers.)
112 * The down_shift drops off the high bits of the hash index, and
113 * decreases as we increase the number of hash buckets (to keep more
114 * range in the hash index). The mask also strips high bits and strips
115 * fewer high bits as the number of hash buckets increases.
116 * I don't understand two things: why is the initial downshift 28
117 * to keep 4 bits when the initial mask is 011 to keep 2 bits,
118 * and why do we have both a mask and a downshift?
121 #define RANDOM_INDEX(table, i) \
122 (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
125 * Initial number of buckets in hash table (hash table statically
126 * allocates its buckets for this size and below).
127 * The initial mask has to be synced to this.
129 #define DBUS_SMALL_HASH_TABLE 4
132 * Typedef for DBusHashEntry
134 typedef struct DBusHashEntry DBusHashEntry;
137 * @brief Internal representation of a hash entry.
139 * A single entry (key-value pair) in the hash table.
140 * Internal to hash table implementation.
144 DBusHashEntry *next; /**< Pointer to next entry in this
145 * hash bucket, or #NULL for end of
148 void *key; /**< Hash key */
149 void *value; /**< Hash value */
153 * Function used to find and optionally create a hash entry.
155 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
157 dbus_bool_t create_if_not_found,
158 DBusHashEntry ***bucket);
161 * @brief Internals of DBusHashTable.
163 * Hash table internals. Hash tables are opaque objects, they must be
164 * used via accessor functions.
166 struct DBusHashTable {
167 int refcount; /**< Reference count */
169 DBusHashEntry **buckets; /**< Pointer to bucket array. Each
170 * element points to first entry in
171 * bucket's hash chain, or #NULL.
173 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
174 /**< Bucket array used for small tables
175 * (to avoid mallocs and frees).
177 int n_buckets; /**< Total number of buckets allocated
180 int n_entries; /**< Total number of entries present
183 int hi_rebuild_size; /**< Enlarge table when n_entries gets
186 int lo_rebuild_size; /**< Shrink table when n_entries gets
189 int down_shift; /**< Shift count used in hashing
190 * function. Designed to use high-
191 * order bits of randomized keys.
193 int mask; /**< Mask value used in hashing
196 DBusHashType key_type; /**< Type of keys used in this table */
199 DBusFindEntryFunction find_function; /**< Function for finding entries */
201 DBusFreeFunction free_key_function; /**< Function to free keys */
202 DBusFreeFunction free_value_function; /**< Function to free values */
204 DBusMemPool *entry_pool; /**< Memory pool for hash entries */
208 * @brief Internals of DBusHashIter.
212 DBusHashTable *table; /**< Pointer to table containing entry. */
213 DBusHashEntry **bucket; /**< Pointer to bucket that points to
214 * first entry in this entry's chain:
215 * used for deleting the entry.
217 DBusHashEntry *entry; /**< Current hash entry */
218 DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
219 int next_bucket; /**< index of next bucket */
220 int n_entries_on_init; /**< used to detect table resize since initialization */
223 static DBusHashEntry* find_direct_function (DBusHashTable *table,
225 dbus_bool_t create_if_not_found,
226 DBusHashEntry ***bucket);
227 static DBusHashEntry* find_string_function (DBusHashTable *table,
229 dbus_bool_t create_if_not_found,
230 DBusHashEntry ***bucket);
231 static unsigned int string_hash (const char *str);
232 static void rebuild_table (DBusHashTable *table);
233 static DBusHashEntry* alloc_entry (DBusHashTable *table);
234 static void remove_entry (DBusHashTable *table,
235 DBusHashEntry **bucket,
236 DBusHashEntry *entry);
237 static void free_entry (DBusHashTable *table,
238 DBusHashEntry *entry);
239 static void free_entry_data (DBusHashTable *table,
240 DBusHashEntry *entry);
245 * @addtogroup DBusHashTable
250 * @typedef DBusHashIter
252 * Public opaque hash table iterator object.
256 * @typedef DBusHashTable
258 * Public opaque hash table object.
262 * @typedef DBusHashType
264 * Indicates the type of a key in the hash table.
268 * Constructs a new hash table. Should be freed with
269 * _dbus_hash_table_unref(). If memory cannot be
270 * allocated for the hash table, returns #NULL.
272 * @param type the type of hash key to use.
273 * @param key_free_function function to free hash keys.
274 * @param value_free_function function to free hash values.
275 * @returns a new DBusHashTable or #NULL if no memory.
278 _dbus_hash_table_new (DBusHashType type,
279 DBusFreeFunction key_free_function,
280 DBusFreeFunction value_free_function)
282 DBusHashTable *table;
283 DBusMemPool *entry_pool;
285 table = dbus_new0 (DBusHashTable, 1);
289 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
290 if (entry_pool == NULL)
297 table->entry_pool = entry_pool;
299 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
301 table->buckets = table->static_buckets;
302 table->n_buckets = DBUS_SMALL_HASH_TABLE;
303 table->n_entries = 0;
304 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
305 table->lo_rebuild_size = 0;
306 table->down_shift = 28;
308 table->key_type = type;
310 _dbus_assert (table->mask < table->n_buckets);
312 switch (table->key_type)
315 case DBUS_HASH_POINTER:
316 table->find_function = find_direct_function;
318 case DBUS_HASH_STRING:
319 table->find_function = find_string_function;
322 _dbus_assert_not_reached ("Unknown hash table type");
326 table->free_key_function = key_free_function;
327 table->free_value_function = value_free_function;
334 * Increments the reference count for a hash table.
336 * @param table the hash table to add a reference to.
339 _dbus_hash_table_ref (DBusHashTable *table)
341 table->refcount += 1;
345 * Decrements the reference count for a hash table,
346 * freeing the hash table if the count reaches zero.
348 * @param table the hash table to remove a reference from.
351 _dbus_hash_table_unref (DBusHashTable *table)
353 table->refcount -= 1;
355 if (table->refcount == 0)
358 DBusHashEntry *entry;
362 /* Free the entries in the table. */
363 for (i = 0; i < table->n_buckets; i++)
365 entry = table->buckets[i];
366 while (entry != NULL)
370 free_entry (table, entry);
376 DBusHashEntry *entry;
379 /* Free the entries in the table. */
380 for (i = 0; i < table->n_buckets; i++)
382 entry = table->buckets[i];
383 while (entry != NULL)
385 free_entry_data (table, entry);
390 /* We can do this very quickly with memory pools ;-) */
391 _dbus_mem_pool_free (table->entry_pool);
394 /* Free the bucket array, if it was dynamically allocated. */
395 if (table->buckets != table->static_buckets)
396 dbus_free (table->buckets);
402 static DBusHashEntry*
403 alloc_entry (DBusHashTable *table)
405 DBusHashEntry *entry;
407 entry = _dbus_mem_pool_alloc (table->entry_pool);
413 free_entry_data (DBusHashTable *table,
414 DBusHashEntry *entry)
416 if (table->free_key_function)
417 (* table->free_key_function) (entry->key);
418 if (table->free_value_function)
419 (* table->free_value_function) (entry->value);
423 free_entry (DBusHashTable *table,
424 DBusHashEntry *entry)
426 free_entry_data (table, entry);
427 _dbus_mem_pool_dealloc (table->entry_pool, entry);
431 remove_entry (DBusHashTable *table,
432 DBusHashEntry **bucket,
433 DBusHashEntry *entry)
435 _dbus_assert (table != NULL);
436 _dbus_assert (bucket != NULL);
437 _dbus_assert (*bucket != NULL);
438 _dbus_assert (entry != NULL);
440 if (*bucket == entry)
441 *bucket = entry->next;
447 while (prev->next != entry)
450 _dbus_assert (prev != NULL);
452 prev->next = entry->next;
455 table->n_entries -= 1;
456 free_entry (table, entry);
460 * Initializes a hash table iterator. To iterate over all entries in a
461 * hash table, use the following code (the printf assumes a hash
462 * from strings to strings obviously):
467 * _dbus_hash_iter_init (table, &iter);
468 * while (_dbus_hash_iter_next (&iter))
470 * printf ("The first key is %s and value is %s\n",
471 * _dbus_hash_iter_get_string_key (&iter),
472 * _dbus_hash_iter_get_value (&iter));
478 * The iterator is initialized pointing "one before" the first hash
479 * entry. The first call to _dbus_hash_iter_next() moves it onto
480 * the first valid entry or returns #FALSE if the hash table is
481 * empty. Subsequent calls move to the next valid entry or return
482 * #FALSE if there are no more entries.
484 * Note that it is guaranteed to be safe to remove a hash entry during
485 * iteration, but it is not safe to add a hash entry.
487 * @param table the hash table to iterate over.
488 * @param iter the iterator to initialize.
491 _dbus_hash_iter_init (DBusHashTable *table,
494 DBusRealHashIter *real;
496 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
498 real = (DBusRealHashIter*) iter;
503 real->next_entry = NULL;
504 real->next_bucket = 0;
505 real->n_entries_on_init = table->n_entries;
509 * Move the hash iterator forward one step, to the next hash entry.
510 * The documentation for _dbus_hash_iter_init() explains in more
513 * @param iter the iterator to move forward.
514 * @returns #FALSE if there are no more entries to move to.
517 _dbus_hash_iter_next (DBusHashIter *iter)
519 DBusRealHashIter *real;
521 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
523 real = (DBusRealHashIter*) iter;
525 /* if this assertion failed someone probably added hash entries
526 * during iteration, which is bad.
528 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
530 /* Remember that real->entry may have been deleted */
532 while (real->next_entry == NULL)
534 if (real->next_bucket >= real->table->n_buckets)
536 /* invalidate iter and return false */
543 real->bucket = &(real->table->buckets[real->next_bucket]);
544 real->next_entry = *(real->bucket);
545 real->next_bucket += 1;
548 _dbus_assert (real->next_entry != NULL);
549 _dbus_assert (real->bucket != NULL);
551 real->entry = real->next_entry;
552 real->next_entry = real->entry->next;
558 * Removes the current entry from the hash table.
559 * If a key_free_function or value_free_function
560 * was provided to _dbus_hash_table_new(),
561 * frees the key and/or value for this entry.
563 * @param iter the hash table iterator.
566 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
568 DBusRealHashIter *real;
570 real = (DBusRealHashIter*) iter;
572 _dbus_assert (real->table != NULL);
573 _dbus_assert (real->entry != NULL);
574 _dbus_assert (real->bucket != NULL);
576 remove_entry (real->table, real->bucket, real->entry);
578 real->entry = NULL; /* make it crash if you try to use this entry */
582 * Gets the value of the current entry.
584 * @param iter the hash table iterator.
587 _dbus_hash_iter_get_value (DBusHashIter *iter)
589 DBusRealHashIter *real;
591 real = (DBusRealHashIter*) iter;
593 _dbus_assert (real->table != NULL);
594 _dbus_assert (real->entry != NULL);
596 return real->entry->value;
600 * Sets the value of the current entry.
601 * If the hash table has a value_free_function
602 * it will be used to free the previous value.
603 * The hash table will own the passed-in value
604 * (it will not be copied).
606 * @param iter the hash table iterator.
607 * @param value the new value.
610 _dbus_hash_iter_set_value (DBusHashIter *iter,
613 DBusRealHashIter *real;
615 real = (DBusRealHashIter*) iter;
617 _dbus_assert (real->table != NULL);
618 _dbus_assert (real->entry != NULL);
620 if (real->table->free_value_function && value != real->entry->value)
621 (* real->table->free_value_function) (real->entry->value);
623 real->entry->value = value;
627 * Gets the key for the current entry.
628 * Only works for hash tables of type #DBUS_HASH_INT.
630 * @param iter the hash table iterator.
633 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
635 DBusRealHashIter *real;
637 real = (DBusRealHashIter*) iter;
639 _dbus_assert (real->table != NULL);
640 _dbus_assert (real->entry != NULL);
642 return _DBUS_POINTER_TO_INT (real->entry->key);
646 * Gets the key for the current entry.
647 * Only works for hash tables of type #DBUS_HASH_STRING
648 * @param iter the hash table iterator.
651 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
653 DBusRealHashIter *real;
655 real = (DBusRealHashIter*) iter;
657 _dbus_assert (real->table != NULL);
658 _dbus_assert (real->entry != NULL);
660 return real->entry->key;
664 * A low-level but efficient interface for manipulating the hash
665 * table. It's efficient because you can get, set, and optionally
666 * create the hash entry while only running the hash function one
669 * Note that while calling _dbus_hash_iter_next() on the iterator
670 * filled in by this function may work, it's completely
671 * undefined which entries are after this iter and which
672 * are before it. So it would be silly to iterate using this
675 * If the hash entry is created, its value will be initialized
678 * #FALSE may be returned due to memory allocation failure, or
679 * because create_if_not_found was #FALSE and the entry
682 * If create_if_not_found is #TRUE and the entry is created, the hash
683 * table takes ownership of the key that's passed in.
685 * For a hash table of type #DBUS_HASH_INT, cast the int
686 * key to the key parameter using #_DBUS_INT_TO_POINTER().
688 * @param table the hash table.
689 * @param key the hash key.
690 * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
691 * @param iter the iterator to initialize.
692 * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
695 _dbus_hash_iter_lookup (DBusHashTable *table,
697 dbus_bool_t create_if_not_found,
700 DBusRealHashIter *real;
701 DBusHashEntry *entry;
702 DBusHashEntry **bucket;
704 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
706 real = (DBusRealHashIter*) iter;
708 entry = (* table->find_function) (table, key, create_if_not_found, &bucket);
714 real->bucket = bucket;
716 real->next_entry = entry->next;
717 real->next_bucket = (bucket - table->buckets) + 1;
718 real->n_entries_on_init = table->n_entries;
720 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
725 static DBusHashEntry*
726 add_entry (DBusHashTable *table,
729 DBusHashEntry ***bucket)
731 DBusHashEntry *entry;
734 entry = alloc_entry (table);
744 b = &(table->buckets[idx]);
751 table->n_entries += 1;
753 /* note we ONLY rebuild when ADDING - because you can iterate over a
754 * table and remove entries safely.
756 if (table->n_entries >= table->hi_rebuild_size ||
757 table->n_entries < table->lo_rebuild_size)
758 rebuild_table (table);
764 string_hash (const char *str)
766 register unsigned int result;
770 * I tried a zillion different hash functions and asked many other
771 * people for advice. Many people had their own favorite functions,
772 * all different, but no-one had much idea why they were good ones.
773 * I chose the one below (multiply by 9 and add new character)
774 * because of the following reasons:
776 * 1. Multiplying by 10 is perfect for keys that are decimal strings,
777 * and multiplying by 9 is just about as good.
778 * 2. Times-9 is (shift-left-3) plus (old). This means that each
779 * character's bits hang around in the low-order bits of the
780 * hash value for ever, plus they spread fairly rapidly up to
781 * the high-order bits to fill out the hash value. This seems
782 * works well both for decimal and non-decimal strings.
793 result += (result << 3) + c;
799 static DBusHashEntry*
800 find_string_function (DBusHashTable *table,
802 dbus_bool_t create_if_not_found,
803 DBusHashEntry ***bucket)
805 DBusHashEntry *entry;
811 idx = string_hash (key) & table->mask;
813 /* Search all of the entries in this bucket. */
814 entry = table->buckets[idx];
815 while (entry != NULL)
817 if (strcmp (key, entry->key) == 0)
820 *bucket = &(table->buckets[idx]);
827 if (create_if_not_found)
828 entry = add_entry (table, idx, key, bucket);
833 static DBusHashEntry*
834 find_direct_function (DBusHashTable *table,
836 dbus_bool_t create_if_not_found,
837 DBusHashEntry ***bucket)
839 DBusHashEntry *entry;
845 idx = RANDOM_INDEX (table, key) & table->mask;
847 /* Search all of the entries in this bucket. */
848 entry = table->buckets[idx];
849 while (entry != NULL)
851 if (key == entry->key)
854 *bucket = &(table->buckets[idx]);
861 /* Entry not found. Add a new one to the bucket. */
862 if (create_if_not_found)
863 entry = add_entry (table, idx, key, bucket);
869 rebuild_table (DBusHashTable *table)
873 DBusHashEntry **old_buckets;
874 DBusHashEntry **old_chain;
875 DBusHashEntry *entry;
879 * Allocate and initialize the new bucket array, and set up
880 * hashing constants for new array size.
883 growing = table->n_entries >= table->hi_rebuild_size;
885 old_size = table->n_buckets;
886 old_buckets = table->buckets;
890 /* overflow paranoia */
891 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
892 table->down_shift >= 0)
893 new_buckets = table->n_buckets * 4;
895 return; /* can't grow anymore */
899 new_buckets = table->n_buckets / 4;
900 if (new_buckets < DBUS_SMALL_HASH_TABLE)
901 return; /* don't bother shrinking this far */
904 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
905 if (table->buckets == NULL)
907 /* out of memory, yay - just don't reallocate, the table will
908 * still work, albeit more slowly.
910 table->buckets = old_buckets;
914 table->n_buckets = new_buckets;
918 table->lo_rebuild_size = table->hi_rebuild_size;
919 table->hi_rebuild_size *= 4;
921 table->down_shift -= 2; /* keep 2 more high bits */
922 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
926 table->hi_rebuild_size = table->lo_rebuild_size;
927 table->lo_rebuild_size /= 4;
929 table->down_shift += 2; /* keep 2 fewer high bits */
930 table->mask = table->mask >> 2; /* keep 2 fewer high bits */
934 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
935 growing ? "GROW" : "SHRINK",
936 table->lo_rebuild_size,
937 table->hi_rebuild_size,
942 _dbus_assert (table->lo_rebuild_size >= 0);
943 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
944 _dbus_assert (table->mask != 0);
945 /* the mask is essentially the max index */
946 _dbus_assert (table->mask < table->n_buckets);
949 * Rehash all of the existing entries into the new bucket array.
952 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
954 for (entry = *old_chain; entry != NULL; entry = *old_chain)
957 DBusHashEntry **bucket;
959 *old_chain = entry->next;
960 switch (table->key_type)
962 case DBUS_HASH_STRING:
963 idx = string_hash (entry->key) & table->mask;
966 case DBUS_HASH_POINTER:
967 idx = RANDOM_INDEX (table, entry->key);
971 _dbus_assert_not_reached ("Unknown hash table type");
975 bucket = &(table->buckets[idx]);
976 entry->next = *bucket;
981 /* Free the old bucket array, if it was dynamically allocated. */
983 if (old_buckets != table->static_buckets)
984 dbus_free (old_buckets);
988 * Looks up the value for a given string in a hash table
989 * of type #DBUS_HASH_STRING. Returns %NULL if the value
990 * is not present. (A not-present entry is indistinguishable
991 * from an entry with a value of %NULL.)
992 * @param table the hash table.
993 * @param key the string to look up.
994 * @returns the value of the hash entry.
997 _dbus_hash_table_lookup_string (DBusHashTable *table,
1000 DBusHashEntry *entry;
1002 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1004 entry = (* table->find_function) (table, (char*) key, FALSE, NULL);
1007 return entry->value;
1013 * Looks up the value for a given integer in a hash table
1014 * of type #DBUS_HASH_INT. Returns %NULL if the value
1015 * is not present. (A not-present entry is indistinguishable
1016 * from an entry with a value of %NULL.)
1017 * @param table the hash table.
1018 * @param key the integer to look up.
1019 * @returns the value of the hash entry.
1022 _dbus_hash_table_lookup_int (DBusHashTable *table,
1025 DBusHashEntry *entry;
1027 _dbus_assert (table->key_type == DBUS_HASH_INT);
1029 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL);
1032 return entry->value;
1038 * Looks up the value for a given integer in a hash table
1039 * of type #DBUS_HASH_POINTER. Returns %NULL if the value
1040 * is not present. (A not-present entry is indistinguishable
1041 * from an entry with a value of %NULL.)
1042 * @param table the hash table.
1043 * @param key the integer to look up.
1044 * @returns the value of the hash entry.
1047 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
1050 DBusHashEntry *entry;
1052 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1054 entry = (* table->find_function) (table, key, FALSE, NULL);
1057 return entry->value;
1063 * Removes the hash entry for the given key. If no hash entry
1064 * for the key exists, does nothing.
1066 * @param table the hash table.
1067 * @param key the hash key.
1068 * @returns #TRUE if the entry existed
1071 _dbus_hash_table_remove_string (DBusHashTable *table,
1074 DBusHashEntry *entry;
1075 DBusHashEntry **bucket;
1077 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1079 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket);
1083 remove_entry (table, bucket, entry);
1091 * Removes the hash entry for the given key. If no hash entry
1092 * for the key exists, does nothing.
1094 * @param table the hash table.
1095 * @param key the hash key.
1096 * @returns #TRUE if the entry existed
1099 _dbus_hash_table_remove_int (DBusHashTable *table,
1102 DBusHashEntry *entry;
1103 DBusHashEntry **bucket;
1105 _dbus_assert (table->key_type == DBUS_HASH_INT);
1107 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket);
1111 remove_entry (table, bucket, entry);
1119 * Removes the hash entry for the given key. If no hash entry
1120 * for the key exists, does nothing.
1122 * @param table the hash table.
1123 * @param key the hash key.
1124 * @returns #TRUE if the entry existed
1127 _dbus_hash_table_remove_pointer (DBusHashTable *table,
1130 DBusHashEntry *entry;
1131 DBusHashEntry **bucket;
1133 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1135 entry = (* table->find_function) (table, key, FALSE, &bucket);
1139 remove_entry (table, bucket, entry);
1148 * Creates a hash entry with the given key and value.
1149 * The key and value are not copied; they are stored
1150 * in the hash table by reference. If an entry with the
1151 * given key already exists, the previous key and value
1152 * are overwritten (and freed if the hash table has
1153 * a key_free_function and/or value_free_function).
1155 * Returns #FALSE if memory for the new hash entry
1156 * can't be allocated.
1158 * @param table the hash table.
1159 * @param key the hash entry key.
1160 * @param value the hash entry value.
1163 _dbus_hash_table_insert_string (DBusHashTable *table,
1167 DBusHashEntry *entry;
1169 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1171 entry = (* table->find_function) (table, key, TRUE, NULL);
1174 return FALSE; /* no memory */
1176 if (table->free_key_function && entry->key != key)
1177 (* table->free_key_function) (entry->key);
1179 if (table->free_value_function && entry->value != value)
1180 (* table->free_value_function) (entry->value);
1183 entry->value = value;
1189 * Creates a hash entry with the given key and value.
1190 * The key and value are not copied; they are stored
1191 * in the hash table by reference. If an entry with the
1192 * given key already exists, the previous key and value
1193 * are overwritten (and freed if the hash table has
1194 * a key_free_function and/or value_free_function).
1196 * Returns #FALSE if memory for the new hash entry
1197 * can't be allocated.
1199 * @param table the hash table.
1200 * @param key the hash entry key.
1201 * @param value the hash entry value.
1204 _dbus_hash_table_insert_int (DBusHashTable *table,
1208 DBusHashEntry *entry;
1210 _dbus_assert (table->key_type == DBUS_HASH_INT);
1212 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL);
1215 return FALSE; /* no memory */
1217 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1218 (* table->free_key_function) (entry->key);
1220 if (table->free_value_function && entry->value != value)
1221 (* table->free_value_function) (entry->value);
1223 entry->key = _DBUS_INT_TO_POINTER (key);
1224 entry->value = value;
1230 * Creates a hash entry with the given key and value.
1231 * The key and value are not copied; they are stored
1232 * in the hash table by reference. If an entry with the
1233 * given key already exists, the previous key and value
1234 * are overwritten (and freed if the hash table has
1235 * a key_free_function and/or value_free_function).
1237 * Returns #FALSE if memory for the new hash entry
1238 * can't be allocated.
1240 * @param table the hash table.
1241 * @param key the hash entry key.
1242 * @param value the hash entry value.
1245 _dbus_hash_table_insert_pointer (DBusHashTable *table,
1249 DBusHashEntry *entry;
1251 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1253 entry = (* table->find_function) (table, key, TRUE, NULL);
1256 return FALSE; /* no memory */
1258 if (table->free_key_function && entry->key != key)
1259 (* table->free_key_function) (entry->key);
1261 if (table->free_value_function && entry->value != value)
1262 (* table->free_value_function) (entry->value);
1265 entry->value = value;
1271 * Gets the number of hash entries in a hash table.
1273 * @param table the hash table.
1274 * @returns the number of entries in the table.
1277 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1279 return table->n_entries;
1284 #ifdef DBUS_BUILD_TESTS
1285 #include "dbus-test.h"
1288 /* If you're wondering why the hash table test takes
1289 * forever to run, it's because we call this function
1290 * in inner loops thus making things quadratic.
1293 count_entries (DBusHashTable *table)
1299 _dbus_hash_iter_init (table, &iter);
1300 while (_dbus_hash_iter_next (&iter))
1303 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1309 * @ingroup DBusHashTableInternals
1310 * Unit test for DBusHashTable
1311 * @returns #TRUE on success.
1314 _dbus_hash_test (void)
1317 DBusHashTable *table1;
1318 DBusHashTable *table2;
1320 #define N_HASH_KEYS 5000
1322 dbus_bool_t ret = FALSE;
1324 keys = dbus_new (char *, N_HASH_KEYS);
1326 _dbus_assert_not_reached ("no memory");
1328 for (i = 0; i < N_HASH_KEYS; i++)
1330 keys[i] = dbus_malloc (128);
1332 if (keys[i] == NULL)
1333 _dbus_assert_not_reached ("no memory");
1336 printf ("Computing test hash keys...\n");
1338 while (i < N_HASH_KEYS)
1340 sprintf (keys[i], "Hash key %d", i);
1343 printf ("... done.\n");
1345 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1346 dbus_free, dbus_free);
1350 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1355 /* Insert and remove a bunch of stuff, counting the table in between
1356 * to be sure it's not broken and that iteration works
1364 key = _dbus_strdup (keys[i]);
1367 value = _dbus_strdup ("Value!");
1371 if (!_dbus_hash_table_insert_string (table1,
1375 value = _dbus_strdup (keys[i]);
1379 if (!_dbus_hash_table_insert_int (table2,
1383 _dbus_assert (count_entries (table1) == i + 1);
1384 _dbus_assert (count_entries (table2) == i + 1);
1386 value = _dbus_hash_table_lookup_string (table1, keys[i]);
1387 _dbus_assert (value != NULL);
1388 _dbus_assert (strcmp (value, "Value!") == 0);
1390 value = _dbus_hash_table_lookup_int (table2, i);
1391 _dbus_assert (value != NULL);
1392 _dbus_assert (strcmp (value, keys[i]) == 0);
1400 _dbus_hash_table_remove_string (table1,
1403 _dbus_hash_table_remove_int (table2, i);
1405 _dbus_assert (count_entries (table1) == i);
1406 _dbus_assert (count_entries (table2) == i);
1411 _dbus_hash_table_ref (table1);
1412 _dbus_hash_table_ref (table2);
1413 _dbus_hash_table_unref (table1);
1414 _dbus_hash_table_unref (table2);
1415 _dbus_hash_table_unref (table1);
1416 _dbus_hash_table_unref (table2);
1419 /* Insert a bunch of stuff then check
1420 * that iteration works correctly (finds the right
1421 * values, iter_set_value works, etc.)
1423 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1424 dbus_free, dbus_free);
1428 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1439 key = _dbus_strdup (keys[i]);
1442 value = _dbus_strdup ("Value!");
1446 if (!_dbus_hash_table_insert_string (table1,
1450 value = _dbus_strdup (keys[i]);
1454 if (!_dbus_hash_table_insert_int (table2,
1458 _dbus_assert (count_entries (table1) == i + 1);
1459 _dbus_assert (count_entries (table2) == i + 1);
1464 _dbus_hash_iter_init (table1, &iter);
1465 while (_dbus_hash_iter_next (&iter))
1470 key = _dbus_hash_iter_get_string_key (&iter);
1471 value = _dbus_hash_iter_get_value (&iter);
1473 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1475 value = _dbus_strdup ("Different value!");
1479 _dbus_hash_iter_set_value (&iter, value);
1481 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1484 _dbus_hash_iter_init (table1, &iter);
1485 while (_dbus_hash_iter_next (&iter))
1487 _dbus_hash_iter_remove_entry (&iter);
1488 _dbus_assert (count_entries (table1) == i - 1);
1492 _dbus_hash_iter_init (table2, &iter);
1493 while (_dbus_hash_iter_next (&iter))
1498 key = _dbus_hash_iter_get_int_key (&iter);
1499 value = _dbus_hash_iter_get_value (&iter);
1501 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1503 value = _dbus_strdup ("Different value!");
1507 _dbus_hash_iter_set_value (&iter, value);
1509 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1512 i = count_entries (table2);
1513 _dbus_hash_iter_init (table2, &iter);
1514 while (_dbus_hash_iter_next (&iter))
1516 _dbus_hash_iter_remove_entry (&iter);
1517 _dbus_assert (count_entries (table2) + 1 == i);
1521 /* add/remove interleaved, to check that we grow/shrink the table
1530 key = _dbus_strdup (keys[i]);
1534 value = _dbus_strdup ("Value!");
1538 if (!_dbus_hash_table_insert_string (table1,
1551 key = _dbus_strdup (keys[i]);
1554 value = _dbus_strdup ("Value!");
1558 if (!_dbus_hash_table_remove_string (table1, keys[i]))
1561 if (!_dbus_hash_table_insert_string (table1,
1565 if (!_dbus_hash_table_remove_string (table1, keys[i]))
1568 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
1573 /* nuke these tables */
1574 _dbus_hash_table_unref (table1);
1575 _dbus_hash_table_unref (table2);
1578 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1579 * be sure that interface works.
1581 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1582 dbus_free, dbus_free);
1586 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1597 key = _dbus_strdup (keys[i]);
1600 value = _dbus_strdup ("Value!");
1604 if (!_dbus_hash_iter_lookup (table1,
1607 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1608 _dbus_hash_iter_set_value (&iter, value);
1610 value = _dbus_strdup (keys[i]);
1614 if (!_dbus_hash_iter_lookup (table2,
1615 _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1617 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1618 _dbus_hash_iter_set_value (&iter, value);
1620 _dbus_assert (count_entries (table1) == i + 1);
1621 _dbus_assert (count_entries (table2) == i + 1);
1623 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1626 value = _dbus_hash_iter_get_value (&iter);
1627 _dbus_assert (value != NULL);
1628 _dbus_assert (strcmp (value, "Value!") == 0);
1630 /* Iterate just to be sure it works, though
1631 * it's a stupid thing to do
1633 while (_dbus_hash_iter_next (&iter))
1636 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1639 value = _dbus_hash_iter_get_value (&iter);
1640 _dbus_assert (value != NULL);
1641 _dbus_assert (strcmp (value, keys[i]) == 0);
1643 /* Iterate just to be sure it works, though
1644 * it's a stupid thing to do
1646 while (_dbus_hash_iter_next (&iter))
1655 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1656 _dbus_assert_not_reached ("hash entry should have existed");
1657 _dbus_hash_iter_remove_entry (&iter);
1659 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1660 _dbus_assert_not_reached ("hash entry should have existed");
1661 _dbus_hash_iter_remove_entry (&iter);
1663 _dbus_assert (count_entries (table1) == i);
1664 _dbus_assert (count_entries (table2) == i);
1669 _dbus_hash_table_unref (table1);
1670 _dbus_hash_table_unref (table2);
1675 for (i = 0; i < N_HASH_KEYS; i++)
1676 dbus_free (keys[i]);
1683 #endif /* DBUS_BUILD_TESTS */