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