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, htable_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], *result;
 115         unsigned int dne;
 116         void *p;
 117         struct htable_obj_iter iter;
 118
 119         plan_tests(26);
 120         for (i = 0; i < NUM_VALS; i++)
 121                 val[i].key = i;
 122         dne = i;
 123
 124         htable_obj_init(&ht);
 125         ok1(ht.raw.max == 0);
 126         ok1(ht.raw.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(ht.raw.bits == NUM_BITS + 1);
 134         ok1(ht.raw.max < (1 << ht.raw.bits));
 135
 136         /* Mask should be set. */
 137         ok1(ht.raw.common_mask != 0);
 138         ok1(ht.raw.common_mask != -1);
 139         ok1(check_mask(&ht.raw, 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(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 157         htable_obj_add(&ht, &val[NUM_VALS-1]);
 158         ok1(ht.raw.common_mask == 0);
 159         ok1(ht.raw.common_bits == 0);
 160         /* Delete the bogus one before we trip over it. */
 161         htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 162
 163         /* Add the rest. */
 164         add_vals(&ht, val, NUM_VALS-1);
 165
 166         /* Check we can find them all. */
 167         find_vals(&ht, val, NUM_VALS);
 168         ok1(!htable_obj_get(&ht, &dne));
 169
 170         /* Delete them all by key. */
 171         del_vals_bykey(&ht, val, NUM_VALS);
 172
 173         /* Write two of the same value. */
 174         val[1] = val[0];
 175         htable_obj_add(&ht, &val[0]);
 176         htable_obj_add(&ht, &val[1]);
 177         i = 0;
 178
 179         result = htable_obj_getfirst(&ht, &i, &iter);
 180         ok1(result == &val[0] || result == &val[1]);
 181         if (result == &val[0]) {
 182                 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]);
 183                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 184
 185                 /* Deleting first should make us iterate over the other. */
 186                 ok1(htable_obj_del(&ht, &val[0]));
 187                 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]);
 188                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 189         } else {
 190                 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]);
 191                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 192
 193                 /* Deleting first should make us iterate over the other. */
 194                 ok1(htable_obj_del(&ht, &val[1]));
 195                 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]);
 196                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 197         }
 198
 199         htable_obj_clear(&ht);
 200         return exit_status();
 201 }