git.saurik.com Git - redis.git/blame_incremental

... / ...

Commit	Line	Data
	1	#define JEMALLOC_BITMAP_C_
	2	#include "jemalloc/internal/jemalloc_internal.h"
	3
	4	/******************************************************************************/
	5	/* Function prototypes for non-inline static functions. */
	6
	7	static size_t bits2groups(size_t nbits);
	8
	9	/******************************************************************************/
	10
	11	static size_t
	12	bits2groups(size_t nbits)
	13	{
	14
	15	return ((nbits >> LG_BITMAP_GROUP_NBITS) +
	16	!!(nbits & BITMAP_GROUP_NBITS_MASK));
	17	}
	18
	19	void
	20	bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
	21	{
	22	unsigned i;
	23	size_t group_count;
	24
	25	assert(nbits > 0);
	26	assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
	27
	28	/*
	29	* Compute the number of groups necessary to store nbits bits, and
	30	* progressively work upward through the levels until reaching a level
	31	* that requires only one group.
	32	*/
	33	binfo->levels[0].group_offset = 0;
	34	group_count = bits2groups(nbits);
	35	for (i = 1; group_count > 1; i++) {
	36	assert(i < BITMAP_MAX_LEVELS);
	37	binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
	38	+ group_count;
	39	group_count = bits2groups(group_count);
	40	}
	41	binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
	42	+ group_count;
	43	binfo->nlevels = i;
	44	binfo->nbits = nbits;
	45	}
	46
	47	size_t
	48	bitmap_info_ngroups(const bitmap_info_t *binfo)
	49	{
	50
	51	return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP);
	52	}
	53
	54	size_t
	55	bitmap_size(size_t nbits)
	56	{
	57	bitmap_info_t binfo;
	58
	59	bitmap_info_init(&binfo, nbits);
	60	return (bitmap_info_ngroups(&binfo));
	61	}
	62
	63	void
	64	bitmap_init(bitmap_t bitmap, const bitmap_info_t binfo)
	65	{
	66	size_t extra;
	67	unsigned i;
	68
	69	/*
	70	* Bits are actually inverted with regard to the external bitmap
	71	* interface, so the bitmap starts out with all 1 bits, except for
	72	* trailing unused bits (if any). Note that each group uses bit 0 to
	73	* correspond to the first logical bit in the group, so extra bits
	74	* are the most significant bits of the last group.
	75	*/
	76	memset(bitmap, 0xffU, binfo->levels[binfo->nlevels].group_offset <<
	77	LG_SIZEOF_BITMAP);
	78	extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
	79	& BITMAP_GROUP_NBITS_MASK;
	80	if (extra != 0)
	81	bitmap[binfo->levels[1].group_offset - 1] >>= extra;
	82	for (i = 1; i < binfo->nlevels; i++) {
	83	size_t group_count = binfo->levels[i].group_offset -
	84	binfo->levels[i-1].group_offset;
	85	extra = (BITMAP_GROUP_NBITS - (group_count &
	86	BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK;
	87	if (extra != 0)
	88	bitmap[binfo->levels[i+1].group_offset - 1] >>= extra;
	89	}
	90	}