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 ((rtree_node_elm_t *)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 assert_false(rtree_set(&rtree, 0, &node_a),
43 "Unexpected rtree_set() failure");
44 assert_ptr_eq(rtree_get(&rtree, 0, true), &node_a,
45 "rtree_get() should return previously set value");
46
47 assert_false(rtree_set(&rtree, ~((uintptr_t)0), &node_b),
48 "Unexpected rtree_set() failure");
49 assert_ptr_eq(rtree_get(&rtree, ~((uintptr_t)0), true), &node_b,
50 "rtree_get() should return previously set value");
51
52 rtree_delete(&rtree);
53 }
54 }
55 TEST_END
56
TEST_BEGIN(test_rtree_bits)57 TEST_BEGIN(test_rtree_bits)
58 {
59 unsigned i, j, k;
60
61 for (i = 1; i < (sizeof(uintptr_t) << 3); i++) {
62 uintptr_t keys[] = {0, 1,
63 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)) - 1};
64 extent_node_t node;
65 rtree_t rtree;
66
67 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
68 "Unexpected rtree_new() failure");
69
70 for (j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) {
71 assert_false(rtree_set(&rtree, keys[j], &node),
72 "Unexpected rtree_set() failure");
73 for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) {
74 assert_ptr_eq(rtree_get(&rtree, keys[k], true),
75 &node, "rtree_get() should return "
76 "previously set value and ignore "
77 "insignificant key bits; i=%u, j=%u, k=%u, "
78 "set key=%#"FMTxPTR", get key=%#"FMTxPTR, i,
79 j, k, keys[j], keys[k]);
80 }
81 assert_ptr_null(rtree_get(&rtree,
82 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)), false),
83 "Only leftmost rtree leaf should be set; "
84 "i=%u, j=%u", i, j);
85 assert_false(rtree_set(&rtree, keys[j], NULL),
86 "Unexpected rtree_set() failure");
87 }
88
89 rtree_delete(&rtree);
90 }
91 }
92 TEST_END
93
TEST_BEGIN(test_rtree_random)94 TEST_BEGIN(test_rtree_random)
95 {
96 unsigned i;
97 sfmt_t *sfmt;
98 #define NSET 16
99 #define SEED 42
100
101 sfmt = init_gen_rand(SEED);
102 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) {
103 uintptr_t keys[NSET];
104 extent_node_t node;
105 unsigned j;
106 rtree_t rtree;
107
108 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
109 "Unexpected rtree_new() failure");
110
111 for (j = 0; j < NSET; j++) {
112 keys[j] = (uintptr_t)gen_rand64(sfmt);
113 assert_false(rtree_set(&rtree, keys[j], &node),
114 "Unexpected rtree_set() failure");
115 assert_ptr_eq(rtree_get(&rtree, keys[j], true), &node,
116 "rtree_get() should return previously set value");
117 }
118 for (j = 0; j < NSET; j++) {
119 assert_ptr_eq(rtree_get(&rtree, keys[j], true), &node,
120 "rtree_get() should return previously set value");
121 }
122
123 for (j = 0; j < NSET; j++) {
124 assert_false(rtree_set(&rtree, keys[j], NULL),
125 "Unexpected rtree_set() failure");
126 assert_ptr_null(rtree_get(&rtree, keys[j], true),
127 "rtree_get() should return previously set value");
128 }
129 for (j = 0; j < NSET; j++) {
130 assert_ptr_null(rtree_get(&rtree, keys[j], true),
131 "rtree_get() should return previously set value");
132 }
133
134 rtree_delete(&rtree);
135 }
136 fini_gen_rand(sfmt);
137 #undef NSET
138 #undef SEED
139 }
140 TEST_END
141
142 int
main(void)143 main(void)
144 {
145
146 return (test(
147 test_rtree_get_empty,
148 test_rtree_extrema,
149 test_rtree_bits,
150 test_rtree_random));
151 }
152