contrib/jemalloc/src/bitmap.c

   1 #define JEMALLOC_BITMAP_C_
   2 #include "jemalloc/internal/jemalloc_internal.h"
   3
   4 /******************************************************************************/
   5
   6 #ifdef USE_TREE
   7
   8 void
   9 bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
  10 {
  11         unsigned i;
  12         size_t group_count;
  13
  14         assert(nbits > 0);
  15         assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
  16
  17         /*
  18          * Compute the number of groups necessary to store nbits bits, and
  19          * progressively work upward through the levels until reaching a level
  20          * that requires only one group.
  21          */
  22         binfo->levels[0].group_offset = 0;
  23         group_count = BITMAP_BITS2GROUPS(nbits);
  24         for (i = 1; group_count > 1; i++) {
  25                 assert(i < BITMAP_MAX_LEVELS);
  26                 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
  27                     + group_count;
  28                 group_count = BITMAP_BITS2GROUPS(group_count);
  29         }
  30         binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
  31             + group_count;
  32         assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX);
  33         binfo->nlevels = i;
  34         binfo->nbits = nbits;
  35 }
  36
  37 static size_t
  38 bitmap_info_ngroups(const bitmap_info_t *binfo)
  39 {
  40
  41         return (binfo->levels[binfo->nlevels].group_offset);
  42 }
  43
  44 void
  45 bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
  46 {
  47         size_t extra;
  48         unsigned i;
  49
  50         /*
  51          * Bits are actually inverted with regard to the external bitmap
  52          * interface, so the bitmap starts out with all 1 bits, except for
  53          * trailing unused bits (if any).  Note that each group uses bit 0 to
  54          * correspond to the first logical bit in the group, so extra bits
  55          * are the most significant bits of the last group.
  56          */
  57         memset(bitmap, 0xffU, bitmap_size(binfo));
  58         extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
  59             & BITMAP_GROUP_NBITS_MASK;
  60         if (extra != 0)
  61                 bitmap[binfo->levels[1].group_offset - 1] >>= extra;
  62         for (i = 1; i < binfo->nlevels; i++) {
  63                 size_t group_count = binfo->levels[i].group_offset -
  64                     binfo->levels[i-1].group_offset;
  65                 extra = (BITMAP_GROUP_NBITS - (group_count &
  66                     BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK;
  67                 if (extra != 0)
  68                         bitmap[binfo->levels[i+1].group_offset - 1] >>= extra;
  69         }
  70 }
  71
  72 #else /* USE_TREE */
  73
  74 void
  75 bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
  76 {
  77         size_t i;
  78
  79         assert(nbits > 0);
  80         assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
  81
  82         i = nbits >> LG_BITMAP_GROUP_NBITS;
  83         if (nbits % BITMAP_GROUP_NBITS != 0)
  84                 i++;
  85         binfo->ngroups = i;
  86         binfo->nbits = nbits;
  87 }
  88
  89 static size_t
  90 bitmap_info_ngroups(const bitmap_info_t *binfo)
  91 {
  92
  93         return (binfo->ngroups);
  94 }
  95
  96 void
  97 bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
  98 {
  99         size_t extra;
 100
 101         memset(bitmap, 0xffU, bitmap_size(binfo));
 102         extra = (binfo->nbits % (binfo->ngroups * BITMAP_GROUP_NBITS));
 103         if (extra != 0)
 104                 bitmap[binfo->ngroups - 1] >>= (BITMAP_GROUP_NBITS - extra);
 105 }
 106
 107 #endif /* USE_TREE */
 108
 109 size_t
 110 bitmap_size(const bitmap_info_t *binfo)
 111 {
 112
 113         return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP);
 114 }