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