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