rtree.c revision 261071 
1#define	JEMALLOC_RTREE_C_
2#include "jemalloc/internal/jemalloc_internal.h"
3
4rtree_t *
5rtree_new(unsigned bits, rtree_alloc_t *alloc, rtree_dalloc_t *dalloc)
6{
7	rtree_t *ret;
8	unsigned bits_per_level, bits_in_leaf, height, i;
9
10	assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3));
11
12	bits_per_level = ffs(pow2_ceil((RTREE_NODESIZE / sizeof(void *)))) - 1;
13	bits_in_leaf = ffs(pow2_ceil((RTREE_NODESIZE / sizeof(uint8_t)))) - 1;
14	if (bits > bits_in_leaf) {
15		height = 1 + (bits - bits_in_leaf) / bits_per_level;
16		if ((height-1) * bits_per_level + bits_in_leaf != bits)
17			height++;
18	} else {
19		height = 1;
20	}
21	assert((height-1) * bits_per_level + bits_in_leaf >= bits);
22
23	ret = (rtree_t*)alloc(offsetof(rtree_t, level2bits) +
24	    (sizeof(unsigned) * height));
25	if (ret == NULL)
26		return (NULL);
27	memset(ret, 0, offsetof(rtree_t, level2bits) + (sizeof(unsigned) *
28	    height));
29
30	ret->alloc = alloc;
31	ret->dalloc = dalloc;
32	if (malloc_mutex_init(&ret->mutex)) {
33		if (dalloc != NULL)
34			dalloc(ret);
35		return (NULL);
36	}
37	ret->height = height;
38	if (height > 1) {
39		if ((height-1) * bits_per_level + bits_in_leaf > bits) {
40			ret->level2bits[0] = (bits - bits_in_leaf) %
41			    bits_per_level;
42		} else
43			ret->level2bits[0] = bits_per_level;
44		for (i = 1; i < height-1; i++)
45			ret->level2bits[i] = bits_per_level;
46		ret->level2bits[height-1] = bits_in_leaf;
47	} else
48		ret->level2bits[0] = bits;
49
50	ret->root = (void**)alloc(sizeof(void *) << ret->level2bits[0]);
51	if (ret->root == NULL) {
52		if (dalloc != NULL)
53			dalloc(ret);
54		return (NULL);
55	}
56	memset(ret->root, 0, sizeof(void *) << ret->level2bits[0]);
57
58	return (ret);
59}
60
61static void
62rtree_delete_subtree(rtree_t *rtree, void **node, unsigned level)
63{
64
65	if (level < rtree->height - 1) {
66		size_t nchildren, i;
67
68		nchildren = ZU(1) << rtree->level2bits[level];
69		for (i = 0; i < nchildren; i++) {
70			void **child = (void **)node[i];
71			if (child != NULL)
72				rtree_delete_subtree(rtree, child, level + 1);
73		}
74	}
75	rtree->dalloc(node);
76}
77
78void
79rtree_delete(rtree_t *rtree)
80{
81
82	rtree_delete_subtree(rtree, rtree->root, 0);
83	rtree->dalloc(rtree);
84}
85
86void
87rtree_prefork(rtree_t *rtree)
88{
89
90	malloc_mutex_prefork(&rtree->mutex);
91}
92
93void
94rtree_postfork_parent(rtree_t *rtree)
95{
96
97	malloc_mutex_postfork_parent(&rtree->mutex);
98}
99
100void
101rtree_postfork_child(rtree_t *rtree)
102{
103
104	malloc_mutex_postfork_child(&rtree->mutex);
105}
106