50 class BinMap {

    51 

    52   typedef uint32_t mask_type;

    53   mask_type _mask;

    54 

    55   static mask_type mask_for_pos(int pos) { return 1 << pos; }

    56 

    57 public:

    58 

    59   BinMap() : _mask(0) {}

    60 

    61   bool all_zero() const          { return _mask == 0; }

    62 

    63   bool get_bit(int pos) const    { return (_mask & mask_for_pos(pos)) != 0 ? true : false; }

    64   void set_bit(int pos)          { _mask |= mask_for_pos(pos); }

    65   void clr_bit(int pos)          { _mask &= ~mask_for_pos(pos); }

    66 

    67   // Starting at (including) pos, find the position of the next 1 bit.

    68   // Return -1 if not found.

    69   inline int find_next_set_bit(int pos) const;

    70 

    71   static int size() { return sizeof(mask_type) * 8; }

    72 

    73 };

    74 

    75 struct block_t {

    76   block_t* next;

    77   size_t size;

    78 };

    79 

    80 struct block_stats_t {

    81   size_t word_size;

    82   int num_blocks;

    83 };

    84 

    85 template <

    86   size_t min_word_size,

    87   size_t spread,

    88   int num_bins

    89 >

    90 class Bins {

    91 

    92   STATIC_ASSERT(sizeof(block_t) <= (min_word_size * BytesPerWord));

    93 

    94   block_t* _bins[num_bins];

    95 

    96   BinMap _mask;

    97 

    98   // e.g. spread = 4

    99   //

   100   // sz    bno (put)  bno (get)

   101   //         (guarant)

   102   // 0     00         00

   103   // 1     00         01

   104   // 2     00         01

   105   // 3     00         01

   106   // 4     01         01

   107   // 5     01         02

   108   // 6     01         02

   109   // 7     01         02

   110   // 8     02         02

   111   // 9     02         03

   112   // 10    02         03

   113   // 11    02         03

   114   //

   115   // put -> no = wordsize / spread

   116   //

   117   // get -> no = (req_wordsize + spread - 1) / spread

   118 

   119   // The bin number for a given word size.

   120   static int bin_for_size(size_t word_size) {

   121     assert(word_size >= min_word_size && word_size < maximal_word_size(),

   122            "Word size oob (" SIZE_FORMAT ")", word_size);

   123     return (word_size - min_word_size) / spread;

   124   }

   125 

   126   // [minimal, maximal) size of blocks which are held in a bin.

   127   // Note that when taking a block out of the bin, only the minimum block size

   128   // is guaranteed.

   129   static size_t minimal_word_size_in_bin(int bno) {

   130     return min_word_size + (bno * spread);

   131   }

   132   static size_t maximal_word_size_in_bin(int bno) {

   133     return minimal_word_size_in_bin(bno) + spread;

   134   }

   135 

   136 public:

   137 

   138   Bins() : _mask() {

   139     assert(BinMap::size() >= num_bins, "mask too small");

   140     ::memset(_bins, 0, sizeof(_bins));

   141   }

   142 

   143   // [min, max) word size

   144   static size_t minimal_word_size() { return min_word_size; }

   145   static size_t maximal_word_size() { return min_word_size + (spread * num_bins); }

   146 

   147   inline void put(MetaWord* p, size_t word_size);

   148 

   149   inline block_t* get(size_t word_size);

   150 

   151 #ifdef ASSERT

   152   void verify() const;

   153 #endif

   154 

   155   void statistics(block_stats_t* stats) const;

   156 

   157   void print(outputStream* st) const;

   158 

   159 };

   160 

   161