bitmap.c revision 234370
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