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