third_party/ulib/jemalloc/include/jemalloc/internal/bitmap_types.h

#ifndef JEMALLOC_INTERNAL_BITMAP_TYPES_H
#define JEMALLOC_INTERNAL_BITMAP_TYPES_H

/* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */
#define	LG_BITMAP_MAXBITS	LG_SLAB_MAXREGS
#define	BITMAP_MAXBITS		(ZU(1) << LG_BITMAP_MAXBITS)

typedef struct bitmap_level_s bitmap_level_t;
typedef struct bitmap_info_s bitmap_info_t;
typedef unsigned long bitmap_t;
#define	LG_SIZEOF_BITMAP	LG_SIZEOF_LONG

/* Number of bits per group. */
#define	LG_BITMAP_GROUP_NBITS		(LG_SIZEOF_BITMAP + 3)
#define	BITMAP_GROUP_NBITS		(1U << LG_BITMAP_GROUP_NBITS)
#define	BITMAP_GROUP_NBITS_MASK		(BITMAP_GROUP_NBITS-1)

/*
 * Do some analysis on how big the bitmap is before we use a tree.  For a brute
 * force linear search, if we would have to call ffs_lu() more than 2^3 times,
 * use a tree instead.
 */
#if LG_BITMAP_MAXBITS - LG_BITMAP_GROUP_NBITS > 3
#  define BITMAP_USE_TREE
#endif

/* Number of groups required to store a given number of bits. */
#define	BITMAP_BITS2GROUPS(nbits)					\
    (((nbits) + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS)

/*
 * Number of groups required at a particular level for a given number of bits.
 */
#define	BITMAP_GROUPS_L0(nbits)						\
    BITMAP_BITS2GROUPS(nbits)
#define	BITMAP_GROUPS_L1(nbits)						\
    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(nbits))
#define	BITMAP_GROUPS_L2(nbits)						\
    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits))))
#define	BITMAP_GROUPS_L3(nbits)						\
    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(		\
	BITMAP_BITS2GROUPS((nbits)))))
#define	BITMAP_GROUPS_L4(nbits)						\
    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(		\
	BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits))))))

/*
 * Assuming the number of levels, number of groups required for a given number
 * of bits.
 */
#define	BITMAP_GROUPS_1_LEVEL(nbits)					\
    BITMAP_GROUPS_L0(nbits)
#define	BITMAP_GROUPS_2_LEVEL(nbits)					\
    (BITMAP_GROUPS_1_LEVEL(nbits) + BITMAP_GROUPS_L1(nbits))
#define	BITMAP_GROUPS_3_LEVEL(nbits)					\
    (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits))
#define	BITMAP_GROUPS_4_LEVEL(nbits)					\
    (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits))
#define	BITMAP_GROUPS_5_LEVEL(nbits)					\
    (BITMAP_GROUPS_4_LEVEL(nbits) + BITMAP_GROUPS_L4(nbits))

/*
 * Maximum number of groups required to support LG_BITMAP_MAXBITS.
 */
#ifdef BITMAP_USE_TREE

#if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 5
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_5_LEVEL(BITMAP_MAXBITS)
#else
#  error "Unsupported bitmap size"
#endif

/*
 * Maximum number of levels possible.  This could be statically computed based
 * on LG_BITMAP_MAXBITS:
 *
 * #define BITMAP_MAX_LEVELS \
 *     (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \
 *     + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
 *
 * However, that would not allow the generic BITMAP_INFO_INITIALIZER() macro, so
 * instead hardcode BITMAP_MAX_LEVELS to the largest number supported by the
 * various cascading macros.  The only additional cost this incurs is some
 * unused trailing entries in bitmap_info_t structures; the bitmaps themselves
 * are not impacted.
 */
#define	BITMAP_MAX_LEVELS	5

#define	BITMAP_INFO_INITIALIZER(nbits) {				\
	/* nbits. */							\
	nbits,								\
	/* nlevels. */							\
	(BITMAP_GROUPS_L0(nbits) > BITMAP_GROUPS_L1(nbits)) +		\
	    (BITMAP_GROUPS_L1(nbits) > BITMAP_GROUPS_L2(nbits)) +	\
	    (BITMAP_GROUPS_L2(nbits) > BITMAP_GROUPS_L3(nbits)) +	\
	    (BITMAP_GROUPS_L3(nbits) > BITMAP_GROUPS_L4(nbits)) + 1,	\
	/* levels. */							\
	{								\
		{0},							\
		{BITMAP_GROUPS_L0(nbits)},				\
		{BITMAP_GROUPS_L1(nbits) + BITMAP_GROUPS_L0(nbits)},	\
		{BITMAP_GROUPS_L2(nbits) + BITMAP_GROUPS_L1(nbits) +	\
		    BITMAP_GROUPS_L0(nbits)},				\
		{BITMAP_GROUPS_L3(nbits) + BITMAP_GROUPS_L2(nbits) +	\
		    BITMAP_GROUPS_L1(nbits) + BITMAP_GROUPS_L0(nbits)},	\
		{BITMAP_GROUPS_L4(nbits) + BITMAP_GROUPS_L3(nbits) +	\
		     BITMAP_GROUPS_L2(nbits) + BITMAP_GROUPS_L1(nbits)	\
		     + BITMAP_GROUPS_L0(nbits)}				\
	}								\
}

#else /* BITMAP_USE_TREE */

#define	BITMAP_GROUPS_MAX	BITMAP_BITS2GROUPS(BITMAP_MAXBITS)

#define	BITMAP_INFO_INITIALIZER(nbits) {				\
	/* nbits. */							\
	nbits,								\
	/* ngroups. */							\
	BITMAP_BITS2GROUPS(nbits)					\
}

#endif /* BITMAP_USE_TREE */

#endif /* JEMALLOC_INTERNAL_BITMAP_TYPES_H */