< prev index next >

src/hotspot/share/utilities/bitMap.hpp

Print this page
rev 52445 : 8211926: Catastrophic size_t underflow in BitMap::*_large methods
Reviewed-by: kbarrett


  55   // Hints for range sizes.
  56   typedef enum {
  57     unknown_range, small_range, large_range
  58   } RangeSizeHint;
  59 
  60  private:
  61   bm_word_t* _map;     // First word in bitmap
  62   idx_t      _size;    // Size of bitmap (in bits)
  63 
  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 




  75  protected:
  76   // Return the position of bit within the word that contains it (e.g., if
  77   // bitmap words are 32 bits, return a number 0 <= n <= 31).
  78   static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
  79 
  80   // Return a mask that will select the specified bit, when applied to the word
  81   // containing the bit.
  82   static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
  83 
  84   // Return the index of the word containing the specified bit.
  85   static idx_t word_index(idx_t bit)  { return bit >> LogBitsPerWord; }
  86 
  87   // Return the bit number of the first bit in the specified word.
  88   static idx_t bit_index(idx_t word)  { return word << LogBitsPerWord; }
  89 
  90   // Return the array of bitmap words, or a specific word from it.
  91   bm_word_t* map()                 { return _map; }
  92   const bm_word_t* map() const     { return _map; }
  93   bm_word_t  map(idx_t word) const { return _map[word]; }
  94 


  99   // Set a word to a specified value or to all ones; clear a word.
 100   void set_word  (idx_t word, bm_word_t val) { _map[word] = val; }
 101   void set_word  (idx_t word)            { set_word(word, ~(bm_word_t)0); }
 102   void clear_word(idx_t word)            { _map[word] = 0; }
 103 
 104   // Utilities for ranges of bits.  Ranges are half-open [beg, end).
 105 
 106   // Ranges within a single word.
 107   bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
 108   void  set_range_within_word      (idx_t beg, idx_t end);
 109   void  clear_range_within_word    (idx_t beg, idx_t end);
 110   void  par_put_range_within_word  (idx_t beg, idx_t end, bool value);
 111 
 112   // Ranges spanning entire words.
 113   void      set_range_of_words         (idx_t beg, idx_t end);
 114   void      clear_range_of_words       (idx_t beg, idx_t end);
 115   void      set_large_range_of_words   (idx_t beg, idx_t end);
 116   void      clear_large_range_of_words (idx_t beg, idx_t end);
 117 
 118   static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);


 119 
 120   // The index of the first full word in a range.
 121   idx_t word_index_round_up(idx_t bit) const;
 122 
 123   // Verification.
 124   void verify_index(idx_t index) const NOT_DEBUG_RETURN;
 125   void verify_range(idx_t beg_index, idx_t end_index) const NOT_DEBUG_RETURN;
 126 
 127   // Statistics.
 128   static const idx_t* _pop_count_table;
 129   static void init_pop_count_table();
 130   static idx_t num_set_bits(bm_word_t w);
 131   static idx_t num_set_bits_from_table(unsigned char c);
 132 
 133   // Allocation Helpers.
 134 
 135   // Allocates and clears the bitmap memory.
 136   template <class Allocator>
 137   static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true);
 138 




  55   // Hints for range sizes.
  56   typedef enum {
  57     unknown_range, small_range, large_range
  58   } RangeSizeHint;
  59 
  60  private:
  61   bm_word_t* _map;     // First word in bitmap
  62   idx_t      _size;    // Size of bitmap (in bits)
  63 
  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 
  75   // Threshold for performing small range operation, even when large range
  76   // operation was requested. Measured in words.
  77   static const size_t small_range_words = 32;
  78 
  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.
  86   static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
  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.
  95   bm_word_t* map()                 { return _map; }
  96   const bm_word_t* map() const     { return _map; }
  97   bm_word_t  map(idx_t word) const { return _map[word]; }
  98 


 103   // Set a word to a specified value or to all ones; clear a word.
 104   void set_word  (idx_t word, bm_word_t val) { _map[word] = val; }
 105   void set_word  (idx_t word)            { set_word(word, ~(bm_word_t)0); }
 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.
 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);
 115 
 116   // Ranges spanning entire words.
 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);
 121 
 122   static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
 123 
 124   static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word);
 125 
 126   // The index of the first full word in a range.
 127   idx_t word_index_round_up(idx_t bit) const;
 128 
 129   // Verification.
 130   void verify_index(idx_t index) const NOT_DEBUG_RETURN;
 131   void verify_range(idx_t beg_index, idx_t end_index) const NOT_DEBUG_RETURN;
 132 
 133   // Statistics.
 134   static const idx_t* _pop_count_table;
 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);
 138 
 139   // Allocation Helpers.
 140 
 141   // Allocates and clears the bitmap memory.
 142   template <class Allocator>
 143   static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true);
 144 


< prev index next >