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  * list.h. */
  19
  20 #include <config.h>
  21 #undef NDEBUG
  22 #include "list.h"
  23 #include <assert.h>
  24 #include <string.h>
  25 #include "ovstest.h"
  26
  27 /* Sample list element. */
  28 struct element {
  29     int value;
  30     struct ovs_list node;
  31 };
  32
  33 /* Puts the 'n' values in 'values' into 'elements', and then puts those
  34  * elements in order into 'list'. */
  35 static void
  36 make_list(struct ovs_list *list, struct element elements[],
  37           int values[], size_t n)
  38 {
  39     size_t i;
  40
  41     list_init(list);
  42     for (i = 0; i < n; i++) {
  43         elements[i].value = i;
  44         list_push_back(list, &elements[i].node);
  45         values[i] = i;
  46     }
  47 }
  48
  49 /* Verifies that 'list' contains exactly the 'n' values in 'values', in the
  50  * specified order. */
  51 static void
  52 check_list(struct ovs_list *list, const int values[], size_t n)
  53 {
  54     struct element *e;
  55     size_t i;
  56
  57     i = 0;
  58     LIST_FOR_EACH (e, node, list) {
  59         assert(i < n);
  60         assert(e->value == values[i]);
  61         i++;
  62     }
  63     assert(&e->node == list);
  64     assert(i == n);
  65
  66     i = 0;
  67     LIST_FOR_EACH_REVERSE (e, node, list) {
  68         assert(i < n);
  69         assert(e->value == values[n - i - 1]);
  70         i++;
  71     }
  72     assert(&e->node == list);
  73     assert(i == n);
  74
  75     assert(list_is_empty(list) == !n);
  76     assert(list_is_singleton(list) == (n == 1));
  77     assert(list_is_short(list) == (n < 2));
  78     assert(list_size(list) == n);
  79 }
  80
  81 #if 0
  82 /* Prints the values in 'list', plus 'name' as a title. */
  83 static void
  84 print_list(const char *name, struct ovs_list *list)
  85 {
  86     struct element *e;
  87
  88     printf("%s:", name);
  89     LIST_FOR_EACH (e, node, list) {
  90         printf(" %d", e->value);
  91     }
  92     printf("\n");
  93 }
  94 #endif
  95
  96 /* Tests basic list construction. */
  97 static void
  98 test_list_construction(void)
  99 {
 100     enum { MAX_ELEMS = 100 };
 101     size_t n;
 102
 103     for (n = 0; n <= MAX_ELEMS; n++) {
 104         struct element elements[MAX_ELEMS];
 105         int values[MAX_ELEMS];
 106         struct ovs_list list;
 107
 108         make_list(&list, elements, values, n);
 109         check_list(&list, values, n);
 110     }
 111 }
 112
 113 /* Tests that LIST_FOR_EACH_SAFE properly allows for deletion of the current
 114  * element of a list.  */
 115 static void
 116 test_list_for_each_safe(void)
 117 {
 118     enum { MAX_ELEMS = 10 };
 119     size_t n;
 120     unsigned long int pattern;
 121
 122     for (n = 0; n <= MAX_ELEMS; n++) {
 123         for (pattern = 0; pattern < 1ul << n; pattern++) {
 124             struct element elements[MAX_ELEMS];
 125             int values[MAX_ELEMS];
 126             struct ovs_list list;
 127             struct element *e, *next;
 128             size_t values_idx, n_remaining;
 129             int i;
 130
 131             make_list(&list, elements, values, n);
 132
 133             i = 0;
 134             values_idx = 0;
 135             n_remaining = n;
 136             LIST_FOR_EACH_SAFE (e, next, node, &list) {
 137                 assert(i < n);
 138                 if (pattern & (1ul << i)) {
 139                     list_remove(&e->node);
 140                     n_remaining--;
 141                     memmove(&values[values_idx], &values[values_idx + 1],
 142                             sizeof *values * (n_remaining - values_idx));
 143                 } else {
 144                     values_idx++;
 145                 }
 146                 check_list(&list, values, n_remaining);
 147                 i++;
 148             }
 149             assert(i == n);
 150             assert(&e->node == &list);
 151
 152             for (i = 0; i < n; i++) {
 153                 if (pattern & (1ul << i)) {
 154                     n_remaining++;
 155                 }
 156             }
 157             assert(n == n_remaining);
 158         }
 159     }
 160 }
 161
 162 /* Tests that LIST_FOR_EACH_POP removes the elements of a list.  */
 163 static void
 164 test_list_for_each_pop(void)
 165 {
 166     enum { MAX_ELEMS = 10 };
 167     size_t n;
 168
 169     for (n = 0; n <= MAX_ELEMS; n++) {
 170         struct element elements[MAX_ELEMS];
 171         int values[MAX_ELEMS];
 172         struct ovs_list list;
 173         struct element *e;
 174         size_t n_remaining;
 175
 176         make_list(&list, elements, values, n);
 177
 178         n_remaining = n;
 179         LIST_FOR_EACH_POP (e, node, &list) {
 180             n_remaining--;
 181             memmove(values, values + 1, sizeof *values * n_remaining);
 182             check_list(&list, values, n_remaining);
 183         }
 184     }
 185 }
 186
 187 static void
 188 run_test(void (*function)(void))
 189 {
 190     function();
 191     printf(".");
 192 }
 193
 194 static void
 195 test_list_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 196 {
 197     run_test(test_list_construction);
 198     run_test(test_list_for_each_safe);
 199     run_test(test_list_for_each_pop);
 200     printf("\n");
 201 }
 202
 203 OVSTEST_REGISTER("test-list", test_list_main);