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