[deb_xorg-server.git] / test / list.c

/**
 * Copyright © 2011 Red Hat, Inc.
 *
 *  Permission is hereby granted, free of charge, to any person obtaining a
 *  copy of this software and associated documentation files (the "Software"),
 *  to deal in the Software without restriction, including without limitation
 *  the rights to use, copy, modify, merge, publish, distribute, sublicense,
 *  and/or sell copies of the Software, and to permit persons to whom the
 *  Software is furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice (including the next
 *  paragraph) shall be included in all copies or substantial portions of the
 *  Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 *  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 *  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 *  DEALINGS IN THE SOFTWARE.
 */

#ifdef HAVE_DIX_CONFIG_H
#include <dix-config.h>
#endif

#include <X11/Xlib.h>
#include <list.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

struct parent {
    int a;
    struct xorg_list children;
    int b;
};

struct child {
    int foo;
    int bar;
    struct xorg_list node;
};

static void
test_xorg_list_init(void)
{
    struct parent parent, tmp;

    memset(&parent, 0, sizeof(parent));
    parent.a = 0xa5a5a5;
    parent.b = ~0xa5a5a5;

    tmp = parent;

    xorg_list_init(&parent.children);

    /* test we haven't touched anything else. */
    assert(parent.a == tmp.a);
    assert(parent.b == tmp.b);

    assert(xorg_list_is_empty(&parent.children));
}

static void
test_xorg_list_add(void)
{
    struct parent parent = { 0 };
    struct child child[3];
    struct child *c;

    xorg_list_init(&parent.children);

    xorg_list_add(&child[0].node, &parent.children);
    assert(!xorg_list_is_empty(&parent.children));

    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[0], sizeof(struct child)) == 0);

    /* note: xorg_list_add prepends */
    xorg_list_add(&child[1].node, &parent.children);
    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[1], sizeof(struct child)) == 0);

    xorg_list_add(&child[2].node, &parent.children);
    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[2], sizeof(struct child)) == 0);
};

static void
test_xorg_list_append(void)
{
    struct parent parent = { 0 };
    struct child child[3];
    struct child *c;
    int i;

    xorg_list_init(&parent.children);

    xorg_list_append(&child[0].node, &parent.children);
    assert(!xorg_list_is_empty(&parent.children));

    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
    c = xorg_list_last_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[0], sizeof(struct child)) == 0);

    xorg_list_append(&child[1].node, &parent.children);
    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
    c = xorg_list_last_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[1], sizeof(struct child)) == 0);

    xorg_list_append(&child[2].node, &parent.children);
    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
    c = xorg_list_last_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[2], sizeof(struct child)) == 0);

    i = 0;
    xorg_list_for_each_entry(c, &parent.children, node) {
        assert(memcmp(c, &child[i++], sizeof(struct child)) == 0);
    }
};

static void
test_xorg_list_del(void)
{
    struct parent parent = { 0 };
    struct child child[2];
    struct child *c;

    xorg_list_init(&parent.children);

    xorg_list_add(&child[0].node, &parent.children);
    assert(!xorg_list_is_empty(&parent.children));

    xorg_list_del(&parent.children);
    assert(xorg_list_is_empty(&parent.children));

    xorg_list_add(&child[0].node, &parent.children);
    xorg_list_del(&child[0].node);
    assert(xorg_list_is_empty(&parent.children));

    xorg_list_add(&child[0].node, &parent.children);
    xorg_list_add(&child[1].node, &parent.children);

    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[1], sizeof(struct child)) == 0);

    /* delete first node */
    xorg_list_del(&child[1].node);
    assert(!xorg_list_is_empty(&parent.children));
    assert(xorg_list_is_empty(&child[1].node));
    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[0], sizeof(struct child)) == 0);

    /* delete last node */
    xorg_list_add(&child[1].node, &parent.children);
    xorg_list_del(&child[0].node);
    c = xorg_list_first_entry(&parent.children, struct child, node);

    assert(memcmp(c, &child[1], sizeof(struct child)) == 0);

    /* delete list head */
    xorg_list_add(&child[0].node, &parent.children);
    xorg_list_del(&parent.children);
    assert(xorg_list_is_empty(&parent.children));
    assert(!xorg_list_is_empty(&child[0].node));
    assert(!xorg_list_is_empty(&child[1].node));
}

