D-Bus  1.4.10
dbus-hash.c
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 
104 #define REBUILD_MULTIPLIER 3
105 
122 #define RANDOM_INDEX(table, i) \
123  (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
124 
130 #define DBUS_SMALL_HASH_TABLE 4
131 
136 
144 {
149  void *key;
150  void *value;
151 };
152 
156 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
157  void *key,
158  dbus_bool_t create_if_not_found,
159  DBusHashEntry ***bucket,
160  DBusPreallocatedHash *preallocated);
161 
169  int refcount;
179  int n_buckets;
182  int n_entries;
195  int mask;
207 };
208 
212 typedef struct
213 {
215  DBusHashEntry **bucket;
224 
225 static DBusHashEntry* find_direct_function (DBusHashTable *table,
226  void *key,
227  dbus_bool_t create_if_not_found,
228  DBusHashEntry ***bucket,
229  DBusPreallocatedHash *preallocated);
230 static DBusHashEntry* find_string_function (DBusHashTable *table,
231  void *key,
232  dbus_bool_t create_if_not_found,
233  DBusHashEntry ***bucket,
234  DBusPreallocatedHash *preallocated);
235 #ifdef DBUS_BUILD_TESTS
236 static DBusHashEntry* find_two_strings_function (DBusHashTable *table,
237  void *key,
238  dbus_bool_t create_if_not_found,
239  DBusHashEntry ***bucket,
240  DBusPreallocatedHash *preallocated);
241 #endif
242 static unsigned int string_hash (const char *str);
243 #ifdef DBUS_BUILD_TESTS
244 static unsigned int two_strings_hash (const char *str);
245 #endif
246 static void rebuild_table (DBusHashTable *table);
247 static DBusHashEntry* alloc_entry (DBusHashTable *table);
248 static void remove_entry (DBusHashTable *table,
249  DBusHashEntry **bucket,
250  DBusHashEntry *entry);
251 static void free_entry (DBusHashTable *table,
252  DBusHashEntry *entry);
253 static void free_entry_data (DBusHashTable *table,
254  DBusHashEntry *entry);
255 
256 
294  DBusFreeFunction key_free_function,
295  DBusFreeFunction value_free_function)
296 {
297  DBusHashTable *table;
298  DBusMemPool *entry_pool;
299 
300  table = dbus_new0 (DBusHashTable, 1);
301  if (table == NULL)
302  return NULL;
303 
304  entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
305  if (entry_pool == NULL)
306  {
307  dbus_free (table);
308  return NULL;
309  }
310 
311  table->refcount = 1;
312  table->entry_pool = entry_pool;
313 
315 
316  table->buckets = table->static_buckets;
318  table->n_entries = 0;
320  table->lo_rebuild_size = 0;
321  table->down_shift = 28;
322  table->mask = 3;
323  table->key_type = type;
324 
325  _dbus_assert (table->mask < table->n_buckets);
326 
327  switch (table->key_type)
328  {
329  case DBUS_HASH_INT:
330  case DBUS_HASH_POINTER:
331  case DBUS_HASH_UINTPTR:
332  table->find_function = find_direct_function;
333  break;
334  case DBUS_HASH_STRING:
335  table->find_function = find_string_function;
336  break;
338 #ifdef DBUS_BUILD_TESTS
339  table->find_function = find_two_strings_function;
340 #endif
341  break;
342  default:
343  _dbus_assert_not_reached ("Unknown hash table type");
344  break;
345  }
346 
347  table->free_key_function = key_free_function;
348  table->free_value_function = value_free_function;
349 
350  return table;
351 }
352 
353 
362 {
363  table->refcount += 1;
364 
365  return table;
366 }
367 
374 void
376 {
377  table->refcount -= 1;
378 
379  if (table->refcount == 0)
380  {
381 #if 0
382  DBusHashEntry *entry;
383  DBusHashEntry *next;
384  int i;
385 
386  /* Free the entries in the table. */
387  for (i = 0; i < table->n_buckets; i++)
388  {
389  entry = table->buckets[i];
390  while (entry != NULL)
391  {
392  next = entry->next;
393 
394  free_entry (table, entry);
395 
396  entry = next;
397  }
398  }
399 #else
400  DBusHashEntry *entry;
401  int i;
402 
403  /* Free the entries in the table. */
404  for (i = 0; i < table->n_buckets; i++)
405  {
406  entry = table->buckets[i];
407  while (entry != NULL)
408  {
409  free_entry_data (table, entry);
410 
411  entry = entry->next;
412  }
413  }
414  /* We can do this very quickly with memory pools ;-) */
416 #endif
417 
418  /* Free the bucket array, if it was dynamically allocated. */
419  if (table->buckets != table->static_buckets)
420  dbus_free (table->buckets);
421 
422  dbus_free (table);
423  }
424 }
425 
431 void
433 {
434  DBusHashIter iter;
435  _dbus_hash_iter_init (table, &iter);
436  while (_dbus_hash_iter_next (&iter))
437  {
439  }
440 }
441 
442 static DBusHashEntry*
443 alloc_entry (DBusHashTable *table)
444 {
445  DBusHashEntry *entry;
446 
447  entry = _dbus_mem_pool_alloc (table->entry_pool);
448 
449  return entry;
450 }
451 
452 static void
453 free_entry_data (DBusHashTable *table,
454  DBusHashEntry *entry)
455 {
456  if (table->free_key_function)
457  (* table->free_key_function) (entry->key);
458  if (table->free_value_function)
459  (* table->free_value_function) (entry->value);
460 }
461 
462 static void
463 free_entry (DBusHashTable *table,
464  DBusHashEntry *entry)
465 {
466  free_entry_data (table, entry);
467  _dbus_mem_pool_dealloc (table->entry_pool, entry);
468 }
469 
470 static void
471 remove_entry (DBusHashTable *table,
472  DBusHashEntry **bucket,
473  DBusHashEntry *entry)
474 {
475  _dbus_assert (table != NULL);
476  _dbus_assert (bucket != NULL);
477  _dbus_assert (*bucket != NULL);
478  _dbus_assert (entry != NULL);
479 
480  if (*bucket == entry)
481  *bucket = entry->next;
482  else
483  {
484  DBusHashEntry *prev;
485  prev = *bucket;
486 
487  while (prev->next != entry)
488  prev = prev->next;
489 
490  _dbus_assert (prev != NULL);
491 
492  prev->next = entry->next;
493  }
494 
495  table->n_entries -= 1;
496  free_entry (table, entry);
497 }
498 
530 void
532  DBusHashIter *iter)
533 {
534  DBusRealHashIter *real;
535 
536  _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
537 
538  real = (DBusRealHashIter*) iter;
539 
540  real->table = table;
541  real->bucket = NULL;
542  real->entry = NULL;
543  real->next_entry = NULL;
544  real->next_bucket = 0;
545  real->n_entries_on_init = table->n_entries;
546 }
547 
558 {
559  DBusRealHashIter *real;
560 
561  _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
562 
563  real = (DBusRealHashIter*) iter;
564 
565  /* if this assertion failed someone probably added hash entries
566  * during iteration, which is bad.
567  */
568  _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
569 
570  /* Remember that real->entry may have been deleted */
571 
572  while (real->next_entry == NULL)
573  {
574  if (real->next_bucket >= real->table->n_buckets)
575  {
576  /* invalidate iter and return false */
577  real->entry = NULL;
578  real->table = NULL;
579  real->bucket = NULL;
580  return FALSE;
581  }
582 
583  real->bucket = &(real->table->buckets[real->next_bucket]);
584  real->next_entry = *(real->bucket);
585  real->next_bucket += 1;
586  }
587 
588  _dbus_assert (real->next_entry != NULL);
589  _dbus_assert (real->bucket != NULL);
590 
591  real->entry = real->next_entry;
592  real->next_entry = real->entry->next;
593 
594  return TRUE;
595 }
596 
605 void
607 {
608  DBusRealHashIter *real;
609 
610  real = (DBusRealHashIter*) iter;
611 
612  _dbus_assert (real->table != NULL);
613  _dbus_assert (real->entry != NULL);
614  _dbus_assert (real->bucket != NULL);
615 
616  remove_entry (real->table, real->bucket, real->entry);
617 
618  real->entry = NULL; /* make it crash if you try to use this entry */
619 }
620 
626 void*
628 {
629  DBusRealHashIter *real;
630 
631  real = (DBusRealHashIter*) iter;
632 
633  _dbus_assert (real->table != NULL);
634  _dbus_assert (real->entry != NULL);
635 
636  return real->entry->value;
637 }
638 
649 void
651  void *value)
652 {
653  DBusRealHashIter *real;
654 
655  real = (DBusRealHashIter*) iter;
656 
657  _dbus_assert (real->table != NULL);
658  _dbus_assert (real->entry != NULL);
659 
660  if (real->table->free_value_function && value != real->entry->value)
661  (* real->table->free_value_function) (real->entry->value);
662 
663  real->entry->value = value;
664 }
665 
672 int
674 {
675  DBusRealHashIter *real;
676 
677  real = (DBusRealHashIter*) iter;
678 
679  _dbus_assert (real->table != NULL);
680  _dbus_assert (real->entry != NULL);
681 
682  return _DBUS_POINTER_TO_INT (real->entry->key);
683 }
684 
691 uintptr_t
693 {
694  DBusRealHashIter *real;
695 
696  real = (DBusRealHashIter*) iter;
697 
698  _dbus_assert (real->table != NULL);
699  _dbus_assert (real->entry != NULL);
700 
701  return (uintptr_t) real->entry->key;
702 }
703 
709 const char*
711 {
712  DBusRealHashIter *real;
713 
714  real = (DBusRealHashIter*) iter;
715 
716  _dbus_assert (real->table != NULL);
717  _dbus_assert (real->entry != NULL);
718 
719  return real->entry->key;
720 }
721 
722 #ifdef DBUS_BUILD_TESTS
723 
728 const char*
729 _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
730 {
731  DBusRealHashIter *real;
732 
733  real = (DBusRealHashIter*) iter;
734 
735  _dbus_assert (real->table != NULL);
736  _dbus_assert (real->entry != NULL);
737 
738  return real->entry->key;
739 }
740 #endif /* DBUS_BUILD_TESTS */
741 
775  void *key,
776  dbus_bool_t create_if_not_found,
777  DBusHashIter *iter)
778 {
779  DBusRealHashIter *real;
780  DBusHashEntry *entry;
781  DBusHashEntry **bucket;
782 
783  _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
784 
785  real = (DBusRealHashIter*) iter;
786 
787  entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
788 
789  if (entry == NULL)
790  return FALSE;
791 
792  real->table = table;
793  real->bucket = bucket;
794  real->entry = entry;
795  real->next_entry = entry->next;
796  real->next_bucket = (bucket - table->buckets) + 1;
797  real->n_entries_on_init = table->n_entries;
798 
799  _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
800 
801  return TRUE;
802 }
803 
804 static void
805 add_allocated_entry (DBusHashTable *table,
806  DBusHashEntry *entry,
807  unsigned int idx,
808  void *key,
809  DBusHashEntry ***bucket)
810 {
811  DBusHashEntry **b;
812 
813  entry->key = key;
814 
815  b = &(table->buckets[idx]);
816  entry->next = *b;
817  *b = entry;
818 
819  if (bucket)
820  *bucket = b;
821 
822  table->n_entries += 1;
823 
824  /* note we ONLY rebuild when ADDING - because you can iterate over a
825  * table and remove entries safely.
826  */
827  if (table->n_entries >= table->hi_rebuild_size ||
828  table->n_entries < table->lo_rebuild_size)
829  rebuild_table (table);
830 }
831 
832 static DBusHashEntry*
833 add_entry (DBusHashTable *table,
834  unsigned int idx,
835  void *key,
836  DBusHashEntry ***bucket,
837  DBusPreallocatedHash *preallocated)
838 {
839  DBusHashEntry *entry;
840 
841  if (preallocated == NULL)
842  {
843  entry = alloc_entry (table);
844  if (entry == NULL)
845  {
846  if (bucket)
847  *bucket = NULL;
848  return NULL;
849  }
850  }
851  else
852  {
853  entry = (DBusHashEntry*) preallocated;
854  }
855 
856  add_allocated_entry (table, entry, idx, key, bucket);
857 
858  return entry;
859 }
860 
861 /* This is g_str_hash from GLib which was
862  * extensively discussed/tested/profiled
863  */
864 static unsigned int
865 string_hash (const char *str)
866 {
867  const char *p = str;
868  unsigned int h = *p;
869 
870  if (h)
871  for (p += 1; *p != '\0'; p++)
872  h = (h << 5) - h + *p;
873 
874  return h;
875 }
876 
877 #ifdef DBUS_BUILD_TESTS
878 /* This hashes a memory block with two nul-terminated strings
879  * in it, used in dbus-object-registry.c at the moment.
880  */
881 static unsigned int
882 two_strings_hash (const char *str)
883 {
884  const char *p = str;
885  unsigned int h = *p;
886 
887  if (h)
888  for (p += 1; *p != '\0'; p++)
889  h = (h << 5) - h + *p;
890 
891  for (p += 1; *p != '\0'; p++)
892  h = (h << 5) - h + *p;
893 
894  return h;
895 }
896 #endif /* DBUS_BUILD_TESTS */
897 
899 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
900 
901 static DBusHashEntry*
902 find_generic_function (DBusHashTable *table,
903  void *key,
904  unsigned int idx,
905  KeyCompareFunc compare_func,
906  dbus_bool_t create_if_not_found,
907  DBusHashEntry ***bucket,
908  DBusPreallocatedHash *preallocated)
909 {
910  DBusHashEntry *entry;
911 
912  if (bucket)
913  *bucket = NULL;
914 
915  /* Search all of the entries in this bucket. */
916  entry = table->buckets[idx];
917  while (entry != NULL)
918  {
919  if ((compare_func == NULL && key == entry->key) ||
920  (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
921  {
922  if (bucket)
923  *bucket = &(table->buckets[idx]);
924 
925  if (preallocated)
926  _dbus_hash_table_free_preallocated_entry (table, preallocated);
927 
928  return entry;
929  }
930 
931  entry = entry->next;
932  }
933 
934  if (create_if_not_found)
935  entry = add_entry (table, idx, key, bucket, preallocated);
936  else if (preallocated)
937  _dbus_hash_table_free_preallocated_entry (table, preallocated);
938 
939  return entry;
940 }
941 
942 static DBusHashEntry*
943 find_string_function (DBusHashTable *table,
944  void *key,
945  dbus_bool_t create_if_not_found,
946  DBusHashEntry ***bucket,
947  DBusPreallocatedHash *preallocated)
948 {
949  unsigned int idx;
950 
951  idx = string_hash (key) & table->mask;
952 
953  return find_generic_function (table, key, idx,
954  (KeyCompareFunc) strcmp, create_if_not_found, bucket,
955  preallocated);
956 }
957 
958 #ifdef DBUS_BUILD_TESTS
959 static int
960 two_strings_cmp (const char *a,
961  const char *b)
962 {
963  size_t len_a;
964  size_t len_b;
965  int res;
966 
967  res = strcmp (a, b);
968  if (res != 0)
969  return res;
970 
971  len_a = strlen (a);
972  len_b = strlen (b);
973 
974  return strcmp (a + len_a + 1, b + len_b + 1);
975 }
976 #endif
977 
978 #ifdef DBUS_BUILD_TESTS
979 static DBusHashEntry*
980 find_two_strings_function (DBusHashTable *table,
981  void *key,
982  dbus_bool_t create_if_not_found,
983  DBusHashEntry ***bucket,
984  DBusPreallocatedHash *preallocated)
985 {
986  unsigned int idx;
987 
988  idx = two_strings_hash (key) & table->mask;
989 
990  return find_generic_function (table, key, idx,
991  (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
992  preallocated);
993 }
994 #endif /* DBUS_BUILD_TESTS */
995 
996 static DBusHashEntry*
997 find_direct_function (DBusHashTable *table,
998  void *key,
999  dbus_bool_t create_if_not_found,
1000  DBusHashEntry ***bucket,
1001  DBusPreallocatedHash *preallocated)
1002 {
1003  unsigned int idx;
1004 
1005  idx = RANDOM_INDEX (table, key) & table->mask;
1006 
1007 
1008  return find_generic_function (table, key, idx,
1009  NULL, create_if_not_found, bucket,
1010  preallocated);
1011 }
1012 
1013 static void
1014 rebuild_table (DBusHashTable *table)
1015 {
1016  int old_size;
1017  int new_buckets;
1018  DBusHashEntry **old_buckets;
1019  DBusHashEntry **old_chain;
1020  DBusHashEntry *entry;
1021  dbus_bool_t growing;
1022 
1023  /*
1024  * Allocate and initialize the new bucket array, and set up
1025  * hashing constants for new array size.
1026  */
1027 
1028  growing = table->n_entries >= table->hi_rebuild_size;
1029 
1030  old_size = table->n_buckets;
1031  old_buckets = table->buckets;
1032 
1033  if (growing)
1034  {
1035  /* overflow paranoia */
1036  if (table->n_buckets < _DBUS_INT_MAX / 4 &&
1037  table->down_shift >= 0)
1038  new_buckets = table->n_buckets * 4;
1039  else
1040  return; /* can't grow anymore */
1041  }
1042  else
1043  {
1044  new_buckets = table->n_buckets / 4;
1045  if (new_buckets < DBUS_SMALL_HASH_TABLE)
1046  return; /* don't bother shrinking this far */
1047  }
1048 
1049  table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
1050  if (table->buckets == NULL)
1051  {
1052  /* out of memory, yay - just don't reallocate, the table will
1053  * still work, albeit more slowly.
1054  */
1055  table->buckets = old_buckets;
1056  return;
1057  }
1058 
1059  table->n_buckets = new_buckets;
1060 
1061  if (growing)
1062  {
1063  table->lo_rebuild_size = table->hi_rebuild_size;
1064  table->hi_rebuild_size *= 4;
1065 
1066  table->down_shift -= 2; /* keep 2 more high bits */
1067  table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
1068  }
1069  else
1070  {
1071  table->hi_rebuild_size = table->lo_rebuild_size;
1072  table->lo_rebuild_size /= 4;
1073 
1074  table->down_shift += 2; /* keep 2 fewer high bits */
1075  table->mask = table->mask >> 2; /* keep 2 fewer high bits */
1076  }
1077 
1078 #if 0
1079  printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
1080  growing ? "GROW" : "SHRINK",
1081  table->lo_rebuild_size,
1082  table->hi_rebuild_size,
1083  table->down_shift,
1084  table->mask);
1085 #endif
1086 
1087  _dbus_assert (table->lo_rebuild_size >= 0);
1088  _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
1089  _dbus_assert (table->mask != 0);
1090  /* the mask is essentially the max index */
1091  _dbus_assert (table->mask < table->n_buckets);
1092 
1093  /*
1094  * Rehash all of the existing entries into the new bucket array.
1095  */
1096 
1097  for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1098  {
1099  for (entry = *old_chain; entry != NULL; entry = *old_chain)
1100  {
1101  unsigned int idx;
1102  DBusHashEntry **bucket;
1103 
1104  *old_chain = entry->next;
1105  switch (table->key_type)
1106  {
1107  case DBUS_HASH_STRING:
1108  idx = string_hash (entry->key) & table->mask;
1109  break;
1110  case DBUS_HASH_TWO_STRINGS:
1111 #ifdef DBUS_BUILD_TESTS
1112  idx = two_strings_hash (entry->key) & table->mask;
1113 #else
1114  idx = 0;
1115  _dbus_assert_not_reached ("two-strings is not enabled");
1116 #endif
1117  break;
1118  case DBUS_HASH_INT:
1119  case DBUS_HASH_UINTPTR:
1120  case DBUS_HASH_POINTER:
1121  idx = RANDOM_INDEX (table, entry->key);
1122  break;
1123  default:
1124  idx = 0;
1125  _dbus_assert_not_reached ("Unknown hash table type");
1126  break;
1127  }
1128 
1129  bucket = &(table->buckets[idx]);
1130  entry->next = *bucket;
1131  *bucket = entry;
1132  }
1133  }
1134 
1135  /* Free the old bucket array, if it was dynamically allocated. */
1136 
1137  if (old_buckets != table->static_buckets)
1138  dbus_free (old_buckets);
1139 }
1140 
1150 void*
1152  const char *key)
1153 {
1154  DBusHashEntry *entry;
1155 
1157 
1158  entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1159 
1160  if (entry)
1161  return entry->value;
1162  else
1163  return NULL;
1164 }
1165 
1166 #ifdef DBUS_BUILD_TESTS
1167 
1176 void*
1177 _dbus_hash_table_lookup_two_strings (DBusHashTable *table,
1178  const char *key)
1179 {
1180  DBusHashEntry *entry;
1181 
1183 
1184  entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1185 
1186  if (entry)
1187  return entry->value;
1188  else
1189  return NULL;
1190 }
1191 #endif /* DBUS_BUILD_TESTS */
1192 
1202 void*
1204  int key)
1205 {
1206  DBusHashEntry *entry;
1207 
1208  _dbus_assert (table->key_type == DBUS_HASH_INT);
1209 
1210  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1211 
1212  if (entry)
1213  return entry->value;
1214  else
1215  return NULL;
1216 }
1217 
1218 #ifdef DBUS_BUILD_TESTS
1219 /* disabled since it's only used for testing */
1229 void*
1230 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
1231  void *key)
1232 {
1233  DBusHashEntry *entry;
1234 
1236 
1237  entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
1238 
1239  if (entry)
1240  return entry->value;
1241  else
1242  return NULL;
1243 }
1244 #endif /* DBUS_BUILD_TESTS */
1245 
1255 void*
1257  uintptr_t key)
1258 {
1259  DBusHashEntry *entry;
1260 
1262 
1263  entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1264 
1265  if (entry)
1266  return entry->value;
1267  else
1268  return NULL;
1269 }
1270 
1281  const char *key)
1282 {
1283  DBusHashEntry *entry;
1284  DBusHashEntry **bucket;
1285 
1287 
1288  entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1289 
1290  if (entry)
1291  {
1292  remove_entry (table, bucket, entry);
1293  return TRUE;
1294  }
1295  else
1296  return FALSE;
1297 }
1298 
1299 #ifdef DBUS_BUILD_TESTS
1300 
1309 _dbus_hash_table_remove_two_strings (DBusHashTable *table,
1310  const char *key)
1311 {
1312  DBusHashEntry *entry;
1313  DBusHashEntry **bucket;
1314 
1316 
1317  entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1318 
1319  if (entry)
1320  {
1321  remove_entry (table, bucket, entry);
1322  return TRUE;
1323  }
1324  else
1325  return FALSE;
1326 }
1327 #endif /* DBUS_BUILD_TESTS */
1328 
1339  int key)
1340 {
1341  DBusHashEntry *entry;
1342  DBusHashEntry **bucket;
1343 
1344  _dbus_assert (table->key_type == DBUS_HASH_INT);
1345 
1346  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1347 
1348  if (entry)
1349  {
1350  remove_entry (table, bucket, entry);
1351  return TRUE;
1352  }
1353  else
1354  return FALSE;
1355 }
1356 
1357 #ifdef DBUS_BUILD_TESTS
1358 /* disabled since it's only used for testing */
1368 _dbus_hash_table_remove_pointer (DBusHashTable *table,
1369  void *key)
1370 {
1371  DBusHashEntry *entry;
1372  DBusHashEntry **bucket;
1373 
1375 
1376  entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
1377 
1378  if (entry)
1379  {
1380  remove_entry (table, bucket, entry);
1381  return TRUE;
1382  }
1383  else
1384  return FALSE;
1385 }
1386 #endif /* DBUS_BUILD_TESTS */
1387 
1398  uintptr_t key)
1399 {
1400  DBusHashEntry *entry;
1401  DBusHashEntry **bucket;
1402 
1404 
1405  entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1406 
1407  if (entry)
1408  {
1409  remove_entry (table, bucket, entry);
1410  return TRUE;
1411  }
1412  else
1413  return FALSE;
1414 }
1415 
1433  char *key,
1434  void *value)
1435 {
1436  DBusPreallocatedHash *preallocated;
1437 
1439 
1440  preallocated = _dbus_hash_table_preallocate_entry (table);
1441  if (preallocated == NULL)
1442  return FALSE;
1443 
1444  _dbus_hash_table_insert_string_preallocated (table, preallocated,
1445  key, value);
1446 
1447  return TRUE;
1448 }
1449 
1450 #ifdef DBUS_BUILD_TESTS
1451 
1467 _dbus_hash_table_insert_two_strings (DBusHashTable *table,
1468  char *key,
1469  void *value)
1470 {
1471  DBusHashEntry *entry;
1472 
1474 
1475  entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
1476 
1477  if (entry == NULL)
1478  return FALSE; /* no memory */
1479 
1480  if (table->free_key_function && entry->key != key)
1481  (* table->free_key_function) (entry->key);
1482 
1483  if (table->free_value_function && entry->value != value)
1484  (* table->free_value_function) (entry->value);
1485 
1486  entry->key = key;
1487  entry->value = value;
1488 
1489  return TRUE;
1490 }
1491 #endif /* DBUS_BUILD_TESTS */
1492 
1510  int key,
1511  void *value)
1512 {
1513  DBusHashEntry *entry;
1514 
1515  _dbus_assert (table->key_type == DBUS_HASH_INT);
1516 
1517  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1518 
1519  if (entry == NULL)
1520  return FALSE; /* no memory */
1521 
1522  if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1523  (* table->free_key_function) (entry->key);
1524 
1525  if (table->free_value_function && entry->value != value)
1526  (* table->free_value_function) (entry->value);
1527 
1528  entry->key = _DBUS_INT_TO_POINTER (key);
1529  entry->value = value;
1530 
1531  return TRUE;
1532 }
1533 
1534 #ifdef DBUS_BUILD_TESTS
1535 /* disabled since it's only used for testing */
1552 _dbus_hash_table_insert_pointer (DBusHashTable *table,
1553  void *key,
1554  void *value)
1555 {
1556  DBusHashEntry *entry;
1557 
1559 
1560  entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
1561 
1562  if (entry == NULL)
1563  return FALSE; /* no memory */
1564 
1565  if (table->free_key_function && entry->key != key)
1566  (* table->free_key_function) (entry->key);
1567 
1568  if (table->free_value_function && entry->value != value)
1569  (* table->free_value_function) (entry->value);
1570 
1571  entry->key = key;
1572  entry->value = value;
1573 
1574  return TRUE;
1575 }
1576 #endif /* DBUS_BUILD_TESTS */
1577 
1595  uintptr_t key,
1596  void *value)
1597 {
1598  DBusHashEntry *entry;
1599 
1601 
1602  entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1603 
1604  if (entry == NULL)
1605  return FALSE; /* no memory */
1606 
1607  if (table->free_key_function && entry->key != (void*) key)
1608  (* table->free_key_function) (entry->key);
1609 
1610  if (table->free_value_function && entry->value != value)
1611  (* table->free_value_function) (entry->value);
1612 
1613  entry->key = (void*) key;
1614  entry->value = value;
1615 
1616  return TRUE;
1617 }
1618 
1628 {
1629  DBusHashEntry *entry;
1630 
1631  entry = alloc_entry (table);
1632 
1633  return (DBusPreallocatedHash*) entry;
1634 }
1635 
1643 void
1645  DBusPreallocatedHash *preallocated)
1646 {
1647  DBusHashEntry *entry;
1648 
1649  _dbus_assert (preallocated != NULL);
1650 
1651  entry = (DBusHashEntry*) preallocated;
1652 
1653  /* Don't use free_entry(), since this entry has no key/data */
1654  _dbus_mem_pool_dealloc (table->entry_pool, entry);
1655 }
1656 
1670 void
1672  DBusPreallocatedHash *preallocated,
1673  char *key,
1674  void *value)
1675 {
1676  DBusHashEntry *entry;
1677 
1679  _dbus_assert (preallocated != NULL);
1680 
1681  entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1682 
1683  _dbus_assert (entry != NULL);
1684 
1685  if (table->free_key_function && entry->key != key)
1686  (* table->free_key_function) (entry->key);
1687 
1688  if (table->free_value_function && entry->value != value)
1689  (* table->free_value_function) (entry->value);
1690 
1691  entry->key = key;
1692  entry->value = value;
1693 }
1694 
1701 int
1703 {
1704  return table->n_entries;
1705 }
1706 
1709 #ifdef DBUS_BUILD_TESTS
1710 #include "dbus-test.h"
1711 #include <stdio.h>
1712 
1713 /* If you're wondering why the hash table test takes
1714  * forever to run, it's because we call this function
1715  * in inner loops thus making things quadratic.
1716  */
1717 static int
1718 count_entries (DBusHashTable *table)
1719 {
1720  DBusHashIter iter;
1721  int count;
1722 
1723  count = 0;
1724  _dbus_hash_iter_init (table, &iter);
1725  while (_dbus_hash_iter_next (&iter))
1726  ++count;
1727 
1728  _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1729 
1730  return count;
1731 }
1732 
1733 /* Copy the foo\0bar\0 double string thing */
1734 static char*
1735 _dbus_strdup2 (const char *str)
1736 {
1737  size_t len;
1738  char *copy;
1739 
1740  if (str == NULL)
1741  return NULL;
1742 
1743  len = strlen (str);
1744  len += strlen ((str + len + 1));
1745 
1746  copy = dbus_malloc (len + 2);
1747  if (copy == NULL)
1748  return NULL;
1749 
1750  memcpy (copy, str, len + 2);
1751 
1752  return copy;
1753 }
1754 
1761 _dbus_hash_test (void)
1762 {
1763  int i;
1764  DBusHashTable *table1;
1765  DBusHashTable *table2;
1766  DBusHashTable *table3;
1767  DBusHashTable *table4;
1768  DBusHashIter iter;
1769 #define N_HASH_KEYS 5000
1770  char **keys;
1771  dbus_bool_t ret = FALSE;
1772 
1773  keys = dbus_new (char *, N_HASH_KEYS);
1774  if (keys == NULL)
1775  _dbus_assert_not_reached ("no memory");
1776 
1777  for (i = 0; i < N_HASH_KEYS; i++)
1778  {
1779  keys[i] = dbus_malloc (128);
1780 
1781  if (keys[i] == NULL)
1782  _dbus_assert_not_reached ("no memory");
1783  }
1784 
1785  printf ("Computing test hash keys...\n");
1786  i = 0;
1787  while (i < N_HASH_KEYS)
1788  {
1789  int len;
1790 
1791  /* all the hash keys are TWO_STRINGS, but
1792  * then we can also use those as regular strings.
1793  */
1794 
1795  len = sprintf (keys[i], "Hash key %d", i);
1796  sprintf (keys[i] + len + 1, "Two string %d", i);
1797  _dbus_assert (*(keys[i] + len) == '\0');
1798  _dbus_assert (*(keys[i] + len + 1) != '\0');
1799  ++i;
1800  }
1801  printf ("... done.\n");
1802 
1804  dbus_free, dbus_free);
1805  if (table1 == NULL)
1806  goto out;
1807 
1809  NULL, dbus_free);
1810  if (table2 == NULL)
1811  goto out;
1812 
1814  NULL, dbus_free);
1815  if (table3 == NULL)
1816  goto out;
1817 
1819  dbus_free, dbus_free);
1820  if (table4 == NULL)
1821  goto out;
1822 
1823 
1824  /* Insert and remove a bunch of stuff, counting the table in between
1825  * to be sure it's not broken and that iteration works
1826  */
1827  i = 0;
1828  while (i < 3000)
1829  {
1830  void *value;
1831  char *key;
1832 
1833  key = _dbus_strdup (keys[i]);
1834  if (key == NULL)
1835  goto out;
1836  value = _dbus_strdup ("Value!");
1837  if (value == NULL)
1838  goto out;
1839 
1840  if (!_dbus_hash_table_insert_string (table1,
1841  key, value))
1842  goto out;
1843 
1844  value = _dbus_strdup (keys[i]);
1845  if (value == NULL)
1846  goto out;
1847 
1848  if (!_dbus_hash_table_insert_int (table2,
1849  i, value))
1850  goto out;
1851 
1852  value = _dbus_strdup (keys[i]);
1853  if (value == NULL)
1854  goto out;
1855 
1856  if (!_dbus_hash_table_insert_uintptr (table3,
1857  i, value))
1858  goto out;
1859 
1860  key = _dbus_strdup2 (keys[i]);
1861  if (key == NULL)
1862  goto out;
1863  value = _dbus_strdup ("Value!");
1864  if (value == NULL)
1865  goto out;
1866 
1867  if (!_dbus_hash_table_insert_two_strings (table4,
1868  key, value))
1869  goto out;
1870 
1871  _dbus_assert (count_entries (table1) == i + 1);
1872  _dbus_assert (count_entries (table2) == i + 1);
1873  _dbus_assert (count_entries (table3) == i + 1);
1874  _dbus_assert (count_entries (table4) == i + 1);
1875 
1876  value = _dbus_hash_table_lookup_string (table1, keys[i]);
1877  _dbus_assert (value != NULL);
1878  _dbus_assert (strcmp (value, "Value!") == 0);
1879 
1880  value = _dbus_hash_table_lookup_int (table2, i);
1881  _dbus_assert (value != NULL);
1882  _dbus_assert (strcmp (value, keys[i]) == 0);
1883 
1884  value = _dbus_hash_table_lookup_uintptr (table3, i);
1885  _dbus_assert (value != NULL);
1886  _dbus_assert (strcmp (value, keys[i]) == 0);
1887 
1888  value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
1889  _dbus_assert (value != NULL);
1890  _dbus_assert (strcmp (value, "Value!") == 0);
1891 
1892  ++i;
1893  }
1894 
1895  --i;
1896  while (i >= 0)
1897  {
1899  keys[i]);
1900 
1901  _dbus_hash_table_remove_int (table2, i);
1902 
1903  _dbus_hash_table_remove_uintptr (table3, i);
1904 
1905  _dbus_hash_table_remove_two_strings (table4,
1906  keys[i]);
1907 
1908  _dbus_assert (count_entries (table1) == i);
1909  _dbus_assert (count_entries (table2) == i);
1910  _dbus_assert (count_entries (table3) == i);
1911  _dbus_assert (count_entries (table4) == i);
1912 
1913  --i;
1914  }
1915 
1916  _dbus_hash_table_ref (table1);
1917  _dbus_hash_table_ref (table2);
1918  _dbus_hash_table_ref (table3);
1919  _dbus_hash_table_ref (table4);
1920  _dbus_hash_table_unref (table1);
1921  _dbus_hash_table_unref (table2);
1922  _dbus_hash_table_unref (table3);
1923  _dbus_hash_table_unref (table4);
1924  _dbus_hash_table_unref (table1);
1925  _dbus_hash_table_unref (table2);
1926  _dbus_hash_table_unref (table3);
1927  _dbus_hash_table_unref (table4);
1928  table3 = NULL;
1929 
1930  /* Insert a bunch of stuff then check
1931  * that iteration works correctly (finds the right
1932  * values, iter_set_value works, etc.)
1933  */
1935  dbus_free, dbus_free);
1936  if (table1 == NULL)
1937  goto out;
1938 
1940  NULL, dbus_free);
1941  if (table2 == NULL)
1942  goto out;
1943 
1944  i = 0;
1945  while (i < 5000)
1946  {
1947  char *key;
1948  void *value;
1949 
1950  key = _dbus_strdup (keys[i]);
1951  if (key == NULL)
1952  goto out;
1953  value = _dbus_strdup ("Value!");
1954  if (value == NULL)
1955  goto out;
1956 
1957  if (!_dbus_hash_table_insert_string (table1,
1958  key, value))
1959  goto out;
1960 
1961  value = _dbus_strdup (keys[i]);
1962  if (value == NULL)
1963  goto out;
1964 
1965  if (!_dbus_hash_table_insert_int (table2,
1966  i, value))
1967  goto out;
1968 
1969  _dbus_assert (count_entries (table1) == i + 1);
1970  _dbus_assert (count_entries (table2) == i + 1);
1971 
1972  ++i;
1973  }
1974 
1975  _dbus_hash_iter_init (table1, &iter);
1976  while (_dbus_hash_iter_next (&iter))
1977  {
1978  const char *key;
1979  void *value;
1980 
1981  key = _dbus_hash_iter_get_string_key (&iter);
1982  value = _dbus_hash_iter_get_value (&iter);
1983 
1984  _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1985 
1986  value = _dbus_strdup ("Different value!");
1987  if (value == NULL)
1988  goto out;
1989 
1990  _dbus_hash_iter_set_value (&iter, value);
1991 
1992  _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1993  }
1994 
1995  _dbus_hash_iter_init (table1, &iter);
1996  while (_dbus_hash_iter_next (&iter))
1997  {
1999  _dbus_assert (count_entries (table1) == i - 1);
2000  --i;
2001  }
2002 
2003  _dbus_hash_iter_init (table2, &iter);
2004  while (_dbus_hash_iter_next (&iter))
2005  {
2006  int key;
2007  void *value;
2008 
2009  key = _dbus_hash_iter_get_int_key (&iter);
2010  value = _dbus_hash_iter_get_value (&iter);
2011 
2012  _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
2013 
2014  value = _dbus_strdup ("Different value!");
2015  if (value == NULL)
2016  goto out;
2017 
2018  _dbus_hash_iter_set_value (&iter, value);
2019 
2020  _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
2021  }
2022 
2023  i = count_entries (table2);
2024  _dbus_hash_iter_init (table2, &iter);
2025  while (_dbus_hash_iter_next (&iter))
2026  {
2028  _dbus_assert (count_entries (table2) + 1 == i);
2029  --i;
2030  }
2031 
2032  /* add/remove interleaved, to check that we grow/shrink the table
2033  * appropriately
2034  */
2035  i = 0;
2036  while (i < 1000)
2037  {
2038  char *key;
2039  void *value;
2040 
2041  key = _dbus_strdup (keys[i]);
2042  if (key == NULL)
2043  goto out;
2044 
2045  value = _dbus_strdup ("Value!");
2046  if (value == NULL)
2047  goto out;
2048 
2049  if (!_dbus_hash_table_insert_string (table1,
2050  key, value))
2051  goto out;
2052 
2053  ++i;
2054  }
2055 
2056  --i;
2057  while (i >= 0)
2058  {
2059  char *key;
2060  void *value;
2061 
2062  key = _dbus_strdup (keys[i]);
2063  if (key == NULL)
2064  goto out;
2065  value = _dbus_strdup ("Value!");
2066  if (value == NULL)
2067  goto out;
2068 
2069  if (!_dbus_hash_table_remove_string (table1, keys[i]))
2070  goto out;
2071 
2072  if (!_dbus_hash_table_insert_string (table1,
2073  key, value))
2074  goto out;
2075 
2076  if (!_dbus_hash_table_remove_string (table1, keys[i]))
2077  goto out;
2078 
2080 
2081  --i;
2082  }
2083 
2084  /* nuke these tables */
2085  _dbus_hash_table_unref (table1);
2086  _dbus_hash_table_unref (table2);
2087 
2088 
2089  /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
2090  * be sure that interface works.
2091  */
2093  dbus_free, dbus_free);
2094  if (table1 == NULL)
2095  goto out;
2096 
2098  NULL, dbus_free);
2099  if (table2 == NULL)
2100  goto out;
2101 
2102  i = 0;
2103  while (i < 3000)
2104  {
2105  void *value;
2106  char *key;
2107 
2108  key = _dbus_strdup (keys[i]);
2109  if (key == NULL)
2110  goto out;
2111  value = _dbus_strdup ("Value!");
2112  if (value == NULL)
2113  goto out;
2114 
2115  if (!_dbus_hash_iter_lookup (table1,
2116  key, TRUE, &iter))
2117  goto out;
2118  _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
2119  _dbus_hash_iter_set_value (&iter, value);
2120 
2121  value = _dbus_strdup (keys[i]);
2122  if (value == NULL)
2123  goto out;
2124 
2125  if (!_dbus_hash_iter_lookup (table2,
2126  _DBUS_INT_TO_POINTER (i), TRUE, &iter))
2127  goto out;
2128  _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
2129  _dbus_hash_iter_set_value (&iter, value);
2130 
2131  _dbus_assert (count_entries (table1) == i + 1);
2132  _dbus_assert (count_entries (table2) == i + 1);
2133 
2134  if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
2135  goto out;
2136 
2137  value = _dbus_hash_iter_get_value (&iter);
2138  _dbus_assert (value != NULL);
2139  _dbus_assert (strcmp (value, "Value!") == 0);
2140 
2141  /* Iterate just to be sure it works, though
2142  * it's a stupid thing to do
2143  */
2144  while (_dbus_hash_iter_next (&iter))
2145  ;
2146 
2147  if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
2148  goto out;
2149 
2150  value = _dbus_hash_iter_get_value (&iter);
2151  _dbus_assert (value != NULL);
2152  _dbus_assert (strcmp (value, keys[i]) == 0);
2153 
2154  /* Iterate just to be sure it works, though
2155  * it's a stupid thing to do
2156  */
2157  while (_dbus_hash_iter_next (&iter))
2158  ;
2159 
2160  ++i;
2161  }
2162 
2163  --i;
2164  while (i >= 0)
2165  {
2166  if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
2167  _dbus_assert_not_reached ("hash entry should have existed");
2169 
2170  if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
2171  _dbus_assert_not_reached ("hash entry should have existed");
2173 
2174  _dbus_assert (count_entries (table1) == i);
2175  _dbus_assert (count_entries (table2) == i);
2176 
2177  --i;
2178  }
2179 
2180  _dbus_hash_table_unref (table1);
2181  _dbus_hash_table_unref (table2);
2182 
2183  ret = TRUE;
2184 
2185  out:
2186  for (i = 0; i < N_HASH_KEYS; i++)
2187  dbus_free (keys[i]);
2188 
2189  dbus_free (keys);
2190 
2191  return ret;
2192 }
2193 
2194 #endif /* DBUS_BUILD_TESTS */