D-Bus  1.13.7
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 #include <dbus/dbus-test-tap.h>
82 
105 #define REBUILD_MULTIPLIER 3
106 
123 #define RANDOM_INDEX(table, i) \
124  (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
125 
131 #define DBUS_SMALL_HASH_TABLE 4
132 
137 
145 {
150  void *key;
151  void *value;
152 };
153 
157 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
158  void *key,
159  dbus_bool_t create_if_not_found,
160  DBusHashEntry ***bucket,
161  DBusPreallocatedHash *preallocated);
162 
170  int refcount;
180  int n_buckets;
183  int n_entries;
196  int mask;
208 };
209 
213 typedef struct
214 {
225 
226 _DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
227 
228 static DBusHashEntry* find_direct_function (DBusHashTable *table,
229  void *key,
230  dbus_bool_t create_if_not_found,
231  DBusHashEntry ***bucket,
232  DBusPreallocatedHash *preallocated);
233 static DBusHashEntry* find_string_function (DBusHashTable *table,
234  void *key,
235  dbus_bool_t create_if_not_found,
236  DBusHashEntry ***bucket,
237  DBusPreallocatedHash *preallocated);
238 static unsigned int string_hash (const char *str);
239 static void rebuild_table (DBusHashTable *table);
240 static DBusHashEntry* alloc_entry (DBusHashTable *table);
241 static void remove_entry (DBusHashTable *table,
242  DBusHashEntry **bucket,
243  DBusHashEntry *entry);
244 static void free_entry (DBusHashTable *table,
245  DBusHashEntry *entry);
246 static void free_entry_data (DBusHashTable *table,
247  DBusHashEntry *entry);
248 
249 
287  DBusFreeFunction key_free_function,
288  DBusFreeFunction value_free_function)
289 {
290  DBusHashTable *table;
291  DBusMemPool *entry_pool;
292 
293  table = dbus_new0 (DBusHashTable, 1);
294  if (table == NULL)
295  return NULL;
296 
297  entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
298  if (entry_pool == NULL)
299  {
300  dbus_free (table);
301  return NULL;
302  }
303 
304  table->refcount = 1;
305  table->entry_pool = entry_pool;
306 
308 
309  table->buckets = table->static_buckets;
311  table->n_entries = 0;
313  table->lo_rebuild_size = 0;
314  table->down_shift = 28;
315  table->mask = 3;
316  table->key_type = type;
317 
318  _dbus_assert (table->mask < table->n_buckets);
319 
320  switch (table->key_type)
321  {
322  case DBUS_HASH_INT:
323  case DBUS_HASH_UINTPTR:
324  table->find_function = find_direct_function;
325  break;
326  case DBUS_HASH_STRING:
327  table->find_function = find_string_function;
328  break;
329  default:
330  _dbus_assert_not_reached ("Unknown hash table type");
331  break;
332  }
333 
334  table->free_key_function = key_free_function;
335  table->free_value_function = value_free_function;
336 
337  return table;
338 }
339 
340 
349 {
350  table->refcount += 1;
351 
352  return table;
353 }
354 
361 void
363 {
364  table->refcount -= 1;
365 
366  if (table->refcount == 0)
367  {
368 #if 0
369  DBusHashEntry *entry;
371  int i;
372 
373  /* Free the entries in the table. */
374  for (i = 0; i < table->n_buckets; i++)
375  {
376  entry = table->buckets[i];
377  while (entry != NULL)
378  {
379  next = entry->next;
380 
381  free_entry (table, entry);
382 
383  entry = next;
384  }
385  }
386 #else
387  DBusHashEntry *entry;
388  int i;
389 
390  /* Free the entries in the table. */
391  for (i = 0; i < table->n_buckets; i++)
392  {
393  entry = table->buckets[i];
394  while (entry != NULL)
395  {
396  free_entry_data (table, entry);
397 
398  entry = entry->next;
399  }
400  }
401  /* We can do this very quickly with memory pools ;-) */
403 #endif
404 
405  /* Free the bucket array, if it was dynamically allocated. */
406  if (table->buckets != table->static_buckets)
407  dbus_free (table->buckets);
408 
409  dbus_free (table);
410  }
411 }
412 
418 void
420 {
421  DBusHashIter iter;
422  _dbus_hash_iter_init (table, &iter);
423  while (_dbus_hash_iter_next (&iter))
424  {
426  }
427 }
428 
429 static DBusHashEntry*
430 alloc_entry (DBusHashTable *table)
431 {
432  DBusHashEntry *entry;
433 
434  entry = _dbus_mem_pool_alloc (table->entry_pool);
435 
436  return entry;
437 }
438 
439 static void
440 free_entry_data (DBusHashTable *table,
441  DBusHashEntry *entry)
442 {
443  if (table->free_key_function)
444  (* table->free_key_function) (entry->key);
445  if (table->free_value_function)
446  (* table->free_value_function) (entry->value);
447 }
448 
449 static void
450 free_entry (DBusHashTable *table,
451  DBusHashEntry *entry)
452 {
453  free_entry_data (table, entry);
454  _dbus_mem_pool_dealloc (table->entry_pool, entry);
455 }
456 
457 static void
458 remove_entry (DBusHashTable *table,
459  DBusHashEntry **bucket,
460  DBusHashEntry *entry)
461 {
462  _dbus_assert (table != NULL);
463  _dbus_assert (bucket != NULL);
464  _dbus_assert (*bucket != NULL);
465  _dbus_assert (entry != NULL);
466 
467  if (*bucket == entry)
468  *bucket = entry->next;
469  else
470  {
471  DBusHashEntry *prev;
472  prev = *bucket;
473 
474  while (prev->next != entry)
475  prev = prev->next;
476 
477  _dbus_assert (prev != NULL);
478 
479  prev->next = entry->next;
480  }
481 
482  table->n_entries -= 1;
483  free_entry (table, entry);
484 }
485 
517 void
519  DBusHashIter *iter)
520 {
521  DBusRealHashIter *real;
522 
523  _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
524 
525  real = (DBusRealHashIter*) iter;
526 
527  real->table = table;
528  real->bucket = NULL;
529  real->entry = NULL;
530  real->next_entry = NULL;
531  real->next_bucket = 0;
532  real->n_entries_on_init = table->n_entries;
533 }
534 
545 {
546  DBusRealHashIter *real;
547 
548  _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
549 
550  real = (DBusRealHashIter*) iter;
551 
552  /* if this assertion failed someone probably added hash entries
553  * during iteration, which is bad.
554  */
555  _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
556 
557  /* Remember that real->entry may have been deleted */
558 
559  while (real->next_entry == NULL)
560  {
561  if (real->next_bucket >= real->table->n_buckets)
562  {
563  /* invalidate iter and return false */
564  real->entry = NULL;
565  real->table = NULL;
566  real->bucket = NULL;
567  return FALSE;
568  }
569 
570  real->bucket = &(real->table->buckets[real->next_bucket]);
571  real->next_entry = *(real->bucket);
572  real->next_bucket += 1;
573  }
574 
575  _dbus_assert (real->next_entry != NULL);
576  _dbus_assert (real->bucket != NULL);
577 
578  real->entry = real->next_entry;
579  real->next_entry = real->entry->next;
580 
581  return TRUE;
582 }
583 
592 void
594 {
595  DBusRealHashIter *real;
596 
597  real = (DBusRealHashIter*) iter;
598 
599  _dbus_assert (real->table != NULL);
600  _dbus_assert (real->entry != NULL);
601  _dbus_assert (real->bucket != NULL);
602 
603  remove_entry (real->table, real->bucket, real->entry);
604 
605  real->entry = NULL; /* make it crash if you try to use this entry */
606 }
607 
613 void*
615 {
616  DBusRealHashIter *real;
617 
618  real = (DBusRealHashIter*) iter;
619 
620  _dbus_assert (real->table != NULL);
621  _dbus_assert (real->entry != NULL);
622 
623  return real->entry->value;
624 }
625 
636 void
638  void *value)
639 {
640  DBusRealHashIter *real;
641 
642  real = (DBusRealHashIter*) iter;
643 
644  _dbus_assert (real->table != NULL);
645  _dbus_assert (real->entry != NULL);
646 
647  if (real->table->free_value_function && value != real->entry->value)
648  (* real->table->free_value_function) (real->entry->value);
649 
650  real->entry->value = value;
651 }
652 
659 int
661 {
662  DBusRealHashIter *real;
663 
664  real = (DBusRealHashIter*) iter;
665 
666  _dbus_assert (real->table != NULL);
667  _dbus_assert (real->entry != NULL);
668 
669  return _DBUS_POINTER_TO_INT (real->entry->key);
670 }
671 
678 uintptr_t
680 {
681  DBusRealHashIter *real;
682 
683  real = (DBusRealHashIter*) iter;
684 
685  _dbus_assert (real->table != NULL);
686  _dbus_assert (real->entry != NULL);
687 
688  return (uintptr_t) real->entry->key;
689 }
690 
696 const char*
698 {
699  DBusRealHashIter *real;
700 
701  real = (DBusRealHashIter*) iter;
702 
703  _dbus_assert (real->table != NULL);
704  _dbus_assert (real->entry != NULL);
705 
706  return real->entry->key;
707 }
708 
743  void *key,
744  dbus_bool_t create_if_not_found,
745  DBusHashIter *iter)
746 {
747  DBusRealHashIter *real;
748  DBusHashEntry *entry;
749  DBusHashEntry **bucket;
750 
751  _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
752 
753  real = (DBusRealHashIter*) iter;
754 
755  entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
756 
757  if (entry == NULL)
758  return FALSE;
759 
760  if (create_if_not_found)
761  {
762  if (table->free_key_function && entry->key != key)
763  (* table->free_key_function) (entry->key);
764 
765  entry->key = key;
766  }
767 
768  real->table = table;
769  real->bucket = bucket;
770  real->entry = entry;
771  real->next_entry = entry->next;
772  real->next_bucket = (bucket - table->buckets) + 1;
773  real->n_entries_on_init = table->n_entries;
774 
775  _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
776 
777  return TRUE;
778 }
779 
780 static void
781 add_allocated_entry (DBusHashTable *table,
782  DBusHashEntry *entry,
783  unsigned int idx,
784  void *key,
785  DBusHashEntry ***bucket)
786 {
787  DBusHashEntry **b;
788 
789  entry->key = key;
790 
791  b = &(table->buckets[idx]);
792  entry->next = *b;
793  *b = entry;
794 
795  if (bucket)
796  *bucket = b;
797 
798  table->n_entries += 1;
799 
800  /* note we ONLY rebuild when ADDING - because you can iterate over a
801  * table and remove entries safely.
802  */
803  if (table->n_entries >= table->hi_rebuild_size ||
804  table->n_entries < table->lo_rebuild_size)
805  rebuild_table (table);
806 }
807 
808 static DBusHashEntry*
809 add_entry (DBusHashTable *table,
810  unsigned int idx,
811  void *key,
812  DBusHashEntry ***bucket,
813  DBusPreallocatedHash *preallocated)
814 {
815  DBusHashEntry *entry;
816 
817  if (preallocated == NULL)
818  {
819  entry = alloc_entry (table);
820  if (entry == NULL)
821  {
822  if (bucket)
823  *bucket = NULL;
824  return NULL;
825  }
826  }
827  else
828  {
829  entry = (DBusHashEntry*) preallocated;
830  }
831 
832  add_allocated_entry (table, entry, idx, key, bucket);
833 
834  return entry;
835 }
836 
837 /* This is g_str_hash from GLib which was
838  * extensively discussed/tested/profiled
839  */
840 static unsigned int
841 string_hash (const char *str)
842 {
843  const char *p = str;
844  unsigned int h = *p;
845 
846  if (h)
847  for (p += 1; *p != '\0'; p++)
848  h = (h << 5) - h + *p;
849 
850  return h;
851 }
852 
854 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
855 
856 static DBusHashEntry*
857 find_generic_function (DBusHashTable *table,
858  void *key,
859  unsigned int idx,
860  KeyCompareFunc compare_func,
861  dbus_bool_t create_if_not_found,
862  DBusHashEntry ***bucket,
863  DBusPreallocatedHash *preallocated)
864 {
865  DBusHashEntry *entry;
866 
867  if (bucket)
868  *bucket = NULL;
869 
870  /* Search all of the entries in this bucket. */
871  entry = table->buckets[idx];
872  while (entry != NULL)
873  {
874  if ((compare_func == NULL && key == entry->key) ||
875  (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
876  {
877  if (bucket)
878  *bucket = &(table->buckets[idx]);
879 
880  if (preallocated)
881  _dbus_hash_table_free_preallocated_entry (table, preallocated);
882 
883  return entry;
884  }
885 
886  entry = entry->next;
887  }
888 
889  if (create_if_not_found)
890  entry = add_entry (table, idx, key, bucket, preallocated);
891  else if (preallocated)
892  _dbus_hash_table_free_preallocated_entry (table, preallocated);
893 
894  return entry;
895 }
896 
897 static DBusHashEntry*
898 find_string_function (DBusHashTable *table,
899  void *key,
900  dbus_bool_t create_if_not_found,
901  DBusHashEntry ***bucket,
902  DBusPreallocatedHash *preallocated)
903 {
904  unsigned int idx;
905 
906  idx = string_hash (key) & table->mask;
907 
908  return find_generic_function (table, key, idx,
909  (KeyCompareFunc) strcmp, create_if_not_found, bucket,
910  preallocated);
911 }
912 
913 static DBusHashEntry*
914 find_direct_function (DBusHashTable *table,
915  void *key,
916  dbus_bool_t create_if_not_found,
917  DBusHashEntry ***bucket,
918  DBusPreallocatedHash *preallocated)
919 {
920  unsigned int idx;
921 
922  idx = RANDOM_INDEX (table, key) & table->mask;
923 
924 
925  return find_generic_function (table, key, idx,
926  NULL, create_if_not_found, bucket,
927  preallocated);
928 }
929 
930 static void
931 rebuild_table (DBusHashTable *table)
932 {
933  int old_size;
934  int new_buckets;
935  DBusHashEntry **old_buckets;
936  DBusHashEntry **old_chain;
937  DBusHashEntry *entry;
938  dbus_bool_t growing;
939 
940  /*
941  * Allocate and initialize the new bucket array, and set up
942  * hashing constants for new array size.
943  */
944 
945  growing = table->n_entries >= table->hi_rebuild_size;
946 
947  old_size = table->n_buckets;
948  old_buckets = table->buckets;
949 
950  if (growing)
951  {
952  /* overflow paranoia */
953  if (table->n_buckets < _DBUS_INT_MAX / 4 &&
954  table->down_shift >= 2)
955  new_buckets = table->n_buckets * 4;
956  else
957  return; /* can't grow anymore */
958  }
959  else
960  {
961  new_buckets = table->n_buckets / 4;
962  if (new_buckets < DBUS_SMALL_HASH_TABLE)
963  return; /* don't bother shrinking this far */
964  }
965 
966  table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
967  if (table->buckets == NULL)
968  {
969  /* out of memory, yay - just don't reallocate, the table will
970  * still work, albeit more slowly.
971  */
972  table->buckets = old_buckets;
973  return;
974  }
975 
976  table->n_buckets = new_buckets;
977 
978  if (growing)
979  {
980  table->lo_rebuild_size = table->hi_rebuild_size;
981  table->hi_rebuild_size *= 4;
982 
983  table->down_shift -= 2; /* keep 2 more high bits */
984  table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
985  }
986  else
987  {
988  table->hi_rebuild_size = table->lo_rebuild_size;
989  table->lo_rebuild_size /= 4;
990 
991  table->down_shift += 2; /* keep 2 fewer high bits */
992  table->mask = table->mask >> 2; /* keep 2 fewer high bits */
993  }
994 
995 #if 0
996  printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
997  growing ? "GROW" : "SHRINK",
998  table->lo_rebuild_size,
999  table->hi_rebuild_size,
1000  table->down_shift,
1001  table->mask);
1002 #endif
1003 
1004  _dbus_assert (table->lo_rebuild_size >= 0);
1005  _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
1006  _dbus_assert (table->down_shift >= 0);
1007  _dbus_assert (table->mask != 0);
1008  /* the mask is essentially the max index */
1009  _dbus_assert (table->mask < table->n_buckets);
1010 
1011  /*
1012  * Rehash all of the existing entries into the new bucket array.
1013  */
1014 
1015  for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1016  {
1017  for (entry = *old_chain; entry != NULL; entry = *old_chain)
1018  {
1019  unsigned int idx;
1020  DBusHashEntry **bucket;
1021 
1022  *old_chain = entry->next;
1023  switch (table->key_type)
1024  {
1025  case DBUS_HASH_STRING:
1026  idx = string_hash (entry->key) & table->mask;
1027  break;
1028  case DBUS_HASH_INT:
1029  case DBUS_HASH_UINTPTR:
1030  idx = RANDOM_INDEX (table, entry->key);
1031  break;
1032  default:
1033  idx = 0;
1034  _dbus_assert_not_reached ("Unknown hash table type");
1035  break;
1036  }
1037 
1038  bucket = &(table->buckets[idx]);
1039  entry->next = *bucket;
1040  *bucket = entry;
1041  }
1042  }
1043 
1044  /* Free the old bucket array, if it was dynamically allocated. */
1045 
1046  if (old_buckets != table->static_buckets)
1047  dbus_free (old_buckets);
1048 }
1049 
1059 void*
1061  const char *key)
1062 {
1063  DBusHashEntry *entry;
1064 
1066 
1067  entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1068 
1069  if (entry)
1070  return entry->value;
1071  else
1072  return NULL;
1073 }
1074 
1084 void*
1086  int key)
1087 {
1088  DBusHashEntry *entry;
1089 
1090  _dbus_assert (table->key_type == DBUS_HASH_INT);
1091 
1092  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1093 
1094  if (entry)
1095  return entry->value;
1096  else
1097  return NULL;
1098 }
1099 
1109 void*
1111  uintptr_t key)
1112 {
1113  DBusHashEntry *entry;
1114 
1116 
1117  entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1118 
1119  if (entry)
1120  return entry->value;
1121  else
1122  return NULL;
1123 }
1124 
1135  const char *key)
1136 {
1137  DBusHashEntry *entry;
1138  DBusHashEntry **bucket;
1139 
1141 
1142  entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1143 
1144  if (entry)
1145  {
1146  remove_entry (table, bucket, entry);
1147  return TRUE;
1148  }
1149  else
1150  return FALSE;
1151 }
1152 
1163  int key)
1164 {
1165  DBusHashEntry *entry;
1166  DBusHashEntry **bucket;
1167 
1168  _dbus_assert (table->key_type == DBUS_HASH_INT);
1169 
1170  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1171 
1172  if (entry)
1173  {
1174  remove_entry (table, bucket, entry);
1175  return TRUE;
1176  }
1177  else
1178  return FALSE;
1179 }
1180 
1191  uintptr_t key)
1192 {
1193  DBusHashEntry *entry;
1194  DBusHashEntry **bucket;
1195 
1197 
1198  entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1199 
1200  if (entry)
1201  {
1202  remove_entry (table, bucket, entry);
1203  return TRUE;
1204  }
1205  else
1206  return FALSE;
1207 }
1208 
1226  char *key,
1227  void *value)
1228 {
1229  DBusPreallocatedHash *preallocated;
1230 
1232 
1233  preallocated = _dbus_hash_table_preallocate_entry (table);
1234  if (preallocated == NULL)
1235  return FALSE;
1236 
1237  _dbus_hash_table_insert_string_preallocated (table, preallocated,
1238  key, value);
1239 
1240  return TRUE;
1241 }
1242 
1260  int key,
1261  void *value)
1262 {
1263  DBusHashEntry *entry;
1264 
1265  _dbus_assert (table->key_type == DBUS_HASH_INT);
1266 
1267  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1268 
1269  if (entry == NULL)
1270  return FALSE; /* no memory */
1271 
1272  if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1273  (* table->free_key_function) (entry->key);
1274 
1275  if (table->free_value_function && entry->value != value)
1276  (* table->free_value_function) (entry->value);
1277 
1278  entry->key = _DBUS_INT_TO_POINTER (key);
1279  entry->value = value;
1280 
1281  return TRUE;
1282 }
1283 
1301  uintptr_t key,
1302  void *value)
1303 {
1304  DBusHashEntry *entry;
1305 
1307 
1308  entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1309 
1310  if (entry == NULL)
1311  return FALSE; /* no memory */
1312 
1313  if (table->free_key_function && entry->key != (void*) key)
1314  (* table->free_key_function) (entry->key);
1315 
1316  if (table->free_value_function && entry->value != value)
1317  (* table->free_value_function) (entry->value);
1318 
1319  entry->key = (void*) key;
1320  entry->value = value;
1321 
1322  return TRUE;
1323 }
1324 
1334 {
1335  DBusHashEntry *entry;
1336 
1337  entry = alloc_entry (table);
1338 
1339  return (DBusPreallocatedHash*) entry;
1340 }
1341 
1349 void
1351  DBusPreallocatedHash *preallocated)
1352 {
1353  DBusHashEntry *entry;
1354 
1355  _dbus_assert (preallocated != NULL);
1356 
1357  entry = (DBusHashEntry*) preallocated;
1358 
1359  /* Don't use free_entry(), since this entry has no key/data */
1360  _dbus_mem_pool_dealloc (table->entry_pool, entry);
1361 }
1362 
1376 void
1378  DBusPreallocatedHash *preallocated,
1379  char *key,
1380  void *value)
1381 {
1382  DBusHashEntry *entry;
1383 
1385  _dbus_assert (preallocated != NULL);
1386 
1387  entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1388 
1389  _dbus_assert (entry != NULL);
1390 
1391  if (table->free_key_function && entry->key != key)
1392  (* table->free_key_function) (entry->key);
1393 
1394  if (table->free_value_function && entry->value != value)
1395  (* table->free_value_function) (entry->value);
1396 
1397  entry->key = key;
1398  entry->value = value;
1399 }
1400 
1407 int
1409 {
1410  return table->n_entries;
1411 }
1412 
1426 _dbus_hash_table_from_array (DBusHashTable *table, char **array, char delimiter)
1427 {
1428  DBusString key;
1429  DBusString value;
1430  int i;
1431  dbus_bool_t retval = FALSE;
1432 
1433  _dbus_assert (table != NULL);
1434  _dbus_assert (array != NULL);
1435 
1436  if (!_dbus_string_init (&key))
1437  {
1438  return FALSE;
1439  }
1440 
1441  if (!_dbus_string_init (&value))
1442  {
1443  _dbus_string_free (&key);
1444  return FALSE;
1445  }
1446 
1447  for (i = 0; array[i] != NULL; i++)
1448  {
1449  if (!_dbus_string_append (&key, array[i]))
1450  break;
1451 
1452  if (_dbus_string_split_on_byte (&key, delimiter, &value))
1453  {
1454  char *hash_key, *hash_value;
1455 
1456  if (!_dbus_string_steal_data (&key, &hash_key))
1457  break;
1458 
1459  if (!_dbus_string_steal_data (&value, &hash_value))
1460  break;
1461 
1462  if (!_dbus_hash_table_insert_string (table,
1463  hash_key, hash_value))
1464  break;
1465  }
1466  _dbus_string_set_length (&key, 0);
1467  _dbus_string_set_length (&value, 0);
1468  }
1469 
1470  if (array[i] != NULL)
1471  goto out;
1472 
1473  retval = TRUE;
1474 out:
1475 
1476  _dbus_string_free (&key);
1477  _dbus_string_free (&value);
1478 
1479  return retval;
1480 }
1481 
1490 char **
1492 {
1493  int i, length;
1494  DBusString entry;
1495  DBusHashIter iter;
1496  char **array;
1497 
1498  _dbus_assert (table != NULL);
1499 
1500  length = _dbus_hash_table_get_n_entries (table);
1501 
1502  array = dbus_new0 (char *, length + 1);
1503 
1504  if (array == NULL)
1505  return NULL;
1506 
1507  i = 0;
1508  _dbus_hash_iter_init (table, &iter);
1509 
1510  if (!_dbus_string_init (&entry))
1511  {
1512  dbus_free_string_array (array);
1513  return NULL;
1514  }
1515 
1516  while (_dbus_hash_iter_next (&iter))
1517  {
1518  const char *key, *value;
1519 
1520  key = (const char *) _dbus_hash_iter_get_string_key (&iter);
1521  value = (const char *) _dbus_hash_iter_get_value (&iter);
1522 
1523  if (!_dbus_string_append_printf (&entry, "%s%c%s", key, delimiter, value))
1524  break;
1525 
1526  if (!_dbus_string_steal_data (&entry, array + i))
1527  break;
1528  i++;
1529  }
1530 
1531  _dbus_string_free (&entry);
1532 
1533  if (i != length)
1534  {
1535  dbus_free_string_array (array);
1536  array = NULL;
1537  }
1538 
1539  return array;
1540 }
1541 
1544 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
1545 #include "dbus-test.h"
1546 #include <stdio.h>
1547 
1548 /* If you're wondering why the hash table test takes
1549  * forever to run, it's because we call this function
1550  * in inner loops thus making things quadratic.
1551  */
1552 static int
1553 count_entries (DBusHashTable *table)
1554 {
1555  DBusHashIter iter;
1556  int count;
1557 
1558  count = 0;
1559  _dbus_hash_iter_init (table, &iter);
1560  while (_dbus_hash_iter_next (&iter))
1561  ++count;
1562 
1563  _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1564 
1565  return count;
1566 }
1567 
1568 static inline void *
1569 steal (void *ptr)
1570 {
1571  /* @ptr is passed in as void* to avoid casting in the call */
1572  void **_ptr = (void **) ptr;
1573  void *val;
1574 
1575  val = *_ptr;
1576  *_ptr = NULL;
1577 
1578  return val;
1579 }
1580 
1587 _dbus_hash_test (void)
1588 {
1589  int i;
1590  DBusHashTable *table1;
1591  DBusHashTable *table2;
1592  DBusHashTable *table3;
1593  DBusHashIter iter;
1594 #define N_HASH_KEYS 5000
1595  char **keys;
1596  dbus_bool_t ret = FALSE;
1597  char *str_key = NULL;
1598  char *str_value = NULL;
1599 
1600  keys = dbus_new (char *, N_HASH_KEYS);
1601  if (keys == NULL)
1602  _dbus_test_fatal ("no memory");
1603 
1604  for (i = 0; i < N_HASH_KEYS; i++)
1605  {
1606  keys[i] = dbus_malloc (128);
1607 
1608  if (keys[i] == NULL)
1609  _dbus_test_fatal ("no memory");
1610  }
1611 
1612  _dbus_test_diag ("Computing test hash keys...");
1613  i = 0;
1614  while (i < N_HASH_KEYS)
1615  {
1616  int len;
1617 
1618  len = sprintf (keys[i], "Hash key %d", i);
1619  _dbus_assert (*(keys[i] + len) == '\0');
1620  ++i;
1621  }
1622  _dbus_test_diag ("... done.");
1623 
1625  dbus_free, dbus_free);
1626  if (table1 == NULL)
1627  goto out;
1628 
1630  NULL, dbus_free);
1631  if (table2 == NULL)
1632  goto out;
1633 
1635  NULL, dbus_free);
1636  if (table3 == NULL)
1637  goto out;
1638 
1639  /* Insert and remove a bunch of stuff, counting the table in between
1640  * to be sure it's not broken and that iteration works
1641  */
1642  i = 0;
1643  while (i < 3000)
1644  {
1645  const void *out_value;
1646 
1647  str_key = _dbus_strdup (keys[i]);
1648  if (str_key == NULL)
1649  goto out;
1650  str_value = _dbus_strdup ("Value!");
1651  if (str_value == NULL)
1652  goto out;
1653 
1654  if (!_dbus_hash_table_insert_string (table1,
1655  steal (&str_key),
1656  steal (&str_value)))
1657  goto out;
1658 
1659  str_value = _dbus_strdup (keys[i]);
1660  if (str_value == NULL)
1661  goto out;
1662 
1663  if (!_dbus_hash_table_insert_int (table2,
1664  i, steal (&str_value)))
1665  goto out;
1666 
1667  str_value = _dbus_strdup (keys[i]);
1668  if (str_value == NULL)
1669  goto out;
1670 
1671  if (!_dbus_hash_table_insert_uintptr (table3,
1672  i, steal (&str_value)))
1673  goto out;
1674 
1675  _dbus_assert (count_entries (table1) == i + 1);
1676  _dbus_assert (count_entries (table2) == i + 1);
1677  _dbus_assert (count_entries (table3) == i + 1);
1678 
1679  out_value = _dbus_hash_table_lookup_string (table1, keys[i]);
1680  _dbus_assert (out_value != NULL);
1681  _dbus_assert (strcmp (out_value, "Value!") == 0);
1682 
1683  out_value = _dbus_hash_table_lookup_int (table2, i);
1684  _dbus_assert (out_value != NULL);
1685  _dbus_assert (strcmp (out_value, keys[i]) == 0);
1686 
1687  out_value = _dbus_hash_table_lookup_uintptr (table3, i);
1688  _dbus_assert (out_value != NULL);
1689  _dbus_assert (strcmp (out_value, keys[i]) == 0);
1690 
1691  ++i;
1692  }
1693 
1694  --i;
1695  while (i >= 0)
1696  {
1698  keys[i]);
1699 
1700  _dbus_hash_table_remove_int (table2, i);
1701 
1702  _dbus_hash_table_remove_uintptr (table3, i);
1703 
1704  _dbus_assert (count_entries (table1) == i);
1705  _dbus_assert (count_entries (table2) == i);
1706  _dbus_assert (count_entries (table3) == i);
1707 
1708  --i;
1709  }
1710 
1711  _dbus_hash_table_ref (table1);
1712  _dbus_hash_table_ref (table2);
1713  _dbus_hash_table_ref (table3);
1714  _dbus_hash_table_unref (table1);
1715  _dbus_hash_table_unref (table2);
1716  _dbus_hash_table_unref (table3);
1717  _dbus_hash_table_unref (table1);
1718  _dbus_hash_table_unref (table2);
1719  _dbus_hash_table_unref (table3);
1720  table3 = NULL;
1721 
1722  /* Insert a bunch of stuff then check
1723  * that iteration works correctly (finds the right
1724  * values, iter_set_value works, etc.)
1725  */
1727  dbus_free, dbus_free);
1728  if (table1 == NULL)
1729  goto out;
1730 
1732  NULL, dbus_free);
1733  if (table2 == NULL)
1734  goto out;
1735 
1736  i = 0;
1737  while (i < 5000)
1738  {
1739  str_key = _dbus_strdup (keys[i]);
1740  if (str_key == NULL)
1741  goto out;
1742  str_value = _dbus_strdup ("Value!");
1743  if (str_value == NULL)
1744  goto out;
1745 
1746  if (!_dbus_hash_table_insert_string (table1,
1747  steal (&str_key),
1748  steal (&str_value)))
1749  goto out;
1750 
1751  str_value = _dbus_strdup (keys[i]);
1752  if (str_value == NULL)
1753  goto out;
1754 
1755  if (!_dbus_hash_table_insert_int (table2,
1756  i, steal (&str_value)))
1757  goto out;
1758 
1759  _dbus_assert (count_entries (table1) == i + 1);
1760  _dbus_assert (count_entries (table2) == i + 1);
1761 
1762  ++i;
1763  }
1764 
1765  _dbus_hash_iter_init (table1, &iter);
1766  while (_dbus_hash_iter_next (&iter))
1767  {
1768  const char *key;
1769  const void *value;
1770 
1771  key = _dbus_hash_iter_get_string_key (&iter);
1772  value = _dbus_hash_iter_get_value (&iter);
1773 
1774  _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1775 
1776  str_value = _dbus_strdup ("Different value!");
1777  if (str_value == NULL)
1778  goto out;
1779 
1780  value = str_value;
1781  _dbus_hash_iter_set_value (&iter, steal (&str_value));
1782  _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1783  }
1784 
1785  _dbus_hash_iter_init (table1, &iter);
1786  while (_dbus_hash_iter_next (&iter))
1787  {
1789  _dbus_assert (count_entries (table1) == i - 1);
1790  --i;
1791  }
1792 
1793  _dbus_hash_iter_init (table2, &iter);
1794  while (_dbus_hash_iter_next (&iter))
1795  {
1796  int key;
1797  const void *value;
1798 
1799  key = _dbus_hash_iter_get_int_key (&iter);
1800  value = _dbus_hash_iter_get_value (&iter);
1801 
1802  _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1803 
1804  str_value = _dbus_strdup ("Different value!");
1805  if (str_value == NULL)
1806  goto out;
1807 
1808  value = str_value;
1809  _dbus_hash_iter_set_value (&iter, steal (&str_value));
1810  _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1811  }
1812 
1813  i = count_entries (table2);
1814  _dbus_hash_iter_init (table2, &iter);
1815  while (_dbus_hash_iter_next (&iter))
1816  {
1818  _dbus_assert (count_entries (table2) + 1 == i);
1819  --i;
1820  }
1821 
1822  /* add/remove interleaved, to check that we grow/shrink the table
1823  * appropriately
1824  */
1825  i = 0;
1826  while (i < 1000)
1827  {
1828  str_key = _dbus_strdup (keys[i]);
1829  if (str_key == NULL)
1830  goto out;
1831 
1832  str_value = _dbus_strdup ("Value!");
1833  if (str_value == NULL)
1834  goto out;
1835 
1836  if (!_dbus_hash_table_insert_string (table1,
1837  steal (&str_key),
1838  steal (&str_value)))
1839  goto out;
1840 
1841  ++i;
1842  }
1843 
1844  --i;
1845  while (i >= 0)
1846  {
1847  str_key = _dbus_strdup (keys[i]);
1848  if (str_key == NULL)
1849  goto out;
1850  str_value = _dbus_strdup ("Value!");
1851  if (str_value == NULL)
1852  goto out;
1853 
1854  if (!_dbus_hash_table_remove_string (table1, keys[i]))
1855  goto out;
1856 
1857  if (!_dbus_hash_table_insert_string (table1,
1858  steal (&str_key),
1859  steal (&str_value)))
1860  goto out;
1861 
1862  if (!_dbus_hash_table_remove_string (table1, keys[i]))
1863  goto out;
1864 
1866 
1867  --i;
1868  }
1869 
1870  /* nuke these tables */
1871  _dbus_hash_table_unref (table1);
1872  _dbus_hash_table_unref (table2);
1873 
1874 
1875  /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1876  * be sure that interface works.
1877  */
1879  dbus_free, dbus_free);
1880  if (table1 == NULL)
1881  goto out;
1882 
1884  NULL, dbus_free);
1885  if (table2 == NULL)
1886  goto out;
1887 
1888  i = 0;
1889  while (i < 3000)
1890  {
1891  const void *out_value;
1892 
1893  str_key = _dbus_strdup (keys[i]);
1894  if (str_key == NULL)
1895  goto out;
1896  str_value = _dbus_strdup ("Value!");
1897  if (str_value == NULL)
1898  goto out;
1899 
1900  if (!_dbus_hash_iter_lookup (table1,
1901  steal (&str_key), TRUE, &iter))
1902  goto out;
1904  _dbus_hash_iter_set_value (&iter, steal (&str_value));
1905 
1906  str_value = _dbus_strdup (keys[i]);
1907  if (str_value == NULL)
1908  goto out;
1909 
1910  if (!_dbus_hash_iter_lookup (table2,
1911  _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1912  goto out;
1914  _dbus_hash_iter_set_value (&iter, steal (&str_value));
1915 
1916  _dbus_assert (count_entries (table1) == i + 1);
1917  _dbus_assert (count_entries (table2) == i + 1);
1918 
1919  if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1920  goto out;
1921 
1922  out_value = _dbus_hash_iter_get_value (&iter);
1923  _dbus_assert (out_value != NULL);
1924  _dbus_assert (strcmp (out_value, "Value!") == 0);
1925 
1926  /* Iterate just to be sure it works, though
1927  * it's a stupid thing to do
1928  */
1929  while (_dbus_hash_iter_next (&iter))
1930  ;
1931 
1932  if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1933  goto out;
1934 
1935  out_value = _dbus_hash_iter_get_value (&iter);
1936  _dbus_assert (out_value != NULL);
1937  _dbus_assert (strcmp (out_value, keys[i]) == 0);
1938 
1939  /* Iterate just to be sure it works, though
1940  * it's a stupid thing to do
1941  */
1942  while (_dbus_hash_iter_next (&iter))
1943  ;
1944 
1945  ++i;
1946  }
1947 
1948  --i;
1949  while (i >= 0)
1950  {
1951  if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1952  _dbus_test_fatal ("hash entry should have existed");
1954 
1955  if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1956  _dbus_test_fatal ("hash entry should have existed");
1958 
1959  _dbus_assert (count_entries (table1) == i);
1960  _dbus_assert (count_entries (table2) == i);
1961 
1962  --i;
1963  }
1964 
1965  _dbus_hash_table_unref (table1);
1966  _dbus_hash_table_unref (table2);
1967 
1968  ret = TRUE;
1969 
1970  out:
1971  for (i = 0; i < N_HASH_KEYS; i++)
1972  dbus_free (keys[i]);
1973 
1974  dbus_free (keys);
1975 
1976  dbus_free (str_key);
1977  dbus_free (str_value);
1978 
1979  return ret;
1980 }
1981 
1982 #endif /* DBUS_ENABLE_EMBEDDED_TESTS */
dbus_bool_t _dbus_string_append(DBusString *str, const char *buffer)
Appends a nul-terminated C-style string to a DBusString.
Definition: dbus-string.c:952
void * _dbus_hash_table_lookup_uintptr(DBusHashTable *table, uintptr_t key)
Looks up the value for a given integer in a hash table of type DBUS_HASH_UINTPTR. ...
Definition: dbus-hash.c:1110
DBusHashEntry *(* DBusFindEntryFunction)(DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated)
Function used to find and optionally create a hash entry.
Definition: dbus-hash.c:157
struct DBusPreallocatedHash DBusPreallocatedHash
A preallocated hash entry.
Definition: dbus-hash.h:149
#define NULL
A null pointer, defined appropriately for C or C++.
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition: dbus-mempool.c:214
void(* DBusFreeFunction)(void *memory)
The type of a function which frees a block of memory.
Definition: dbus-memory.h:63
DBusPreallocatedHash * _dbus_hash_table_preallocate_entry(DBusHashTable *table)
Preallocate an opaque data blob that allows us to insert into the hash table at a later time without ...
Definition: dbus-hash.c:1333
int down_shift
Shift count used in hashing function.
Definition: dbus-hash.c:192
void dbus_free(void *memory)
Frees a block of memory previously allocated by dbus_malloc() or dbus_malloc0().
Definition: dbus-memory.c:703
dbus_bool_t _dbus_hash_table_insert_int(DBusHashTable *table, int key, void *value)
Creates a hash entry with the given key and value.
Definition: dbus-hash.c:1259
#define dbus_new(type, count)
Safe macro for using dbus_malloc().
Definition: dbus-memory.h:57
void _dbus_hash_iter_set_value(DBusHashIter *iter, void *value)
Sets the value of the current entry.
Definition: dbus-hash.c:637
const char * _dbus_hash_iter_get_string_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:697
#define _dbus_assert(condition)
Aborts with an error message if the condition is false.
#define _DBUS_INT_TO_POINTER(integer)
Safely stuffs an integer into a pointer, to be extracted later with _DBUS_POINTER_TO_INT.
dbus_bool_t _dbus_hash_table_insert_uintptr(DBusHashTable *table, uintptr_t key, void *value)
Creates a hash entry with the given key and value.
Definition: dbus-hash.c:1300
void _dbus_hash_table_unref(DBusHashTable *table)
Decrements the reference count for a hash table, freeing the hash table if the count reaches zero...
Definition: dbus-hash.c:362
DBusHashType key_type
Type of keys used in this table.
Definition: dbus-hash.c:199
int n_buckets
Total number of buckets allocated at **buckets.
Definition: dbus-hash.c:180
dbus_bool_t _dbus_string_init(DBusString *str)
Initializes a string.
Definition: dbus-string.c:175
DBusHashTable * _dbus_hash_table_ref(DBusHashTable *table)
Increments the reference count for a hash table.
Definition: dbus-hash.c:348
dbus_bool_t _dbus_hash_iter_next(DBusHashIter *iter)
Move the hash iterator forward one step, to the next hash entry.
Definition: dbus-hash.c:544
Hash keys are strings.
Definition: dbus-hash.h:69
dbus_bool_t _dbus_mem_pool_dealloc(DBusMemPool *pool, void *element)
Deallocates an object previously created with _dbus_mem_pool_alloc().
Definition: dbus-mempool.c:347
Hash keys are integer capable to hold a pointer.
Definition: dbus-hash.h:71
Hash iterator object.
Definition: dbus-hash.h:49
void _dbus_hash_table_remove_all(DBusHashTable *table)
Removed all entries from a hash table.
Definition: dbus-hash.c:419
dbus_bool_t _dbus_hash_table_from_array(DBusHashTable *table, char **array, char delimiter)
Imports a string array into a hash table The hash table needs to be initialized with string keys...
Definition: dbus-hash.c:1426
#define _DBUS_INT_MAX
Maximum value of type "int".
void _dbus_hash_table_insert_string_preallocated(DBusHashTable *table, DBusPreallocatedHash *preallocated, char *key, void *value)
Inserts a string-keyed entry into the hash table, using a preallocated data block from _dbus_hash_tab...
Definition: dbus-hash.c:1377
dbus_bool_t _dbus_hash_table_remove_int(DBusHashTable *table, int key)
Removes the hash entry for the given key.
Definition: dbus-hash.c:1162
void * dbus_malloc(size_t bytes)
Allocates the given number of bytes, as with standard malloc().
Definition: dbus-memory.c:463
Hash keys are integers.
Definition: dbus-hash.h:70
#define dbus_new0(type, count)
Safe macro for using dbus_malloc0().
Definition: dbus-memory.h:58
int _dbus_hash_table_get_n_entries(DBusHashTable *table)
Gets the number of hash entries in a hash table.
Definition: dbus-hash.c:1408
void * _dbus_hash_iter_get_value(DBusHashIter *iter)
Gets the value of the current entry.
Definition: dbus-hash.c:614
dbus_uint32_t dbus_bool_t
A boolean, valid values are TRUE and FALSE.
Definition: dbus-types.h:35
void * key
Hash key.
Definition: dbus-hash.c:150
int next_bucket
index of next bucket
Definition: dbus-hash.c:222
void * value
Hash value.
Definition: dbus-hash.c:151
uintptr_t _dbus_hash_iter_get_uintptr_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:679
dbus_bool_t _dbus_hash_table_insert_string(DBusHashTable *table, char *key, void *value)
Creates a hash entry with the given key and value.
Definition: dbus-hash.c:1225
dbus_bool_t _dbus_string_append_printf(DBusString *str, const char *format,...)
Appends a printf-style formatted string to the DBusString.
Definition: dbus-string.c:1131
DBusHashEntry * entry
Current hash entry.
Definition: dbus-hash.c:220
int(* KeyCompareFunc)(const void *key_a, const void *key_b)
Key comparison function.
Definition: dbus-hash.c:854
void _dbus_hash_iter_remove_entry(DBusHashIter *iter)
Removes the current entry from the hash table.
Definition: dbus-hash.c:593
Internals of DBusHashIter.
Definition: dbus-hash.c:213
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
Definition: dbus-mempool.c:187
int lo_rebuild_size
Shrink table when n_entries gets below this.
Definition: dbus-hash.c:189
#define _DBUS_POINTER_TO_INT(pointer)
Safely casts a void* to an integer; should only be used on void* that actually contain integers...
Internal representation of a hash entry.
Definition: dbus-hash.c:144
Internals fields of DBusMemPool.
Definition: dbus-mempool.c:98
DBusHashEntry * next
Pointer to next entry in this hash bucket, or NULL for end of chain.
Definition: dbus-hash.c:146
int n_entries_on_init
used to detect table resize since initialization
Definition: dbus-hash.c:223
int refcount
Reference count.
Definition: dbus-hash.c:170
DBusHashEntry ** buckets
Pointer to bucket array.
Definition: dbus-hash.c:172
DBusHashTable * table
Pointer to table containing entry.
Definition: dbus-hash.c:215
#define _DBUS_N_ELEMENTS(array)
Computes the number of elements in a fixed-size array using sizeof().
void _dbus_string_free(DBusString *str)
Frees a string created by _dbus_string_init(), and fills it with the same contents as #_DBUS_STRING_I...
Definition: dbus-string.c:264
DBusHashEntry * static_buckets[DBUS_SMALL_HASH_TABLE]
Bucket array used for small tables (to avoid mallocs and frees).
Definition: dbus-hash.c:176
#define TRUE
Expands to "1".
#define _dbus_assert_not_reached(explanation)
Aborts with an error message if called.
int hi_rebuild_size
Enlarge table when n_entries gets to be this large.
Definition: dbus-hash.c:186
DBusFreeFunction free_value_function
Function to free values.
Definition: dbus-hash.c:205
DBusHashEntry ** bucket
Pointer to bucket that points to first entry in this entry&#39;s chain: used for deleting the entry...
Definition: dbus-hash.c:216
DBusHashType
Indicates the type of a key in the hash table.
Definition: dbus-hash.h:67
DBusFreeFunction free_key_function
Function to free keys.
Definition: dbus-hash.c:204
dbus_bool_t _dbus_hash_table_remove_string(DBusHashTable *table, const char *key)
Removes the hash entry for the given key.
Definition: dbus-hash.c:1134
void _dbus_hash_iter_init(DBusHashTable *table, DBusHashIter *iter)
Initializes a hash table iterator.
Definition: dbus-hash.c:518
void dbus_free_string_array(char **str_array)
Frees a NULL-terminated array of strings.
Definition: dbus-memory.c:751
char ** _dbus_hash_table_to_array(DBusHashTable *table, char delimiter)
Creates a string array from a hash table.
Definition: dbus-hash.c:1491
void * _dbus_hash_table_lookup_string(DBusHashTable *table, const char *key)
Looks up the value for a given string in a hash table of type DBUS_HASH_STRING.
Definition: dbus-hash.c:1060
void * _dbus_hash_table_lookup_int(DBusHashTable *table, int key)
Looks up the value for a given integer in a hash table of type DBUS_HASH_INT.
Definition: dbus-hash.c:1085
int _dbus_hash_iter_get_int_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:660
void _dbus_hash_table_free_preallocated_entry(DBusHashTable *table, DBusPreallocatedHash *preallocated)
Frees an opaque DBusPreallocatedHash that was not used in order to insert into the hash table...
Definition: dbus-hash.c:1350
#define FALSE
Expands to "0".
#define DBUS_SMALL_HASH_TABLE
Initial number of buckets in hash table (hash table statically allocates its buckets for this size an...
Definition: dbus-hash.c:131
dbus_bool_t _dbus_hash_iter_lookup(DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashIter *iter)
A low-level but efficient interface for manipulating the hash table.
Definition: dbus-hash.c:742
dbus_bool_t _dbus_string_set_length(DBusString *str, int length)
Sets the length of a string.
Definition: dbus-string.c:819
dbus_bool_t _dbus_string_steal_data(DBusString *str, char **data_return)
Like _dbus_string_get_data(), but removes the gotten data from the original string.
Definition: dbus-string.c:658
Internals of DBusHashTable.
Definition: dbus-hash.c:169
char * _dbus_strdup(const char *str)
Duplicates a string.
DBusHashEntry * next_entry
Next entry to be iterated onto in current bucket.
Definition: dbus-hash.c:221
#define REBUILD_MULTIPLIER
When there are this many entries per bucket, on average, rebuild the hash table to make it larger...
Definition: dbus-hash.c:105
int mask
Mask value used in hashing function.
Definition: dbus-hash.c:196
dbus_bool_t _dbus_hash_table_remove_uintptr(DBusHashTable *table, uintptr_t key)
Removes the hash entry for the given key.
Definition: dbus-hash.c:1190
DBusFindEntryFunction find_function
Function for finding entries.
Definition: dbus-hash.c:202
DBusHashTable * _dbus_hash_table_new(DBusHashType type, DBusFreeFunction key_free_function, DBusFreeFunction value_free_function)
Constructs a new hash table.
Definition: dbus-hash.c:286
dbus_bool_t _dbus_string_split_on_byte(DBusString *source, unsigned char byte, DBusString *tail)
Looks for the first occurance of a byte, deletes that byte, and moves everything after the byte to th...
Definition: dbus-string.c:1484
DBusMemPool * _dbus_mem_pool_new(int element_size, dbus_bool_t zero_elements)
Creates a new memory pool, or returns NULL on failure.
Definition: dbus-mempool.c:138
#define RANDOM_INDEX(table, i)
Takes a preliminary integer hash value and produces an index into a hash tables bucket list...
Definition: dbus-hash.c:123
int n_entries
Total number of entries present in table.
Definition: dbus-hash.c:183
DBusMemPool * entry_pool
Memory pool for hash entries.
Definition: dbus-hash.c:207