1.1 --- a/src/share/vm/utilities/bitMap.hpp Wed Jun 04 13:51:09 2008 -0700
1.2 +++ b/src/share/vm/utilities/bitMap.hpp Thu Jun 05 15:57:56 2008 -0700
1.3 @@ -22,25 +22,19 @@
1.4 *
1.5 */
1.6
1.7 -// Closure for iterating over BitMaps
1.8 +// Forward decl;
1.9 +class BitMapClosure;
1.10
1.11 -class BitMapClosure VALUE_OBJ_CLASS_SPEC {
1.12 - public:
1.13 - // Callback when bit in map is set
1.14 - virtual void do_bit(size_t offset) = 0;
1.15 -};
1.16 -
1.17 -
1.18 -// Operations for bitmaps represented as arrays of unsigned 32- or 64-bit
1.19 -// integers (uintptr_t).
1.20 -//
1.21 -// Bit offsets are numbered from 0 to size-1
1.22 +// Operations for bitmaps represented as arrays of unsigned integers.
1.23 +// Bit offsets are numbered from 0 to size-1.
1.24
1.25 class BitMap VALUE_OBJ_CLASS_SPEC {
1.26 friend class BitMap2D;
1.27
1.28 public:
1.29 typedef size_t idx_t; // Type used for bit and word indices.
1.30 + typedef uintptr_t bm_word_t; // Element type of array that represents
1.31 + // the bitmap.
1.32
1.33 // Hints for range sizes.
1.34 typedef enum {
1.35 @@ -48,8 +42,8 @@
1.36 } RangeSizeHint;
1.37
1.38 private:
1.39 - idx_t* _map; // First word in bitmap
1.40 - idx_t _size; // Size of bitmap (in bits)
1.41 + bm_word_t* _map; // First word in bitmap
1.42 + idx_t _size; // Size of bitmap (in bits)
1.43
1.44 // Puts the given value at the given offset, using resize() to size
1.45 // the bitmap appropriately if needed using factor-of-two expansion.
1.46 @@ -62,7 +56,7 @@
1.47
1.48 // Return a mask that will select the specified bit, when applied to the word
1.49 // containing the bit.
1.50 - static idx_t bit_mask(idx_t bit) { return (idx_t)1 << bit_in_word(bit); }
1.51 + static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
1.52
1.53 // Return the index of the word containing the specified bit.
1.54 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; }
1.55 @@ -71,66 +65,68 @@
1.56 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
1.57
1.58 // Return the array of bitmap words, or a specific word from it.
1.59 - idx_t* map() const { return _map; }
1.60 - idx_t map(idx_t word) const { return _map[word]; }
1.61 + bm_word_t* map() const { return _map; }
1.62 + bm_word_t map(idx_t word) const { return _map[word]; }
1.63
1.64 // Return a pointer to the word containing the specified bit.
1.65 - idx_t* word_addr(idx_t bit) const { return map() + word_index(bit); }
1.66 + bm_word_t* word_addr(idx_t bit) const { return map() + word_index(bit); }
1.67
1.68 // Set a word to a specified value or to all ones; clear a word.
1.69 - void set_word (idx_t word, idx_t val) { _map[word] = val; }
1.70 + void set_word (idx_t word, bm_word_t val) { _map[word] = val; }
1.71 void set_word (idx_t word) { set_word(word, ~(uintptr_t)0); }
1.72 void clear_word(idx_t word) { _map[word] = 0; }
1.73
1.74 // Utilities for ranges of bits. Ranges are half-open [beg, end).
1.75
1.76 // Ranges within a single word.
1.77 - inline idx_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
1.78 - inline void set_range_within_word (idx_t beg, idx_t end);
1.79 - inline void clear_range_within_word (idx_t beg, idx_t end);
1.80 - inline void par_put_range_within_word (idx_t beg, idx_t end, bool value);
1.81 + bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
1.82 + void set_range_within_word (idx_t beg, idx_t end);
1.83 + void clear_range_within_word (idx_t beg, idx_t end);
1.84 + void par_put_range_within_word (idx_t beg, idx_t end, bool value);
1.85
1.86 // Ranges spanning entire words.
1.87 - inline void set_range_of_words (idx_t beg, idx_t end);
1.88 - inline void clear_range_of_words (idx_t beg, idx_t end);
1.89 - inline void set_large_range_of_words (idx_t beg, idx_t end);
1.90 - inline void clear_large_range_of_words (idx_t beg, idx_t end);
1.91 + void set_range_of_words (idx_t beg, idx_t end);
1.92 + void clear_range_of_words (idx_t beg, idx_t end);
1.93 + void set_large_range_of_words (idx_t beg, idx_t end);
1.94 + void clear_large_range_of_words (idx_t beg, idx_t end);
1.95
1.96 // The index of the first full word in a range.
1.97 - inline idx_t word_index_round_up(idx_t bit) const;
1.98 + idx_t word_index_round_up(idx_t bit) const;
1.99
1.100 // Verification, statistics.
1.101 - void verify_index(idx_t index) const {
1.102 - assert(index < _size, "BitMap index out of bounds");
1.103 - }
1.104 + void verify_index(idx_t index) const;
1.105 + void verify_range(idx_t beg_index, idx_t end_index) const;
1.106
1.107 - void verify_range(idx_t beg_index, idx_t end_index) const {
1.108 -#ifdef ASSERT
1.109 - assert(beg_index <= end_index, "BitMap range error");
1.110 - // Note that [0,0) and [size,size) are both valid ranges.
1.111 - if (end_index != _size) verify_index(end_index);
1.112 -#endif
1.113 - }
1.114 + static idx_t* _pop_count_table;
1.115 + static void init_pop_count_table();
1.116 + static idx_t num_set_bits(bm_word_t w);
1.117 + static idx_t num_set_bits_from_table(unsigned char c);
1.118
1.119 public:
1.120
1.121 // Constructs a bitmap with no map, and size 0.
1.122 BitMap() : _map(NULL), _size(0) {}
1.123
1.124 - // Construction
1.125 - BitMap(idx_t* map, idx_t size_in_bits);
1.126 + // Constructs a bitmap with the given map and size.
1.127 + BitMap(bm_word_t* map, idx_t size_in_bits);
1.128
1.129 - // Allocates necessary data structure in resource area
1.130 - BitMap(idx_t size_in_bits);
1.131 + // Constructs an empty bitmap of the given size (that is, this clears the
1.132 + // new bitmap). Allocates the map array in resource area if
1.133 + // "in_resource_area" is true, else in the C heap.
1.134 + BitMap(idx_t size_in_bits, bool in_resource_area = true);
1.135
1.136 - void set_map(idx_t* map) { _map = map; }
1.137 + // Set the map and size.
1.138 + void set_map(bm_word_t* map) { _map = map; }
1.139 void set_size(idx_t size_in_bits) { _size = size_in_bits; }
1.140
1.141 - // Allocates necessary data structure in resource area.
1.142 + // Allocates necessary data structure, either in the resource area
1.143 + // or in the C heap, as indicated by "in_resource_area."
1.144 // Preserves state currently in bit map by copying data.
1.145 // Zeros any newly-addressable bits.
1.146 - // Does not perform any frees (i.e., of current _map).
1.147 - void resize(idx_t size_in_bits);
1.148 + // If "in_resource_area" is false, frees the current map.
1.149 + // (Note that this assumes that all calls to "resize" on the same BitMap
1.150 + // use the same value for "in_resource_area".)
1.151 + void resize(idx_t size_in_bits, bool in_resource_area = true);
1.152
1.153 // Accessing
1.154 idx_t size() const { return _size; }
1.155 @@ -157,11 +153,11 @@
1.156
1.157 // Set or clear the specified bit.
1.158 inline void set_bit(idx_t bit);
1.159 - inline void clear_bit(idx_t bit);
1.160 + void clear_bit(idx_t bit);
1.161
1.162 // Atomically set or clear the specified bit.
1.163 - inline bool par_set_bit(idx_t bit);
1.164 - inline bool par_clear_bit(idx_t bit);
1.165 + bool par_set_bit(idx_t bit);
1.166 + bool par_clear_bit(idx_t bit);
1.167
1.168 // Put the given value at the given offset. The parallel version
1.169 // will CAS the value into the bitmap and is quite a bit slower.
1.170 @@ -183,23 +179,61 @@
1.171 // Update a range of bits, using a hint about the size. Currently only
1.172 // inlines the predominant case of a 1-bit range. Works best when hint is a
1.173 // compile-time constant.
1.174 - inline void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
1.175 - inline void clear_range(idx_t beg, idx_t end, RangeSizeHint hint);
1.176 - inline void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint);
1.177 - inline void par_clear_range (idx_t beg, idx_t end, RangeSizeHint hint);
1.178 + void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
1.179 + void clear_range(idx_t beg, idx_t end, RangeSizeHint hint);
1.180 + void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint);
1.181 + void par_clear_range (idx_t beg, idx_t end, RangeSizeHint hint);
1.182 +
1.183 + // It performs the union operation between subsets of equal length
1.184 + // of two bitmaps (the target bitmap of the method and the
1.185 + // from_bitmap) and stores the result to the target bitmap. The
1.186 + // from_start_index represents the first bit index of the subrange
1.187 + // of the from_bitmap. The to_start_index is the equivalent of the
1.188 + // target bitmap. Both indexes should be word-aligned, i.e. they
1.189 + // should correspond to the first bit on a bitmap word (it's up to
1.190 + // the caller to ensure this; the method does check it). The length
1.191 + // of the subset is specified with word_num and it is in number of
1.192 + // bitmap words. The caller should ensure that this is at least 2
1.193 + // (smaller ranges are not support to save extra checks). Again,
1.194 + // this is checked in the method.
1.195 + //
1.196 + // Atomicity concerns: it is assumed that any contention on the
1.197 + // target bitmap with other threads will happen on the first and
1.198 + // last words; the ones in between will be "owned" exclusively by
1.199 + // the calling thread and, in fact, they will already be 0. So, the
1.200 + // method performs a CAS on the first word, copies the next
1.201 + // word_num-2 words, and finally performs a CAS on the last word.
1.202 + void mostly_disjoint_range_union(BitMap* from_bitmap,
1.203 + idx_t from_start_index,
1.204 + idx_t to_start_index,
1.205 + size_t word_num);
1.206 +
1.207
1.208 // Clearing
1.209 - void clear();
1.210 void clear_large();
1.211 + inline void clear();
1.212
1.213 - // Iteration support
1.214 - void iterate(BitMapClosure* blk, idx_t leftIndex, idx_t rightIndex);
1.215 - inline void iterate(BitMapClosure* blk) {
1.216 + // Iteration support. Returns "true" if the iteration completed, false
1.217 + // if the iteration terminated early (because the closure "blk" returned
1.218 + // false).
1.219 + bool iterate(BitMapClosure* blk, idx_t leftIndex, idx_t rightIndex);
1.220 + bool iterate(BitMapClosure* blk) {
1.221 // call the version that takes an interval
1.222 - iterate(blk, 0, size());
1.223 + return iterate(blk, 0, size());
1.224 }
1.225
1.226 - // Looking for 1's and 0's to the "right"
1.227 + // Looking for 1's and 0's at indices equal to or greater than "l_index",
1.228 + // stopping if none has been found before "r_index", and returning
1.229 + // "r_index" (which must be at most "size") in that case.
1.230 + idx_t get_next_one_offset_inline (idx_t l_index, idx_t r_index) const;
1.231 + idx_t get_next_zero_offset_inline(idx_t l_index, idx_t r_index) const;
1.232 +
1.233 + // Like "get_next_one_offset_inline", except requires that "r_index" is
1.234 + // aligned to bitsizeof(bm_word_t).
1.235 + idx_t get_next_one_offset_inline_aligned_right(idx_t l_index,
1.236 + idx_t r_index) const;
1.237 +
1.238 + // Non-inline versionsof the above.
1.239 idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const;
1.240 idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const;
1.241
1.242 @@ -210,12 +244,8 @@
1.243 return get_next_zero_offset(offset, size());
1.244 }
1.245
1.246 -
1.247 -
1.248 - // Find the next one bit in the range [beg_bit, end_bit), or return end_bit if
1.249 - // no one bit is found. Equivalent to get_next_one_offset(), but inline for
1.250 - // use in performance-critical code.
1.251 - inline idx_t find_next_one_bit(idx_t beg_bit, idx_t end_bit) const;
1.252 + // Returns the number of bits set in the bitmap.
1.253 + idx_t count_one_bits() const;
1.254
1.255 // Set operations.
1.256 void set_union(BitMap bits);
1.257 @@ -232,6 +262,15 @@
1.258 bool set_difference_with_result(BitMap bits);
1.259 bool set_intersection_with_result(BitMap bits);
1.260
1.261 + // Requires the submap of "bits" starting at offset to be at least as
1.262 + // large as "this". Modifies "this" to be the intersection of its
1.263 + // current contents and the submap of "bits" starting at "offset" of the
1.264 + // same length as "this."
1.265 + // (For expedience, currently requires the offset to be aligned to the
1.266 + // bitsize of a uintptr_t. This should go away in the future though it
1.267 + // will probably remain a good case to optimize.)
1.268 + void set_intersection_at_offset(BitMap bits, idx_t offset);
1.269 +
1.270 void set_from(BitMap bits);
1.271
1.272 bool is_same(BitMap bits);
1.273 @@ -248,58 +287,13 @@
1.274 #endif
1.275 };
1.276
1.277 -inline void BitMap::set_bit(idx_t bit) {
1.278 - verify_index(bit);
1.279 - *word_addr(bit) |= bit_mask(bit);
1.280 -}
1.281 -
1.282 -inline void BitMap::clear_bit(idx_t bit) {
1.283 - verify_index(bit);
1.284 - *word_addr(bit) &= ~bit_mask(bit);
1.285 -}
1.286 -
1.287 -inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
1.288 - if (hint == small_range && end - beg == 1) {
1.289 - set_bit(beg);
1.290 - } else {
1.291 - if (hint == large_range) {
1.292 - set_large_range(beg, end);
1.293 - } else {
1.294 - set_range(beg, end);
1.295 - }
1.296 - }
1.297 -}
1.298 -
1.299 -inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
1.300 - if (hint == small_range && end - beg == 1) {
1.301 - clear_bit(beg);
1.302 - } else {
1.303 - if (hint == large_range) {
1.304 - clear_large_range(beg, end);
1.305 - } else {
1.306 - clear_range(beg, end);
1.307 - }
1.308 - }
1.309 -}
1.310 -
1.311 -inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
1.312 - if (hint == small_range && end - beg == 1) {
1.313 - par_at_put(beg, true);
1.314 - } else {
1.315 - if (hint == large_range) {
1.316 - par_at_put_large_range(beg, end, true);
1.317 - } else {
1.318 - par_at_put_range(beg, end, true);
1.319 - }
1.320 - }
1.321 -}
1.322 -
1.323
1.324 // Convenience class wrapping BitMap which provides multiple bits per slot.
1.325 class BitMap2D VALUE_OBJ_CLASS_SPEC {
1.326 public:
1.327 - typedef size_t idx_t; // Type used for bit and word indices.
1.328 -
1.329 + typedef BitMap::idx_t idx_t; // Type used for bit and word indices.
1.330 + typedef BitMap::bm_word_t bm_word_t; // Element type of array that
1.331 + // represents the bitmap.
1.332 private:
1.333 BitMap _map;
1.334 idx_t _bits_per_slot;
1.335 @@ -314,7 +308,7 @@
1.336
1.337 public:
1.338 // Construction. bits_per_slot must be greater than 0.
1.339 - BitMap2D(uintptr_t* map, idx_t size_in_slots, idx_t bits_per_slot);
1.340 + BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot);
1.341
1.342 // Allocates necessary data structure in resource area. bits_per_slot must be greater than 0.
1.343 BitMap2D(idx_t size_in_slots, idx_t bits_per_slot);
1.344 @@ -359,38 +353,14 @@
1.345 _map.at_put_grow(bit_index(slot_index, bit_within_slot_index), value);
1.346 }
1.347
1.348 - void clear() {
1.349 - _map.clear();
1.350 - }
1.351 + void clear();
1.352 };
1.353
1.354 +// Closure for iterating over BitMaps
1.355
1.356 -
1.357 -inline void BitMap::set_range_of_words(idx_t beg, idx_t end) {
1.358 - uintptr_t* map = _map;
1.359 - for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0;
1.360 -}
1.361 -
1.362 -
1.363 -inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
1.364 - uintptr_t* map = _map;
1.365 - for (idx_t i = beg; i < end; ++i) map[i] = 0;
1.366 -}
1.367 -
1.368 -
1.369 -inline void BitMap::clear() {
1.370 - clear_range_of_words(0, size_in_words());
1.371 -}
1.372 -
1.373 -
1.374 -inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
1.375 - if (hint == small_range && end - beg == 1) {
1.376 - par_at_put(beg, false);
1.377 - } else {
1.378 - if (hint == large_range) {
1.379 - par_at_put_large_range(beg, end, false);
1.380 - } else {
1.381 - par_at_put_range(beg, end, false);
1.382 - }
1.383 - }
1.384 -}
1.385 +class BitMapClosure VALUE_OBJ_CLASS_SPEC {
1.386 + public:
1.387 + // Callback when bit in map is set. Should normally return "true";
1.388 + // return of false indicates that the bitmap iteration should terminate.
1.389 + virtual bool do_bit(BitMap::idx_t offset) = 0;
1.390 +};
