/* * BIRD Library -- Bitmap Tests * * (c) 2019 Ondrej Zajicek <santiago@crfreenet.org> * (c) 2019 CZ.NIC z.s.p.o. * * Can be freely distributed and used under the terms of the GNU GPL. */ #include "test/birdtest.h" #include "sysdep/config.h" #include "lib/bitmap.h" #define MAX_NUM (1 << 20) #define MAX_SET (1 << 19) #define MAX_CLR (1 << 17) #define STEP_NUM 1000 #define STEP_SET 1000 #define STEP_CLR 500 static int t_bmap_set_clear_random(void) { struct bmap b; resource_init(); bmap_init(&b, &root_pool, 1024); char expected[MAX_NUM] = {}; uint i, n; for (i = 0; i < MAX_SET; i++) { do n = bt_random() % MAX_NUM; while (expected[n]); bmap_set(&b, n); expected[n] = 1; } for (i = 0; i < MAX_CLR; i++) { do n = bt_random() % MAX_NUM; while (!expected[n]); bmap_clear(&b, n); expected[n] = 0; } for (i = 0; i < MAX_NUM; i++) if (bmap_test(&b, i) != expected[i]) bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, bmap_test(&b, i), expected[i]); return 1; } static int t_hmap_set_clear_random(void) { struct hmap b; resource_init(); hmap_init(&b, &root_pool, 1024); char expected[MAX_NUM] = {}; uint i, n; for (i = 0; i < MAX_SET; i++) { do n = bt_random() % MAX_NUM; while (expected[n]); hmap_set(&b, n); expected[n] = 1; } hmap_check(&b); for (i = 0; i < MAX_CLR; i++) { do n = bt_random() % MAX_NUM; while (!expected[n]); hmap_clear(&b, n); expected[n] = 0; } hmap_check(&b); for (i = 0; i < MAX_NUM; i++) if (hmap_test(&b, i) != expected[i]) bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, hmap_test(&b, i), expected[i]); for (i = 0; 1; i++) { n = hmap_first_zero(&b); bt_assert(n >= i); bt_assert(n <= MAX_NUM); for (; i < n; i++) bt_assert(expected[i]); if (n == MAX_NUM) break; bt_assert(!expected[i]); hmap_set(&b, n); } hmap_check(&b); return 1; } static int t_hmap_set_clear_fill(void) { struct hmap b; resource_init(); hmap_init(&b, &root_pool, 1024); char expected[MAX_NUM] = {}; uint i, j, n, max = 0; for (i = 0; i < STEP_NUM; i++) { uint last = 0; uint step_set = bt_random() % STEP_SET; uint step_clr = bt_random() % STEP_CLR; for (j = 0; j < step_set; j++) { n = hmap_first_zero(&b); bt_assert(n > last || !last); bt_assert(n < MAX_NUM); if (!last) last = n; for (; last < n; last++) bt_assert(expected[last]); bt_assert(!expected[n]); hmap_set(&b, n); expected[n] = 1; max = MAX(max, n); } for (j = 0; j < step_clr; j++) { uint k = 0; do n = bt_random() % max; while (!expected[n] && (k++ < 8)); if (!expected[n]) continue; hmap_clear(&b, n); expected[n] = 0; } } for (i = 0; i < MAX_NUM; i++) if (hmap_test(&b, i) != expected[i]) bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, hmap_test(&b, i), expected[i]); hmap_check(&b); return 1; } int main(int argc, char *argv[]) { bt_init(argc, argv); bt_test_suite(t_bmap_set_clear_random, "BMap - random sequence of sets / clears"); bt_test_suite(t_hmap_set_clear_random, "HMap - random sequence of sets / clears"); bt_test_suite(t_hmap_set_clear_fill, "HMap - linear sets and random clears"); return bt_exit_value(); }