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
  78         assert(nbits > 0);
  79         assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
  80
  81         binfo->ngroups = BITMAP_BITS2GROUPS(nbits);
  82         binfo->nbits = nbits;
  83 }
  84
  85 static size_t
  86 bitmap_info_ngroups(const bitmap_info_t *binfo)
  87 {
  88
  89         return (binfo->ngroups);
  90 }
  91
  92 void
  93 bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
  94 {
  95         size_t extra;
  96
  97         memset(bitmap, 0xffU, bitmap_size(binfo));
  98         extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
  99             & BITMAP_GROUP_NBITS_MASK;
 100         if (extra != 0)
 101                 bitmap[binfo->ngroups - 1] >>= extra;
 102 }
 103
 104 #endif /* USE_TREE */
 105
 106 size_t
 107 bitmap_size(const bitmap_info_t *binfo)
 108 {
 109
 110         return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP);
 111 }