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