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 "runtime/orderAccess.hpp" 30 #include "utilities/bitMap.hpp" 31 #include "utilities/count_trailing_zeros.hpp" 32 33 inline void BitMap::set_bit(idx_t bit) { 34 verify_index(bit); 35 *word_addr(bit) |= bit_mask(bit); 36 } 37 38 inline void BitMap::clear_bit(idx_t bit) { 39 verify_index(bit); 40 *word_addr(bit) &= ~bit_mask(bit); 41 } 42 43 inline const BitMap::bm_word_t BitMap::load_word_ordered(const volatile bm_word_t* const addr, atomic_memory_order memory_order) { 44 if (memory_order == memory_order_relaxed || memory_order == memory_order_release) { 45 return Atomic::load(addr); 46 } else { 47 assert(memory_order == memory_order_acq_rel || 48 memory_order == memory_order_acquire || 49 memory_order == memory_order_conservative, 50 "unexpected memory ordering"); 51 return OrderAccess::load_acquire(addr); 52 } 53 } 54 55 inline bool BitMap::par_at(idx_t index, atomic_memory_order memory_order) const { 56 verify_index(index); 57 assert(memory_order == memory_order_acquire || 58 memory_order == memory_order_relaxed, 59 "unexpected memory ordering"); 60 const volatile bm_word_t* const addr = word_addr(index); 61 return (load_word_ordered(addr, memory_order) & bit_mask(index)) != 0; 62 } 63 64 inline bool BitMap::par_set_bit(idx_t bit, atomic_memory_order memory_order) { 65 verify_index(bit); 66 volatile bm_word_t* const addr = word_addr(bit); 67 const bm_word_t mask = bit_mask(bit); 68 bm_word_t old_val = load_word_ordered(addr, memory_order); 69 70 do { 71 const bm_word_t new_val = old_val | mask; 72 if (new_val == old_val) { 73 return false; // Someone else beat us to it. 74 } 75 const bm_word_t cur_val = Atomic::cmpxchg(new_val, addr, old_val, memory_order); 76 if (cur_val == old_val) { 77 return true; // Success. 78 } 79 old_val = cur_val; // The value changed, try again. 80 } while (true); 81 } 82 83 inline bool BitMap::par_clear_bit(idx_t bit, atomic_memory_order memory_order) { 84 verify_index(bit); 85 volatile bm_word_t* const addr = word_addr(bit); 86 const bm_word_t mask = ~bit_mask(bit); 87 bm_word_t old_val = load_word_ordered(addr, memory_order); 88 89 do { 90 const bm_word_t new_val = old_val & mask; 91 if (new_val == old_val) { 92 return false; // Someone else beat us to it. 93 } 94 const bm_word_t cur_val = Atomic::cmpxchg(new_val, addr, old_val, memory_order); 95 if (cur_val == old_val) { 96 return true; // Success. 97 } 98 old_val = cur_val; // The value changed, try again. 99 } while (true); 100 } 101 102 inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) { 103 if (hint == small_range && end - beg == 1) { 104 set_bit(beg); 105 } else { 106 if (hint == large_range) { 107 set_large_range(beg, end); 108 } else { 109 set_range(beg, end); 110 } 111 } 112 } 113 114 inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { 115 if (end - beg == 1) { 116 clear_bit(beg); 117 } else { 118 if (hint == large_range) { 119 clear_large_range(beg, end); 120 } else { 121 clear_range(beg, end); 122 } 123 } 124 } 125 126 inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) { 127 if (hint == small_range && end - beg == 1) { 128 par_at_put(beg, true); 129 } else { 130 if (hint == large_range) { 131 par_at_put_large_range(beg, end, true); 132 } else { 133 par_at_put_range(beg, end, true); 134 } 135 } 136 } 137 138 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) { 139 bm_word_t* map = _map; 140 for (idx_t i = beg; i < end; ++i) map[i] = ~(bm_word_t)0; 141 } 142 143 inline void BitMap::clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end) { 144 for (idx_t i = beg; i < end; ++i) map[i] = 0; 145 } 146 147 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) { 148 clear_range_of_words(_map, beg, end); 149 } 150 151 inline void BitMap::clear() { 152 clear_range_of_words(0, size_in_words()); 153 } 154 155 inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { 156 if (hint == small_range && end - beg == 1) { 157 par_at_put(beg, false); 158 } else { 159 if (hint == large_range) { 160 par_at_put_large_range(beg, end, false); 161 } else { 162 par_at_put_range(beg, end, false); 163 } 164 } 165 } 166 167 template<BitMap::bm_word_t flip, bool aligned_right> 168 inline BitMap::idx_t BitMap::get_next_bit_impl(idx_t l_index, idx_t r_index) const { 169 STATIC_ASSERT(flip == find_ones_flip || flip == find_zeros_flip); 170 verify_range(l_index, r_index); 171 assert(!aligned_right || is_word_aligned(r_index), "r_index not aligned"); 172 173 // The first word often contains an interesting bit, either due to 174 // density or because of features of the calling algorithm. So it's 175 // important to examine that first word with a minimum of fuss, 176 // minimizing setup time for later words that will be wasted if the 177 // first word is indeed interesting. 178 179 // The benefit from aligned_right being true is relatively small. 180 // It saves a couple instructions in the setup for the word search 181 // loop. It also eliminates the range check on the final result. 182 // However, callers often have a comparison with r_index, and 183 // inlining often allows the two comparisons to be combined; it is 184 // important when !aligned_right that return paths either return 185 // r_index or a value dominated by a comparison with r_index. 186 // aligned_right is still helpful when the caller doesn't have a 187 // range check because features of the calling algorithm guarantee 188 // an interesting bit will be present. 189 190 if (l_index < r_index) { 191 // Get the word containing l_index, and shift out low bits. 192 idx_t index = word_index(l_index); 193 bm_word_t cword = (map(index) ^ flip) >> bit_in_word(l_index); 194 if ((cword & 1) != 0) { 195 // The first bit is similarly often interesting. When it matters 196 // (density or features of the calling algorithm make it likely 197 // the first bit is set), going straight to the next clause compares 198 // poorly with doing this check first; count_trailing_zeros can be 199 // relatively expensive, plus there is the additional range check. 200 // But when the first bit isn't set, the cost of having tested for 201 // it is relatively small compared to the rest of the search. 202 return l_index; 203 } else if (cword != 0) { 204 // Flipped and shifted first word is non-zero. 205 idx_t result = l_index + count_trailing_zeros(cword); 206 if (aligned_right || (result < r_index)) return result; 207 // Result is beyond range bound; return r_index. 208 } else { 209 // Flipped and shifted first word is zero. Word search through 210 // aligned up r_index for a non-zero flipped word. 211 idx_t limit = aligned_right 212 ? word_index(r_index) 213 : (word_index(r_index - 1) + 1); // Align up, knowing r_index > 0. 214 while (++index < limit) { 215 cword = map(index) ^ flip; 216 if (cword != 0) { 217 idx_t result = bit_index(index) + count_trailing_zeros(cword); 218 if (aligned_right || (result < r_index)) return result; 219 // Result is beyond range bound; return r_index. 220 assert((index + 1) == limit, "invariant"); 221 break; 222 } 223 } 224 // No bits in range; return r_index. 225 } 226 } 227 return r_index; 228 } 229 230 inline BitMap::idx_t 231 BitMap::get_next_one_offset(idx_t l_offset, idx_t r_offset) const { 232 return get_next_bit_impl<find_ones_flip, false>(l_offset, r_offset); 233 } 234 235 inline BitMap::idx_t 236 BitMap::get_next_zero_offset(idx_t l_offset, idx_t r_offset) const { 237 return get_next_bit_impl<find_zeros_flip, false>(l_offset, r_offset); 238 } 239 240 inline BitMap::idx_t 241 BitMap::get_next_one_offset_aligned_right(idx_t l_offset, idx_t r_offset) const { 242 return get_next_bit_impl<find_ones_flip, true>(l_offset, r_offset); 243 } 244 245 // Returns a bit mask for a range of bits [beg, end) within a single word. Each 246 // bit in the mask is 0 if the bit is in the range, 1 if not in the range. The 247 // returned mask can be used directly to clear the range, or inverted to set the 248 // range. Note: end must not be 0. 249 inline BitMap::bm_word_t 250 BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const { 251 assert(end != 0, "does not work when end == 0"); 252 assert(beg == end || word_index(beg) == word_index(end - 1), 253 "must be a single-word range"); 254 bm_word_t mask = bit_mask(beg) - 1; // low (right) bits 255 if (bit_in_word(end) != 0) { 256 mask |= ~(bit_mask(end) - 1); // high (left) bits 257 } 258 return mask; 259 } 260 261 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) { 262 assert(beg <= end, "underflow"); 263 memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(bm_word_t)); 264 } 265 266 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) { 267 assert(beg <= end, "underflow"); 268 memset(_map + beg, 0, (end - beg) * sizeof(bm_word_t)); 269 } 270 271 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const { 272 idx_t bit_rounded_up = bit + (BitsPerWord - 1); 273 // Check for integer arithmetic overflow. 274 return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words(); 275 } 276 277 inline bool BitMap2D::is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) { 278 verify_bit_within_slot_index(bit_within_slot_index); 279 return (bit_index(slot_index, bit_within_slot_index) < size_in_bits()); 280 } 281 282 inline bool BitMap2D::at(idx_t slot_index, idx_t bit_within_slot_index) const { 283 verify_bit_within_slot_index(bit_within_slot_index); 284 return _map.at(bit_index(slot_index, bit_within_slot_index)); 285 } 286 287 inline void BitMap2D::set_bit(idx_t slot_index, idx_t bit_within_slot_index) { 288 verify_bit_within_slot_index(bit_within_slot_index); 289 _map.set_bit(bit_index(slot_index, bit_within_slot_index)); 290 } 291 292 inline void BitMap2D::clear_bit(idx_t slot_index, idx_t bit_within_slot_index) { 293 verify_bit_within_slot_index(bit_within_slot_index); 294 _map.clear_bit(bit_index(slot_index, bit_within_slot_index)); 295 } 296 297 inline void BitMap2D::at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value) { 298 verify_bit_within_slot_index(bit_within_slot_index); 299 _map.at_put(bit_index(slot_index, bit_within_slot_index), value); 300 } 301 302 inline void BitMap2D::at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value) { 303 verify_bit_within_slot_index(bit_within_slot_index); 304 305 idx_t bit = bit_index(slot_index, bit_within_slot_index); 306 if (bit >= _map.size()) { 307 _map.resize(2 * MAX2(_map.size(), bit)); 308 } 309 _map.at_put(bit, value); 310 } 311 312 #endif // SHARE_UTILITIES_BITMAP_INLINE_HPP