tests/test-list.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 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  * openvswitch/list.h. */
  19
  20 #include <config.h>
  21 #undef NDEBUG
  22 #include "openvswitch/list.h"
  23 #include <assert.h>
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include "ovstest.h"
  27
  28 /* Sample list element. */
  29 struct element {
  30     int value;
  31     struct ovs_list node;
  32 };
  33
  34 /* Puts the 'n' values in 'values' into 'elements', and then puts those
  35  * elements in order into 'list'. */
  36 static void
  37 make_list(struct ovs_list *list, struct element elements[],
  38           int values[], size_t n)
  39 {
  40     size_t i;
  41
  42     ovs_list_init(list);
  43     for (i = 0; i < n; i++) {
  44         elements[i].value = i;
  45         ovs_list_push_back(list, &elements[i].node);
  46         values[i] = i;
  47     }
  48 }
  49
  50 /* Verifies that 'list' contains exactly the 'n' values in 'values', in the
  51  * specified order. */
  52 static void
  53 check_list(struct ovs_list *list, const int values[], size_t n)
  54 {
  55     struct element *e;
  56     size_t i;
  57
  58     i = 0;
  59     LIST_FOR_EACH (e, node, list) {
  60         assert(i < n);
  61         assert(e->value == values[i]);
  62         i++;
  63     }
  64     assert(&e->node == list);
  65     assert(i == n);
  66
  67     i = 0;
  68     LIST_FOR_EACH_REVERSE (e, node, list) {
  69         assert(i < n);
  70         assert(e->value == values[n - i - 1]);
  71         i++;
  72     }
  73     assert(&e->node == list);
  74     assert(i == n);
  75
  76     assert(ovs_list_is_empty(list) == !n);
  77     assert(ovs_list_is_singleton(list) == (n == 1));
  78     assert(ovs_list_is_short(list) == (n < 2));
  79     assert(ovs_list_size(list) == n);
  80 }
  81
  82 #if 0
  83 /* Prints the values in 'list', plus 'name' as a title. */
  84 static void
  85 print_list(const char *name, struct ovs_list *list)
  86 {
  87     struct element *e;
  88
  89     printf("%s:", name);
  90     LIST_FOR_EACH (e, node, list) {
  91         printf(" %d", e->value);
  92     }
  93     printf("\n");
  94 }
  95 #endif
  96
  97 /* Tests basic list construction. */
  98 static void
  99 test_list_construction(void)
 100 {
 101     enum { MAX_ELEMS = 100 };
 102     size_t n;
 103
 104     for (n = 0; n <= MAX_ELEMS; n++) {
 105         struct element elements[MAX_ELEMS];
 106         int values[MAX_ELEMS];
 107         struct ovs_list list;
 108
 109         make_list(&list, elements, values, n);
 110         check_list(&list, values, n);
 111     }
 112 }
 113
 114 /* Tests that LIST_FOR_EACH_SAFE properly allows for deletion of the current
 115  * element of a list.  */
 116 static void
 117 test_list_for_each_safe(void)
 118 {
 119     enum { MAX_ELEMS = 10 };
 120     size_t n;
 121     unsigned long int pattern;
 122
 123     for (n = 0; n <= MAX_ELEMS; n++) {
 124         for (pattern = 0; pattern < 1ul << n; pattern++) {
 125             struct element elements[MAX_ELEMS];
 126             int values[MAX_ELEMS];
 127             struct ovs_list list;
 128             struct element *e, *next;
 129             size_t values_idx, n_remaining;
 130             int i;
 131
 132             make_list(&list, elements, values, n);
 133
 134             i = 0;
 135             values_idx = 0;
 136             n_remaining = n;
 137             LIST_FOR_EACH_SAFE (e, next, node, &list) {
 138                 assert(i < n);
 139                 if (pattern & (1ul << i)) {
 140                     ovs_list_remove(&e->node);
 141                     n_remaining--;
 142                     memmove(&values[values_idx], &values[values_idx + 1],
 143                             sizeof *values * (n_remaining - values_idx));
 144                 } else {
 145                     values_idx++;
 146                 }
 147                 check_list(&list, values, n_remaining);
 148                 i++;
 149             }
 150             assert(i == n);
 151             assert(&e->node == &list);
 152
 153             for (i = 0; i < n; i++) {
 154                 if (pattern & (1ul << i)) {
 155                     n_remaining++;
 156                 }
 157             }
 158             assert(n == n_remaining);
 159         }
 160     }
 161 }
 162
 163 /* Tests that LIST_FOR_EACH_POP removes the elements of a list.  */
 164 static void
 165 test_list_for_each_pop(void)
 166 {
 167     enum { MAX_ELEMS = 10 };
 168     size_t n;
 169
 170     for (n = 0; n <= MAX_ELEMS; n++) {
 171         struct element elements[MAX_ELEMS];
 172         int values[MAX_ELEMS];
 173         struct ovs_list list;
 174         struct element *e;
 175         size_t n_remaining;
 176
 177         make_list(&list, elements, values, n);
 178
 179         n_remaining = n;
 180         LIST_FOR_EACH_POP (e, node, &list) {
 181             n_remaining--;
 182             memmove(values, values + 1, sizeof *values * n_remaining);
 183             check_list(&list, values, n_remaining);
 184         }
 185     }
 186 }
 187
 188 /* Tests the transplant of one list into another  */
 189 static void
 190 test_list_push_back_all(void)
 191 {
 192     struct ovs_list list_a, list_b;
 193     struct element a, b, c, d;
 194
 195     a.value = 0;
 196     b.value = 1;
 197     c.value = 2;
 198     d.value = 3;
 199
 200     ovs_list_init(&list_a);
 201     ovs_list_init(&list_b);
 202
 203     ovs_list_insert(&list_a, &a.node);
 204     ovs_list_insert(&list_a, &b.node);
 205     ovs_list_insert(&list_b, &c.node);
 206     ovs_list_insert(&list_b, &d.node);
 207
 208     /* Check test preconditions */
 209     assert(2 == ovs_list_size(&list_a));
 210     assert(2 == ovs_list_size(&list_b));
 211
 212     /* Perform transplant */
 213     ovs_list_push_back_all(&list_a, &list_b);
 214
 215     /* Check expected result */
 216     assert(4 == ovs_list_size(&list_a));
 217     assert(0 == ovs_list_size(&list_b));
 218
 219     struct element *node;
 220     int n = 0;
 221     LIST_FOR_EACH(node, node, &list_a) {
 222         assert(n == node->value);
 223         n++;
 224     }
 225     assert(n == 4);
 226 }
 227
 228 static void
 229 run_test(void (*function)(void))
 230 {
 231     function();
 232     printf(".");
 233 }
 234
 235 static void
 236 test_list_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 237 {
 238     run_test(test_list_construction);
 239     run_test(test_list_for_each_safe);
 240     run_test(test_list_for_each_pop);
 241     run_test(test_list_push_back_all);
 242     printf("\n");
 243 }
 244
 245 OVSTEST_REGISTER("test-list", test_list_main);