static void
test_xorg_list_for_each(void)
{
    struct parent parent = { 0 };
    struct child child[3];
    struct child *c;
    int i = 0;

    xorg_list_init(&parent.children);

    xorg_list_add(&child[2].node, &parent.children);
    xorg_list_add(&child[1].node, &parent.children);
    xorg_list_add(&child[0].node, &parent.children);

    xorg_list_for_each_entry(c, &parent.children, node) {
        assert(memcmp(c, &child[i], sizeof(struct child)) == 0);
        i++;
    }

    /* foreach on empty list */
    xorg_list_del(&parent.children);
    assert(xorg_list_is_empty(&parent.children));

    xorg_list_for_each_entry(c, &parent.children, node) {
        assert(0);              /* we must not get here */
    }
}

struct foo {
    char a;
    struct foo *next;
    char b;
};

static void
test_nt_list_init(void)
{
    struct foo foo;

    foo.a = 10;
    foo.b = 20;
    nt_list_init(&foo, next);

    assert(foo.a == 10);
    assert(foo.b == 20);
    assert(foo.next == NULL);
    assert(nt_list_next(&foo, next) == NULL);
}

static void
test_nt_list_append(void)
{
    int i;
    struct foo *foo = calloc(10, sizeof(struct foo));
    struct foo *item;

    for (item = foo, i = 1; i <= 10; i++, item++) {
        item->a = i;
        item->b = i * 2;
        nt_list_init(item, next);

        if (item != foo)
            nt_list_append(item, foo, struct foo, next);
    }

    /* Test using nt_list_next */
    for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next)) {
        assert(item->a = i);
        assert(item->b = i * 2);
    }

    /* Test using nt_list_for_each_entry */
    i = 1;
    nt_list_for_each_entry(item, foo, next) {
        assert(item->a = i);
        assert(item->b = i * 2);
        i++;
    }
    assert(i == 11);
}

static void
test_nt_list_insert(void)
{
    int i;
    struct foo *foo = calloc(10, sizeof(struct foo));
    struct foo *item;

    foo->a = 10;
    foo->b = 20;
    nt_list_init(foo, next);

    for (item = &foo[1], i = 9; i > 0; i--, item++) {
        item->a = i;
        item->b = i * 2;
        nt_list_init(item, next);
        nt_list_insert(item, foo, struct foo, next);
    }

    /* Test using nt_list_next */
    for (item = foo, i = 10; i > 0; i--, item = nt_list_next(item, next)) {
        assert(item->a = i);
        assert(item->b = i * 2);
    }

    /* Test using nt_list_for_each_entry */
    i = 1;
    nt_list_for_each_entry(item, foo, next) {
        assert(item->a = i);
        assert(item->b = i * 2);
        i++;
    }
    assert(i == 11);
}

static void
test_nt_list_delete(void)
{
    int i = 1;
    struct foo *list = calloc(10, sizeof(struct foo));
    struct foo *foo = list;
    struct foo *item, *tmp;
    struct foo *empty_list = foo;

    nt_list_init(empty_list, next);
    nt_list_del(empty_list, empty_list, struct foo, next);

    assert(!empty_list);

    for (item = foo, i = 1; i <= 10; i++, item++) {
        item->a = i;
        item->b = i * 2;
        nt_list_init(item, next);

        if (item != foo)
            nt_list_append(item, foo, struct foo, next);
    }

    i = 0;
    nt_list_for_each_entry(item, foo, next) {
        i++;
    }
    assert(i == 10);

    /* delete last item */
    nt_list_del(&foo[9], foo, struct foo, next);

    i = 0;
    nt_list_for_each_entry(item, foo, next) {
        assert(item->a != 10);  /* element 10 is gone now */
        i++;
    }
    assert(i == 9);             /* 9 elements left */

    /* delete second item */
    nt_list_del(foo->next, foo, struct foo, next);

    assert(foo->next->a == 3);

    i = 0;
    nt_list_for_each_entry(item, foo, next) {
        assert(item->a != 10);  /* element 10 is gone now */
        assert(item->a != 2);   /* element 2 is gone now */
        i++;
    }
    assert(i == 8);             /* 9 elements left */

    item = foo;
    /* delete first item */
    nt_list_del(foo, foo, struct foo, next);

    assert(item != foo);
    assert(item->next == NULL);
    assert(foo->a == 3);
    assert(foo->next->a == 4);

    nt_list_for_each_entry_safe(item, tmp, foo, next) {
        nt_list_del(item, foo, struct foo, next);
    }

    assert(!foo);
    assert(!item);

    free(list);
}

int
main(int argc, char **argv)
{
    test_xorg_list_init();
    test_xorg_list_add();
    test_xorg_list_append();
    test_xorg_list_del();
    test_xorg_list_for_each();

    test_nt_list_init();
    test_nt_list_append();
    test_nt_list_insert();
    test_nt_list_delete();

    return 0;
}
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	}