1 #ifndef JEMALLOC_INTERNAL_RTREE_TYPES_H
2 #define JEMALLOC_INTERNAL_RTREE_TYPES_H
3 
4 /*
5  * This radix tree implementation is tailored to the singular purpose of
6  * associating metadata with extents that are currently owned by jemalloc.
7  *
8  *******************************************************************************
9  */
10 
11 typedef struct rtree_elm_s rtree_elm_t;
12 typedef struct rtree_elm_witness_s rtree_elm_witness_t;
13 typedef struct rtree_elm_witness_tsd_s rtree_elm_witness_tsd_t;
14 typedef struct rtree_level_s rtree_level_t;
15 typedef struct rtree_ctx_s rtree_ctx_t;
16 typedef struct rtree_s rtree_t;
17 
18 /*
19  * RTREE_BITS_PER_LEVEL must be a power of two that is no larger than the
20  * machine address width.
21  */
22 #define	LG_RTREE_BITS_PER_LEVEL	4
23 #define	RTREE_BITS_PER_LEVEL	(1U << LG_RTREE_BITS_PER_LEVEL)
24 /* Maximum rtree height. */
25 #define	RTREE_HEIGHT_MAX						\
26     ((1U << (LG_SIZEOF_PTR+3)) / RTREE_BITS_PER_LEVEL)
27 
28 #define	RTREE_CTX_INITIALIZER	{					\
29 	false,								\
30 	0,								\
31 	0,								\
32 	{NULL /* C initializes all trailing elements to NULL. */}	\
33 }
34 
35 /*
36  * Maximum number of concurrently acquired elements per thread.  This controls
37  * how many witness_t structures are embedded in tsd.  Ideally rtree_elm_t would
38  * have a witness_t directly embedded, but that would dramatically bloat the
39  * tree.  This must contain enough entries to e.g. coalesce two extents.
40  */
41 #define	RTREE_ELM_ACQUIRE_MAX	4
42 
43 /* Initializers for rtree_elm_witness_tsd_t. */
44 #define	RTREE_ELM_WITNESS_INITIALIZER {					\
45 	NULL,								\
46 	WITNESS_INITIALIZER("rtree_elm", WITNESS_RANK_RTREE_ELM)	\
47 }
48 
49 #define	RTREE_ELM_WITNESS_TSD_INITIALIZER {				\
50 	{								\
51 		RTREE_ELM_WITNESS_INITIALIZER,				\
52 		RTREE_ELM_WITNESS_INITIALIZER,				\
53 		RTREE_ELM_WITNESS_INITIALIZER,				\
54 		RTREE_ELM_WITNESS_INITIALIZER				\
55 	}								\
56 }
57 
58 #endif /* JEMALLOC_INTERNAL_RTREE_TYPES_H */
59