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

   1 #include <ccan/hashtable/hashtable.h>
   2 #include <ccan/hashtable/hashtable.c>
   3 #include <ccan/tap/tap.h>
   4 #include <stdbool.h>
   5 #include <string.h>
   6
   7 #define NUM_VALS (1 << HASHTABLE_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 unsigned long hash(const void *elem, void *unused)
  13 {
  14         unsigned long h = *(uint64_t *)elem / 2;
  15         h |= -1UL << HASHTABLE_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 hashtable *ht,
  25                      const uint64_t val[], unsigned int num)
  26 {
  27         uint64_t i;
  28
  29         for (i = 0; i < num; i++) {
  30                 if (hashtable_find(ht, hash(&i, NULL), objcmp, &i)) {
  31                         fail("%llu already in hash", (long long)i);
  32                         return;
  33                 }
  34                 hashtable_add(ht, hash(&val[i], NULL), &val[i]);
  35                 if (hashtable_find(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 static void refill_vals(struct hashtable *ht,
  44                         const uint64_t val[], unsigned int num)
  45 {
  46         uint64_t i;
  47
  48         for (i = 0; i < num; i++) {
  49                 if (hashtable_find(ht, hash(&i, NULL), objcmp, &i))
  50                         continue;
  51                 hashtable_add(ht, hash(&val[i], NULL), &val[i]);
  52         }
  53 }
  54
  55 static void find_vals(struct hashtable *ht,
  56                       const uint64_t val[], unsigned int num)
  57 {
  58         uint64_t i;
  59
  60         for (i = 0; i < num; i++) {
  61                 if (hashtable_find(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
  62                         fail("%llu not found in hash", (long long)i);
  63                         return;
  64                 }
  65         }
  66         pass("Found %llu numbers in hash", (long long)i);
  67 }
  68
  69 static void del_vals(struct hashtable *ht,
  70                      const uint64_t val[], unsigned int num)
  71 {
  72         uint64_t i;
  73
  74         for (i = 0; i < num; i++) {
  75                 if (!hashtable_del(ht, hash(&val[i], NULL), &val[i])) {
  76                         fail("%llu not deleted from hash", (long long)i);
  77                         return;
  78                 }
  79         }
  80         pass("Deleted %llu numbers in hash", (long long)i);
  81 }
  82
  83 struct travarg {
  84         unsigned int count;
  85         struct hashtable *ht;
  86         char touched[NUM_VALS];
  87         uint64_t *val;
  88 };
  89
  90 static bool count(void *p, void *cbarg)
  91 {
  92         struct travarg *travarg = cbarg;
  93         travarg->count++;
  94         travarg->touched[*(uint64_t *)p]++;
  95         return false;
  96 }
  97
  98 static bool delete_self(void *p, void *cbarg)
  99 {
 100         struct travarg *travarg = cbarg;
 101         uint64_t val = *(uint64_t *)p;
 102
 103         travarg->count++;
 104         travarg->touched[val]++;
 105         return !hashtable_del(travarg->ht, hash(p, NULL), p);
 106 }
 107
 108 static bool delete_next(void *p, void *cbarg)
 109 {
 110         struct travarg *travarg = cbarg;
 111         uint64_t val = *(uint64_t *)p;
 112         uint64_t *next = &travarg->val[(val + 1) % NUM_VALS];
 113
 114         travarg->count++;
 115         travarg->touched[val]++;
 116         return !hashtable_del(travarg->ht, hash(next, NULL), next);
 117 }
 118
 119 static bool delete_prev(void *p, void *cbarg)
 120 {
 121         struct travarg *travarg = cbarg;
 122         uint64_t val = *(uint64_t *)p;
 123         uint64_t *prev = &travarg->val[(val - 1) % NUM_VALS];
 124
 125         travarg->count++;
 126         travarg->touched[val]++;
 127         return !hashtable_del(travarg->ht, hash(prev, NULL), prev);
 128 }
 129
 130 static bool stop_halfway(void *p, void *cbarg)
 131 {
 132         struct travarg *travarg = cbarg;
 133         travarg->count++;
 134         travarg->touched[*(uint64_t *)p]++;
 135
 136         return (travarg->count == NUM_VALS / 2);
 137 }
 138
 139 static void check_all_touched_once(struct travarg *travarg)
 140 {
 141         unsigned int i;
 142
 143         for (i = 0; i < NUM_VALS; i++) {
 144                 if (travarg->touched[i] != 1) {
 145                         fail("Value %u touched %u times",
 146                              i, travarg->touched[i]);
 147                         return;
 148                 }
 149         }
 150         pass("All values touched once");
 151 }
 152
 153 static void check_only_touched_once(struct travarg *travarg)
 154 {
 155         unsigned int i;
 156
 157         for (i = 0; i < NUM_VALS; i++) {
 158                 if (travarg->touched[i] > 1) {
 159                         fail("Value %u touched multiple (%u) times",
 160                              i, travarg->touched[i]);
 161                         return;
 162                 }
 163         }
 164         pass("No value touched twice");
 165 }
 166
 167 int main(int argc, char *argv[])
 168 {
 169         unsigned int i;
 170         struct hashtable *ht;
 171         uint64_t val[NUM_VALS];
 172         struct travarg travarg;
 173         uint64_t dne;
 174
 175         plan_tests(20);
 176         for (i = 0; i < NUM_VALS; i++)
 177                 val[i] = i;
 178         dne = i;
 179
 180         ht = hashtable_new(hash, NULL);
 181         ok1(ht->max < (1 << ht->bits));
 182         ok1(ht->bits == HASHTABLE_BASE_BITS);
 183
 184         /* We cannot find an entry which doesn't exist. */
 185         ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
 186
 187         /* Fill it, it should increase in size (once). */
 188         add_vals(ht, val, NUM_VALS);
 189         ok1(ht->bits == HASHTABLE_BASE_BITS + 1);
 190         ok1(ht->max < (1 << ht->bits));
 191
 192         /* Find all. */
 193         find_vals(ht, val, NUM_VALS);
 194         ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
 195
 196         /* Delete all. */
 197         del_vals(ht, val, NUM_VALS);
 198         ok1(!hashtable_find(ht, hash(&val[0], NULL), objcmp, &val[0]));
 199
 200         /* Refill. */
 201         refill_vals(ht, val, NUM_VALS);
 202
 203         /* Traverse tests. */
 204         travarg.ht = ht;
 205         travarg.val = val;
 206         memset(travarg.touched, 0, sizeof(travarg.touched));
 207         travarg.count = 0;
 208
 209         /* Traverse. */
 210         hashtable_traverse(ht, count, &travarg);
 211         ok1(travarg.count == NUM_VALS);
 212         check_all_touched_once(&travarg);
 213
 214         memset(travarg.touched, 0, sizeof(travarg.touched));
 215         travarg.count = 0;
 216         hashtable_traverse(ht, stop_halfway, &travarg);
 217         ok1(travarg.count == NUM_VALS / 2);
 218         check_only_touched_once(&travarg);
 219
 220         memset(travarg.touched, 0, sizeof(travarg.touched));
 221         travarg.count = 0;
 222         i = 0;
 223         /* Delete until we make no more progress. */
 224         for (;;) {
 225                 hashtable_traverse(ht, delete_self, &travarg);
 226                 if (travarg.count == i || travarg.count > NUM_VALS)
 227                         break;
 228                 i = travarg.count;
 229         }
 230         ok1(travarg.count == NUM_VALS);
 231         check_all_touched_once(&travarg);
 232
 233         memset(travarg.touched, 0, sizeof(travarg.touched));
 234         travarg.count = 0;
 235         refill_vals(ht, val, NUM_VALS);
 236         hashtable_traverse(ht, delete_next, &travarg);
 237         ok1(travarg.count <= NUM_VALS);
 238         check_only_touched_once(&travarg);
 239
 240         memset(travarg.touched, 0, sizeof(travarg.touched));
 241         travarg.count = 0;
 242         refill_vals(ht, val, NUM_VALS);
 243         hashtable_traverse(ht, delete_prev, &travarg);
 244         ok1(travarg.count <= NUM_VALS);
 245         check_only_touched_once(&travarg);
 246
 247         return exit_status();
 248 }