1234370Sjasone#define JEMALLOC_RTREE_C_ 2234370Sjasone#include "jemalloc/internal/jemalloc_internal.h" 3234370Sjasone 4286866Sjasonestatic unsigned 5286866Sjasonehmin(unsigned ha, unsigned hb) 6234370Sjasone{ 7234370Sjasone 8286866Sjasone return (ha < hb ? ha : hb); 9286866Sjasone} 10286866Sjasone 11286866Sjasone/* Only the most significant bits of keys passed to rtree_[gs]et() are used. */ 12286866Sjasonebool 13286866Sjasonertree_new(rtree_t *rtree, unsigned bits, rtree_node_alloc_t *alloc, 14286866Sjasone rtree_node_dalloc_t *dalloc) 15286866Sjasone{ 16286866Sjasone unsigned bits_in_leaf, height, i; 17286866Sjasone 18299587Sjasone assert(RTREE_HEIGHT_MAX == ((ZU(1) << (LG_SIZEOF_PTR+3)) / 19299587Sjasone RTREE_BITS_PER_LEVEL)); 20261071Sjasone assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3)); 21261071Sjasone 22286866Sjasone bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL 23286866Sjasone : (bits % RTREE_BITS_PER_LEVEL); 24261071Sjasone if (bits > bits_in_leaf) { 25286866Sjasone height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL; 26286866Sjasone if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits) 27261071Sjasone height++; 28286866Sjasone } else 29261071Sjasone height = 1; 30286866Sjasone assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits); 31234370Sjasone 32286866Sjasone rtree->alloc = alloc; 33286866Sjasone rtree->dalloc = dalloc; 34286866Sjasone rtree->height = height; 35234370Sjasone 36286866Sjasone /* Root level. */ 37286866Sjasone rtree->levels[0].subtree = NULL; 38286866Sjasone rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL : 39286866Sjasone bits_in_leaf; 40286866Sjasone rtree->levels[0].cumbits = rtree->levels[0].bits; 41286866Sjasone /* Interior levels. */ 42286866Sjasone for (i = 1; i < height-1; i++) { 43286866Sjasone rtree->levels[i].subtree = NULL; 44286866Sjasone rtree->levels[i].bits = RTREE_BITS_PER_LEVEL; 45286866Sjasone rtree->levels[i].cumbits = rtree->levels[i-1].cumbits + 46286866Sjasone RTREE_BITS_PER_LEVEL; 47234370Sjasone } 48286866Sjasone /* Leaf level. */ 49261071Sjasone if (height > 1) { 50286866Sjasone rtree->levels[height-1].subtree = NULL; 51286866Sjasone rtree->levels[height-1].bits = bits_in_leaf; 52286866Sjasone rtree->levels[height-1].cumbits = bits; 53286866Sjasone } 54234370Sjasone 55286866Sjasone /* Compute lookup table to be used by rtree_start_level(). */ 56286866Sjasone for (i = 0; i < RTREE_HEIGHT_MAX; i++) { 57286866Sjasone rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height - 58286866Sjasone 1); 59234370Sjasone } 60234370Sjasone 61286866Sjasone return (false); 62234370Sjasone} 63242844Sjasone 64261071Sjasonestatic void 65286866Sjasonertree_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level) 66261071Sjasone{ 67261071Sjasone 68286866Sjasone if (level + 1 < rtree->height) { 69261071Sjasone size_t nchildren, i; 70261071Sjasone 71286866Sjasone nchildren = ZU(1) << rtree->levels[level].bits; 72261071Sjasone for (i = 0; i < nchildren; i++) { 73286866Sjasone rtree_node_elm_t *child = node[i].child; 74261071Sjasone if (child != NULL) 75261071Sjasone rtree_delete_subtree(rtree, child, level + 1); 76261071Sjasone } 77261071Sjasone } 78261071Sjasone rtree->dalloc(node); 79261071Sjasone} 80261071Sjasone 81242844Sjasonevoid 82261071Sjasonertree_delete(rtree_t *rtree) 83261071Sjasone{ 84286866Sjasone unsigned i; 85261071Sjasone 86286866Sjasone for (i = 0; i < rtree->height; i++) { 87286866Sjasone rtree_node_elm_t *subtree = rtree->levels[i].subtree; 88286866Sjasone if (subtree != NULL) 89286866Sjasone rtree_delete_subtree(rtree, subtree, i); 90286866Sjasone } 91261071Sjasone} 92261071Sjasone 93286866Sjasonestatic rtree_node_elm_t * 94286866Sjasonertree_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp) 95242844Sjasone{ 96286866Sjasone rtree_node_elm_t *node; 97242844Sjasone 98286866Sjasone if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) { 99286866Sjasone /* 100286866Sjasone * Another thread is already in the process of initializing. 101286866Sjasone * Spin-wait until initialization is complete. 102286866Sjasone */ 103286866Sjasone do { 104286866Sjasone CPU_SPINWAIT; 105286866Sjasone node = atomic_read_p((void **)elmp); 106286866Sjasone } while (node == RTREE_NODE_INITIALIZING); 107286866Sjasone } else { 108286866Sjasone node = rtree->alloc(ZU(1) << rtree->levels[level].bits); 109286866Sjasone if (node == NULL) 110286866Sjasone return (NULL); 111286866Sjasone atomic_write_p((void **)elmp, node); 112286866Sjasone } 113286866Sjasone 114286866Sjasone return (node); 115242844Sjasone} 116242844Sjasone 117286866Sjasonertree_node_elm_t * 118286866Sjasonertree_subtree_read_hard(rtree_t *rtree, unsigned level) 119242844Sjasone{ 120242844Sjasone 121286866Sjasone return (rtree_node_init(rtree, level, &rtree->levels[level].subtree)); 122242844Sjasone} 123242844Sjasone 124286866Sjasonertree_node_elm_t * 125286866Sjasonertree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level) 126242844Sjasone{ 127242844Sjasone 128286866Sjasone return (rtree_node_init(rtree, level, &elm->child)); 129242844Sjasone} 130