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 void *htable_prev(const struct htable *ht, struct htable_iter *i)
 139 {
 140         for (;;) {
 141                 if (!i->off)
 142                         return NULL;
 143                 i->off --;
 144                 if (entry_is_valid(ht->table[i->off]))
 145                         return get_raw_ptr(ht, ht->table[i->off]);
 146         }
 147 }
 148
 149 /* This does not expand the hash table, that's up to caller. */
 150 static void ht_add(struct htable *ht, const void *new, size_t h)
 151 {
 152         size_t i;
 153         uintptr_t perfect = ht->perfect_bit;
 154
 155         i = hash_bucket(ht, h);
 156
 157         while (entry_is_valid(ht->table[i])) {
 158                 perfect = 0;
 159                 i = (i + 1) & ((1 << ht->bits)-1);
 160         }
 161         ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);
 162 }
 163
 164 static COLD bool double_table(struct htable *ht)
 165 {
 166         unsigned int i;
 167         size_t oldnum = (size_t)1 << ht->bits;
 168         uintptr_t *oldtable, e;
 169
 170         oldtable = ht->table;
 171         ht->table = calloc(1 << (ht->bits+1), sizeof(size_t));
 172         if (!ht->table) {
 173                 ht->table = oldtable;
 174                 return false;
 175         }
 176         ht->bits++;
 177         ht->max = ((size_t)3 << ht->bits) / 4;
 178         ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
 179
 180         /* If we lost our "perfect bit", get it back now. */
 181         if (!ht->perfect_bit && ht->common_mask) {
 182                 for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) {
 183                         if (ht->common_mask & ((size_t)1 << i)) {
 184                                 ht->perfect_bit = (size_t)1 << i;
 185                                 break;
 186                         }
 187                 }
 188         }
 189
 190         if (oldtable != &ht->perfect_bit) {
 191                 for (i = 0; i < oldnum; i++) {
 192                         if (entry_is_valid(e = oldtable[i])) {
 193                                 void *p = get_raw_ptr(ht, e);
 194                                 ht_add(ht, p, ht->rehash(p, ht->priv));
 195                         }
 196                 }
 197                 free(oldtable);
 198         }
 199         ht->deleted = 0;
 200         return true;
 201 }
 202
 203 static COLD void rehash_table(struct htable *ht)
 204 {
 205         size_t start, i;
 206         uintptr_t e;
 207
 208         /* Beware wrap cases: we need to start from first empty bucket. */
 209         for (start = 0; ht->table[start]; start++);
 210
 211         for (i = 0; i < (size_t)1 << ht->bits; i++) {
 212                 size_t h = (i + start) & ((1 << ht->bits)-1);
 213                 e = ht->table[h];
 214                 if (!e)
 215                         continue;
 216                 if (e == HTABLE_DELETED)
 217                         ht->table[h] = 0;
 218                 else if (!(e & ht->perfect_bit)) {
 219                         void *p = get_raw_ptr(ht, e);
 220                         ht->table[h] = 0;
 221                         ht_add(ht, p, ht->rehash(p, ht->priv));
 222                 }
 223         }
 224         ht->deleted = 0;
 225 }
 226
 227 /* We stole some bits, now we need to put them back... */
 228 static COLD void update_common(struct htable *ht, const void *p)
 229 {
 230         unsigned int i;
 231         uintptr_t maskdiff, bitsdiff;
 232
 233         if (ht->elems == 0) {
 234                 /* Always reveal one bit of the pointer in the bucket,
 235                  * so it's not zero or HTABLE_DELETED (1), even if
 236                  * hash happens to be 0.  Assumes (void *)1 is not a
 237                  * valid pointer. */
 238                 for (i = sizeof(uintptr_t)*CHAR_BIT - 1; i > 0; i--) {
 239                         if ((uintptr_t)p & ((uintptr_t)1 << i))
 240                                 break;
 241                 }
 242
 243                 ht->common_mask = ~((uintptr_t)1 << i);
 244                 ht->common_bits = ((uintptr_t)p & ht->common_mask);
 245                 ht->perfect_bit = 1;
 246                 return;
 247         }
 248
 249         /* Find bits which are unequal to old common set. */
 250         maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask);
 251
 252         /* These are the bits which go there in existing entries. */
 253         bitsdiff = ht->common_bits & maskdiff;
 254
 255         for (i = 0; i < (size_t)1 << ht->bits; i++) {
 256                 if (!entry_is_valid(ht->table[i]))
 257                         continue;
 258                 /* Clear the bits no longer in the mask, set them as
 259                  * expected. */
 260                 ht->table[i] &= ~maskdiff;
 261                 ht->table[i] |= bitsdiff;
 262         }
 263
 264         /* Take away those bits from our mask, bits and perfect bit. */
 265         ht->common_mask &= ~maskdiff;
 266         ht->common_bits &= ~maskdiff;
 267         ht->perfect_bit &= ~maskdiff;
 268 }
 269
 270 bool htable_add(struct htable *ht, size_t hash, const void *p)
 271 {
 272         if (ht->elems+1 > ht->max && !double_table(ht))
 273                 return false;
 274         if (ht->elems+1 + ht->deleted > ht->max_with_deleted)
 275                 rehash_table(ht);
 276         assert(p);
 277         if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
 278                 update_common(ht, p);
 279
 280         ht_add(ht, p, hash);
 281         ht->elems++;
 282         return true;
 283 }
 284
 285 bool htable_del(struct htable *ht, size_t h, const void *p)
 286 {
 287         struct htable_iter i;
 288         void *c;
 289
 290         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
 291                 if (c == p) {
 292                         htable_delval(ht, &i);
 293                         return true;
 294                 }
 295         }
 296         return false;
 297 }
 298
 299 void htable_delval(struct htable *ht, struct htable_iter *i)
 300 {
 301         assert(i->off < (size_t)1 << ht->bits);
 302         assert(entry_is_valid(ht->table[i->off]));
 303
 304         ht->elems--;
 305         ht->table[i->off] = HTABLE_DELETED;
 306         ht->deleted++;
 307 }