memory/jemalloc/src/src/bitmap.c
 author Nicholas D. Matsakis Tue, 11 Mar 2014 13:23:24 -0400 changeset 187335 4903226b4f2ff4f6c44fe08e91e5dff0e163741d parent 184501 f37de5ce263d5739202ef7102abf1c8e0cada212 child 220051 b5b1a8e8aee4c94b1dc2e60e751343afdeb6f72c permissions -rw-r--r--
Bug 973238 Part 6 -- Consult prototype rather than typed object addendum r=bhackett
```
#define	JEMALLOC_BITMAP_C_
#include "jemalloc/internal/jemalloc_internal.h"

/******************************************************************************/
/* Function prototypes for non-inline static functions. */

static size_t	bits2groups(size_t nbits);

/******************************************************************************/

static size_t
bits2groups(size_t nbits)
{

return ((nbits >> LG_BITMAP_GROUP_NBITS) +
}

void
bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
{
unsigned i;
size_t group_count;

assert(nbits > 0);
assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));

/*
* Compute the number of groups necessary to store nbits bits, and
* progressively work upward through the levels until reaching a level
* that requires only one group.
*/
binfo->levels[0].group_offset = 0;
group_count = bits2groups(nbits);
for (i = 1; group_count > 1; i++) {
assert(i < BITMAP_MAX_LEVELS);
binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
+ group_count;
group_count = bits2groups(group_count);
}
binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
+ group_count;
binfo->nlevels = i;
binfo->nbits = nbits;
}

size_t
bitmap_info_ngroups(const bitmap_info_t *binfo)
{

return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP);
}

size_t
bitmap_size(size_t nbits)
{
bitmap_info_t binfo;

bitmap_info_init(&binfo, nbits);
return (bitmap_info_ngroups(&binfo));
}

void
bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
{
size_t extra;
unsigned i;

/*
* Bits are actually inverted with regard to the external bitmap
* interface, so the bitmap starts out with all 1 bits, except for
* trailing unused bits (if any).  Note that each group uses bit 0 to
* correspond to the first logical bit in the group, so extra bits
* are the most significant bits of the last group.
*/
memset(bitmap, 0xffU, binfo->levels[binfo->nlevels].group_offset <<
LG_SIZEOF_BITMAP);
extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))