contrib/jemalloc/src/bitmap.c

   1 #define JEMALLOC_BITMAP_C_
   2 #include "jemalloc/internal/jemalloc_internal.h"
   3
   4 /******************************************************************************/
   5
   6 void
   7 bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
   8 {
   9         unsigned i;
  10         size_t group_count;
  11
  12         assert(nbits > 0);
  13         assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
  14
  15         /*
  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.
  19          */
  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
  25                     + group_count;
  26                 group_count = BITMAP_BITS2GROUPS(group_count);
  27         }
  28         binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
  29             + group_count;
  30         assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX);
  31         binfo->nlevels = i;
  32         binfo->nbits = nbits;
  33 }
  34
  35 size_t
  36 bitmap_info_ngroups(const bitmap_info_t *binfo)
  37 {
  38
  39         return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP);
  40 }
  41
  42 size_t
  43 bitmap_size(size_t nbits)
  44 {
  45         bitmap_info_t binfo;
  46
  47         bitmap_info_init(&binfo, nbits);
  48         return (bitmap_info_ngroups(&binfo));
  49 }
  50
  51 void
  52 bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
  53 {
  54         size_t extra;
  55         unsigned i;
  56
  57         /*
  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.
  63          */
  64         memset(bitmap, 0xffU, binfo->levels[binfo->nlevels].group_offset <<
  65             LG_SIZEOF_BITMAP);
  66         extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
  67             & BITMAP_GROUP_NBITS_MASK;
  68         if (extra != 0)
  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;
  75                 if (extra != 0)
  76                         bitmap[binfo->levels[i+1].group_offset - 1] >>= extra;
  77         }
  78 }