blob: a56018f88282a611ef683b3d9e6c28c56b0dd53b [file] [log] [blame]
Jason Evanse476f8a2010-01-16 09:53:50 -08001#define JEMALLOC_EXTENT_C_
Jason Evans376b1522010-02-11 14:45:59 -08002#include "jemalloc/internal/jemalloc_internal.h"
Jason Evanse476f8a2010-01-16 09:53:50 -08003
4/******************************************************************************/
5
Jason Evans2cdf07a2016-11-11 21:14:29 -08006/*
7 * Round down to the nearest chunk size that can actually be requested during
8 * normal huge allocation.
9 */
Jason Evans8a03cf02015-05-04 09:58:36 -070010JEMALLOC_INLINE_C size_t
11extent_quantize(size_t size)
12{
Jason Evans2cdf07a2016-11-11 21:14:29 -080013 size_t ret;
14 szind_t ind;
Jason Evans8a03cf02015-05-04 09:58:36 -070015
Jason Evans2cdf07a2016-11-11 21:14:29 -080016 assert(size > 0);
17
18 ind = size2index(size + 1);
Jason Evans1aeea0f2016-11-11 22:46:55 -080019 if (ind == 0) {
20 /* Avoid underflow. */
21 return (index2size(0));
Jason Evans2cdf07a2016-11-11 21:14:29 -080022 }
23 ret = index2size(ind - 1);
24 assert(ret <= size);
25 return (ret);
Jason Evans8a03cf02015-05-04 09:58:36 -070026}
27
Jason Evansaf1f5922014-10-30 16:38:08 -070028JEMALLOC_INLINE_C int
Jason Evans5c77af92016-11-14 18:27:23 -080029extent_sz_comp(const extent_node_t *a, const extent_node_t *b)
Jason Evanse476f8a2010-01-16 09:53:50 -080030{
Jason Evans8a03cf02015-05-04 09:58:36 -070031 size_t a_qsize = extent_quantize(extent_node_size_get(a));
32 size_t b_qsize = extent_quantize(extent_node_size_get(b));
Jason Evanse476f8a2010-01-16 09:53:50 -080033
Jason Evans5c77af92016-11-14 18:27:23 -080034 return ((a_qsize > b_qsize) - (a_qsize < b_qsize));
Jason Evanse476f8a2010-01-16 09:53:50 -080035}
36
Jason Evans5c77af92016-11-14 18:27:23 -080037JEMALLOC_INLINE_C int
38extent_sn_comp(const extent_node_t *a, const extent_node_t *b)
39{
40 uint64_t a_sn = (uintptr_t)extent_node_sn_get(a);
41 uint64_t b_sn = (uintptr_t)extent_node_sn_get(b);
42
43 return ((a_sn > b_sn) - (a_sn < b_sn));
44}
Jason Evanse476f8a2010-01-16 09:53:50 -080045
Jason Evansaf1f5922014-10-30 16:38:08 -070046JEMALLOC_INLINE_C int
Joshua Kahn13b40152015-09-18 16:58:17 -040047extent_ad_comp(const extent_node_t *a, const extent_node_t *b)
Jason Evanse476f8a2010-01-16 09:53:50 -080048{
Jason Evansee41ad42015-02-15 18:04:46 -080049 uintptr_t a_addr = (uintptr_t)extent_node_addr_get(a);
50 uintptr_t b_addr = (uintptr_t)extent_node_addr_get(b);
Jason Evanse476f8a2010-01-16 09:53:50 -080051
52 return ((a_addr > b_addr) - (a_addr < b_addr));
53}
54
Jason Evans5c77af92016-11-14 18:27:23 -080055JEMALLOC_INLINE_C int
56extent_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. */
73rb_gen(, extent_tree_szsnad_, extent_tree_t, extent_node_t, szsnad_link,
74 extent_szsnad_comp)
75
Jason Evansf3ff7522010-02-28 15:00:18 -080076/* Generate red-black tree functions. */
Jason Evans2195ba42015-02-15 16:43:52 -080077rb_gen(, extent_tree_ad_, extent_tree_t, extent_node_t, ad_link, extent_ad_comp)