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