lib/ccan/htable/htable.c

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #include <ccan/htable/htable.h>
   3 #include <ccan/compiler/compiler.h>
   4 #include <stdint.h>
   5 #include <stdlib.h>
   6 #include <limits.h>
   7 #include <stdbool.h>
   8 #include <assert.h>
   9
  10 /* This means a struct htable takes at least 512 bytes / 1k (32/64 bits). */
  11 #define HTABLE_BASE_BITS 7
  12
  13 /* We use 0x1 as deleted marker. */
  14 #define HTABLE_DELETED (0x1)
  15
  16 struct htable {
  17         size_t (*rehash)(const void *elem, void *priv);
  18         void *priv;
  19         unsigned int bits;
  20         size_t elems, deleted, max, max_with_deleted;
  21         /* These are the bits which are the same in all pointers. */
  22         uintptr_t common_mask, common_bits;
  23         uintptr_t perfect_bit;
  24         uintptr_t *table;
  25 };
  26
  27 /* We clear out the bits which are always the same, and put metadata there. */
  28 static inline uintptr_t get_extra_ptr_bits(const struct htable *ht,
  29                                            uintptr_t e)
  30 {
  31         return e & ht->common_mask;
  32 }
  33
  34 static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e)
  35 {
  36         return (void *)((e & ~ht->common_mask) | ht->common_bits);
  37 }
  38
  39 static inline uintptr_t make_hval(const struct htable *ht,
  40                                   const void *p, uintptr_t bits)
  41 {
  42         return ((uintptr_t)p & ~ht->common_mask) | bits;
  43 }
  44
  45 static inline bool entry_is_valid(uintptr_t e)
  46 {
  47         return e > HTABLE_DELETED;
  48 }
  49
  50 static inline uintptr_t get_hash_ptr_bits(const struct htable *ht,
  51                                           size_t hash)
  52 {
  53         /* Shuffling the extra bits (as specified in mask) down the
  54          * end is quite expensive.  But the lower bits are redundant, so
  55          * we fold the value first. */
  56         return (hash ^ (hash >> ht->bits))
  57                 & ht->common_mask & ~ht->perfect_bit;
  58 }
  59
  60 struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
  61                           void *priv)
  62 {
  63         struct htable *ht = malloc(sizeof(struct htable));
  64         if (ht) {
  65                 ht->bits = HTABLE_BASE_BITS;
  66                 ht->rehash = rehash;
  67                 ht->priv = priv;
  68                 ht->elems = 0;
  69                 ht->deleted = 0;
  70                 ht->max = ((size_t)1 << ht->bits) * 3 / 4;
  71                 ht->max_with_deleted = ((size_t)1 << ht->bits) * 9 / 10;
  72                 /* This guarantees we enter update_common first add. */
  73                 ht->common_mask = -1;
  74                 ht->common_bits = 0;
  75                 ht->perfect_bit = 0;
  76                 ht->table = calloc(1 << ht->bits, sizeof(uintptr_t));
  77                 if (!ht->table) {
  78                         free(ht);
  79                         ht = NULL;
  80                 }
  81         }
  82         return ht;
  83 }
  84
  85 void htable_free(const struct htable *ht)
  86 {
  87         free((void *)ht->table);
  88         free((void *)ht);
  89 }
  90
  91 static size_t hash_bucket(const struct htable *ht, size_t h)
  92 {
  93         return h & ((1 << ht->bits)-1);
  94 }
  95
  96 static void *htable_val(const struct htable *ht,
  97                         struct htable_iter *i, size_t hash, uintptr_t perfect)
  98 {
  99         uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect;
 100
 101         while (ht->table[i->off]) {
 102                 if (ht->table[i->off] != HTABLE_DELETED) {
 103                         if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2)
 104                                 return get_raw_ptr(ht, ht->table[i->off]);
 105                 }
 106                 i->off = (i->off + 1) & ((1 << ht->bits)-1);
 107                 h2 &= ~perfect;
 108         }
 109         return NULL;
 110 }
 111
 112 void *htable_firstval(const struct htable *ht,
 113                       struct htable_iter *i, size_t hash)
 114 {
 115         i->off = hash_bucket(ht, hash);
 116         return htable_val(ht, i, hash, ht->perfect_bit);
 117 }
 118
 119 void *htable_nextval(const struct htable *ht,
 120                      struct htable_iter *i, size_t hash)
 121 {
 122         i->off = (i->off + 1) & ((1 << ht->bits)-1);
 123         return htable_val(ht, i, hash, 0);
 124 }
 125
 126 void *htable_first(const struct htable *ht, struct htable_iter *i)
 127 {
 128         for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) {
 129                 if (entry_is_valid(ht->table[i->off]))
 130                         return get_raw_ptr(ht, ht->table[i->off]);
 131         }
 132         return NULL;
 133 }
 134
 135 void *htable_next(const struct htable *ht, struct htable_iter *i)
 136 {
 137         for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) {
 138                 if (entry_is_valid(ht->table[i->off]))
 139                         return get_raw_ptr(ht, ht->table[i->off]);
 140         }
 141         return NULL;
 142 }
 143
 144 /* This does not expand the hash table, that's up to caller. */
 145 static void ht_add(struct htable *ht, const void *new, size_t h)
 146 {
 147         size_t i;
 148         uintptr_t perfect = ht->perfect_bit;
 149
 150         i = hash_bucket(ht, h);
 151
 152         while (entry_is_valid(ht->table[i])) {
 153                 perfect = 0;
 154                 i = (i + 1) & ((1 << ht->bits)-1);
 155         }
 156         ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);
 157 }
 158
 159 static COLD bool double_table(struct htable *ht)
 160 {
 161         unsigned int i;
 162         size_t oldnum = (size_t)1 << ht->bits;
 163         uintptr_t *oldtable, e;
 164
 165         oldtable = ht->table;
 166         ht->table = calloc(1 << (ht->bits+1), sizeof(size_t));
 167         if (!ht->table) {
 168                 ht->table = oldtable;
 169                 return false;
 170         }
 171         ht->bits++;
 172         ht->max *= 2;
 173         ht->max_with_deleted *= 2;
 174
 175         /* If we lost our "perfect bit", get it back now. */
 176         if (!ht->perfect_bit && ht->common_mask) {
 177                 for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) {
 178                         if (ht->common_mask & ((size_t)1 << i)) {
 179                                 ht->perfect_bit = (size_t)1 << i;
 180                                 break;
 181                         }
 182                 }
 183         }
 184
 185         for (i = 0; i < oldnum; i++) {
 186                 if (entry_is_valid(e = oldtable[i])) {
 187                         void *p = get_raw_ptr(ht, e);
 188                         ht_add(ht, p, ht->rehash(p, ht->priv));
 189                 }
 190         }
 191         ht->deleted = 0;
 192         free(oldtable);
 193         return true;
 194 }
 195
 196 static COLD void rehash_table(struct htable *ht)
 197 {
 198         size_t start, i;
 199         uintptr_t e;
 200
 201         /* Beware wrap cases: we need to start from first empty bucket. */
 202         for (start = 0; ht->table[start]; start++);
 203
 204         for (i = 0; i < (size_t)1 << ht->bits; i++) {
 205                 size_t h = (i + start) & ((1 << ht->bits)-1);
 206                 e = ht->table[h];
 207                 if (!e)
 208                         continue;
 209                 if (e == HTABLE_DELETED)
 210                         ht->table[h] = 0;
 211                 else if (!(e & ht->perfect_bit)) {
 212                         void *p = get_raw_ptr(ht, e);
 213                         ht->table[h] = 0;
 214                         ht_add(ht, p, ht->rehash(p, ht->priv));
 215                 }
 216         }
 217         ht->deleted = 0;
 218 }
 219
 220 /* We stole some bits, now we need to put them back... */
 221 static COLD void update_common(struct htable *ht, const void *p)
 222 {
 223         unsigned int i;
 224         uintptr_t maskdiff, bitsdiff;
 225
 226         if (ht->elems == 0) {
 227                 ht->common_mask = -1;
 228                 ht->common_bits = (uintptr_t)p;
 229                 ht->perfect_bit = 1;
 230                 return;
 231         }
 232
 233         /* Find bits which are unequal to old common set. */
 234         maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask);
 235
 236         /* These are the bits which go there in existing entries. */
 237         bitsdiff = ht->common_bits & maskdiff;
 238
 239         for (i = 0; i < (size_t)1 << ht->bits; i++) {
 240                 if (!entry_is_valid(ht->table[i]))
 241                         continue;
 242                 /* Clear the bits no longer in the mask, set them as
 243                  * expected. */
 244                 ht->table[i] &= ~maskdiff;
 245                 ht->table[i] |= bitsdiff;
 246         }
 247
 248         /* Take away those bits from our mask, bits and perfect bit. */
 249         ht->common_mask &= ~maskdiff;
 250         ht->common_bits &= ~maskdiff;
 251         ht->perfect_bit &= ~maskdiff;
 252 }
 253
 254 bool htable_add(struct htable *ht, size_t hash, const void *p)
 255 {
 256         if (ht->elems+1 > ht->max && !double_table(ht))
 257                 return false;
 258         if (ht->elems+1 + ht->deleted > ht->max_with_deleted)
 259                 rehash_table(ht);
 260         assert(p);
 261         if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
 262                 update_common(ht, p);
 263
 264         ht_add(ht, p, hash);
 265         ht->elems++;
 266         return true;
 267 }
 268
 269 bool htable_del(struct htable *ht, size_t h, const void *p)
 270 {
 271         struct htable_iter i;
 272         void *c;
 273
 274         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
 275                 if (c == p) {
 276                         htable_delval(ht, &i);
 277                         return true;
 278                 }
 279         }
 280         return false;
 281 }
 282
 283 void htable_delval(struct htable *ht, struct htable_iter *i)
 284 {
 285         assert(i->off < (size_t)1 << ht->bits);
 286         assert(entry_is_valid(ht->table[i->off]));
 287
 288         ht->elems--;
 289         ht->table[i->off] = HTABLE_DELETED;
 290         ht->deleted++;
 291 }