git.ozlabs.org Git - ccan/blob - ccan/hashtable/hashtable.c

   1 #include <ccan/hashtable/hashtable.h>
   2 #include <stdint.h>
   3 #include <stdlib.h>
   4 #include <assert.h>
   5
   6 /* This means a struct hashtable takes at least 512 bytes / 1k (32/64 bits). */
   7 #define HASHTABLE_BASE_BITS 7
   8
   9 /* We use 0x1 as deleted marker. */
  10 #define HASHTABLE_DELETED ((void *)0x1)
  11
  12 /* Number of redundant bits in a pointer. */
  13 #define PTR_STEAL_BITS 3
  14
  15 static inline uintptr_t get_extra_ptr_bits(const void *p)
  16 {
  17         return (uintptr_t)p & (((uintptr_t)1 << PTR_STEAL_BITS)-1);
  18 }
  19
  20 static inline void *get_raw_ptr(const void *p)
  21 {
  22         return (void *)((uintptr_t)p & ~(((uintptr_t)1 << PTR_STEAL_BITS)-1));
  23 }
  24
  25 static inline void *make_ptr(const void *p, uintptr_t bits)
  26 {
  27         return (void *)((uintptr_t)p | bits);
  28 }
  29
  30 struct hashtable {
  31         unsigned long (*rehash)(const void *elem, void *priv);
  32         void *priv;
  33         unsigned int bits;
  34         unsigned long elems, max;
  35         void **table;
  36 };
  37
  38 static inline bool ptr_is_valid(const void *e)
  39 {
  40         return e > HASHTABLE_DELETED;
  41 }
  42
  43 struct hashtable *hashtable_new(unsigned long (*rehash)(const void *elem,
  44                                                         void *priv),
  45                                 void *priv)
  46 {
  47         struct hashtable *ht = malloc(sizeof(struct hashtable));
  48         if (ht) {
  49                 ht->bits = HASHTABLE_BASE_BITS;
  50                 ht->rehash = rehash;
  51                 ht->priv = priv;
  52                 ht->elems = 0;
  53                 ht->max = (1 << ht->bits) * 3 / 4;
  54                 ht->table = calloc(1 << ht->bits, sizeof(void *));
  55                 if (!ht->table) {
  56                         free(ht);
  57                         ht = NULL;
  58                 }
  59         }
  60         return ht;
  61 }
  62
  63 void hashtable_free(struct hashtable *ht)
  64 {
  65         free(ht->table);
  66         free(ht);
  67 }
  68
  69 static unsigned long hash_bucket(const struct hashtable *ht,
  70                                  unsigned long h, unsigned long *ptrbits)
  71 {
  72         *ptrbits = (h >> ht->bits) & (((uintptr_t)1 << PTR_STEAL_BITS)-1);
  73         return h & ((1 << ht->bits)-1);
  74 }
  75
  76 /* This does not expand the hash table, that's up to caller. */
  77 static void ht_add(struct hashtable *ht, const void *new, unsigned long h)
  78 {
  79         unsigned long i, h2;
  80
  81         i = hash_bucket(ht, h, &h2);
  82
  83         while (ptr_is_valid(ht->table[i])) {
  84                 i = (i + 1) & ((1 << ht->bits)-1);
  85         }
  86         ht->table[i] = make_ptr(new, h2);
  87 }
  88
  89 static bool double_table(struct hashtable *ht)
  90 {
  91         unsigned int i;
  92         size_t oldnum = (size_t)1 << ht->bits;
  93         void **oldtable, *e;
  94
  95         oldtable = ht->table;
  96         ht->table = calloc(1 << (ht->bits+1), sizeof(void *));
  97         if (!ht->table) {
  98                 ht->table = oldtable;
  99                 return false;
 100         }
 101         ht->bits++;
 102         ht->max *= 2;
 103
 104         for (i = 0; i < oldnum; i++) {
 105                 if (ptr_is_valid(e = oldtable[i])) {
 106                         e = get_raw_ptr(e);
 107                         ht_add(ht, e, ht->rehash(e, ht->priv));
 108                 }
 109         }
 110         free(oldtable);
 111         return true;
 112 }
 113
 114 bool hashtable_add(struct hashtable *ht, unsigned long hash, const void *p)
 115 {
 116         if (ht->elems+1 > ht->max && !double_table(ht))
 117                 return false;
 118         ht->elems++;
 119         assert(p);
 120         assert(((uintptr_t)p & (((uintptr_t)1 << PTR_STEAL_BITS)-1)) == 0);
 121         ht_add(ht, p, hash);
 122         return true;
 123 }
 124
 125 /* Find bucket for an element. */
 126 static size_t ht_find(struct hashtable *ht,
 127                       unsigned long hash,
 128                       bool (*cmp)(const void *htelem, void *cmpdata),
 129                       void *cmpdata)
 130 {
 131         void *e;
 132         unsigned long i, h2;
 133
 134         i = hash_bucket(ht, hash, &h2);
 135
 136         while ((e = ht->table[i]) != NULL) {
 137                 if (e != HASHTABLE_DELETED
 138                     && h2 == get_extra_ptr_bits(e)
 139                     && cmp(get_raw_ptr(ht->table[i]), cmpdata))
 140                         return i;
 141                 i = (i + 1) & ((1 << ht->bits)-1);
 142         }
 143         return (size_t)-1;
 144 }
 145
 146
 147 /* If every one of the following buckets are DELETED (up to the next unused
 148    one), we can actually mark them all unused. */
 149 static void delete_run(struct hashtable *ht, unsigned int num)
 150 {
 151         unsigned int i, last = num + 1;
 152
 153         while (ht->table[last & ((1 << ht->bits)-1)]) {
 154                 if (ptr_is_valid(ht->table[last & ((1 << ht->bits)-1)]))
 155                         return;
 156                 last++;
 157         }
 158         for (i = num; i < last; i++)
 159                 ht->table[i & ((1 << ht->bits)-1)] = NULL;
 160 }
 161
 162 void *hashtable_find(struct hashtable *ht,
 163                      unsigned long hash,
 164                      bool (*cmp)(const void *htelem, void *cmpdata),
 165                      void *cmpdata)
 166 {
 167         size_t i = ht_find(ht, hash, cmp, cmpdata);
 168         if (i != (size_t)-1)
 169                 return get_raw_ptr(ht->table[i]);
 170         return NULL;
 171 }
 172
 173 static bool ptr_cmp(const void *htelem, void *cmpdata)
 174 {
 175         return htelem == cmpdata;
 176 }
 177
 178 bool hashtable_del(struct hashtable *ht, unsigned long hash, const void *p)
 179 {
 180         size_t i = ht_find(ht, hash, ptr_cmp, (void *)p);
 181         if (i == (size_t)-1)
 182                 return false;
 183
 184         ht->elems--;
 185         ht->table[i] = HASHTABLE_DELETED;
 186         delete_run(ht, i);
 187         return true;
 188 }
 189
 190 void _hashtable_traverse(struct hashtable *ht,
 191                          bool (*cb)(void *p, void *cbarg),
 192                          void *cbarg)
 193 {
 194         size_t i;
 195
 196         for (i = 0; i < (1 << ht->bits); i++) {
 197                 if (ptr_is_valid(ht->table[i]))
 198                         if (cb(get_raw_ptr(ht->table[i]), cbarg))
 199                                 return;
 200         }
 201 }