src/hotspot/share/utilities/bitMap.hpp

rev 54932 : [mq]: tschatzl_review
rev 54933 : [mq]: stefank_review

*** 46,71 ****
  class BitMap {
    friend class BitMap2D;
  
   public:
    typedef size_t idx_t;         // Type used for bit and word indices.
!   typedef uintptr_t bm_word_t;  // Element type of array that represents
!                                 // the bitmap.  BitsPerWord bits per element.
  
    // Hints for range sizes.
    typedef enum {
      unknown_range, small_range, large_range
    } RangeSizeHint;
  
   private:
    bm_word_t* _map;     // First word in bitmap
    idx_t      _size;    // Size of bitmap (in bits)
  
!   // Limit max_size_in_bits so roundup in calc_size_in_words can't overflow.
    static idx_t max_size_in_words() { return word_index(~idx_t(0)); }
    static idx_t max_size_in_bits() { return max_size_in_words() * BitsPerWord; }
  
    // Helper for get_next_{zero,one}_bit variants.
    // - flip designates whether searching for 1s or 0s.  Must be one of
    //   find_{zeros,ones}_flip.
    // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
    template<bm_word_t flip, bool aligned_right>
--- 46,77 ----
  class BitMap {
    friend class BitMap2D;
  
   public:
    typedef size_t idx_t;         // Type used for bit and word indices.
!   typedef uintptr_t bm_word_t;  // Element type of array that represents the
!                                 // bitmap, with BitsPerWord bits per element.
!   // If this were to fail, there are lots of places that would need repair.
!   STATIC_ASSERT((sizeof(bm_word_t) * BitsPerByte) == BitsPerWord);
  
    // Hints for range sizes.
    typedef enum {
      unknown_range, small_range, large_range
    } RangeSizeHint;
  
   private:
    bm_word_t* _map;     // First word in bitmap
    idx_t      _size;    // Size of bitmap (in bits)
  
!   // Limit max_size_in_bits so aligning up to a word never overflows.
    static idx_t max_size_in_words() { return word_index(~idx_t(0)); }
    static idx_t max_size_in_bits() { return max_size_in_words() * BitsPerWord; }
  
+   // bit must be the begin/end of a validated range.
+   static inline idx_t range_begin_align_up(idx_t bit);
+   static inline idx_t range_end_align_down(idx_t bit);
+ 
    // Helper for get_next_{zero,one}_bit variants.
    // - flip designates whether searching for 1s or 0s.  Must be one of
    //   find_{zeros,ones}_flip.
    // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
    template<bm_word_t flip, bool aligned_right>
*** 77,86 ****
--- 83,95 ----
  
    // Threshold for performing small range operation, even when large range
    // operation was requested. Measured in words.
    static const size_t small_range_words = 32;
  
+   // beg/end_aligned must be from range_begin/end aligners.
+   static bool is_small_aligned_range(idx_t beg_aligned, idx_t end_aligned);
+ 
   protected:
    // Return the position of bit within the word that contains it (e.g., if
    // bitmap words are 32 bits, return a number 0 <= n <= 31).
    static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
  
*** 122,139 ****
    void      set_large_range_of_words   (idx_t beg, idx_t end);
    void      clear_large_range_of_words (idx_t beg, idx_t end);
  
    static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
  
-   static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word);
- 
-   // The index of the first full word in a range.
-   idx_t word_index_round_up(idx_t bit) const;
- 
    // Verification.
!   static void verify_max_size_limited(idx_t bit) NOT_DEBUG_RETURN;
    void verify_index(idx_t index) const NOT_DEBUG_RETURN;
    void verify_range(idx_t beg_index, idx_t end_index) const NOT_DEBUG_RETURN;
  
    // Statistics.
    static const idx_t* _pop_count_table;
    static void init_pop_count_table();
--- 131,147 ----
    void      set_large_range_of_words   (idx_t beg, idx_t end);
    void      clear_large_range_of_words (idx_t beg, idx_t end);
  
    static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
  
    // Verification.
! 
!   // Verify size_in_bits does not exceed maximum size.
!   static void verify_valid_size(idx_t size_in_bits) NOT_DEBUG_RETURN;
!   // Verify index is less than size.
    void verify_index(idx_t index) const NOT_DEBUG_RETURN;
+   // Verify [beg,end) is a valid range.
    void verify_range(idx_t beg_index, idx_t end_index) const NOT_DEBUG_RETURN;
  
    // Statistics.
    static const idx_t* _pop_count_table;
    static void init_pop_count_table();
*** 189,199 ****
   public:
    // Pretouch the entire range of memory this BitMap covers.
    void pretouch();
  
    static idx_t calc_size_in_words(idx_t size_in_bits) {
!     verify_max_size_limited(size_in_bits);
      return word_index(size_in_bits + (BitsPerWord - 1));
    }
  
    idx_t size() const          { return _size; }
    idx_t size_in_words() const { return calc_size_in_words(size()); }
--- 197,207 ----
   public:
    // Pretouch the entire range of memory this BitMap covers.
    void pretouch();
  
    static idx_t calc_size_in_words(idx_t size_in_bits) {
!     verify_valid_size(size_in_bits);
      return word_index(size_in_bits + (BitsPerWord - 1));
    }
  
    idx_t size() const          { return _size; }
    idx_t size_in_words() const { return calc_size_in_words(size()); }