git.ozlabs.org Git - ccan/blob - ccan/htable/test/run.c

   1 #include <ccan/htable/htable.h>
   2 #include <ccan/htable/htable.c>
   3 #include <ccan/tap/tap.h>
   4 #include <stdbool.h>
   5 #include <string.h>
   6
   7 #define NUM_VALS (1 << HTABLE_BASE_BITS)
   8
   9 /* We use the number divided by two as the hash (for lots of
  10    collisions), plus set all the higher bits so we can detect if they
  11    don't get masked out. */
  12 static size_t hash(const void *elem, void *unused)
  13 {
  14         size_t h = *(uint64_t *)elem / 2;
  15         h |= -1UL << HTABLE_BASE_BITS;
  16         return h;
  17 }
  18
  19 static bool objcmp(const void *htelem, void *cmpdata)
  20 {
  21         return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
  22 }
  23
  24 static void add_vals(struct htable *ht,
  25                      const uint64_t val[], unsigned int num)
  26 {
  27         uint64_t i;
  28
  29         for (i = 0; i < num; i++) {
  30                 if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
  31                         fail("%llu already in hash", (long long)i);
  32                         return;
  33                 }
  34                 htable_add(ht, hash(&val[i], NULL), &val[i]);
  35                 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
  36                         fail("%llu not added to hash", (long long)i);
  37                         return;
  38                 }
  39         }
  40         pass("Added %llu numbers to hash", (long long)i);
  41 }
  42
  43 #if 0
  44 static void refill_vals(struct htable *ht,
  45                         const uint64_t val[], unsigned int num)
  46 {
  47         uint64_t i;
  48
  49         for (i = 0; i < num; i++) {
  50                 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
  51                         continue;
  52                 htable_add(ht, hash(&val[i], NULL), &val[i]);
  53         }
  54 }
  55 #endif
  56
  57 static void find_vals(struct htable *ht,
  58                       const uint64_t val[], unsigned int num)
  59 {
  60         uint64_t i;
  61
  62         for (i = 0; i < num; i++) {
  63                 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
  64                         fail("%llu not found in hash", (long long)i);
  65                         return;
  66                 }
  67         }
  68         pass("Found %llu numbers in hash", (long long)i);
  69 }
  70
  71 static void del_vals(struct htable *ht,
  72                      const uint64_t val[], unsigned int num)
  73 {
  74         uint64_t i;
  75
  76         for (i = 0; i < num; i++) {
  77                 if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
  78                         fail("%llu not deleted from hash", (long long)i);
  79                         return;
  80                 }
  81         }
  82         pass("Deleted %llu numbers in hash", (long long)i);
  83 }
  84
  85 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
  86 {
  87         uint64_t i;
  88
  89         for (i = 0; i < num; i++) {
  90                 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
  91                         return false;
  92         }
  93         return true;
  94 }
  95
  96 int main(int argc, char *argv[])
  97 {
  98         unsigned int i;
  99         uintptr_t perfect_bit;
 100         struct htable *ht;
 101         uint64_t val[NUM_VALS];
 102         uint64_t dne;
 103         void *p;
 104         struct htable_iter iter;
 105
 106         plan_tests(23);
 107         for (i = 0; i < NUM_VALS; i++)
 108                 val[i] = i;
 109         dne = i;
 110
 111         ht = htable_new(hash, NULL);
 112         ok1(ht->max < (1 << ht->bits));
 113         ok1(ht->bits == HTABLE_BASE_BITS);
 114
 115         /* We cannot find an entry which doesn't exist. */
 116         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
 117
 118         /* Fill it, it should increase in size (once). */
 119         add_vals(ht, val, NUM_VALS);
 120         ok1(ht->bits == HTABLE_BASE_BITS + 1);
 121         ok1(ht->max < (1 << ht->bits));
 122
 123         /* Mask should be set. */
 124         ok1(ht->common_mask != 0);
 125         ok1(ht->common_mask != -1);
 126         ok1(check_mask(ht, val, NUM_VALS));
 127
 128         /* Find all. */
 129         find_vals(ht, val, NUM_VALS);
 130         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
 131
 132         /* Walk once, should get them all. */
 133         i = 0;
 134         for (p = htable_first(ht,&iter); p; p = htable_next(ht, &iter))
 135                 i++;
 136         ok1(i == NUM_VALS);
 137
 138         /* Delete all. */
 139         del_vals(ht, val, NUM_VALS);
 140         ok1(!htable_get(ht, hash(&val[0], NULL), objcmp, &val[0]));
 141
 142         /* Worst case, a "pointer" which doesn't have any matching bits. */
 143         htable_add(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 144         htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
 145         ok1(ht->common_mask == 0);
 146         ok1(ht->common_bits == 0);
 147         /* Get rid of bogus pointer before we trip over it! */
 148         htable_del(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 149
 150         /* Add the rest. */
 151         add_vals(ht, val, NUM_VALS-1);
 152
 153         /* Check we can find them all. */
 154         find_vals(ht, val, NUM_VALS);
 155         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
 156
 157         htable_free(ht);
 158
 159         /* Corner cases: wipe out the perfect bit using bogus pointer. */
 160         ht = htable_new(hash, NULL);
 161         htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
 162         ok1(ht->perfect_bit);
 163         perfect_bit = ht->perfect_bit;
 164         htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
 165                                    | perfect_bit));
 166         ok1(ht->perfect_bit == 0);
 167         htable_del(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
 168
 169         /* Enlarging should restore it... */
 170         add_vals(ht, val, NUM_VALS-1);
 171
 172         ok1(ht->perfect_bit != 0);
 173         htable_free(ht);
 174
 175         return exit_status();
 176 }