< prev index next >

src/hotspot/share/utilities/bitMap.hpp

Print this page

144 
145   // Utilities for ranges of bits.  Ranges are half-open [beg, end).
146 
147   // Ranges within a single word.
148   bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
149   void  set_range_within_word      (idx_t beg, idx_t end);
150   void  clear_range_within_word    (idx_t beg, idx_t end);
151   void  par_put_range_within_word  (idx_t beg, idx_t end, bool value);
152 
153   // Ranges spanning entire words.
154   void      set_range_of_words         (idx_t beg, idx_t end);
155   void      clear_range_of_words       (idx_t beg, idx_t end);
156   void      set_large_range_of_words   (idx_t beg, idx_t end);
157   void      clear_large_range_of_words (idx_t beg, idx_t end);
158 
159   static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
160 
161   idx_t count_one_bits_within_word(idx_t beg, idx_t end) const;
162   idx_t count_one_bits_in_range_of_words(idx_t beg_full_word, idx_t end_full_word) const;
163 
164   // Verification.
165 
166   // Verify size_in_bits does not exceed max_size_in_bits().
167   static void verify_size(idx_t size_in_bits) NOT_DEBUG_RETURN;
168   // Verify bit is less than size().
169   void verify_index(idx_t bit) const NOT_DEBUG_RETURN;
170   // Verify bit is not greater than size().
171   void verify_limit(idx_t bit) const NOT_DEBUG_RETURN;
172   // Verify [beg,end) is a valid range, e.g. beg <= end <= size().
173   void verify_range(idx_t beg, idx_t end) const NOT_DEBUG_RETURN;
174 
175   // Allocation Helpers.
176 
177   // Allocates and clears the bitmap memory.
178   template <class Allocator>
179   static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true);
180 
181   // Reallocates and clears the new bitmap memory.
182   template <class Allocator>
183   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);
184 
185   // Free the bitmap memory.
186   template <class Allocator>
187   static void free(const Allocator&, bm_word_t* map, idx_t size_in_bits);
188 
189   // Protected functions, that are used by BitMap sub-classes that support them.
190 
191   // Resize the backing bitmap memory.
192   //
193   // Old bits are transfered to the new memory
194   // and the extended memory is cleared.

267   void clear_range (idx_t beg, idx_t end);
268   void set_large_range   (idx_t beg, idx_t end);
269   void clear_large_range (idx_t beg, idx_t end);
270   void at_put_range(idx_t beg, idx_t end, bool value);
271   void par_at_put_range(idx_t beg, idx_t end, bool value);
272   void at_put_large_range(idx_t beg, idx_t end, bool value);
273   void par_at_put_large_range(idx_t beg, idx_t end, bool value);
274 
275   // Update a range of bits, using a hint about the size.  Currently only
276   // inlines the predominant case of a 1-bit range.  Works best when hint is a
277   // compile-time constant.
278   void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
279   void clear_range(idx_t beg, idx_t end, RangeSizeHint hint);
280   void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint);
281   void par_clear_range  (idx_t beg, idx_t end, RangeSizeHint hint);
282 
283   // Clearing
284   void clear_large();
285   inline void clear();
286 











287   // Iteration support.  Applies the closure to the index for each set bit,
288   // starting from the least index in the range to the greatest, in order.
289   // The iteration terminates if the closure returns false.  Returns true if
290   // the iteration completed, false if terminated early because the closure
291   // returned false.  If the closure modifies the bitmap, modifications to
292   // bits at indices greater than the current index will affect which further
293   // indices the closure will be applied to.
294   // precondition: beg and end form a valid range.
295   bool iterate(BitMapClosure* cl, idx_t beg, idx_t end);
296   bool iterate(BitMapClosure* cl);



297 
298   // Looking for 1's and 0's at indices equal to or greater than "l_index",
299   // stopping if none has been found before "r_index", and returning
300   // "r_index" (which must be at most "size") in that case.
301   idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const;
302   idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const;
303 
304   idx_t get_next_one_offset(idx_t offset) const {
305     return get_next_one_offset(offset, size());
306   }
307   idx_t get_next_zero_offset(idx_t offset) const {
308     return get_next_zero_offset(offset, size());
309   }
310 
311   // Like "get_next_one_offset", except requires that "r_index" is
312   // aligned to bitsizeof(bm_word_t).
313   idx_t get_next_one_offset_aligned_right(idx_t l_index, idx_t r_index) const;
314 
315   // Returns the number of bits set in the bitmap.
316   idx_t count_one_bits() const;

