contrib/jemalloc/src/bitmap.c

   1 #define JEMALLOC_BITMAP_C_
   2 #include "jemalloc/internal/jemalloc_internal.h"
   3
   4 /******************************************************************************/
   5 /* Function prototypes for non-inline static functions. */
   6
   7 static size_t   bits2groups(size_t nbits);
   8
   9 /******************************************************************************/
  10
  11 static size_t
  12 bits2groups(size_t nbits)
  13 {
  14
  15         return ((nbits >> LG_BITMAP_GROUP_NBITS) +
  16             !!(nbits & BITMAP_GROUP_NBITS_MASK));
  17 }
  18
  19 void
  20 bitmap_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
  47 size_t
  48 bitmap_info_ngroups(const bitmap_info_t *binfo)
  49 {
  50
  51         return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP);
  52 }
  53
  54 size_t
  55 bitmap_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
  63 void
  64 bitmap_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 }