author | coleenp |
Fri, 04 Jan 2019 15:06:01 -0500 | |
changeset 53149 | 259c36ef27df |
parent 52485 | e5534cc91a10 |
child 53244 | 9807daeb47c4 |
permissions | -rw-r--r-- |
1 | 1 |
/* |
49364
601146c66cad
8173070: Remove ValueObj class for allocation subclassing for runtime code
coleenp
parents:
47216
diff
changeset
|
2 |
* Copyright (c) 1997, 2018, 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 |
||
7397 | 25 |
#ifndef SHARE_VM_UTILITIES_BITMAP_HPP |
26 |
#define SHARE_VM_UTILITIES_BITMAP_HPP |
|
27 |
||
49670
1a1a69219637
8200607: Add missing include dependency in bitMap.hpp
pliden
parents:
49621
diff
changeset
|
28 |
#include "memory/allocation.hpp" |
46625 | 29 |
#include "utilities/align.hpp" |
7397 | 30 |
|
1374 | 31 |
// Forward decl; |
32 |
class BitMapClosure; |
|
1 | 33 |
|
1374 | 34 |
// Operations for bitmaps represented as arrays of unsigned integers. |
35 |
// Bit offsets are numbered from 0 to size-1. |
|
1 | 36 |
|
38177 | 37 |
// The "abstract" base BitMap class. |
38 |
// |
|
39 |
// The constructor and destructor are protected to prevent |
|
40 |
// creation of BitMap instances outside of the BitMap class. |
|
41 |
// |
|
42 |
// The BitMap class doesn't use virtual calls on purpose, |
|
43 |
// this ensures that we don't get a vtable unnecessarily. |
|
44 |
// |
|
45 |
// The allocation of the backing storage for the BitMap are handled by |
|
46 |
// the subclasses. BitMap doesn't allocate or delete backing storage. |
|
49364
601146c66cad
8173070: Remove ValueObj class for allocation subclassing for runtime code
coleenp
parents:
47216
diff
changeset
|
47 |
class BitMap { |
1 | 48 |
friend class BitMap2D; |
49 |
||
50 |
public: |
|
51 |
typedef size_t idx_t; // Type used for bit and word indices. |
|
1374 | 52 |
typedef uintptr_t bm_word_t; // Element type of array that represents |
53 |
// the bitmap. |
|
1 | 54 |
|
55 |
// Hints for range sizes. |
|
56 |
typedef enum { |
|
57 |
unknown_range, small_range, large_range |
|
58 |
} RangeSizeHint; |
|
59 |
||
60 |
private: |
|
1374 | 61 |
bm_word_t* _map; // First word in bitmap |
62 |
idx_t _size; // Size of bitmap (in bits) |
|
1 | 63 |
|
52394 | 64 |
// Helper for get_next_{zero,one}_bit variants. |
65 |
// - flip designates whether searching for 1s or 0s. Must be one of |
|
66 |
// find_{zeros,ones}_flip. |
|
67 |
// - aligned_right is true if r_index is a priori on a bm_word_t boundary. |
|
68 |
template<bm_word_t flip, bool aligned_right> |
|
69 |
inline idx_t get_next_bit_impl(idx_t l_index, idx_t r_index) const; |
|
70 |
||
71 |
// Values for get_next_bit_impl flip parameter. |
|
72 |
static const bm_word_t find_ones_flip = 0; |
|
73 |
static const bm_word_t find_zeros_flip = ~(bm_word_t)0; |
|
74 |
||
52485
e5534cc91a10
8211926: Catastrophic size_t underflow in BitMap::*_large methods
shade
parents:
52394
diff
changeset
|
75 |
// Threshold for performing small range operation, even when large range |
e5534cc91a10
8211926: Catastrophic size_t underflow in BitMap::*_large methods
shade
parents:
52394
diff
changeset
|
76 |
// operation was requested. Measured in words. |
e5534cc91a10
8211926: Catastrophic size_t underflow in BitMap::*_large methods
shade
parents:
52394
diff
changeset
|
77 |
static const size_t small_range_words = 32; |
e5534cc91a10
8211926: Catastrophic size_t underflow in BitMap::*_large methods
shade
parents:
52394
diff
changeset
|
78 |
|
1 | 79 |
protected: |
80 |
// Return the position of bit within the word that contains it (e.g., if |
|
81 |
// bitmap words are 32 bits, return a number 0 <= n <= 31). |
|
82 |
static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); } |
|
83 |
||
84 |
// Return a mask that will select the specified bit, when applied to the word |
|
85 |
// containing the bit. |
|
1374 | 86 |
static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); } |
1 | 87 |
|
88 |
// Return the index of the word containing the specified bit. |
|
89 |
static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; } |
|
90 |
||
91 |
// Return the bit number of the first bit in the specified word. |
|
92 |
static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; } |
|
93 |
||
94 |
// Return the array of bitmap words, or a specific word from it. |
|
38102
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
95 |
bm_word_t* map() { return _map; } |
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
96 |
const bm_word_t* map() const { return _map; } |
1374 | 97 |
bm_word_t map(idx_t word) const { return _map[word]; } |
1 | 98 |
|
99 |
// Return a pointer to the word containing the specified bit. |
|
38102
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
100 |
bm_word_t* word_addr(idx_t bit) { return map() + word_index(bit); } |
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
101 |
const bm_word_t* word_addr(idx_t bit) const { return map() + word_index(bit); } |
1 | 102 |
|
103 |
// Set a word to a specified value or to all ones; clear a word. |
|
1374 | 104 |
void set_word (idx_t word, bm_word_t val) { _map[word] = val; } |
26937 | 105 |
void set_word (idx_t word) { set_word(word, ~(bm_word_t)0); } |
1 | 106 |
void clear_word(idx_t word) { _map[word] = 0; } |
107 |
||
108 |
// Utilities for ranges of bits. Ranges are half-open [beg, end). |
|
109 |
||
110 |
// Ranges within a single word. |
|
1374 | 111 |
bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const; |
112 |
void set_range_within_word (idx_t beg, idx_t end); |
|
113 |
void clear_range_within_word (idx_t beg, idx_t end); |
|
114 |
void par_put_range_within_word (idx_t beg, idx_t end, bool value); |
|
1 | 115 |
|
116 |
// Ranges spanning entire words. |
|
1374 | 117 |
void set_range_of_words (idx_t beg, idx_t end); |
118 |
void clear_range_of_words (idx_t beg, idx_t end); |
|
119 |
void set_large_range_of_words (idx_t beg, idx_t end); |
|
120 |
void clear_large_range_of_words (idx_t beg, idx_t end); |
|
1 | 121 |
|
38177 | 122 |
static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end); |
123 |
||
52485
e5534cc91a10
8211926: Catastrophic size_t underflow in BitMap::*_large methods
shade
parents:
52394
diff
changeset
|
124 |
static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word); |
e5534cc91a10
8211926: Catastrophic size_t underflow in BitMap::*_large methods
shade
parents:
52394
diff
changeset
|
125 |
|
1 | 126 |
// The index of the first full word in a range. |
1374 | 127 |
idx_t word_index_round_up(idx_t bit) const; |
1 | 128 |
|
2998
b501bd305780
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
1374
diff
changeset
|
129 |
// Verification. |
37059
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
37058
diff
changeset
|
130 |
void verify_index(idx_t index) const NOT_DEBUG_RETURN; |
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
37058
diff
changeset
|
131 |
void verify_range(idx_t beg_index, idx_t end_index) const NOT_DEBUG_RETURN; |
1 | 132 |
|
2998
b501bd305780
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
1374
diff
changeset
|
133 |
// Statistics. |
46958
a13bd8c6b7a2
8186166: Generalize Atomic::cmpxchg with templates
eosterlund
parents:
46745
diff
changeset
|
134 |
static const idx_t* _pop_count_table; |
1374 | 135 |
static void init_pop_count_table(); |
136 |
static idx_t num_set_bits(bm_word_t w); |
|
137 |
static idx_t num_set_bits_from_table(unsigned char c); |
|
1 | 138 |
|
38177 | 139 |
// Allocation Helpers. |
140 |
||
141 |
// Allocates and clears the bitmap memory. |
|
142 |
template <class Allocator> |
|
49828
ee3555b4a130
8201647: Make initial clearing of CHeapBitMap optional
pliden
parents:
49670
diff
changeset
|
143 |
static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true); |
1 | 144 |
|
38177 | 145 |
// Reallocates and clears the new bitmap memory. |
146 |
template <class Allocator> |
|
49828
ee3555b4a130
8201647: Make initial clearing of CHeapBitMap optional
pliden
parents:
49670
diff
changeset
|
147 |
static bm_word_t* reallocate(const Allocator&, bm_word_t* map, idx_t old_size_in_bits, idx_t new_size_in_bits, bool clear = true); |
38177 | 148 |
|
149 |
// Free the bitmap memory. |
|
150 |
template <class Allocator> |
|
151 |
static void free(const Allocator&, bm_word_t* map, idx_t size_in_bits); |
|
152 |
||
153 |
// Protected functions, that are used by BitMap sub-classes that support them. |
|
1 | 154 |
|
38177 | 155 |
// Resize the backing bitmap memory. |
156 |
// |
|
157 |
// Old bits are transfered to the new memory |
|
158 |
// and the extended memory is cleared. |
|
159 |
template <class Allocator> |
|
160 |
void resize(const Allocator& allocator, idx_t new_size_in_bits); |
|
1 | 161 |
|
38177 | 162 |
// Set up and clear the bitmap memory. |
163 |
// |
|
164 |
// Precondition: The bitmap was default constructed and has |
|
165 |
// not yet had memory allocated via resize or (re)initialize. |
|
166 |
template <class Allocator> |
|
167 |
void initialize(const Allocator& allocator, idx_t size_in_bits); |
|
168 |
||
169 |
// Set up and clear the bitmap memory. |
|
170 |
// |
|
171 |
// Can be called on previously initialized bitmaps. |
|
172 |
template <class Allocator> |
|
173 |
void reinitialize(const Allocator& allocator, idx_t new_size_in_bits); |
|
1 | 174 |
|
1374 | 175 |
// Set the map and size. |
38177 | 176 |
void update(bm_word_t* map, idx_t size) { |
177 |
_map = map; |
|
178 |
_size = size; |
|
179 |
} |
|
1 | 180 |
|
38177 | 181 |
// Protected constructor and destructor. |
182 |
BitMap(bm_word_t* map, idx_t size_in_bits) : _map(map), _size(size_in_bits) {} |
|
183 |
~BitMap() {} |
|
1 | 184 |
|
38177 | 185 |
public: |
37413
2f71679d06dd
8077144: Concurrent mark initialization takes too long
tschatzl
parents:
37059
diff
changeset
|
186 |
// Pretouch the entire range of memory this BitMap covers. |
2f71679d06dd
8077144: Concurrent mark initialization takes too long
tschatzl
parents:
37059
diff
changeset
|
187 |
void pretouch(); |
2f71679d06dd
8077144: Concurrent mark initialization takes too long
tschatzl
parents:
37059
diff
changeset
|
188 |
|
1 | 189 |
// Accessing |
37414
2672ba9af0dc
8151386: Extract card live data out of G1ConcurrentMark
tschatzl
parents:
37413
diff
changeset
|
190 |
static idx_t calc_size_in_words(size_t size_in_bits) { |
37413
2f71679d06dd
8077144: Concurrent mark initialization takes too long
tschatzl
parents:
37059
diff
changeset
|
191 |
return word_index(size_in_bits + BitsPerWord - 1); |
2f71679d06dd
8077144: Concurrent mark initialization takes too long
tschatzl
parents:
37059
diff
changeset
|
192 |
} |
2f71679d06dd
8077144: Concurrent mark initialization takes too long
tschatzl
parents:
37059
diff
changeset
|
193 |
|
38177 | 194 |
static idx_t calc_size_in_bytes(size_t size_in_bits) { |
195 |
return calc_size_in_words(size_in_bits) * BytesPerWord; |
|
196 |
} |
|
197 |
||
198 |
idx_t size() const { return _size; } |
|
199 |
idx_t size_in_words() const { return calc_size_in_words(size()); } |
|
200 |
idx_t size_in_bytes() const { return calc_size_in_bytes(size()); } |
|
201 |
||
1 | 202 |
bool at(idx_t index) const { |
203 |
verify_index(index); |
|
204 |
return (*word_addr(index) & bit_mask(index)) != 0; |
|
205 |
} |
|
206 |
||
207 |
// Align bit index up or down to the next bitmap word boundary, or check |
|
208 |
// alignment. |
|
209 |
static idx_t word_align_up(idx_t bit) { |
|
46619
a3919f5e8d2b
8178499: Remove _ptr_ and _size_ infixes from align functions
stefank
parents:
46402
diff
changeset
|
210 |
return align_up(bit, BitsPerWord); |
1 | 211 |
} |
212 |
static idx_t word_align_down(idx_t bit) { |
|
46619
a3919f5e8d2b
8178499: Remove _ptr_ and _size_ infixes from align functions
stefank
parents:
46402
diff
changeset
|
213 |
return align_down(bit, BitsPerWord); |
1 | 214 |
} |
215 |
static bool is_word_aligned(idx_t bit) { |
|
216 |
return word_align_up(bit) == bit; |
|
217 |
} |
|
218 |
||
219 |
// Set or clear the specified bit. |
|
220 |
inline void set_bit(idx_t bit); |
|
9994 | 221 |
inline void clear_bit(idx_t bit); |
1 | 222 |
|
223 |
// Atomically set or clear the specified bit. |
|
9994 | 224 |
inline bool par_set_bit(idx_t bit); |
225 |
inline bool par_clear_bit(idx_t bit); |
|
1 | 226 |
|
227 |
// Put the given value at the given offset. The parallel version |
|
228 |
// will CAS the value into the bitmap and is quite a bit slower. |
|
229 |
// The parallel version also returns a value indicating if the |
|
230 |
// calling thread was the one that changed the value of the bit. |
|
231 |
void at_put(idx_t index, bool value); |
|
232 |
bool par_at_put(idx_t index, bool value); |
|
233 |
||
234 |
// Update a range of bits. Ranges are half-open [beg, end). |
|
235 |
void set_range (idx_t beg, idx_t end); |
|
236 |
void clear_range (idx_t beg, idx_t end); |
|
237 |
void set_large_range (idx_t beg, idx_t end); |
|
238 |
void clear_large_range (idx_t beg, idx_t end); |
|
239 |
void at_put_range(idx_t beg, idx_t end, bool value); |
|
240 |
void par_at_put_range(idx_t beg, idx_t end, bool value); |
|
241 |
void at_put_large_range(idx_t beg, idx_t end, bool value); |
|
242 |
void par_at_put_large_range(idx_t beg, idx_t end, bool value); |
|
243 |
||
244 |
// Update a range of bits, using a hint about the size. Currently only |
|
245 |
// inlines the predominant case of a 1-bit range. Works best when hint is a |
|
246 |
// compile-time constant. |
|
1374 | 247 |
void set_range(idx_t beg, idx_t end, RangeSizeHint hint); |
248 |
void clear_range(idx_t beg, idx_t end, RangeSizeHint hint); |
|
249 |
void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint); |
|
250 |
void par_clear_range (idx_t beg, idx_t end, RangeSizeHint hint); |
|
251 |
||
1 | 252 |
// Clearing |
253 |
void clear_large(); |
|
1374 | 254 |
inline void clear(); |
1 | 255 |
|
1374 | 256 |
// Iteration support. Returns "true" if the iteration completed, false |
257 |
// if the iteration terminated early (because the closure "blk" returned |
|
258 |
// false). |
|
259 |
bool iterate(BitMapClosure* blk, idx_t leftIndex, idx_t rightIndex); |
|
260 |
bool iterate(BitMapClosure* blk) { |
|
1 | 261 |
// call the version that takes an interval |
1374 | 262 |
return iterate(blk, 0, size()); |
1 | 263 |
} |
264 |
||
1374 | 265 |
// Looking for 1's and 0's at indices equal to or greater than "l_index", |
266 |
// stopping if none has been found before "r_index", and returning |
|
267 |
// "r_index" (which must be at most "size") in that case. |
|
1 | 268 |
idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const; |
269 |
idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const; |
|
270 |
||
271 |
idx_t get_next_one_offset(idx_t offset) const { |
|
272 |
return get_next_one_offset(offset, size()); |
|
273 |
} |
|
274 |
idx_t get_next_zero_offset(idx_t offset) const { |
|
275 |
return get_next_zero_offset(offset, size()); |
|
276 |
} |
|
277 |
||
46402 | 278 |
// Like "get_next_one_offset", except requires that "r_index" is |
279 |
// aligned to bitsizeof(bm_word_t). |
|
280 |
idx_t get_next_one_offset_aligned_right(idx_t l_index, idx_t r_index) const; |
|
281 |
||
1374 | 282 |
// Returns the number of bits set in the bitmap. |
283 |
idx_t count_one_bits() const; |
|
1 | 284 |
|
285 |
// Set operations. |
|
38102
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
286 |
void set_union(const BitMap& bits); |
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
287 |
void set_difference(const BitMap& bits); |
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
288 |
void set_intersection(const BitMap& bits); |
1 | 289 |
// Returns true iff "this" is a superset of "bits". |
38102
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
290 |
bool contains(const BitMap& bits) const; |
1 | 291 |
// Returns true iff "this and "bits" have a non-empty intersection. |
38102
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
292 |
bool intersects(const BitMap& bits) const; |
1 | 293 |
|
294 |
// Returns result of whether this map changed |
|
295 |
// during the operation |
|
38102
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
296 |
bool set_union_with_result(const BitMap& bits); |
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
297 |
bool set_difference_with_result(const BitMap& bits); |
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
298 |
bool set_intersection_with_result(const BitMap& bits); |
1 | 299 |
|
38102
839593075df1
8141496: BitMap set operations copy their other BitMap argument
stefank
parents:
37466
diff
changeset
|
300 |
void set_from(const BitMap& bits); |
1 | 301 |
|
40639
83c879c8db57
8155043: BitMap set operations assume clear bits beyond unaligned end
kbarrett
parents:
39219
diff
changeset
|
302 |
bool is_same(const BitMap& bits) const; |
1 | 303 |
|
304 |
// Test if all bits are set or cleared |
|
305 |
bool is_full() const; |
|
306 |
bool is_empty() const; |
|
307 |
||
51491
187c84a5efe1
8208658: Make CDS archived heap regions usable even if compressed oop encoding has changed
iklam
parents:
49828
diff
changeset
|
308 |
void write_to(bm_word_t* buffer, size_t buffer_size_in_bytes) const; |
16685
41c34debcde0
8011872: Include Bit Map addresses in the hs_err files
stefank
parents:
12272
diff
changeset
|
309 |
void print_on_error(outputStream* st, const char* prefix) const; |
1 | 310 |
|
311 |
#ifndef PRODUCT |
|
312 |
public: |
|
313 |
// Printing |
|
314 |
void print_on(outputStream* st) const; |
|
315 |
#endif |
|
316 |
}; |
|
317 |
||
38177 | 318 |
// A concrete implementation of the the "abstract" BitMap class. |
319 |
// |
|
320 |
// The BitMapView is used when the backing storage is managed externally. |
|
321 |
class BitMapView : public BitMap { |
|
322 |
public: |
|
323 |
BitMapView() : BitMap(NULL, 0) {} |
|
324 |
BitMapView(bm_word_t* map, idx_t size_in_bits) : BitMap(map, size_in_bits) {} |
|
325 |
}; |
|
326 |
||
327 |
// A BitMap with storage in a ResourceArea. |
|
328 |
class ResourceBitMap : public BitMap { |
|
329 |
||
330 |
public: |
|
331 |
ResourceBitMap() : BitMap(NULL, 0) {} |
|
332 |
// Clears the bitmap memory. |
|
333 |
ResourceBitMap(idx_t size_in_bits); |
|
334 |
||
335 |
// Resize the backing bitmap memory. |
|
336 |
// |
|
337 |
// Old bits are transfered to the new memory |
|
338 |
// and the extended memory is cleared. |
|
339 |
void resize(idx_t new_size_in_bits); |
|
340 |
||
341 |
// Set up and clear the bitmap memory. |
|
342 |
// |
|
343 |
// Precondition: The bitmap was default constructed and has |
|
344 |
// not yet had memory allocated via resize or initialize. |
|
345 |
void initialize(idx_t size_in_bits); |
|
346 |
||
347 |
// Set up and clear the bitmap memory. |
|
348 |
// |
|
349 |
// Can be called on previously initialized bitmaps. |
|
350 |
void reinitialize(idx_t size_in_bits); |
|
351 |
}; |
|
352 |
||
353 |
// A BitMap with storage in a specific Arena. |
|
354 |
class ArenaBitMap : public BitMap { |
|
355 |
public: |
|
356 |
// Clears the bitmap memory. |
|
357 |
ArenaBitMap(Arena* arena, idx_t size_in_bits); |
|
358 |
||
359 |
private: |
|
360 |
// Don't allow copy or assignment. |
|
361 |
ArenaBitMap(const ArenaBitMap&); |
|
362 |
ArenaBitMap& operator=(const ArenaBitMap&); |
|
363 |
}; |
|
364 |
||
365 |
// A BitMap with storage in the CHeap. |
|
366 |
class CHeapBitMap : public BitMap { |
|
367 |
||
368 |
private: |
|
369 |
// Don't allow copy or assignment, to prevent the |
|
370 |
// allocated memory from leaking out to other instances. |
|
371 |
CHeapBitMap(const CHeapBitMap&); |
|
372 |
CHeapBitMap& operator=(const CHeapBitMap&); |
|
373 |
||
46745
f7b9bb98bb72
8176571: Fine bitmaps should be allocated as belonging to mtGC, not mtInternal
kbarrett
parents:
46625
diff
changeset
|
374 |
// NMT memory type |
f7b9bb98bb72
8176571: Fine bitmaps should be allocated as belonging to mtGC, not mtInternal
kbarrett
parents:
46625
diff
changeset
|
375 |
MEMFLAGS _flags; |
f7b9bb98bb72
8176571: Fine bitmaps should be allocated as belonging to mtGC, not mtInternal
kbarrett
parents:
46625
diff
changeset
|
376 |
|
38177 | 377 |
public: |
46745
f7b9bb98bb72
8176571: Fine bitmaps should be allocated as belonging to mtGC, not mtInternal
kbarrett
parents:
46625
diff
changeset
|
378 |
CHeapBitMap(MEMFLAGS flags = mtInternal) : BitMap(NULL, 0), _flags(flags) {} |
38177 | 379 |
// Clears the bitmap memory. |
49828
ee3555b4a130
8201647: Make initial clearing of CHeapBitMap optional
pliden
parents:
49670
diff
changeset
|
380 |
CHeapBitMap(idx_t size_in_bits, MEMFLAGS flags = mtInternal, bool clear = true); |
38177 | 381 |
~CHeapBitMap(); |
382 |
||
383 |
// Resize the backing bitmap memory. |
|
384 |
// |
|
385 |
// Old bits are transfered to the new memory |
|
386 |
// and the extended memory is cleared. |
|
387 |
void resize(idx_t new_size_in_bits); |
|
388 |
||
389 |
// Set up and clear the bitmap memory. |
|
390 |
// |
|
391 |
// Precondition: The bitmap was default constructed and has |
|
392 |
// not yet had memory allocated via resize or initialize. |
|
393 |
void initialize(idx_t size_in_bits); |
|
394 |
||
395 |
// Set up and clear the bitmap memory. |
|
396 |
// |
|
397 |
// Can be called on previously initialized bitmaps. |
|
398 |
void reinitialize(idx_t size_in_bits); |
|
399 |
}; |
|
400 |
||
1 | 401 |
// Convenience class wrapping BitMap which provides multiple bits per slot. |
49364
601146c66cad
8173070: Remove ValueObj class for allocation subclassing for runtime code
coleenp
parents:
47216
diff
changeset
|
402 |
class BitMap2D { |
1 | 403 |
public: |
1374 | 404 |
typedef BitMap::idx_t idx_t; // Type used for bit and word indices. |
405 |
typedef BitMap::bm_word_t bm_word_t; // Element type of array that |
|
406 |
// represents the bitmap. |
|
1 | 407 |
private: |
38177 | 408 |
ResourceBitMap _map; |
409 |
idx_t _bits_per_slot; |
|
1 | 410 |
|
411 |
idx_t bit_index(idx_t slot_index, idx_t bit_within_slot_index) const { |
|
412 |
return slot_index * _bits_per_slot + bit_within_slot_index; |
|
413 |
} |
|
414 |
||
415 |
void verify_bit_within_slot_index(idx_t index) const { |
|
416 |
assert(index < _bits_per_slot, "bit_within_slot index out of bounds"); |
|
417 |
} |
|
418 |
||
419 |
public: |
|
420 |
// Construction. bits_per_slot must be greater than 0. |
|
38177 | 421 |
BitMap2D(idx_t bits_per_slot) : |
422 |
_map(), _bits_per_slot(bits_per_slot) {} |
|
1 | 423 |
|
424 |
// Allocates necessary data structure in resource area. bits_per_slot must be greater than 0. |
|
38177 | 425 |
BitMap2D(idx_t size_in_slots, idx_t bits_per_slot) : |
426 |
_map(size_in_slots * bits_per_slot), _bits_per_slot(bits_per_slot) {} |
|
1 | 427 |
|
428 |
idx_t size_in_bits() { |
|
429 |
return _map.size(); |
|
430 |
} |
|
431 |
||
432 |
// Returns number of full slots that have been allocated |
|
433 |
idx_t size_in_slots() { |
|
434 |
// Round down |
|
435 |
return _map.size() / _bits_per_slot; |
|
436 |
} |
|
437 |
||
37059
c482915a21aa
8151440: Move BitMap verfication inline functions out from bitMap.hpp
stefank
parents:
37058
diff
changeset
|
438 |
bool 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:
37058
diff
changeset
|
439 |
bool 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:
37058
diff
changeset
|
440 |
void 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:
37058
diff
changeset
|
441 |
void 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:
37058
diff
changeset
|
442 |
void 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:
37058
diff
changeset
|
443 |
void at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value); |
1 | 444 |
}; |
445 |
||
1374 | 446 |
// Closure for iterating over BitMaps |
1 | 447 |
|
49364
601146c66cad
8173070: Remove ValueObj class for allocation subclassing for runtime code
coleenp
parents:
47216
diff
changeset
|
448 |
class BitMapClosure { |
1374 | 449 |
public: |
450 |
// Callback when bit in map is set. Should normally return "true"; |
|
451 |
// return of false indicates that the bitmap iteration should terminate. |
|
452 |
virtual bool do_bit(BitMap::idx_t offset) = 0; |
|
453 |
}; |
|
7397 | 454 |
|
455 |
#endif // SHARE_VM_UTILITIES_BITMAP_HPP |