D-Bus 1.15.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 1991-1993 The Regents of the University of California.
5 * Copyright 1994 Sun Microsystems, Inc.
6 * Copyright 2002-2005 Red Hat, Inc.
7 * Copyright 2003 Joe Shaw
8 * Copyright 2006 Sjoerd Simons
9 * Copyright 2010 Fridrich Štrba
10 * Copyright 2016 Ralf Habacker
11 * Copyright 2017 Endless Mobile, Inc.
12 *
13 * Hash table implementation based on generic/tclHash.c from the Tcl
14 * source code. The original Tcl license applies to portions of the
15 * code from tclHash.c; the Tcl license follows this standad D-Bus
16 * license information.
17 *
18 * Licensed under the Academic Free License version 2.1
19 *
20 * This program is free software; you can redistribute it and/or modify
21 * it under the terms of the GNU General Public License as published by
22 * the Free Software Foundation; either version 2 of the License, or
23 * (at your option) any later version.
24 *
25 * This program is distributed in the hope that it will be useful,
26 * but WITHOUT ANY WARRANTY; without even the implied warranty of
27 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 * GNU General Public License for more details.
29 *
30 * You should have received a copy of the GNU General Public License
31 * along with this program; if not, write to the Free Software
32 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
33 *
34 */
35/*
36 * The following copyright applies to code from the Tcl distribution.
37 *
38 * Copyright (c) 1991-1993 The Regents of the University of California.
39 * Copyright (c) 1994 Sun Microsystems, Inc.
40 *
41 * This software is copyrighted by the Regents of the University of
42 * California, Sun Microsystems, Inc., Scriptics Corporation, and
43 * other parties. The following terms apply to all files associated
44 * with the software unless explicitly disclaimed in individual files.
45 *
46 * The authors hereby grant permission to use, copy, modify,
47 * distribute, and license this software and its documentation for any
48 * purpose, provided that existing copyright notices are retained in
49 * all copies and that this notice is included verbatim in any
50 * distributions. No written agreement, license, or royalty fee is
51 * required for any of the authorized uses. Modifications to this
52 * software may be copyrighted by their authors and need not follow
53 * the licensing terms described here, provided that the new terms are
54 * clearly indicated on the first page of each file where they apply.
55 *
56 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
57 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
58 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
59 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
60 * OF THE POSSIBILITY OF SUCH DAMAGE.
61 *
62 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
63 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
64 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
65 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
66 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
67 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
68 *
69 * GOVERNMENT USE: If you are acquiring this software on behalf of the
70 * U.S. government, the Government shall have only "Restricted Rights"
71 * in the software and related documentation as defined in the Federal
72 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you
73 * are acquiring the software on behalf of the Department of Defense,
74 * the software shall be classified as "Commercial Computer Software"
75 * and the Government shall have only "Restricted Rights" as defined
76 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the
77 * foregoing, the authors grant the U.S. Government and others acting
78 * in its behalf permission to use and distribute the software in
79 * accordance with the terms specified in this license.
80 */
81
82#include <config.h>
83#include "dbus-hash.h"
84#include "dbus-internals.h"
85#include "dbus-mempool.h"
86#include <dbus/dbus-test-tap.h>
87
110#define REBUILD_MULTIPLIER 3
111
128#define RANDOM_INDEX(table, i) \
129 (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
130
136#define DBUS_SMALL_HASH_TABLE 4
137
142
150{
155 void *key;
156 void *value;
157};
158
162typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
163 void *key,
164 dbus_bool_t create_if_not_found,
165 DBusHashEntry ***bucket,
166 DBusPreallocatedHash *preallocated);
167
201 int mask;
213};
214
218typedef struct
219{
230
231_DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
232
233static DBusHashEntry* find_direct_function (DBusHashTable *table,
234 void *key,
235 dbus_bool_t create_if_not_found,
236 DBusHashEntry ***bucket,
237 DBusPreallocatedHash *preallocated);
238static DBusHashEntry* find_string_function (DBusHashTable *table,
239 void *key,
240 dbus_bool_t create_if_not_found,
241 DBusHashEntry ***bucket,
242 DBusPreallocatedHash *preallocated);
243static unsigned int string_hash (const char *str);
244static dbus_bool_t rebuild_table (DBusHashTable *table);
245static DBusHashEntry* alloc_entry (DBusHashTable *table);
246static void remove_entry (DBusHashTable *table,
247 DBusHashEntry **bucket,
248 DBusHashEntry *entry);
249static void free_entry (DBusHashTable *table,
250 DBusHashEntry *entry);
251static void free_entry_data (DBusHashTable *table,
252 DBusHashEntry *entry);
253
254
292 DBusFreeFunction key_free_function,
293 DBusFreeFunction value_free_function)
294{
295 DBusHashTable *table;
296 DBusMemPool *entry_pool;
297
298 table = dbus_new0 (DBusHashTable, 1);
299 if (table == NULL)
300 return NULL;
301
302 entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
303 if (entry_pool == NULL)
304 {
305 dbus_free (table);
306 return NULL;
307 }
308
309 table->refcount = 1;
310 table->entry_pool = entry_pool;
311
313
314 table->buckets = table->static_buckets;
316 table->n_entries = 0;
318 table->lo_rebuild_size = 0;
319 table->down_shift = 28;
320 table->mask = 3;
321 table->key_type = type;
322
323 _dbus_assert (table->mask < table->n_buckets);
324
325 switch (table->key_type)
326 {
327 case DBUS_HASH_INT:
329 table->find_function = find_direct_function;
330 break;
331 case DBUS_HASH_STRING:
332 table->find_function = find_string_function;
333 break;
334 default:
335 _dbus_assert_not_reached ("Unknown hash table type");
336 break;
337 }
338
339 table->free_key_function = key_free_function;
340 table->free_value_function = value_free_function;
341
342 return table;
343}
344
345
354{
355 table->refcount += 1;
356
357 return table;
358}
359
366void
368{
369 table->refcount -= 1;
370
371 if (table->refcount == 0)
372 {
373#if 0
374 DBusHashEntry *entry;
375 DBusHashEntry *next;
376 int i;
377
378 /* Free the entries in the table. */
379 for (i = 0; i < table->n_buckets; i++)
380 {
381 entry = table->buckets[i];
382 while (entry != NULL)
383 {
384 next = entry->next;
385
386 free_entry (table, entry);
387
388 entry = next;
389 }
390 }
391#else
392 DBusHashEntry *entry;
393 int i;
394
395 /* Free the entries in the table. */
396 for (i = 0; i < table->n_buckets; i++)
397 {
398 entry = table->buckets[i];
399 while (entry != NULL)
400 {
401 free_entry_data (table, entry);
402
403 entry = entry->next;
404 }
405 }
406 /* We can do this very quickly with memory pools ;-) */
408#endif
409
410 /* Free the bucket array, if it was dynamically allocated. */
411 if (table->buckets != table->static_buckets)
412 dbus_free (table->buckets);
413
414 dbus_free (table);
415 }
416}
417
423void
425{
426 DBusHashIter iter;
427 _dbus_hash_iter_init (table, &iter);
428 while (_dbus_hash_iter_next (&iter))
429 {
431 }
432}
433
434static DBusHashEntry*
435alloc_entry (DBusHashTable *table)
436{
437 DBusHashEntry *entry;
438
439 entry = _dbus_mem_pool_alloc (table->entry_pool);
440
441 return entry;
442}
443
444static void
445free_entry_data (DBusHashTable *table,
446 DBusHashEntry *entry)
447{
448 if (table->free_key_function)
449 (* table->free_key_function) (entry->key);
450 if (table->free_value_function)
451 (* table->free_value_function) (entry->value);
452}
453
454static void
455free_entry (DBusHashTable *table,
456 DBusHashEntry *entry)
457{
458 free_entry_data (table, entry);
459 _dbus_mem_pool_dealloc (table->entry_pool, entry);
460}
461
462static void
463remove_entry (DBusHashTable *table,
464 DBusHashEntry **bucket,
465 DBusHashEntry *entry)
466{
467 _dbus_assert (table != NULL);
468 _dbus_assert (bucket != NULL);
469 _dbus_assert (*bucket != NULL);
470 _dbus_assert (entry != NULL);
471
472 if (*bucket == entry)
473 *bucket = entry->next;
474 else
475 {
476 DBusHashEntry *prev;
477 prev = *bucket;
478
479 while (prev->next != entry)
480 prev = prev->next;
481
482 _dbus_assert (prev != NULL);
483
484 prev->next = entry->next;
485 }
486
487 table->n_entries -= 1;
488 free_entry (table, entry);
489}
490
522void
524 DBusHashIter *iter)
525{
526 DBusRealHashIter *real;
527
528 _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
529
530 real = (DBusRealHashIter*) iter;
531
532 real->table = table;
533 real->bucket = NULL;
534 real->entry = NULL;
535 real->next_entry = NULL;
536 real->next_bucket = 0;
537 real->n_entries_on_init = table->n_entries;
538}
539
550{
551 DBusRealHashIter *real;
552
553 _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
554
555 real = (DBusRealHashIter*) iter;
556
557 /* if this assertion failed someone probably added hash entries
558 * during iteration, which is bad.
559 */
561
562 /* Remember that real->entry may have been deleted */
563
564 while (real->next_entry == NULL)
565 {
566 if (real->next_bucket >= real->table->n_buckets)
567 {
568 /* invalidate iter and return false */
569 real->entry = NULL;
570 real->table = NULL;
571 real->bucket = NULL;
572 return FALSE;
573 }
574
575 real->bucket = &(real->table->buckets[real->next_bucket]);
576 real->next_entry = *(real->bucket);
577 real->next_bucket += 1;
578 }
579
580 _dbus_assert (real->next_entry != NULL);
581 _dbus_assert (real->bucket != NULL);
582
583 real->entry = real->next_entry;
584 real->next_entry = real->entry->next;
585
586 return TRUE;
587}
588
597void
599{
600 DBusRealHashIter *real;
601
602 real = (DBusRealHashIter*) iter;
603
604 _dbus_assert (real->table != NULL);
605 _dbus_assert (real->entry != NULL);
606 _dbus_assert (real->bucket != NULL);
607
608 remove_entry (real->table, real->bucket, real->entry);
609
610 real->entry = NULL; /* make it crash if you try to use this entry */
611}
612
618void*
620{
621 DBusRealHashIter *real;
622
623 real = (DBusRealHashIter*) iter;
624
625 _dbus_assert (real->table != NULL);
626 _dbus_assert (real->entry != NULL);
627
628 return real->entry->value;
629}
630
641void
643 void *value)
644{
645 DBusRealHashIter *real;
646
647 real = (DBusRealHashIter*) iter;
648
649 _dbus_assert (real->table != NULL);
650 _dbus_assert (real->entry != NULL);
651
652 if (real->table->free_value_function && value != real->entry->value)
653 (* real->table->free_value_function) (real->entry->value);
654
655 real->entry->value = value;
656}
657
664int
666{
667 DBusRealHashIter *real;
668
669 real = (DBusRealHashIter*) iter;
670
671 _dbus_assert (real->table != NULL);
672 _dbus_assert (real->entry != NULL);
673
674 return _DBUS_POINTER_TO_INT (real->entry->key);
675}
676
683uintptr_t
685{
686 DBusRealHashIter *real;
687
688 real = (DBusRealHashIter*) iter;
689
690 _dbus_assert (real->table != NULL);
691 _dbus_assert (real->entry != NULL);
692
693 return (uintptr_t) real->entry->key;
694}
695
701const char*
703{
704 DBusRealHashIter *real;
705
706 real = (DBusRealHashIter*) iter;
707
708 _dbus_assert (real->table != NULL);
709 _dbus_assert (real->entry != NULL);
710
711 return real->entry->key;
712}
713
748 void *key,
749 dbus_bool_t create_if_not_found,
750 DBusHashIter *iter)
751{
752 DBusRealHashIter *real;
753 DBusHashEntry *entry = NULL;
754 DBusHashEntry **bucket = NULL;
755
756 _DBUS_STATIC_ASSERT (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
757
758 real = (DBusRealHashIter*) iter;
759
760 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
761
762 /* entry == NULL means not found, and either !create_if_not_found or OOM */
763 if (entry == NULL)
764 return FALSE;
765
766 _dbus_assert (bucket != NULL);
767 _dbus_assert (table->n_buckets >= 1);
768 _dbus_assert (bucket >= table->buckets);
769 _dbus_assert (bucket <= &table->buckets[table->n_buckets - 1]);
770
771 if (create_if_not_found)
772 {
773 if (table->free_key_function && entry->key != key)
774 (* table->free_key_function) (entry->key);
775
776 entry->key = key;
777 }
778
779 real->table = table;
780 real->bucket = bucket;
781 real->entry = entry;
782 real->next_entry = entry->next;
783 real->next_bucket = (bucket - table->buckets) + 1;
784 real->n_entries_on_init = table->n_entries;
785
786 _dbus_assert (real->next_bucket >= 0);
787 _dbus_assert (real->next_bucket <= table->n_buckets);
788 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
789
790 return TRUE;
791}
792
793static void
794add_allocated_entry (DBusHashTable *table,
795 DBusHashEntry *entry,
796 unsigned int idx,
797 void *key,
798 DBusHashEntry ***bucket)
799{
800 DBusHashEntry **b;
801
802 entry->key = key;
803
804 b = &(table->buckets[idx]);
805 entry->next = *b;
806 *b = entry;
807
808 if (bucket)
809 *bucket = b;
810
811 table->n_entries += 1;
812
813 /* note we ONLY rebuild when ADDING - because you can iterate over a
814 * table and remove entries safely.
815 */
816 if (table->n_entries >= table->hi_rebuild_size ||
817 table->n_entries < table->lo_rebuild_size)
818 {
819 if (!rebuild_table (table))
820 return;
821
822 if (bucket)
823 {
824 /* Recalculate hash for the new table size */
825 switch (table->key_type)
826 {
827 case DBUS_HASH_STRING:
828 idx = string_hash (entry->key) & table->mask;
829 break;
830
831 case DBUS_HASH_INT:
833 idx = RANDOM_INDEX (table, entry->key);
834 break;
835
836 default:
837 idx = 0;
838 _dbus_assert_not_reached ("Unknown hash table type");
839 break;
840 }
841
842 *bucket = &(table->buckets[idx]);
843 }
844 }
845}
846
847static DBusHashEntry*
848add_entry (DBusHashTable *table,
849 unsigned int idx,
850 void *key,
851 DBusHashEntry ***bucket,
852 DBusPreallocatedHash *preallocated)
853{
854 DBusHashEntry *entry;
855
856 if (preallocated == NULL)
857 {
858 entry = alloc_entry (table);
859 if (entry == NULL)
860 {
861 if (bucket)
862 *bucket = NULL;
863 return NULL;
864 }
865 }
866 else
867 {
868 entry = (DBusHashEntry*) preallocated;
869 }
870
871 add_allocated_entry (table, entry, idx, key, bucket);
872 _dbus_assert (bucket == NULL || *bucket != NULL);
873
874 return entry;
875}
876
877/* This is g_str_hash from GLib which was
878 * extensively discussed/tested/profiled
879 */
880static unsigned int
881string_hash (const char *str)
882{
883 const char *p = str;
884 unsigned int h = *p;
885
886 if (h)
887 for (p += 1; *p != '\0'; p++)
888 h = (h << 5) - h + *p;
889
890 return h;
891}
892
894typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
895
896static DBusHashEntry*
897find_generic_function (DBusHashTable *table,
898 void *key,
899 unsigned int idx,
900 KeyCompareFunc compare_func,
901 dbus_bool_t create_if_not_found,
902 DBusHashEntry ***bucket,
903 DBusPreallocatedHash *preallocated)
904{
905 DBusHashEntry *entry;
906
907 if (bucket)
908 *bucket = NULL;
909
910 /* Search all of the entries in this bucket. */
911 entry = table->buckets[idx];
912 while (entry != NULL)
913 {
914 if ((compare_func == NULL && key == entry->key) ||
915 (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
916 {
917 if (bucket)
918 *bucket = &(table->buckets[idx]);
919
920 if (preallocated)
921 _dbus_hash_table_free_preallocated_entry (table, preallocated);
922
923 return entry;
924 }
925
926 entry = entry->next;
927 }
928
929 if (create_if_not_found)
930 {
931 entry = add_entry (table, idx, key, bucket, preallocated);
932
933 if (entry == NULL) /* OOM */
934 return NULL;
935
936 _dbus_assert (bucket == NULL || *bucket != NULL);
937 }
938 else if (preallocated)
939 {
940 _dbus_hash_table_free_preallocated_entry (table, preallocated);
941 }
942
943 return entry;
944}
945
946static DBusHashEntry*
947find_string_function (DBusHashTable *table,
948 void *key,
949 dbus_bool_t create_if_not_found,
950 DBusHashEntry ***bucket,
951 DBusPreallocatedHash *preallocated)
952{
953 unsigned int idx;
954
955 idx = string_hash (key) & table->mask;
956
957 return find_generic_function (table, key, idx,
958 (KeyCompareFunc) strcmp, create_if_not_found, bucket,
959 preallocated);
960}
961
962static DBusHashEntry*
963find_direct_function (DBusHashTable *table,
964 void *key,
965 dbus_bool_t create_if_not_found,
966 DBusHashEntry ***bucket,
967 DBusPreallocatedHash *preallocated)
968{
969 unsigned int idx;
970
971 idx = RANDOM_INDEX (table, key) & table->mask;
972
973
974 return find_generic_function (table, key, idx,
975 NULL, create_if_not_found, bucket,
976 preallocated);
977}
978
979/* Return FALSE if nothing happened. */
980static dbus_bool_t
981rebuild_table (DBusHashTable *table)
982{
983 int old_size;
984 int new_buckets;
985 DBusHashEntry **old_buckets;
986 DBusHashEntry **old_chain;
987 DBusHashEntry *entry;
988 dbus_bool_t growing;
989
990 /*
991 * Allocate and initialize the new bucket array, and set up
992 * hashing constants for new array size.
993 */
994
995 growing = table->n_entries >= table->hi_rebuild_size;
996
997 old_size = table->n_buckets;
998 old_buckets = table->buckets;
999
1000 if (growing)
1001 {
1002 /* overflow paranoia */
1003 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
1004 table->down_shift >= 2)
1005 new_buckets = table->n_buckets * 4;
1006 else
1007 return FALSE; /* can't grow any more */
1008 }
1009 else
1010 {
1011 new_buckets = table->n_buckets / 4;
1012 if (new_buckets < DBUS_SMALL_HASH_TABLE)
1013 return FALSE; /* don't bother shrinking this far */
1014 }
1015
1016 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
1017 if (table->buckets == NULL)
1018 {
1019 /* out of memory, yay - just don't reallocate, the table will
1020 * still work, albeit more slowly.
1021 */
1022 table->buckets = old_buckets;
1023 return FALSE;
1024 }
1025
1026 table->n_buckets = new_buckets;
1027
1028 if (growing)
1029 {
1030 table->lo_rebuild_size = table->hi_rebuild_size;
1031 table->hi_rebuild_size *= 4;
1032
1033 table->down_shift -= 2; /* keep 2 more high bits */
1034 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
1035 }
1036 else
1037 {
1038 table->hi_rebuild_size = table->lo_rebuild_size;
1039 table->lo_rebuild_size /= 4;
1040
1041 table->down_shift += 2; /* keep 2 fewer high bits */
1042 table->mask = table->mask >> 2; /* keep 2 fewer high bits */
1043 }
1044
1045#if 0
1046 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
1047 growing ? "GROW" : "SHRINK",
1048 table->lo_rebuild_size,
1049 table->hi_rebuild_size,
1050 table->down_shift,
1051 table->mask);
1052#endif
1053
1054 _dbus_assert (table->lo_rebuild_size >= 0);
1056 _dbus_assert (table->down_shift >= 0);
1057 _dbus_assert (table->mask != 0);
1058 /* the mask is essentially the max index */
1059 _dbus_assert (table->mask < table->n_buckets);
1060
1061 /*
1062 * Rehash all of the existing entries into the new bucket array.
1063 */
1064
1065 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1066 {
1067 for (entry = *old_chain; entry != NULL; entry = *old_chain)
1068 {
1069 unsigned int idx;
1070 DBusHashEntry **bucket;
1071
1072 *old_chain = entry->next;
1073 switch (table->key_type)
1074 {
1075 case DBUS_HASH_STRING:
1076 idx = string_hash (entry->key) & table->mask;
1077 break;
1078 case DBUS_HASH_INT:
1079 case DBUS_HASH_UINTPTR:
1080 idx = RANDOM_INDEX (table, entry->key);
1081 break;
1082 default:
1083 idx = 0;
1084 _dbus_assert_not_reached ("Unknown hash table type");
1085 break;
1086 }
1087
1088 bucket = &(table->buckets[idx]);
1089 entry->next = *bucket;
1090 *bucket = entry;
1091 }
1092 }
1093
1094 /* Free the old bucket array, if it was dynamically allocated. */
1095
1096 if (old_buckets != table->static_buckets)
1097 dbus_free (old_buckets);
1098
1099 return TRUE;
1100}
1101
1111void*
1113 const char *key)
1114{
1115 DBusHashEntry *entry;
1116
1118
1119 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1120
1121 if (entry)
1122 return entry->value;
1123 else
1124 return NULL;
1125}
1126
1136void*
1138 int key)
1139{
1140 DBusHashEntry *entry;
1141
1143
1144 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1145
1146 if (entry)
1147 return entry->value;
1148 else
1149 return NULL;
1150}
1151
1161void*
1163 uintptr_t key)
1164{
1165 DBusHashEntry *entry;
1166
1168
1169 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1170
1171 if (entry)
1172 return entry->value;
1173 else
1174 return NULL;
1175}
1176
1187 const char *key)
1188{
1189 DBusHashEntry *entry;
1190 DBusHashEntry **bucket;
1191
1193
1194 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1195
1196 if (entry)
1197 {
1198 remove_entry (table, bucket, entry);
1199 return TRUE;
1200 }
1201 else
1202 return FALSE;
1203}
1204
1215 int key)
1216{
1217 DBusHashEntry *entry;
1218 DBusHashEntry **bucket;
1219
1221
1222 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1223
1224 if (entry)
1225 {
1226 remove_entry (table, bucket, entry);
1227 return TRUE;
1228 }
1229 else
1230 return FALSE;
1231}
1232
1243 uintptr_t key)
1244{
1245 DBusHashEntry *entry;
1246 DBusHashEntry **bucket;
1247
1249
1250 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1251
1252 if (entry)
1253 {
1254 remove_entry (table, bucket, entry);
1255 return TRUE;
1256 }
1257 else
1258 return FALSE;
1259}
1260
1278 char *key,
1279 void *value)
1280{
1281 DBusPreallocatedHash *preallocated;
1282
1284
1285 preallocated = _dbus_hash_table_preallocate_entry (table);
1286 if (preallocated == NULL)
1287 return FALSE;
1288
1290 key, value);
1291
1292 return TRUE;
1293}
1294
1312 int key,
1313 void *value)
1314{
1315 DBusHashEntry *entry;
1316
1318
1319 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1320
1321 if (entry == NULL)
1322 return FALSE; /* no memory */
1323
1324 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1325 (* table->free_key_function) (entry->key);
1326
1327 if (table->free_value_function && entry->value != value)
1328 (* table->free_value_function) (entry->value);
1329
1330 entry->key = _DBUS_INT_TO_POINTER (key);
1331 entry->value = value;
1332
1333 return TRUE;
1334}
1335
1353 uintptr_t key,
1354 void *value)
1355{
1356 DBusHashEntry *entry;
1357
1359
1360 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1361
1362 if (entry == NULL)
1363 return FALSE; /* no memory */
1364
1365 if (table->free_key_function && entry->key != (void*) key)
1366 (* table->free_key_function) (entry->key);
1367
1368 if (table->free_value_function && entry->value != value)
1369 (* table->free_value_function) (entry->value);
1370
1371 entry->key = (void*) key;
1372 entry->value = value;
1373
1374 return TRUE;
1375}
1376
1386{
1387 DBusHashEntry *entry;
1388
1389 entry = alloc_entry (table);
1390
1391 return (DBusPreallocatedHash*) entry;
1392}
1393
1401void
1403 DBusPreallocatedHash *preallocated)
1404{
1405 DBusHashEntry *entry;
1406
1407 _dbus_assert (preallocated != NULL);
1408
1409 entry = (DBusHashEntry*) preallocated;
1410
1411 /* Don't use free_entry(), since this entry has no key/data */
1412 _dbus_mem_pool_dealloc (table->entry_pool, entry);
1413}
1414
1428void
1430 DBusPreallocatedHash *preallocated,
1431 char *key,
1432 void *value)
1433{
1434 DBusHashEntry *entry;
1435
1437 _dbus_assert (preallocated != NULL);
1438
1439 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1440
1441 _dbus_assert (entry != NULL);
1442
1443 if (table->free_key_function && entry->key != key)
1444 (* table->free_key_function) (entry->key);
1445
1446 if (table->free_value_function && entry->value != value)
1447 (* table->free_value_function) (entry->value);
1448
1449 entry->key = key;
1450 entry->value = value;
1451}
1452
1459int
1461{
1462 return table->n_entries;
1463}
1464
1478_dbus_hash_table_from_array (DBusHashTable *table, char **array, char delimiter)
1479{
1480 DBusString key;
1481 DBusString value;
1482 int i;
1483 dbus_bool_t retval = FALSE;
1484
1485 _dbus_assert (table != NULL);
1486 _dbus_assert (array != NULL);
1487
1488 if (!_dbus_string_init (&key))
1489 {
1490 return FALSE;
1491 }
1492
1493 if (!_dbus_string_init (&value))
1494 {
1495 _dbus_string_free (&key);
1496 return FALSE;
1497 }
1498
1499 for (i = 0; array[i] != NULL; i++)
1500 {
1501 if (!_dbus_string_append (&key, array[i]))
1502 break;
1503
1504 if (_dbus_string_split_on_byte (&key, delimiter, &value))
1505 {
1506 char *hash_key, *hash_value;
1507
1508 if (!_dbus_string_steal_data (&key, &hash_key))
1509 break;
1510
1511 if (!_dbus_string_steal_data (&value, &hash_value))
1512 break;
1513
1515 hash_key, hash_value))
1516 break;
1517 }
1518 _dbus_string_set_length (&key, 0);
1519 _dbus_string_set_length (&value, 0);
1520 }
1521
1522 if (array[i] != NULL)
1523 goto out;
1524
1525 retval = TRUE;
1526out:
1527
1528 _dbus_string_free (&key);
1529 _dbus_string_free (&value);
1530
1531 return retval;
1532}
1533
1542char **
1544{
1545 int i, length;
1546 DBusString entry;
1547 DBusHashIter iter;
1548 char **array;
1549
1550 _dbus_assert (table != NULL);
1551
1552 length = _dbus_hash_table_get_n_entries (table);
1553
1554 array = dbus_new0 (char *, length + 1);
1555
1556 if (array == NULL)
1557 return NULL;
1558
1559 i = 0;
1560 _dbus_hash_iter_init (table, &iter);
1561
1562 if (!_dbus_string_init (&entry))
1563 {
1564 dbus_free_string_array (array);
1565 return NULL;
1566 }
1567
1568 while (_dbus_hash_iter_next (&iter))
1569 {
1570 const char *key, *value;
1571
1572 key = (const char *) _dbus_hash_iter_get_string_key (&iter);
1573 value = (const char *) _dbus_hash_iter_get_value (&iter);
1574
1575 if (!_dbus_string_append_printf (&entry, "%s%c%s", key, delimiter, value))
1576 break;
1577
1578 if (!_dbus_string_steal_data (&entry, array + i))
1579 break;
1580 i++;
1581 }
1582
1583 _dbus_string_free (&entry);
1584
1585 if (i != length)
1586 {
1587 dbus_free_string_array (array);
1588 array = NULL;
1589 }
1590
1591 return array;
1592}
1593
#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:136
#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:110
#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:128
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:162
int _dbus_hash_table_get_n_entries(DBusHashTable *table)
Gets the number of hash entries in a hash table.
Definition: dbus-hash.c:1460
DBusHashTable * _dbus_hash_table_ref(DBusHashTable *table)
Increments the reference count for a hash table.
Definition: dbus-hash.c:353
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:1242
void * _dbus_hash_iter_get_value(DBusHashIter *iter)
Gets the value of the current entry.
Definition: dbus-hash.c:619
struct DBusPreallocatedHash DBusPreallocatedHash
A preallocated hash entry.
Definition: dbus-hash.h:148
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:1311
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:1277
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:1478
uintptr_t _dbus_hash_iter_get_uintptr_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:684
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:1162
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:367
int(* KeyCompareFunc)(const void *key_a, const void *key_b)
Key comparison function.
Definition: dbus-hash.c:894
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:549
int _dbus_hash_iter_get_int_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:665
void _dbus_hash_iter_init(DBusHashTable *table, DBusHashIter *iter)
Initializes a hash table iterator.
Definition: dbus-hash.c:523
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:1402
DBusHashTable * _dbus_hash_table_new(DBusHashType type, DBusFreeFunction key_free_function, DBusFreeFunction value_free_function)
Constructs a new hash table.
Definition: dbus-hash.c:291
dbus_bool_t _dbus_hash_table_remove_int(DBusHashTable *table, int key)
Removes the hash entry for the given key.
Definition: dbus-hash.c:1214
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:1385
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:1186
char ** _dbus_hash_table_to_array(DBusHashTable *table, char delimiter)
Creates a string array from a hash table.
Definition: dbus-hash.c:1543
void _dbus_hash_iter_set_value(DBusHashIter *iter, void *value)
Sets the value of the current entry.
Definition: dbus-hash.c:642
DBusHashType
Indicates the type of a key in the hash table.
Definition: dbus-hash.h:66
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:1112
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:747
void _dbus_hash_table_remove_all(DBusHashTable *table)
Removed all entries from a hash table.
Definition: dbus-hash.c:424
const char * _dbus_hash_iter_get_string_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:702
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:1352
void _dbus_hash_iter_remove_entry(DBusHashIter *iter)
Removes the current entry from the hash table.
Definition: dbus-hash.c:598
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:1429
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:1137
@ DBUS_HASH_INT
Hash keys are integers.
Definition: dbus-hash.h:68
@ DBUS_HASH_UINTPTR
Hash keys are integer capable to hold a pointer.
Definition: dbus-hash.h:69
@ DBUS_HASH_STRING
Hash keys are strings.
Definition: dbus-hash.h:67
#define _DBUS_INT_TO_POINTER(integer)
Safely stuffs an integer into a pointer, to be extracted later with _DBUS_POINTER_TO_INT.
#define _dbus_assert_not_reached(explanation)
Aborts with an error message if called.
#define _dbus_assert(condition)
Aborts with an error message if the condition is false.
#define _DBUS_INT_MAX
Maximum value of type "int".
#define _DBUS_POINTER_TO_INT(pointer)
Safely casts a void* to an integer; should only be used on void* that actually contain integers,...
#define _DBUS_N_ELEMENTS(array)
Computes the number of elements in a fixed-size array using sizeof().
#define NULL
A null pointer, defined appropriately for C or C++.
#define TRUE
Expands to "1".
#define FALSE
Expands to "0".
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition: dbus-mempool.c:225
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:364
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
Definition: dbus-mempool.c:198
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:146
void(* DBusFreeFunction)(void *memory)
The type of a function which frees a block of memory.
Definition: dbus-memory.h:63
void dbus_free(void *memory)
Frees a block of memory previously allocated by dbus_malloc() or dbus_malloc0().
Definition: dbus-memory.c:692
#define dbus_new0(type, count)
Safe macro for using dbus_malloc0().
Definition: dbus-memory.h:58
void dbus_free_string_array(char **str_array)
Frees a NULL-terminated array of strings.
Definition: dbus-memory.c:740
dbus_bool_t _dbus_string_set_length(DBusString *str, int length)
Sets the length of a string.
Definition: dbus-string.c:845
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:978
dbus_bool_t _dbus_string_init(DBusString *str)
Initializes a string.
Definition: dbus-string.c:180
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:684
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:1527
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:276
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:1145
dbus_uint32_t dbus_bool_t
A boolean, valid values are TRUE and FALSE.
Definition: dbus-types.h:35
Internal representation of a hash entry.
Definition: dbus-hash.c:150
void * value
Hash value.
Definition: dbus-hash.c:156
DBusHashEntry * next
Pointer to next entry in this hash bucket, or NULL for end of chain.
Definition: dbus-hash.c:151
void * key
Hash key.
Definition: dbus-hash.c:155
Hash iterator object.
Definition: dbus-hash.h:48
Internals of DBusHashTable.
Definition: dbus-hash.c:174
DBusHashEntry ** buckets
Pointer to bucket array.
Definition: dbus-hash.c:177
DBusHashType key_type
Type of keys used in this table.
Definition: dbus-hash.c:204
int hi_rebuild_size
Enlarge table when n_entries gets to be this large.
Definition: dbus-hash.c:191
int n_buckets
Total number of buckets allocated at **buckets.
Definition: dbus-hash.c:185
int down_shift
Shift count used in hashing function.
Definition: dbus-hash.c:197
DBusFreeFunction free_key_function
Function to free keys.
Definition: dbus-hash.c:209
int lo_rebuild_size
Shrink table when n_entries gets below this.
Definition: dbus-hash.c:194
DBusFindEntryFunction find_function
Function for finding entries.
Definition: dbus-hash.c:207
int refcount
Reference count.
Definition: dbus-hash.c:175
DBusMemPool * entry_pool
Memory pool for hash entries.
Definition: dbus-hash.c:212
int mask
Mask value used in hashing function.
Definition: dbus-hash.c:201
DBusHashEntry * static_buckets[DBUS_SMALL_HASH_TABLE]
Bucket array used for small tables (to avoid mallocs and frees).
Definition: dbus-hash.c:181
DBusFreeFunction free_value_function
Function to free values.
Definition: dbus-hash.c:210
int n_entries
Total number of entries present in table.
Definition: dbus-hash.c:188
Internals fields of DBusMemPool.
Definition: dbus-mempool.c:107
Internals of DBusHashIter.
Definition: dbus-hash.c:219
DBusHashTable * table
Pointer to table containing entry.
Definition: dbus-hash.c:220
DBusHashEntry * next_entry
Next entry to be iterated onto in current bucket.
Definition: dbus-hash.c:226
DBusHashEntry * entry
Current hash entry.
Definition: dbus-hash.c:225
int n_entries_on_init
used to detect table resize since initialization
Definition: dbus-hash.c:228
DBusHashEntry ** bucket
Pointer to bucket that points to first entry in this entry's chain: used for deleting the entry.
Definition: dbus-hash.c:221
int next_bucket
index of next bucket
Definition: dbus-hash.c:227