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

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