1#include "test/jemalloc_test.h"
2
3/* Number of ring entries, in [2..26]. */
4#define	NENTRIES 9
5
6typedef struct list_s list_t;
7typedef ql_head(list_t) list_head_t;
8
9struct list_s {
10	ql_elm(list_t) link;
11	char id;
12};
13
14static void
15test_empty_list(list_head_t *head)
16{
17	list_t *t;
18	unsigned i;
19
20	assert_ptr_null(ql_first(head), "Unexpected element for empty list");
21	assert_ptr_null(ql_last(head, link),
22	    "Unexpected element for empty list");
23
24	i = 0;
25	ql_foreach(t, head, link) {
26		i++;
27	}
28	assert_u_eq(i, 0, "Unexpected element for empty list");
29
30	i = 0;
31	ql_reverse_foreach(t, head, link) {
32		i++;
33	}
34	assert_u_eq(i, 0, "Unexpected element for empty list");
35}
36
37TEST_BEGIN(test_ql_empty)
38{
39	list_head_t head;
40
41	ql_new(&head);
42	test_empty_list(&head);
43}
44TEST_END
45
46static void
47init_entries(list_t *entries, unsigned nentries)
48{
49	unsigned i;
50
51	for (i = 0; i < nentries; i++) {
52		entries[i].id = 'a' + i;
53		ql_elm_new(&entries[i], link);
54	}
55}
56
57static void
58test_entries_list(list_head_t *head, list_t *entries, unsigned nentries)
59{
60	list_t *t;
61	unsigned i;
62
63	assert_c_eq(ql_first(head)->id, entries[0].id, "Element id mismatch");
64	assert_c_eq(ql_last(head, link)->id, entries[nentries-1].id,
65	    "Element id mismatch");
66
67	i = 0;
68	ql_foreach(t, head, link) {
69		assert_c_eq(t->id, entries[i].id, "Element id mismatch");
70		i++;
71	}
72
73	i = 0;
74	ql_reverse_foreach(t, head, link) {
75		assert_c_eq(t->id, entries[nentries-i-1].id,
76		    "Element id mismatch");
77		i++;
78	}
79
80	for (i = 0; i < nentries-1; i++) {
81		t = ql_next(head, &entries[i], link);
82		assert_c_eq(t->id, entries[i+1].id, "Element id mismatch");
83	}
84	assert_ptr_null(ql_next(head, &entries[nentries-1], link),
85	    "Unexpected element");
86
87	assert_ptr_null(ql_prev(head, &entries[0], link), "Unexpected element");
88	for (i = 1; i < nentries; i++) {
89		t = ql_prev(head, &entries[i], link);
90		assert_c_eq(t->id, entries[i-1].id, "Element id mismatch");
91	}
92}
93
94TEST_BEGIN(test_ql_tail_insert)
95{
96	list_head_t head;
97	list_t entries[NENTRIES];
98	unsigned i;
99
100	ql_new(&head);
101	init_entries(entries, sizeof(entries)/sizeof(list_t));
102	for (i = 0; i < NENTRIES; i++)
103		ql_tail_insert(&head, &entries[i], link);
104
105	test_entries_list(&head, entries, NENTRIES);
106}
107TEST_END
108
109TEST_BEGIN(test_ql_tail_remove)
110{
111	list_head_t head;
112	list_t entries[NENTRIES];
113	unsigned i;
114
115	ql_new(&head);
116	init_entries(entries, sizeof(entries)/sizeof(list_t));
117	for (i = 0; i < NENTRIES; i++)
118		ql_tail_insert(&head, &entries[i], link);
119
120	for (i = 0; i < NENTRIES; i++) {
121		test_entries_list(&head, entries, NENTRIES-i);
122		ql_tail_remove(&head, list_t, link);
123	}
124	test_empty_list(&head);
125}
126TEST_END
127
128TEST_BEGIN(test_ql_head_insert)
129{
130	list_head_t head;
131	list_t entries[NENTRIES];
132	unsigned i;
133
134	ql_new(&head);
135	init_entries(entries, sizeof(entries)/sizeof(list_t));
136	for (i = 0; i < NENTRIES; i++)
137		ql_head_insert(&head, &entries[NENTRIES-i-1], link);
138
139	test_entries_list(&head, entries, NENTRIES);
140}
141TEST_END
142
143TEST_BEGIN(test_ql_head_remove)
144{
145	list_head_t head;
146	list_t entries[NENTRIES];
147	unsigned i;
148
149	ql_new(&head);
150	init_entries(entries, sizeof(entries)/sizeof(list_t));
151	for (i = 0; i < NENTRIES; i++)
152		ql_head_insert(&head, &entries[NENTRIES-i-1], link);
153
154	for (i = 0; i < NENTRIES; i++) {
155		test_entries_list(&head, &entries[i], NENTRIES-i);
156		ql_head_remove(&head, list_t, link);
157	}
158	test_empty_list(&head);
159}
160TEST_END
161
162TEST_BEGIN(test_ql_insert)
163{
164	list_head_t head;
165	list_t entries[8];
166	list_t *a, *b, *c, *d, *e, *f, *g, *h;
167
168	ql_new(&head);
169	init_entries(entries, sizeof(entries)/sizeof(list_t));
170	a = &entries[0];
171	b = &entries[1];
172	c = &entries[2];
173	d = &entries[3];
174	e = &entries[4];
175	f = &entries[5];
176	g = &entries[6];
177	h = &entries[7];
178
179	/*
180	 * ql_remove(), ql_before_insert(), and ql_after_insert() are used
181	 * internally by other macros that are already tested, so there's no
182	 * need to test them completely.  However, insertion/deletion from the
183	 * middle of lists is not otherwise tested; do so here.
184	 */
185	ql_tail_insert(&head, f, link);
186	ql_before_insert(&head, f, b, link);
187	ql_before_insert(&head, f, c, link);
188	ql_after_insert(f, h, link);
189	ql_after_insert(f, g, link);
190	ql_before_insert(&head, b, a, link);
191	ql_after_insert(c, d, link);
192	ql_before_insert(&head, f, e, link);
193
194	test_entries_list(&head, entries, sizeof(entries)/sizeof(list_t));
195}
196TEST_END
197
198int
199main(void)
200{
201
202	return (test(
203	    test_ql_empty,
204	    test_ql_tail_insert,
205	    test_ql_tail_remove,
206	    test_ql_head_insert,
207	    test_ql_head_remove,
208	    test_ql_insert));
209}
210