1 #include "test/jemalloc_test.h"
2
3 /* Number of ring entries, in [2..26]. */
4 #define NENTRIES 9
5 /* Split index, in [1..NENTRIES). */
6 #define SPLIT_INDEX 5
7
8 typedef struct ring_s ring_t;
9
10 struct ring_s {
11 qr(ring_t) link;
12 char id;
13 };
14
15 static void
init_entries(ring_t * entries)16 init_entries(ring_t *entries)
17 {
18 unsigned i;
19
20 for (i = 0; i < NENTRIES; i++) {
21 qr_new(&entries[i], link);
22 entries[i].id = 'a' + i;
23 }
24 }
25
26 static void
test_independent_entries(ring_t * entries)27 test_independent_entries(ring_t *entries)
28 {
29 ring_t *t;
30 unsigned i, j;
31
32 for (i = 0; i < NENTRIES; i++) {
33 j = 0;
34 qr_foreach(t, &entries[i], link) {
35 j++;
36 }
37 assert_u_eq(j, 1,
38 "Iteration over single-element ring should visit precisely "
39 "one element");
40 }
41 for (i = 0; i < NENTRIES; i++) {
42 j = 0;
43 qr_reverse_foreach(t, &entries[i], link) {
44 j++;
45 }
46 assert_u_eq(j, 1,
47 "Iteration over single-element ring should visit precisely "
48 "one element");
49 }
50 for (i = 0; i < NENTRIES; i++) {
51 t = qr_next(&entries[i], link);
52 assert_ptr_eq(t, &entries[i],
53 "Next element in single-element ring should be same as "
54 "current element");
55 }
56 for (i = 0; i < NENTRIES; i++) {
57 t = qr_prev(&entries[i], link);
58 assert_ptr_eq(t, &entries[i],
59 "Previous element in single-element ring should be same as "
60 "current element");
61 }
62 }
63
TEST_BEGIN(test_qr_one)64 TEST_BEGIN(test_qr_one)
65 {
66 ring_t entries[NENTRIES];
67
68 init_entries(entries);
69 test_independent_entries(entries);
70 }
71 TEST_END
72
73 static void
test_entries_ring(ring_t * entries)74 test_entries_ring(ring_t *entries)
75 {
76 ring_t *t;
77 unsigned i, j;
78
79 for (i = 0; i < NENTRIES; i++) {
80 j = 0;
81 qr_foreach(t, &entries[i], link) {
82 assert_c_eq(t->id, entries[(i+j) % NENTRIES].id,
83 "Element id mismatch");
84 j++;
85 }
86 }
87 for (i = 0; i < NENTRIES; i++) {
88 j = 0;
89 qr_reverse_foreach(t, &entries[i], link) {
90 assert_c_eq(t->id, entries[(NENTRIES+i-j-1) %
91 NENTRIES].id, "Element id mismatch");
92 j++;
93 }
94 }
95 for (i = 0; i < NENTRIES; i++) {
96 t = qr_next(&entries[i], link);
97 assert_c_eq(t->id, entries[(i+1) % NENTRIES].id,
98 "Element id mismatch");
99 }
100 for (i = 0; i < NENTRIES; i++) {
101 t = qr_prev(&entries[i], link);
102 assert_c_eq(t->id, entries[(NENTRIES+i-1) % NENTRIES].id,
103 "Element id mismatch");
104 }
105 }
106
TEST_BEGIN(test_qr_after_insert)107 TEST_BEGIN(test_qr_after_insert)
108 {
109 ring_t entries[NENTRIES];
110 unsigned i;
111
112 init_entries(entries);
113 for (i = 1; i < NENTRIES; i++)
114 qr_after_insert(&entries[i - 1], &entries[i], link);
115 test_entries_ring(entries);
116 }
117 TEST_END
118
TEST_BEGIN(test_qr_remove)119 TEST_BEGIN(test_qr_remove)
120 {
121 ring_t entries[NENTRIES];
122 ring_t *t;
123 unsigned i, j;
124
125 init_entries(entries);
126 for (i = 1; i < NENTRIES; i++)
127 qr_after_insert(&entries[i - 1], &entries[i], link);
128
129 for (i = 0; i < NENTRIES; i++) {
130 j = 0;
131 qr_foreach(t, &entries[i], link) {
132 assert_c_eq(t->id, entries[i+j].id,
133 "Element id mismatch");
134 j++;
135 }
136 j = 0;
137 qr_reverse_foreach(t, &entries[i], link) {
138 assert_c_eq(t->id, entries[NENTRIES - 1 - j].id,
139 "Element id mismatch");
140 j++;
141 }
142 qr_remove(&entries[i], link);
143 }
144 test_independent_entries(entries);
145 }
146 TEST_END
147
TEST_BEGIN(test_qr_before_insert)148 TEST_BEGIN(test_qr_before_insert)
149 {
150 ring_t entries[NENTRIES];
151 ring_t *t;
152 unsigned i, j;
153
154 init_entries(entries);
155 for (i = 1; i < NENTRIES; i++)
156 qr_before_insert(&entries[i - 1], &entries[i], link);
157 for (i = 0; i < NENTRIES; i++) {
158 j = 0;
159 qr_foreach(t, &entries[i], link) {
160 assert_c_eq(t->id, entries[(NENTRIES+i-j) %
161 NENTRIES].id, "Element id mismatch");
162 j++;
163 }
164 }
165 for (i = 0; i < NENTRIES; i++) {
166 j = 0;
167 qr_reverse_foreach(t, &entries[i], link) {
168 assert_c_eq(t->id, entries[(i+j+1) % NENTRIES].id,
169 "Element id mismatch");
170 j++;
171 }
172 }
173 for (i = 0; i < NENTRIES; i++) {
174 t = qr_next(&entries[i], link);
175 assert_c_eq(t->id, entries[(NENTRIES+i-1) % NENTRIES].id,
176 "Element id mismatch");
177 }
178 for (i = 0; i < NENTRIES; i++) {
179 t = qr_prev(&entries[i], link);
180 assert_c_eq(t->id, entries[(i+1) % NENTRIES].id,
181 "Element id mismatch");
182 }
183 }
184 TEST_END
185
186 static void
test_split_entries(ring_t * entries)187 test_split_entries(ring_t *entries)
188 {
189 ring_t *t;
190 unsigned i, j;
191
192 for (i = 0; i < NENTRIES; i++) {
193 j = 0;
194 qr_foreach(t, &entries[i], link) {
195 if (i < SPLIT_INDEX) {
196 assert_c_eq(t->id,
197 entries[(i+j) % SPLIT_INDEX].id,
198 "Element id mismatch");
199 } else {
200 assert_c_eq(t->id, entries[(i+j-SPLIT_INDEX) %
201 (NENTRIES-SPLIT_INDEX) + SPLIT_INDEX].id,
202 "Element id mismatch");
203 }
204 j++;
205 }
206 }
207 }
208
TEST_BEGIN(test_qr_meld_split)209 TEST_BEGIN(test_qr_meld_split)
210 {
211 ring_t entries[NENTRIES];
212 unsigned i;
213
214 init_entries(entries);
215 for (i = 1; i < NENTRIES; i++)
216 qr_after_insert(&entries[i - 1], &entries[i], link);
217
218 qr_split(&entries[0], &entries[SPLIT_INDEX], link);
219 test_split_entries(entries);
220
221 qr_meld(&entries[0], &entries[SPLIT_INDEX], link);
222 test_entries_ring(entries);
223
224 qr_meld(&entries[0], &entries[SPLIT_INDEX], link);
225 test_split_entries(entries);
226
227 qr_split(&entries[0], &entries[SPLIT_INDEX], link);
228 test_entries_ring(entries);
229
230 qr_split(&entries[0], &entries[0], link);
231 test_entries_ring(entries);
232
233 qr_meld(&entries[0], &entries[0], link);
234 test_entries_ring(entries);
235 }
236 TEST_END
237
238 int
main(void)239 main(void)
240 {
241
242 return (test(
243 test_qr_one,
244 test_qr_after_insert,
245 test_qr_remove,
246 test_qr_before_insert,
247 test_qr_meld_split));
248 }
249