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