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