1 /*
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2025 The FreeBSD Foundation
5 *
6 * This software was developed by Olivier Certner <olce@FreeBSD.org> at
7 * Kumacom SARL under sponsorship from the FreeBSD Foundation.
8 */
9
10 #include <sys/types.h>
11 #define QUEUE_MACRO_DEBUG_ASSERTIONS
12 #include <sys/queue.h>
13
14 #include <stdio.h>
15 #include <stdlib.h>
16
17 #include <atf-c.h>
18
19 /*
20 * General utilities.
21 */
22 #define DIAG(fmt, ...) do { \
23 fprintf(stderr, "%s(): " fmt "\n", __func__, ##__VA_ARGS__); \
24 } while (0)
25
26 /*
27 * Common definitions and utilities.
28 *
29 * 'type' should be tailq, stailq, list or slist. 'TYPE' is 'type' in
30 * uppercase.
31 */
32
33 #define QUEUE_TESTS_COMMON(type, TYPE) \
34 /* \
35 * Definitions and utilities. \
36 */ \
37 \
38 struct type ## _id_elem { \
39 TYPE ## _ENTRY(type ## _id_elem) ie_entry; \
40 u_int ie_id; \
41 }; \
42 \
43 TYPE ## _HEAD(type ## _ids, type ## _id_elem); \
44 \
45 static void \
46 type ## _check(const struct type ## _ids *const type, \
47 const u_int nb, const u_int id_shift); \
48 \
49 /* \
50 * Creates a tailq/list with 'nb' elements with contiguous IDs \
51 * in ascending order starting at 'id_shift'. \
52 */ \
53 static struct type ## _ids * \
54 type ## _create(const u_int nb, const u_int id_shift) \
55 { \
56 struct type ## _ids *const type = \
57 malloc(sizeof(*type)); \
58 \
59 ATF_REQUIRE_MSG(type != NULL, \
60 "Cannot malloc " #type " head"); \
61 \
62 TYPE ## _INIT(type); \
63 for (u_int i = 0; i < nb; ++i) { \
64 struct type ## _id_elem *const e = \
65 malloc(sizeof(*e)); \
66 \
67 ATF_REQUIRE_MSG(e != NULL, \
68 "Cannot malloc " #type " element %u", i); \
69 e->ie_id = nb - 1 - i + id_shift; \
70 TYPE ## _INSERT_HEAD(type, e, ie_entry); \
71 } \
72 \
73 DIAG("Created " #type " %p with %u elements", \
74 type, nb); \
75 type ## _check(type, nb, id_shift); \
76 return (type); \
77 } \
78 \
79 /* Performs no check. */ \
80 static void \
81 type ## _destroy(struct type ## _ids *const type) \
82 { \
83 struct type ## _id_elem *e, *tmp_e; \
84 \
85 DIAG("Destroying " #type" %p", type); \
86 TYPE ## _FOREACH_SAFE(e, type, ie_entry, \
87 tmp_e) { \
88 free(e); \
89 } \
90 free(type); \
91 } \
92 \
93 \
94 /* Checks that some tailq/list is as produced by *_create(). */ \
95 static void \
96 type ## _check(const struct type ## _ids *const type, \
97 const u_int nb, const u_int id_shift) \
98 { \
99 struct type ## _id_elem *e; \
100 u_int i = 0; \
101 \
102 TYPE ## _FOREACH(e, type, ie_entry) { \
103 ATF_REQUIRE_MSG(i + 1 <= nb, \
104 #type " %p has more than %u elements", \
105 type, nb); \
106 ATF_REQUIRE_MSG(e->ie_id == i + id_shift, \
107 #type " %p element %p: Found ID %u, " \
108 "expected %u", \
109 type, e, e->ie_id, i + id_shift); \
110 ++i; \
111 } \
112 ATF_REQUIRE_MSG(i == nb, \
113 #type " %p has only %u elements, expected %u", \
114 type, i, nb); \
115 } \
116 \
117 /* Returns NULL if not enough elements. */ \
118 static struct type ## _id_elem * \
119 type ## _nth(const struct type ## _ids *const type, \
120 const u_int idx) \
121 { \
122 struct type ## _id_elem *e; \
123 u_int i = 0; \
124 \
125 TYPE ## _FOREACH(e, type, ie_entry) { \
126 if (i == idx) { \
127 DIAG(#type " %p has element %p " \
128 "(ID %u) at index %u", \
129 type, e, e->ie_id, idx); \
130 return (e); \
131 } \
132 ++i; \
133 } \
134 DIAG(#type " %p: Only %u elements, no index %u", \
135 type, i, idx); \
136 return (NULL); \
137 } \
138 \
139 /* \
140 * Tests. \
141 */ \
142 \
143 ATF_TC(type ## _split_after_and_concat); \
144 ATF_TC_HEAD(type ## _split_after_and_concat, tc) \
145 { \
146 atf_tc_set_md_var(tc, "descr", \
147 "Test " #TYPE "_SPLIT_AFTER() followed by " \
148 #TYPE "_CONCAT()"); \
149 } \
150 ATF_TC_BODY(type ## _split_after_and_concat, tc) \
151 { \
152 struct type ## _ids *const type = \
153 type ## _create(100, 0); \
154 struct type ## _ids rest; \
155 struct type ## _id_elem *e; \
156 \
157 e = type ## _nth(type, 49); \
158 TYPE ## _SPLIT_AFTER(type, e, &rest, ie_entry); \
159 type ## _check(type, 50, 0); \
160 type ## _check(&rest, 50, 50); \
161 QUEUE_TESTS_ ## TYPE ## _CONCAT(type, &rest); \
162 ATF_REQUIRE_MSG(TYPE ## _EMPTY(&rest), \
163 "'rest' not empty after concat"); \
164 type ## _check(type, 100, 0); \
165 type ## _destroy(type); \
166 }
167
168 #define QUEUE_TESTS_CHECK_REVERSED(type, TYPE) \
169 /* \
170 * Checks that some tailq/list is reversed. \
171 */ \
172 static void \
173 type ## _check_reversed(const struct type ## _ids *const type, \
174 const u_int nb, const u_int id_shift) \
175 { \
176 struct type ## _id_elem *e; \
177 u_int i = 0; \
178 \
179 TYPE ## _FOREACH(e, type, ie_entry) { \
180 const u_int expected_id = nb - 1 - i + id_shift; \
181 \
182 ATF_REQUIRE_MSG(i < nb, \
183 #type " %p has more than %u elements", \
184 type, nb); \
185 ATF_REQUIRE_MSG(e->ie_id == expected_id, \
186 #type " %p element %p, idx %u: Found ID %u, " \
187 "expected %u", \
188 type, e, i, e->ie_id, expected_id); \
189 ++i; \
190 } \
191 ATF_REQUIRE_MSG(i == nb, \
192 #type " %p has only %u elements, expected %u", \
193 type, i, nb); \
194 }
195
196 /*
197 * Paper over the *_CONCAT() signature differences.
198 */
199
200 #define QUEUE_TESTS_TAILQ_CONCAT(first, second) \
201 TAILQ_CONCAT(first, second, ie_entry)
202
203 #define QUEUE_TESTS_LIST_CONCAT(first, second) \
204 LIST_CONCAT(first, second, list_id_elem, ie_entry)
205
206 #define QUEUE_TESTS_STAILQ_CONCAT(first, second) \
207 STAILQ_CONCAT(first, second)
208
209 #define QUEUE_TESTS_SLIST_CONCAT(first, second) \
210 SLIST_CONCAT(first, second, slist_id_elem, ie_entry)
211
212 /*
213 * ATF test registration.
214 */
215
216 #define QUEUE_TESTS_REGISTRATION(tp, type) \
217 ATF_TP_ADD_TC(tp, type ## _split_after_and_concat)
218
219 /*
220 * Macros defining print functions.
221 *
222 * They are currently not used in the tests above, but are useful for debugging.
223 */
224
225 #define QUEUE_TESTS_TQ_PRINT(type, hfp) \
226 static void \
227 type ## _print(const struct type ## _ids *const type) \
228 { \
229 printf(#type " %p: " __STRING(hfp ## _first) \
230 " = %p, " __STRING(hfp ## _last) " = %p\n", \
231 type, type->hfp ## _first, type->hfp ## _last); \
232 }
233
234 #define QUEUE_TESTS_L_PRINT(type, hfp) \
235 static void \
236 type ## _print(const struct type ## _ids *const type) \
237 { \
238 printf(#type " %p: " __STRING(hfp ## _first) " = %p\n", \
239 type, type->hfp ## _first); \
240 }
241
242
243 /*
244 * Meat.
245 */
246
247 /* Common tests. */
248 QUEUE_TESTS_COMMON(tailq, TAILQ);
249 QUEUE_TESTS_COMMON(list, LIST);
250 QUEUE_TESTS_COMMON(stailq, STAILQ);
251 QUEUE_TESTS_COMMON(slist, SLIST);
252
253 /* STAILQ_REVERSE(). */
254 QUEUE_TESTS_CHECK_REVERSED(stailq, STAILQ);
255 ATF_TC(stailq_reverse);
ATF_TC_HEAD(stailq_reverse,tc)256 ATF_TC_HEAD(stailq_reverse, tc)
257 {
258 atf_tc_set_md_var(tc, "descr", "Test STAILQ_REVERSE");
259 }
ATF_TC_BODY(stailq_reverse,tc)260 ATF_TC_BODY(stailq_reverse, tc)
261 {
262 const u_int size = 100;
263 struct stailq_ids *const stailq = stailq_create(size, 0);
264 struct stailq_ids *const empty_stailq = stailq_create(0, 0);
265 const struct stailq_id_elem *last;
266
267 stailq_check(stailq, size, 0);
268 STAILQ_REVERSE(stailq, stailq_id_elem, ie_entry);
269 stailq_check_reversed(stailq, size, 0);
270 last = STAILQ_LAST(stailq, stailq_id_elem, ie_entry);
271 ATF_REQUIRE_MSG(last->ie_id == 0,
272 "Last element of stailq %p has id %u, expected 0",
273 stailq, last->ie_id);
274 stailq_destroy(stailq);
275
276 STAILQ_REVERSE(empty_stailq, stailq_id_elem, ie_entry);
277 stailq_check(empty_stailq, 0, 0);
278 stailq_destroy(empty_stailq);
279 }
280
281 /*
282 * Main.
283 */
ATF_TP_ADD_TCS(tp)284 ATF_TP_ADD_TCS(tp)
285 {
286 QUEUE_TESTS_REGISTRATION(tp, tailq);
287 QUEUE_TESTS_REGISTRATION(tp, list);
288 QUEUE_TESTS_REGISTRATION(tp, stailq);
289 QUEUE_TESTS_REGISTRATION(tp, slist);
290 ATF_TP_ADD_TC(tp, stailq_reverse);
291
292 return (atf_no_error());
293 }
294