tests/test-hmap.c

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