1 #define JEMALLOC_EXTENT_C_ 2 #include "jemalloc/internal/jemalloc_internal.h" 3 4 /******************************************************************************/ 5 6 #ifndef JEMALLOC_JET 7 static 8 #endif 9 size_t 10 extent_size_quantize_floor(size_t size) { 11 size_t ret; 12 szind_t ind; 13 14 assert(size > 0); 15 16 ind = size2index(size + 1); 17 if (ind == 0) { 18 /* Avoid underflow. */ 19 return (index2size(0)); 20 } 21 ret = index2size(ind - 1); 22 assert(ret <= size); 23 return (ret); 24 } 25 26 size_t 27 extent_size_quantize_ceil(size_t size) { 28 size_t ret; 29 30 assert(size > 0); 31 32 ret = extent_size_quantize_floor(size); 33 if (ret < size) { 34 /* 35 * Skip a quantization that may have an adequately large extent, 36 * because under-sized extents may be mixed in. This only 37 * happens when an unusual size is requested, i.e. for aligned 38 * allocation, and is just one of several places where linear 39 * search would potentially find sufficiently aligned available 40 * memory somewhere lower. 41 */ 42 ret = index2size(size2index(ret + 1)); 43 } 44 return ret; 45 } 46 47 JEMALLOC_INLINE_C int 48 extent_sz_comp(const extent_node_t *a, const extent_node_t *b) 49 { 50 size_t a_qsize = extent_size_quantize_floor(extent_node_size_get(a)); 51 size_t b_qsize = extent_size_quantize_floor(extent_node_size_get(b)); 52 53 return ((a_qsize > b_qsize) - (a_qsize < b_qsize)); 54 } 55 56 JEMALLOC_INLINE_C int 57 extent_sn_comp(const extent_node_t *a, const extent_node_t *b) 58 { 59 size_t a_sn = extent_node_sn_get(a); 60 size_t b_sn = extent_node_sn_get(b); 61 62 return ((a_sn > b_sn) - (a_sn < b_sn)); 63 } 64 65 JEMALLOC_INLINE_C int 66 extent_ad_comp(const extent_node_t *a, const extent_node_t *b) 67 { 68 uintptr_t a_addr = (uintptr_t)extent_node_addr_get(a); 69 uintptr_t b_addr = (uintptr_t)extent_node_addr_get(b); 70 71 return ((a_addr > b_addr) - (a_addr < b_addr)); 72 } 73 74 JEMALLOC_INLINE_C int 75 extent_szsnad_comp(const extent_node_t *a, const extent_node_t *b) 76 { 77 int ret; 78 79 ret = extent_sz_comp(a, b); 80 if (ret != 0) 81 return (ret); 82 83 ret = extent_sn_comp(a, b); 84 if (ret != 0) 85 return (ret); 86 87 ret = extent_ad_comp(a, b); 88 return (ret); 89 } 90 91 /* Generate red-black tree functions. */ 92 rb_gen(, extent_tree_szsnad_, extent_tree_t, extent_node_t, szsnad_link, 93 extent_szsnad_comp) 94 95 /* Generate red-black tree functions. */ 96 rb_gen(, extent_tree_ad_, extent_tree_t, extent_node_t, ad_link, extent_ad_comp) 97