D-Bus  1.13.16
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 
162 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
163  void *key,
164  dbus_bool_t create_if_not_found,
165  DBusHashEntry ***bucket,
166  DBusPreallocatedHash *preallocated);
167 
175  int refcount;
185  int n_buckets;
188  int n_entries;
201  int mask;
213 };
214 
218 typedef struct
219 {
230 
231 _DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
232 
233 static DBusHashEntry* find_direct_function (DBusHashTable *table,
234  void *key,
235  dbus_bool_t create_if_not_found,
236  DBusHashEntry ***bucket,
237  DBusPreallocatedHash *preallocated);
238 static DBusHashEntry* find_string_function (DBusHashTable *table,
239  void *key,
240  dbus_bool_t create_if_not_found,
241  DBusHashEntry ***bucket,
242  DBusPreallocatedHash *preallocated);
243 static unsigned int string_hash (const char *str);
244 static dbus_bool_t rebuild_table (DBusHashTable *table);
245 static DBusHashEntry* alloc_entry (DBusHashTable *table);
246 static void remove_entry (DBusHashTable *table,
247  DBusHashEntry **bucket,
248  DBusHashEntry *entry);
249 static void free_entry (DBusHashTable *table,
250  DBusHashEntry *entry);
251 static 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:
328  case DBUS_HASH_UINTPTR:
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 
366 void
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 
423 void
425 {
426  DBusHashIter iter;
427  _dbus_hash_iter_init (table, &iter);
428  while (_dbus_hash_iter_next (&iter))
429  {
431  }
432 }
433 
434 static DBusHashEntry*
435 alloc_entry (DBusHashTable *table)
436 {
437  DBusHashEntry *entry;
438 
439  entry = _dbus_mem_pool_alloc (table->entry_pool);
440 
441  return entry;
442 }
443 
444 static void
445 free_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 
454 static void
455 free_entry (DBusHashTable *table,
456  DBusHashEntry *entry)
457 {
458  free_entry_data (table, entry);
459  _dbus_mem_pool_dealloc (table->entry_pool, entry);
460 }
461 
462 static void
463 remove_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 
522 void
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  */
560  _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
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 
597 void
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 
618 void*
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 
641 void
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 
664 int
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 
683 uintptr_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 
701 const 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 
793 static void
794 add_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:
832  case DBUS_HASH_UINTPTR:
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 
847 static DBusHashEntry*
848 add_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  */
880 static unsigned int
881 string_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 
894 typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
895 
896 static DBusHashEntry*
897 find_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 
946 static DBusHashEntry*
947 find_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 
962 static DBusHashEntry*
963 find_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. */
980 static dbus_bool_t
981 rebuild_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);
1055  _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
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 
1111 void*
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 
1136 void*
1138  int key)
1139 {
1140  DBusHashEntry *entry;
1141 
1142  _dbus_assert (table->key_type == DBUS_HASH_INT);
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 
1161 void*
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 
1220  _dbus_assert (table->key_type == DBUS_HASH_INT);
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 
1289  _dbus_hash_table_insert_string_preallocated (table, preallocated,
1290  key, value);
1291 
1292  return TRUE;
1293 }
1294 
1312  int key,
1313  void *value)
1314 {
1315  DBusHashEntry *entry;
1316 
1317  _dbus_assert (table->key_type == DBUS_HASH_INT);
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 
1401 void
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 
1428 void
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 
1459 int
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 
1514  if (!_dbus_hash_table_insert_string (table,
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;
1526 out:
1527 
1528  _dbus_string_free (&key);
1529  _dbus_string_free (&value);
1530 
1531  return retval;
1532 }
1533 
1542 char **
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 
DBusHashTable::free_value_function
DBusFreeFunction free_value_function
Function to free values.
Definition: dbus-hash.c:210
_dbus_hash_table_get_n_entries
int _dbus_hash_table_get_n_entries(DBusHashTable *table)
Gets the number of hash entries in a hash table.
Definition: dbus-hash.c:1460
_DBUS_N_ELEMENTS
#define _DBUS_N_ELEMENTS(array)
Definition: dbus-internals.h:189
_dbus_hash_table_insert_uintptr
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
_dbus_hash_table_to_array
char ** _dbus_hash_table_to_array(DBusHashTable *table, char delimiter)
Creates a string array from a hash table.
Definition: dbus-hash.c:1543
_dbus_hash_table_unref
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
DBusRealHashIter::next_entry
DBusHashEntry * next_entry
Next entry to be iterated onto in current bucket.
Definition: dbus-hash.c:226
_dbus_mem_pool_new
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:140
_dbus_hash_table_remove_int
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
DBusHashTable::n_buckets
int n_buckets
Total number of buckets allocated at **buckets.
Definition: dbus-hash.c:185
REBUILD_MULTIPLIER
#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
_dbus_string_free
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:271
DBusHashTable::static_buckets
DBusHashEntry * static_buckets[DBUS_SMALL_HASH_TABLE]
Bucket array used for small tables (to avoid mallocs and frees).
Definition: dbus-hash.c:181
_DBUS_INT_MAX
#define _DBUS_INT_MAX
Definition: dbus-internals.h:302
_dbus_hash_table_lookup_string
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_hash_table_lookup_int
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
@ DBUS_HASH_INT
Hash keys are integers.
Definition: dbus-hash.h:70
_dbus_hash_table_free_preallocated_entry
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
DBusHashEntry::next
DBusHashEntry * next
Pointer to next entry in this hash bucket, or NULL for end of chain.
Definition: dbus-hash.c:151
DBusFreeFunction
void(* DBusFreeFunction)(void *memory)
Definition: dbus-memory.h:63
DBusFindEntryFunction
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
DBusMemPool
Internals fields of DBusMemPool.
Definition: dbus-mempool.c:100
_dbus_hash_iter_get_uintptr_key
uintptr_t _dbus_hash_iter_get_uintptr_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:684
DBusHashTable::mask
int mask
Mask value used in hashing function.
Definition: dbus-hash.c:201
DBusHashTable::buckets
DBusHashEntry ** buckets
Pointer to bucket array.
Definition: dbus-hash.c:177
_dbus_hash_table_preallocate_entry
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_hash_iter_remove_entry
void _dbus_hash_iter_remove_entry(DBusHashIter *iter)
Removes the current entry from the hash table.
Definition: dbus-hash.c:598
_dbus_string_split_on_byte
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:1491
_dbus_string_init
dbus_bool_t _dbus_string_init(DBusString *str)
Initializes a string.
Definition: dbus-string.c:182
DBusHashTable::find_function
DBusFindEntryFunction find_function
Function for finding entries.
Definition: dbus-hash.c:207
_dbus_hash_table_new
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
TRUE
#define TRUE
DBusRealHashIter::entry
DBusHashEntry * entry
Current hash entry.
Definition: dbus-hash.c:225
DBusHashIter
Hash iterator object.
Definition: dbus-hash.h:49
DBUS_HASH_STRING
@ DBUS_HASH_STRING
Hash keys are strings.
Definition: dbus-hash.h:69
_dbus_hash_iter_set_value
void _dbus_hash_iter_set_value(DBusHashIter *iter, void *value)
Sets the value of the current entry.
Definition: dbus-hash.c:642
dbus_free
void dbus_free(void *memory)
Frees a block of memory previously allocated by dbus_malloc() or dbus_malloc0().
Definition: dbus-memory.c:704
DBusRealHashIter::n_entries_on_init
int n_entries_on_init
used to detect table resize since initialization
Definition: dbus-hash.c:228
RANDOM_INDEX
#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
_DBUS_INT_TO_POINTER
#define _DBUS_INT_TO_POINTER(integer)
Definition: dbus-internals.h:192
DBusHashEntry
Internal representation of a hash entry.
Definition: dbus-hash.c:149
_dbus_hash_iter_next
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
DBusString
Definition: dbus-string.h:42
DBusHashType
DBusHashType
Definition: dbus-hash.h:67
_dbus_hash_table_insert_int
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_string_append_printf
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:1138
DBUS_SMALL_HASH_TABLE
#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
_dbus_hash_iter_lookup
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
DBusHashTable::free_key_function
DBusFreeFunction free_key_function
Function to free keys.
Definition: dbus-hash.c:209
DBusHashTable::entry_pool
DBusMemPool * entry_pool
Memory pool for hash entries.
Definition: dbus-hash.c:212
FALSE
#define FALSE
DBusHashTable::n_entries
int n_entries
Total number of entries present in table.
Definition: dbus-hash.c:188
_dbus_hash_iter_get_int_key
int _dbus_hash_iter_get_int_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:665
_dbus_hash_table_remove_all
void _dbus_hash_table_remove_all(DBusHashTable *table)
Removed all entries from a hash table.
Definition: dbus-hash.c:424
DBusHashEntry::value
void * value
Hash value.
Definition: dbus-hash.c:156
_dbus_mem_pool_dealloc
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:349
_dbus_hash_table_lookup_uintptr
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
DBusRealHashIter::next_bucket
int next_bucket
index of next bucket
Definition: dbus-hash.c:227
_dbus_mem_pool_free
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
Definition: dbus-mempool.c:189
DBUS_HASH_UINTPTR
@ DBUS_HASH_UINTPTR
Hash keys are integer capable to hold a pointer.
Definition: dbus-hash.h:71
DBusHashTable::down_shift
int down_shift
Shift count used in hashing function.
Definition: dbus-hash.c:197
DBusHashTable
Internals of DBusHashTable.
Definition: dbus-hash.c:174
_dbus_assert_not_reached
#define _dbus_assert_not_reached(explanation)
Definition: dbus-internals.h:164
_dbus_string_set_length
dbus_bool_t _dbus_string_set_length(DBusString *str, int length)
Sets the length of a string.
Definition: dbus-string.c:826
DBusHashEntry::key
void * key
Hash key.
Definition: dbus-hash.c:155
DBusRealHashIter
Internals of DBusHashIter.
Definition: dbus-hash.c:218
DBusHashTable::key_type
DBusHashType key_type
Type of keys used in this table.
Definition: dbus-hash.c:204
_dbus_assert
#define _dbus_assert(condition)
Definition: dbus-internals.h:153
_DBUS_POINTER_TO_INT
#define _DBUS_POINTER_TO_INT(pointer)
Definition: dbus-internals.h:191
DBusRealHashIter::table
DBusHashTable * table
Pointer to table containing entry.
Definition: dbus-hash.c:220
_dbus_hash_iter_get_string_key
const char * _dbus_hash_iter_get_string_key(DBusHashIter *iter)
Gets the key for the current entry.
Definition: dbus-hash.c:702
_dbus_hash_table_from_array
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
_dbus_hash_iter_get_value
void * _dbus_hash_iter_get_value(DBusHashIter *iter)
Gets the value of the current entry.
Definition: dbus-hash.c:619
_dbus_hash_table_remove_uintptr
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
_dbus_hash_table_insert_string_preallocated
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
KeyCompareFunc
int(* KeyCompareFunc)(const void *key_a, const void *key_b)
Key comparison function.
Definition: dbus-hash.c:894
dbus_free_string_array
void dbus_free_string_array(char **str_array)
Frees a NULL-terminated array of strings.
Definition: dbus-memory.c:752
_dbus_hash_table_ref
DBusHashTable * _dbus_hash_table_ref(DBusHashTable *table)
Increments the reference count for a hash table.
Definition: dbus-hash.c:353
_dbus_string_steal_data
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:665
DBusHashTable::refcount
int refcount
Reference count.
Definition: dbus-hash.c:175
DBusRealHashIter::bucket
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
_dbus_mem_pool_alloc
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition: dbus-mempool.c:216
DBusPreallocatedHash
struct DBusPreallocatedHash DBusPreallocatedHash
A preallocated hash entry.
Definition: dbus-hash.h:150
DBusHashTable::lo_rebuild_size
int lo_rebuild_size
Shrink table when n_entries gets below this.
Definition: dbus-hash.c:194
dbus_new0
#define dbus_new0(type, count)
Definition: dbus-memory.h:58
_dbus_hash_iter_init
void _dbus_hash_iter_init(DBusHashTable *table, DBusHashIter *iter)
Initializes a hash table iterator.
Definition: dbus-hash.c:523
_dbus_hash_table_insert_string
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_string_append
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:959
DBusHashTable::hi_rebuild_size
int hi_rebuild_size
Enlarge table when n_entries gets to be this large.
Definition: dbus-hash.c:191
_dbus_hash_table_remove_string
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
dbus_bool_t
dbus_uint32_t dbus_bool_t
Definition: dbus-types.h:35
NULL
#define NULL