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

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