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