summaryrefslogtreecommitdiff
path: root/examples/redis-unstable/deps/jemalloc/test/unit/fb.c
diff options
context:
space:
mode:
Diffstat (limited to 'examples/redis-unstable/deps/jemalloc/test/unit/fb.c')
-rw-r--r--examples/redis-unstable/deps/jemalloc/test/unit/fb.c954
1 files changed, 0 insertions, 954 deletions
diff --git a/examples/redis-unstable/deps/jemalloc/test/unit/fb.c b/examples/redis-unstable/deps/jemalloc/test/unit/fb.c
deleted file mode 100644
index ad72c75..0000000
--- a/examples/redis-unstable/deps/jemalloc/test/unit/fb.c
+++ /dev/null
@@ -1,954 +0,0 @@
1#include "test/jemalloc_test.h"
2
3#include "jemalloc/internal/fb.h"
4#include "test/nbits.h"
5
6static void
7do_test_init(size_t nbits) {
8 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
9 fb_group_t *fb = malloc(sz);
10 /* Junk fb's contents. */
11 memset(fb, 99, sz);
12 fb_init(fb, nbits);
13 for (size_t i = 0; i < nbits; i++) {
14 expect_false(fb_get(fb, nbits, i),
15 "bitmap should start empty");
16 }
17 free(fb);
18}
19
20TEST_BEGIN(test_fb_init) {
21#define NB(nbits) \
22 do_test_init(nbits);
23 NBITS_TAB
24#undef NB
25}
26TEST_END
27
28static void
29do_test_get_set_unset(size_t nbits) {
30 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
31 fb_group_t *fb = malloc(sz);
32 fb_init(fb, nbits);
33 /* Set the bits divisible by 3. */
34 for (size_t i = 0; i < nbits; i++) {
35 if (i % 3 == 0) {
36 fb_set(fb, nbits, i);
37 }
38 }
39 /* Check them. */
40 for (size_t i = 0; i < nbits; i++) {
41 expect_b_eq(i % 3 == 0, fb_get(fb, nbits, i),
42 "Unexpected bit at position %zu", i);
43 }
44 /* Unset those divisible by 5. */
45 for (size_t i = 0; i < nbits; i++) {
46 if (i % 5 == 0) {
47 fb_unset(fb, nbits, i);
48 }
49 }
50 /* Check them. */
51 for (size_t i = 0; i < nbits; i++) {
52 expect_b_eq(i % 3 == 0 && i % 5 != 0, fb_get(fb, nbits, i),
53 "Unexpected bit at position %zu", i);
54 }
55 free(fb);
56}
57
58TEST_BEGIN(test_get_set_unset) {
59#define NB(nbits) \
60 do_test_get_set_unset(nbits);
61 NBITS_TAB
62#undef NB
63}
64TEST_END
65
66static ssize_t
67find_3_5_compute(ssize_t i, size_t nbits, bool bit, bool forward) {
68 for(; i < (ssize_t)nbits && i >= 0; i += (forward ? 1 : -1)) {
69 bool expected_bit = i % 3 == 0 || i % 5 == 0;
70 if (expected_bit == bit) {
71 return i;
72 }
73 }
74 return forward ? (ssize_t)nbits : (ssize_t)-1;
75}
76
77static void
78do_test_search_simple(size_t nbits) {
79 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
80 fb_group_t *fb = malloc(sz);
81 fb_init(fb, nbits);
82
83 /* We pick multiples of 3 or 5. */
84 for (size_t i = 0; i < nbits; i++) {
85 if (i % 3 == 0) {
86 fb_set(fb, nbits, i);
87 }
88 /* This tests double-setting a little, too. */
89 if (i % 5 == 0) {
90 fb_set(fb, nbits, i);
91 }
92 }
93 for (size_t i = 0; i < nbits; i++) {
94 size_t ffs_compute = find_3_5_compute(i, nbits, true, true);
95 size_t ffs_search = fb_ffs(fb, nbits, i);
96 expect_zu_eq(ffs_compute, ffs_search, "ffs mismatch at %zu", i);
97
98 ssize_t fls_compute = find_3_5_compute(i, nbits, true, false);
99 size_t fls_search = fb_fls(fb, nbits, i);
100 expect_zu_eq(fls_compute, fls_search, "fls mismatch at %zu", i);
101
102 size_t ffu_compute = find_3_5_compute(i, nbits, false, true);
103 size_t ffu_search = fb_ffu(fb, nbits, i);
104 expect_zu_eq(ffu_compute, ffu_search, "ffu mismatch at %zu", i);
105
106 size_t flu_compute = find_3_5_compute(i, nbits, false, false);
107 size_t flu_search = fb_flu(fb, nbits, i);
108 expect_zu_eq(flu_compute, flu_search, "flu mismatch at %zu", i);
109 }
110
111 free(fb);
112}
113
114TEST_BEGIN(test_search_simple) {
115#define NB(nbits) \
116 do_test_search_simple(nbits);
117 NBITS_TAB
118#undef NB
119}
120TEST_END
121
122static void
123expect_exhaustive_results(fb_group_t *mostly_full, fb_group_t *mostly_empty,
124 size_t nbits, size_t special_bit, size_t position) {
125 if (position < special_bit) {
126 expect_zu_eq(special_bit, fb_ffs(mostly_empty, nbits, position),
127 "mismatch at %zu, %zu", position, special_bit);
128 expect_zd_eq(-1, fb_fls(mostly_empty, nbits, position),
129 "mismatch at %zu, %zu", position, special_bit);
130 expect_zu_eq(position, fb_ffu(mostly_empty, nbits, position),
131 "mismatch at %zu, %zu", position, special_bit);
132 expect_zd_eq(position, fb_flu(mostly_empty, nbits, position),
133 "mismatch at %zu, %zu", position, special_bit);
134
135 expect_zu_eq(position, fb_ffs(mostly_full, nbits, position),
136 "mismatch at %zu, %zu", position, special_bit);
137 expect_zd_eq(position, fb_fls(mostly_full, nbits, position),
138 "mismatch at %zu, %zu", position, special_bit);
139 expect_zu_eq(special_bit, fb_ffu(mostly_full, nbits, position),
140 "mismatch at %zu, %zu", position, special_bit);
141 expect_zd_eq(-1, fb_flu(mostly_full, nbits, position),
142 "mismatch at %zu, %zu", position, special_bit);
143 } else if (position == special_bit) {
144 expect_zu_eq(special_bit, fb_ffs(mostly_empty, nbits, position),
145 "mismatch at %zu, %zu", position, special_bit);
146 expect_zd_eq(special_bit, fb_fls(mostly_empty, nbits, position),
147 "mismatch at %zu, %zu", position, special_bit);
148 expect_zu_eq(position + 1, fb_ffu(mostly_empty, nbits, position),
149 "mismatch at %zu, %zu", position, special_bit);
150 expect_zd_eq(position - 1, fb_flu(mostly_empty, nbits,
151 position), "mismatch at %zu, %zu", position, special_bit);
152
153 expect_zu_eq(position + 1, fb_ffs(mostly_full, nbits, position),
154 "mismatch at %zu, %zu", position, special_bit);
155 expect_zd_eq(position - 1, fb_fls(mostly_full, nbits,
156 position), "mismatch at %zu, %zu", position, special_bit);
157 expect_zu_eq(position, fb_ffu(mostly_full, nbits, position),
158 "mismatch at %zu, %zu", position, special_bit);
159 expect_zd_eq(position, fb_flu(mostly_full, nbits, position),
160 "mismatch at %zu, %zu", position, special_bit);
161 } else {
162 /* position > special_bit. */
163 expect_zu_eq(nbits, fb_ffs(mostly_empty, nbits, position),
164 "mismatch at %zu, %zu", position, special_bit);
165 expect_zd_eq(special_bit, fb_fls(mostly_empty, nbits,
166 position), "mismatch at %zu, %zu", position, special_bit);
167 expect_zu_eq(position, fb_ffu(mostly_empty, nbits, position),
168 "mismatch at %zu, %zu", position, special_bit);
169 expect_zd_eq(position, fb_flu(mostly_empty, nbits, position),
170 "mismatch at %zu, %zu", position, special_bit);
171
172 expect_zu_eq(position, fb_ffs(mostly_full, nbits, position),
173 "mismatch at %zu, %zu", position, special_bit);
174 expect_zd_eq(position, fb_fls(mostly_full, nbits, position),
175 "mismatch at %zu, %zu", position, special_bit);
176 expect_zu_eq(nbits, fb_ffu(mostly_full, nbits, position),
177 "mismatch at %zu, %zu", position, special_bit);
178 expect_zd_eq(special_bit, fb_flu(mostly_full, nbits, position),
179 "mismatch at %zu, %zu", position, special_bit);
180 }
181}
182
183static void
184do_test_search_exhaustive(size_t nbits) {
185 /* This test is quadratic; let's not get too big. */
186 if (nbits > 1000) {
187 return;
188 }
189 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
190 fb_group_t *empty = malloc(sz);
191 fb_init(empty, nbits);
192 fb_group_t *full = malloc(sz);
193 fb_init(full, nbits);
194 fb_set_range(full, nbits, 0, nbits);
195
196 for (size_t i = 0; i < nbits; i++) {
197 fb_set(empty, nbits, i);
198 fb_unset(full, nbits, i);
199
200 for (size_t j = 0; j < nbits; j++) {
201 expect_exhaustive_results(full, empty, nbits, i, j);
202 }
203 fb_unset(empty, nbits, i);
204 fb_set(full, nbits, i);
205 }
206
207 free(empty);
208 free(full);
209}
210
211TEST_BEGIN(test_search_exhaustive) {
212#define NB(nbits) \
213 do_test_search_exhaustive(nbits);
214 NBITS_TAB
215#undef NB
216}
217TEST_END
218
219TEST_BEGIN(test_range_simple) {
220 /*
221 * Just pick a constant big enough to have nontrivial middle sizes, and
222 * big enough that usages of things like weirdnum (below) near the
223 * beginning fit comfortably into the beginning of the bitmap.
224 */
225 size_t nbits = 64 * 10;
226 size_t ngroups = FB_NGROUPS(nbits);
227 fb_group_t *fb = malloc(sizeof(fb_group_t) * ngroups);
228 fb_init(fb, nbits);
229 for (size_t i = 0; i < nbits; i++) {
230 if (i % 2 == 0) {
231 fb_set_range(fb, nbits, i, 1);
232 }
233 }
234 for (size_t i = 0; i < nbits; i++) {
235 expect_b_eq(i % 2 == 0, fb_get(fb, nbits, i),
236 "mismatch at position %zu", i);
237 }
238 fb_set_range(fb, nbits, 0, nbits / 2);
239 fb_unset_range(fb, nbits, nbits / 2, nbits / 2);
240 for (size_t i = 0; i < nbits; i++) {
241 expect_b_eq(i < nbits / 2, fb_get(fb, nbits, i),
242 "mismatch at position %zu", i);
243 }
244
245 static const size_t weirdnum = 7;
246 fb_set_range(fb, nbits, 0, nbits);
247 fb_unset_range(fb, nbits, weirdnum, FB_GROUP_BITS + weirdnum);
248 for (size_t i = 0; i < nbits; i++) {
249 expect_b_eq(7 <= i && i <= 2 * weirdnum + FB_GROUP_BITS - 1,
250 !fb_get(fb, nbits, i), "mismatch at position %zu", i);
251 }
252 free(fb);
253}
254TEST_END
255
256static void
257do_test_empty_full_exhaustive(size_t nbits) {
258 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
259 fb_group_t *empty = malloc(sz);
260 fb_init(empty, nbits);
261 fb_group_t *full = malloc(sz);
262 fb_init(full, nbits);
263 fb_set_range(full, nbits, 0, nbits);
264
265 expect_true(fb_full(full, nbits), "");
266 expect_false(fb_empty(full, nbits), "");
267 expect_false(fb_full(empty, nbits), "");
268 expect_true(fb_empty(empty, nbits), "");
269
270 for (size_t i = 0; i < nbits; i++) {
271 fb_set(empty, nbits, i);
272 fb_unset(full, nbits, i);
273
274 expect_false(fb_empty(empty, nbits), "error at bit %zu", i);
275 if (nbits != 1) {
276 expect_false(fb_full(empty, nbits),
277 "error at bit %zu", i);
278 expect_false(fb_empty(full, nbits),
279 "error at bit %zu", i);
280 } else {
281 expect_true(fb_full(empty, nbits),
282 "error at bit %zu", i);
283 expect_true(fb_empty(full, nbits),
284 "error at bit %zu", i);
285 }
286 expect_false(fb_full(full, nbits), "error at bit %zu", i);
287
288 fb_unset(empty, nbits, i);
289 fb_set(full, nbits, i);
290 }
291
292 free(empty);
293 free(full);
294}
295
296TEST_BEGIN(test_empty_full) {
297#define NB(nbits) \
298 do_test_empty_full_exhaustive(nbits);
299 NBITS_TAB
300#undef NB
301}
302TEST_END
303
304/*
305 * This tests both iter_range and the longest range functionality, which is
306 * built closely on top of it.
307 */
308TEST_BEGIN(test_iter_range_simple) {
309 size_t set_limit = 30;
310 size_t nbits = 100;
311 fb_group_t fb[FB_NGROUPS(100)];
312
313 fb_init(fb, nbits);
314
315 /*
316 * Failing to initialize these can lead to build failures with -Wall;
317 * the compiler can't prove that they're set.
318 */
319 size_t begin = (size_t)-1;
320 size_t len = (size_t)-1;
321 bool result;
322
323 /* A set of checks with only the first set_limit bits *set*. */
324 fb_set_range(fb, nbits, 0, set_limit);
325 expect_zu_eq(set_limit, fb_srange_longest(fb, nbits),
326 "Incorrect longest set range");
327 expect_zu_eq(nbits - set_limit, fb_urange_longest(fb, nbits),
328 "Incorrect longest unset range");
329 for (size_t i = 0; i < set_limit; i++) {
330 result = fb_srange_iter(fb, nbits, i, &begin, &len);
331 expect_true(result, "Should have found a range at %zu", i);
332 expect_zu_eq(i, begin, "Incorrect begin at %zu", i);
333 expect_zu_eq(set_limit - i, len, "Incorrect len at %zu", i);
334
335 result = fb_urange_iter(fb, nbits, i, &begin, &len);
336 expect_true(result, "Should have found a range at %zu", i);
337 expect_zu_eq(set_limit, begin, "Incorrect begin at %zu", i);
338 expect_zu_eq(nbits - set_limit, len, "Incorrect len at %zu", i);
339
340 result = fb_srange_riter(fb, nbits, i, &begin, &len);
341 expect_true(result, "Should have found a range at %zu", i);
342 expect_zu_eq(0, begin, "Incorrect begin at %zu", i);
343 expect_zu_eq(i + 1, len, "Incorrect len at %zu", i);
344
345 result = fb_urange_riter(fb, nbits, i, &begin, &len);
346 expect_false(result, "Should not have found a range at %zu", i);
347 }
348 for (size_t i = set_limit; i < nbits; i++) {
349 result = fb_srange_iter(fb, nbits, i, &begin, &len);
350 expect_false(result, "Should not have found a range at %zu", i);
351
352 result = fb_urange_iter(fb, nbits, i, &begin, &len);
353 expect_true(result, "Should have found a range at %zu", i);
354 expect_zu_eq(i, begin, "Incorrect begin at %zu", i);
355 expect_zu_eq(nbits - i, len, "Incorrect len at %zu", i);
356
357 result = fb_srange_riter(fb, nbits, i, &begin, &len);
358 expect_true(result, "Should have found a range at %zu", i);
359 expect_zu_eq(0, begin, "Incorrect begin at %zu", i);
360 expect_zu_eq(set_limit, len, "Incorrect len at %zu", i);
361
362 result = fb_urange_riter(fb, nbits, i, &begin, &len);
363 expect_true(result, "Should have found a range at %zu", i);
364 expect_zu_eq(set_limit, begin, "Incorrect begin at %zu", i);
365 expect_zu_eq(i - set_limit + 1, len, "Incorrect len at %zu", i);
366 }
367
368 /* A set of checks with only the first set_limit bits *unset*. */
369 fb_unset_range(fb, nbits, 0, set_limit);
370 fb_set_range(fb, nbits, set_limit, nbits - set_limit);
371 expect_zu_eq(nbits - set_limit, fb_srange_longest(fb, nbits),
372 "Incorrect longest set range");
373 expect_zu_eq(set_limit, fb_urange_longest(fb, nbits),
374 "Incorrect longest unset range");
375 for (size_t i = 0; i < set_limit; i++) {
376 result = fb_srange_iter(fb, nbits, i, &begin, &len);
377 expect_true(result, "Should have found a range at %zu", i);
378 expect_zu_eq(set_limit, begin, "Incorrect begin at %zu", i);
379 expect_zu_eq(nbits - set_limit, len, "Incorrect len at %zu", i);
380
381 result = fb_urange_iter(fb, nbits, i, &begin, &len);
382 expect_true(result, "Should have found a range at %zu", i);
383 expect_zu_eq(i, begin, "Incorrect begin at %zu", i);
384 expect_zu_eq(set_limit - i, len, "Incorrect len at %zu", i);
385
386 result = fb_srange_riter(fb, nbits, i, &begin, &len);
387 expect_false(result, "Should not have found a range at %zu", i);
388
389 result = fb_urange_riter(fb, nbits, i, &begin, &len);
390 expect_true(result, "Should not have found a range at %zu", i);
391 expect_zu_eq(0, begin, "Incorrect begin at %zu", i);
392 expect_zu_eq(i + 1, len, "Incorrect len at %zu", i);
393 }
394 for (size_t i = set_limit; i < nbits; i++) {
395 result = fb_srange_iter(fb, nbits, i, &begin, &len);
396 expect_true(result, "Should have found a range at %zu", i);
397 expect_zu_eq(i, begin, "Incorrect begin at %zu", i);
398 expect_zu_eq(nbits - i, len, "Incorrect len at %zu", i);
399
400 result = fb_urange_iter(fb, nbits, i, &begin, &len);
401 expect_false(result, "Should not have found a range at %zu", i);
402
403 result = fb_srange_riter(fb, nbits, i, &begin, &len);
404 expect_true(result, "Should have found a range at %zu", i);
405 expect_zu_eq(set_limit, begin, "Incorrect begin at %zu", i);
406 expect_zu_eq(i - set_limit + 1, len, "Incorrect len at %zu", i);
407
408 result = fb_urange_riter(fb, nbits, i, &begin, &len);
409 expect_true(result, "Should have found a range at %zu", i);
410 expect_zu_eq(0, begin, "Incorrect begin at %zu", i);
411 expect_zu_eq(set_limit, len, "Incorrect len at %zu", i);
412 }
413
414}
415TEST_END
416
417/*
418 * Doing this bit-by-bit is too slow for a real implementation, but for testing
419 * code, it's easy to get right. In the exhaustive tests, we'll compare the
420 * (fast but tricky) real implementation against the (slow but simple) testing
421 * one.
422 */
423static bool
424fb_iter_simple(fb_group_t *fb, size_t nbits, size_t start, size_t *r_begin,
425 size_t *r_len, bool val, bool forward) {
426 ssize_t stride = (forward ? (ssize_t)1 : (ssize_t)-1);
427 ssize_t range_begin = (ssize_t)start;
428 for (; range_begin != (ssize_t)nbits && range_begin != -1;
429 range_begin += stride) {
430 if (fb_get(fb, nbits, range_begin) == val) {
431 ssize_t range_end = range_begin;
432 for (; range_end != (ssize_t)nbits && range_end != -1;
433 range_end += stride) {
434 if (fb_get(fb, nbits, range_end) != val) {
435 break;
436 }
437 }
438 if (forward) {
439 *r_begin = range_begin;
440 *r_len = range_end - range_begin;
441 } else {
442 *r_begin = range_end + 1;
443 *r_len = range_begin - range_end;
444 }
445 return true;
446 }
447 }
448 return false;
449}
450
451/* Similar, but for finding longest ranges. */
452static size_t
453fb_range_longest_simple(fb_group_t *fb, size_t nbits, bool val) {
454 size_t longest_so_far = 0;
455 for (size_t begin = 0; begin < nbits; begin++) {
456 if (fb_get(fb, nbits, begin) != val) {
457 continue;
458 }
459 size_t end = begin + 1;
460 for (; end < nbits; end++) {
461 if (fb_get(fb, nbits, end) != val) {
462 break;
463 }
464 }
465 if (end - begin > longest_so_far) {
466 longest_so_far = end - begin;
467 }
468 }
469 return longest_so_far;
470}
471
472static void
473expect_iter_results_at(fb_group_t *fb, size_t nbits, size_t pos,
474 bool val, bool forward) {
475 bool iter_res;
476 size_t iter_begin JEMALLOC_CC_SILENCE_INIT(0);
477 size_t iter_len JEMALLOC_CC_SILENCE_INIT(0);
478 if (val) {
479 if (forward) {
480 iter_res = fb_srange_iter(fb, nbits, pos,
481 &iter_begin, &iter_len);
482 } else {
483 iter_res = fb_srange_riter(fb, nbits, pos,
484 &iter_begin, &iter_len);
485 }
486 } else {
487 if (forward) {
488 iter_res = fb_urange_iter(fb, nbits, pos,
489 &iter_begin, &iter_len);
490 } else {
491 iter_res = fb_urange_riter(fb, nbits, pos,
492 &iter_begin, &iter_len);
493 }
494 }
495
496 bool simple_iter_res;
497 /*
498 * These are dead stores, but the compiler can't always figure that out
499 * statically, and warns on the uninitialized variable.
500 */
501 size_t simple_iter_begin = 0;
502 size_t simple_iter_len = 0;
503 simple_iter_res = fb_iter_simple(fb, nbits, pos, &simple_iter_begin,
504 &simple_iter_len, val, forward);
505
506 expect_b_eq(iter_res, simple_iter_res, "Result mismatch at %zu", pos);
507 if (iter_res && simple_iter_res) {
508 assert_zu_eq(iter_begin, simple_iter_begin,
509 "Begin mismatch at %zu", pos);
510 expect_zu_eq(iter_len, simple_iter_len,
511 "Length mismatch at %zu", pos);
512 }
513}
514
515static void
516expect_iter_results(fb_group_t *fb, size_t nbits) {
517 for (size_t i = 0; i < nbits; i++) {
518 expect_iter_results_at(fb, nbits, i, false, false);
519 expect_iter_results_at(fb, nbits, i, false, true);
520 expect_iter_results_at(fb, nbits, i, true, false);
521 expect_iter_results_at(fb, nbits, i, true, true);
522 }
523 expect_zu_eq(fb_range_longest_simple(fb, nbits, true),
524 fb_srange_longest(fb, nbits), "Longest range mismatch");
525 expect_zu_eq(fb_range_longest_simple(fb, nbits, false),
526 fb_urange_longest(fb, nbits), "Longest range mismatch");
527}
528
529static void
530set_pattern_3(fb_group_t *fb, size_t nbits, bool zero_val) {
531 for (size_t i = 0; i < nbits; i++) {
532 if ((i % 6 < 3 && zero_val) || (i % 6 >= 3 && !zero_val)) {
533 fb_set(fb, nbits, i);
534 } else {
535 fb_unset(fb, nbits, i);
536 }
537 }
538}
539
540static void
541do_test_iter_range_exhaustive(size_t nbits) {
542 /* This test is also pretty slow. */
543 if (nbits > 1000) {
544 return;
545 }
546 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
547 fb_group_t *fb = malloc(sz);
548 fb_init(fb, nbits);
549
550 set_pattern_3(fb, nbits, /* zero_val */ true);
551 expect_iter_results(fb, nbits);
552
553 set_pattern_3(fb, nbits, /* zero_val */ false);
554 expect_iter_results(fb, nbits);
555
556 fb_set_range(fb, nbits, 0, nbits);
557 fb_unset_range(fb, nbits, 0, nbits / 2 == 0 ? 1 : nbits / 2);
558 expect_iter_results(fb, nbits);
559
560 fb_unset_range(fb, nbits, 0, nbits);
561 fb_set_range(fb, nbits, 0, nbits / 2 == 0 ? 1: nbits / 2);
562 expect_iter_results(fb, nbits);
563
564 free(fb);
565}
566
567/*
568 * Like test_iter_range_simple, this tests both iteration and longest-range
569 * computation.
570 */
571TEST_BEGIN(test_iter_range_exhaustive) {
572#define NB(nbits) \
573 do_test_iter_range_exhaustive(nbits);
574 NBITS_TAB
575#undef NB
576}
577TEST_END
578
579/*
580 * If all set bits in the bitmap are contiguous, in [set_start, set_end),
581 * returns the number of set bits in [scount_start, scount_end).
582 */
583static size_t
584scount_contiguous(size_t set_start, size_t set_end, size_t scount_start,
585 size_t scount_end) {
586 /* No overlap. */
587 if (set_end <= scount_start || scount_end <= set_start) {
588 return 0;
589 }
590 /* set range contains scount range */
591 if (set_start <= scount_start && set_end >= scount_end) {
592 return scount_end - scount_start;
593 }
594 /* scount range contains set range. */
595 if (scount_start <= set_start && scount_end >= set_end) {
596 return set_end - set_start;
597 }
598 /* Partial overlap, with set range starting first. */
599 if (set_start < scount_start && set_end < scount_end) {
600 return set_end - scount_start;
601 }
602 /* Partial overlap, with scount range starting first. */
603 if (scount_start < set_start && scount_end < set_end) {
604 return scount_end - set_start;
605 }
606 /*
607 * Trigger an assert failure; the above list should have been
608 * exhaustive.
609 */
610 unreachable();
611}
612
613static size_t
614ucount_contiguous(size_t set_start, size_t set_end, size_t ucount_start,
615 size_t ucount_end) {
616 /* No overlap. */
617 if (set_end <= ucount_start || ucount_end <= set_start) {
618 return ucount_end - ucount_start;
619 }
620 /* set range contains ucount range */
621 if (set_start <= ucount_start && set_end >= ucount_end) {
622 return 0;
623 }
624 /* ucount range contains set range. */
625 if (ucount_start <= set_start && ucount_end >= set_end) {
626 return (ucount_end - ucount_start) - (set_end - set_start);
627 }
628 /* Partial overlap, with set range starting first. */
629 if (set_start < ucount_start && set_end < ucount_end) {
630 return ucount_end - set_end;
631 }
632 /* Partial overlap, with ucount range starting first. */
633 if (ucount_start < set_start && ucount_end < set_end) {
634 return set_start - ucount_start;
635 }
636 /*
637 * Trigger an assert failure; the above list should have been
638 * exhaustive.
639 */
640 unreachable();
641}
642
643static void
644expect_count_match_contiguous(fb_group_t *fb, size_t nbits, size_t set_start,
645 size_t set_end) {
646 for (size_t i = 0; i < nbits; i++) {
647 for (size_t j = i + 1; j <= nbits; j++) {
648 size_t cnt = j - i;
649 size_t scount_expected = scount_contiguous(set_start,
650 set_end, i, j);
651 size_t scount_computed = fb_scount(fb, nbits, i, cnt);
652 expect_zu_eq(scount_expected, scount_computed,
653 "fb_scount error with nbits=%zu, start=%zu, "
654 "cnt=%zu, with bits set in [%zu, %zu)",
655 nbits, i, cnt, set_start, set_end);
656
657 size_t ucount_expected = ucount_contiguous(set_start,
658 set_end, i, j);
659 size_t ucount_computed = fb_ucount(fb, nbits, i, cnt);
660 assert_zu_eq(ucount_expected, ucount_computed,
661 "fb_ucount error with nbits=%zu, start=%zu, "
662 "cnt=%zu, with bits set in [%zu, %zu)",
663 nbits, i, cnt, set_start, set_end);
664
665 }
666 }
667}
668
669static void
670do_test_count_contiguous(size_t nbits) {
671 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
672 fb_group_t *fb = malloc(sz);
673
674 fb_init(fb, nbits);
675
676 expect_count_match_contiguous(fb, nbits, 0, 0);
677 for (size_t i = 0; i < nbits; i++) {
678 fb_set(fb, nbits, i);
679 expect_count_match_contiguous(fb, nbits, 0, i + 1);
680 }
681
682 for (size_t i = 0; i < nbits; i++) {
683 fb_unset(fb, nbits, i);
684 expect_count_match_contiguous(fb, nbits, i + 1, nbits);
685 }
686
687 free(fb);
688}
689
690TEST_BEGIN(test_count_contiguous_simple) {
691 enum {nbits = 300};
692 fb_group_t fb[FB_NGROUPS(nbits)];
693 fb_init(fb, nbits);
694 /* Just an arbitrary number. */
695 size_t start = 23;
696
697 fb_set_range(fb, nbits, start, 30 - start);
698 expect_count_match_contiguous(fb, nbits, start, 30);
699
700 fb_set_range(fb, nbits, start, 40 - start);
701 expect_count_match_contiguous(fb, nbits, start, 40);
702
703 fb_set_range(fb, nbits, start, 70 - start);
704 expect_count_match_contiguous(fb, nbits, start, 70);
705
706 fb_set_range(fb, nbits, start, 120 - start);
707 expect_count_match_contiguous(fb, nbits, start, 120);
708
709 fb_set_range(fb, nbits, start, 150 - start);
710 expect_count_match_contiguous(fb, nbits, start, 150);
711
712 fb_set_range(fb, nbits, start, 200 - start);
713 expect_count_match_contiguous(fb, nbits, start, 200);
714
715 fb_set_range(fb, nbits, start, 290 - start);
716 expect_count_match_contiguous(fb, nbits, start, 290);
717}
718TEST_END
719
720TEST_BEGIN(test_count_contiguous) {
721#define NB(nbits) \
722 /* This test is *particularly* slow in debug builds. */ \
723 if ((!config_debug && nbits < 300) || nbits < 150) { \
724 do_test_count_contiguous(nbits); \
725 }
726 NBITS_TAB
727#undef NB
728}
729TEST_END
730
731static void
732expect_count_match_alternating(fb_group_t *fb_even, fb_group_t *fb_odd,
733 size_t nbits) {
734 for (size_t i = 0; i < nbits; i++) {
735 for (size_t j = i + 1; j <= nbits; j++) {
736 size_t cnt = j - i;
737 size_t odd_scount = cnt / 2
738 + (size_t)(cnt % 2 == 1 && i % 2 == 1);
739 size_t odd_scount_computed = fb_scount(fb_odd, nbits,
740 i, j - i);
741 assert_zu_eq(odd_scount, odd_scount_computed,
742 "fb_scount error with nbits=%zu, start=%zu, "
743 "cnt=%zu, with alternating bits set.",
744 nbits, i, j - i);
745
746 size_t odd_ucount = cnt / 2
747 + (size_t)(cnt % 2 == 1 && i % 2 == 0);
748 size_t odd_ucount_computed = fb_ucount(fb_odd, nbits,
749 i, j - i);
750 assert_zu_eq(odd_ucount, odd_ucount_computed,
751 "fb_ucount error with nbits=%zu, start=%zu, "
752 "cnt=%zu, with alternating bits set.",
753 nbits, i, j - i);
754
755 size_t even_scount = cnt / 2
756 + (size_t)(cnt % 2 == 1 && i % 2 == 0);
757 size_t even_scount_computed = fb_scount(fb_even, nbits,
758 i, j - i);
759 assert_zu_eq(even_scount, even_scount_computed,
760 "fb_scount error with nbits=%zu, start=%zu, "
761 "cnt=%zu, with alternating bits set.",
762 nbits, i, j - i);
763
764 size_t even_ucount = cnt / 2
765 + (size_t)(cnt % 2 == 1 && i % 2 == 1);
766 size_t even_ucount_computed = fb_ucount(fb_even, nbits,
767 i, j - i);
768 assert_zu_eq(even_ucount, even_ucount_computed,
769 "fb_ucount error with nbits=%zu, start=%zu, "
770 "cnt=%zu, with alternating bits set.",
771 nbits, i, j - i);
772 }
773 }
774}
775
776static void
777do_test_count_alternating(size_t nbits) {
778 if (nbits > 1000) {
779 return;
780 }
781 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
782 fb_group_t *fb_even = malloc(sz);
783 fb_group_t *fb_odd = malloc(sz);
784
785 fb_init(fb_even, nbits);
786 fb_init(fb_odd, nbits);
787
788 for (size_t i = 0; i < nbits; i++) {
789 if (i % 2 == 0) {
790 fb_set(fb_even, nbits, i);
791 } else {
792 fb_set(fb_odd, nbits, i);
793 }
794 }
795
796 expect_count_match_alternating(fb_even, fb_odd, nbits);
797
798 free(fb_even);
799 free(fb_odd);
800}
801
802TEST_BEGIN(test_count_alternating) {
803#define NB(nbits) \
804 do_test_count_alternating(nbits);
805 NBITS_TAB
806#undef NB
807}
808TEST_END
809
810static void
811do_test_bit_op(size_t nbits, bool (*op)(bool a, bool b),
812 void (*fb_op)(fb_group_t *dst, fb_group_t *src1, fb_group_t *src2, size_t nbits)) {
813 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t);
814 fb_group_t *fb1 = malloc(sz);
815 fb_group_t *fb2 = malloc(sz);
816 fb_group_t *fb_result = malloc(sz);
817 fb_init(fb1, nbits);
818 fb_init(fb2, nbits);
819 fb_init(fb_result, nbits);
820
821 /* Just two random numbers. */
822 const uint64_t prng_init1 = (uint64_t)0X4E9A9DE6A35691CDULL;
823 const uint64_t prng_init2 = (uint64_t)0X7856E396B063C36EULL;
824
825 uint64_t prng1 = prng_init1;
826 uint64_t prng2 = prng_init2;
827
828 for (size_t i = 0; i < nbits; i++) {
829 bool bit1 = ((prng1 & (1ULL << (i % 64))) != 0);
830 bool bit2 = ((prng2 & (1ULL << (i % 64))) != 0);
831
832 if (bit1) {
833 fb_set(fb1, nbits, i);
834 }
835 if (bit2) {
836 fb_set(fb2, nbits, i);
837 }
838
839 if (i % 64 == 0) {
840 prng1 = prng_state_next_u64(prng1);
841 prng2 = prng_state_next_u64(prng2);
842 }
843 }
844
845 fb_op(fb_result, fb1, fb2, nbits);
846
847 /* Reset the prngs to replay them. */
848 prng1 = prng_init1;
849 prng2 = prng_init2;
850
851 for (size_t i = 0; i < nbits; i++) {
852 bool bit1 = ((prng1 & (1ULL << (i % 64))) != 0);
853 bool bit2 = ((prng2 & (1ULL << (i % 64))) != 0);
854
855 /* Original bitmaps shouldn't change. */
856 expect_b_eq(bit1, fb_get(fb1, nbits, i), "difference at bit %zu", i);
857 expect_b_eq(bit2, fb_get(fb2, nbits, i), "difference at bit %zu", i);
858
859 /* New one should be bitwise and. */
860 expect_b_eq(op(bit1, bit2), fb_get(fb_result, nbits, i),
861 "difference at bit %zu", i);
862
863 /* Update the same way we did last time. */
864 if (i % 64 == 0) {
865 prng1 = prng_state_next_u64(prng1);
866 prng2 = prng_state_next_u64(prng2);
867 }
868 }
869
870 free(fb1);
871 free(fb2);
872 free(fb_result);
873}
874
875static bool
876binary_and(bool a, bool b) {
877 return a & b;
878}
879
880static void
881do_test_bit_and(size_t nbits) {
882 do_test_bit_op(nbits, &binary_and, &fb_bit_and);
883}
884
885TEST_BEGIN(test_bit_and) {
886#define NB(nbits) \
887 do_test_bit_and(nbits);
888 NBITS_TAB
889#undef NB
890}
891TEST_END
892
893static bool
894binary_or(bool a, bool b) {
895 return a | b;
896}
897
898static void
899do_test_bit_or(size_t nbits) {
900 do_test_bit_op(nbits, &binary_or, &fb_bit_or);
901}
902
903TEST_BEGIN(test_bit_or) {
904#define NB(nbits) \
905 do_test_bit_or(nbits);
906 NBITS_TAB
907#undef NB
908}
909TEST_END
910
911static bool
912binary_not(bool a, bool b) {
913 (void)b;
914 return !a;
915}
916
917static void
918fb_bit_not_shim(fb_group_t *dst, fb_group_t *src1, fb_group_t *src2,
919 size_t nbits) {
920 (void)src2;
921 fb_bit_not(dst, src1, nbits);
922}
923
924static void
925do_test_bit_not(size_t nbits) {
926 do_test_bit_op(nbits, &binary_not, &fb_bit_not_shim);
927}
928
929TEST_BEGIN(test_bit_not) {
930#define NB(nbits) \
931 do_test_bit_not(nbits);
932 NBITS_TAB
933#undef NB
934}
935TEST_END
936
937int
938main(void) {
939 return test_no_reentrancy(
940 test_fb_init,
941 test_get_set_unset,
942 test_search_simple,
943 test_search_exhaustive,
944 test_range_simple,
945 test_empty_full,
946 test_iter_range_simple,
947 test_iter_range_exhaustive,
948 test_count_contiguous_simple,
949 test_count_contiguous,
950 test_count_alternating,
951 test_bit_and,
952 test_bit_or,
953 test_bit_not);
954}
generated by cgit v1.2.3 (git 2.46.0) at 2026-04-29 23:44:25 +0000