tests/test-hindex.c

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