1 #define JEMALLOC_BITMAP_C_
2 #include "jemalloc/internal/jemalloc_internal.h"
4 /******************************************************************************/
7 bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
13 assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
16 * Compute the number of groups necessary to store nbits bits, and
17 * progressively work upward through the levels until reaching a level
18 * that requires only one group.
20 binfo->levels[0].group_offset = 0;
21 group_count = BITMAP_BITS2GROUPS(nbits);
22 for (i = 1; group_count > 1; i++) {
23 assert(i < BITMAP_MAX_LEVELS);
24 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
26 group_count = BITMAP_BITS2GROUPS(group_count);
28 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
30 assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX);
36 bitmap_info_ngroups(const bitmap_info_t *binfo)
39 return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP);
43 bitmap_size(size_t nbits)
47 bitmap_info_init(&binfo, nbits);
48 return (bitmap_info_ngroups(&binfo));
52 bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
58 * Bits are actually inverted with regard to the external bitmap
59 * interface, so the bitmap starts out with all 1 bits, except for
60 * trailing unused bits (if any). Note that each group uses bit 0 to
61 * correspond to the first logical bit in the group, so extra bits
62 * are the most significant bits of the last group.
64 memset(bitmap, 0xffU, binfo->levels[binfo->nlevels].group_offset <<
66 extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
67 & BITMAP_GROUP_NBITS_MASK;
69 bitmap[binfo->levels[1].group_offset - 1] >>= extra;
70 for (i = 1; i < binfo->nlevels; i++) {
71 size_t group_count = binfo->levels[i].group_offset -
72 binfo->levels[i-1].group_offset;
73 extra = (BITMAP_GROUP_NBITS - (group_count &
74 BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK;
76 bitmap[binfo->levels[i+1].group_offset - 1] >>= extra;