tests/test-hmap.c

   1 /* A non-exhaustive test for some of the functions and macros declared in
   2  * hmap.h. */
   3
   4 #include <config.h>
   5 #include "hmap.h"
   6 #include <string.h>
   7 #include "hash.h"
   8 #include "util.h"
   9
  10 #undef NDEBUG
  11 #include <assert.h>
  12
  13 /* Sample hmap element. */
  14 struct element {
  15     int value;
  16     struct hmap_node node;
  17 };
  18
  19 typedef size_t hash_func(int value);
  20
  21 static int
  22 compare_ints(const void *a_, const void *b_)
  23 {
  24     const int *a = a_;
  25     const int *b = b_;
  26     return *a < *b ? -1 : *a > *b;
  27 }
  28
  29 /* Verifies that 'hmap' contains exactly the 'n' values in 'values'. */
  30 static void
  31 check_hmap(struct hmap *hmap, const int values[], size_t n,
  32            hash_func *hash)
  33 {
  34     int *sort_values, *hmap_values;
  35     struct element *e;
  36     size_t i;
  37
  38     /* Check that all the values are there in iteration. */
  39     sort_values = xmalloc(sizeof *sort_values * n);
  40     hmap_values = xmalloc(sizeof *sort_values * n);
  41
  42     i = 0;
  43     HMAP_FOR_EACH (e, struct element, node, hmap) {
  44         assert(i < n);
  45         hmap_values[i++] = e->value;
  46     }
  47     assert(i == n);
  48
  49     memcpy(sort_values, values, sizeof *sort_values * n);
  50     qsort(sort_values, n, sizeof *sort_values, compare_ints);
  51     qsort(hmap_values, n, sizeof *hmap_values, compare_ints);
  52
  53     for (i = 0; i < n; i++) {
  54         assert(sort_values[i] == hmap_values[i]);
  55     }
  56
  57     free(hmap_values);
  58     free(sort_values);
  59
  60     /* Check that all the values are there in lookup. */
  61     for (i = 0; i < n; i++) {
  62         size_t count = 0;
  63
  64         HMAP_FOR_EACH_WITH_HASH (e, struct element, node,
  65                                  hash(values[i]), hmap) {
  66             count += e->value == values[i];
  67         }
  68         assert(count == 1);
  69     }
  70
  71     /* Check counters. */
  72     assert(hmap_is_empty(hmap) == !n);
  73     assert(hmap_count(hmap) == n);
  74 }
  75
  76 /* Puts the 'n' values in 'values' into 'elements', and then puts those
  77  * elements into 'hmap'. */
  78 static void
  79 make_hmap(struct hmap *hmap, struct element elements[],
  80           int values[], size_t n, hash_func *hash)
  81 {
  82     size_t i;
  83
  84     hmap_init(hmap);
  85     for (i = 0; i < n; i++) {
  86         elements[i].value = i;
  87         hmap_insert(hmap, &elements[i].node, hash(elements[i].value));
  88         values[i] = i;
  89     }
  90 }
  91
  92 static void
  93 shuffle(int *p, size_t n)
  94 {
  95     for (; n > 1; n--, p++) {
  96         int *q = &p[rand() % n];
  97         int tmp = *p;
  98         *p = *q;
  99         *q = tmp;
 100     }
 101 }
 102
 103 #if 0
 104 /* Prints the values in 'hmap', plus 'name' as a title. */
 105 static void
 106 print_hmap(const char *name, struct hmap *hmap)
 107 {
 108     struct element *e;
 109
 110     printf("%s:", name);
 111     HMAP_FOR_EACH (e, struct element, node, hmap) {
 112         printf(" %d(%zu)", e->value, e->node.hash & hmap->mask);
 113     }
 114     printf("\n");
 115 }
 116
 117 /* Prints the 'n' values in 'values', plus 'name' as a title. */
 118 static void
 119 print_ints(const char *name, const int *values, size_t n)
 120 {
 121     size_t i;
 122
 123     printf("%s:", name);
 124     for (i = 0; i < n; i++) {
 125         printf(" %d", values[i]);
 126     }
 127     printf("\n");
 128 }
 129 #endif
 130
 131 static size_t
 132 identity_hash(int value)
 133 {
 134     return value;
 135 }
 136
 137 static size_t
 138 good_hash(int value)
 139 {
 140     return hash_int(value, 0x1234abcd);
 141 }
 142
 143 static size_t
 144 constant_hash(int value UNUSED)
 145 {
 146     return 123;
 147 }
 148
 149 /* Tests basic hmap insertion and deletion. */
 150 static void
 151 test_hmap_insert_delete(hash_func *hash)
 152 {
 153     enum { N_ELEMS = 100 };
 154
 155     struct element elements[N_ELEMS];
 156     int values[N_ELEMS];
 157     struct hmap hmap;
 158     size_t i;
 159
 160     hmap_init(&hmap);
 161     for (i = 0; i < N_ELEMS; i++) {
 162         elements[i].value = i;
 163         hmap_insert(&hmap, &elements[i].node, hash(i));
 164         values[i] = i;
 165         check_hmap(&hmap, values, i + 1, hash);
 166     }
 167     shuffle(values, N_ELEMS);
 168     for (i = 0; i < N_ELEMS; i++) {
 169         hmap_remove(&hmap, &elements[values[i]].node);
 170         check_hmap(&hmap, values + (i + 1), N_ELEMS - (i + 1), hash);
 171     }
 172     hmap_destroy(&hmap);
 173 }
 174
 175 /* Tests basic hmap_reserve() and hmap_shrink(). */
 176 static void
 177 test_hmap_reserve_shrink(hash_func *hash)
 178 {
 179     enum { N_ELEMS = 32 };
 180
 181     size_t i;
 182
 183     for (i = 0; i < N_ELEMS; i++) {
 184         struct element elements[N_ELEMS];
 185         int values[N_ELEMS];
 186         struct hmap hmap;
 187         size_t j;
 188
 189         hmap_init(&hmap);
 190         hmap_reserve(&hmap, i);
 191         for (j = 0; j < N_ELEMS; j++) {
 192             elements[j].value = j;
 193             hmap_insert(&hmap, &elements[j].node, hash(j));
 194             values[j] = j;
 195             check_hmap(&hmap, values, j + 1, hash);
 196         }
 197         shuffle(values, N_ELEMS);
 198         for (j = 0; j < N_ELEMS; j++) {
 199             hmap_remove(&hmap, &elements[values[j]].node);
 200             hmap_shrink(&hmap);
 201             check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash);
 202         }
 203         hmap_destroy(&hmap);
 204     }
 205 }
 206
 207 /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
 208  * element of a hmap.  */
 209 static void
 210 test_hmap_for_each_safe(hash_func *hash)
 211 {
 212     enum { MAX_ELEMS = 10 };
 213     size_t n;
 214     unsigned long int pattern;
 215
 216     for (n = 0; n <= MAX_ELEMS; n++) {
 217         for (pattern = 0; pattern < 1ul << n; pattern++) {
 218             struct element elements[MAX_ELEMS];
 219             int values[MAX_ELEMS];
 220             struct hmap hmap;
 221             struct element *e, *next;
 222             size_t n_remaining;
 223             int i;
 224
 225             make_hmap(&hmap, elements, values, n, hash);
 226
 227             i = 0;
 228             n_remaining = n;
 229             HMAP_FOR_EACH_SAFE (e, next, struct element, node, &hmap) {
 230                 assert(i < n);
 231                 if (pattern & (1ul << e->value)) {
 232                     size_t j;
 233                     hmap_remove(&hmap, &e->node);
 234                     for (j = 0; ; j++) {
 235                         assert(j < n_remaining);
 236                         if (values[j] == e->value) {
 237                             values[j] = values[--n_remaining];
 238                             break;
 239                         }
 240                     }
 241                 }
 242                 check_hmap(&hmap, values, n_remaining, hash);
 243                 i++;
 244             }
 245             assert(i == n);
 246
 247             for (i = 0; i < n; i++) {
 248                 if (pattern & (1ul << i)) {
 249                     n_remaining++;
 250                 }
 251             }
 252             assert(n == n_remaining);
 253
 254             hmap_destroy(&hmap);
 255         }
 256     }
 257 }
 258
 259 static void
 260 run_test(void (*function)(hash_func *))
 261 {
 262     hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
 263     size_t i;
 264
 265     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
 266         function(hash_funcs[i]);
 267         printf(".");
 268         fflush(stdout);
 269     }
 270 }
 271
 272 int
 273 main(void)
 274 {
 275     run_test(test_hmap_insert_delete);
 276     run_test(test_hmap_for_each_safe);
 277     run_test(test_hmap_reserve_shrink);
 278     printf("\n");
 279     return 0;
 280 }
 281