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