1 /* -*- mode: C; c-file-style: "gnu" -*- */
2 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
3 *
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.
7 *
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.
12 *
13 * Licensed under the Academic Free License version 2.1
14 *
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.
19 *
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.
24 *
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
28 *
29 */
30 /*
31 * The following copyright applies to code from the Tcl distribution.
32 *
33 * Copyright (c) 1991-1993 The Regents of the University of California.
34 * Copyright (c) 1994 Sun Microsystems, Inc.
35 *
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.
40 *
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.
50 *
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.
56 *
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.
63 *
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.
75 */
76
77 #include "dbus-hash.h"
78 #include "dbus-internals.h"
79 #include "dbus-mempool.h"
80
81 /**
82 * @defgroup DBusHashTable Hash table
83 * @ingroup DBusInternals
84 * @brief DBusHashTable data structure
85 *
86 * Types and functions related to DBusHashTable.
87 */
88
89 /**
90 * @defgroup DBusHashTableInternals Hash table implementation details
91 * @ingroup DBusInternals
92 * @brief DBusHashTable implementation details
93 *
94 * The guts of DBusHashTable.
95 *
96 * @{
97 */
98
99 /**
100 * When there are this many entries per bucket, on average, rebuild
101 * the hash table to make it larger.
102 */
103 #define REBUILD_MULTIPLIER 3
104
105 /**
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.)
111 *
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?
119 *
120 */
121 #define RANDOM_INDEX(table, i) \
122 (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
123
124 /**
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.
128 */
129 #define DBUS_SMALL_HASH_TABLE 4
130
131 /**
132 * Typedef for DBusHashEntry
133 */
134 typedef struct DBusHashEntry DBusHashEntry;
135
136 /**
137 * @brief Internal representation of a hash entry.
138 *
139 * A single entry (key-value pair) in the hash table.
140 * Internal to hash table implementation.
141 */
142 struct DBusHashEntry
143 {
144 DBusHashEntry *next; /**< Pointer to next entry in this
145 * hash bucket, or #NULL for end of
146 * chain.
147 */
148 void *key; /**< Hash key */
149 void *value; /**< Hash value */
150 };
151
152 /**
153 * Function used to find and optionally create a hash entry.
154 */
155 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
156 void *key,
157 dbus_bool_t create_if_not_found,
158 DBusHashEntry ***bucket,
159 DBusPreallocatedHash *preallocated);
160
161 /**
162 * @brief Internals of DBusHashTable.
163 *
164 * Hash table internals. Hash tables are opaque objects, they must be
165 * used via accessor functions.
166 */
167 struct DBusHashTable {
168 int refcount; /**< Reference count */
169
170 DBusHashEntry **buckets; /**< Pointer to bucket array. Each
171 * element points to first entry in
172 * bucket's hash chain, or #NULL.
173 */
174 DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
175 /**< Bucket array used for small tables
176 * (to avoid mallocs and frees).
177 */
178 int n_buckets; /**< Total number of buckets allocated
179 * at **buckets.
180 */
181 int n_entries; /**< Total number of entries present
182 * in table.
183 */
184 int hi_rebuild_size; /**< Enlarge table when n_entries gets
185 * to be this large.
186 */
187 int lo_rebuild_size; /**< Shrink table when n_entries gets
188 * below this.
189 */
190 int down_shift; /**< Shift count used in hashing
191 * function. Designed to use high-
192 * order bits of randomized keys.
193 */
194 int mask; /**< Mask value used in hashing
195 * function.
196 */
197 DBusHashType key_type; /**< Type of keys used in this table */
198
199
200 DBusFindEntryFunction find_function; /**< Function for finding entries */
201
202 DBusFreeFunction free_key_function; /**< Function to free keys */
203 DBusFreeFunction free_value_function; /**< Function to free values */
204
205 DBusMemPool *entry_pool; /**< Memory pool for hash entries */
206 };
207
208 /**
209 * @brief Internals of DBusHashIter.
210 */
211 typedef struct
212 {
213 DBusHashTable *table; /**< Pointer to table containing entry. */
214 DBusHashEntry **bucket; /**< Pointer to bucket that points to
215 * first entry in this entry's chain:
216 * used for deleting the entry.
217 */
218 DBusHashEntry *entry; /**< Current hash entry */
219 DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
220 int next_bucket; /**< index of next bucket */
221 int n_entries_on_init; /**< used to detect table resize since initialization */
222 } DBusRealHashIter;
223
224 static DBusHashEntry* find_direct_function (DBusHashTable *table,
225 void *key,
226 dbus_bool_t create_if_not_found,
227 DBusHashEntry ***bucket,
228 DBusPreallocatedHash *preallocated);
229 static DBusHashEntry* find_string_function (DBusHashTable *table,
230 void *key,
231 dbus_bool_t create_if_not_found,
232 DBusHashEntry ***bucket,
233 DBusPreallocatedHash *preallocated);
234 #ifdef DBUS_BUILD_TESTS
235 static DBusHashEntry* find_two_strings_function (DBusHashTable *table,
236 void *key,
237 dbus_bool_t create_if_not_found,
238 DBusHashEntry ***bucket,
239 DBusPreallocatedHash *preallocated);
240 #endif
241 static unsigned int string_hash (const char *str);
242 #ifdef DBUS_BUILD_TESTS
243 static unsigned int two_strings_hash (const char *str);
244 #endif
245 static void rebuild_table (DBusHashTable *table);
246 static DBusHashEntry* alloc_entry (DBusHashTable *table);
247 static void remove_entry (DBusHashTable *table,
248 DBusHashEntry **bucket,
249 DBusHashEntry *entry);
250 static void free_entry (DBusHashTable *table,
251 DBusHashEntry *entry);
252 static void free_entry_data (DBusHashTable *table,
253 DBusHashEntry *entry);
254
255
256 /** @} */
257
258 /**
259 * @addtogroup DBusHashTable
260 * @{
261 */
262
263 /**
264 * @typedef DBusHashIter
265 *
266 * Public opaque hash table iterator object.
267 */
268
269 /**
270 * @typedef DBusHashTable
271 *
272 * Public opaque hash table object.
273 */
274
275 /**
276 * @typedef DBusHashType
277 *
278 * Indicates the type of a key in the hash table.
279 */
280
281 /**
282 * Constructs a new hash table. Should be freed with
283 * _dbus_hash_table_unref(). If memory cannot be
284 * allocated for the hash table, returns #NULL.
285 *
286 * @param type the type of hash key to use.
287 * @param key_free_function function to free hash keys.
288 * @param value_free_function function to free hash values.
289 * @returns a new DBusHashTable or #NULL if no memory.
290 */
291 DBusHashTable*
_dbus_hash_table_new(DBusHashType type,DBusFreeFunction key_free_function,DBusFreeFunction value_free_function)292 _dbus_hash_table_new (DBusHashType type,
293 DBusFreeFunction key_free_function,
294 DBusFreeFunction value_free_function)
295 {
296 DBusHashTable *table;
297 DBusMemPool *entry_pool;
298
299 table = dbus_new0 (DBusHashTable, 1);
300 if (table == NULL)
301 return NULL;
302
303 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
304 if (entry_pool == NULL)
305 {
306 dbus_free (table);
307 return NULL;
308 }
309
310 table->refcount = 1;
311 table->entry_pool = entry_pool;
312
313 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
314
315 table->buckets = table->static_buckets;
316 table->n_buckets = DBUS_SMALL_HASH_TABLE;
317 table->n_entries = 0;
318 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
319 table->lo_rebuild_size = 0;
320 table->down_shift = 28;
321 table->mask = 3;
322 table->key_type = type;
323
324 _dbus_assert (table->mask < table->n_buckets);
325
326 switch (table->key_type)
327 {
328 case DBUS_HASH_INT:
329 case DBUS_HASH_POINTER:
330 case DBUS_HASH_ULONG:
331 table->find_function = find_direct_function;
332 break;
333 case DBUS_HASH_STRING:
334 table->find_function = find_string_function;
335 break;
336 case DBUS_HASH_TWO_STRINGS:
337 #ifdef DBUS_BUILD_TESTS
338 table->find_function = find_two_strings_function;
339 #endif
340 break;
341 default:
342 _dbus_assert_not_reached ("Unknown hash table type");
343 break;
344 }
345
346 table->free_key_function = key_free_function;
347 table->free_value_function = value_free_function;
348
349 return table;
350 }
351
352
353 /**
354 * Increments the reference count for a hash table.
355 *
356 * @param table the hash table to add a reference to.
357 * @returns the hash table.
358 */
359 DBusHashTable *
_dbus_hash_table_ref(DBusHashTable * table)360 _dbus_hash_table_ref (DBusHashTable *table)
361 {
362 table->refcount += 1;
363
364 return table;
365 }
366
367 /**
368 * Decrements the reference count for a hash table,
369 * freeing the hash table if the count reaches zero.
370 *
371 * @param table the hash table to remove a reference from.
372 */
373 void
_dbus_hash_table_unref(DBusHashTable * table)374 _dbus_hash_table_unref (DBusHashTable *table)
375 {
376 table->refcount -= 1;
377
378 if (table->refcount == 0)
379 {
380 #if 0
381 DBusHashEntry *entry;
382 DBusHashEntry *next;
383 int i;
384
385 /* Free the entries in the table. */
386 for (i = 0; i < table->n_buckets; i++)
387 {
388 entry = table->buckets[i];
389 while (entry != NULL)
390 {
391 next = entry->next;
392
393 free_entry (table, entry);
394
395 entry = next;
396 }
397 }
398 #else
399 DBusHashEntry *entry;
400 int i;
401
402 /* Free the entries in the table. */
403 for (i = 0; i < table->n_buckets; i++)
404 {
405 entry = table->buckets[i];
406 while (entry != NULL)
407 {
408 free_entry_data (table, entry);
409
410 entry = entry->next;
411 }
412 }
413 /* We can do this very quickly with memory pools ;-) */
414 _dbus_mem_pool_free (table->entry_pool);
415 #endif
416
417 /* Free the bucket array, if it was dynamically allocated. */
418 if (table->buckets != table->static_buckets)
419 dbus_free (table->buckets);
420
421 dbus_free (table);
422 }
423 }
424
425 /**
426 * Removed all entries from a hash table.
427 *
428 * @param table the hash table to remove all entries from.
429 */
430 void
_dbus_hash_table_remove_all(DBusHashTable * table)431 _dbus_hash_table_remove_all (DBusHashTable *table)
432 {
433 DBusHashIter iter;
434 _dbus_hash_iter_init (table, &iter);
435 while (_dbus_hash_iter_next (&iter))
436 {
437 _dbus_hash_iter_remove_entry(&iter);
438 }
439 }
440
441 static DBusHashEntry*
alloc_entry(DBusHashTable * table)442 alloc_entry (DBusHashTable *table)
443 {
444 DBusHashEntry *entry;
445
446 entry = _dbus_mem_pool_alloc (table->entry_pool);
447
448 return entry;
449 }
450
451 static void
free_entry_data(DBusHashTable * table,DBusHashEntry * entry)452 free_entry_data (DBusHashTable *table,
453 DBusHashEntry *entry)
454 {
455 if (table->free_key_function)
456 (* table->free_key_function) (entry->key);
457 if (table->free_value_function)
458 (* table->free_value_function) (entry->value);
459 }
460
461 static void
free_entry(DBusHashTable * table,DBusHashEntry * entry)462 free_entry (DBusHashTable *table,
463 DBusHashEntry *entry)
464 {
465 free_entry_data (table, entry);
466 _dbus_mem_pool_dealloc (table->entry_pool, entry);
467 }
468
469 static void
remove_entry(DBusHashTable * table,DBusHashEntry ** bucket,DBusHashEntry * entry)470 remove_entry (DBusHashTable *table,
471 DBusHashEntry **bucket,
472 DBusHashEntry *entry)
473 {
474 _dbus_assert (table != NULL);
475 _dbus_assert (bucket != NULL);
476 _dbus_assert (*bucket != NULL);
477 _dbus_assert (entry != NULL);
478
479 if (*bucket == entry)
480 *bucket = entry->next;
481 else
482 {
483 DBusHashEntry *prev;
484 prev = *bucket;
485
486 while (prev->next != entry)
487 prev = prev->next;
488
489 _dbus_assert (prev != NULL);
490
491 prev->next = entry->next;
492 }
493
494 table->n_entries -= 1;
495 free_entry (table, entry);
496 }
497
498 /**
499 * Initializes a hash table iterator. To iterate over all entries in a
500 * hash table, use the following code (the printf assumes a hash
501 * from strings to strings obviously):
502 *
503 * @code
504 * DBusHashIter iter;
505 *
506 * _dbus_hash_iter_init (table, &iter);
507 * while (_dbus_hash_iter_next (&iter))
508 * {
509 * printf ("The first key is %s and value is %s\n",
510 * _dbus_hash_iter_get_string_key (&iter),
511 * _dbus_hash_iter_get_value (&iter));
512 * }
513 *
514 *
515 * @endcode
516 *
517 * The iterator is initialized pointing "one before" the first hash
518 * entry. The first call to _dbus_hash_iter_next() moves it onto
519 * the first valid entry or returns #FALSE if the hash table is
520 * empty. Subsequent calls move to the next valid entry or return
521 * #FALSE if there are no more entries.
522 *
523 * Note that it is guaranteed to be safe to remove a hash entry during
524 * iteration, but it is not safe to add a hash entry.
525 *
526 * @param table the hash table to iterate over.
527 * @param iter the iterator to initialize.
528 */
529 void
_dbus_hash_iter_init(DBusHashTable * table,DBusHashIter * iter)530 _dbus_hash_iter_init (DBusHashTable *table,
531 DBusHashIter *iter)
532 {
533 DBusRealHashIter *real;
534
535 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
536
537 real = (DBusRealHashIter*) iter;
538
539 real->table = table;
540 real->bucket = NULL;
541 real->entry = NULL;
542 real->next_entry = NULL;
543 real->next_bucket = 0;
544 real->n_entries_on_init = table->n_entries;
545 }
546
547 /**
548 * Move the hash iterator forward one step, to the next hash entry.
549 * The documentation for _dbus_hash_iter_init() explains in more
550 * detail.
551 *
552 * @param iter the iterator to move forward.
553 * @returns #FALSE if there are no more entries to move to.
554 */
555 dbus_bool_t
_dbus_hash_iter_next(DBusHashIter * iter)556 _dbus_hash_iter_next (DBusHashIter *iter)
557 {
558 DBusRealHashIter *real;
559
560 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
561
562 real = (DBusRealHashIter*) iter;
563
564 /* if this assertion failed someone probably added hash entries
565 * during iteration, which is bad.
566 */
567 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
568
569 /* Remember that real->entry may have been deleted */
570
571 while (real->next_entry == NULL)
572 {
573 if (real->next_bucket >= real->table->n_buckets)
574 {
575 /* invalidate iter and return false */
576 real->entry = NULL;
577 real->table = NULL;
578 real->bucket = NULL;
579 return FALSE;
580 }
581
582 real->bucket = &(real->table->buckets[real->next_bucket]);
583 real->next_entry = *(real->bucket);
584 real->next_bucket += 1;
585 }
586
587 _dbus_assert (real->next_entry != NULL);
588 _dbus_assert (real->bucket != NULL);
589
590 real->entry = real->next_entry;
591 real->next_entry = real->entry->next;
592
593 return TRUE;
594 }
595
596 /**
597 * Removes the current entry from the hash table.
598 * If a key_free_function or value_free_function
599 * was provided to _dbus_hash_table_new(),
600 * frees the key and/or value for this entry.
601 *
602 * @param iter the hash table iterator.
603 */
604 void
_dbus_hash_iter_remove_entry(DBusHashIter * iter)605 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
606 {
607 DBusRealHashIter *real;
608
609 real = (DBusRealHashIter*) iter;
610
611 _dbus_assert (real->table != NULL);
612 _dbus_assert (real->entry != NULL);
613 _dbus_assert (real->bucket != NULL);
614
615 remove_entry (real->table, real->bucket, real->entry);
616
617 real->entry = NULL; /* make it crash if you try to use this entry */
618 }
619
620 /**
621 * Gets the value of the current entry.
622 *
623 * @param iter the hash table iterator.
624 */
625 void*
_dbus_hash_iter_get_value(DBusHashIter * iter)626 _dbus_hash_iter_get_value (DBusHashIter *iter)
627 {
628 DBusRealHashIter *real;
629
630 real = (DBusRealHashIter*) iter;
631
632 _dbus_assert (real->table != NULL);
633 _dbus_assert (real->entry != NULL);
634
635 return real->entry->value;
636 }
637
638 /**
639 * Sets the value of the current entry.
640 * If the hash table has a value_free_function
641 * it will be used to free the previous value.
642 * The hash table will own the passed-in value
643 * (it will not be copied).
644 *
645 * @param iter the hash table iterator.
646 * @param value the new value.
647 */
648 void
_dbus_hash_iter_set_value(DBusHashIter * iter,void * value)649 _dbus_hash_iter_set_value (DBusHashIter *iter,
650 void *value)
651 {
652 DBusRealHashIter *real;
653
654 real = (DBusRealHashIter*) iter;
655
656 _dbus_assert (real->table != NULL);
657 _dbus_assert (real->entry != NULL);
658
659 if (real->table->free_value_function && value != real->entry->value)
660 (* real->table->free_value_function) (real->entry->value);
661
662 real->entry->value = value;
663 }
664
665 /**
666 * Gets the key for the current entry.
667 * Only works for hash tables of type #DBUS_HASH_INT.
668 *
669 * @param iter the hash table iterator.
670 */
671 int
_dbus_hash_iter_get_int_key(DBusHashIter * iter)672 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
673 {
674 DBusRealHashIter *real;
675
676 real = (DBusRealHashIter*) iter;
677
678 _dbus_assert (real->table != NULL);
679 _dbus_assert (real->entry != NULL);
680
681 return _DBUS_POINTER_TO_INT (real->entry->key);
682 }
683
684 /**
685 * Gets the key for the current entry.
686 * Only works for hash tables of type #DBUS_HASH_ULONG.
687 *
688 * @param iter the hash table iterator.
689 */
690 unsigned long
_dbus_hash_iter_get_ulong_key(DBusHashIter * iter)691 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
692 {
693 DBusRealHashIter *real;
694
695 real = (DBusRealHashIter*) iter;
696
697 _dbus_assert (real->table != NULL);
698 _dbus_assert (real->entry != NULL);
699
700 return (unsigned long) real->entry->key;
701 }
702
703 /**
704 * Gets the key for the current entry.
705 * Only works for hash tables of type #DBUS_HASH_STRING
706 * @param iter the hash table iterator.
707 */
708 const char*
_dbus_hash_iter_get_string_key(DBusHashIter * iter)709 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
710 {
711 DBusRealHashIter *real;
712
713 real = (DBusRealHashIter*) iter;
714
715 _dbus_assert (real->table != NULL);
716 _dbus_assert (real->entry != NULL);
717
718 return real->entry->key;
719 }
720
721 #ifdef DBUS_BUILD_TESTS
722 /**
723 * Gets the key for the current entry.
724 * Only works for hash tables of type #DBUS_HASH_TWO_STRINGS
725 * @param iter the hash table iterator.
726 */
727 const char*
_dbus_hash_iter_get_two_strings_key(DBusHashIter * iter)728 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
729 {
730 DBusRealHashIter *real;
731
732 real = (DBusRealHashIter*) iter;
733
734 _dbus_assert (real->table != NULL);
735 _dbus_assert (real->entry != NULL);
736
737 return real->entry->key;
738 }
739 #endif /* DBUS_BUILD_TESTS */
740
741 /**
742 * A low-level but efficient interface for manipulating the hash
743 * table. It's efficient because you can get, set, and optionally
744 * create the hash entry while only running the hash function one
745 * time.
746 *
747 * Note that while calling _dbus_hash_iter_next() on the iterator
748 * filled in by this function may work, it's completely
749 * undefined which entries are after this iter and which
750 * are before it. So it would be silly to iterate using this
751 * iterator.
752 *
753 * If the hash entry is created, its value will be initialized
754 * to all bits zero.
755 *
756 * #FALSE may be returned due to memory allocation failure, or
757 * because create_if_not_found was #FALSE and the entry
758 * did not exist.
759 *
760 * If create_if_not_found is #TRUE and the entry is created, the hash
761 * table takes ownership of the key that's passed in.
762 *
763 * For a hash table of type #DBUS_HASH_INT, cast the int
764 * key to the key parameter using #_DBUS_INT_TO_POINTER().
765 *
766 * @param table the hash table.
767 * @param key the hash key.
768 * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
769 * @param iter the iterator to initialize.
770 * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
771 */
772 dbus_bool_t
_dbus_hash_iter_lookup(DBusHashTable * table,void * key,dbus_bool_t create_if_not_found,DBusHashIter * iter)773 _dbus_hash_iter_lookup (DBusHashTable *table,
774 void *key,
775 dbus_bool_t create_if_not_found,
776 DBusHashIter *iter)
777 {
778 DBusRealHashIter *real;
779 DBusHashEntry *entry;
780 DBusHashEntry **bucket;
781
782 _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
783
784 real = (DBusRealHashIter*) iter;
785
786 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
787
788 if (entry == NULL)
789 return FALSE;
790
791 real->table = table;
792 real->bucket = bucket;
793 real->entry = entry;
794 real->next_entry = entry->next;
795 real->next_bucket = (bucket - table->buckets) + 1;
796 real->n_entries_on_init = table->n_entries;
797
798 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
799
800 return TRUE;
801 }
802
803 static void
add_allocated_entry(DBusHashTable * table,DBusHashEntry * entry,unsigned int idx,void * key,DBusHashEntry *** bucket)804 add_allocated_entry (DBusHashTable *table,
805 DBusHashEntry *entry,
806 unsigned int idx,
807 void *key,
808 DBusHashEntry ***bucket)
809 {
810 DBusHashEntry **b;
811
812 entry->key = key;
813
814 b = &(table->buckets[idx]);
815 entry->next = *b;
816 *b = entry;
817
818 if (bucket)
819 *bucket = b;
820
821 table->n_entries += 1;
822
823 /* note we ONLY rebuild when ADDING - because you can iterate over a
824 * table and remove entries safely.
825 */
826 if (table->n_entries >= table->hi_rebuild_size ||
827 table->n_entries < table->lo_rebuild_size)
828 rebuild_table (table);
829 }
830
831 static DBusHashEntry*
add_entry(DBusHashTable * table,unsigned int idx,void * key,DBusHashEntry *** bucket,DBusPreallocatedHash * preallocated)832 add_entry (DBusHashTable *table,
833 unsigned int idx,
834 void *key,
835 DBusHashEntry ***bucket,
836 DBusPreallocatedHash *preallocated)
837 {
838 DBusHashEntry *entry;
839
840 if (preallocated == NULL)
841 {
842 entry = alloc_entry (table);
843 if (entry == NULL)
844 {
845 if (bucket)
846 *bucket = NULL;
847 return NULL;
848 }
849 }
850 else
851 {
852 entry = (DBusHashEntry*) preallocated;
853 }
854
855 add_allocated_entry (table, entry, idx, key, bucket);
856
857 return entry;
858 }
859
860 /* This is g_str_hash from GLib which was
861 * extensively discussed/tested/profiled
862 */
863 static unsigned int
string_hash(const char * str)864 string_hash (const char *str)
865 {
866 const char *p = str;
867 unsigned int h = *p;
868
869 if (h)
870 for (p += 1; *p != '\0'; p++)
871 h = (h << 5) - h + *p;
872
873 return h;
874 }
875
876 #ifdef DBUS_BUILD_TESTS
877 /* This hashes a memory block with two nul-terminated strings
878 * in it, used in dbus-object-registry.c at the moment.
879 */
880 static unsigned int
two_strings_hash(const char * str)881 two_strings_hash (const char *str)
882 {
883 const char *p = str;
884 unsigned int h = *p;
885
886 if (h)
887 for (p += 1; *p != '\0'; p++)
888 h = (h << 5) - h + *p;
889
890 for (p += 1; *p != '\0'; p++)
891 h = (h << 5) - h + *p;
892
893 return h;
894 }
895 #endif /* DBUS_BUILD_TESTS */
896
897 /** Key comparison function */
898 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
899
900 static DBusHashEntry*
find_generic_function(DBusHashTable * table,void * key,unsigned int idx,KeyCompareFunc compare_func,dbus_bool_t create_if_not_found,DBusHashEntry *** bucket,DBusPreallocatedHash * preallocated)901 find_generic_function (DBusHashTable *table,
902 void *key,
903 unsigned int idx,
904 KeyCompareFunc compare_func,
905 dbus_bool_t create_if_not_found,
906 DBusHashEntry ***bucket,
907 DBusPreallocatedHash *preallocated)
908 {
909 DBusHashEntry *entry;
910
911 if (bucket)
912 *bucket = NULL;
913
914 /* Search all of the entries in this bucket. */
915 entry = table->buckets[idx];
916 while (entry != NULL)
917 {
918 if ((compare_func == NULL && key == entry->key) ||
919 (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
920 {
921 if (bucket)
922 *bucket = &(table->buckets[idx]);
923
924 if (preallocated)
925 _dbus_hash_table_free_preallocated_entry (table, preallocated);
926
927 return entry;
928 }
929
930 entry = entry->next;
931 }
932
933 if (create_if_not_found)
934 entry = add_entry (table, idx, key, bucket, preallocated);
935 else if (preallocated)
936 _dbus_hash_table_free_preallocated_entry (table, preallocated);
937
938 return entry;
939 }
940
941 static DBusHashEntry*
find_string_function(DBusHashTable * table,void * key,dbus_bool_t create_if_not_found,DBusHashEntry *** bucket,DBusPreallocatedHash * preallocated)942 find_string_function (DBusHashTable *table,
943 void *key,
944 dbus_bool_t create_if_not_found,
945 DBusHashEntry ***bucket,
946 DBusPreallocatedHash *preallocated)
947 {
948 unsigned int idx;
949
950 idx = string_hash (key) & table->mask;
951
952 return find_generic_function (table, key, idx,
953 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
954 preallocated);
955 }
956
957 #ifdef DBUS_BUILD_TESTS
958 static int
two_strings_cmp(const char * a,const char * b)959 two_strings_cmp (const char *a,
960 const char *b)
961 {
962 size_t len_a;
963 size_t len_b;
964 int res;
965
966 res = strcmp (a, b);
967 if (res != 0)
968 return res;
969
970 len_a = strlen (a);
971 len_b = strlen (b);
972
973 return strcmp (a + len_a + 1, b + len_b + 1);
974 }
975 #endif
976
977 #ifdef DBUS_BUILD_TESTS
978 static DBusHashEntry*
find_two_strings_function(DBusHashTable * table,void * key,dbus_bool_t create_if_not_found,DBusHashEntry *** bucket,DBusPreallocatedHash * preallocated)979 find_two_strings_function (DBusHashTable *table,
980 void *key,
981 dbus_bool_t create_if_not_found,
982 DBusHashEntry ***bucket,
983 DBusPreallocatedHash *preallocated)
984 {
985 unsigned int idx;
986
987 idx = two_strings_hash (key) & table->mask;
988
989 return find_generic_function (table, key, idx,
990 (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
991 preallocated);
992 }
993 #endif /* DBUS_BUILD_TESTS */
994
995 static DBusHashEntry*
find_direct_function(DBusHashTable * table,void * key,dbus_bool_t create_if_not_found,DBusHashEntry *** bucket,DBusPreallocatedHash * preallocated)996 find_direct_function (DBusHashTable *table,
997 void *key,
998 dbus_bool_t create_if_not_found,
999 DBusHashEntry ***bucket,
1000 DBusPreallocatedHash *preallocated)
1001 {
1002 unsigned int idx;
1003
1004 idx = RANDOM_INDEX (table, key) & table->mask;
1005
1006
1007 return find_generic_function (table, key, idx,
1008 NULL, create_if_not_found, bucket,
1009 preallocated);
1010 }
1011
1012 static void
rebuild_table(DBusHashTable * table)1013 rebuild_table (DBusHashTable *table)
1014 {
1015 int old_size;
1016 int new_buckets;
1017 DBusHashEntry **old_buckets;
1018 DBusHashEntry **old_chain;
1019 DBusHashEntry *entry;
1020 dbus_bool_t growing;
1021
1022 /*
1023 * Allocate and initialize the new bucket array, and set up
1024 * hashing constants for new array size.
1025 */
1026
1027 growing = table->n_entries >= table->hi_rebuild_size;
1028
1029 old_size = table->n_buckets;
1030 old_buckets = table->buckets;
1031
1032 if (growing)
1033 {
1034 /* overflow paranoia */
1035 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
1036 table->down_shift >= 0)
1037 new_buckets = table->n_buckets * 4;
1038 else
1039 return; /* can't grow anymore */
1040 }
1041 else
1042 {
1043 new_buckets = table->n_buckets / 4;
1044 if (new_buckets < DBUS_SMALL_HASH_TABLE)
1045 return; /* don't bother shrinking this far */
1046 }
1047
1048 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
1049 if (table->buckets == NULL)
1050 {
1051 /* out of memory, yay - just don't reallocate, the table will
1052 * still work, albeit more slowly.
1053 */
1054 table->buckets = old_buckets;
1055 return;
1056 }
1057
1058 table->n_buckets = new_buckets;
1059
1060 if (growing)
1061 {
1062 table->lo_rebuild_size = table->hi_rebuild_size;
1063 table->hi_rebuild_size *= 4;
1064
1065 table->down_shift -= 2; /* keep 2 more high bits */
1066 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
1067 }
1068 else
1069 {
1070 table->hi_rebuild_size = table->lo_rebuild_size;
1071 table->lo_rebuild_size /= 4;
1072
1073 table->down_shift += 2; /* keep 2 fewer high bits */
1074 table->mask = table->mask >> 2; /* keep 2 fewer high bits */
1075 }
1076
1077 #if 0
1078 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
1079 growing ? "GROW" : "SHRINK",
1080 table->lo_rebuild_size,
1081 table->hi_rebuild_size,
1082 table->down_shift,
1083 table->mask);
1084 #endif
1085
1086 _dbus_assert (table->lo_rebuild_size >= 0);
1087 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
1088 _dbus_assert (table->mask != 0);
1089 /* the mask is essentially the max index */
1090 _dbus_assert (table->mask < table->n_buckets);
1091
1092 /*
1093 * Rehash all of the existing entries into the new bucket array.
1094 */
1095
1096 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1097 {
1098 for (entry = *old_chain; entry != NULL; entry = *old_chain)
1099 {
1100 unsigned int idx;
1101 DBusHashEntry **bucket;
1102
1103 *old_chain = entry->next;
1104 switch (table->key_type)
1105 {
1106 case DBUS_HASH_STRING:
1107 idx = string_hash (entry->key) & table->mask;
1108 break;
1109 case DBUS_HASH_TWO_STRINGS:
1110 #ifdef DBUS_BUILD_TESTS
1111 idx = two_strings_hash (entry->key) & table->mask;
1112 #else
1113 idx = 0;
1114 _dbus_assert_not_reached ("two-strings is not enabled");
1115 #endif
1116 break;
1117 case DBUS_HASH_INT:
1118 case DBUS_HASH_ULONG:
1119 case DBUS_HASH_POINTER:
1120 idx = RANDOM_INDEX (table, entry->key);
1121 break;
1122 default:
1123 idx = 0;
1124 _dbus_assert_not_reached ("Unknown hash table type");
1125 break;
1126 }
1127
1128 bucket = &(table->buckets[idx]);
1129 entry->next = *bucket;
1130 *bucket = entry;
1131 }
1132 }
1133
1134 /* Free the old bucket array, if it was dynamically allocated. */
1135
1136 if (old_buckets != table->static_buckets)
1137 dbus_free (old_buckets);
1138 }
1139
1140 /**
1141 * Looks up the value for a given string in a hash table
1142 * of type #DBUS_HASH_STRING. Returns %NULL if the value
1143 * is not present. (A not-present entry is indistinguishable
1144 * from an entry with a value of %NULL.)
1145 * @param table the hash table.
1146 * @param key the string to look up.
1147 * @returns the value of the hash entry.
1148 */
1149 void*
_dbus_hash_table_lookup_string(DBusHashTable * table,const char * key)1150 _dbus_hash_table_lookup_string (DBusHashTable *table,
1151 const char *key)
1152 {
1153 DBusHashEntry *entry;
1154
1155 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1156
1157 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1158
1159 if (entry)
1160 return entry->value;
1161 else
1162 return NULL;
1163 }
1164
1165 #ifdef DBUS_BUILD_TESTS
1166 /**
1167 * Looks up the value for a given string in a hash table
1168 * of type #DBUS_HASH_TWO_STRINGS. Returns %NULL if the value
1169 * is not present. (A not-present entry is indistinguishable
1170 * from an entry with a value of %NULL.)
1171 * @param table the hash table.
1172 * @param key the string to look up.
1173 * @returns the value of the hash entry.
1174 */
1175 void*
_dbus_hash_table_lookup_two_strings(DBusHashTable * table,const char * key)1176 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
1177 const char *key)
1178 {
1179 DBusHashEntry *entry;
1180
1181 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
1182
1183 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1184
1185 if (entry)
1186 return entry->value;
1187 else
1188 return NULL;
1189 }
1190 #endif /* DBUS_BUILD_TESTS */
1191
1192 /**
1193 * Looks up the value for a given integer in a hash table
1194 * of type #DBUS_HASH_INT. Returns %NULL if the value
1195 * is not present. (A not-present entry is indistinguishable
1196 * from an entry with a value of %NULL.)
1197 * @param table the hash table.
1198 * @param key the integer to look up.
1199 * @returns the value of the hash entry.
1200 */
1201 void*
_dbus_hash_table_lookup_int(DBusHashTable * table,int key)1202 _dbus_hash_table_lookup_int (DBusHashTable *table,
1203 int key)
1204 {
1205 DBusHashEntry *entry;
1206
1207 _dbus_assert (table->key_type == DBUS_HASH_INT);
1208
1209 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1210
1211 if (entry)
1212 return entry->value;
1213 else
1214 return NULL;
1215 }
1216
1217 #ifdef DBUS_BUILD_TESTS
1218 /* disabled since it's only used for testing */
1219 /**
1220 * Looks up the value for a given integer in a hash table
1221 * of type #DBUS_HASH_POINTER. Returns %NULL if the value
1222 * is not present. (A not-present entry is indistinguishable
1223 * from an entry with a value of %NULL.)
1224 * @param table the hash table.
1225 * @param key the integer to look up.
1226 * @returns the value of the hash entry.
1227 */
1228 void*
_dbus_hash_table_lookup_pointer(DBusHashTable * table,void * key)1229 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
1230 void *key)
1231 {
1232 DBusHashEntry *entry;
1233
1234 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1235
1236 entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
1237
1238 if (entry)
1239 return entry->value;
1240 else
1241 return NULL;
1242 }
1243 #endif /* DBUS_BUILD_TESTS */
1244
1245 /**
1246 * Looks up the value for a given integer in a hash table
1247 * of type #DBUS_HASH_ULONG. Returns %NULL if the value
1248 * is not present. (A not-present entry is indistinguishable
1249 * from an entry with a value of %NULL.)
1250 * @param table the hash table.
1251 * @param key the integer to look up.
1252 * @returns the value of the hash entry.
1253 */
1254 void*
_dbus_hash_table_lookup_ulong(DBusHashTable * table,unsigned long key)1255 _dbus_hash_table_lookup_ulong (DBusHashTable *table,
1256 unsigned long key)
1257 {
1258 DBusHashEntry *entry;
1259
1260 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
1261
1262 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1263
1264 if (entry)
1265 return entry->value;
1266 else
1267 return NULL;
1268 }
1269
1270 /**
1271 * Removes the hash entry for the given key. If no hash entry
1272 * for the key exists, does nothing.
1273 *
1274 * @param table the hash table.
1275 * @param key the hash key.
1276 * @returns #TRUE if the entry existed
1277 */
1278 dbus_bool_t
_dbus_hash_table_remove_string(DBusHashTable * table,const char * key)1279 _dbus_hash_table_remove_string (DBusHashTable *table,
1280 const char *key)
1281 {
1282 DBusHashEntry *entry;
1283 DBusHashEntry **bucket;
1284
1285 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1286
1287 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1288
1289 if (entry)
1290 {
1291 remove_entry (table, bucket, entry);
1292 return TRUE;
1293 }
1294 else
1295 return FALSE;
1296 }
1297
1298 #ifdef DBUS_BUILD_TESTS
1299 /**
1300 * Removes the hash entry for the given key. If no hash entry
1301 * for the key exists, does nothing.
1302 *
1303 * @param table the hash table.
1304 * @param key the hash key.
1305 * @returns #TRUE if the entry existed
1306 */
1307 dbus_bool_t
_dbus_hash_table_remove_two_strings(DBusHashTable * table,const char * key)1308 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
1309 const char *key)
1310 {
1311 DBusHashEntry *entry;
1312 DBusHashEntry **bucket;
1313
1314 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
1315
1316 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1317
1318 if (entry)
1319 {
1320 remove_entry (table, bucket, entry);
1321 return TRUE;
1322 }
1323 else
1324 return FALSE;
1325 }
1326 #endif /* DBUS_BUILD_TESTS */
1327
1328 /**
1329 * Removes the hash entry for the given key. If no hash entry
1330 * for the key exists, does nothing.
1331 *
1332 * @param table the hash table.
1333 * @param key the hash key.
1334 * @returns #TRUE if the entry existed
1335 */
1336 dbus_bool_t
_dbus_hash_table_remove_int(DBusHashTable * table,int key)1337 _dbus_hash_table_remove_int (DBusHashTable *table,
1338 int key)
1339 {
1340 DBusHashEntry *entry;
1341 DBusHashEntry **bucket;
1342
1343 _dbus_assert (table->key_type == DBUS_HASH_INT);
1344
1345 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1346
1347 if (entry)
1348 {
1349 remove_entry (table, bucket, entry);
1350 return TRUE;
1351 }
1352 else
1353 return FALSE;
1354 }
1355
1356 #ifdef DBUS_BUILD_TESTS
1357 /* disabled since it's only used for testing */
1358 /**
1359 * Removes the hash entry for the given key. If no hash entry
1360 * for the key exists, does nothing.
1361 *
1362 * @param table the hash table.
1363 * @param key the hash key.
1364 * @returns #TRUE if the entry existed
1365 */
1366 dbus_bool_t
_dbus_hash_table_remove_pointer(DBusHashTable * table,void * key)1367 _dbus_hash_table_remove_pointer (DBusHashTable *table,
1368 void *key)
1369 {
1370 DBusHashEntry *entry;
1371 DBusHashEntry **bucket;
1372
1373 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1374
1375 entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
1376
1377 if (entry)
1378 {
1379 remove_entry (table, bucket, entry);
1380 return TRUE;
1381 }
1382 else
1383 return FALSE;
1384 }
1385 #endif /* DBUS_BUILD_TESTS */
1386
1387 /**
1388 * Removes the hash entry for the given key. If no hash entry
1389 * for the key exists, does nothing.
1390 *
1391 * @param table the hash table.
1392 * @param key the hash key.
1393 * @returns #TRUE if the entry existed
1394 */
1395 dbus_bool_t
_dbus_hash_table_remove_ulong(DBusHashTable * table,unsigned long key)1396 _dbus_hash_table_remove_ulong (DBusHashTable *table,
1397 unsigned long key)
1398 {
1399 DBusHashEntry *entry;
1400 DBusHashEntry **bucket;
1401
1402 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
1403
1404 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1405
1406 if (entry)
1407 {
1408 remove_entry (table, bucket, entry);
1409 return TRUE;
1410 }
1411 else
1412 return FALSE;
1413 }
1414
1415 /**
1416 * Creates a hash entry with the given key and value.
1417 * The key and value are not copied; they are stored
1418 * in the hash table by reference. If an entry with the
1419 * given key already exists, the previous key and value
1420 * are overwritten (and freed if the hash table has
1421 * a key_free_function and/or value_free_function).
1422 *
1423 * Returns #FALSE if memory for the new hash entry
1424 * can't be allocated.
1425 *
1426 * @param table the hash table.
1427 * @param key the hash entry key.
1428 * @param value the hash entry value.
1429 */
1430 dbus_bool_t
_dbus_hash_table_insert_string(DBusHashTable * table,char * key,void * value)1431 _dbus_hash_table_insert_string (DBusHashTable *table,
1432 char *key,
1433 void *value)
1434 {
1435 DBusPreallocatedHash *preallocated;
1436
1437 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1438
1439 preallocated = _dbus_hash_table_preallocate_entry (table);
1440 if (preallocated == NULL)
1441 return FALSE;
1442
1443 _dbus_hash_table_insert_string_preallocated (table, preallocated,
1444 key, value);
1445
1446 return TRUE;
1447 }
1448
1449 #ifdef DBUS_BUILD_TESTS
1450 /**
1451 * Creates a hash entry with the given key and value.
1452 * The key and value are not copied; they are stored
1453 * in the hash table by reference. If an entry with the
1454 * given key already exists, the previous key and value
1455 * are overwritten (and freed if the hash table has
1456 * a key_free_function and/or value_free_function).
1457 *
1458 * Returns #FALSE if memory for the new hash entry
1459 * can't be allocated.
1460 *
1461 * @param table the hash table.
1462 * @param key the hash entry key.
1463 * @param value the hash entry value.
1464 */
1465 dbus_bool_t
_dbus_hash_table_insert_two_strings(DBusHashTable * table,char * key,void * value)1466 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
1467 char *key,
1468 void *value)
1469 {
1470 DBusHashEntry *entry;
1471
1472 _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
1473
1474 entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
1475
1476 if (entry == NULL)
1477 return FALSE; /* no memory */
1478
1479 if (table->free_key_function && entry->key != key)
1480 (* table->free_key_function) (entry->key);
1481
1482 if (table->free_value_function && entry->value != value)
1483 (* table->free_value_function) (entry->value);
1484
1485 entry->key = key;
1486 entry->value = value;
1487
1488 return TRUE;
1489 }
1490 #endif /* DBUS_BUILD_TESTS */
1491
1492 /**
1493 * Creates a hash entry with the given key and value.
1494 * The key and value are not copied; they are stored
1495 * in the hash table by reference. If an entry with the
1496 * given key already exists, the previous key and value
1497 * are overwritten (and freed if the hash table has
1498 * a key_free_function and/or value_free_function).
1499 *
1500 * Returns #FALSE if memory for the new hash entry
1501 * can't be allocated.
1502 *
1503 * @param table the hash table.
1504 * @param key the hash entry key.
1505 * @param value the hash entry value.
1506 */
1507 dbus_bool_t
_dbus_hash_table_insert_int(DBusHashTable * table,int key,void * value)1508 _dbus_hash_table_insert_int (DBusHashTable *table,
1509 int key,
1510 void *value)
1511 {
1512 DBusHashEntry *entry;
1513
1514 _dbus_assert (table->key_type == DBUS_HASH_INT);
1515
1516 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1517
1518 if (entry == NULL)
1519 return FALSE; /* no memory */
1520
1521 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1522 (* table->free_key_function) (entry->key);
1523
1524 if (table->free_value_function && entry->value != value)
1525 (* table->free_value_function) (entry->value);
1526
1527 entry->key = _DBUS_INT_TO_POINTER (key);
1528 entry->value = value;
1529
1530 return TRUE;
1531 }
1532
1533 #ifdef DBUS_BUILD_TESTS
1534 /* disabled since it's only used for testing */
1535 /**
1536 * Creates a hash entry with the given key and value.
1537 * The key and value are not copied; they are stored
1538 * in the hash table by reference. If an entry with the
1539 * given key already exists, the previous key and value
1540 * are overwritten (and freed if the hash table has
1541 * a key_free_function and/or value_free_function).
1542 *
1543 * Returns #FALSE if memory for the new hash entry
1544 * can't be allocated.
1545 *
1546 * @param table the hash table.
1547 * @param key the hash entry key.
1548 * @param value the hash entry value.
1549 */
1550 dbus_bool_t
_dbus_hash_table_insert_pointer(DBusHashTable * table,void * key,void * value)1551 _dbus_hash_table_insert_pointer (DBusHashTable *table,
1552 void *key,
1553 void *value)
1554 {
1555 DBusHashEntry *entry;
1556
1557 _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1558
1559 entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
1560
1561 if (entry == NULL)
1562 return FALSE; /* no memory */
1563
1564 if (table->free_key_function && entry->key != key)
1565 (* table->free_key_function) (entry->key);
1566
1567 if (table->free_value_function && entry->value != value)
1568 (* table->free_value_function) (entry->value);
1569
1570 entry->key = key;
1571 entry->value = value;
1572
1573 return TRUE;
1574 }
1575 #endif /* DBUS_BUILD_TESTS */
1576
1577 /**
1578 * Creates a hash entry with the given key and value.
1579 * The key and value are not copied; they are stored
1580 * in the hash table by reference. If an entry with the
1581 * given key already exists, the previous key and value
1582 * are overwritten (and freed if the hash table has
1583 * a key_free_function and/or value_free_function).
1584 *
1585 * Returns #FALSE if memory for the new hash entry
1586 * can't be allocated.
1587 *
1588 * @param table the hash table.
1589 * @param key the hash entry key.
1590 * @param value the hash entry value.
1591 */
1592 dbus_bool_t
_dbus_hash_table_insert_ulong(DBusHashTable * table,unsigned long key,void * value)1593 _dbus_hash_table_insert_ulong (DBusHashTable *table,
1594 unsigned long key,
1595 void *value)
1596 {
1597 DBusHashEntry *entry;
1598
1599 _dbus_assert (table->key_type == DBUS_HASH_ULONG);
1600
1601 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1602
1603 if (entry == NULL)
1604 return FALSE; /* no memory */
1605
1606 if (table->free_key_function && entry->key != (void*) key)
1607 (* table->free_key_function) (entry->key);
1608
1609 if (table->free_value_function && entry->value != value)
1610 (* table->free_value_function) (entry->value);
1611
1612 entry->key = (void*) key;
1613 entry->value = value;
1614
1615 return TRUE;
1616 }
1617
1618 /**
1619 * Preallocate an opaque data blob that allows us to insert into the
1620 * hash table at a later time without allocating any memory.
1621 *
1622 * @param table the hash table
1623 * @returns the preallocated data, or #NULL if no memory
1624 */
1625 DBusPreallocatedHash*
_dbus_hash_table_preallocate_entry(DBusHashTable * table)1626 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
1627 {
1628 DBusHashEntry *entry;
1629
1630 entry = alloc_entry (table);
1631
1632 return (DBusPreallocatedHash*) entry;
1633 }
1634
1635 /**
1636 * Frees an opaque DBusPreallocatedHash that was *not* used
1637 * in order to insert into the hash table.
1638 *
1639 * @param table the hash table
1640 * @param preallocated the preallocated data
1641 */
1642 void
_dbus_hash_table_free_preallocated_entry(DBusHashTable * table,DBusPreallocatedHash * preallocated)1643 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table,
1644 DBusPreallocatedHash *preallocated)
1645 {
1646 DBusHashEntry *entry;
1647
1648 _dbus_assert (preallocated != NULL);
1649
1650 entry = (DBusHashEntry*) preallocated;
1651
1652 /* Don't use free_entry(), since this entry has no key/data */
1653 _dbus_mem_pool_dealloc (table->entry_pool, entry);
1654 }
1655
1656 /**
1657 * Inserts a string-keyed entry into the hash table, using a
1658 * preallocated data block from
1659 * _dbus_hash_table_preallocate_entry(). This function cannot fail due
1660 * to lack of memory. The DBusPreallocatedHash object is consumed and
1661 * should not be reused or freed. Otherwise this function works
1662 * just like _dbus_hash_table_insert_string().
1663 *
1664 * @param table the hash table
1665 * @param preallocated the preallocated data
1666 * @param key the hash key
1667 * @param value the value
1668 */
1669 void
_dbus_hash_table_insert_string_preallocated(DBusHashTable * table,DBusPreallocatedHash * preallocated,char * key,void * value)1670 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table,
1671 DBusPreallocatedHash *preallocated,
1672 char *key,
1673 void *value)
1674 {
1675 DBusHashEntry *entry;
1676
1677 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1678 _dbus_assert (preallocated != NULL);
1679
1680 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1681
1682 _dbus_assert (entry != NULL);
1683
1684 if (table->free_key_function && entry->key != key)
1685 (* table->free_key_function) (entry->key);
1686
1687 if (table->free_value_function && entry->value != value)
1688 (* table->free_value_function) (entry->value);
1689
1690 entry->key = key;
1691 entry->value = value;
1692 }
1693
1694 /**
1695 * Gets the number of hash entries in a hash table.
1696 *
1697 * @param table the hash table.
1698 * @returns the number of entries in the table.
1699 */
1700 int
_dbus_hash_table_get_n_entries(DBusHashTable * table)1701 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1702 {
1703 return table->n_entries;
1704 }
1705
1706 /** @} */
1707
1708 #ifdef DBUS_BUILD_TESTS
1709 #include "dbus-test.h"
1710 #include <stdio.h>
1711
1712 /* If you're wondering why the hash table test takes
1713 * forever to run, it's because we call this function
1714 * in inner loops thus making things quadratic.
1715 */
1716 static int
count_entries(DBusHashTable * table)1717 count_entries (DBusHashTable *table)
1718 {
1719 DBusHashIter iter;
1720 int count;
1721
1722 count = 0;
1723 _dbus_hash_iter_init (table, &iter);
1724 while (_dbus_hash_iter_next (&iter))
1725 ++count;
1726
1727 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1728
1729 return count;
1730 }
1731
1732 /* Copy the foo\0bar\0 double string thing */
1733 static char*
_dbus_strdup2(const char * str)1734 _dbus_strdup2 (const char *str)
1735 {
1736 size_t len;
1737 char *copy;
1738
1739 if (str == NULL)
1740 return NULL;
1741
1742 len = strlen (str);
1743 len += strlen ((str + len + 1));
1744
1745 copy = dbus_malloc (len + 2);
1746 if (copy == NULL)
1747 return NULL;
1748
1749 memcpy (copy, str, len + 2);
1750
1751 return copy;
1752 }
1753
1754 /**
1755 * @ingroup DBusHashTableInternals
1756 * Unit test for DBusHashTable
1757 * @returns #TRUE on success.
1758 */
1759 dbus_bool_t
_dbus_hash_test(void)1760 _dbus_hash_test (void)
1761 {
1762 int i;
1763 DBusHashTable *table1;
1764 DBusHashTable *table2;
1765 DBusHashTable *table3;
1766 DBusHashTable *table4;
1767 DBusHashIter iter;
1768 #define N_HASH_KEYS 5000
1769 char **keys;
1770 dbus_bool_t ret = FALSE;
1771
1772 keys = dbus_new (char *, N_HASH_KEYS);
1773 if (keys == NULL)
1774 _dbus_assert_not_reached ("no memory");
1775
1776 for (i = 0; i < N_HASH_KEYS; i++)
1777 {
1778 keys[i] = dbus_malloc (128);
1779
1780 if (keys[i] == NULL)
1781 _dbus_assert_not_reached ("no memory");
1782 }
1783
1784 printf ("Computing test hash keys...\n");
1785 i = 0;
1786 while (i < N_HASH_KEYS)
1787 {
1788 int len;
1789
1790 /* all the hash keys are TWO_STRINGS, but
1791 * then we can also use those as regular strings.
1792 */
1793
1794 len = sprintf (keys[i], "Hash key %d", i);
1795 sprintf (keys[i] + len + 1, "Two string %d", i);
1796 _dbus_assert (*(keys[i] + len) == '\0');
1797 _dbus_assert (*(keys[i] + len + 1) != '\0');
1798 ++i;
1799 }
1800 printf ("... done.\n");
1801
1802 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1803 dbus_free, dbus_free);
1804 if (table1 == NULL)
1805 goto out;
1806
1807 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1808 NULL, dbus_free);
1809 if (table2 == NULL)
1810 goto out;
1811
1812 table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
1813 NULL, dbus_free);
1814 if (table3 == NULL)
1815 goto out;
1816
1817 table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
1818 dbus_free, dbus_free);
1819 if (table4 == NULL)
1820 goto out;
1821
1822
1823 /* Insert and remove a bunch of stuff, counting the table in between
1824 * to be sure it's not broken and that iteration works
1825 */
1826 i = 0;
1827 while (i < 3000)
1828 {
1829 void *value;
1830 char *key;
1831
1832 key = _dbus_strdup (keys[i]);
1833 if (key == NULL)
1834 goto out;
1835 value = _dbus_strdup ("Value!");
1836 if (value == NULL)
1837 goto out;
1838
1839 if (!_dbus_hash_table_insert_string (table1,
1840 key, value))
1841 goto out;
1842
1843 value = _dbus_strdup (keys[i]);
1844 if (value == NULL)
1845 goto out;
1846
1847 if (!_dbus_hash_table_insert_int (table2,
1848 i, value))
1849 goto out;
1850
1851 value = _dbus_strdup (keys[i]);
1852 if (value == NULL)
1853 goto out;
1854
1855 if (!_dbus_hash_table_insert_ulong (table3,
1856 i, value))
1857 goto out;
1858
1859 key = _dbus_strdup2 (keys[i]);
1860 if (key == NULL)
1861 goto out;
1862 value = _dbus_strdup ("Value!");
1863 if (value == NULL)
1864 goto out;
1865
1866 if (!_dbus_hash_table_insert_two_strings (table4,
1867 key, value))
1868 goto out;
1869
1870 _dbus_assert (count_entries (table1) == i + 1);
1871 _dbus_assert (count_entries (table2) == i + 1);
1872 _dbus_assert (count_entries (table3) == i + 1);
1873 _dbus_assert (count_entries (table4) == i + 1);
1874
1875 value = _dbus_hash_table_lookup_string (table1, keys[i]);
1876 _dbus_assert (value != NULL);
1877 _dbus_assert (strcmp (value, "Value!") == 0);
1878
1879 value = _dbus_hash_table_lookup_int (table2, i);
1880 _dbus_assert (value != NULL);
1881 _dbus_assert (strcmp (value, keys[i]) == 0);
1882
1883 value = _dbus_hash_table_lookup_ulong (table3, i);
1884 _dbus_assert (value != NULL);
1885 _dbus_assert (strcmp (value, keys[i]) == 0);
1886
1887 value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
1888 _dbus_assert (value != NULL);
1889 _dbus_assert (strcmp (value, "Value!") == 0);
1890
1891 ++i;
1892 }
1893
1894 --i;
1895 while (i >= 0)
1896 {
1897 _dbus_hash_table_remove_string (table1,
1898 keys[i]);
1899
1900 _dbus_hash_table_remove_int (table2, i);
1901
1902 _dbus_hash_table_remove_ulong (table3, i);
1903
1904 _dbus_hash_table_remove_two_strings (table4,
1905 keys[i]);
1906
1907 _dbus_assert (count_entries (table1) == i);
1908 _dbus_assert (count_entries (table2) == i);
1909 _dbus_assert (count_entries (table3) == i);
1910 _dbus_assert (count_entries (table4) == i);
1911
1912 --i;
1913 }
1914
1915 _dbus_hash_table_ref (table1);
1916 _dbus_hash_table_ref (table2);
1917 _dbus_hash_table_ref (table3);
1918 _dbus_hash_table_ref (table4);
1919 _dbus_hash_table_unref (table1);
1920 _dbus_hash_table_unref (table2);
1921 _dbus_hash_table_unref (table3);
1922 _dbus_hash_table_unref (table4);
1923 _dbus_hash_table_unref (table1);
1924 _dbus_hash_table_unref (table2);
1925 _dbus_hash_table_unref (table3);
1926 _dbus_hash_table_unref (table4);
1927 table3 = NULL;
1928
1929 /* Insert a bunch of stuff then check
1930 * that iteration works correctly (finds the right
1931 * values, iter_set_value works, etc.)
1932 */
1933 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1934 dbus_free, dbus_free);
1935 if (table1 == NULL)
1936 goto out;
1937
1938 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1939 NULL, dbus_free);
1940 if (table2 == NULL)
1941 goto out;
1942
1943 i = 0;
1944 while (i < 5000)
1945 {
1946 char *key;
1947 void *value;
1948
1949 key = _dbus_strdup (keys[i]);
1950 if (key == NULL)
1951 goto out;
1952 value = _dbus_strdup ("Value!");
1953 if (value == NULL)
1954 goto out;
1955
1956 if (!_dbus_hash_table_insert_string (table1,
1957 key, value))
1958 goto out;
1959
1960 value = _dbus_strdup (keys[i]);
1961 if (value == NULL)
1962 goto out;
1963
1964 if (!_dbus_hash_table_insert_int (table2,
1965 i, value))
1966 goto out;
1967
1968 _dbus_assert (count_entries (table1) == i + 1);
1969 _dbus_assert (count_entries (table2) == i + 1);
1970
1971 ++i;
1972 }
1973
1974 _dbus_hash_iter_init (table1, &iter);
1975 while (_dbus_hash_iter_next (&iter))
1976 {
1977 const char *key;
1978 void *value;
1979
1980 key = _dbus_hash_iter_get_string_key (&iter);
1981 value = _dbus_hash_iter_get_value (&iter);
1982
1983 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1984
1985 value = _dbus_strdup ("Different value!");
1986 if (value == NULL)
1987 goto out;
1988
1989 _dbus_hash_iter_set_value (&iter, value);
1990
1991 _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1992 }
1993
1994 _dbus_hash_iter_init (table1, &iter);
1995 while (_dbus_hash_iter_next (&iter))
1996 {
1997 _dbus_hash_iter_remove_entry (&iter);
1998 _dbus_assert (count_entries (table1) == i - 1);
1999 --i;
2000 }
2001
2002 _dbus_hash_iter_init (table2, &iter);
2003 while (_dbus_hash_iter_next (&iter))
2004 {
2005 int key;
2006 void *value;
2007
2008 key = _dbus_hash_iter_get_int_key (&iter);
2009 value = _dbus_hash_iter_get_value (&iter);
2010
2011 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
2012
2013 value = _dbus_strdup ("Different value!");
2014 if (value == NULL)
2015 goto out;
2016
2017 _dbus_hash_iter_set_value (&iter, value);
2018
2019 _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
2020 }
2021
2022 i = count_entries (table2);
2023 _dbus_hash_iter_init (table2, &iter);
2024 while (_dbus_hash_iter_next (&iter))
2025 {
2026 _dbus_hash_iter_remove_entry (&iter);
2027 _dbus_assert (count_entries (table2) + 1 == i);
2028 --i;
2029 }
2030
2031 /* add/remove interleaved, to check that we grow/shrink the table
2032 * appropriately
2033 */
2034 i = 0;
2035 while (i < 1000)
2036 {
2037 char *key;
2038 void *value;
2039
2040 key = _dbus_strdup (keys[i]);
2041 if (key == NULL)
2042 goto out;
2043
2044 value = _dbus_strdup ("Value!");
2045 if (value == NULL)
2046 goto out;
2047
2048 if (!_dbus_hash_table_insert_string (table1,
2049 key, value))
2050 goto out;
2051
2052 ++i;
2053 }
2054
2055 --i;
2056 while (i >= 0)
2057 {
2058 char *key;
2059 void *value;
2060
2061 key = _dbus_strdup (keys[i]);
2062 if (key == NULL)
2063 goto out;
2064 value = _dbus_strdup ("Value!");
2065 if (value == NULL)
2066 goto out;
2067
2068 if (!_dbus_hash_table_remove_string (table1, keys[i]))
2069 goto out;
2070
2071 if (!_dbus_hash_table_insert_string (table1,
2072 key, value))
2073 goto out;
2074
2075 if (!_dbus_hash_table_remove_string (table1, keys[i]))
2076 goto out;
2077
2078 _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
2079
2080 --i;
2081 }
2082
2083 /* nuke these tables */
2084 _dbus_hash_table_unref (table1);
2085 _dbus_hash_table_unref (table2);
2086
2087
2088 /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
2089 * be sure that interface works.
2090 */
2091 table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
2092 dbus_free, dbus_free);
2093 if (table1 == NULL)
2094 goto out;
2095
2096 table2 = _dbus_hash_table_new (DBUS_HASH_INT,
2097 NULL, dbus_free);
2098 if (table2 == NULL)
2099 goto out;
2100
2101 i = 0;
2102 while (i < 3000)
2103 {
2104 void *value;
2105 char *key;
2106
2107 key = _dbus_strdup (keys[i]);
2108 if (key == NULL)
2109 goto out;
2110 value = _dbus_strdup ("Value!");
2111 if (value == NULL)
2112 goto out;
2113
2114 if (!_dbus_hash_iter_lookup (table1,
2115 key, TRUE, &iter))
2116 goto out;
2117 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
2118 _dbus_hash_iter_set_value (&iter, value);
2119
2120 value = _dbus_strdup (keys[i]);
2121 if (value == NULL)
2122 goto out;
2123
2124 if (!_dbus_hash_iter_lookup (table2,
2125 _DBUS_INT_TO_POINTER (i), TRUE, &iter))
2126 goto out;
2127 _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
2128 _dbus_hash_iter_set_value (&iter, value);
2129
2130 _dbus_assert (count_entries (table1) == i + 1);
2131 _dbus_assert (count_entries (table2) == i + 1);
2132
2133 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
2134 goto out;
2135
2136 value = _dbus_hash_iter_get_value (&iter);
2137 _dbus_assert (value != NULL);
2138 _dbus_assert (strcmp (value, "Value!") == 0);
2139
2140 /* Iterate just to be sure it works, though
2141 * it's a stupid thing to do
2142 */
2143 while (_dbus_hash_iter_next (&iter))
2144 ;
2145
2146 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
2147 goto out;
2148
2149 value = _dbus_hash_iter_get_value (&iter);
2150 _dbus_assert (value != NULL);
2151 _dbus_assert (strcmp (value, keys[i]) == 0);
2152
2153 /* Iterate just to be sure it works, though
2154 * it's a stupid thing to do
2155 */
2156 while (_dbus_hash_iter_next (&iter))
2157 ;
2158
2159 ++i;
2160 }
2161
2162 --i;
2163 while (i >= 0)
2164 {
2165 if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
2166 _dbus_assert_not_reached ("hash entry should have existed");
2167 _dbus_hash_iter_remove_entry (&iter);
2168
2169 if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
2170 _dbus_assert_not_reached ("hash entry should have existed");
2171 _dbus_hash_iter_remove_entry (&iter);
2172
2173 _dbus_assert (count_entries (table1) == i);
2174 _dbus_assert (count_entries (table2) == i);
2175
2176 --i;
2177 }
2178
2179 _dbus_hash_table_unref (table1);
2180 _dbus_hash_table_unref (table2);
2181
2182 ret = TRUE;
2183
2184 out:
2185 for (i = 0; i < N_HASH_KEYS; i++)
2186 dbus_free (keys[i]);
2187
2188 dbus_free (keys);
2189
2190 return ret;
2191 }
2192
2193 #endif /* DBUS_BUILD_TESTS */
2194