[rustc.git] / src / jemalloc / test / unit / qr.c

#include "test/jemalloc_test.h"

/* Number of ring entries, in [2..26]. */
#define	NENTRIES 9
/* Split index, in [1..NENTRIES). */
#define	SPLIT_INDEX 5

typedef struct ring_s ring_t;

struct ring_s {
	qr(ring_t) link;
	char id;
};

static void
init_entries(ring_t *entries)
{
	unsigned i;

	for (i = 0; i < NENTRIES; i++) {
		qr_new(&entries[i], link);
		entries[i].id = 'a' + i;
	}
}

static void
test_independent_entries(ring_t *entries)
{
	ring_t *t;
	unsigned i, j;

	for (i = 0; i < NENTRIES; i++) {
		j = 0;
		qr_foreach(t, &entries[i], link) {
			j++;
		}
		assert_u_eq(j, 1,
		    "Iteration over single-element ring should visit precisely "
		    "one element");
	}
	for (i = 0; i < NENTRIES; i++) {
		j = 0;
		qr_reverse_foreach(t, &entries[i], link) {
			j++;
		}
		assert_u_eq(j, 1,
		    "Iteration over single-element ring should visit precisely "
		    "one element");
	}
	for (i = 0; i < NENTRIES; i++) {
		t = qr_next(&entries[i], link);
		assert_ptr_eq(t, &entries[i],
		    "Next element in single-element ring should be same as "
		    "current element");
	}
	for (i = 0; i < NENTRIES; i++) {
		t = qr_prev(&entries[i], link);
		assert_ptr_eq(t, &entries[i],
		    "Previous element in single-element ring should be same as "
		    "current element");
	}
}

TEST_BEGIN(test_qr_one)
{
	ring_t entries[NENTRIES];

	init_entries(entries);
	test_independent_entries(entries);
}
TEST_END

static void
test_entries_ring(ring_t *entries)
{
	ring_t *t;
	unsigned i, j;

	for (i = 0; i < NENTRIES; i++) {
		j = 0;
		qr_foreach(t, &entries[i], link) {
			assert_c_eq(t->id, entries[(i+j) % NENTRIES].id,
			    "Element id mismatch");
			j++;
		}
	}
	for (i = 0; i < NENTRIES; i++) {
		j = 0;
		qr_reverse_foreach(t, &entries[i], link) {
			assert_c_eq(t->id, entries[(NENTRIES+i-j-1) %
			    NENTRIES].id, "Element id mismatch");
			j++;
		}
	}
	for (i = 0; i < NENTRIES; i++) {
		t = qr_next(&entries[i], link);
		assert_c_eq(t->id, entries[(i+1) % NENTRIES].id,
		    "Element id mismatch");
	}
	for (i = 0; i < NENTRIES; i++) {
		t = qr_prev(&entries[i], link);
		assert_c_eq(t->id, entries[(NENTRIES+i-1) % NENTRIES].id,
		    "Element id mismatch");
	}
}

TEST_BEGIN(test_qr_after_insert)
{
	ring_t entries[NENTRIES];
	unsigned i;

	init_entries(entries);
	for (i = 1; i < NENTRIES; i++)
		qr_after_insert(&entries[i - 1], &entries[i], link);
	test_entries_ring(entries);
}
TEST_END

TEST_BEGIN(test_qr_remove)
{
	ring_t entries[NENTRIES];
	ring_t *t;
	unsigned i, j;

	init_entries(entries);
	for (i = 1; i < NENTRIES; i++)
		qr_after_insert(&entries[i - 1], &entries[i], link);

	for (i = 0; i < NENTRIES; i++) {
		j = 0;
		qr_foreach(t, &entries[i], link) {
			assert_c_eq(t->id, entries[i+j].id,
			    "Element id mismatch");
			j++;
		}
		j = 0;
		qr_reverse_foreach(t, &entries[i], link) {
			assert_c_eq(t->id, entries[NENTRIES - 1 - j].id,
			"Element id mismatch");
			j++;
		}
		qr_remove(&entries[i], link);
	}
	test_independent_entries(entries);
}
TEST_END

TEST_BEGIN(test_qr_before_insert)
{
	ring_t entries[NENTRIES];
	ring_t *t;
	unsigned i, j;

	init_entries(entries);
	for (i = 1; i < NENTRIES; i++)
		qr_before_insert(&entries[i - 1], &entries[i], link);
	for (i = 0; i < NENTRIES; i++) {
		j = 0;
		qr_foreach(t, &entries[i], link) {
			assert_c_eq(t->id, entries[(NENTRIES+i-j) %
			    NENTRIES].id, "Element id mismatch");
			j++;
		}
	}
	for (i = 0; i < NENTRIES; i++) {
		j = 0;
		qr_reverse_foreach(t, &entries[i], link) {
			assert_c_eq(t->id, entries[(i+j+1) % NENTRIES].id,
			    "Element id mismatch");
			j++;
		}
	}
	for (i = 0; i < NENTRIES; i++) {
		t = qr_next(&entries[i], link);
		assert_c_eq(t->id, entries[(NENTRIES+i-1) % NENTRIES].id,
		    "Element id mismatch");
	}
	for (i = 0; i < NENTRIES; i++) {
		t = qr_prev(&entries[i], link);
		assert_c_eq(t->id, entries[(i+1) % NENTRIES].id,
		    "Element id mismatch");
	}
}
TEST_END

static void
test_split_entries(ring_t *entries)
{
	ring_t *t;
	unsigned i, j;

	for (i = 0; i < NENTRIES; i++) {
		j = 0;
		qr_foreach(t, &entries[i], link) {
			if (i < SPLIT_INDEX) {
				assert_c_eq(t->id,
				    entries[(i+j) % SPLIT_INDEX].id,
				    "Element id mismatch");
			} else {
				assert_c_eq(t->id, entries[(i+j-SPLIT_INDEX) %
				    (NENTRIES-SPLIT_INDEX) + SPLIT_INDEX].id,
				    "Element id mismatch");
			}
			j++;
		}
	}
}

TEST_BEGIN(test_qr_meld_split)
{
	ring_t entries[NENTRIES];
	unsigned i;

	init_entries(entries);
	for (i = 1; i < NENTRIES; i++)
		qr_after_insert(&entries[i - 1], &entries[i], link);

	qr_split(&entries[0], &entries[SPLIT_INDEX], link);
	test_split_entries(entries);

	qr_meld(&entries[0], &entries[SPLIT_INDEX], link);
	test_entries_ring(entries);

	qr_meld(&entries[0], &entries[SPLIT_INDEX], link);
	test_split_entries(entries);

	qr_split(&entries[0], &entries[SPLIT_INDEX], link);
	test_entries_ring(entries);

	qr_split(&entries[0], &entries[0], link);
	test_entries_ring(entries);

	qr_meld(&entries[0], &entries[0], link);
	test_entries_ring(entries);
}
TEST_END

int
main(void)
{

	return (test(
	    test_qr_one,
	    test_qr_after_insert,
	    test_qr_remove,
	    test_qr_before_insert,
	    test_qr_meld_split));
}
Commit	Line	Data
1a4d82fc JJ	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
	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
	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
	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
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
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
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
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
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
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
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	}