31 class BitMapClosure;
32
33 // Operations for bitmaps represented as arrays of unsigned integers.
34 // Bit offsets are numbered from 0 to size-1.
35
36 // The "abstract" base BitMap class.
37 //
38 // The constructor and destructor are protected to prevent
39 // creation of BitMap instances outside of the BitMap class.
40 //
41 // The BitMap class doesn't use virtual calls on purpose,
42 // this ensures that we don't get a vtable unnecessarily.
43 //
44 // The allocation of the backing storage for the BitMap are handled by
45 // the subclasses. BitMap doesn't allocate or delete backing storage.
46 class BitMap {
47 friend class BitMap2D;
48
49 public:
50 typedef size_t idx_t; // Type used for bit and word indices.
51 typedef uintptr_t bm_word_t; // Element type of array that represents
52 // the bitmap. BitsPerWord bits per element.
53
54 // Hints for range sizes.
55 typedef enum {
56 unknown_range, small_range, large_range
57 } RangeSizeHint;
58
59 private:
60 bm_word_t* _map; // First word in bitmap
61 idx_t _size; // Size of bitmap (in bits)
62
63 // Limit max_size_in_bits so roundup in calc_size_in_words can't overflow.
64 static idx_t max_size_in_words() { return word_index(~idx_t(0)); }
65 static idx_t max_size_in_bits() { return max_size_in_words() * BitsPerWord; }
66
67 // Helper for get_next_{zero,one}_bit variants.
68 // - flip designates whether searching for 1s or 0s. Must be one of
69 // find_{zeros,ones}_flip.
70 // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
71 template<bm_word_t flip, bool aligned_right>
72 inline idx_t get_next_bit_impl(idx_t l_index, idx_t r_index) const;
73
74 // Values for get_next_bit_impl flip parameter.
75 static const bm_word_t find_ones_flip = 0;
76 static const bm_word_t find_zeros_flip = ~(bm_word_t)0;
77
78 // Threshold for performing small range operation, even when large range
79 // operation was requested. Measured in words.
80 static const size_t small_range_words = 32;
81
82 protected:
83 // Return the position of bit within the word that contains it (e.g., if
84 // bitmap words are 32 bits, return a number 0 <= n <= 31).
85 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
86
87 // Return a mask that will select the specified bit, when applied to the word
88 // containing the bit.
89 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
90
91 // Return the index of the word containing the specified bit.
92 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; }
93
94 // Return the bit number of the first bit in the specified word.
95 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
96
97 // Return the array of bitmap words, or a specific word from it.
98 bm_word_t* map() { return _map; }
99 const bm_word_t* map() const { return _map; }
100 bm_word_t map(idx_t word) const { return _map[word]; }
101
107 void set_word (idx_t word, bm_word_t val) { _map[word] = val; }
108 void set_word (idx_t word) { set_word(word, ~(bm_word_t)0); }
109 void clear_word(idx_t word) { _map[word] = 0; }
110
111 // Utilities for ranges of bits. Ranges are half-open [beg, end).
112
113 // Ranges within a single word.
114 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
115 void set_range_within_word (idx_t beg, idx_t end);
116 void clear_range_within_word (idx_t beg, idx_t end);
117 void par_put_range_within_word (idx_t beg, idx_t end, bool value);
118
119 // Ranges spanning entire words.
120 void set_range_of_words (idx_t beg, idx_t end);
121 void clear_range_of_words (idx_t beg, idx_t end);
122 void set_large_range_of_words (idx_t beg, idx_t end);
123 void clear_large_range_of_words (idx_t beg, idx_t end);
124
125 static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
126
127 static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word);
128
129 // The index of the first full word in a range.
130 idx_t word_index_round_up(idx_t bit) const;
131
132 // Verification.
133 static void verify_max_size_limited(idx_t bit) NOT_DEBUG_RETURN;
134 void verify_index(idx_t index) const NOT_DEBUG_RETURN;
135 void verify_range(idx_t beg_index, idx_t end_index) const NOT_DEBUG_RETURN;
136
137 // Statistics.
138 static const idx_t* _pop_count_table;
139 static void init_pop_count_table();
140 static idx_t num_set_bits(bm_word_t w);
141 static idx_t num_set_bits_from_table(unsigned char c);
142
143 // Allocation Helpers.
144
145 // Allocates and clears the bitmap memory.
146 template <class Allocator>
147 static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true);
148
149 // Reallocates and clears the new bitmap memory.
150 template <class Allocator>
151 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);
152
153 // Free the bitmap memory.
154 template <class Allocator>
174 //
175 // Can be called on previously initialized bitmaps.
176 template <class Allocator>
177 void reinitialize(const Allocator& allocator, idx_t new_size_in_bits, bool clear);
178
179 // Set the map and size.
180 void update(bm_word_t* map, idx_t size) {
181 _map = map;
182 _size = size;
183 }
184
185 // Protected constructor and destructor.
186 BitMap(bm_word_t* map, idx_t size_in_bits) : _map(map), _size(size_in_bits) {}
187 ~BitMap() {}
188
189 public:
190 // Pretouch the entire range of memory this BitMap covers.
191 void pretouch();
192
193 static idx_t calc_size_in_words(idx_t size_in_bits) {
194 verify_max_size_limited(size_in_bits);
195 return word_index(size_in_bits + (BitsPerWord - 1));
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 size_in_words() * BytesPerWord; }
201
202 bool at(idx_t index) const {
203 verify_index(index);
204 return (*word_addr(index) & bit_mask(index)) != 0;
205 }
206
207 // Set or clear the specified bit.
208 inline void set_bit(idx_t bit);
209 inline void clear_bit(idx_t bit);
210
211 // Atomically set or clear the specified bit.
212 inline bool par_set_bit(idx_t bit);
213 inline bool par_clear_bit(idx_t bit);
214
|
31 class BitMapClosure;
32
33 // Operations for bitmaps represented as arrays of unsigned integers.
34 // Bit offsets are numbered from 0 to size-1.
35
36 // The "abstract" base BitMap class.
37 //
38 // The constructor and destructor are protected to prevent
39 // creation of BitMap instances outside of the BitMap class.
40 //
41 // The BitMap class doesn't use virtual calls on purpose,
42 // this ensures that we don't get a vtable unnecessarily.
43 //
44 // The allocation of the backing storage for the BitMap are handled by
45 // the subclasses. BitMap doesn't allocate or delete backing storage.
46 class BitMap {
47 friend class BitMap2D;
48
49 public:
50 typedef size_t idx_t; // Type used for bit and word indices.
51 typedef uintptr_t bm_word_t; // Element type of array that represents the
52 // bitmap, with BitsPerWord bits per element.
53 // If this were to fail, there are lots of places that would need repair.
54 STATIC_ASSERT((sizeof(bm_word_t) * BitsPerByte) == BitsPerWord);
55
56 // Hints for range sizes.
57 typedef enum {
58 unknown_range, small_range, large_range
59 } RangeSizeHint;
60
61 private:
62 bm_word_t* _map; // First word in bitmap
63 idx_t _size; // Size of bitmap (in bits)
64
65 // Limit max_size_in_bits so aligning up to a word never overflows.
66 static idx_t max_size_in_words() { return word_index(~idx_t(0)); }
67 static idx_t max_size_in_bits() { return max_size_in_words() * BitsPerWord; }
68
69 // bit must be the begin/end of a validated range.
70 static inline idx_t range_begin_align_up(idx_t bit);
71 static inline idx_t range_end_align_down(idx_t bit);
72
73 // Helper for get_next_{zero,one}_bit variants.
74 // - flip designates whether searching for 1s or 0s. Must be one of
75 // find_{zeros,ones}_flip.
76 // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
77 template<bm_word_t flip, bool aligned_right>
78 inline idx_t get_next_bit_impl(idx_t l_index, idx_t r_index) const;
79
80 // Values for get_next_bit_impl flip parameter.
81 static const bm_word_t find_ones_flip = 0;
82 static const bm_word_t find_zeros_flip = ~(bm_word_t)0;
83
84 // Threshold for performing small range operation, even when large range
85 // operation was requested. Measured in words.
86 static const size_t small_range_words = 32;
87
88 // beg/end_aligned must be from range_begin/end aligners.
89 static bool is_small_aligned_range(idx_t beg_aligned, idx_t end_aligned);
90
91 protected:
92 // Return the position of bit within the word that contains it (e.g., if
93 // bitmap words are 32 bits, return a number 0 <= n <= 31).
94 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
95
96 // Return a mask that will select the specified bit, when applied to the word
97 // containing the bit.
98 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
99
100 // Return the index of the word containing the specified bit.
101 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; }
102
103 // Return the bit number of the first bit in the specified word.
104 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
105
106 // Return the array of bitmap words, or a specific word from it.
107 bm_word_t* map() { return _map; }
108 const bm_word_t* map() const { return _map; }
109 bm_word_t map(idx_t word) const { return _map[word]; }
110
116 void set_word (idx_t word, bm_word_t val) { _map[word] = val; }
117 void set_word (idx_t word) { set_word(word, ~(bm_word_t)0); }
118 void clear_word(idx_t word) { _map[word] = 0; }
119
120 // Utilities for ranges of bits. Ranges are half-open [beg, end).
121
122 // Ranges within a single word.
123 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
124 void set_range_within_word (idx_t beg, idx_t end);
125 void clear_range_within_word (idx_t beg, idx_t end);
126 void par_put_range_within_word (idx_t beg, idx_t end, bool value);
127
128 // Ranges spanning entire words.
129 void set_range_of_words (idx_t beg, idx_t end);
130 void clear_range_of_words (idx_t beg, idx_t end);
131 void set_large_range_of_words (idx_t beg, idx_t end);
132 void clear_large_range_of_words (idx_t beg, idx_t end);
133
134 static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
135
136 // Verification.
137
138 // Verify size_in_bits does not exceed maximum size.
139 static void verify_valid_size(idx_t size_in_bits) NOT_DEBUG_RETURN;
140 // Verify index is less than size.
141 void verify_index(idx_t index) const NOT_DEBUG_RETURN;
142 // Verify [beg,end) is a valid range.
143 void verify_range(idx_t beg_index, idx_t end_index) const NOT_DEBUG_RETURN;
144
145 // Statistics.
146 static const idx_t* _pop_count_table;
147 static void init_pop_count_table();
148 static idx_t num_set_bits(bm_word_t w);
149 static idx_t num_set_bits_from_table(unsigned char c);
150
151 // Allocation Helpers.
152
153 // Allocates and clears the bitmap memory.
154 template <class Allocator>
155 static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true);
156
157 // Reallocates and clears the new bitmap memory.
158 template <class Allocator>
159 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);
160
161 // Free the bitmap memory.
162 template <class Allocator>
182 //
183 // Can be called on previously initialized bitmaps.
184 template <class Allocator>
185 void reinitialize(const Allocator& allocator, idx_t new_size_in_bits, bool clear);
186
187 // Set the map and size.
188 void update(bm_word_t* map, idx_t size) {
189 _map = map;
190 _size = size;
191 }
192
193 // Protected constructor and destructor.
194 BitMap(bm_word_t* map, idx_t size_in_bits) : _map(map), _size(size_in_bits) {}
195 ~BitMap() {}
196
197 public:
198 // Pretouch the entire range of memory this BitMap covers.
199 void pretouch();
200
201 static idx_t calc_size_in_words(idx_t size_in_bits) {
202 verify_valid_size(size_in_bits);
203 return word_index(size_in_bits + (BitsPerWord - 1));
204 }
205
206 idx_t size() const { return _size; }
207 idx_t size_in_words() const { return calc_size_in_words(size()); }
208 idx_t size_in_bytes() const { return size_in_words() * BytesPerWord; }
209
210 bool at(idx_t index) const {
211 verify_index(index);
212 return (*word_addr(index) & bit_mask(index)) != 0;
213 }
214
215 // Set or clear the specified bit.
216 inline void set_bit(idx_t bit);
217 inline void clear_bit(idx_t bit);
218
219 // Atomically set or clear the specified bit.
220 inline bool par_set_bit(idx_t bit);
221 inline bool par_clear_bit(idx_t bit);
222
|