144 
145   // Utilities for ranges of bits.  Ranges are half-open [beg, end).
146 
147   // Ranges within a single word.
148   bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
149   void  set_range_within_word      (idx_t beg, idx_t end);
150   void  clear_range_within_word    (idx_t beg, idx_t end);
151   void  par_put_range_within_word  (idx_t beg, idx_t end, bool value);
152 
153   // Ranges spanning entire words.
154   void      set_range_of_words         (idx_t beg, idx_t end);
155   void      clear_range_of_words       (idx_t beg, idx_t end);
156   void      set_large_range_of_words   (idx_t beg, idx_t end);
157   void      clear_large_range_of_words (idx_t beg, idx_t end);
158 
159   static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
160 
161   idx_t count_one_bits_within_word(idx_t beg, idx_t end) const;
162   idx_t count_one_bits_in_range_of_words(idx_t beg_full_word, idx_t end_full_word) const;
163 











164   // Allocation Helpers.
165 
166   // Allocates and clears the bitmap memory.
167   template <class Allocator>
168   static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true);
169 
170   // Reallocates and clears the new bitmap memory.
171   template <class Allocator>
172   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);
173 
174   // Free the bitmap memory.
175   template <class Allocator>
176   static void free(const Allocator&, bm_word_t* map, idx_t size_in_bits);
177 
178   // Protected functions, that are used by BitMap sub-classes that support them.
179 
180   // Resize the backing bitmap memory.
181   //
182   // Old bits are transfered to the new memory
183   // and the extended memory is cleared.

256   void clear_range (idx_t beg, idx_t end);
257   void set_large_range   (idx_t beg, idx_t end);
258   void clear_large_range (idx_t beg, idx_t end);
259   void at_put_range(idx_t beg, idx_t end, bool value);
260   void par_at_put_range(idx_t beg, idx_t end, bool value);
261   void at_put_large_range(idx_t beg, idx_t end, bool value);
262   void par_at_put_large_range(idx_t beg, idx_t end, bool value);
263 
264   // Update a range of bits, using a hint about the size.  Currently only
265   // inlines the predominant case of a 1-bit range.  Works best when hint is a
266   // compile-time constant.
267   void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
268   void clear_range(idx_t beg, idx_t end, RangeSizeHint hint);
269   void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint);
270   void par_clear_range  (idx_t beg, idx_t end, RangeSizeHint hint);
271 
272   // Clearing
273   void clear_large();
274   inline void clear();
275 
276   // Verification.
277 
278   // Verify size_in_bits does not exceed max_size_in_bits().
279   static void verify_size(idx_t size_in_bits) NOT_DEBUG_RETURN;
280   // Verify bit is less than size().
281   void verify_index(idx_t bit) const NOT_DEBUG_RETURN;
282   // Verify bit is not greater than size().
283   void verify_limit(idx_t bit) const NOT_DEBUG_RETURN;
284   // Verify [beg,end) is a valid range, e.g. beg <= end <= size().
285   void verify_range(idx_t beg, idx_t end) const NOT_DEBUG_RETURN;
286   
287   // Iteration support.  Applies the closure to the index for each set bit,
288   // starting from the least index in the range to the greatest, in order.
289   // The iteration terminates if the closure returns false.  Returns true if
290   // the iteration completed, false if terminated early because the closure
291   // returned false.  If the closure modifies the bitmap, modifications to
292   // bits at indices greater than the current index will affect which further
293   // indices the closure will be applied to.
294   // precondition: beg and end form a valid range.
295   template <class BitMapClosureType>
296   bool iterate(BitMapClosureType* cl, idx_t beg, idx_t end);
297 
298   template <class BitMapClosureType>
299   bool iterate(BitMapClosureType* cl);
300 
301   // Looking for 1's and 0's at indices equal to or greater than "l_index",
302   // stopping if none has been found before "r_index", and returning
303   // "r_index" (which must be at most "size") in that case.
304   idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const;
305   idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const;
306 
307   idx_t get_next_one_offset(idx_t offset) const {
308     return get_next_one_offset(offset, size());
309   }
310   idx_t get_next_zero_offset(idx_t offset) const {
311     return get_next_zero_offset(offset, size());
312   }
313 
314   // Like "get_next_one_offset", except requires that "r_index" is
315   // aligned to bitsizeof(bm_word_t).
316   idx_t get_next_one_offset_aligned_right(idx_t l_index, idx_t r_index) const;
317 
318   // Returns the number of bits set in the bitmap.
319   idx_t count_one_bits() const;
< prev index next >