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