1#define	JEMALLOC_BITMAP_C_
2#include "jemalloc/internal/jemalloc_internal.h"
3
4/******************************************************************************/
5/* Function prototypes for non-inline static functions. */
6
7static size_t	bits2groups(size_t nbits);
8
9/******************************************************************************/
10
11static size_t
12bits2groups(size_t nbits)
13{
14
15	return ((nbits >> LG_BITMAP_GROUP_NBITS) +
16	    !!(nbits & BITMAP_GROUP_NBITS_MASK));
17}
18
19void
20bitmap_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
47size_t
48bitmap_info_ngroups(const bitmap_info_t *binfo)
49{
50
51	return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP);
52}
53
54size_t
55bitmap_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
63void
64bitmap_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}
91