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