]>
git.proxmox.com Git - rustc.git/blob - src/jemalloc/src/rtree.c
1 #define JEMALLOC_RTREE_C_
2 #include "jemalloc/internal/jemalloc_internal.h"
5 hmin(unsigned ha
, unsigned hb
)
8 return (ha
< hb
? ha
: hb
);
11 /* Only the most significant bits of keys passed to rtree_[gs]et() are used. */
13 rtree_new(rtree_t
*rtree
, unsigned bits
, rtree_node_alloc_t
*alloc
,
14 rtree_node_dalloc_t
*dalloc
)
16 unsigned bits_in_leaf
, height
, i
;
18 assert(bits
> 0 && bits
<= (sizeof(uintptr_t) << 3));
20 bits_in_leaf
= (bits
% RTREE_BITS_PER_LEVEL
) == 0 ? RTREE_BITS_PER_LEVEL
21 : (bits
% RTREE_BITS_PER_LEVEL
);
22 if (bits
> bits_in_leaf
) {
23 height
= 1 + (bits
- bits_in_leaf
) / RTREE_BITS_PER_LEVEL
;
24 if ((height
-1) * RTREE_BITS_PER_LEVEL
+ bits_in_leaf
!= bits
)
28 assert((height
-1) * RTREE_BITS_PER_LEVEL
+ bits_in_leaf
== bits
);
31 rtree
->dalloc
= dalloc
;
32 rtree
->height
= height
;
35 rtree
->levels
[0].subtree
= NULL
;
36 rtree
->levels
[0].bits
= (height
> 1) ? RTREE_BITS_PER_LEVEL
:
38 rtree
->levels
[0].cumbits
= rtree
->levels
[0].bits
;
39 /* Interior levels. */
40 for (i
= 1; i
< height
-1; i
++) {
41 rtree
->levels
[i
].subtree
= NULL
;
42 rtree
->levels
[i
].bits
= RTREE_BITS_PER_LEVEL
;
43 rtree
->levels
[i
].cumbits
= rtree
->levels
[i
-1].cumbits
+
48 rtree
->levels
[height
-1].subtree
= NULL
;
49 rtree
->levels
[height
-1].bits
= bits_in_leaf
;
50 rtree
->levels
[height
-1].cumbits
= bits
;
53 /* Compute lookup table to be used by rtree_start_level(). */
54 for (i
= 0; i
< RTREE_HEIGHT_MAX
; i
++) {
55 rtree
->start_level
[i
] = hmin(RTREE_HEIGHT_MAX
- 1 - i
, height
-
63 rtree_delete_subtree(rtree_t
*rtree
, rtree_node_elm_t
*node
, unsigned level
)
66 if (level
+ 1 < rtree
->height
) {
69 nchildren
= ZU(1) << rtree
->levels
[level
].bits
;
70 for (i
= 0; i
< nchildren
; i
++) {
71 rtree_node_elm_t
*child
= node
[i
].child
;
73 rtree_delete_subtree(rtree
, child
, level
+ 1);
80 rtree_delete(rtree_t
*rtree
)
84 for (i
= 0; i
< rtree
->height
; i
++) {
85 rtree_node_elm_t
*subtree
= rtree
->levels
[i
].subtree
;
87 rtree_delete_subtree(rtree
, subtree
, i
);
91 static rtree_node_elm_t
*
92 rtree_node_init(rtree_t
*rtree
, unsigned level
, rtree_node_elm_t
**elmp
)
94 rtree_node_elm_t
*node
;
96 if (atomic_cas_p((void **)elmp
, NULL
, RTREE_NODE_INITIALIZING
)) {
98 * Another thread is already in the process of initializing.
99 * Spin-wait until initialization is complete.
103 node
= atomic_read_p((void **)elmp
);
104 } while (node
== RTREE_NODE_INITIALIZING
);
106 node
= rtree
->alloc(ZU(1) << rtree
->levels
[level
].bits
);
109 atomic_write_p((void **)elmp
, node
);
116 rtree_subtree_read_hard(rtree_t
*rtree
, unsigned level
)
119 return (rtree_node_init(rtree
, level
, &rtree
->levels
[level
].subtree
));
123 rtree_child_read_hard(rtree_t
*rtree
, rtree_node_elm_t
*elm
, unsigned level
)
126 return (rtree_node_init(rtree
, level
, &elm
->child
));