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
32inline void BitMap::set_bit(idx_t bit) {
33 verify_index(bit);
34 *word_addr(bit) |= bit_mask(bit);
35}
36
37inline void BitMap::clear_bit(idx_t bit) {
38 verify_index(bit);
39 *word_addr(bit) &= ~bit_mask(bit);
40}
41
42inline 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
61inline 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
80inline 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
92inline 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
104inline 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
116inline 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
121inline 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
125inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
126 clear_range_of_words(_map, beg, end);
127}
128
129inline void BitMap::clear() {
130 clear_range_of_words(0, size_in_words());
131}
132
133inline 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
145template<BitMap::bm_word_t flip, bool aligned_right>
146inline 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
208inline BitMap::idx_t
209BitMap::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
213inline BitMap::idx_t
214BitMap::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
218inline BitMap::idx_t
219BitMap::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.
227inline BitMap::bm_word_t
228BitMap::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
239inline 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
244inline 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
249inline 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
255inline 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
260inline 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
265inline 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
270inline 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
275inline 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
280inline 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
291