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         ok1(htable_obj_count(ht) == 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[] UNNEEDED, 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(void)
 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(32);
 120         for (i = 0; i < NUM_VALS; i++)
 121                 val[i].key = i;
 122         dne = i;
 123
 124         htable_obj_init(&ht);
 125         ok1(htable_obj_count(&ht) == 0);
 126         ok1(ht_max(&ht.raw) == 0);
 127         ok1(ht.raw.bits == 0);
 128
 129         /* We cannot find an entry which doesn't exist. */
 130         ok1(!htable_obj_get(&ht, &dne));
 131
 132         /* Fill it, it should increase in size. */
 133         add_vals(&ht, val, NUM_VALS);
 134         ok1(ht.raw.bits == NUM_BITS + 1);
 135         ok1(ht_max(&ht.raw) < (1 << ht.raw.bits));
 136
 137         /* Mask should be set. */
 138         ok1(ht.raw.common_mask != 0);
 139         ok1(ht.raw.common_mask != -1);
 140         ok1(check_mask(&ht.raw, val, NUM_VALS));
 141
 142         /* Find all. */
 143         find_vals(&ht, val, NUM_VALS);
 144         ok1(!htable_obj_get(&ht, &dne));
 145
 146         /* Walk once, should get them all. */
 147         i = 0;
 148         for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
 149                 i++;
 150         ok1(i == NUM_VALS);
 151         i = 0;
 152         for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
 153                 i++;
 154         ok1(i == NUM_VALS);
 155
 156         /* Delete all. */
 157         del_vals(&ht, val, NUM_VALS);
 158         ok1(!htable_obj_get(&ht, &val[0].key));
 159
 160         /* Worst case, a "pointer" which doesn't have any matching bits. */
 161         htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 162         htable_obj_add(&ht, &val[NUM_VALS-1]);
 163         ok1(ht.raw.common_mask == 0);
 164         ok1(ht.raw.common_bits == 0);
 165         /* Delete the bogus one before we trip over it. */
 166         htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 167
 168         /* Add the rest. */
 169         add_vals(&ht, val, NUM_VALS-1);
 170
 171         /* Check we can find them all. */
 172         find_vals(&ht, val, NUM_VALS);
 173         ok1(!htable_obj_get(&ht, &dne));
 174
 175         /* Check copy. */
 176         ok1(htable_obj_copy(&ht2, &ht));
 177
 178         /* Delete them all by key. */
 179         del_vals_bykey(&ht, val, NUM_VALS);
 180         del_vals_bykey(&ht2, val, NUM_VALS);
 181
 182         /* Write two of the same value. */
 183         val[1] = val[0];
 184         htable_obj_add(&ht, &val[0]);
 185         htable_obj_add(&ht, &val[1]);
 186         i = 0;
 187
 188         result = htable_obj_getfirst(&ht, &i, &iter);
 189         ok1(result == &val[0] || result == &val[1]);
 190         if (result == &val[0]) {
 191                 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]);
 192                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 193
 194                 /* Deleting first should make us iterate over the other. */
 195                 ok1(htable_obj_del(&ht, &val[0]));
 196                 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]);
 197                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 198         } else {
 199                 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]);
 200                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 201
 202                 /* Deleting first should make us iterate over the other. */
 203                 ok1(htable_obj_del(&ht, &val[1]));
 204                 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]);
 205                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 206         }
 207
 208         htable_obj_clear(&ht);
 209         ok1(htable_obj_count(&ht) == 0);
 210         htable_obj_clear(&ht2);
 211         ok1(htable_obj_count(&ht2) == 0);
 212         return exit_status();
 213 }