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