1 #include "test/jemalloc_test.h"
2
3 /* Number of ring entries, in [2..26]. */
4 #define NENTRIES 9
5
6 typedef struct list_s list_t;
7 typedef ql_head(list_t) list_head_t;
8
9 struct list_s {
10 ql_elm(list_t) link;
11 char id;
12 };
13
14 static void
test_empty_list(list_head_t * head)15 test_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
TEST_BEGIN(test_ql_empty)37 TEST_BEGIN(test_ql_empty)
38 {
39 list_head_t head;
40
41 ql_new(&head);
42 test_empty_list(&head);
43 }
44 TEST_END
45
46 static void
init_entries(list_t * entries,unsigned nentries)47 init_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
57 static void
test_entries_list(list_head_t * head,list_t * entries,unsigned nentries)58 test_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
TEST_BEGIN(test_ql_tail_insert)94 TEST_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 }
107 TEST_END
108
TEST_BEGIN(test_ql_tail_remove)109 TEST_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 }
126 TEST_END
127
TEST_BEGIN(test_ql_head_insert)128 TEST_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 }
141 TEST_END
142
TEST_BEGIN(test_ql_head_remove)143 TEST_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 }
160 TEST_END
161
TEST_BEGIN(test_ql_insert)162 TEST_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 }
196 TEST_END
197
198 int
main(void)199 main(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