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"
81 * @defgroup DBusHashTable Hash table
82 * @ingroup DBusInternals
83 * @brief DBusHashTable data structure
85 * Types and functions related to DBusHashTable.
89 * @defgroup DBusHashTableInternals Hash table implementation details
90 * @ingroup DBusInternals
91 * @brief DBusHashTable implementation details
93 * The guts of DBusHashTable.
99 * When there are this many entries per bucket, on average, rebuild
100 * the hash table to make it larger.
102 #define REBUILD_MULTIPLIER 3
105 * Takes a preliminary integer hash value and produces an index into a
106 * hash tables bucket list. The idea is to make it so that
107 * preliminary values that are arbitrarily similar will end up in
108 * different buckets. The hash function was taken from a
109 * random-number generator. (This is used to hash integers.)
111 #define RANDOM_INDEX(table, i) \
112 (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
115 * Initial number of buckets in hash table (hash table statically
116 * allocates its buckets for this size and below).
118 #define DBUS_SMALL_HASH_TABLE 4
121 * Typedef for DBusHashEntry
123 typedef struct DBusHashEntry DBusHashEntry;
126 * @brief Internal representation of a hash entry.
128 * A single entry (key-value pair) in the hash table.
129 * Internal to hash table implementation.
133 DBusHashEntry *next; /**< Pointer to next entry in this
134 * hash bucket, or #NULL for end of
137 void *key; /**< Hash key */
138 void *value; /**< Hash value */
142 * Function used to find and optionally create a hash entry.
144 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
146 dbus_bool_t create_if_not_found,
147 DBusHashEntry ***bucket);
150 * @brief Internals of DBusHashTable.
152 * Hash table internals. Hash tables are opaque objects, they must be
153 * used via accessor functions.
155 struct DBusHashTable {
156 int refcount; /**< Reference count */
158 DBusHashEntry **buckets; /**< Pointer to bucket array. Each
159 * element points to first entry in
160 * bucket's hash chain, or #NULL.
162 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
163 /**< Bucket array used for small tables
164 * (to avoid mallocs and frees).
166 int n_buckets; /**< Total number of buckets allocated
169 int n_entries; /**< Total number of entries present
172 int rebuild_size; /**< Enlarge table when numEntries gets
175 int down_shift; /**< Shift count used in hashing
176 * function. Designed to use high-
177 * order bits of randomized keys.
179 int mask; /**< Mask value used in hashing
182 DBusHashType key_type; /**< Type of keys used in this table */
185 DBusFindEntryFunction find_function; /**< Function for finding entries */
187 DBusFreeFunction free_key_function; /**< Function to free keys */
188 DBusFreeFunction free_value_function; /**< Function to free values */
192 * @brief Internals of DBusHashIter.
196 DBusHashTable *table; /**< Pointer to table containing entry. */
197 DBusHashEntry **bucket; /**< Pointer to bucket that points to
198 * first entry in this entry's chain:
199 * used for deleting the entry.
201 DBusHashEntry *entry; /**< Current hash entry */
202 DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
203 int next_bucket; /**< index of next bucket */
204 int n_entries_on_init; /**< used to detect table resize since initialization */
207 static DBusHashEntry* find_int_function (DBusHashTable *table,
209 dbus_bool_t create_if_not_found,
210 DBusHashEntry ***bucket);
211 static DBusHashEntry* find_string_function (DBusHashTable *table,
213 dbus_bool_t create_if_not_found,
214 DBusHashEntry ***bucket);
215 static unsigned int string_hash (const char *str);
216 static void rebuild_table (DBusHashTable *table);
217 static DBusHashEntry* alloc_entry (DBusHashTable *table);
218 static void remove_entry (DBusHashTable *table,
219 DBusHashEntry **bucket,
220 DBusHashEntry *entry);
221 static void free_entry (DBusHashTable *table,
222 DBusHashEntry *entry);
227 * @addtogroup DBusHashTable
232 * @typedef DBusHashIter
234 * Public opaque hash table iterator object.
238 * @typedef DBusHashTable
240 * Public opaque hash table object.
244 * @typedef DBusHashType
246 * Indicates the type of a key in the hash table.
250 * Constructs a new hash table. Should be freed with
251 * _dbus_hash_table_unref(). If memory cannot be
252 * allocated for the hash table, returns #NULL.
254 * @param type the type of hash key to use.
255 * @param key_free_function function to free hash keys.
256 * @param value_free_function function to free hash values.
257 * @returns a new DBusHashTable or #NULL if no memory.
260 _dbus_hash_table_new (DBusHashType type,
261 DBusFreeFunction key_free_function,
262 DBusFreeFunction value_free_function)
264 DBusHashTable *table;
266 table = dbus_new0 (DBusHashTable, 1);
272 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
274 table->buckets = table->static_buckets;
275 table->n_buckets = DBUS_SMALL_HASH_TABLE;
276 table->n_entries = 0;
277 table->rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
278 table->down_shift = 28;
280 table->key_type = type;
282 switch (table->key_type)
285 table->find_function = find_int_function;
287 case DBUS_HASH_STRING:
288 table->find_function = find_string_function;
291 _dbus_assert_not_reached ("Unknown hash table type");
295 table->free_key_function = key_free_function;
296 table->free_value_function = value_free_function;
303 * Increments the reference count for a hash table.
305 * @param table the hash table to add a reference to.
308 _dbus_hash_table_ref (DBusHashTable *table)
310 table->refcount += 1;
314 * Decrements the reference count for a hash table,
315 * freeing the hash table if the count reaches zero.
317 * @param table the hash table to remove a reference from.
320 _dbus_hash_table_unref (DBusHashTable *table)
322 table->refcount -= 1;
324 if (table->refcount == 0)
326 DBusHashEntry *entry;
330 /* Free the entries in the table. */
332 for (i = 0; i < table->n_buckets; i++)
334 entry = table->buckets[i];
335 while (entry != NULL)
339 free_entry (table, entry);
345 /* Free the bucket array, if it was dynamically allocated. */
346 if (table->buckets != table->static_buckets)
347 dbus_free (table->buckets);
353 static DBusHashEntry*
354 alloc_entry (DBusHashTable *table)
356 DBusHashEntry *entry;
358 entry = dbus_new0 (DBusHashEntry, 1);
364 free_entry (DBusHashTable *table,
365 DBusHashEntry *entry)
367 if (table->free_key_function)
368 (* table->free_key_function) (entry->key);
369 if (table->free_value_function)
370 (* table->free_value_function) (entry->value);
376 remove_entry (DBusHashTable *table,
377 DBusHashEntry **bucket,
378 DBusHashEntry *entry)
380 _dbus_assert (table != NULL);
381 _dbus_assert (bucket != NULL);
382 _dbus_assert (*bucket != NULL);
383 _dbus_assert (entry != NULL);
385 if (*bucket == entry)
386 *bucket = entry->next;
392 while (prev->next != entry)
395 _dbus_assert (prev != NULL);
397 prev->next = entry->next;
400 table->n_entries -= 1;
401 free_entry (table, entry);
405 * Initializes a hash table iterator. To iterate over all entries in a
406 * hash table, use the following code (the printf assumes a hash
407 * from strings to strings obviously):
412 * _dbus_hash_iter_init (table, &iter);
413 * while (_dbus_hash_iter_next (&iter))
415 * printf ("The first key is %s and value is %s\n",
416 * _dbus_hash_iter_get_string_key (&iter),
417 * _dbus_hash_iter_get_value (&iter));
423 * The iterator is initialized pointing "one before" the first hash
424 * entry. The first call to _dbus_hash_iter_next() moves it onto
425 * the first valid entry or returns #FALSE if the hash table is
426 * empty. Subsequent calls move to the next valid entry or return
427 * #FALSE if there are no more entries.
429 * Note that it is guaranteed to be safe to remove a hash entry during
430 * iteration, but it is not safe to add a hash entry.
432 * @param table the hash table to iterate over.
433 * @param iter the iterator to initialize.
436 _dbus_hash_iter_init (DBusHashTable *table,
439 DBusRealHashIter *real;
441 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
443 real = (DBusRealHashIter*) iter;
448 real->next_entry = NULL;
449 real->next_bucket = 0;
450 real->n_entries_on_init = table->n_entries;
454 * Move the hash iterator forward one step, to the next hash entry.
455 * The documentation for _dbus_hash_iter_init() explains in more
458 * @param iter the iterator to move forward.
459 * @returns #FALSE if there are no more entries to move to.
462 _dbus_hash_iter_next (DBusHashIter *iter)
464 DBusRealHashIter *real;
466 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
468 real = (DBusRealHashIter*) iter;
470 /* if this assertion failed someone probably added hash entries
471 * during iteration, which is bad.
473 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
475 /* Remember that real->entry may have been deleted */
477 while (real->next_entry == NULL)
479 if (real->next_bucket >= real->table->n_buckets)
481 /* invalidate iter and return false */
488 real->bucket = &(real->table->buckets[real->next_bucket]);
489 real->next_entry = *(real->bucket);
490 real->next_bucket += 1;
493 _dbus_assert (real->next_entry != NULL);
494 _dbus_assert (real->bucket != NULL);
496 real->entry = real->next_entry;
497 real->next_entry = real->entry->next;
503 * Removes the current entry from the hash table.
504 * If a key_free_function or value_free_function
505 * was provided to _dbus_hash_table_new(),
506 * frees the key and/or value for this entry.
508 * @param iter the hash table iterator.
511 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
513 DBusRealHashIter *real;
515 real = (DBusRealHashIter*) iter;
517 _dbus_assert (real->table != NULL);
518 _dbus_assert (real->entry != NULL);
519 _dbus_assert (real->bucket != NULL);
521 remove_entry (real->table, real->bucket, real->entry);
523 real->entry = NULL; /* make it crash if you try to use this entry */
527 * Gets the value of the current entry.
529 * @param iter the hash table iterator.
532 _dbus_hash_iter_get_value (DBusHashIter *iter)
534 DBusRealHashIter *real;
536 real = (DBusRealHashIter*) iter;
538 _dbus_assert (real->table != NULL);
539 _dbus_assert (real->entry != NULL);
541 return real->entry->value;
545 * Sets the value of the current entry.
546 * If the hash table has a value_free_function
547 * it will be used to free the previous value.
548 * The hash table will own the passed-in value
549 * (it will not be copied).
551 * @param iter the hash table iterator.
552 * @param value the new value.
555 _dbus_hash_iter_set_value (DBusHashIter *iter,
558 DBusRealHashIter *real;
560 real = (DBusRealHashIter*) iter;
562 _dbus_assert (real->table != NULL);
563 _dbus_assert (real->entry != NULL);
565 if (real->table->free_value_function && value != real->entry->value)
566 (* real->table->free_value_function) (real->entry->value);
568 real->entry->value = value;
572 * Gets the key for the current entry.
573 * Only works for hash tables of type #DBUS_HASH_INT.
575 * @param iter the hash table iterator.
578 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
580 DBusRealHashIter *real;
582 real = (DBusRealHashIter*) iter;
584 _dbus_assert (real->table != NULL);
585 _dbus_assert (real->entry != NULL);
587 return _DBUS_POINTER_TO_INT (real->entry->key);
591 * Gets the key for the current entry.
592 * Only works for hash tables of type #DBUS_HASH_STRING
593 * @param iter the hash table iterator.
596 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
598 DBusRealHashIter *real;
600 real = (DBusRealHashIter*) iter;
602 _dbus_assert (real->table != NULL);
603 _dbus_assert (real->entry != NULL);
605 return real->entry->key;
609 * A low-level but efficient interface for manipulating the hash
610 * table. It's efficient because you can get, set, and optionally
611 * create the hash entry while only running the hash function one
614 * Note that while calling _dbus_hash_iter_next() on the iterator
615 * filled in by this function may work, it's completely
616 * undefined which entries are after this iter and which
617 * are before it. So it would be silly to iterate using this
620 * If the hash entry is created, its value will be initialized
623 * #FALSE may be returned due to memory allocation failure, or
624 * because create_if_not_found was #FALSE and the entry
627 * For a hash table of type #DBUS_HASH_INT, cast the int
628 * key to the key parameter using #_DBUS_INT_TO_POINTER().
630 * @param table the hash table.
631 * @param key the hash key.
632 * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
633 * @param iter the iterator to initialize.
634 * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
637 _dbus_hash_iter_lookup (DBusHashTable *table,
639 dbus_bool_t create_if_not_found,
642 DBusRealHashIter *real;
643 DBusHashEntry *entry;
644 DBusHashEntry **bucket;
646 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
648 real = (DBusRealHashIter*) iter;
650 entry = (* table->find_function) (table, key, create_if_not_found, &bucket);
656 real->bucket = bucket;
658 real->next_entry = entry->next;
659 real->next_bucket = (bucket - table->buckets) + 1;
660 real->n_entries_on_init = table->n_entries;
662 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
667 static DBusHashEntry*
668 add_entry (DBusHashTable *table,
671 DBusHashEntry ***bucket)
673 DBusHashEntry *entry;
676 entry = alloc_entry (table);
686 b = &(table->buckets[idx]);
693 table->n_entries += 1;
695 if (table->n_entries >= table->rebuild_size)
696 rebuild_table (table);
702 string_hash (const char *str)
704 register unsigned int result;
708 * I tried a zillion different hash functions and asked many other
709 * people for advice. Many people had their own favorite functions,
710 * all different, but no-one had much idea why they were good ones.
711 * I chose the one below (multiply by 9 and add new character)
712 * because of the following reasons:
714 * 1. Multiplying by 10 is perfect for keys that are decimal strings,
715 * and multiplying by 9 is just about as good.
716 * 2. Times-9 is (shift-left-3) plus (old). This means that each
717 * character's bits hang around in the low-order bits of the
718 * hash value for ever, plus they spread fairly rapidly up to
719 * the high-order bits to fill out the hash value. This seems
720 * works well both for decimal and non-decimal strings.
731 result += (result << 3) + c;
737 static DBusHashEntry*
738 find_string_function (DBusHashTable *table,
740 dbus_bool_t create_if_not_found,
741 DBusHashEntry ***bucket)
743 DBusHashEntry *entry;
749 idx = string_hash (key) & table->mask;
751 /* Search all of the entries in this bucket. */
752 entry = table->buckets[idx];
753 while (entry != NULL)
755 if (strcmp (key, entry->key) == 0)
758 *bucket = &(table->buckets[idx]);
765 if (create_if_not_found)
766 entry = add_entry (table, idx, key, bucket);
771 static DBusHashEntry*
772 find_int_function (DBusHashTable *table,
774 dbus_bool_t create_if_not_found,
775 DBusHashEntry ***bucket)
777 DBusHashEntry *entry;
783 idx = RANDOM_INDEX (table, key) & table->mask;
785 /* Search all of the entries in this bucket. */
786 entry = table->buckets[idx];
787 while (entry != NULL)
789 if (key == entry->key)
792 *bucket = &(table->buckets[idx]);
799 /* Entry not found. Add a new one to the bucket. */
800 if (create_if_not_found)
801 entry = add_entry (table, idx, key, bucket);
807 rebuild_table (DBusHashTable *table)
810 DBusHashEntry **old_buckets;
811 DBusHashEntry **old_chain;
812 DBusHashEntry *entry;
815 * Allocate and initialize the new bucket array, and set up
816 * hashing constants for new array size.
819 old_size = table->n_buckets;
820 old_buckets = table->buckets;
822 table->n_buckets *= 4;
823 table->buckets = dbus_new0 (DBusHashEntry*, table->n_buckets);
824 if (table->buckets == NULL)
826 /* out of memory, yay - just don't reallocate, the table will
827 * still work, albeit more slowly.
829 table->n_buckets /= 4;
830 table->buckets = old_buckets;
834 table->rebuild_size *= 4;
835 table->down_shift -= 2;
836 table->mask = (table->mask << 2) + 3;
839 * Rehash all of the existing entries into the new bucket array.
842 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
844 for (entry = *old_chain; entry != NULL; entry = *old_chain)
847 DBusHashEntry **bucket;
849 *old_chain = entry->next;
850 switch (table->key_type)
852 case DBUS_HASH_STRING:
853 idx = string_hash (entry->key) & table->mask;
856 idx = RANDOM_INDEX (table, entry->key);
860 _dbus_assert_not_reached ("Unknown hash table type");
864 bucket = &(table->buckets[idx]);
865 entry->next = *bucket;
870 /* Free the old bucket array, if it was dynamically allocated. */
872 if (old_buckets != table->static_buckets)
873 dbus_free (old_buckets);
877 * Looks up the value for a given string in a hash table
878 * of type #DBUS_HASH_STRING. Returns %NULL if the value
879 * is not present. (A not-present entry is indistinguishable
880 * from an entry with a value of %NULL.)
881 * @param table the hash table.
882 * @param key the string to look up.
883 * @returns the value of the hash entry.
886 _dbus_hash_table_lookup_string (DBusHashTable *table,
889 DBusHashEntry *entry;
891 _dbus_assert (table->key_type == DBUS_HASH_STRING);
893 entry = (* table->find_function) (table, (char*) key, FALSE, NULL);
902 * Looks up the value for a given integer in a hash table
903 * of type #DBUS_HASH_INT. Returns %NULL if the value
904 * is not present. (A not-present entry is indistinguishable
905 * from an entry with a value of %NULL.)
906 * @param table the hash table.
907 * @param key the integer to look up.
908 * @returns the value of the hash entry.
911 _dbus_hash_table_lookup_int (DBusHashTable *table,
914 DBusHashEntry *entry;
916 _dbus_assert (table->key_type == DBUS_HASH_INT);
918 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL);
927 * Removes the hash entry for the given key. If no hash entry
928 * for the key exists, does nothing.
930 * @param table the hash table.
931 * @param key the hash key.
934 _dbus_hash_table_remove_string (DBusHashTable *table,
937 DBusHashEntry *entry;
938 DBusHashEntry **bucket;
940 _dbus_assert (table->key_type == DBUS_HASH_STRING);
942 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket);
945 remove_entry (table, bucket, entry);
949 * Removes the hash entry for the given key. If no hash entry
950 * for the key exists, does nothing.
952 * @param table the hash table.
953 * @param key the hash key.
956 _dbus_hash_table_remove_int (DBusHashTable *table,
959 DBusHashEntry *entry;
960 DBusHashEntry **bucket;
962 _dbus_assert (table->key_type == DBUS_HASH_INT);
964 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket);
967 remove_entry (table, bucket, entry);
971 * Creates a hash entry with the given key and value.
972 * The key and value are not copied; they are stored
973 * in the hash table by reference. If an entry with the
974 * given key already exists, the previous key and value
975 * are overwritten (and freed if the hash table has
976 * a key_free_function and/or value_free_function).
978 * Returns #FALSE if memory for the new hash entry
979 * can't be allocated.
981 * @param table the hash table.
982 * @param key the hash entry key.
983 * @param value the hash entry value.
986 _dbus_hash_table_insert_string (DBusHashTable *table,
990 DBusHashEntry *entry;
992 _dbus_assert (table->key_type == DBUS_HASH_STRING);
994 entry = (* table->find_function) (table, key, TRUE, NULL);
997 return FALSE; /* no memory */
999 if (table->free_key_function && entry->key != key)
1000 (* table->free_key_function) (entry->key);
1002 if (table->free_value_function && entry->value != value)
1003 (* table->free_value_function) (entry->value);
1006 entry->value = value;
1012 * Creates a hash entry with the given key and value.
1013 * The key and value are not copied; they are stored
1014 * in the hash table by reference. If an entry with the
1015 * given key already exists, the previous key and value
1016 * are overwritten (and freed if the hash table has
1017 * a key_free_function and/or value_free_function).
1019 * Returns #FALSE if memory for the new hash entry
1020 * can't be allocated.
1022 * @param table the hash table.
1023 * @param key the hash entry key.
1024 * @param value the hash entry value.
1027 _dbus_hash_table_insert_int (DBusHashTable *table,
1031 DBusHashEntry *entry;
1033 _dbus_assert (table->key_type == DBUS_HASH_INT);
1035 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL);
1038 return FALSE; /* no memory */
1040 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1041 (* table->free_key_function) (entry->key);
1043 if (table->free_value_function && entry->value != value)
1044 (* table->free_value_function) (entry->value);
1046 entry->key = _DBUS_INT_TO_POINTER (key);
1047 entry->value = value;
1053 * Gets the number of hash entries in a hash table.
1055 * @param table the hash table.
1056 * @returns the number of entries in the table.
1059 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1061 return table->n_entries;
1066 #ifdef DBUS_BUILD_TESTS
1067 #include "dbus-test.h"
1071 count_entries (DBusHashTable *table)
1077 _dbus_hash_iter_init (table, &iter);
1078 while (_dbus_hash_iter_next (&iter))
1081 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1087 * @ingroup DBusHashTableInternals
1088 * Unit test for DBusHashTable
1089 * @returns #TRUE on success.
1092 _dbus_hash_test (void)
1095 DBusHashTable *table1;
1096 DBusHashTable *table2;
1099 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1100 dbus_free, dbus_free);
1104 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1109 /* Insert and remove a bunch of stuff, counting the table in between
1110 * to be sure it's not broken and that iteration works
1116 sprintf (buf, "Hash key %d", i);
1120 key = _dbus_strdup (buf);
1123 value = _dbus_strdup ("Value!");
1127 if (!_dbus_hash_table_insert_string (table1,
1131 value = _dbus_strdup (buf);
1135 if (!_dbus_hash_table_insert_int (table2,
1139 _dbus_assert (count_entries (table1) == i + 1);
1140 _dbus_assert (count_entries (table2) == i + 1);
1142 value = _dbus_hash_table_lookup_string (table1, buf);
1143 _dbus_assert (value != NULL);
1144 _dbus_assert (strcmp (value, "Value!") == 0);
1146 value = _dbus_hash_table_lookup_int (table2, i);
1147 _dbus_assert (value != NULL);
1148 _dbus_assert (strcmp (value, buf) == 0);
1157 sprintf (buf, "Hash key %d", i);
1159 _dbus_hash_table_remove_string (table1,
1162 _dbus_hash_table_remove_int (table2, i);
1164 _dbus_assert (count_entries (table1) == i);
1165 _dbus_assert (count_entries (table2) == i);
1170 _dbus_hash_table_ref (table1);
1171 _dbus_hash_table_ref (table2);
1172 _dbus_hash_table_unref (table1);
1173 _dbus_hash_table_unref (table2);
1174 _dbus_hash_table_unref (table1);
1175 _dbus_hash_table_unref (table2);
1178 /* Insert a bunch of stuff then check
1179 * that iteration works correctly (finds the right
1180 * values, iter_set_value works, etc.)
1182 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1183 dbus_free, dbus_free);
1187 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1196 sprintf (buf, "Hash key %d", i);
1200 key = _dbus_strdup (buf);
1203 value = _dbus_strdup ("Value!");
1207 if (!_dbus_hash_table_insert_string (table1,
1211 value = _dbus_strdup (buf);
1215 if (!_dbus_hash_table_insert_int (table2,
1219 _dbus_assert (count_entries (table1) == i + 1);
1220 _dbus_assert (count_entries (table2) == i + 1);
1225 _dbus_hash_iter_init (table1, &iter);
1226 while (_dbus_hash_iter_next (&iter))
1231 key = _dbus_hash_iter_get_string_key (&iter);
1232 value = _dbus_hash_iter_get_value (&iter);
1234 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1236 value = _dbus_strdup ("Different value!");
1240 _dbus_hash_iter_set_value (&iter, value);
1242 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1245 _dbus_hash_iter_init (table1, &iter);
1246 while (_dbus_hash_iter_next (&iter))
1248 _dbus_hash_iter_remove_entry (&iter);
1249 _dbus_assert (count_entries (table1) == i - 1);
1253 _dbus_hash_iter_init (table2, &iter);
1254 while (_dbus_hash_iter_next (&iter))
1259 key = _dbus_hash_iter_get_int_key (&iter);
1260 value = _dbus_hash_iter_get_value (&iter);
1262 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1264 value = _dbus_strdup ("Different value!");
1268 _dbus_hash_iter_set_value (&iter, value);
1270 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1273 i = count_entries (table2);
1274 _dbus_hash_iter_init (table2, &iter);
1275 while (_dbus_hash_iter_next (&iter))
1277 _dbus_hash_iter_remove_entry (&iter);
1278 _dbus_assert (count_entries (table2) + 1 == i);
1282 _dbus_hash_table_unref (table1);
1283 _dbus_hash_table_unref (table2);
1286 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1287 * be sure that interface works.
1289 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1290 dbus_free, dbus_free);
1294 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1303 sprintf (buf, "Hash key %d", i);
1307 key = _dbus_strdup (buf);
1310 value = _dbus_strdup ("Value!");
1314 if (!_dbus_hash_iter_lookup (table1,
1317 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1318 _dbus_hash_iter_set_value (&iter, value);
1320 value = _dbus_strdup (buf);
1324 if (!_dbus_hash_iter_lookup (table2,
1325 _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1327 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1328 _dbus_hash_iter_set_value (&iter, value);
1330 _dbus_assert (count_entries (table1) == i + 1);
1331 _dbus_assert (count_entries (table2) == i + 1);
1333 if (!_dbus_hash_iter_lookup (table1, buf, FALSE, &iter))
1336 value = _dbus_hash_iter_get_value (&iter);
1337 _dbus_assert (value != NULL);
1338 _dbus_assert (strcmp (value, "Value!") == 0);
1340 /* Iterate just to be sure it works, though
1341 * it's a stupid thing to do
1343 while (_dbus_hash_iter_next (&iter))
1346 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1349 value = _dbus_hash_iter_get_value (&iter);
1350 _dbus_assert (value != NULL);
1351 _dbus_assert (strcmp (value, buf) == 0);
1353 /* Iterate just to be sure it works, though
1354 * it's a stupid thing to do
1356 while (_dbus_hash_iter_next (&iter))
1366 sprintf (buf, "Hash key %d", i);
1368 if (!_dbus_hash_iter_lookup (table1, buf, FALSE, &iter))
1369 _dbus_assert_not_reached ("hash entry should have existed");
1370 _dbus_hash_iter_remove_entry (&iter);
1372 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1373 _dbus_assert_not_reached ("hash entry should have existed");
1374 _dbus_hash_iter_remove_entry (&iter);
1376 _dbus_assert (count_entries (table1) == i);
1377 _dbus_assert (count_entries (table2) == i);
1382 _dbus_hash_table_unref (table1);
1383 _dbus_hash_table_unref (table2);