• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 #include "test/jemalloc_test.h"
2 
TEST_BEGIN(test_rtree_get_empty)3 TEST_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 }
14 TEST_END
15 
TEST_BEGIN(test_rtree_extrema)16 TEST_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 }
34 TEST_END
35 
TEST_BEGIN(test_rtree_bits)36 TEST_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 }
65 TEST_END
66 
TEST_BEGIN(test_rtree_random)67 TEST_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 }
107 TEST_END
108 
109 int
main(void)110 main(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