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_VALS (1 << HTABLE_BASE_BITS)
   8
   9 /* We use the number divided by two as the hash (for lots of
  10    collisions), plus set all the higher bits so we can detect if they
  11    don't get masked out. */
  12 static size_t hash(const void *elem, void *unused)
  13 {
  14         size_t h = *(uint64_t *)elem / 2;
  15         h |= -1UL << HTABLE_BASE_BITS;
  16         return h;
  17 }
  18
  19 static bool objcmp(const void *htelem, void *cmpdata)
  20 {
  21         return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
  22 }
  23
  24 static void add_vals(struct htable *ht,
  25                      const uint64_t val[], unsigned int num)
  26 {
  27         uint64_t i;
  28
  29         for (i = 0; i < num; i++) {
  30                 if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
  31                         fail("%llu already in hash", (long long)i);
  32                         return;
  33                 }
  34                 htable_add(ht, hash(&val[i], NULL), &val[i]);
  35                 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
  36                         fail("%llu not added to hash", (long long)i);
  37                         return;
  38                 }
  39         }
  40         pass("Added %llu numbers to hash", (long long)i);
  41 }
  42
  43 #if 0
  44 static void refill_vals(struct htable *ht,
  45                         const uint64_t val[], unsigned int num)
  46 {
  47         uint64_t i;
  48
  49         for (i = 0; i < num; i++) {
  50                 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
  51                         continue;
  52                 htable_add(ht, hash(&val[i], NULL), &val[i]);
  53         }
  54 }
  55 #endif
  56
  57 static void find_vals(struct htable *ht,
  58                       const uint64_t val[], unsigned int num)
  59 {
  60         uint64_t i;
  61
  62         for (i = 0; i < num; i++) {
  63                 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
  64                         fail("%llu not found in hash", (long long)i);
  65                         return;
  66                 }
  67         }
  68         pass("Found %llu numbers in hash", (long long)i);
  69 }
  70
  71 static void del_vals(struct htable *ht,
  72                      const uint64_t val[], unsigned int num)
  73 {
  74         uint64_t i;
  75
  76         for (i = 0; i < num; i++) {
  77                 if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
  78                         fail("%llu not deleted from hash", (long long)i);
  79                         return;
  80                 }
  81         }
  82         pass("Deleted %llu numbers in hash", (long long)i);
  83 }
  84
  85 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
  86 {
  87         uint64_t i;
  88
  89         for (i = 0; i < num; i++) {
  90                 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
  91                         return false;
  92         }
  93         return true;
  94 }
  95
  96 int main(int argc, char *argv[])
  97 {
  98         unsigned int i;
  99         struct htable *ht;
 100         uint64_t val[NUM_VALS];
 101         uint64_t dne;
 102         void *p;
 103         struct htable_iter iter;
 104
 105         plan_tests(19);
 106         for (i = 0; i < NUM_VALS; i++)
 107                 val[i] = i;
 108         dne = i;
 109
 110         ht = htable_new(hash, NULL);
 111         ok1(ht->max < (1 << ht->bits));
 112         ok1(ht->bits == HTABLE_BASE_BITS);
 113
 114         /* We cannot find an entry which doesn't exist. */
 115         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
 116
 117         /* Fill it, it should increase in size (once). */
 118         add_vals(ht, val, NUM_VALS);
 119         ok1(ht->bits == HTABLE_BASE_BITS + 1);
 120         ok1(ht->max < (1 << ht->bits));
 121
 122         /* Mask should be set. */
 123         ok1(ht->common_mask != 0);
 124         ok1(ht->common_mask != -1);
 125         ok1(check_mask(ht, val, NUM_VALS));
 126
 127         /* Find all. */
 128         find_vals(ht, val, NUM_VALS);
 129         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
 130
 131         /* Walk once, should get them all. */
 132         i = 0;
 133         for (p = htable_first(ht,&iter); p; p = htable_next(ht, &iter))
 134                 i++;
 135         ok1(i == NUM_VALS);
 136
 137         /* Delete all. */
 138         del_vals(ht, val, NUM_VALS);
 139         ok1(!htable_get(ht, hash(&val[0], NULL), objcmp, &val[0]));
 140
 141         /* Worst case, a "pointer" which doesn't have any matching bits. */
 142         htable_add(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 143         htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
 144         ok1(ht->common_mask == 0);
 145         ok1(ht->common_bits == 0);
 146
 147         /* Add the rest. */
 148         add_vals(ht, val, NUM_VALS-1);
 149
 150         /* Check we can find them all. */
 151         find_vals(ht, val, NUM_VALS);
 152         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
 153
 154         return exit_status();
 155 }