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_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(void)
  99 {
 100         unsigned int i, weight;
 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(36);
 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         weight = 0;
 125         for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
 126                 if (ht.common_mask & ((uintptr_t)1 << i)) {
 127                         weight++;
 128                 }
 129         }
 130         /* Only one bit should be clear. */
 131         ok1(weight == i-1);
 132
 133         /* Mask should be set. */
 134         ok1(check_mask(&ht, val, 1));
 135
 136         /* This should increase it again. */
 137         add_vals(&ht, val, 1, 1);
 138         ok1(ht.bits == 2);
 139         ok1(ht.max == 3);
 140
 141         /* Mask should be set. */
 142         ok1(ht.common_mask != 0);
 143         ok1(ht.common_mask != -1);
 144         ok1(check_mask(&ht, val, 2));
 145
 146         /* Now do the rest. */
 147         add_vals(&ht, val, 2, NUM_VALS - 2);
 148
 149         /* Find all. */
 150         find_vals(&ht, val, NUM_VALS);
 151         ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
 152
 153         /* Walk once, should get them all. */
 154         i = 0;
 155         for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
 156                 i++;
 157         ok1(i == NUM_VALS);
 158
 159         i = 0;
 160         for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
 161                 i++;
 162         ok1(i == NUM_VALS);
 163
 164         /* Delete all. */
 165         del_vals(&ht, val, NUM_VALS);
 166         ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
 167
 168         /* Worst case, a "pointer" which doesn't have any matching bits. */
 169         htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 170         htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
 171         ok1(ht.common_mask == 0);
 172         ok1(ht.common_bits == 0);
 173         /* Get rid of bogus pointer before we trip over it! */
 174         htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 175
 176         /* Add the rest. */
 177         add_vals(&ht, val, 0, NUM_VALS-1);
 178
 179         /* Check we can find them all. */
 180         find_vals(&ht, val, NUM_VALS);
 181         ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
 182
 183         /* Corner cases: wipe out the perfect bit using bogus pointer. */
 184         htable_clear(&ht);
 185         htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
 186         ok1(ht.perfect_bit);
 187         perfect_bit = ht.perfect_bit;
 188         htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
 189                                    | perfect_bit));
 190         ok1(ht.perfect_bit == 0);
 191         htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
 192
 193         /* Enlarging should restore it... */
 194         add_vals(&ht, val, 0, NUM_VALS-1);
 195
 196         ok1(ht.perfect_bit != 0);
 197         htable_clear(&ht);
 198
 199         ok1(htable_init_sized(&ht, hash, NULL, 1024));
 200         ok1(ht.max >= 1024);
 201         htable_clear(&ht);
 202
 203         ok1(htable_init_sized(&ht, hash, NULL, 1023));
 204         ok1(ht.max >= 1023);
 205         htable_clear(&ht);
 206
 207         ok1(htable_init_sized(&ht, hash, NULL, 1025));
 208         ok1(ht.max >= 1025);
 209         htable_clear(&ht);
 210
 211         return exit_status();
 212 }