1#define	JEMALLOC_RTREE_C_
2#include "jemalloc/internal/jemalloc_internal.h"
3
4static unsigned
5hmin(unsigned ha, unsigned hb)
6{
7
8	return (ha < hb ? ha : hb);
9}
10
11/* Only the most significant bits of keys passed to rtree_[gs]et() are used. */
12bool
13rtree_new(rtree_t *rtree, unsigned bits, rtree_node_alloc_t *alloc,
14    rtree_node_dalloc_t *dalloc)
15{
16	unsigned bits_in_leaf, height, i;
17
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));
21
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)
27			height++;
28	} else
29		height = 1;
30	assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits);
31
32	rtree->alloc = alloc;
33	rtree->dalloc = dalloc;
34	rtree->height = height;
35
36	/* Root level. */
37	rtree->levels[0].subtree = NULL;
38	rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL :
39	    bits_in_leaf;
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 +
46		    RTREE_BITS_PER_LEVEL;
47	}
48	/* Leaf level. */
49	if (height > 1) {
50		rtree->levels[height-1].subtree = NULL;
51		rtree->levels[height-1].bits = bits_in_leaf;
52		rtree->levels[height-1].cumbits = bits;
53	}
54
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 -
58		    1);
59	}
60
61	return (false);
62}
63
64static void
65rtree_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level)
66{
67
68	if (level + 1 < rtree->height) {
69		size_t nchildren, i;
70
71		nchildren = ZU(1) << rtree->levels[level].bits;
72		for (i = 0; i < nchildren; i++) {
73			rtree_node_elm_t *child = node[i].child;
74			if (child != NULL)
75				rtree_delete_subtree(rtree, child, level + 1);
76		}
77	}
78	rtree->dalloc(node);
79}
80
81void
82rtree_delete(rtree_t *rtree)
83{
84	unsigned i;
85
86	for (i = 0; i < rtree->height; i++) {
87		rtree_node_elm_t *subtree = rtree->levels[i].subtree;
88		if (subtree != NULL)
89			rtree_delete_subtree(rtree, subtree, i);
90	}
91}
92
93static rtree_node_elm_t *
94rtree_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp)
95{
96	rtree_node_elm_t *node;
97
98	if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) {
99		/*
100		 * Another thread is already in the process of initializing.
101		 * Spin-wait until initialization is complete.
102		 */
103		do {
104			CPU_SPINWAIT;
105			node = atomic_read_p((void **)elmp);
106		} while (node == RTREE_NODE_INITIALIZING);
107	} else {
108		node = rtree->alloc(ZU(1) << rtree->levels[level].bits);
109		if (node == NULL)
110			return (NULL);
111		atomic_write_p((void **)elmp, node);
112	}
113
114	return (node);
115}
116
117rtree_node_elm_t *
118rtree_subtree_read_hard(rtree_t *rtree, unsigned level)
119{
120
121	return (rtree_node_init(rtree, level, &rtree->levels[level].subtree));
122}
123
124rtree_node_elm_t *
125rtree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level)
126{
127
128	return (rtree_node_init(rtree, level, &elm->child));
129}
130