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 #include "list.h"
  22 #include <string.h>
  23 #include "ovstest.h"
  24
  25 #undef NDEBUG
  26 #include <assert.h>
  27
  28 /* Sample list element. */
  29 struct element {
  30     int value;
  31     struct 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 list *list, struct element elements[],
  38           int values[], size_t n)
  39 {
  40     size_t i;
  41
  42     list_init(list);
  43     for (i = 0; i < n; i++) {
  44         elements[i].value = i;
  45         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 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(list_is_empty(list) == !n);
  77     assert(list_is_singleton(list) == (n == 1));
  78     assert(list_is_short(list) == (n < 2));
  79     assert(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 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 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 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                     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 static void
 164 run_test(void (*function)(void))
 165 {
 166     function();
 167     printf(".");
 168 }
 169
 170 static void
 171 test_list_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 172 {
 173     run_test(test_list_construction);
 174     run_test(test_list_for_each_safe);
 175     printf("\n");
 176 }
 177
 178 OVSTEST_REGISTER("test-list", test_list_main);