]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | #include "test/jemalloc_test.h" |
2 | ||
54a0048b SL |
3 | static rtree_node_elm_t * |
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 | |
11 | node_dalloc(rtree_node_elm_t *node) | |
12 | { | |
13 | ||
14 | free(node); | |
15 | } | |
16 | ||
1a4d82fc JJ |
17 | TEST_BEGIN(test_rtree_get_empty) |
18 | { | |
19 | unsigned i; | |
20 | ||
21 | for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { | |
54a0048b SL |
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), | |
1a4d82fc | 26 | "rtree_get() should return NULL for empty tree"); |
54a0048b | 27 | rtree_delete(&rtree); |
1a4d82fc JJ |
28 | } |
29 | } | |
30 | TEST_END | |
31 | ||
32 | TEST_BEGIN(test_rtree_extrema) | |
33 | { | |
34 | unsigned i; | |
54a0048b | 35 | extent_node_t node_a, node_b; |
1a4d82fc JJ |
36 | |
37 | for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { | |
54a0048b SL |
38 | rtree_t rtree; |
39 | assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc), | |
40 | "Unexpected rtree_new() failure"); | |
1a4d82fc | 41 | |
54a0048b SL |
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, | |
1a4d82fc JJ |
45 | "rtree_get() should return previously set value"); |
46 | ||
54a0048b SL |
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, | |
1a4d82fc JJ |
50 | "rtree_get() should return previously set value"); |
51 | ||
54a0048b | 52 | rtree_delete(&rtree); |
1a4d82fc JJ |
53 | } |
54 | } | |
55 | TEST_END | |
56 | ||
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}; | |
54a0048b SL |
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"); | |
1a4d82fc JJ |
69 | |
70 | for (j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) { | |
54a0048b SL |
71 | assert_false(rtree_set(&rtree, keys[j], &node), |
72 | "Unexpected rtree_set() failure"); | |
1a4d82fc | 73 | for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) { |
54a0048b SL |
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]); | |
1a4d82fc | 80 | } |
54a0048b SL |
81 | assert_ptr_null(rtree_get(&rtree, |
82 | (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)), false), | |
1a4d82fc JJ |
83 | "Only leftmost rtree leaf should be set; " |
84 | "i=%u, j=%u", i, j); | |
54a0048b SL |
85 | assert_false(rtree_set(&rtree, keys[j], NULL), |
86 | "Unexpected rtree_set() failure"); | |
1a4d82fc JJ |
87 | } |
88 | ||
54a0048b | 89 | rtree_delete(&rtree); |
1a4d82fc JJ |
90 | } |
91 | } | |
92 | TEST_END | |
93 | ||
94 | TEST_BEGIN(test_rtree_random) | |
95 | { | |
96 | unsigned i; | |
97 | sfmt_t *sfmt; | |
54a0048b | 98 | #define NSET 16 |
1a4d82fc JJ |
99 | #define SEED 42 |
100 | ||
101 | sfmt = init_gen_rand(SEED); | |
102 | for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { | |
1a4d82fc | 103 | uintptr_t keys[NSET]; |
54a0048b | 104 | extent_node_t node; |
1a4d82fc | 105 | unsigned j; |
54a0048b SL |
106 | rtree_t rtree; |
107 | ||
108 | assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc), | |
109 | "Unexpected rtree_new() failure"); | |
1a4d82fc JJ |
110 | |
111 | for (j = 0; j < NSET; j++) { | |
112 | keys[j] = (uintptr_t)gen_rand64(sfmt); | |
54a0048b SL |
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, | |
1a4d82fc JJ |
116 | "rtree_get() should return previously set value"); |
117 | } | |
118 | for (j = 0; j < NSET; j++) { | |
54a0048b | 119 | assert_ptr_eq(rtree_get(&rtree, keys[j], true), &node, |
1a4d82fc JJ |
120 | "rtree_get() should return previously set value"); |
121 | } | |
122 | ||
123 | for (j = 0; j < NSET; j++) { | |
54a0048b SL |
124 | assert_false(rtree_set(&rtree, keys[j], NULL), |
125 | "Unexpected rtree_set() failure"); | |
126 | assert_ptr_null(rtree_get(&rtree, keys[j], true), | |
1a4d82fc JJ |
127 | "rtree_get() should return previously set value"); |
128 | } | |
129 | for (j = 0; j < NSET; j++) { | |
54a0048b | 130 | assert_ptr_null(rtree_get(&rtree, keys[j], true), |
1a4d82fc JJ |
131 | "rtree_get() should return previously set value"); |
132 | } | |
133 | ||
54a0048b | 134 | rtree_delete(&rtree); |
1a4d82fc JJ |
135 | } |
136 | fini_gen_rand(sfmt); | |
137 | #undef NSET | |
138 | #undef SEED | |
139 | } | |
140 | TEST_END | |
141 | ||
142 | int | |
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 | } |