D-Bus  1.12.2
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 {
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 
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 
307 
308  table->buckets = table->static_buckets;
310  table->n_entries = 0;
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 
348 {
349  table->refcount += 1;
350 
351  return table;
352 }
353 
360 void
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 ;-) */
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 
417 void
419 {
420  DBusHashIter iter;
421  _dbus_hash_iter_init (table, &iter);
422  while (_dbus_hash_iter_next (&iter))
423  {
425  }
426 }
427 
428 static DBusHashEntry*
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
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
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
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 
516 void
518  DBusHashIter *iter)
519 {
520  DBusRealHashIter *real;
521 
522  _DBUS_STATIC_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 
544 {
545  DBusRealHashIter *real;
546 
547  _DBUS_STATIC_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 
591 void
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 
612 void*
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 
635 void
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 
658 int
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 
677 uintptr_t
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 
695 const char*
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 
742  void *key,
743  dbus_bool_t create_if_not_found,
744  DBusHashIter *iter)
745 {
746  DBusRealHashIter *real;
747  DBusHashEntry *entry;
748  DBusHashEntry **bucket;
749 
750  _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
751 
752  real = (DBusRealHashIter*) iter;
753 
754  entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
755 
756  if (entry == NULL)
757  return FALSE;
758 
759  if (create_if_not_found)
760  {
761  if (table->free_key_function && entry->key != key)
762  (* table->free_key_function) (entry->key);
763 
764  entry->key = key;
765  }
766 
767  real->table = table;
768  real->bucket = bucket;
769  real->entry = entry;
770  real->next_entry = entry->next;
771  real->next_bucket = (bucket - table->buckets) + 1;
772  real->n_entries_on_init = table->n_entries;
773 
774  _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
775 
776  return TRUE;
777 }
778 
779 static void
780 add_allocated_entry (DBusHashTable *table,
781  DBusHashEntry *entry,
782  unsigned int idx,
783  void *key,
784  DBusHashEntry ***bucket)
785 {
786  DBusHashEntry **b;
787 
788  entry->key = key;
789 
790  b = &(table->buckets[idx]);
791  entry->next = *b;
792  *b = entry;
793 
794  if (bucket)
795  *bucket = b;
796 
797  table->n_entries += 1;
798 
799  /* note we ONLY rebuild when ADDING - because you can iterate over a
800  * table and remove entries safely.
801  */
802  if (table->n_entries >= table->hi_rebuild_size ||
803  table->n_entries < table->lo_rebuild_size)
804  rebuild_table (table);
805 }
806 
807 static DBusHashEntry*
808 add_entry (DBusHashTable *table,
809  unsigned int idx,
810  void *key,
811  DBusHashEntry ***bucket,
812  DBusPreallocatedHash *preallocated)
813 {
814  DBusHashEntry *entry;
815 
816  if (preallocated == NULL)
817  {
818  entry = alloc_entry (table);
819  if (entry == NULL)
820  {
821  if (bucket)
822  *bucket = NULL;
823  return NULL;
824  }
825  }
826  else
827  {
828  entry = (DBusHashEntry*) preallocated;
829  }
830 
831  add_allocated_entry (table, entry, idx, key, bucket);
832 
833  return entry;
834 }
835 
836 /* This is g_str_hash from GLib which was
837  * extensively discussed/tested/profiled
838  */
839 static unsigned int
840 string_hash (const char *str)
841 {
842  const char *p = str;
843  unsigned int h = *p;
844 
845  if (h)
846  for (p += 1; *p != '\0'; p++)
847  h = (h << 5) - h + *p;
848 
849  return h;
850 }
851 
853 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
854 
855 static DBusHashEntry*
856 find_generic_function (DBusHashTable *table,
857  void *key,
858  unsigned int idx,
859  KeyCompareFunc compare_func,
860  dbus_bool_t create_if_not_found,
861  DBusHashEntry ***bucket,
862  DBusPreallocatedHash *preallocated)
863 {
864  DBusHashEntry *entry;
865 
866  if (bucket)
867  *bucket = NULL;
868 
869  /* Search all of the entries in this bucket. */
870  entry = table->buckets[idx];
871  while (entry != NULL)
872  {
873  if ((compare_func == NULL && key == entry->key) ||
874  (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
875  {
876  if (bucket)
877  *bucket = &(table->buckets[idx]);
878 
879  if (preallocated)
880  _dbus_hash_table_free_preallocated_entry (table, preallocated);
881 
882  return entry;
883  }
884 
885  entry = entry->next;
886  }
887 
888  if (create_if_not_found)
889  entry = add_entry (table, idx, key, bucket, preallocated);
890  else if (preallocated)
891  _dbus_hash_table_free_preallocated_entry (table, preallocated);
892 
893  return entry;
894 }
895 
896 static DBusHashEntry*
897 find_string_function (DBusHashTable *table,
898  void *key,
899  dbus_bool_t create_if_not_found,
900  DBusHashEntry ***bucket,
901  DBusPreallocatedHash *preallocated)
902 {
903  unsigned int idx;
904 
905  idx = string_hash (key) & table->mask;
906 
907  return find_generic_function (table, key, idx,
908  (KeyCompareFunc) strcmp, create_if_not_found, bucket,
909  preallocated);
910 }
911 
912 static DBusHashEntry*
913 find_direct_function (DBusHashTable *table,
914  void *key,
915  dbus_bool_t create_if_not_found,
916  DBusHashEntry ***bucket,
917  DBusPreallocatedHash *preallocated)
918 {
919  unsigned int idx;
920 
921  idx = RANDOM_INDEX (table, key) & table->mask;
922 
923 
924  return find_generic_function (table, key, idx,
925  NULL, create_if_not_found, bucket,
926  preallocated);
927 }
928 
929 static void
930 rebuild_table (DBusHashTable *table)
931 {
932  int old_size;
933  int new_buckets;
934  DBusHashEntry **old_buckets;
935  DBusHashEntry **old_chain;
936  DBusHashEntry *entry;
937  dbus_bool_t growing;
938 
939  /*
940  * Allocate and initialize the new bucket array, and set up
941  * hashing constants for new array size.
942  */
943 
944  growing = table->n_entries >= table->hi_rebuild_size;
945 
946  old_size = table->n_buckets;
947  old_buckets = table->buckets;
948 
949  if (growing)
950  {
951  /* overflow paranoia */
952  if (table->n_buckets < _DBUS_INT_MAX / 4 &&
953  table->down_shift >= 2)
954  new_buckets = table->n_buckets * 4;
955  else
956  return; /* can't grow anymore */
957  }
958  else
959  {
960  new_buckets = table->n_buckets / 4;
961  if (new_buckets < DBUS_SMALL_HASH_TABLE)
962  return; /* don't bother shrinking this far */
963  }
964 
965  table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
966  if (table->buckets == NULL)
967  {
968  /* out of memory, yay - just don't reallocate, the table will
969  * still work, albeit more slowly.
970  */
971  table->buckets = old_buckets;
972  return;
973  }
974 
975  table->n_buckets = new_buckets;
976 
977  if (growing)
978  {
979  table->lo_rebuild_size = table->hi_rebuild_size;
980  table->hi_rebuild_size *= 4;
981 
982  table->down_shift -= 2; /* keep 2 more high bits */
983  table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
984  }
985  else
986  {
987  table->hi_rebuild_size = table->lo_rebuild_size;
988  table->lo_rebuild_size /= 4;
989 
990  table->down_shift += 2; /* keep 2 fewer high bits */
991  table->mask = table->mask >> 2; /* keep 2 fewer high bits */
992  }
993 
994 #if 0
995  printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
996  growing ? "GROW" : "SHRINK",
997  table->lo_rebuild_size,
998  table->hi_rebuild_size,
999  table->down_shift,
1000  table->mask);
1001 #endif
1002 
1003  _dbus_assert (table->lo_rebuild_size >= 0);
1004  _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
1005  _dbus_assert (table->down_shift >= 0);
1006  _dbus_assert (table->mask != 0);
1007  /* the mask is essentially the max index */
1008  _dbus_assert (table->mask < table->n_buckets);
1009 
1010  /*
1011  * Rehash all of the existing entries into the new bucket array.
1012  */
1013 
1014  for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1015  {
1016  for (entry = *old_chain; entry != NULL; entry = *old_chain)
1017  {
1018  unsigned int idx;
1019  DBusHashEntry **bucket;
1020 
1021  *old_chain = entry->next;
1022  switch (table->key_type)
1023  {
1024  case DBUS_HASH_STRING:
1025  idx = string_hash (entry->key) & table->mask;
1026  break;
1027  case DBUS_HASH_INT:
1028  case DBUS_HASH_UINTPTR:
1029  idx = RANDOM_INDEX (table, entry->key);
1030  break;
1031  default:
1032  idx = 0;
1033  _dbus_assert_not_reached ("Unknown hash table type");
1034  break;
1035  }
1036 
1037  bucket = &(table->buckets[idx]);
1038  entry->next = *bucket;
1039  *bucket = entry;
1040  }
1041  }
1042 
1043  /* Free the old bucket array, if it was dynamically allocated. */
1044 
1045  if (old_buckets != table->static_buckets)
1046  dbus_free (old_buckets);
1047 }
1048 
1058 void*
1060  const char *key)
1061 {
1062  DBusHashEntry *entry;
1063 
1065 
1066  entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1067 
1068  if (entry)
1069  return entry->value;
1070  else
1071  return NULL;
1072 }
1073 
1083 void*
1085  int key)
1086 {
1087  DBusHashEntry *entry;
1088 
1089  _dbus_assert (table->key_type == DBUS_HASH_INT);
1090 
1091  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1092 
1093  if (entry)
1094  return entry->value;
1095  else
1096  return NULL;
1097 }
1098 
1108 void*
1110  uintptr_t key)
1111 {
1112  DBusHashEntry *entry;
1113 
1115 
1116  entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1117 
1118  if (entry)
1119  return entry->value;
1120  else
1121  return NULL;
1122 }
1123 
1134  const char *key)
1135 {
1136  DBusHashEntry *entry;
1137  DBusHashEntry **bucket;
1138 
1140 
1141  entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1142 
1143  if (entry)
1144  {
1145  remove_entry (table, bucket, entry);
1146  return TRUE;
1147  }
1148  else
1149  return FALSE;
1150 }
1151 
1162  int key)
1163 {
1164  DBusHashEntry *entry;
1165  DBusHashEntry **bucket;
1166 
1167  _dbus_assert (table->key_type == DBUS_HASH_INT);
1168 
1169  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1170 
1171  if (entry)
1172  {
1173  remove_entry (table, bucket, entry);
1174  return TRUE;
1175  }
1176  else
1177  return FALSE;
1178 }
1179 
1190  uintptr_t key)
1191 {
1192  DBusHashEntry *entry;
1193  DBusHashEntry **bucket;
1194 
1196 
1197  entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1198 
1199  if (entry)
1200  {
1201  remove_entry (table, bucket, entry);
1202  return TRUE;
1203  }
1204  else
1205  return FALSE;
1206 }
1207 
1225  char *key,
1226  void *value)
1227 {
1228  DBusPreallocatedHash *preallocated;
1229 
1231 
1232  preallocated = _dbus_hash_table_preallocate_entry (table);
1233  if (preallocated == NULL)
1234  return FALSE;
1235 
1236  _dbus_hash_table_insert_string_preallocated (table, preallocated,
1237  key, value);
1238 
1239  return TRUE;
1240 }
1241 
1259  int key,
1260  void *value)
1261 {
1262  DBusHashEntry *entry;
1263 
1264  _dbus_assert (table->key_type == DBUS_HASH_INT);
1265 
1266  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1267 
1268  if (entry == NULL)
1269  return FALSE; /* no memory */
1270 
1271  if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1272  (* table->free_key_function) (entry->key);
1273 
1274  if (table->free_value_function && entry->value != value)
1275  (* table->free_value_function) (entry->value);
1276 
1277  entry->key = _DBUS_INT_TO_POINTER (key);
1278  entry->value = value;
1279 
1280  return TRUE;
1281 }
1282 
1300  uintptr_t key,
1301  void *value)
1302 {
1303  DBusHashEntry *entry;
1304 
1306 
1307  entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1308 
1309  if (entry == NULL)
1310  return FALSE; /* no memory */
1311 
1312  if (table->free_key_function && entry->key != (void*) key)
1313  (* table->free_key_function) (entry->key);
1314 
1315  if (table->free_value_function && entry->value != value)
1316  (* table->free_value_function) (entry->value);
1317 
1318  entry->key = (void*) key;
1319  entry->value = value;
1320 
1321  return TRUE;
1322 }
1323 
1333 {
1334  DBusHashEntry *entry;
1335 
1336  entry = alloc_entry (table);
1337 
1338  return (DBusPreallocatedHash*) entry;
1339 }
1340 
1348 void
1350  DBusPreallocatedHash *preallocated)
1351 {
1352  DBusHashEntry *entry;
1353 
1354  _dbus_assert (preallocated != NULL);
1355 
1356  entry = (DBusHashEntry*) preallocated;
1357 
1358  /* Don't use free_entry(), since this entry has no key/data */
1359  _dbus_mem_pool_dealloc (table->entry_pool, entry);
1360 }
1361 
1375 void
1377  DBusPreallocatedHash *preallocated,
1378  char *key,
1379  void *value)
1380 {
1381  DBusHashEntry *entry;
1382 
1384  _dbus_assert (preallocated != NULL);
1385 
1386  entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1387 
1388  _dbus_assert (entry != NULL);
1389 
1390  if (table->free_key_function && entry->key != key)
1391  (* table->free_key_function) (entry->key);
1392 
1393  if (table->free_value_function && entry->value != value)
1394  (* table->free_value_function) (entry->value);
1395 
1396  entry->key = key;
1397  entry->value = value;
1398 }
1399 
1406 int
1408 {
1409  return table->n_entries;
1410 }
1411 
1425 _dbus_hash_table_from_array (DBusHashTable *table, char **array, char delimiter)
1426 {
1427  DBusString key;
1428  DBusString value;
1429  int i;
1430  dbus_bool_t retval = FALSE;
1431 
1432  _dbus_assert (table != NULL);
1433  _dbus_assert (array != NULL);
1434 
1435  if (!_dbus_string_init (&key))
1436  {
1437  return FALSE;
1438  }
1439 
1440  if (!_dbus_string_init (&value))
1441  {
1442  _dbus_string_free (&key);
1443  return FALSE;
1444  }
1445 
1446  for (i = 0; array[i] != NULL; i++)
1447  {
1448  if (!_dbus_string_append (&key, array[i]))
1449  break;
1450 
1451  if (_dbus_string_split_on_byte (&key, delimiter, &value))
1452  {
1453  char *hash_key, *hash_value;
1454 
1455  if (!_dbus_string_steal_data (&key, &hash_key))
1456  break;
1457 
1458  if (!_dbus_string_steal_data (&value, &hash_value))
1459  break;
1460 
1461  if (!_dbus_hash_table_insert_string (table,
1462  hash_key, hash_value))
1463  break;
1464  }
1465  _dbus_string_set_length (&key, 0);
1466  _dbus_string_set_length (&value, 0);
1467  }
1468 
1469  if (array[i] != NULL)
1470  goto out;
1471 
1472  retval = TRUE;
1473 out:
1474 
1475  _dbus_string_free (&key);
1476  _dbus_string_free (&value);
1477 
1478  return retval;
1479 }
1480 
1489 char **
1491 {
1492  int i, length;
1493  DBusString entry;
1494  DBusHashIter iter;
1495  char **array;
1496 
1497  _dbus_assert (table != NULL);
1498 
1499  length = _dbus_hash_table_get_n_entries (table);
1500 
1501  array = dbus_new0 (char *, length + 1);
1502 
1503  if (array == NULL)
1504  return NULL;
1505 
1506  i = 0;
1507  _dbus_hash_iter_init (table, &iter);
1508 
1509  if (!_dbus_string_init (&entry))
1510  {
1511  dbus_free_string_array (array);
1512  return NULL;
1513  }
1514 
1515  while (_dbus_hash_iter_next (&iter))
1516  {
1517  const char *key, *value;
1518 
1519  key = (const char *) _dbus_hash_iter_get_string_key (&iter);
1520  value = (const char *) _dbus_hash_iter_get_value (&iter);
1521 
1522  if (!_dbus_string_append_printf (&entry, "%s%c%s", key, delimiter, value))
1523  break;
1524 
1525  if (!_dbus_string_steal_data (&entry, array + i))
1526  break;
1527  i++;
1528  }
1529 
1530  _dbus_string_free (&entry);
1531 
1532  if (i != length)
1533  {
1534  dbus_free_string_array (array);
1535  array = NULL;
1536  }
1537 
1538  return array;
1539 }
1540 
1543 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
1544 #include "dbus-test.h"
1545 #include <stdio.h>
1546 
1547 /* If you're wondering why the hash table test takes
1548  * forever to run, it's because we call this function
1549  * in inner loops thus making things quadratic.
1550  */
1551 static int
1552 count_entries (DBusHashTable *table)
1553 {
1554  DBusHashIter iter;
1555  int count;
1556 
1557  count = 0;
1558  _dbus_hash_iter_init (table, &iter);
1559  while (_dbus_hash_iter_next (&iter))
1560  ++count;
1561 
1562  _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1563 
1564  return count;
1565 }
1566 
1567 static inline void *
1568 steal (void *ptr)
1569 {
1570  /* @ptr is passed in as void* to avoid casting in the call */
1571  void **_ptr = (void **) ptr;
1572  void *val;
1573 
1574  val = *_ptr;
1575  *_ptr = NULL;
1576 
1577  return val;
1578 }
1579 
1586 _dbus_hash_test (void)
1587 {
1588  int i;
1589  DBusHashTable *table1;
1590  DBusHashTable *table2;
1591  DBusHashTable *table3;
1592  DBusHashIter iter;
1593 #define N_HASH_KEYS 5000
1594  char **keys;
1595  dbus_bool_t ret = FALSE;
1596  char *str_key = NULL;
1597  char *str_value = NULL;
1598 
1599  keys = dbus_new (char *, N_HASH_KEYS);
1600  if (keys == NULL)
1601  _dbus_assert_not_reached ("no memory");
1602 
1603  for (i = 0; i < N_HASH_KEYS; i++)
1604  {
1605  keys[i] = dbus_malloc (128);
1606 
1607  if (keys[i] == NULL)
1608  _dbus_assert_not_reached ("no memory");
1609  }
1610 
1611  printf ("Computing test hash keys...\n");
1612  i = 0;
1613  while (i < N_HASH_KEYS)
1614  {
1615  int len;
1616 
1617  len = sprintf (keys[i], "Hash key %d", i);
1618  _dbus_assert (*(keys[i] + len) == '\0');
1619  ++i;
1620  }
1621  printf ("... done.\n");
1622 
1624  dbus_free, dbus_free);
1625  if (table1 == NULL)
1626  goto out;
1627 
1629  NULL, dbus_free);
1630  if (table2 == NULL)
1631  goto out;
1632 
1634  NULL, dbus_free);
1635  if (table3 == NULL)
1636  goto out;
1637 
1638  /* Insert and remove a bunch of stuff, counting the table in between
1639  * to be sure it's not broken and that iteration works
1640  */
1641  i = 0;
1642  while (i < 3000)
1643  {
1644  const void *out_value;
1645 
1646  str_key = _dbus_strdup (keys[i]);
1647  if (str_key == NULL)
1648  goto out;
1649  str_value = _dbus_strdup ("Value!");
1650  if (str_value == NULL)
1651  goto out;
1652 
1653  if (!_dbus_hash_table_insert_string (table1,
1654  steal (&str_key),
1655  steal (&str_value)))
1656  goto out;
1657 
1658  str_value = _dbus_strdup (keys[i]);
1659  if (str_value == NULL)
1660  goto out;
1661 
1662  if (!_dbus_hash_table_insert_int (table2,
1663  i, steal (&str_value)))
1664  goto out;
1665 
1666  str_value = _dbus_strdup (keys[i]);
1667  if (str_value == NULL)
1668  goto out;
1669 
1670  if (!_dbus_hash_table_insert_uintptr (table3,
1671  i, steal (&str_value)))
1672  goto out;
1673 
1674  _dbus_assert (count_entries (table1) == i + 1);
1675  _dbus_assert (count_entries (table2) == i + 1);
1676  _dbus_assert (count_entries (table3) == i + 1);
1677 
1678  out_value = _dbus_hash_table_lookup_string (table1, keys[i]);
1679  _dbus_assert (out_value != NULL);
1680  _dbus_assert (strcmp (out_value, "Value!") == 0);
1681 
1682  out_value = _dbus_hash_table_lookup_int (table2, i);
1683  _dbus_assert (out_value != NULL);
1684  _dbus_assert (strcmp (out_value, keys[i]) == 0);
1685 
1686  out_value = _dbus_hash_table_lookup_uintptr (table3, i);
1687  _dbus_assert (out_value != NULL);
1688  _dbus_assert (strcmp (out_value, keys[i]) == 0);
1689 
1690  ++i;
1691  }
1692 
1693  --i;
1694  while (i >= 0)
1695  {
1697  keys[i]);
1698 
1699  _dbus_hash_table_remove_int (table2, i);
1700 
1701  _dbus_hash_table_remove_uintptr (table3, i);
1702 
1703  _dbus_assert (count_entries (table1) == i);
1704  _dbus_assert (count_entries (table2) == i);
1705  _dbus_assert (count_entries (table3) == i);
1706 
1707  --i;
1708  }
1709 
1710  _dbus_hash_table_ref (table1);
1711  _dbus_hash_table_ref (table2);
1712  _dbus_hash_table_ref (table3);
1713  _dbus_hash_table_unref (table1);
1714  _dbus_hash_table_unref (table2);
1715  _dbus_hash_table_unref (table3);
1716  _dbus_hash_table_unref (table1);
1717  _dbus_hash_table_unref (table2);
1718  _dbus_hash_table_unref (table3);
1719  table3 = NULL;
1720 
1721  /* Insert a bunch of stuff then check
1722  * that iteration works correctly (finds the right
1723  * values, iter_set_value works, etc.)
1724  */
1726  dbus_free, dbus_free);
1727  if (table1 == NULL)
1728  goto out;
1729 
1731  NULL, dbus_free);
1732  if (table2 == NULL)
1733  goto out;
1734 
1735  i = 0;
1736  while (i < 5000)
1737  {
1738  str_key = _dbus_strdup (keys[i]);
1739  if (str_key == NULL)
1740  goto out;
1741  str_value = _dbus_strdup ("Value!");
1742  if (str_value == NULL)
1743  goto out;
1744 
1745  if (!_dbus_hash_table_insert_string (table1,
1746  steal (&str_key),
1747  steal (&str_value)))
1748  goto out;
1749 
1750  str_value = _dbus_strdup (keys[i]);
1751  if (str_value == NULL)
1752  goto out;
1753 
1754  if (!_dbus_hash_table_insert_int (table2,
1755  i, steal (&str_value)))
1756  goto out;
1757 
1758  _dbus_assert (count_entries (table1) == i + 1);
1759  _dbus_assert (count_entries (table2) == i + 1);
1760 
1761  ++i;
1762  }
1763 
1764  _dbus_hash_iter_init (table1, &iter);
1765  while (_dbus_hash_iter_next (&iter))
1766  {
1767  const char *key;
1768  const void *value;
1769 
1770  key = _dbus_hash_iter_get_string_key (&iter);
1771  value = _dbus_hash_iter_get_value (&iter);
1772 
1773  _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1774 
1775  str_value = _dbus_strdup ("Different value!");
1776  if (str_value == NULL)
1777  goto out;
1778 
1779  value = str_value;
1780  _dbus_hash_iter_set_value (&iter, steal (&str_value));
1781  _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1782  }
1783 
1784  _dbus_hash_iter_init (table1, &iter);
1785  while (_dbus_hash_iter_next (&iter))
1786  {
1788  _dbus_assert (count_entries (table1) == i - 1);
1789  --i;
1790  }
1791 
1792  _dbus_hash_iter_init (table2, &iter);
1793  while (_dbus_hash_iter_next (&iter))
1794  {
1795  int key;
1796  const void *value;
1797 
1798  key = _dbus_hash_iter_get_int_key (&iter);
1799  value = _dbus_hash_iter_get_value (&iter);
1800 
1801  _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1802 
1803  str_value = _dbus_strdup ("Different value!");
1804  if (str_value == NULL)
1805  goto out;
1806 
1807  value = str_value;
1808  _dbus_hash_iter_set_value (&iter, steal (&str_value));
1809  _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1810  }
1811 
1812  i = count_entries (table2);
1813  _dbus_hash_iter_init (table2, &iter);
1814  while (_dbus_hash_iter_next (&iter))
1815  {
1817  _dbus_assert (count_entries (table2) + 1 == i);
1818  --i;
1819  }
1820 
1821  /* add/remove interleaved, to check that we grow/shrink the table
1822  * appropriately
1823  */
1824  i = 0;
1825  while (i < 1000)
1826  {
1827  str_key = _dbus_strdup (keys[i]);
1828  if (str_key == NULL)
1829  goto out;
1830 
1831  str_value = _dbus_strdup ("Value!");
1832  if (str_value == NULL)
1833  goto out;
1834 
1835  if (!_dbus_hash_table_insert_string (table1,
1836  steal (&str_key),
1837  steal (&str_value)))
1838  goto out;
1839 
1840  ++i;
1841  }
1842 
1843  --i;
1844  while (i >= 0)
1845  {
1846  str_key = _dbus_strdup (keys[i]);
1847  if (str_key == NULL)
1848  goto out;
1849  str_value = _dbus_strdup ("Value!");
1850  if (str_value == NULL)
1851  goto out;
1852 
1853  if (!_dbus_hash_table_remove_string (table1, keys[i]))
1854  goto out;
1855 
1856  if (!_dbus_hash_table_insert_string (table1,
1857  steal (&str_key),
1858  steal (&str_value)))
1859  goto out;
1860 
1861  if (!_dbus_hash_table_remove_string (table1, keys[i]))
1862  goto out;
1863 
1865 
1866  --i;
1867  }
1868 
1869  /* nuke these tables */
1870  _dbus_hash_table_unref (table1);
1871  _dbus_hash_table_unref (table2);
1872 
1873 
1874  /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1875  * be sure that interface works.
1876  */
1878  dbus_free, dbus_free);
1879  if (table1 == NULL)
1880  goto out;
1881 
1883  NULL, dbus_free);
1884  if (table2 == NULL)
1885  goto out;
1886 
1887  i = 0;
1888  while (i < 3000)
1889  {
1890  const void *out_value;
1891 
1892  str_key = _dbus_strdup (keys[i]);
1893  if (str_key == NULL)
1894  goto out;
1895  str_value = _dbus_strdup ("Value!");
1896  if (str_value == NULL)
1897  goto out;
1898 
1899  if (!_dbus_hash_iter_lookup (table1,
1900  steal (&str_key), TRUE, &iter))
1901  goto out;
1903  _dbus_hash_iter_set_value (&iter, steal (&str_value));
1904 
1905  str_value = _dbus_strdup (keys[i]);
1906  if (str_value == NULL)
1907  goto out;
1908 
1909  if (!_dbus_hash_iter_lookup (table2,
1910  _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1911  goto out;
1913  _dbus_hash_iter_set_value (&iter, steal (&str_value));
1914 
1915  _dbus_assert (count_entries (table1) == i + 1);
1916  _dbus_assert (count_entries (table2) == i + 1);
1917 
1918  if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1919  goto out;
1920 
1921  out_value = _dbus_hash_iter_get_value (&iter);
1922  _dbus_assert (out_value != NULL);
1923  _dbus_assert (strcmp (out_value, "Value!") == 0);
1924 
1925  /* Iterate just to be sure it works, though
1926  * it's a stupid thing to do
1927  */
1928  while (_dbus_hash_iter_next (&iter))
1929  ;
1930 
1931  if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1932  goto out;
1933 
1934  out_value = _dbus_hash_iter_get_value (&iter);
1935  _dbus_assert (out_value != NULL);
1936  _dbus_assert (strcmp (out_value, keys[i]) == 0);
1937 
1938  /* Iterate just to be sure it works, though
1939  * it's a stupid thing to do
1940  */
1941  while (_dbus_hash_iter_next (&iter))
1942  ;
1943 
1944  ++i;
1945  }
1946 
1947  --i;
1948  while (i >= 0)
1949  {
1950  if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1951  _dbus_assert_not_reached ("hash entry should have existed");
1953 
1954  if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1955  _dbus_assert_not_reached ("hash entry should have existed");
1957 
1958  _dbus_assert (count_entries (table1) == i);
1959  _dbus_assert (count_entries (table2) == i);
1960 
1961  --i;
1962  }
1963 
1964  _dbus_hash_table_unref (table1);
1965  _dbus_hash_table_unref (table2);
1966 
1967  ret = TRUE;
1968 
1969  out:
1970  for (i = 0; i < N_HASH_KEYS; i++)
1971  dbus_free (keys[i]);
1972 
1973  dbus_free (keys);
1974 
1975  dbus_free (str_key);
1976  dbus_free (str_value);
1977 
1978  return ret;
1979 }
1980 
1981 #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:935
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:1109
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:156
struct DBusPreallocatedHash DBusPreallocatedHash
A preallocated hash entry.
Definition: dbus-hash.h:147
#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:64
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:1332
int down_shift
Shift count used in hashing function.
Definition: dbus-hash.c:191
void dbus_free(void *memory)
Frees a block of memory previously allocated by dbus_malloc() or dbus_malloc0().
Definition: dbus-memory.c:702
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:1258
#define dbus_new(type, count)
Safe macro for using dbus_malloc().
Definition: dbus-memory.h:58
const char * _dbus_hash_iter_get_string_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:696
#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:1299
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:361
DBusHashType key_type
Type of keys used in this table.
Definition: dbus-hash.c:198
int n_buckets
Total number of buckets allocated at **buckets.
Definition: dbus-hash.c:179
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:347
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:543
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:418
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:1425
#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:1376
dbus_bool_t _dbus_hash_table_remove_int(DBusHashTable *table, int key)
Removes the hash entry for the given key.
Definition: dbus-hash.c:1161
void * dbus_malloc(size_t bytes)
Allocates the given number of bytes, as with standard malloc().
Definition: dbus-memory.c:462
Hash keys are integers.
Definition: dbus-hash.h:70
#define dbus_new0(type, count)
Safe macro for using dbus_malloc0().
Definition: dbus-memory.h:59
int _dbus_hash_table_get_n_entries(DBusHashTable *table)
Gets the number of hash entries in a hash table.
Definition: dbus-hash.c:1407
void * _dbus_hash_iter_get_value(DBusHashIter *iter)
Gets the value of the current entry.
Definition: dbus-hash.c:613
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:741
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:149
int next_bucket
index of next bucket
Definition: dbus-hash.c:221
void * value
Hash value.
Definition: dbus-hash.c:150
uintptr_t _dbus_hash_iter_get_uintptr_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:678
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:1224
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:1114
DBusHashEntry * entry
Current hash entry.
Definition: dbus-hash.c:219
int(* KeyCompareFunc)(const void *key_a, const void *key_b)
Key comparison function.
Definition: dbus-hash.c:853
void _dbus_hash_iter_remove_entry(DBusHashIter *iter)
Removes the current entry from the hash table.
Definition: dbus-hash.c:592
Internals of DBusHashIter.
Definition: dbus-hash.c:212
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:188
#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:143
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:145
int n_entries_on_init
used to detect table resize since initialization
Definition: dbus-hash.c:222
int refcount
Reference count.
Definition: dbus-hash.c:169
DBusHashEntry ** buckets
Pointer to bucket array.
Definition: dbus-hash.c:171
DBusHashTable * table
Pointer to table containing entry.
Definition: dbus-hash.c:214
#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().
Definition: dbus-string.c:259
DBusHashEntry * static_buckets[DBUS_SMALL_HASH_TABLE]
Bucket array used for small tables (to avoid mallocs and frees).
Definition: dbus-hash.c:175
#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:185
DBusFreeFunction free_value_function
Function to free values.
Definition: dbus-hash.c:204
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:215
void _dbus_hash_iter_set_value(DBusHashIter *iter, void *value)
Sets the value of the current entry.
Definition: dbus-hash.c:636
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:203
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:1133
void _dbus_hash_iter_init(DBusHashTable *table, DBusHashIter *iter)
Initializes a hash table iterator.
Definition: dbus-hash.c:517
void dbus_free_string_array(char **str_array)
Frees a NULL-terminated array of strings.
Definition: dbus-memory.c:750
char ** _dbus_hash_table_to_array(DBusHashTable *table, char delimiter)
Creates a string array from a hash table.
Definition: dbus-hash.c:1490
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:1059
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:1084
int _dbus_hash_iter_get_int_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:659
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:1349
#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:130
dbus_bool_t _dbus_string_set_length(DBusString *str, int length)
Sets the length of a string.
Definition: dbus-string.c:802
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:641
Internals of DBusHashTable.
Definition: dbus-hash.c:168
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:220
#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:104
int mask
Mask value used in hashing function.
Definition: dbus-hash.c:195
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:1189
DBusFindEntryFunction find_function
Function for finding entries.
Definition: dbus-hash.c:201
DBusHashTable * _dbus_hash_table_new(DBusHashType type, DBusFreeFunction key_free_function, DBusFreeFunction value_free_function)
Constructs a new hash table.
Definition: dbus-hash.c:285
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:1467
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:122
int n_entries
Total number of entries present in table.
Definition: dbus-hash.c:182
DBusMemPool * entry_pool
Memory pool for hash entries.
Definition: dbus-hash.c:206