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