Global replace of Nicira Networks.
[openvswitch] / tests / test-list.c
1 /*
2  * Copyright (c) 2008, 2009, 2010, 2011 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
24 #undef NDEBUG
25 #include <assert.h>
26
27 /* Sample list element. */
28 struct element {
29     int value;
30     struct 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 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 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 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 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 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 static void
163 run_test(void (*function)(void))
164 {
165     function();
166     printf(".");
167 }
168
169 int
170 main(void)
171 {
172     run_test(test_list_construction);
173     run_test(test_list_for_each_safe);
174     printf("\n");
175     return 0;
176 }
177