author | mr |
Tue, 29 Oct 2019 13:52:04 -0700 | |
changeset 58850 | f4290bf1cc21 |
parent 53244 | 9807daeb47c4 |
child 58961 | 5d462d4b7a8b |
permissions | -rw-r--r-- |
1 | 1 |
/* |
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
52485
diff
changeset
|
2 |
* Copyright (c) 2005, 2019, Oracle and/or its affiliates. All rights reserved. |
1 | 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 |
* |
|
5547
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
3261
diff
changeset
|
19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
3261
diff
changeset
|
20 |
* or visit www.oracle.com if you need additional information or have any |
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
3261
diff
changeset
|
21 |
* questions. |
1 | 22 |
* |
23 |
*/ |
|
24 |
||
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
52485
diff
changeset
|
25 |
#ifndef SHARE_UTILITIES_BITMAP_INLINE_HPP |
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
52485
diff
changeset
|
26 |
#define SHARE_UTILITIES_BITMAP_INLINE_HPP |
7397 | 27 |
|
40655
9f644073d3a0
8157907: Incorrect inclusion of atomic.hpp instead of atomic.inline.hpp
dholmes
parents:
39219
diff
changeset
|
28 |
#include "runtime/atomic.hpp" |
7397 | 29 |
#include "utilities/bitMap.hpp" |
52394 | 30 |
#include "utilities/count_trailing_zeros.hpp" |
7397 | 31 |
|
1374 | 32 |
inline void BitMap::set_bit(idx_t bit) { |
33 |
verify_index(bit); |
|
34 |
*word_addr(bit) |= bit_mask(bit); |
|
35 |
} |
|
36 |
||
37 |
inline void BitMap::clear_bit(idx_t bit) { |
|
38 |
verify_index(bit); |
|
39 |
*word_addr(bit) &= ~bit_mask(bit); |
|
40 |
} |
|
41 |
||
1 | 42 |
inline bool BitMap::par_set_bit(idx_t bit) { |
43 |
verify_index(bit); |
|
19998
c18a7b05127a
8024914: Swapped usage of idx_t and bm_word_t types in bitMap.inline.hpp
tschatzl
parents:
11574
diff
changeset
|
44 |
volatile bm_word_t* const addr = word_addr(bit); |
c18a7b05127a
8024914: Swapped usage of idx_t and bm_word_t types in bitMap.inline.hpp
tschatzl
parents:
11574
diff
changeset
|
45 |
const bm_word_t mask = bit_mask(bit); |
c18a7b05127a
8024914: Swapped usage of idx_t and bm_word_t types in bitMap.inline.hpp
tschatzl
parents:
11574
diff
changeset
|
46 |
bm_word_t old_val = *addr; |
1 | 47 |
|
48 |
do { |
|
19998
c18a7b05127a
8024914: Swapped usage of idx_t and bm_word_t types in bitMap.inline.hpp
tschatzl
parents:
11574
diff
changeset
|
49 |
const bm_word_t new_val = old_val | mask; |
1 | 50 |
if (new_val == old_val) { |
51 |
return false; // Someone else beat us to it. |
|
52 |
} |
|
46958
a13bd8c6b7a2
8186166: Generalize Atomic::cmpxchg with templates
eosterlund
parents:
46428
diff
changeset
|
53 |
const bm_word_t cur_val = Atomic::cmpxchg(new_val, addr, old_val); |
1 | 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 |
||
61 |
inline bool BitMap::par_clear_bit(idx_t bit) { |
|
62 |
verify_index(bit); |
|
19998
c18a7b05127a
8024914: Swapped usage of idx_t and bm_word_t types in bitMap.inline.hpp
tschatzl
parents:
11574
diff
changeset
|
63 |
volatile bm_word_t* const addr = word_addr(bit); |
c18a7b05127a
8024914: Swapped usage of idx_t and bm_word_t types in bitMap.inline.hpp
tschatzl
parents:
11574
diff
changeset
|
64 |
const bm_word_t mask = ~bit_mask(bit); |
c18a7b05127a
8024914: Swapped usage of idx_t and bm_word_t types in bitMap.inline.hpp
tschatzl
parents:
11574
diff
changeset
|
65 |
bm_word_t old_val = *addr; |
1 | 66 |
|
67 |
do { |
|
19998
c18a7b05127a
8024914: Swapped usage of idx_t and bm_word_t types in bitMap.inline.hpp
tschatzl
parents:
11574
diff
changeset
|
68 |
const bm_word_t new_val = old_val & mask; |
1 | 69 |
if (new_val == old_val) { |
70 |
return false; // Someone else beat us to it. |
|
71 |
} |
|
46958
a13bd8c6b7a2
8186166: Generalize Atomic::cmpxchg with templates
eosterlund
parents:
46428
diff
changeset
|
72 |
const bm_word_t cur_val = Atomic::cmpxchg(new_val, addr, old_val); |
1 | 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 |
||
1374 | 80 |
inline 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 |
||
92 |
inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { |
|
37264
d9b0f2b53b73
8152188: Allow CMSBitMapYieldQuantum for BitMap::clear_range and clear_large_range
sangheki
parents:
37059
diff
changeset
|
93 |
if (end - beg == 1) { |
1374 | 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 |
||
104 |
inline 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 |
} |
|
1 | 115 |
|
1374 | 116 |
inline void BitMap::set_range_of_words(idx_t beg, idx_t end) { |
117 |
bm_word_t* map = _map; |
|
26937 | 118 |
for (idx_t i = beg; i < end; ++i) map[i] = ~(bm_word_t)0; |
1374 | 119 |
} |
120 |
||
38177 | 121 |
inline void BitMap::clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end) { |
1374 | 122 |
for (idx_t i = beg; i < end; ++i) map[i] = 0; |
123 |
} |
|
124 |
||
38177 | 125 |
inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) { |
126 |
clear_range_of_words(_map, beg, end); |
|
127 |
} |
|
1374 | 128 |
|
129 |
inline void BitMap::clear() { |
|
130 |
clear_range_of_words(0, size_in_words()); |
|
131 |
} |
|
132 |
||
133 |
inline 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 |
||
52394 | 145 |
template<BitMap::bm_word_t flip, bool aligned_right> |
146 |
inline 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 |
||
1374 | 208 |
inline BitMap::idx_t |
46402 | 209 |
BitMap::get_next_one_offset(idx_t l_offset, idx_t r_offset) const { |
52394 | 210 |
return get_next_bit_impl<find_ones_flip, false>(l_offset, r_offset); |
1374 | 211 |
} |
212 |
||
213 |
inline BitMap::idx_t |
|
46402 | 214 |
BitMap::get_next_zero_offset(idx_t l_offset, idx_t r_offset) const { |
52394 | 215 |
return get_next_bit_impl<find_zeros_flip, false>(l_offset, r_offset); |
1374 | 216 |
} |
217 |
||
218 |
inline BitMap::idx_t |
|
52394 | 219 |
BitMap::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); |
|
1 | 221 |
} |
1374 | 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. |
|
227 |
inline BitMap::bm_word_t |
|
228 |
BitMap::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 |
||
239 |
inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) { |
|
52485
e5534cc91a10
8211926: Catastrophic size_t underflow in BitMap::*_large methods
shade
parents:
52394
diff
changeset
|
240 |
assert(beg <= end, "underflow"); |
26937 | 241 |
memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(bm_word_t)); |
1374 | 242 |
} |
243 |
||
244 |
inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) { |
|
52485
e5534cc91a10
8211926: Catastrophic size_t underflow in BitMap::*_large methods
shade
parents:
52394
diff
changeset
|
245 |
assert(beg <= end, "underflow"); |
26937 | 246 |
memset(_map + beg, 0, (end - beg) * sizeof(bm_word_t)); |
1374 | 247 |
} |
248 |
||
249 |
inline 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 |
||
37059
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
255 |
inline bool BitMap2D::is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) { |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
256 |
verify_bit_within_slot_index(bit_within_slot_index); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
257 |
return (bit_index(slot_index, bit_within_slot_index) < size_in_bits()); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
258 |
} |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
259 |
|
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
260 |
inline bool BitMap2D::at(idx_t slot_index, idx_t bit_within_slot_index) const { |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
261 |
verify_bit_within_slot_index(bit_within_slot_index); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
262 |
return _map.at(bit_index(slot_index, bit_within_slot_index)); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
263 |
} |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
264 |
|
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
265 |
inline void BitMap2D::set_bit(idx_t slot_index, idx_t bit_within_slot_index) { |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
266 |
verify_bit_within_slot_index(bit_within_slot_index); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
267 |
_map.set_bit(bit_index(slot_index, bit_within_slot_index)); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
268 |
} |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
269 |
|
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
270 |
inline void BitMap2D::clear_bit(idx_t slot_index, idx_t bit_within_slot_index) { |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
271 |
verify_bit_within_slot_index(bit_within_slot_index); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
272 |
_map.clear_bit(bit_index(slot_index, bit_within_slot_index)); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
273 |
} |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
274 |
|
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
275 |
inline void BitMap2D::at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value) { |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
276 |
verify_bit_within_slot_index(bit_within_slot_index); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
277 |
_map.at_put(bit_index(slot_index, bit_within_slot_index), value); |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
278 |
} |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
279 |
|
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
280 |
inline void BitMap2D::at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value) { |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
281 |
verify_bit_within_slot_index(bit_within_slot_index); |
38177 | 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); |
|
37059
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
288 |
} |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
26937
diff
changeset
|
289 |
|
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
52485
diff
changeset
|
290 |
#endif // SHARE_UTILITIES_BITMAP_INLINE_HPP |