1 #include "test/jemalloc_test.h"
2
3 static rtree_node_elm_t *
node_alloc(size_t nelms)4 node_alloc(size_t nelms)
5 {
6
7 return (calloc(nelms, sizeof(rtree_node_elm_t)));
8 }
9
10 static void
node_dalloc(rtree_node_elm_t * node)11 node_dalloc(rtree_node_elm_t *node)
12 {
13
14 free(node);
15 }
16
TEST_BEGIN(test_rtree_get_empty)17 TEST_BEGIN(test_rtree_get_empty)
18 {
19 unsigned i;
20
21 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) {
22 rtree_t rtree;
23 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
24 "Unexpected rtree_new() failure");
25 assert_ptr_null(rtree_get(&rtree, 0, false),
26 "rtree_get() should return NULL for empty tree");
27 rtree_delete(&rtree);
28 }
29 }
30 TEST_END
31
TEST_BEGIN(test_rtree_extrema)32 TEST_BEGIN(test_rtree_extrema)
33 {
34 unsigned i;
35 extent_node_t node_a, node_b;
36
37 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) {
38 rtree_t rtree;
39 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
40 "Unexpected rtree_new() failure");
41
42 rtree_set(&rtree, 0, &node_a);
43 assert_ptr_eq(rtree_get(&rtree, 0, true), &node_a,
44 "rtree_get() should return previously set value");
45
46 rtree_set(&rtree, ~((uintptr_t)0), &node_b);
47 assert_ptr_eq(rtree_get(&rtree, ~((uintptr_t)0), true), &node_b,
48 "rtree_get() should return previously set value");
49
50 rtree_delete(&rtree);
51 }
52 }
53 TEST_END
54
TEST_BEGIN(test_rtree_bits)55 TEST_BEGIN(test_rtree_bits)
56 {
57 unsigned i, j, k;
58
59 for (i = 1; i < (sizeof(uintptr_t) << 3); i++) {
60 uintptr_t keys[] = {0, 1,
61 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)) - 1};
62 extent_node_t node;
63 rtree_t rtree;
64
65 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
66 "Unexpected rtree_new() failure");
67
68 for (j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) {
69 rtree_set(&rtree, keys[j], &node);
70 for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) {
71 assert_ptr_eq(rtree_get(&rtree, keys[k], true),
72 &node, "rtree_get() should return "
73 "previously set value and ignore "
74 "insignificant key bits; i=%u, j=%u, k=%u, "
75 "set key=%#"PRIxPTR", get key=%#"PRIxPTR, i,
76 j, k, keys[j], keys[k]);
77 }
78 assert_ptr_null(rtree_get(&rtree,
79 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)), false),
80 "Only leftmost rtree leaf should be set; "
81 "i=%u, j=%u", i, j);
82 rtree_set(&rtree, keys[j], NULL);
83 }
84
85 rtree_delete(&rtree);
86 }
87 }
88 TEST_END
89
TEST_BEGIN(test_rtree_random)90 TEST_BEGIN(test_rtree_random)
91 {
92 unsigned i;
93 sfmt_t *sfmt;
94 #define NSET 16
95 #define SEED 42
96
97 sfmt = init_gen_rand(SEED);
98 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) {
99 uintptr_t keys[NSET];
100 extent_node_t node;
101 unsigned j;
102 rtree_t rtree;
103
104 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
105 "Unexpected rtree_new() failure");
106
107 for (j = 0; j < NSET; j++) {
108 keys[j] = (uintptr_t)gen_rand64(sfmt);
109 rtree_set(&rtree, keys[j], &node);
110 assert_ptr_eq(rtree_get(&rtree, keys[j], true), &node,
111 "rtree_get() should return previously set value");
112 }
113 for (j = 0; j < NSET; j++) {
114 assert_ptr_eq(rtree_get(&rtree, keys[j], true), &node,
115 "rtree_get() should return previously set value");
116 }
117
118 for (j = 0; j < NSET; j++) {
119 rtree_set(&rtree, keys[j], NULL);
120 assert_ptr_null(rtree_get(&rtree, keys[j], true),
121 "rtree_get() should return previously set value");
122 }
123 for (j = 0; j < NSET; j++) {
124 assert_ptr_null(rtree_get(&rtree, keys[j], true),
125 "rtree_get() should return previously set value");
126 }
127
128 rtree_delete(&rtree);
129 }
130 fini_gen_rand(sfmt);
131 #undef NSET
132 #undef SEED
133 }
134 TEST_END
135
136 int
main(void)137 main(void)
138 {
139
140 return (test(
141 test_rtree_get_empty,
142 test_rtree_extrema,
143 test_rtree_bits,
144 test_rtree_random));
145 }
146