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, ht2;
 114         struct obj val[NUM_VALS], *result;
 115         unsigned int dne;
 116         void *p;
 117         struct htable_obj_iter iter;
 118
 119         plan_tests(29);
 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         i = 0;
 151         for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
 152                 i++;
 153         ok1(i == NUM_VALS);
 154
 155         /* Delete all. */
 156         del_vals(&ht, val, NUM_VALS);
 157         ok1(!htable_obj_get(&ht, &val[0].key));
 158
 159         /* Worst case, a "pointer" which doesn't have any matching bits. */
 160         htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 161         htable_obj_add(&ht, &val[NUM_VALS-1]);
 162         ok1(ht.raw.common_mask == 0);
 163         ok1(ht.raw.common_bits == 0);
 164         /* Delete the bogus one before we trip over it. */
 165         htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 166
 167         /* Add the rest. */
 168         add_vals(&ht, val, NUM_VALS-1);
 169
 170         /* Check we can find them all. */
 171         find_vals(&ht, val, NUM_VALS);
 172         ok1(!htable_obj_get(&ht, &dne));
 173
 174         /* Check copy. */
 175         ok1(htable_obj_copy(&ht2, &ht));
 176
 177         /* Delete them all by key. */
 178         del_vals_bykey(&ht, val, NUM_VALS);
 179         del_vals_bykey(&ht2, val, NUM_VALS);
 180
 181         /* Write two of the same value. */
 182         val[1] = val[0];
 183         htable_obj_add(&ht, &val[0]);
 184         htable_obj_add(&ht, &val[1]);
 185         i = 0;
 186
 187         result = htable_obj_getfirst(&ht, &i, &iter);
 188         ok1(result == &val[0] || result == &val[1]);
 189         if (result == &val[0]) {
 190                 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]);
 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[0]));
 195                 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]);
 196                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 197         } else {
 198                 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]);
 199                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 200
 201                 /* Deleting first should make us iterate over the other. */
 202                 ok1(htable_obj_del(&ht, &val[1]));
 203                 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]);
 204                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 205         }
 206
 207         htable_obj_clear(&ht);
 208         htable_obj_clear(&ht2);
 209         return exit_status();
 210 }