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