1 /*
  2  * Copyright Amazon.com Inc. 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_GC_SHENANDOAH_SHENANDOAHSIMPLEBITMAP_INLINE_HPP
 26 #define SHARE_GC_SHENANDOAH_SHENANDOAHSIMPLEBITMAP_INLINE_HPP
 27 
 28 #include "gc/shenandoah/shenandoahSimpleBitMap.hpp"
 29 
 30 inline idx_t ShenandoahSimpleBitMap::find_first_set_bit(idx_t beg, idx_t end) const {
 31   assert((beg >= 0) && (beg < _num_bits), "precondition");
 32   assert((end > beg) && (end <= _num_bits), "precondition");
 33   do {
 34     size_t array_idx = beg >> LogBitsPerWord;
 35     uintx bit_number = beg & right_n_bits(LogBitsPerWord);
 36     uintx element_bits = _bitmap[array_idx];
 37     if (bit_number > 0) {
 38       uintx mask_out = right_n_bits(bit_number);
 39       element_bits &= ~mask_out;
 40     }
 41     if (element_bits) {
 42       // The next set bit is here.  Find first set bit >= bit_number;
 43       uintx aligned = element_bits >> bit_number;
 44       uintx first_set_bit = count_trailing_zeros<uintx>(aligned);
 45       idx_t candidate_result = (array_idx * BitsPerWord) + bit_number + first_set_bit;
 46       return (candidate_result < end)? candidate_result: end;
 47     } else {
 48       // Next bit is not here.  Try the next array element
 49       beg += BitsPerWord - bit_number;
 50     }
 51   } while (beg < end);
 52   return end;
 53 }
 54 
 55 inline idx_t ShenandoahSimpleBitMap::find_first_set_bit(idx_t beg) const {
 56   assert((beg >= 0) && (beg < size()), "precondition");
 57   return find_first_set_bit(beg, size());
 58 }
 59 
 60 inline idx_t ShenandoahSimpleBitMap::find_last_set_bit(idx_t beg, idx_t end) const {
 61   assert((end >= 0) && (end < _num_bits), "precondition");
 62   assert((beg >= -1) && (beg < end), "precondition");
 63   do {
 64     idx_t array_idx = end >> LogBitsPerWord;
 65     uintx bit_number = end & right_n_bits(LogBitsPerWord);
 66     uintx element_bits = _bitmap[array_idx];
 67     if (bit_number < BitsPerWord - 1){
 68       uintx mask_in = right_n_bits(bit_number + 1);
 69       element_bits &= mask_in;
 70     }
 71     if (element_bits) {
 72       // The prev set bit is here.  Find the first set bit <= bit_number
 73       uintx aligned = element_bits << (BitsPerWord - (bit_number + 1));
 74       uintx first_set_bit = count_leading_zeros<uintx>(aligned);
 75       idx_t candidate_result = array_idx * BitsPerWord + (bit_number - first_set_bit);
 76       return (candidate_result > beg)? candidate_result: beg;
 77     } else {
 78       // Next bit is not here.  Try the previous array element
 79       end -= (bit_number + 1);
 80     }
 81   } while (end > beg);
 82   return beg;
 83 }
 84 
 85 inline idx_t ShenandoahSimpleBitMap::find_last_set_bit(idx_t end) const {
 86   assert((end >= 0) && (end < _num_bits), "precondition");
 87   return find_last_set_bit(-1, end);
 88 }
 89 
 90 inline idx_t ShenandoahSimpleBitMap::find_first_consecutive_set_bits(idx_t beg, size_t num_bits) const {
 91   assert((beg >= 0) && (beg < _num_bits), "precondition");
 92   return find_first_consecutive_set_bits(beg, size(), num_bits);
 93 }
 94 
 95 inline idx_t ShenandoahSimpleBitMap::find_last_consecutive_set_bits(idx_t end, size_t num_bits) const {
 96   assert((end >= 0) && (end < _num_bits), "precondition");
 97   return find_last_consecutive_set_bits((idx_t) -1, end, num_bits);
 98 }
 99 
100 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHSIMPLEBITMAP_INLINE_HPP