1 #include "test/jemalloc_test.h"
2
TEST_BEGIN(test_rtree_get_empty)3 TEST_BEGIN(test_rtree_get_empty)
4 {
5 unsigned i;
6
7 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) {
8 rtree_t *rtree = rtree_new(i, imalloc, idalloc);
9 assert_u_eq(rtree_get(rtree, 0), 0,
10 "rtree_get() should return NULL for empty tree");
11 rtree_delete(rtree);
12 }
13 }
14 TEST_END
15
TEST_BEGIN(test_rtree_extrema)16 TEST_BEGIN(test_rtree_extrema)
17 {
18 unsigned i;
19
20 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) {
21 rtree_t *rtree = rtree_new(i, imalloc, idalloc);
22
23 rtree_set(rtree, 0, 1);
24 assert_u_eq(rtree_get(rtree, 0), 1,
25 "rtree_get() should return previously set value");
26
27 rtree_set(rtree, ~((uintptr_t)0), 1);
28 assert_u_eq(rtree_get(rtree, ~((uintptr_t)0)), 1,
29 "rtree_get() should return previously set value");
30
31 rtree_delete(rtree);
32 }
33 }
34 TEST_END
35
TEST_BEGIN(test_rtree_bits)36 TEST_BEGIN(test_rtree_bits)
37 {
38 unsigned i, j, k;
39
40 for (i = 1; i < (sizeof(uintptr_t) << 3); i++) {
41 uintptr_t keys[] = {0, 1,
42 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)) - 1};
43 rtree_t *rtree = rtree_new(i, imalloc, idalloc);
44
45 for (j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) {
46 rtree_set(rtree, keys[j], 1);
47 for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) {
48 assert_u_eq(rtree_get(rtree, keys[k]), 1,
49 "rtree_get() should return previously set "
50 "value and ignore insignificant key bits; "
51 "i=%u, j=%u, k=%u, set key=%#"PRIxPTR", "
52 "get key=%#"PRIxPTR, i, j, k, keys[j],
53 keys[k]);
54 }
55 assert_u_eq(rtree_get(rtree,
56 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i))), 0,
57 "Only leftmost rtree leaf should be set; "
58 "i=%u, j=%u", i, j);
59 rtree_set(rtree, keys[j], 0);
60 }
61
62 rtree_delete(rtree);
63 }
64 }
65 TEST_END
66
TEST_BEGIN(test_rtree_random)67 TEST_BEGIN(test_rtree_random)
68 {
69 unsigned i;
70 sfmt_t *sfmt;
71 #define NSET 100
72 #define SEED 42
73
74 sfmt = init_gen_rand(SEED);
75 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) {
76 rtree_t *rtree = rtree_new(i, imalloc, idalloc);
77 uintptr_t keys[NSET];
78 unsigned j;
79
80 for (j = 0; j < NSET; j++) {
81 keys[j] = (uintptr_t)gen_rand64(sfmt);
82 rtree_set(rtree, keys[j], 1);
83 assert_u_eq(rtree_get(rtree, keys[j]), 1,
84 "rtree_get() should return previously set value");
85 }
86 for (j = 0; j < NSET; j++) {
87 assert_u_eq(rtree_get(rtree, keys[j]), 1,
88 "rtree_get() should return previously set value");
89 }
90
91 for (j = 0; j < NSET; j++) {
92 rtree_set(rtree, keys[j], 0);
93 assert_u_eq(rtree_get(rtree, keys[j]), 0,
94 "rtree_get() should return previously set value");
95 }
96 for (j = 0; j < NSET; j++) {
97 assert_u_eq(rtree_get(rtree, keys[j]), 0,
98 "rtree_get() should return previously set value");
99 }
100
101 rtree_delete(rtree);
102 }
103 fini_gen_rand(sfmt);
104 #undef NSET
105 #undef SEED
106 }
107 TEST_END
108
109 int
main(void)110 main(void)
111 {
112
113 return (test(
114 test_rtree_get_empty,
115 test_rtree_extrema,
116 test_rtree_bits,
117 test_rtree_random));
118 }
119