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
8typedef struct ring_s ring_t;
9
10struct ring_s {
11	qr(ring_t) link;
12	char id;
13};
14
15static void
16init_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
26static void
27test_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
64TEST_BEGIN(test_qr_one)
65{
66	ring_t entries[NENTRIES];
67
68	init_entries(entries);
69	test_independent_entries(entries);
70}
71TEST_END
72
73static void
74test_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
107TEST_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}
117TEST_END
118
119TEST_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}
146TEST_END
147
148TEST_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}
184TEST_END
185
186static void
187test_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
209TEST_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}
236TEST_END
237
238int
239main(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