1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include <btree.h>
uint32_t prng() {
static uint32_t prng_s = 5091;
prng_s = ((prng_s + 24162) * 15322) % 100001;
return prng_s;
}
void test_btree_2() {
BEGIN_TEST("test-btree-2");
btree_t *ht = create_btree(id_key_cmp_fun, 0);
ASSERT(ht != 0);
const int n = 100;
uint32_t k[n], v[n];
for (int i = 0; i < n; i++) {
k[i] = prng();
v[i] = prng();
dbg_printf("add %d -> %d\n", k[i], v[i]);
ASSERT(btree_add(ht, (void*)k[i], (void*)v[i]));
ASSERT(btree_find(ht, (void*)k[i]) == (void*)v[i]);
}
for (int i = 0; i < n; i++) {
ASSERT(btree_find(ht, (void*)k[i]) == (void*)v[i]);
ASSERT(btree_lower(ht, (void*)k[i], 0) == (void*)v[i]);
ASSERT(btree_upper(ht, (void*)k[i], 0) == (void*)v[i]);
}
// random lower bound/upper bound tests
for (int t = 0; t < 100; t++) {
const uint32_t xk = prng();
int ilower = -1, iupper = -1;
for (int i = 1; i < n; i++) {
if (k[i] <= xk && (ilower == -1 || k[i] > k[ilower])) ilower = i;
if (k[i] >= xk && (iupper == -1 || k[i] < k[iupper])) iupper = i;
}
dbg_printf("random %d : ", xk);
if (ilower == -1)
dbg_printf("no lower, ");
else
dbg_printf("lower %d (= %d), ", k[ilower], v[ilower]);
if (iupper == -1)
dbg_printf("no upper ; ");
else
dbg_printf("upper %d (= %d) ; ", k[iupper], v[iupper]);
const uint32_t bt_lower = (uint32_t)btree_lower(ht, (void*)xk, 0);
const uint32_t bt_upper = (uint32_t)btree_upper(ht, (void*)xk, 0);
dbg_printf("got lower %d, upper %d\n", bt_lower, bt_upper);
ASSERT(bt_lower == (ilower == -1 ? 0 : v[ilower]));;
ASSERT(bt_upper == (iupper == -1 ? 0 : v[iupper]));;
}
for (int i = 0; i < n/2; i++) {
btree_remove(ht, (void*)k[i]);
ASSERT(btree_find(ht, (void*)k[i]) == 0);
}
for (int i = 0; i < n; i++) {
ASSERT(btree_find(ht, (void*)k[i]) == (i < n/2 ? 0 : (void*)v[i]));
}
delete_btree(ht);
TEST_OK;
}
#undef TEST_PLACEHOLDER_AFTER_TASKING
#define TEST_PLACEHOLDER_AFTER_TASKING { test_btree_2(); }
/* vim: set ts=4 sw=4 tw=0 noet :*/
|
