1 #define JEMALLOC_RTREE_C_ 2 #include "jemalloc/internal/jemalloc_internal.h" 3 4 rtree_t * 5 rtree_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 61 static void 62 rtree_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 78 void 79 rtree_delete(rtree_t *rtree) 80 { 81 82 rtree_delete_subtree(rtree, rtree->root, 0); 83 rtree->dalloc(rtree); 84 } 85 86 void 87 rtree_prefork(rtree_t *rtree) 88 { 89 90 malloc_mutex_prefork(&rtree->mutex); 91 } 92 93 void 94 rtree_postfork_parent(rtree_t *rtree) 95 { 96 97 malloc_mutex_postfork_parent(&rtree->mutex); 98 } 99 100 void 101 rtree_postfork_child(rtree_t *rtree) 102 { 103 104 malloc_mutex_postfork_child(&rtree->mutex); 105 } 106