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_int_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);
243 * @addtogroup DBusHashTable
248 * @typedef DBusHashIter
250 * Public opaque hash table iterator object.
254 * @typedef DBusHashTable
256 * Public opaque hash table object.
260 * @typedef DBusHashType
262 * Indicates the type of a key in the hash table.
266 * Constructs a new hash table. Should be freed with
267 * _dbus_hash_table_unref(). If memory cannot be
268 * allocated for the hash table, returns #NULL.
270 * @param type the type of hash key to use.
271 * @param key_free_function function to free hash keys.
272 * @param value_free_function function to free hash values.
273 * @returns a new DBusHashTable or #NULL if no memory.
276 _dbus_hash_table_new (DBusHashType type,
277 DBusFreeFunction key_free_function,
278 DBusFreeFunction value_free_function)
280 DBusHashTable *table;
281 DBusMemPool *entry_pool;
283 table = dbus_new0 (DBusHashTable, 1);
287 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
288 if (entry_pool == NULL)
295 table->entry_pool = entry_pool;
297 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
299 table->buckets = table->static_buckets;
300 table->n_buckets = DBUS_SMALL_HASH_TABLE;
301 table->n_entries = 0;
302 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
303 table->lo_rebuild_size = 0;
304 table->down_shift = 28;
306 table->key_type = type;
308 _dbus_assert (table->mask < table->n_buckets);
310 switch (table->key_type)
313 table->find_function = find_int_function;
315 case DBUS_HASH_STRING:
316 table->find_function = find_string_function;
319 _dbus_assert_not_reached ("Unknown hash table type");
323 table->free_key_function = key_free_function;
324 table->free_value_function = value_free_function;
331 * Increments the reference count for a hash table.
333 * @param table the hash table to add a reference to.
336 _dbus_hash_table_ref (DBusHashTable *table)
338 table->refcount += 1;
342 * Decrements the reference count for a hash table,
343 * freeing the hash table if the count reaches zero.
345 * @param table the hash table to remove a reference from.
348 _dbus_hash_table_unref (DBusHashTable *table)
350 table->refcount -= 1;
352 if (table->refcount == 0)
355 DBusHashEntry *entry;
359 /* Free the entries in the table. */
360 for (i = 0; i < table->n_buckets; i++)
362 entry = table->buckets[i];
363 while (entry != NULL)
367 free_entry (table, entry);
373 /* We can do this very quickly with memory pools ;-) */
374 _dbus_mem_pool_free (table->entry_pool);
377 /* Free the bucket array, if it was dynamically allocated. */
378 if (table->buckets != table->static_buckets)
379 dbus_free (table->buckets);
385 static DBusHashEntry*
386 alloc_entry (DBusHashTable *table)
388 DBusHashEntry *entry;
390 entry = _dbus_mem_pool_alloc (table->entry_pool);
396 free_entry (DBusHashTable *table,
397 DBusHashEntry *entry)
399 if (table->free_key_function)
400 (* table->free_key_function) (entry->key);
401 if (table->free_value_function)
402 (* table->free_value_function) (entry->value);
404 _dbus_mem_pool_dealloc (table->entry_pool, entry);
408 remove_entry (DBusHashTable *table,
409 DBusHashEntry **bucket,
410 DBusHashEntry *entry)
412 _dbus_assert (table != NULL);
413 _dbus_assert (bucket != NULL);
414 _dbus_assert (*bucket != NULL);
415 _dbus_assert (entry != NULL);
417 if (*bucket == entry)
418 *bucket = entry->next;
424 while (prev->next != entry)
427 _dbus_assert (prev != NULL);
429 prev->next = entry->next;
432 table->n_entries -= 1;
433 free_entry (table, entry);
437 * Initializes a hash table iterator. To iterate over all entries in a
438 * hash table, use the following code (the printf assumes a hash
439 * from strings to strings obviously):
444 * _dbus_hash_iter_init (table, &iter);
445 * while (_dbus_hash_iter_next (&iter))
447 * printf ("The first key is %s and value is %s\n",
448 * _dbus_hash_iter_get_string_key (&iter),
449 * _dbus_hash_iter_get_value (&iter));
455 * The iterator is initialized pointing "one before" the first hash
456 * entry. The first call to _dbus_hash_iter_next() moves it onto
457 * the first valid entry or returns #FALSE if the hash table is
458 * empty. Subsequent calls move to the next valid entry or return
459 * #FALSE if there are no more entries.
461 * Note that it is guaranteed to be safe to remove a hash entry during
462 * iteration, but it is not safe to add a hash entry.
464 * @param table the hash table to iterate over.
465 * @param iter the iterator to initialize.
468 _dbus_hash_iter_init (DBusHashTable *table,
471 DBusRealHashIter *real;
473 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
475 real = (DBusRealHashIter*) iter;
480 real->next_entry = NULL;
481 real->next_bucket = 0;
482 real->n_entries_on_init = table->n_entries;
486 * Move the hash iterator forward one step, to the next hash entry.
487 * The documentation for _dbus_hash_iter_init() explains in more
490 * @param iter the iterator to move forward.
491 * @returns #FALSE if there are no more entries to move to.
494 _dbus_hash_iter_next (DBusHashIter *iter)
496 DBusRealHashIter *real;
498 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
500 real = (DBusRealHashIter*) iter;
502 /* if this assertion failed someone probably added hash entries
503 * during iteration, which is bad.
505 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
507 /* Remember that real->entry may have been deleted */
509 while (real->next_entry == NULL)
511 if (real->next_bucket >= real->table->n_buckets)
513 /* invalidate iter and return false */
520 real->bucket = &(real->table->buckets[real->next_bucket]);
521 real->next_entry = *(real->bucket);
522 real->next_bucket += 1;
525 _dbus_assert (real->next_entry != NULL);
526 _dbus_assert (real->bucket != NULL);
528 real->entry = real->next_entry;
529 real->next_entry = real->entry->next;
535 * Removes the current entry from the hash table.
536 * If a key_free_function or value_free_function
537 * was provided to _dbus_hash_table_new(),
538 * frees the key and/or value for this entry.
540 * @param iter the hash table iterator.
543 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
545 DBusRealHashIter *real;
547 real = (DBusRealHashIter*) iter;
549 _dbus_assert (real->table != NULL);
550 _dbus_assert (real->entry != NULL);
551 _dbus_assert (real->bucket != NULL);
553 remove_entry (real->table, real->bucket, real->entry);
555 real->entry = NULL; /* make it crash if you try to use this entry */
559 * Gets the value of the current entry.
561 * @param iter the hash table iterator.
564 _dbus_hash_iter_get_value (DBusHashIter *iter)
566 DBusRealHashIter *real;
568 real = (DBusRealHashIter*) iter;
570 _dbus_assert (real->table != NULL);
571 _dbus_assert (real->entry != NULL);
573 return real->entry->value;
577 * Sets the value of the current entry.
578 * If the hash table has a value_free_function
579 * it will be used to free the previous value.
580 * The hash table will own the passed-in value
581 * (it will not be copied).
583 * @param iter the hash table iterator.
584 * @param value the new value.
587 _dbus_hash_iter_set_value (DBusHashIter *iter,
590 DBusRealHashIter *real;
592 real = (DBusRealHashIter*) iter;
594 _dbus_assert (real->table != NULL);
595 _dbus_assert (real->entry != NULL);
597 if (real->table->free_value_function && value != real->entry->value)
598 (* real->table->free_value_function) (real->entry->value);
600 real->entry->value = value;
604 * Gets the key for the current entry.
605 * Only works for hash tables of type #DBUS_HASH_INT.
607 * @param iter the hash table iterator.
610 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
612 DBusRealHashIter *real;
614 real = (DBusRealHashIter*) iter;
616 _dbus_assert (real->table != NULL);
617 _dbus_assert (real->entry != NULL);
619 return _DBUS_POINTER_TO_INT (real->entry->key);
623 * Gets the key for the current entry.
624 * Only works for hash tables of type #DBUS_HASH_STRING
625 * @param iter the hash table iterator.
628 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
630 DBusRealHashIter *real;
632 real = (DBusRealHashIter*) iter;
634 _dbus_assert (real->table != NULL);
635 _dbus_assert (real->entry != NULL);
637 return real->entry->key;
641 * A low-level but efficient interface for manipulating the hash
642 * table. It's efficient because you can get, set, and optionally
643 * create the hash entry while only running the hash function one
646 * Note that while calling _dbus_hash_iter_next() on the iterator
647 * filled in by this function may work, it's completely
648 * undefined which entries are after this iter and which
649 * are before it. So it would be silly to iterate using this
652 * If the hash entry is created, its value will be initialized
655 * #FALSE may be returned due to memory allocation failure, or
656 * because create_if_not_found was #FALSE and the entry
659 * If create_if_not_found is #TRUE and the entry is created, the hash
660 * table takes ownership of the key that's passed in.
662 * For a hash table of type #DBUS_HASH_INT, cast the int
663 * key to the key parameter using #_DBUS_INT_TO_POINTER().
665 * @param table the hash table.
666 * @param key the hash key.
667 * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
668 * @param iter the iterator to initialize.
669 * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
672 _dbus_hash_iter_lookup (DBusHashTable *table,
674 dbus_bool_t create_if_not_found,
677 DBusRealHashIter *real;
678 DBusHashEntry *entry;
679 DBusHashEntry **bucket;
681 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
683 real = (DBusRealHashIter*) iter;
685 entry = (* table->find_function) (table, key, create_if_not_found, &bucket);
691 real->bucket = bucket;
693 real->next_entry = entry->next;
694 real->next_bucket = (bucket - table->buckets) + 1;
695 real->n_entries_on_init = table->n_entries;
697 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
702 static DBusHashEntry*
703 add_entry (DBusHashTable *table,
706 DBusHashEntry ***bucket)
708 DBusHashEntry *entry;
711 entry = alloc_entry (table);
721 b = &(table->buckets[idx]);
728 table->n_entries += 1;
730 /* note we ONLY rebuild when ADDING - because you can iterate over a
731 * table and remove entries safely.
733 if (table->n_entries >= table->hi_rebuild_size ||
734 table->n_entries < table->lo_rebuild_size)
735 rebuild_table (table);
741 string_hash (const char *str)
743 register unsigned int result;
747 * I tried a zillion different hash functions and asked many other
748 * people for advice. Many people had their own favorite functions,
749 * all different, but no-one had much idea why they were good ones.
750 * I chose the one below (multiply by 9 and add new character)
751 * because of the following reasons:
753 * 1. Multiplying by 10 is perfect for keys that are decimal strings,
754 * and multiplying by 9 is just about as good.
755 * 2. Times-9 is (shift-left-3) plus (old). This means that each
756 * character's bits hang around in the low-order bits of the
757 * hash value for ever, plus they spread fairly rapidly up to
758 * the high-order bits to fill out the hash value. This seems
759 * works well both for decimal and non-decimal strings.
770 result += (result << 3) + c;
776 static DBusHashEntry*
777 find_string_function (DBusHashTable *table,
779 dbus_bool_t create_if_not_found,
780 DBusHashEntry ***bucket)
782 DBusHashEntry *entry;
788 idx = string_hash (key) & table->mask;
790 /* Search all of the entries in this bucket. */
791 entry = table->buckets[idx];
792 while (entry != NULL)
794 if (strcmp (key, entry->key) == 0)
797 *bucket = &(table->buckets[idx]);
804 if (create_if_not_found)
805 entry = add_entry (table, idx, key, bucket);
810 static DBusHashEntry*
811 find_int_function (DBusHashTable *table,
813 dbus_bool_t create_if_not_found,
814 DBusHashEntry ***bucket)
816 DBusHashEntry *entry;
822 idx = RANDOM_INDEX (table, key) & table->mask;
824 /* Search all of the entries in this bucket. */
825 entry = table->buckets[idx];
826 while (entry != NULL)
828 if (key == entry->key)
831 *bucket = &(table->buckets[idx]);
838 /* Entry not found. Add a new one to the bucket. */
839 if (create_if_not_found)
840 entry = add_entry (table, idx, key, bucket);
846 rebuild_table (DBusHashTable *table)
850 DBusHashEntry **old_buckets;
851 DBusHashEntry **old_chain;
852 DBusHashEntry *entry;
856 * Allocate and initialize the new bucket array, and set up
857 * hashing constants for new array size.
860 growing = table->n_entries >= table->hi_rebuild_size;
862 old_size = table->n_buckets;
863 old_buckets = table->buckets;
867 /* overflow paranoia */
868 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
869 table->down_shift >= 0)
870 new_buckets = table->n_buckets * 4;
872 return; /* can't grow anymore */
876 new_buckets = table->n_buckets / 4;
877 if (new_buckets < DBUS_SMALL_HASH_TABLE)
878 return; /* don't bother shrinking this far */
881 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
882 if (table->buckets == NULL)
884 /* out of memory, yay - just don't reallocate, the table will
885 * still work, albeit more slowly.
887 table->buckets = old_buckets;
891 table->n_buckets = new_buckets;
895 table->lo_rebuild_size = table->hi_rebuild_size;
896 table->hi_rebuild_size *= 4;
898 table->down_shift -= 2; /* keep 2 more high bits */
899 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
903 table->hi_rebuild_size = table->lo_rebuild_size;
904 table->lo_rebuild_size /= 4;
906 table->down_shift += 2; /* keep 2 fewer high bits */
907 table->mask = table->mask >> 2; /* keep 2 fewer high bits */
911 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
912 growing ? "GROW" : "SHRINK",
913 table->lo_rebuild_size,
914 table->hi_rebuild_size,
919 _dbus_assert (table->lo_rebuild_size >= 0);
920 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
921 _dbus_assert (table->mask != 0);
922 /* the mask is essentially the max index */
923 _dbus_assert (table->mask < table->n_buckets);
926 * Rehash all of the existing entries into the new bucket array.
929 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
931 for (entry = *old_chain; entry != NULL; entry = *old_chain)
934 DBusHashEntry **bucket;
936 *old_chain = entry->next;
937 switch (table->key_type)
939 case DBUS_HASH_STRING:
940 idx = string_hash (entry->key) & table->mask;
943 idx = RANDOM_INDEX (table, entry->key);
947 _dbus_assert_not_reached ("Unknown hash table type");
951 bucket = &(table->buckets[idx]);
952 entry->next = *bucket;
957 /* Free the old bucket array, if it was dynamically allocated. */
959 if (old_buckets != table->static_buckets)
960 dbus_free (old_buckets);
964 * Looks up the value for a given string in a hash table
965 * of type #DBUS_HASH_STRING. Returns %NULL if the value
966 * is not present. (A not-present entry is indistinguishable
967 * from an entry with a value of %NULL.)
968 * @param table the hash table.
969 * @param key the string to look up.
970 * @returns the value of the hash entry.
973 _dbus_hash_table_lookup_string (DBusHashTable *table,
976 DBusHashEntry *entry;
978 _dbus_assert (table->key_type == DBUS_HASH_STRING);
980 entry = (* table->find_function) (table, (char*) key, FALSE, NULL);
989 * Looks up the value for a given integer in a hash table
990 * of type #DBUS_HASH_INT. Returns %NULL if the value
991 * is not present. (A not-present entry is indistinguishable
992 * from an entry with a value of %NULL.)
993 * @param table the hash table.
994 * @param key the integer to look up.
995 * @returns the value of the hash entry.
998 _dbus_hash_table_lookup_int (DBusHashTable *table,
1001 DBusHashEntry *entry;
1003 _dbus_assert (table->key_type == DBUS_HASH_INT);
1005 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL);
1008 return entry->value;
1014 * Removes the hash entry for the given key. If no hash entry
1015 * for the key exists, does nothing.
1017 * @param table the hash table.
1018 * @param key the hash key.
1019 * @returns #TRUE if the entry existed
1022 _dbus_hash_table_remove_string (DBusHashTable *table,
1025 DBusHashEntry *entry;
1026 DBusHashEntry **bucket;
1028 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1030 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket);
1034 remove_entry (table, bucket, entry);
1042 * Removes the hash entry for the given key. If no hash entry
1043 * for the key exists, does nothing.
1045 * @param table the hash table.
1046 * @param key the hash key.
1047 * @returns #TRUE if the entry existed
1050 _dbus_hash_table_remove_int (DBusHashTable *table,
1053 DBusHashEntry *entry;
1054 DBusHashEntry **bucket;
1056 _dbus_assert (table->key_type == DBUS_HASH_INT);
1058 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket);
1062 remove_entry (table, bucket, entry);
1070 * Creates a hash entry with the given key and value.
1071 * The key and value are not copied; they are stored
1072 * in the hash table by reference. If an entry with the
1073 * given key already exists, the previous key and value
1074 * are overwritten (and freed if the hash table has
1075 * a key_free_function and/or value_free_function).
1077 * Returns #FALSE if memory for the new hash entry
1078 * can't be allocated.
1080 * @param table the hash table.
1081 * @param key the hash entry key.
1082 * @param value the hash entry value.
1085 _dbus_hash_table_insert_string (DBusHashTable *table,
1089 DBusHashEntry *entry;
1091 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1093 entry = (* table->find_function) (table, key, TRUE, NULL);
1096 return FALSE; /* no memory */
1098 if (table->free_key_function && entry->key != key)
1099 (* table->free_key_function) (entry->key);
1101 if (table->free_value_function && entry->value != value)
1102 (* table->free_value_function) (entry->value);
1105 entry->value = value;
1111 * Creates a hash entry with the given key and value.
1112 * The key and value are not copied; they are stored
1113 * in the hash table by reference. If an entry with the
1114 * given key already exists, the previous key and value
1115 * are overwritten (and freed if the hash table has
1116 * a key_free_function and/or value_free_function).
1118 * Returns #FALSE if memory for the new hash entry
1119 * can't be allocated.
1121 * @param table the hash table.
1122 * @param key the hash entry key.
1123 * @param value the hash entry value.
1126 _dbus_hash_table_insert_int (DBusHashTable *table,
1130 DBusHashEntry *entry;
1132 _dbus_assert (table->key_type == DBUS_HASH_INT);
1134 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL);
1137 return FALSE; /* no memory */
1139 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1140 (* table->free_key_function) (entry->key);
1142 if (table->free_value_function && entry->value != value)
1143 (* table->free_value_function) (entry->value);
1145 entry->key = _DBUS_INT_TO_POINTER (key);
1146 entry->value = value;
1152 * Gets the number of hash entries in a hash table.
1154 * @param table the hash table.
1155 * @returns the number of entries in the table.
1158 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1160 return table->n_entries;
1165 #ifdef DBUS_BUILD_TESTS
1166 #include "dbus-test.h"
1169 /* If you're wondering why the hash table test takes
1170 * forever to run, it's because we call this function
1171 * in inner loops thus making things quadratic.
1174 count_entries (DBusHashTable *table)
1180 _dbus_hash_iter_init (table, &iter);
1181 while (_dbus_hash_iter_next (&iter))
1184 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1190 * @ingroup DBusHashTableInternals
1191 * Unit test for DBusHashTable
1192 * @returns #TRUE on success.
1195 _dbus_hash_test (void)
1198 DBusHashTable *table1;
1199 DBusHashTable *table2;
1201 #define N_HASH_KEYS 5000
1202 char keys[N_HASH_KEYS][128];
1204 printf ("Computing test hash keys...\n");
1206 while (i < N_HASH_KEYS)
1208 sprintf (keys[i], "Hash key %d", i);
1211 printf ("... done.\n");
1213 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1214 dbus_free, dbus_free);
1218 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1223 /* Insert and remove a bunch of stuff, counting the table in between
1224 * to be sure it's not broken and that iteration works
1232 key = _dbus_strdup (keys[i]);
1235 value = _dbus_strdup ("Value!");
1239 if (!_dbus_hash_table_insert_string (table1,
1243 value = _dbus_strdup (keys[i]);
1247 if (!_dbus_hash_table_insert_int (table2,
1251 _dbus_assert (count_entries (table1) == i + 1);
1252 _dbus_assert (count_entries (table2) == i + 1);
1254 value = _dbus_hash_table_lookup_string (table1, keys[i]);
1255 _dbus_assert (value != NULL);
1256 _dbus_assert (strcmp (value, "Value!") == 0);
1258 value = _dbus_hash_table_lookup_int (table2, i);
1259 _dbus_assert (value != NULL);
1260 _dbus_assert (strcmp (value, keys[i]) == 0);
1268 _dbus_hash_table_remove_string (table1,
1271 _dbus_hash_table_remove_int (table2, i);
1273 _dbus_assert (count_entries (table1) == i);
1274 _dbus_assert (count_entries (table2) == i);
1279 _dbus_hash_table_ref (table1);
1280 _dbus_hash_table_ref (table2);
1281 _dbus_hash_table_unref (table1);
1282 _dbus_hash_table_unref (table2);
1283 _dbus_hash_table_unref (table1);
1284 _dbus_hash_table_unref (table2);
1287 /* Insert a bunch of stuff then check
1288 * that iteration works correctly (finds the right
1289 * values, iter_set_value works, etc.)
1291 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1292 dbus_free, dbus_free);
1296 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1307 key = _dbus_strdup (keys[i]);
1310 value = _dbus_strdup ("Value!");
1314 if (!_dbus_hash_table_insert_string (table1,
1318 value = _dbus_strdup (keys[i]);
1322 if (!_dbus_hash_table_insert_int (table2,
1326 _dbus_assert (count_entries (table1) == i + 1);
1327 _dbus_assert (count_entries (table2) == i + 1);
1332 _dbus_hash_iter_init (table1, &iter);
1333 while (_dbus_hash_iter_next (&iter))
1338 key = _dbus_hash_iter_get_string_key (&iter);
1339 value = _dbus_hash_iter_get_value (&iter);
1341 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1343 value = _dbus_strdup ("Different value!");
1347 _dbus_hash_iter_set_value (&iter, value);
1349 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1352 _dbus_hash_iter_init (table1, &iter);
1353 while (_dbus_hash_iter_next (&iter))
1355 _dbus_hash_iter_remove_entry (&iter);
1356 _dbus_assert (count_entries (table1) == i - 1);
1360 _dbus_hash_iter_init (table2, &iter);
1361 while (_dbus_hash_iter_next (&iter))
1366 key = _dbus_hash_iter_get_int_key (&iter);
1367 value = _dbus_hash_iter_get_value (&iter);
1369 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1371 value = _dbus_strdup ("Different value!");
1375 _dbus_hash_iter_set_value (&iter, value);
1377 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1380 i = count_entries (table2);
1381 _dbus_hash_iter_init (table2, &iter);
1382 while (_dbus_hash_iter_next (&iter))
1384 _dbus_hash_iter_remove_entry (&iter);
1385 _dbus_assert (count_entries (table2) + 1 == i);
1389 /* add/remove interleaved, to check that we grow/shrink the table
1398 key = _dbus_strdup (keys[i]);
1402 value = _dbus_strdup ("Value!");
1406 if (!_dbus_hash_table_insert_string (table1,
1419 key = _dbus_strdup (keys[i]);
1422 value = _dbus_strdup ("Value!");
1426 if (!_dbus_hash_table_remove_string (table1, keys[i]))
1429 if (!_dbus_hash_table_insert_string (table1,
1433 if (!_dbus_hash_table_remove_string (table1, keys[i]))
1436 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
1441 /* nuke these tables */
1442 _dbus_hash_table_unref (table1);
1443 _dbus_hash_table_unref (table2);
1446 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1447 * be sure that interface works.
1449 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1450 dbus_free, dbus_free);
1454 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1465 key = _dbus_strdup (keys[i]);
1468 value = _dbus_strdup ("Value!");
1472 if (!_dbus_hash_iter_lookup (table1,
1475 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1476 _dbus_hash_iter_set_value (&iter, value);
1478 value = _dbus_strdup (keys[i]);
1482 if (!_dbus_hash_iter_lookup (table2,
1483 _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1485 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1486 _dbus_hash_iter_set_value (&iter, value);
1488 _dbus_assert (count_entries (table1) == i + 1);
1489 _dbus_assert (count_entries (table2) == i + 1);
1491 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1494 value = _dbus_hash_iter_get_value (&iter);
1495 _dbus_assert (value != NULL);
1496 _dbus_assert (strcmp (value, "Value!") == 0);
1498 /* Iterate just to be sure it works, though
1499 * it's a stupid thing to do
1501 while (_dbus_hash_iter_next (&iter))
1504 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1507 value = _dbus_hash_iter_get_value (&iter);
1508 _dbus_assert (value != NULL);
1509 _dbus_assert (strcmp (value, keys[i]) == 0);
1511 /* Iterate just to be sure it works, though
1512 * it's a stupid thing to do
1514 while (_dbus_hash_iter_next (&iter))
1523 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1524 _dbus_assert_not_reached ("hash entry should have existed");
1525 _dbus_hash_iter_remove_entry (&iter);
1527 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1528 _dbus_assert_not_reached ("hash entry should have existed");
1529 _dbus_hash_iter_remove_entry (&iter);
1531 _dbus_assert (count_entries (table1) == i);
1532 _dbus_assert (count_entries (table2) == i);
1537 _dbus_hash_table_unref (table1);
1538 _dbus_hash_table_unref (table2);
1544 #endif /* DBUS_BUILD_TESTS */