Branch data Line data Source code
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 : 2159 : make_list(struct ovs_list *list, struct element elements[],
38 : : int values[], size_t n)
39 : : {
40 : : size_t i;
41 : :
42 : 2159 : ovs_list_init(list);
43 [ + + ]: 25698 : for (i = 0; i < n; i++) {
44 : 23539 : elements[i].value = i;
45 : 23539 : ovs_list_push_back(list, &elements[i].node);
46 : 23539 : values[i] = i;
47 : : }
48 : 2159 : }
49 : :
50 : : /* Verifies that 'list' contains exactly the 'n' values in 'values', in the
51 : : * specified order. */
52 : : static void
53 : 18590 : check_list(struct ovs_list *list, const int values[], size_t n)
54 : : {
55 : : struct element *e;
56 : : size_t i;
57 : :
58 : 18590 : i = 0;
59 [ + + ]: 146680 : LIST_FOR_EACH (e, node, list) {
60 [ - + ]: 128090 : assert(i < n);
61 [ - + ]: 128090 : assert(e->value == values[i]);
62 : 128090 : i++;
63 : : }
64 [ - + ]: 18590 : assert(&e->node == list);
65 [ - + ]: 18590 : assert(i == n);
66 : :
67 : 18590 : i = 0;
68 [ + + ]: 146680 : LIST_FOR_EACH_REVERSE (e, node, list) {
69 [ - + ]: 128090 : assert(i < n);
70 [ - + ]: 128090 : assert(e->value == values[n - i - 1]);
71 : 128090 : i++;
72 : : }
73 [ - + ]: 18590 : assert(&e->node == list);
74 [ - + ]: 18590 : assert(i == n);
75 : :
76 [ - + ]: 18590 : assert(ovs_list_is_empty(list) == !n);
77 [ - + ]: 18590 : assert(ovs_list_is_singleton(list) == (n == 1));
78 [ - + ]: 18590 : assert(ovs_list_is_short(list) == (n < 2));
79 [ - + ]: 18590 : assert(ovs_list_size(list) == n);
80 : 18590 : }
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 : 1 : test_list_construction(void)
100 : : {
101 : : enum { MAX_ELEMS = 100 };
102 : : size_t n;
103 : :
104 [ + + ]: 102 : 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 : 101 : make_list(&list, elements, values, n);
110 : 101 : check_list(&list, values, n);
111 : : }
112 : 1 : }
113 : :
114 : : /* Tests that LIST_FOR_EACH_SAFE properly allows for deletion of the current
115 : : * element of a list. */
116 : : static void
117 : 1 : test_list_for_each_safe(void)
118 : : {
119 : : enum { MAX_ELEMS = 10 };
120 : : size_t n;
121 : : unsigned long int pattern;
122 : :
123 [ + + ]: 12 : for (n = 0; n <= MAX_ELEMS; n++) {
124 [ + + ]: 2058 : 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 : 2047 : make_list(&list, elements, values, n);
133 : :
134 : 2047 : i = 0;
135 : 2047 : values_idx = 0;
136 : 2047 : n_remaining = n;
137 [ + + ][ + + ]: 20481 : LIST_FOR_EACH_SAFE (e, next, node, &list) {
138 [ - + ]: 18434 : assert(i < n);
139 [ + + ]: 18434 : if (pattern & (1ul << i)) {
140 : 9217 : ovs_list_remove(&e->node);
141 : 9217 : n_remaining--;
142 : 9217 : memmove(&values[values_idx], &values[values_idx + 1],
143 : 9217 : sizeof *values * (n_remaining - values_idx));
144 : : } else {
145 : 9217 : values_idx++;
146 : : }
147 : 18434 : check_list(&list, values, n_remaining);
148 : 18434 : i++;
149 : : }
150 [ - + ]: 2047 : assert(i == n);
151 [ - + ]: 2047 : assert(&e->node == &list);
152 : :
153 [ + + ]: 20481 : for (i = 0; i < n; i++) {
154 [ + + ]: 18434 : if (pattern & (1ul << i)) {
155 : 9217 : n_remaining++;
156 : : }
157 : : }
158 [ - + ]: 2047 : assert(n == n_remaining);
159 : : }
160 : : }
161 : 1 : }
162 : :
163 : : /* Tests that LIST_FOR_EACH_POP removes the elements of a list. */
164 : : static void
165 : 1 : test_list_for_each_pop(void)
166 : : {
167 : : enum { MAX_ELEMS = 10 };
168 : : size_t n;
169 : :
170 [ + + ]: 12 : 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 : 11 : make_list(&list, elements, values, n);
178 : :
179 : 11 : n_remaining = n;
180 [ + + ]: 66 : LIST_FOR_EACH_POP (e, node, &list) {
181 : 55 : n_remaining--;
182 : 55 : memmove(values, values + 1, sizeof *values * n_remaining);
183 : 55 : check_list(&list, values, n_remaining);
184 : : }
185 : : }
186 : 1 : }
187 : :
188 : : /* Tests the transplant of one list into another */
189 : : static void
190 : 1 : test_list_push_back_all(void)
191 : : {
192 : : struct ovs_list list_a, list_b;
193 : : struct element a, b, c, d;
194 : :
195 : 1 : a.value = 0;
196 : 1 : b.value = 1;
197 : 1 : c.value = 2;
198 : 1 : d.value = 3;
199 : :
200 : 1 : ovs_list_init(&list_a);
201 : 1 : ovs_list_init(&list_b);
202 : :
203 : 1 : ovs_list_insert(&list_a, &a.node);
204 : 1 : ovs_list_insert(&list_a, &b.node);
205 : 1 : ovs_list_insert(&list_b, &c.node);
206 : 1 : ovs_list_insert(&list_b, &d.node);
207 : :
208 : : /* Check test preconditions */
209 [ - + ]: 1 : assert(2 == ovs_list_size(&list_a));
210 [ - + ]: 1 : assert(2 == ovs_list_size(&list_b));
211 : :
212 : : /* Perform transplant */
213 : 1 : ovs_list_push_back_all(&list_a, &list_b);
214 : :
215 : : /* Check expected result */
216 [ - + ]: 1 : assert(4 == ovs_list_size(&list_a));
217 [ - + ]: 1 : assert(0 == ovs_list_size(&list_b));
218 : :
219 : : struct element *node;
220 : 1 : int n = 0;
221 [ + + ]: 5 : LIST_FOR_EACH(node, node, &list_a) {
222 [ - + ]: 4 : assert(n == node->value);
223 : 4 : n++;
224 : : }
225 [ - + ]: 1 : assert(n == 4);
226 : 1 : }
227 : :
228 : : static void
229 : 4 : run_test(void (*function)(void))
230 : : {
231 : 4 : function();
232 : 4 : printf(".");
233 : 4 : }
234 : :
235 : : static void
236 : 1 : test_list_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
237 : : {
238 : 1 : run_test(test_list_construction);
239 : 1 : run_test(test_list_for_each_safe);
240 : 1 : run_test(test_list_for_each_pop);
241 : 1 : run_test(test_list_push_back_all);
242 : 1 : printf("\n");
243 : 1 : }
244 : :
245 : 1176 : OVSTEST_REGISTER("test-list", test_list_main);
|
