git.ozlabs.org Git - ccan/blob - ccan/htable/test/run-type-int.c

   1 /* Key is an unsigned int, not a pointer. */
   2 #include "config.h"
   3 #if !defined(HAVE_TYPEOF) || !HAVE_TYPEOF
   4 #define HTABLE_KTYPE(keyof, type) unsigned int
   5 #endif
   6 #include <ccan/htable/htable_type.h>
   7 #include <ccan/htable/htable.c>
   8 #include <ccan/tap/tap.h>
   9 #include <stdbool.h>
  10 #include <string.h>
  11
  12 #define NUM_BITS 7
  13 #define NUM_VALS (1 << NUM_BITS)
  14
  15 struct obj {
  16         /* Makes sure we don't try to treat and obj as a key or vice versa */
  17         unsigned char unused;
  18         unsigned int key;
  19 };
  20
  21 static const unsigned int objkey(const struct obj *obj)
  22 {
  23         return obj->key;
  24 }
  25
  26 /* We use the number divided by two as the hash (for lots of
  27    collisions), plus set all the higher bits so we can detect if they
  28    don't get masked out. */
  29 static size_t objhash(const unsigned int key)
  30 {
  31         size_t h = key / 2;
  32         h |= -1UL << NUM_BITS;
  33         return h;
  34 }
  35
  36 static bool cmp(const struct obj *obj, const unsigned int key)
  37 {
  38         return obj->key == key;
  39 }
  40
  41 HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj);
  42
  43 static void add_vals(struct htable_obj *ht,
  44                      struct obj val[], unsigned int num)
  45 {
  46         unsigned int i;
  47
  48         for (i = 0; i < num; i++) {
  49                 if (htable_obj_get(ht, i)) {
  50                         fail("%u already in hash", i);
  51                         return;
  52                 }
  53                 htable_obj_add(ht, &val[i]);
  54                 if (htable_obj_get(ht, i) != &val[i]) {
  55                         fail("%u not added to hash", i);
  56                         return;
  57                 }
  58         }
  59         pass("Added %u numbers to hash", i);
  60 }
  61
  62 static void find_vals(const struct htable_obj *ht,
  63                       const struct obj val[], unsigned int num)
  64 {
  65         unsigned int i;
  66
  67         for (i = 0; i < num; i++) {
  68                 if (htable_obj_get(ht, i) != &val[i]) {
  69                         fail("%u not found in hash", i);
  70                         return;
  71                 }
  72         }
  73         pass("Found %u numbers in hash", i);
  74 }
  75
  76 static void del_vals(struct htable_obj *ht,
  77                      const struct obj val[], unsigned int num)
  78 {
  79         unsigned int i;
  80
  81         for (i = 0; i < num; i++) {
  82                 if (!htable_obj_delkey(ht, val[i].key)) {
  83                         fail("%u not deleted from hash", i);
  84                         return;
  85                 }
  86         }
  87         pass("Deleted %u numbers in hash", i);
  88 }
  89
  90 static void del_vals_bykey(struct htable_obj *ht,
  91                            const struct obj val[] UNNEEDED, unsigned int num)
  92 {
  93         unsigned int i;
  94
  95         for (i = 0; i < num; i++) {
  96                 if (!htable_obj_delkey(ht, i)) {
  97                         fail("%u not deleted by key from hash", i);
  98                         return;
  99                 }
 100         }
 101         pass("Deleted %u numbers by key from hash", i);
 102 }
 103
 104 static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
 105 {
 106         uint64_t i;
 107
 108         for (i = 0; i < num; i++) {
 109                 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
 110                         return false;
 111         }
 112         return true;
 113 }
 114
 115 int main(void)
 116 {
 117         unsigned int i;
 118         struct htable_obj ht, ht2;
 119         struct obj val[NUM_VALS], *result;
 120         unsigned int dne;
 121         void *p;
 122         struct htable_obj_iter iter;
 123
 124         plan_tests(29);
 125         for (i = 0; i < NUM_VALS; i++)
 126                 val[i].key = i;
 127         dne = i;
 128
 129         htable_obj_init(&ht);
 130         ok1(ht.raw.max == 0);
 131         ok1(ht.raw.bits == 0);
 132
 133         /* We cannot find an entry which doesn't exist. */
 134         ok1(!htable_obj_get(&ht, dne));
 135
 136         /* Fill it, it should increase in size. */
 137         add_vals(&ht, val, NUM_VALS);
 138         ok1(ht.raw.bits == NUM_BITS + 1);
 139         ok1(ht.raw.max < (1 << ht.raw.bits));
 140
 141         /* Mask should be set. */
 142         ok1(ht.raw.common_mask != 0);
 143         ok1(ht.raw.common_mask != -1);
 144         ok1(check_mask(&ht.raw, val, NUM_VALS));
 145
 146         /* Find all. */
 147         find_vals(&ht, val, NUM_VALS);
 148         ok1(!htable_obj_get(&ht, dne));
 149
 150         /* Walk once, should get them all. */
 151         i = 0;
 152         for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
 153                 i++;
 154         ok1(i == NUM_VALS);
 155         i = 0;
 156         for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
 157                 i++;
 158         ok1(i == NUM_VALS);
 159
 160         /* Delete all. */
 161         del_vals(&ht, val, NUM_VALS);
 162         ok1(!htable_obj_get(&ht, val[0].key));
 163
 164         /* Worst case, a "pointer" which doesn't have any matching bits. */
 165         htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 166         htable_obj_add(&ht, &val[NUM_VALS-1]);
 167         ok1(ht.raw.common_mask == 0);
 168         ok1(ht.raw.common_bits == 0);
 169         /* Delete the bogus one before we trip over it. */
 170         htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
 171
 172         /* Add the rest. */
 173         add_vals(&ht, val, NUM_VALS-1);
 174
 175         /* Check we can find them all. */
 176         find_vals(&ht, val, NUM_VALS);
 177         ok1(!htable_obj_get(&ht, dne));
 178
 179         /* Check copy. */
 180         ok1(htable_obj_copy(&ht2, &ht));
 181
 182         /* Delete them all by key. */
 183         del_vals_bykey(&ht, val, NUM_VALS);
 184         del_vals_bykey(&ht2, val, NUM_VALS);
 185
 186         /* Write two of the same value. */
 187         val[1] = val[0];
 188         htable_obj_add(&ht, &val[0]);
 189         htable_obj_add(&ht, &val[1]);
 190         i = 0;
 191
 192         result = htable_obj_getfirst(&ht, i, &iter);
 193         ok1(result == &val[0] || result == &val[1]);
 194         if (result == &val[0]) {
 195                 ok1(htable_obj_getnext(&ht, i, &iter) == &val[1]);
 196                 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
 197
 198                 /* Deleting first should make us iterate over the other. */
 199                 ok1(htable_obj_del(&ht, &val[0]));
 200                 ok1(htable_obj_getfirst(&ht, i, &iter) == &val[1]);
 201                 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
 202         } else {
 203                 ok1(htable_obj_getnext(&ht, i, &iter) == &val[0]);
 204                 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
 205
 206                 /* Deleting first should make us iterate over the other. */
 207                 ok1(htable_obj_del(&ht, &val[1]));
 208                 ok1(htable_obj_getfirst(&ht, i, &iter) == &val[0]);
 209                 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
 210         }
 211
 212         htable_obj_clear(&ht);
 213         htable_obj_clear(&ht2);
 214         return exit_status();
 215 }