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(27);
 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         /* Delete them all by key. */
 175         del_vals_bykey(&ht, val, NUM_VALS);
 176
 177         /* Write two of the same value. */
 178         val[1] = val[0];
 179         htable_obj_add(&ht, &val[0]);
 180         htable_obj_add(&ht, &val[1]);
 181         i = 0;
 182
 183         result = htable_obj_getfirst(&ht, &i, &iter);
 184         ok1(result == &val[0] || result == &val[1]);
 185         if (result == &val[0]) {
 186                 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]);
 187                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 188
 189                 /* Deleting first should make us iterate over the other. */
 190                 ok1(htable_obj_del(&ht, &val[0]));
 191                 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]);
 192                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 193         } else {
 194                 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]);
 195                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 196
 197                 /* Deleting first should make us iterate over the other. */
 198                 ok1(htable_obj_del(&ht, &val[1]));
 199                 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]);
 200                 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
 201         }
 202
 203         htable_obj_clear(&ht);
 204         return exit_status();
 205 }