tests/test-hindex.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  * hindex.h. */
  19
  20 #include <config.h>
  21 #include "hindex.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 hindex element. */
  32 struct element {
  33     int value;
  34     struct hindex_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 'hindex' contains exactly the 'n' values in 'values'. */
  48 static void
  49 check_hindex(struct hindex *hindex, const int values[], size_t n,
  50            hash_func *hash)
  51 {
  52     int *sort_values, *hindex_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     hindex_values = xmalloc(sizeof *sort_values * n);
  59
  60     i = 0;
  61     HINDEX_FOR_EACH (e, node, hindex) {
  62         assert(i < n);
  63         hindex_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(hindex_values, n, sizeof *hindex_values, compare_ints);
  70
  71     for (i = 0; i < n; i++) {
  72         assert(sort_values[i] == hindex_values[i]);
  73     }
  74
  75     free(hindex_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         HINDEX_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hindex) {
  83             count += e->value == values[i];
  84         }
  85         assert(count == 1);
  86     }
  87
  88     /* Check counters. */
  89     assert(hindex_is_empty(hindex) == !n);
  90     assert(hindex->n_unique <= n);
  91 }
  92
  93 /* Puts the 'n' values in 'values' into 'elements', and then puts those
  94  * elements into 'hindex'. */
  95 static void
  96 make_hindex(struct hindex *hindex, struct element elements[],
  97           int values[], size_t n, hash_func *hash)
  98 {
  99     size_t i;
 100
 101     hindex_init(hindex);
 102     for (i = 0; i < n; i++) {
 103         elements[i].value = i;
 104         hindex_insert(hindex, &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 /* Prints the 'n' values in 'values', plus 'name' as a title. */
 121 static void OVS_UNUSED
 122 print_ints(const char *name, const int *values, size_t n)
 123 {
 124     size_t i;
 125
 126     printf("%s:", name);
 127     for (i = 0; i < n; i++) {
 128         printf(" %d", values[i]);
 129     }
 130     printf("\n");
 131 }
 132
 133 /* Prints the values in 'hindex', plus 'name' as a title. */
 134 static void OVS_UNUSED
 135 print_hindex(const char *name, struct hindex *hindex)
 136 {
 137     struct element *e;
 138
 139     printf("%s:", name);
 140     HINDEX_FOR_EACH (e, node, hindex) {
 141         printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hindex->mask);
 142     }
 143     printf("\n");
 144 }
 145
 146 static size_t
 147 unique_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 static size_t
 165 mod4_hash(int value)
 166 {
 167     return value % 4;
 168 }
 169
 170 static size_t
 171 mod3_hash(int value)
 172 {
 173     return value % 3;
 174 }
 175
 176 static size_t
 177 mod2_hash(int value)
 178 {
 179     return value % 2;
 180 }
 181
 182 static size_t
 183 multipart_hash(int value)
 184 {
 185     return (mod4_hash(value) << 16) | (constant_hash(value) & 0xFFFF);
 186 }
 187
 188 /* Tests basic hindex insertion and deletion. */
 189 static void
 190 test_hindex_insert_delete(hash_func *hash)
 191 {
 192     enum { N_ELEMS = 100 };
 193
 194     struct element elements[N_ELEMS];
 195     int values[N_ELEMS];
 196     struct hindex hindex;
 197     size_t i;
 198
 199     hindex_init(&hindex);
 200     for (i = 0; i < N_ELEMS; i++) {
 201         elements[i].value = i;
 202         hindex_insert(&hindex, &elements[i].node, hash(i));
 203         values[i] = i;
 204         check_hindex(&hindex, values, i + 1, hash);
 205     }
 206     shuffle(values, N_ELEMS);
 207     for (i = 0; i < N_ELEMS; i++) {
 208         hindex_remove(&hindex, &elements[values[i]].node);
 209         check_hindex(&hindex, values + (i + 1), N_ELEMS - (i + 1), hash);
 210     }
 211     hindex_destroy(&hindex);
 212 }
 213
 214 /* Tests basic hindex_reserve() and hindex_shrink(). */
 215 static void
 216 test_hindex_reserve_shrink(hash_func *hash)
 217 {
 218     enum { N_ELEMS = 32 };
 219
 220     size_t i;
 221
 222     for (i = 0; i < N_ELEMS; i++) {
 223         struct element elements[N_ELEMS];
 224         int values[N_ELEMS];
 225         struct hindex hindex;
 226         size_t j;
 227
 228         hindex_init(&hindex);
 229         hindex_reserve(&hindex, i);
 230         for (j = 0; j < N_ELEMS; j++) {
 231             elements[j].value = j;
 232             hindex_insert(&hindex, &elements[j].node, hash(j));
 233             values[j] = j;
 234             check_hindex(&hindex, values, j + 1, hash);
 235         }
 236         shuffle(values, N_ELEMS);
 237         for (j = 0; j < N_ELEMS; j++) {
 238             hindex_remove(&hindex, &elements[values[j]].node);
 239             hindex_shrink(&hindex);
 240             check_hindex(&hindex, values + (j + 1), N_ELEMS - (j + 1), hash);
 241         }
 242         hindex_destroy(&hindex);
 243     }
 244 }
 245
 246 /* Tests that HINDEX_FOR_EACH_SAFE properly allows for deletion of the current
 247  * element of a hindex.  */
 248 static void
 249 test_hindex_for_each_safe(hash_func *hash)
 250 {
 251     enum { MAX_ELEMS = 10 };
 252     size_t n;
 253     unsigned long int pattern;
 254
 255     for (n = 0; n <= MAX_ELEMS; n++) {
 256         for (pattern = 0; pattern < 1ul << n; pattern++) {
 257             struct element elements[MAX_ELEMS];
 258             int values[MAX_ELEMS];
 259             struct hindex hindex;
 260             struct element *e, *next;
 261             size_t n_remaining;
 262             int i;
 263
 264             make_hindex(&hindex, elements, values, n, hash);
 265
 266             i = 0;
 267             n_remaining = n;
 268             HINDEX_FOR_EACH_SAFE (e, next, node, &hindex) {
 269                 assert(i < n);
 270                 if (pattern & (1ul << e->value)) {
 271                     size_t j;
 272                     hindex_remove(&hindex, &e->node);
 273                     for (j = 0; ; j++) {
 274                         assert(j < n_remaining);
 275                         if (values[j] == e->value) {
 276                             values[j] = values[--n_remaining];
 277                             break;
 278                         }
 279                     }
 280                 }
 281                 check_hindex(&hindex, values, n_remaining, hash);
 282                 i++;
 283             }
 284             assert(i == n);
 285
 286             for (i = 0; i < n; i++) {
 287                 if (pattern & (1ul << i)) {
 288                     n_remaining++;
 289                 }
 290             }
 291             assert(n == n_remaining);
 292
 293             hindex_destroy(&hindex);
 294         }
 295     }
 296 }
 297
 298 static void
 299 run_test(void (*function)(hash_func *))
 300 {
 301     hash_func *hash_funcs[] = {
 302         unique_hash,
 303         good_hash,
 304         constant_hash,
 305         mod4_hash,
 306         mod3_hash,
 307         mod2_hash,
 308         multipart_hash,
 309     };
 310     size_t i;
 311
 312     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
 313         function(hash_funcs[i]);
 314         printf(".");
 315         fflush(stdout);
 316     }
 317 }
 318
 319 static void
 320 test_hindex_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 321 {
 322     run_test(test_hindex_insert_delete);
 323     run_test(test_hindex_for_each_safe);
 324     run_test(test_hindex_reserve_shrink);
 325     printf("\n");
 326 }
 327
 328 OVSTEST_REGISTER("test-hindex", test_hindex_main);