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