contrib/jemalloc/src/bitmap.c

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