1*a4bd5210SJason Evans #define JEMALLOC_RTREE_C_ 2*a4bd5210SJason Evans #include "jemalloc/internal/jemalloc_internal.h" 3*a4bd5210SJason Evans 4*a4bd5210SJason Evans rtree_t * 5*a4bd5210SJason Evans rtree_new(unsigned bits) 6*a4bd5210SJason Evans { 7*a4bd5210SJason Evans rtree_t *ret; 8*a4bd5210SJason Evans unsigned bits_per_level, height, i; 9*a4bd5210SJason Evans 10*a4bd5210SJason Evans bits_per_level = ffs(pow2_ceil((RTREE_NODESIZE / sizeof(void *)))) - 1; 11*a4bd5210SJason Evans height = bits / bits_per_level; 12*a4bd5210SJason Evans if (height * bits_per_level != bits) 13*a4bd5210SJason Evans height++; 14*a4bd5210SJason Evans assert(height * bits_per_level >= bits); 15*a4bd5210SJason Evans 16*a4bd5210SJason Evans ret = (rtree_t*)base_alloc(offsetof(rtree_t, level2bits) + 17*a4bd5210SJason Evans (sizeof(unsigned) * height)); 18*a4bd5210SJason Evans if (ret == NULL) 19*a4bd5210SJason Evans return (NULL); 20*a4bd5210SJason Evans memset(ret, 0, offsetof(rtree_t, level2bits) + (sizeof(unsigned) * 21*a4bd5210SJason Evans height)); 22*a4bd5210SJason Evans 23*a4bd5210SJason Evans if (malloc_mutex_init(&ret->mutex)) { 24*a4bd5210SJason Evans /* Leak the rtree. */ 25*a4bd5210SJason Evans return (NULL); 26*a4bd5210SJason Evans } 27*a4bd5210SJason Evans ret->height = height; 28*a4bd5210SJason Evans if (bits_per_level * height > bits) 29*a4bd5210SJason Evans ret->level2bits[0] = bits % bits_per_level; 30*a4bd5210SJason Evans else 31*a4bd5210SJason Evans ret->level2bits[0] = bits_per_level; 32*a4bd5210SJason Evans for (i = 1; i < height; i++) 33*a4bd5210SJason Evans ret->level2bits[i] = bits_per_level; 34*a4bd5210SJason Evans 35*a4bd5210SJason Evans ret->root = (void**)base_alloc(sizeof(void *) << ret->level2bits[0]); 36*a4bd5210SJason Evans if (ret->root == NULL) { 37*a4bd5210SJason Evans /* 38*a4bd5210SJason Evans * We leak the rtree here, since there's no generic base 39*a4bd5210SJason Evans * deallocation. 40*a4bd5210SJason Evans */ 41*a4bd5210SJason Evans return (NULL); 42*a4bd5210SJason Evans } 43*a4bd5210SJason Evans memset(ret->root, 0, sizeof(void *) << ret->level2bits[0]); 44*a4bd5210SJason Evans 45*a4bd5210SJason Evans return (ret); 46*a4bd5210SJason Evans } 47