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