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, struct travarg *travarg)
  91 {
  92         travarg->count++;
  93         travarg->touched[*(uint64_t *)p]++;
  94         return false;
  95 }
  96
  97 static bool delete_self(uint64_t *p, struct travarg *travarg)
  98 {
  99         travarg->count++;
 100         travarg->touched[*p]++;
 101         return !hashtable_del(travarg->ht, hash(p, NULL), p);
 102 }
 103
 104 static bool delete_next(uint64_t *p, struct travarg *travarg)
 105 {
 106         uint64_t *next = &travarg->val[((*p) + 1) % NUM_VALS];
 107
 108         travarg->count++;
 109         travarg->touched[*p]++;
 110         return !hashtable_del(travarg->ht, hash(next, NULL), next);
 111 }
 112
 113 static bool delete_prev(uint64_t *p, struct travarg *travarg)
 114 {
 115         uint64_t *prev = &travarg->val[((*p) - 1) % NUM_VALS];
 116
 117         travarg->count++;
 118         travarg->touched[*p]++;
 119         return !hashtable_del(travarg->ht, hash(prev, NULL), prev);
 120 }
 121
 122 static bool stop_halfway(void *p, struct travarg *travarg)
 123 {
 124         travarg->count++;
 125         travarg->touched[*(uint64_t *)p]++;
 126
 127         return (travarg->count == NUM_VALS / 2);
 128 }
 129
 130 static void check_all_touched_once(struct travarg *travarg)
 131 {
 132         unsigned int i;
 133
 134         for (i = 0; i < NUM_VALS; i++) {
 135                 if (travarg->touched[i] != 1) {
 136                         fail("Value %u touched %u times",
 137                              i, travarg->touched[i]);
 138                         return;
 139                 }
 140         }
 141         pass("All values touched once");
 142 }
 143
 144 static void check_only_touched_once(struct travarg *travarg)
 145 {
 146         unsigned int i;
 147
 148         for (i = 0; i < NUM_VALS; i++) {
 149                 if (travarg->touched[i] > 1) {
 150                         fail("Value %u touched multiple (%u) times",
 151                              i, travarg->touched[i]);
 152                         return;
 153                 }
 154         }
 155         pass("No value touched twice");
 156 }
 157
 158 int main(int argc, char *argv[])
 159 {
 160         unsigned int i;
 161         struct hashtable *ht;
 162         uint64_t val[NUM_VALS];
 163         struct travarg travarg;
 164         uint64_t dne;
 165
 166         plan_tests(20);
 167         for (i = 0; i < NUM_VALS; i++)
 168                 val[i] = i;
 169         dne = i;
 170
 171         ht = hashtable_new(hash, NULL);
 172         ok1(ht->max < (1 << ht->bits));
 173         ok1(ht->bits == HASHTABLE_BASE_BITS);
 174
 175         /* We cannot find an entry which doesn't exist. */
 176         ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
 177
 178         /* Fill it, it should increase in size (once). */
 179         add_vals(ht, val, NUM_VALS);
 180         ok1(ht->bits == HASHTABLE_BASE_BITS + 1);
 181         ok1(ht->max < (1 << ht->bits));
 182
 183         /* Find all. */
 184         find_vals(ht, val, NUM_VALS);
 185         ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
 186
 187         /* Delete all. */
 188         del_vals(ht, val, NUM_VALS);
 189         ok1(!hashtable_find(ht, hash(&val[0], NULL), objcmp, &val[0]));
 190
 191         /* Refill. */
 192         refill_vals(ht, val, NUM_VALS);
 193
 194         /* Traverse tests. */
 195         travarg.ht = ht;
 196         travarg.val = val;
 197         memset(travarg.touched, 0, sizeof(travarg.touched));
 198         travarg.count = 0;
 199
 200         /* Traverse. */
 201         hashtable_traverse(ht, void, count, &travarg);
 202         ok1(travarg.count == NUM_VALS);
 203         check_all_touched_once(&travarg);
 204
 205         memset(travarg.touched, 0, sizeof(travarg.touched));
 206         travarg.count = 0;
 207         hashtable_traverse(ht, void, stop_halfway, &travarg);
 208         ok1(travarg.count == NUM_VALS / 2);
 209         check_only_touched_once(&travarg);
 210
 211         memset(travarg.touched, 0, sizeof(travarg.touched));
 212         travarg.count = 0;
 213         i = 0;
 214         /* Delete until we make no more progress. */
 215         for (;;) {
 216                 hashtable_traverse(ht, uint64_t, delete_self, &travarg);
 217                 if (travarg.count == i || travarg.count > NUM_VALS)
 218                         break;
 219                 i = travarg.count;
 220         }
 221         ok1(travarg.count == NUM_VALS);
 222         check_all_touched_once(&travarg);
 223
 224         memset(travarg.touched, 0, sizeof(travarg.touched));
 225         travarg.count = 0;
 226         refill_vals(ht, val, NUM_VALS);
 227         hashtable_traverse(ht, uint64_t, delete_next, &travarg);
 228         ok1(travarg.count <= NUM_VALS);
 229         check_only_touched_once(&travarg);
 230
 231         memset(travarg.touched, 0, sizeof(travarg.touched));
 232         travarg.count = 0;
 233         refill_vals(ht, val, NUM_VALS);
 234         hashtable_traverse(ht, uint64_t, delete_prev, &travarg);
 235         ok1(travarg.count <= NUM_VALS);
 236         check_only_touched_once(&travarg);
 237
 238         return exit_status();
 239 }