1#include "test/jemalloc_test.h"
2
3TEST_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}
14TEST_END
15
16TEST_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}
34TEST_END
35
36TEST_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}
65TEST_END
66
67TEST_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}
107TEST_END
108
109int
110main(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