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