Commit | Line | Data |
---|---|---|
a09e091a JB |
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 | struct parent { | |
35 | int a; | |
36 | struct xorg_list children; | |
37 | int b; | |
38 | }; | |
39 | ||
40 | struct child { | |
41 | int foo; | |
42 | int bar; | |
43 | struct xorg_list node; | |
44 | }; | |
45 | ||
46 | static void | |
47 | test_xorg_list_init(void) | |
48 | { | |
49 | struct parent parent, tmp; | |
50 | ||
51 | memset(&parent, 0, sizeof(parent)); | |
52 | parent.a = 0xa5a5a5; | |
53 | parent.b = ~0xa5a5a5; | |
54 | ||
55 | tmp = parent; | |
56 | ||
57 | xorg_list_init(&parent.children); | |
58 | ||
59 | /* test we haven't touched anything else. */ | |
60 | assert(parent.a == tmp.a); | |
61 | assert(parent.b == tmp.b); | |
62 | ||
63 | assert(xorg_list_is_empty(&parent.children)); | |
64 | } | |
65 | ||
66 | static void | |
67 | test_xorg_list_add(void) | |
68 | { | |
69 | struct parent parent = { 0 }; | |
70 | struct child child[3]; | |
71 | struct child *c; | |
72 | ||
73 | xorg_list_init(&parent.children); | |
74 | ||
75 | xorg_list_add(&child[0].node, &parent.children); | |
76 | assert(!xorg_list_is_empty(&parent.children)); | |
77 | ||
78 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
79 | ||
80 | assert(memcmp(c, &child[0], sizeof(struct child)) == 0); | |
81 | ||
82 | /* note: xorg_list_add prepends */ | |
83 | xorg_list_add(&child[1].node, &parent.children); | |
84 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
85 | ||
86 | assert(memcmp(c, &child[1], sizeof(struct child)) == 0); | |
87 | ||
88 | xorg_list_add(&child[2].node, &parent.children); | |
89 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
90 | ||
91 | assert(memcmp(c, &child[2], sizeof(struct child)) == 0); | |
92 | }; | |
93 | ||
94 | static void | |
95 | test_xorg_list_append(void) | |
96 | { | |
97 | struct parent parent = { 0 }; | |
98 | struct child child[3]; | |
99 | struct child *c; | |
100 | int i; | |
101 | ||
102 | xorg_list_init(&parent.children); | |
103 | ||
104 | xorg_list_append(&child[0].node, &parent.children); | |
105 | assert(!xorg_list_is_empty(&parent.children)); | |
106 | ||
107 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
108 | ||
109 | assert(memcmp(c, &child[0], sizeof(struct child)) == 0); | |
110 | c = xorg_list_last_entry(&parent.children, struct child, node); | |
111 | ||
112 | assert(memcmp(c, &child[0], sizeof(struct child)) == 0); | |
113 | ||
114 | xorg_list_append(&child[1].node, &parent.children); | |
115 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
116 | ||
117 | assert(memcmp(c, &child[0], sizeof(struct child)) == 0); | |
118 | c = xorg_list_last_entry(&parent.children, struct child, node); | |
119 | ||
120 | assert(memcmp(c, &child[1], sizeof(struct child)) == 0); | |
121 | ||
122 | xorg_list_append(&child[2].node, &parent.children); | |
123 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
124 | ||
125 | assert(memcmp(c, &child[0], sizeof(struct child)) == 0); | |
126 | c = xorg_list_last_entry(&parent.children, struct child, node); | |
127 | ||
128 | assert(memcmp(c, &child[2], sizeof(struct child)) == 0); | |
129 | ||
130 | i = 0; | |
131 | xorg_list_for_each_entry(c, &parent.children, node) { | |
132 | assert(memcmp(c, &child[i++], sizeof(struct child)) == 0); | |
133 | } | |
134 | }; | |
135 | ||
136 | static void | |
137 | test_xorg_list_del(void) | |
138 | { | |
139 | struct parent parent = { 0 }; | |
140 | struct child child[2]; | |
141 | struct child *c; | |
142 | ||
143 | xorg_list_init(&parent.children); | |
144 | ||
145 | xorg_list_add(&child[0].node, &parent.children); | |
146 | assert(!xorg_list_is_empty(&parent.children)); | |
147 | ||
148 | xorg_list_del(&parent.children); | |
149 | assert(xorg_list_is_empty(&parent.children)); | |
150 | ||
151 | xorg_list_add(&child[0].node, &parent.children); | |
152 | xorg_list_del(&child[0].node); | |
153 | assert(xorg_list_is_empty(&parent.children)); | |
154 | ||
155 | xorg_list_add(&child[0].node, &parent.children); | |
156 | xorg_list_add(&child[1].node, &parent.children); | |
157 | ||
158 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
159 | ||
160 | assert(memcmp(c, &child[1], sizeof(struct child)) == 0); | |
161 | ||
162 | /* delete first node */ | |
163 | xorg_list_del(&child[1].node); | |
164 | assert(!xorg_list_is_empty(&parent.children)); | |
165 | assert(xorg_list_is_empty(&child[1].node)); | |
166 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
167 | ||
168 | assert(memcmp(c, &child[0], sizeof(struct child)) == 0); | |
169 | ||
170 | /* delete last node */ | |
171 | xorg_list_add(&child[1].node, &parent.children); | |
172 | xorg_list_del(&child[0].node); | |
173 | c = xorg_list_first_entry(&parent.children, struct child, node); | |
174 | ||
175 | assert(memcmp(c, &child[1], sizeof(struct child)) == 0); | |
176 | ||
177 | /* delete list head */ | |
178 | xorg_list_add(&child[0].node, &parent.children); | |
179 | xorg_list_del(&parent.children); | |
180 | assert(xorg_list_is_empty(&parent.children)); | |
181 | assert(!xorg_list_is_empty(&child[0].node)); | |
182 | assert(!xorg_list_is_empty(&child[1].node)); | |
183 | } | |
184 | ||
185 | static void | |
186 | test_xorg_list_for_each(void) | |
187 | { | |
188 | struct parent parent = { 0 }; | |
189 | struct child child[3]; | |
190 | struct child *c; | |
191 | int i = 0; | |
192 | ||
193 | xorg_list_init(&parent.children); | |
194 | ||
195 | xorg_list_add(&child[2].node, &parent.children); | |
196 | xorg_list_add(&child[1].node, &parent.children); | |
197 | xorg_list_add(&child[0].node, &parent.children); | |
198 | ||
199 | xorg_list_for_each_entry(c, &parent.children, node) { | |
200 | assert(memcmp(c, &child[i], sizeof(struct child)) == 0); | |
201 | i++; | |
202 | } | |
203 | ||
204 | /* foreach on empty list */ | |
205 | xorg_list_del(&parent.children); | |
206 | assert(xorg_list_is_empty(&parent.children)); | |
207 | ||
208 | xorg_list_for_each_entry(c, &parent.children, node) { | |
209 | assert(0); /* we must not get here */ | |
210 | } | |
211 | } | |
212 | ||
213 | struct foo { | |
214 | char a; | |
215 | struct foo *next; | |
216 | char b; | |
217 | }; | |
218 | ||
219 | static void | |
220 | test_nt_list_init(void) | |
221 | { | |
222 | struct foo foo; | |
223 | ||
224 | foo.a = 10; | |
225 | foo.b = 20; | |
226 | nt_list_init(&foo, next); | |
227 | ||
228 | assert(foo.a == 10); | |
229 | assert(foo.b == 20); | |
230 | assert(foo.next == NULL); | |
231 | assert(nt_list_next(&foo, next) == NULL); | |
232 | } | |
233 | ||
234 | static void | |
235 | test_nt_list_append(void) | |
236 | { | |
237 | int i; | |
238 | struct foo *foo = calloc(10, sizeof(struct foo)); | |
239 | struct foo *item; | |
240 | ||
241 | for (item = foo, i = 1; i <= 10; i++, item++) { | |
242 | item->a = i; | |
243 | item->b = i * 2; | |
244 | nt_list_init(item, next); | |
245 | ||
246 | if (item != foo) | |
247 | nt_list_append(item, foo, struct foo, next); | |
248 | } | |
249 | ||
250 | /* Test using nt_list_next */ | |
251 | for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next)) { | |
252 | assert(item->a = i); | |
253 | assert(item->b = i * 2); | |
254 | } | |
255 | ||
256 | /* Test using nt_list_for_each_entry */ | |
257 | i = 1; | |
258 | nt_list_for_each_entry(item, foo, next) { | |
259 | assert(item->a = i); | |
260 | assert(item->b = i * 2); | |
261 | i++; | |
262 | } | |
263 | assert(i == 11); | |
264 | } | |
265 | ||
266 | static void | |
267 | test_nt_list_insert(void) | |
268 | { | |
269 | int i; | |
270 | struct foo *foo = calloc(10, sizeof(struct foo)); | |
271 | struct foo *item; | |
272 | ||
273 | foo->a = 10; | |
274 | foo->b = 20; | |
275 | nt_list_init(foo, next); | |
276 | ||
277 | for (item = &foo[1], i = 9; i > 0; i--, item++) { | |
278 | item->a = i; | |
279 | item->b = i * 2; | |
280 | nt_list_init(item, next); | |
281 | nt_list_insert(item, foo, struct foo, next); | |
282 | } | |
283 | ||
284 | /* Test using nt_list_next */ | |
285 | for (item = foo, i = 10; i > 0; i--, item = nt_list_next(item, next)) { | |
286 | assert(item->a = i); | |
287 | assert(item->b = i * 2); | |
288 | } | |
289 | ||
290 | /* Test using nt_list_for_each_entry */ | |
291 | i = 1; | |
292 | nt_list_for_each_entry(item, foo, next) { | |
293 | assert(item->a = i); | |
294 | assert(item->b = i * 2); | |
295 | i++; | |
296 | } | |
297 | assert(i == 11); | |
298 | } | |
299 | ||
300 | static void | |
301 | test_nt_list_delete(void) | |
302 | { | |
303 | int i = 1; | |
304 | struct foo *list = calloc(10, sizeof(struct foo)); | |
305 | struct foo *foo = list; | |
306 | struct foo *item, *tmp; | |
307 | struct foo *empty_list = foo; | |
308 | ||
309 | nt_list_init(empty_list, next); | |
310 | nt_list_del(empty_list, empty_list, struct foo, next); | |
311 | ||
312 | assert(!empty_list); | |
313 | ||
314 | for (item = foo, i = 1; i <= 10; i++, item++) { | |
315 | item->a = i; | |
316 | item->b = i * 2; | |
317 | nt_list_init(item, next); | |
318 | ||
319 | if (item != foo) | |
320 | nt_list_append(item, foo, struct foo, next); | |
321 | } | |
322 | ||
323 | i = 0; | |
324 | nt_list_for_each_entry(item, foo, next) { | |
325 | i++; | |
326 | } | |
327 | assert(i == 10); | |
328 | ||
329 | /* delete last item */ | |
330 | nt_list_del(&foo[9], foo, struct foo, next); | |
331 | ||
332 | i = 0; | |
333 | nt_list_for_each_entry(item, foo, next) { | |
334 | assert(item->a != 10); /* element 10 is gone now */ | |
335 | i++; | |
336 | } | |
337 | assert(i == 9); /* 9 elements left */ | |
338 | ||
339 | /* delete second item */ | |
340 | nt_list_del(foo->next, foo, struct foo, next); | |
341 | ||
342 | assert(foo->next->a == 3); | |
343 | ||
344 | i = 0; | |
345 | nt_list_for_each_entry(item, foo, next) { | |
346 | assert(item->a != 10); /* element 10 is gone now */ | |
347 | assert(item->a != 2); /* element 2 is gone now */ | |
348 | i++; | |
349 | } | |
350 | assert(i == 8); /* 9 elements left */ | |
351 | ||
352 | item = foo; | |
353 | /* delete first item */ | |
354 | nt_list_del(foo, foo, struct foo, next); | |
355 | ||
356 | assert(item != foo); | |
357 | assert(item->next == NULL); | |
358 | assert(foo->a == 3); | |
359 | assert(foo->next->a == 4); | |
360 | ||
361 | nt_list_for_each_entry_safe(item, tmp, foo, next) { | |
362 | nt_list_del(item, foo, struct foo, next); | |
363 | } | |
364 | ||
365 | assert(!foo); | |
366 | assert(!item); | |
367 | ||
368 | free(list); | |
369 | } | |
370 | ||
371 | int | |
372 | main(int argc, char **argv) | |
373 | { | |
374 | test_xorg_list_init(); | |
375 | test_xorg_list_add(); | |
376 | test_xorg_list_append(); | |
377 | test_xorg_list_del(); | |
378 | test_xorg_list_for_each(); | |
379 | ||
380 | test_nt_list_init(); | |
381 | test_nt_list_append(); | |
382 | test_nt_list_insert(); | |
383 | test_nt_list_delete(); | |
384 | ||
385 | return 0; | |
386 | } |