1 /*
   2  * Copyright (c) 2005, 2019, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #ifndef SHARE_UTILITIES_BITMAP_INLINE_HPP
  26 #define SHARE_UTILITIES_BITMAP_INLINE_HPP
  27 
  28 #include "runtime/atomic.hpp"
  29 #include "utilities/bitMap.hpp"
  30 #include "utilities/count_trailing_zeros.hpp"
  31 
  32 inline void BitMap::set_bit(idx_t bit) {
  33   verify_index(bit);
  34   *word_addr(bit) |= bit_mask(bit);
  35 }
  36 
  37 inline void BitMap::clear_bit(idx_t bit) {
  38   verify_index(bit);
  39   *word_addr(bit) &= ~bit_mask(bit);
  40 }
  41 
  42 inline bool BitMap::par_set_bit(idx_t bit) {
  43   verify_index(bit);
  44   volatile bm_word_t* const addr = word_addr(bit);
  45   const bm_word_t mask = bit_mask(bit);
  46   bm_word_t old_val = *addr;
  47 
  48   do {
  49     const bm_word_t new_val = old_val | mask;
  50     if (new_val == old_val) {
  51       return false;     // Someone else beat us to it.
  52     }
  53     const bm_word_t cur_val = Atomic::cmpxchg(new_val, addr, old_val);
  54     if (cur_val == old_val) {
  55       return true;      // Success.
  56     }
  57     old_val = cur_val;  // The value changed, try again.
  58   } while (true);
  59 }
  60 
  61 inline bool BitMap::par_clear_bit(idx_t bit) {
  62   verify_index(bit);
  63   volatile bm_word_t* const addr = word_addr(bit);
  64   const bm_word_t mask = ~bit_mask(bit);
  65   bm_word_t old_val = *addr;
  66 
  67   do {
  68     const bm_word_t new_val = old_val & mask;
  69     if (new_val == old_val) {
  70       return false;     // Someone else beat us to it.
  71     }
  72     const bm_word_t cur_val = Atomic::cmpxchg(new_val, addr, old_val);
  73     if (cur_val == old_val) {
  74       return true;      // Success.
  75     }
  76     old_val = cur_val;  // The value changed, try again.
  77   } while (true);
  78 }
  79 
  80 inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
  81   if (hint == small_range && end - beg == 1) {
  82     set_bit(beg);
  83   } else {
  84     if (hint == large_range) {
  85       set_large_range(beg, end);
  86     } else {
  87       set_range(beg, end);
  88     }
  89   }
  90 }
  91 
  92 inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
  93   if (end - beg == 1) {
  94     clear_bit(beg);
  95   } else {
  96     if (hint == large_range) {
  97       clear_large_range(beg, end);
  98     } else {
  99       clear_range(beg, end);
 100     }
 101   }
 102 }
 103 
 104 inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
 105   if (hint == small_range && end - beg == 1) {
 106     par_at_put(beg, true);
 107   } else {
 108     if (hint == large_range) {
 109       par_at_put_large_range(beg, end, true);
 110     } else {
 111       par_at_put_range(beg, end, true);
 112     }
 113   }
 114 }
 115 
 116 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) {
 117   bm_word_t* map = _map;
 118   for (idx_t i = beg; i < end; ++i) map[i] = ~(bm_word_t)0;
 119 }
 120 
 121 inline void BitMap::clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end) {
 122   for (idx_t i = beg; i < end; ++i) map[i] = 0;
 123 }
 124 
 125 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
 126   clear_range_of_words(_map, beg, end);
 127 }
 128 
 129 inline void BitMap::clear() {
 130   clear_range_of_words(0, size_in_words());
 131 }
 132 
 133 inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
 134   if (hint == small_range && end - beg == 1) {
 135     par_at_put(beg, false);
 136   } else {
 137     if (hint == large_range) {
 138       par_at_put_large_range(beg, end, false);
 139     } else {
 140       par_at_put_range(beg, end, false);
 141     }
 142   }
 143 }
 144 
 145 template<BitMap::bm_word_t flip, bool aligned_right>
 146 inline BitMap::idx_t BitMap::get_next_bit_impl(idx_t l_index, idx_t r_index) const {
 147   STATIC_ASSERT(flip == find_ones_flip || flip == find_zeros_flip);
 148   verify_range(l_index, r_index);
 149   assert(!aligned_right || is_word_aligned(r_index), "r_index not aligned");
 150 
 151   // The first word often contains an interesting bit, either due to
 152   // density or because of features of the calling algorithm.  So it's
 153   // important to examine that first word with a minimum of fuss,
 154   // minimizing setup time for later words that will be wasted if the
 155   // first word is indeed interesting.
 156 
 157   // The benefit from aligned_right being true is relatively small.
 158   // It saves a couple instructions in the setup for the word search
 159   // loop.  It also eliminates the range check on the final result.
 160   // However, callers often have a comparison with r_index, and
 161   // inlining often allows the two comparisons to be combined; it is
 162   // important when !aligned_right that return paths either return
 163   // r_index or a value dominated by a comparison with r_index.
 164   // aligned_right is still helpful when the caller doesn't have a
 165   // range check because features of the calling algorithm guarantee
 166   // an interesting bit will be present.
 167 
 168   if (l_index < r_index) {
 169     // Get the word containing l_index, and shift out low bits.
 170     idx_t index = word_index(l_index);
 171     bm_word_t cword = (map(index) ^ flip) >> bit_in_word(l_index);
 172     if ((cword & 1) != 0) {
 173       // The first bit is similarly often interesting. When it matters
 174       // (density or features of the calling algorithm make it likely
 175       // the first bit is set), going straight to the next clause compares
 176       // poorly with doing this check first; count_trailing_zeros can be
 177       // relatively expensive, plus there is the additional range check.
 178       // But when the first bit isn't set, the cost of having tested for
 179       // it is relatively small compared to the rest of the search.
 180       return l_index;
 181     } else if (cword != 0) {
 182       // Flipped and shifted first word is non-zero.
 183       idx_t result = l_index + count_trailing_zeros(cword);
 184       if (aligned_right || (result < r_index)) return result;
 185       // Result is beyond range bound; return r_index.
 186     } else {
 187       // Flipped and shifted first word is zero.  Word search through
 188       // aligned up r_index for a non-zero flipped word.
 189       idx_t limit = aligned_right
 190         ? word_index(r_index)
 191         : (word_index(r_index - 1) + 1); // Align up, knowing r_index > 0.
 192       while (++index < limit) {
 193         cword = map(index) ^ flip;
 194         if (cword != 0) {
 195           idx_t result = bit_index(index) + count_trailing_zeros(cword);
 196           if (aligned_right || (result < r_index)) return result;
 197           // Result is beyond range bound; return r_index.
 198           assert((index + 1) == limit, "invariant");
 199           break;
 200         }
 201       }
 202       // No bits in range; return r_index.
 203     }
 204   }
 205   return r_index;
 206 }
 207 
 208 inline BitMap::idx_t
 209 BitMap::get_next_one_offset(idx_t l_offset, idx_t r_offset) const {
 210   return get_next_bit_impl<find_ones_flip, false>(l_offset, r_offset);
 211 }
 212 
 213 inline BitMap::idx_t
 214 BitMap::get_next_zero_offset(idx_t l_offset, idx_t r_offset) const {
 215   return get_next_bit_impl<find_zeros_flip, false>(l_offset, r_offset);
 216 }
 217 
 218 inline BitMap::idx_t
 219 BitMap::get_next_one_offset_aligned_right(idx_t l_offset, idx_t r_offset) const {
 220   return get_next_bit_impl<find_ones_flip, true>(l_offset, r_offset);
 221 }
 222 
 223 // Returns a bit mask for a range of bits [beg, end) within a single word.  Each
 224 // bit in the mask is 0 if the bit is in the range, 1 if not in the range.  The
 225 // returned mask can be used directly to clear the range, or inverted to set the
 226 // range.  Note:  end must not be 0.
 227 inline BitMap::bm_word_t
 228 BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
 229   assert(end != 0, "does not work when end == 0");
 230   assert(beg == end || word_index(beg) == word_index(end - 1),
 231          "must be a single-word range");
 232   bm_word_t mask = bit_mask(beg) - 1;   // low (right) bits
 233   if (bit_in_word(end) != 0) {
 234     mask |= ~(bit_mask(end) - 1);       // high (left) bits
 235   }
 236   return mask;
 237 }
 238 
 239 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
 240   assert(beg <= end, "underflow");
 241   memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(bm_word_t));
 242 }
 243 
 244 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
 245   assert(beg <= end, "underflow");
 246   memset(_map + beg, 0, (end - beg) * sizeof(bm_word_t));
 247 }
 248 
 249 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
 250   idx_t bit_rounded_up = bit + (BitsPerWord - 1);
 251   // Check for integer arithmetic overflow.
 252   return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
 253 }
 254 
 255 inline bool BitMap2D::is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) {
 256   verify_bit_within_slot_index(bit_within_slot_index);
 257   return (bit_index(slot_index, bit_within_slot_index) < size_in_bits());
 258 }
 259 
 260 inline bool BitMap2D::at(idx_t slot_index, idx_t bit_within_slot_index) const {
 261   verify_bit_within_slot_index(bit_within_slot_index);
 262   return _map.at(bit_index(slot_index, bit_within_slot_index));
 263 }
 264 
 265 inline void BitMap2D::set_bit(idx_t slot_index, idx_t bit_within_slot_index) {
 266   verify_bit_within_slot_index(bit_within_slot_index);
 267   _map.set_bit(bit_index(slot_index, bit_within_slot_index));
 268 }
 269 
 270 inline void BitMap2D::clear_bit(idx_t slot_index, idx_t bit_within_slot_index) {
 271   verify_bit_within_slot_index(bit_within_slot_index);
 272   _map.clear_bit(bit_index(slot_index, bit_within_slot_index));
 273 }
 274 
 275 inline void BitMap2D::at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value) {
 276   verify_bit_within_slot_index(bit_within_slot_index);
 277   _map.at_put(bit_index(slot_index, bit_within_slot_index), value);
 278 }
 279 
 280 inline void BitMap2D::at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value) {
 281   verify_bit_within_slot_index(bit_within_slot_index);
 282 
 283   idx_t bit = bit_index(slot_index, bit_within_slot_index);
 284   if (bit >= _map.size()) {
 285     _map.resize(2 * MAX2(_map.size(), bit));
 286   }
 287   _map.at_put(bit, value);
 288 }
 289 
 290 #endif // SHARE_UTILITIES_BITMAP_INLINE_HPP