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