]> git.proxmox.com Git - rustc.git/blame - src/jemalloc/test/unit/rtree.c
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / jemalloc / test / unit / rtree.c
CommitLineData
1a4d82fc
JJ
1#include "test/jemalloc_test.h"
2
54a0048b
SL
3static rtree_node_elm_t *
4node_alloc(size_t nelms)
5{
6
7 return ((rtree_node_elm_t *)calloc(nelms, sizeof(rtree_node_elm_t)));
8}
9
10static void
11node_dalloc(rtree_node_elm_t *node)
12{
13
14 free(node);
15}
16
1a4d82fc
JJ
17TEST_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}
30TEST_END
31
32TEST_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}
55TEST_END
56
57TEST_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}
92TEST_END
93
94TEST_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}
140TEST_END
141
142int
143main(void)
144{
145
146 return (test(
147 test_rtree_get_empty,
148 test_rtree_extrema,
149 test_rtree_bits,
150 test_rtree_random));
151}