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(RTREE_HEIGHT_MAX == ((ZU(1) << (LG_SIZEOF_PTR+3)) /
19 RTREE_BITS_PER_LEVEL));
20 assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3));
22 bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL
23 : (bits % RTREE_BITS_PER_LEVEL);
24 if (bits > bits_in_leaf) {
25 height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL;
26 if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits)
30 assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits);
33 rtree->dalloc = dalloc;
34 rtree->height = height;
37 rtree->levels[0].subtree = NULL;
38 rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL :
40 rtree->levels[0].cumbits = rtree->levels[0].bits;
41 /* Interior levels. */
42 for (i = 1; i < height-1; i++) {
43 rtree->levels[i].subtree = NULL;
44 rtree->levels[i].bits = RTREE_BITS_PER_LEVEL;
45 rtree->levels[i].cumbits = rtree->levels[i-1].cumbits +
50 rtree->levels[height-1].subtree = NULL;
51 rtree->levels[height-1].bits = bits_in_leaf;
52 rtree->levels[height-1].cumbits = bits;
55 /* Compute lookup table to be used by rtree_start_level(). */
56 for (i = 0; i < RTREE_HEIGHT_MAX; i++) {
57 rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height -
65 rtree_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level)
68 if (level + 1 < rtree->height) {
71 nchildren = ZU(1) << rtree->levels[level].bits;
72 for (i = 0; i < nchildren; i++) {
73 rtree_node_elm_t *child = node[i].child;
75 rtree_delete_subtree(rtree, child, level + 1);
82 rtree_delete(rtree_t *rtree)
86 for (i = 0; i < rtree->height; i++) {
87 rtree_node_elm_t *subtree = rtree->levels[i].subtree;
89 rtree_delete_subtree(rtree, subtree, i);
93 static rtree_node_elm_t *
94 rtree_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp)
96 rtree_node_elm_t *node;
98 if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) {
100 * Another thread is already in the process of initializing.
101 * Spin-wait until initialization is complete.
105 node = atomic_read_p((void **)elmp);
106 } while (node == RTREE_NODE_INITIALIZING);
108 node = rtree->alloc(ZU(1) << rtree->levels[level].bits);
111 atomic_write_p((void **)elmp, node);
118 rtree_subtree_read_hard(rtree_t *rtree, unsigned level)
121 return (rtree_node_init(rtree, level, &rtree->levels[level].subtree));
125 rtree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level)
128 return (rtree_node_init(rtree, level, &elm->child));