1 #define JEMALLOC_EXTENT_C_
2 #include "jemalloc/internal/jemalloc_internal.h"
3
4 /******************************************************************************/
5
6 /*
7 * Round down to the nearest chunk size that can actually be requested during
8 * normal huge allocation.
9 */
10 JEMALLOC_INLINE_C size_t
extent_quantize(size_t size)11 extent_quantize(size_t size)
12 {
13 size_t ret;
14 szind_t ind;
15
16 assert(size > 0);
17
18 ind = size2index(size + 1);
19 if (ind == 0) {
20 /* Avoid underflow. */
21 return (index2size(0));
22 }
23 ret = index2size(ind - 1);
24 assert(ret <= size);
25 return (ret);
26 }
27
28 JEMALLOC_INLINE_C int
extent_sz_comp(const extent_node_t * a,const extent_node_t * b)29 extent_sz_comp(const extent_node_t *a, const extent_node_t *b)
30 {
31 size_t a_qsize = extent_quantize(extent_node_size_get(a));
32 size_t b_qsize = extent_quantize(extent_node_size_get(b));
33
34 return ((a_qsize > b_qsize) - (a_qsize < b_qsize));
35 }
36
37 JEMALLOC_INLINE_C int
extent_sn_comp(const extent_node_t * a,const extent_node_t * b)38 extent_sn_comp(const extent_node_t *a, const extent_node_t *b)
39 {
40 size_t a_sn = extent_node_sn_get(a);
41 size_t b_sn = extent_node_sn_get(b);
42
43 return ((a_sn > b_sn) - (a_sn < b_sn));
44 }
45
46 JEMALLOC_INLINE_C int
extent_ad_comp(const extent_node_t * a,const extent_node_t * b)47 extent_ad_comp(const extent_node_t *a, const extent_node_t *b)
48 {
49 uintptr_t a_addr = (uintptr_t)extent_node_addr_get(a);
50 uintptr_t b_addr = (uintptr_t)extent_node_addr_get(b);
51
52 return ((a_addr > b_addr) - (a_addr < b_addr));
53 }
54
55 JEMALLOC_INLINE_C int
extent_szsnad_comp(const extent_node_t * a,const extent_node_t * b)56 extent_szsnad_comp(const extent_node_t *a, const extent_node_t *b)
57 {
58 int ret;
59
60 ret = extent_sz_comp(a, b);
61 if (ret != 0)
62 return (ret);
63
64 ret = extent_sn_comp(a, b);
65 if (ret != 0)
66 return (ret);
67
68 ret = extent_ad_comp(a, b);
69 return (ret);
70 }
71
72 /* Generate red-black tree functions. */
73 rb_gen(, extent_tree_szsnad_, extent_tree_t, extent_node_t, szsnad_link,
74 extent_szsnad_comp)
75
76 /* Generate red-black tree functions. */
77 rb_gen(, extent_tree_ad_, extent_tree_t, extent_node_t, ad_link, extent_ad_comp)
78