tests/test-hmap.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2013, 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /* A non-exhaustive test for some of the functions and macros declared in
  18  * hmap.h. */
  19
  20 #include <config.h>
  21 #undef NDEBUG
  22 #include "openvswitch/hmap.h"
  23 #include <assert.h>
  24 #include <string.h>
  25 #include "hash.h"
  26 #include "ovstest.h"
  27 #include "random.h"
  28 #include "util.h"
  29
  30 /* Sample hmap element. */
  31 struct element {
  32     int value;
  33     struct hmap_node node;
  34 };
  35
  36 typedef size_t hash_func(int value);
  37
  38 static int
  39 compare_ints(const void *a_, const void *b_)
  40 {
  41     const int *a = a_;
  42     const int *b = b_;
  43     return *a < *b ? -1 : *a > *b;
  44 }
  45
  46 /* Verifies that 'hmap' contains exactly the 'n' values in 'values'. */
  47 static void
  48 check_hmap(struct hmap *hmap, const int values[], size_t n,
  49            hash_func *hash)
  50 {
  51     int *sort_values, *hmap_values;
  52     struct element *e;
  53     size_t i;
  54
  55     /* Check that all the values are there in iteration. */
  56     sort_values = xmalloc(sizeof *sort_values * n);
  57     hmap_values = xmalloc(sizeof *sort_values * n);
  58
  59     i = 0;
  60     HMAP_FOR_EACH (e, node, hmap) {
  61         assert(i < n);
  62         hmap_values[i++] = e->value;
  63     }
  64     assert(i == n);
  65
  66     memcpy(sort_values, values, sizeof *sort_values * n);
  67     qsort(sort_values, n, sizeof *sort_values, compare_ints);
  68     qsort(hmap_values, n, sizeof *hmap_values, compare_ints);
  69
  70     for (i = 0; i < n; i++) {
  71         assert(sort_values[i] == hmap_values[i]);
  72     }
  73
  74     free(hmap_values);
  75     free(sort_values);
  76
  77     /* Check that all the values are there in lookup. */
  78     for (i = 0; i < n; i++) {
  79         size_t count = 0;
  80
  81         HMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hmap) {
  82             count += e->value == values[i];
  83         }
  84         assert(count == 1);
  85     }
  86
  87     /* Check counters. */
  88     assert(hmap_is_empty(hmap) == !n);
  89     assert(hmap_count(hmap) == n);
  90 }
  91
  92 /* Puts the 'n' values in 'values' into 'elements', and then puts those
  93  * elements into 'hmap'. */
  94 static void
  95 make_hmap(struct hmap *hmap, struct element elements[],
  96           int values[], size_t n, hash_func *hash)
  97 {
  98     size_t i;
  99
 100     hmap_init(hmap);
 101     for (i = 0; i < n; i++) {
 102         elements[i].value = i;
 103         hmap_insert(hmap, &elements[i].node, hash(elements[i].value));
 104         values[i] = i;
 105     }
 106 }
 107
 108 static void
 109 shuffle(int *p, size_t n)
 110 {
 111     for (; n > 1; n--, p++) {
 112         int *q = &p[random_range(n)];
 113         int tmp = *p;
 114         *p = *q;
 115         *q = tmp;
 116     }
 117 }
 118
 119 #if 0
 120 /* Prints the values in 'hmap', plus 'name' as a title. */
 121 static void
 122 print_hmap(const char *name, struct hmap *hmap)
 123 {
 124     struct element *e;
 125
 126     printf("%s:", name);
 127     HMAP_FOR_EACH (e, node, hmap) {
 128         printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hmap->mask);
 129     }
 130     printf("\n");
 131 }
 132
 133 /* Prints the 'n' values in 'values', plus 'name' as a title. */
 134 static void
 135 print_ints(const char *name, const int *values, size_t n)
 136 {
 137     size_t i;
 138
 139     printf("%s:", name);
 140     for (i = 0; i < n; i++) {
 141         printf(" %d", values[i]);
 142     }
 143     printf("\n");
 144 }
 145 #endif
 146
 147 static size_t
 148 identity_hash(int value)
 149 {
 150     return value;
 151 }
 152
 153 static size_t
 154 good_hash(int value)
 155 {
 156     return hash_int(value, 0x1234abcd);
 157 }
 158
 159 static size_t
 160 constant_hash(int value OVS_UNUSED)
 161 {
 162     return 123;
 163 }
 164
 165 /* Tests basic hmap insertion and deletion. */
 166 static void
 167 test_hmap_insert_delete(hash_func *hash)
 168 {
 169     enum { N_ELEMS = 100 };
 170
 171     struct element elements[N_ELEMS];
 172     int values[N_ELEMS];
 173     struct hmap hmap;
 174     size_t i;
 175
 176     hmap_init(&hmap);
 177     for (i = 0; i < N_ELEMS; i++) {
 178         elements[i].value = i;
 179         hmap_insert(&hmap, &elements[i].node, hash(i));
 180         values[i] = i;
 181         check_hmap(&hmap, values, i + 1, hash);
 182     }
 183     shuffle(values, N_ELEMS);
 184     for (i = 0; i < N_ELEMS; i++) {
 185         hmap_remove(&hmap, &elements[values[i]].node);
 186         check_hmap(&hmap, values + (i + 1), N_ELEMS - (i + 1), hash);
 187     }
 188     hmap_destroy(&hmap);
 189 }
 190
 191 /* Tests basic hmap_reserve() and hmap_shrink(). */
 192 static void
 193 test_hmap_reserve_shrink(hash_func *hash)
 194 {
 195     enum { N_ELEMS = 32 };
 196
 197     size_t i;
 198
 199     for (i = 0; i < N_ELEMS; i++) {
 200         struct element elements[N_ELEMS];
 201         int values[N_ELEMS];
 202         struct hmap hmap;
 203         size_t j;
 204
 205         hmap_init(&hmap);
 206         hmap_reserve(&hmap, i);
 207         for (j = 0; j < N_ELEMS; j++) {
 208             elements[j].value = j;
 209             hmap_insert(&hmap, &elements[j].node, hash(j));
 210             values[j] = j;
 211             check_hmap(&hmap, values, j + 1, hash);
 212         }
 213         shuffle(values, N_ELEMS);
 214         for (j = 0; j < N_ELEMS; j++) {
 215             hmap_remove(&hmap, &elements[values[j]].node);
 216             hmap_shrink(&hmap);
 217             check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash);
 218         }
 219         hmap_destroy(&hmap);
 220     }
 221 }
 222
 223 /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
 224  * element of a hmap.  */
 225 static void
 226 test_hmap_for_each_safe(hash_func *hash)
 227 {
 228     enum { MAX_ELEMS = 10 };
 229     size_t n;
 230     unsigned long int pattern;
 231
 232     for (n = 0; n <= MAX_ELEMS; n++) {
 233         for (pattern = 0; pattern < 1ul << n; pattern++) {
 234             struct element elements[MAX_ELEMS];
 235             int values[MAX_ELEMS];
 236             struct hmap hmap;
 237             struct element *e, *next;
 238             size_t n_remaining;
 239             int i;
 240
 241             make_hmap(&hmap, elements, values, n, hash);
 242
 243             i = 0;
 244             n_remaining = n;
 245             HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
 246                 assert(i < n);
 247                 if (pattern & (1ul << e->value)) {
 248                     size_t j;
 249                     hmap_remove(&hmap, &e->node);
 250                     for (j = 0; ; j++) {
 251                         assert(j < n_remaining);
 252                         if (values[j] == e->value) {
 253                             values[j] = values[--n_remaining];
 254                             break;
 255                         }
 256                     }
 257                 }
 258                 check_hmap(&hmap, values, n_remaining, hash);
 259                 i++;
 260             }
 261             assert(i == n);
 262
 263             for (i = 0; i < n; i++) {
 264                 if (pattern & (1ul << i)) {
 265                     n_remaining++;
 266                 }
 267             }
 268             assert(n == n_remaining);
 269
 270             hmap_destroy(&hmap);
 271         }
 272     }
 273 }
 274
 275 /* Tests that HMAP_FOR_EACH_POP removes every element of a hmap. */
 276 static void
 277 test_hmap_for_each_pop(hash_func *hash)
 278 {
 279     enum { MAX_ELEMS = 10 };
 280     size_t n;
 281
 282     for (n = 0; n <= MAX_ELEMS; n++) {
 283         struct element elements[MAX_ELEMS];
 284         int values[MAX_ELEMS];
 285         struct hmap hmap;
 286         struct element *e;
 287         size_t n_remaining, i;
 288
 289         make_hmap(&hmap, elements, values, n, hash);
 290
 291         i = 0;
 292         n_remaining = n;
 293         HMAP_FOR_EACH_POP (e, node, &hmap) {
 294             size_t j;
 295
 296             assert(i < n);
 297
 298             for (j = 0; ; j++) {
 299                 assert(j < n_remaining);
 300                 if (values[j] == e->value) {
 301                     values[j] = values[--n_remaining];
 302                     break;
 303                 }
 304             }
 305             /* Trash the element memory (including the hmap node) */
 306             memset(e, 0, sizeof *e);
 307             check_hmap(&hmap, values, n_remaining, hash);
 308             i++;
 309         }
 310         assert(i == n);
 311
 312         hmap_destroy(&hmap);
 313     }
 314 }
 315
 316 static void
 317 run_test(void (*function)(hash_func *))
 318 {
 319     hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
 320     size_t i;
 321
 322     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
 323         function(hash_funcs[i]);
 324         printf(".");
 325         fflush(stdout);
 326     }
 327 }
 328
 329 static void
 330 test_hmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 331 {
 332     run_test(test_hmap_insert_delete);
 333     run_test(test_hmap_for_each_safe);
 334     run_test(test_hmap_reserve_shrink);
 335     run_test(test_hmap_for_each_pop);
 336     printf("\n");
 337 }
 338
 339 OVSTEST_REGISTER("test-hmap", test_hmap_main);