rtree.c revision b980cc774a9ccb208a82f4e9ccdcc695d06a960a 
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_ptr_null(rtree_get(rtree, 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, (void *)1);
24		assert_ptr_eq(rtree_get(rtree, 0), (void *)1,
25		    "rtree_get() should return previously set value");
26
27		rtree_set(rtree, ~((uintptr_t)0), (void *)1);
28		assert_ptr_eq(rtree_get(rtree, ~((uintptr_t)0)), (void *)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], (void *)1);
47			for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) {
48				assert_ptr_eq(rtree_get(rtree, keys[k]),
49				    (void *)1,
50				    "rtree_get() should return previously set "
51				    "value and ignore insignificant key bits; "
52				    "i=%u, j=%u, k=%u, set key=%#x, "
53				    "get key=%#x", i, j, k, keys[j], keys[k]);
54			}
55			assert_ptr_eq(rtree_get(rtree,
56			    (((uintptr_t)1) << (sizeof(uintptr_t)*8-i))),
57			    (void *)0,
58			    "Only leftmost rtree leaf should be set; "
59			    "i=%u, j=%u", i, j);
60			rtree_set(rtree, keys[j], (void *)0);
61		}
62
63		rtree_delete(rtree);
64	}
65}
66TEST_END
67
68TEST_BEGIN(test_rtree_random)
69{
70	unsigned i;
71	sfmt_t *sfmt;
72#define	NSET 100
73#define	SEED 42
74
75	sfmt = init_gen_rand(SEED);
76	for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) {
77		rtree_t *rtree = rtree_new(i, imalloc, idalloc);
78		uintptr_t keys[NSET];
79		unsigned j;
80
81		for (j = 0; j < NSET; j++) {
82			keys[j] = (uintptr_t)gen_rand64(sfmt);
83			rtree_set(rtree, keys[j], (void *)1);
84			assert_ptr_eq(rtree_get(rtree, keys[j]), (void *)1,
85			    "rtree_get() should return previously set value");
86		}
87		for (j = 0; j < NSET; j++) {
88			assert_ptr_eq(rtree_get(rtree, keys[j]), (void *)1,
89			    "rtree_get() should return previously set value");
90		}
91
92		for (j = 0; j < NSET; j++) {
93			rtree_set(rtree, keys[j], (void *)0);
94			assert_ptr_eq(rtree_get(rtree, keys[j]), (void *)0,
95			    "rtree_get() should return previously set value");
96		}
97		for (j = 0; j < NSET; j++) {
98			assert_ptr_eq(rtree_get(rtree, keys[j]), (void *)0,
99			    "rtree_get() should return previously set value");
100		}
101
102		rtree_delete(rtree);
103	}
104	fini_gen_rand(sfmt);
105#undef NSET
106#undef SEED
107}
108TEST_END
109
110int
111main(void)
112{
113
114	return (test(
115	    test_rtree_get_empty,
116	    test_rtree_extrema,
117	    test_rtree_bits,
118	    test_rtree_random));
119}
120