Lines Matching refs:rtree
15 rtree_new(rtree_t *rtree, unsigned bits) in rtree_new() argument
33 rtree->height = height; in rtree_new()
36 rtree->levels[0].subtree = NULL; in rtree_new()
37 rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL : in rtree_new()
39 rtree->levels[0].cumbits = rtree->levels[0].bits; in rtree_new()
42 rtree->levels[i].subtree = NULL; in rtree_new()
43 rtree->levels[i].bits = RTREE_BITS_PER_LEVEL; in rtree_new()
44 rtree->levels[i].cumbits = rtree->levels[i-1].cumbits + in rtree_new()
49 rtree->levels[height-1].subtree = NULL; in rtree_new()
50 rtree->levels[height-1].bits = bits_in_leaf; in rtree_new()
51 rtree->levels[height-1].cumbits = bits; in rtree_new()
56 rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height - in rtree_new()
59 rtree->start_level[RTREE_HEIGHT_MAX] = 0; in rtree_new()
61 malloc_mutex_init(&rtree->init_lock, "rtree", WITNESS_RANK_RTREE); in rtree_new()
71 rtree_node_alloc(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) in rtree_node_alloc() argument
87 rtree_node_dalloc(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *node) in rtree_node_dalloc() argument
100 rtree_delete_subtree(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *node, in rtree_delete_subtree() argument
103 if (level + 1 < rtree->height) { in rtree_delete_subtree()
106 nchildren = ZU(1) << rtree->levels[level].bits; in rtree_delete_subtree()
110 rtree_delete_subtree(tsdn, rtree, child, level + in rtree_delete_subtree()
115 rtree_node_dalloc(tsdn, rtree, node); in rtree_delete_subtree()
119 rtree_delete(tsdn_t *tsdn, rtree_t *rtree) in rtree_delete() argument
123 for (i = 0; i < rtree->height; i++) { in rtree_delete()
124 rtree_elm_t *subtree = rtree->levels[i].subtree; in rtree_delete()
126 rtree_delete_subtree(tsdn, rtree, subtree, i); in rtree_delete()
132 rtree_node_init(tsdn_t *tsdn, rtree_t *rtree, unsigned level, in rtree_node_init() argument
137 malloc_mutex_lock(tsdn, &rtree->init_lock); in rtree_node_init()
140 node = rtree_node_alloc(tsdn, rtree, ZU(1) << in rtree_node_init()
141 rtree->levels[level].bits); in rtree_node_init()
143 malloc_mutex_unlock(tsdn, &rtree->init_lock); in rtree_node_init()
148 malloc_mutex_unlock(tsdn, &rtree->init_lock); in rtree_node_init()
154 rtree_subtree_read_hard(tsdn_t *tsdn, rtree_t *rtree, unsigned level) in rtree_subtree_read_hard() argument
156 return (rtree_node_init(tsdn, rtree, level, in rtree_subtree_read_hard()
157 &rtree->levels[level].subtree)); in rtree_subtree_read_hard()
161 rtree_child_read_hard(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *elm, in rtree_child_read_hard() argument
164 return (rtree_node_init(tsdn, rtree, level+1, &elm->child)); in rtree_child_read_hard()
244 rtree_elm_witness_acquire(tsdn_t *tsdn, const rtree_t *rtree, uintptr_t key, in rtree_elm_witness_acquire() argument
257 rtree_elm_witness_access(tsdn_t *tsdn, const rtree_t *rtree, in rtree_elm_witness_access() argument
270 rtree_elm_witness_release(tsdn_t *tsdn, const rtree_t *rtree, in rtree_elm_witness_release() argument