1 /**
2 * Copyright © 2011 Red Hat, Inc.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
22 */
23
24 #ifdef HAVE_DIX_CONFIG_H
25 #include <dix-config.h>
26 #endif
27
28 #include <X11/Xlib.h>
29 #include <list.h>
30 #include <string.h>
31 #include <assert.h>
32 #include <stdlib.h>
33
34 #include "tests-common.h"
35
36 struct parent {
37 int a;
38 struct xorg_list children;
39 int b;
40 };
41
42 struct child {
43 int foo;
44 int bar;
45 struct xorg_list node;
46 };
47
48 static void
test_xorg_list_init(void)49 test_xorg_list_init(void)
50 {
51 struct parent parent, tmp;
52
53 memset(&parent, 0, sizeof(parent));
54 parent.a = 0xa5a5a5;
55 parent.b = ~0xa5a5a5;
56
57 tmp = parent;
58
59 xorg_list_init(&parent.children);
60
61 /* test we haven't touched anything else. */
62 assert(parent.a == tmp.a);
63 assert(parent.b == tmp.b);
64
65 assert(xorg_list_is_empty(&parent.children));
66 }
67
68 static void
test_xorg_list_add(void)69 test_xorg_list_add(void)
70 {
71 struct parent parent = { 0 };
72 struct child child[3];
73 struct child *c;
74
75 xorg_list_init(&parent.children);
76
77 xorg_list_add(&child[0].node, &parent.children);
78 assert(!xorg_list_is_empty(&parent.children));
79
80 c = xorg_list_first_entry(&parent.children, struct child, node);
81
82 assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
83
84 /* note: xorg_list_add prepends */
85 xorg_list_add(&child[1].node, &parent.children);
86 c = xorg_list_first_entry(&parent.children, struct child, node);
87
88 assert(memcmp(c, &child[1], sizeof(struct child)) == 0);
89
90 xorg_list_add(&child[2].node, &parent.children);
91 c = xorg_list_first_entry(&parent.children, struct child, node);
92
93 assert(memcmp(c, &child[2], sizeof(struct child)) == 0);
94 };
95
96 static void
test_xorg_list_append(void)97 test_xorg_list_append(void)
98 {
99 struct parent parent = { 0 };
100 struct child child[3];
101 struct child *c;
102 int i;
103
104 xorg_list_init(&parent.children);
105
106 xorg_list_append(&child[0].node, &parent.children);
107 assert(!xorg_list_is_empty(&parent.children));
108
109 c = xorg_list_first_entry(&parent.children, struct child, node);
110
111 assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
112 c = xorg_list_last_entry(&parent.children, struct child, node);
113
114 assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
115
116 xorg_list_append(&child[1].node, &parent.children);
117 c = xorg_list_first_entry(&parent.children, struct child, node);
118
119 assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
120 c = xorg_list_last_entry(&parent.children, struct child, node);
121
122 assert(memcmp(c, &child[1], sizeof(struct child)) == 0);
123
124 xorg_list_append(&child[2].node, &parent.children);
125 c = xorg_list_first_entry(&parent.children, struct child, node);
126
127 assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
128 c = xorg_list_last_entry(&parent.children, struct child, node);
129
130 assert(memcmp(c, &child[2], sizeof(struct child)) == 0);
131
132 i = 0;
133 xorg_list_for_each_entry(c, &parent.children, node) {
134 assert(memcmp(c, &child[i++], sizeof(struct child)) == 0);
135 }
136 };
137
138 static void
test_xorg_list_del(void)139 test_xorg_list_del(void)
140 {
141 struct parent parent = { 0 };
142 struct child child[2];
143 struct child *c;
144
145 xorg_list_init(&parent.children);
146
147 xorg_list_add(&child[0].node, &parent.children);
148 assert(!xorg_list_is_empty(&parent.children));
149
150 xorg_list_del(&parent.children);
151 assert(xorg_list_is_empty(&parent.children));
152
153 xorg_list_add(&child[0].node, &parent.children);
154 xorg_list_del(&child[0].node);
155 assert(xorg_list_is_empty(&parent.children));
156
157 xorg_list_add(&child[0].node, &parent.children);
158 xorg_list_add(&child[1].node, &parent.children);
159
160 c = xorg_list_first_entry(&parent.children, struct child, node);
161
162 assert(memcmp(c, &child[1], sizeof(struct child)) == 0);
163
164 /* delete first node */
165 xorg_list_del(&child[1].node);
166 assert(!xorg_list_is_empty(&parent.children));
167 assert(xorg_list_is_empty(&child[1].node));
168 c = xorg_list_first_entry(&parent.children, struct child, node);
169
170 assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
171
172 /* delete last node */
173 xorg_list_add(&child[1].node, &parent.children);
174 xorg_list_del(&child[0].node);
175 c = xorg_list_first_entry(&parent.children, struct child, node);
176
177 assert(memcmp(c, &child[1], sizeof(struct child)) == 0);
178
179 /* delete list head */
180 xorg_list_add(&child[0].node, &parent.children);
181 xorg_list_del(&parent.children);
182 assert(xorg_list_is_empty(&parent.children));
183 assert(!xorg_list_is_empty(&child[0].node));
184 assert(!xorg_list_is_empty(&child[1].node));
185 }
186
187 static void
test_xorg_list_for_each(void)188 test_xorg_list_for_each(void)
189 {
190 struct parent parent = { 0 };
191 struct child child[3];
192 struct child *c;
193 int i = 0;
194
195 xorg_list_init(&parent.children);
196
197 xorg_list_add(&child[2].node, &parent.children);
198 xorg_list_add(&child[1].node, &parent.children);
199 xorg_list_add(&child[0].node, &parent.children);
200
201 xorg_list_for_each_entry(c, &parent.children, node) {
202 assert(memcmp(c, &child[i], sizeof(struct child)) == 0);
203 i++;
204 }
205
206 /* foreach on empty list */
207 xorg_list_del(&parent.children);
208 assert(xorg_list_is_empty(&parent.children));
209
210 xorg_list_for_each_entry(c, &parent.children, node) {
211 assert(0); /* we must not get here */
212 }
213 }
214
215 struct foo {
216 char a;
217 struct foo *next;
218 char b;
219 };
220
221 static void
test_nt_list_init(void)222 test_nt_list_init(void)
223 {
224 struct foo foo;
225
226 foo.a = 10;
227 foo.b = 20;
228 nt_list_init(&foo, next);
229
230 assert(foo.a == 10);
231 assert(foo.b == 20);
232 assert(foo.next == NULL);
233 assert(nt_list_next(&foo, next) == NULL);
234 }
235
236 static void
test_nt_list_append(void)237 test_nt_list_append(void)
238 {
239 int i;
240 struct foo *foo = calloc(10, sizeof(struct foo));
241 struct foo *item;
242
243 for (item = foo, i = 1; i <= 10; i++, item++) {
244 item->a = i;
245 item->b = i * 2;
246 nt_list_init(item, next);
247
248 if (item != foo)
249 nt_list_append(item, foo, struct foo, next);
250 }
251
252 /* Test using nt_list_next */
253 for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next)) {
254 assert(item->a == i);
255 assert(item->b == i * 2);
256 }
257
258 /* Test using nt_list_for_each_entry */
259 i = 1;
260 nt_list_for_each_entry(item, foo, next) {
261 assert(item->a == i);
262 assert(item->b == i * 2);
263 i++;
264 }
265 assert(i == 11);
266 }
267
268 static void
test_nt_list_insert(void)269 test_nt_list_insert(void)
270 {
271 int i;
272 struct foo *foo = calloc(10, sizeof(struct foo));
273 struct foo *item;
274
275 foo->a = 1;
276 foo->b = 2;
277 nt_list_init(foo, next);
278
279 for (item = &foo[1], i = 10; i > 1; i--, item++) {
280 item->a = i;
281 item->b = i * 2;
282 nt_list_init(item, next);
283 nt_list_insert(item, foo, struct foo, next);
284 }
285
286 /* Test using nt_list_next */
287 for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next)) {
288 assert(item->a == i);
289 assert(item->b == i * 2);
290 }
291
292 /* Test using nt_list_for_each_entry */
293 i = 1;
294 nt_list_for_each_entry(item, foo, next) {
295 assert(item->a == i);
296 assert(item->b == i * 2);
297 i++;
298 }
299 assert(i == 11);
300 }
301
302 static void
test_nt_list_delete(void)303 test_nt_list_delete(void)
304 {
305 int i = 1;
306 struct foo *list = calloc(10, sizeof(struct foo));
307 struct foo *foo = list;
308 struct foo *item, *tmp;
309 struct foo *empty_list = foo;
310
311 nt_list_init(empty_list, next);
312 nt_list_del(empty_list, empty_list, struct foo, next);
313
314 assert(!empty_list);
315
316 for (item = foo, i = 1; i <= 10; i++, item++) {
317 item->a = i;
318 item->b = i * 2;
319 nt_list_init(item, next);
320
321 if (item != foo)
322 nt_list_append(item, foo, struct foo, next);
323 }
324
325 i = 0;
326 nt_list_for_each_entry(item, foo, next) {
327 i++;
328 }
329 assert(i == 10);
330
331 /* delete last item */
332 nt_list_del(&foo[9], foo, struct foo, next);
333
334 i = 0;
335 nt_list_for_each_entry(item, foo, next) {
336 assert(item->a != 10); /* element 10 is gone now */
337 i++;
338 }
339 assert(i == 9); /* 9 elements left */
340
341 /* delete second item */
342 nt_list_del(foo->next, foo, struct foo, next);
343
344 assert(foo->next->a == 3);
345
346 i = 0;
347 nt_list_for_each_entry(item, foo, next) {
348 assert(item->a != 10); /* element 10 is gone now */
349 assert(item->a != 2); /* element 2 is gone now */
350 i++;
351 }
352 assert(i == 8); /* 9 elements left */
353
354 item = foo;
355 /* delete first item */
356 nt_list_del(foo, foo, struct foo, next);
357
358 assert(item != foo);
359 assert(item->next == NULL);
360 assert(foo->a == 3);
361 assert(foo->next->a == 4);
362
363 nt_list_for_each_entry_safe(item, tmp, foo, next) {
364 nt_list_del(item, foo, struct foo, next);
365 }
366
367 assert(!foo);
368 assert(!item);
369
370 free(list);
371 }
372
373 int
list_test(void)374 list_test(void)
375 {
376 test_xorg_list_init();
377 test_xorg_list_add();
378 test_xorg_list_append();
379 test_xorg_list_del();
380 test_xorg_list_for_each();
381
382 test_nt_list_init();
383 test_nt_list_append();
384 test_nt_list_insert();
385 test_nt_list_delete();
386
387 return 0;
388 }
389