178 _size = size;
179 }
180
181 // Protected constructor and destructor.
182 BitMap(bm_word_t* map, idx_t size_in_bits) : _map(map), _size(size_in_bits) {}
183 ~BitMap() {}
184
185 public:
186 // Pretouch the entire range of memory this BitMap covers.
187 void pretouch();
188
189 // Accessing
190 static idx_t calc_size_in_words(size_t size_in_bits) {
191 return word_index(size_in_bits + BitsPerWord - 1);
192 }
193
194 static idx_t calc_size_in_bytes(size_t size_in_bits) {
195 return calc_size_in_words(size_in_bits) * BytesPerWord;
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 calc_size_in_bytes(size()); }
201
202 bool at(idx_t index) const {
203 verify_index(index);
204 return (*word_addr(index) & bit_mask(index)) != 0;
205 }
206
207 // Align bit index up or down to the next bitmap word boundary, or check
208 // alignment.
209 static idx_t word_align_up(idx_t bit) {
210 return align_up(bit, BitsPerWord);
211 }
212 static idx_t word_align_down(idx_t bit) {
213 return align_down(bit, BitsPerWord);
214 }
215 static bool is_word_aligned(idx_t bit) {
216 return word_align_up(bit) == bit;
217 }
236 void clear_range (idx_t beg, idx_t end);
237 void set_large_range (idx_t beg, idx_t end);
238 void clear_large_range (idx_t beg, idx_t end);
239 void at_put_range(idx_t beg, idx_t end, bool value);
240 void par_at_put_range(idx_t beg, idx_t end, bool value);
241 void at_put_large_range(idx_t beg, idx_t end, bool value);
242 void par_at_put_large_range(idx_t beg, idx_t end, bool value);
243
244 // Update a range of bits, using a hint about the size. Currently only
245 // inlines the predominant case of a 1-bit range. Works best when hint is a
246 // compile-time constant.
247 void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
248 void clear_range(idx_t beg, idx_t end, RangeSizeHint hint);
249 void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint);
250 void par_clear_range (idx_t beg, idx_t end, RangeSizeHint hint);
251
252 // Clearing
253 void clear_large();
254 inline void clear();
255
256 // Iteration support. Returns "true" if the iteration completed, false
257 // if the iteration terminated early (because the closure "blk" returned
258 // false).
259 bool iterate(BitMapClosure* blk, idx_t leftIndex, idx_t rightIndex);
260 bool iterate(BitMapClosure* blk) {
261 // call the version that takes an interval
262 return iterate(blk, 0, size());
263 }
264
265 // Looking for 1's and 0's at indices equal to or greater than "l_index",
266 // stopping if none has been found before "r_index", and returning
267 // "r_index" (which must be at most "size") in that case.
268 idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const;
269 idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const;
270
271 idx_t get_next_one_offset(idx_t offset) const {
272 return get_next_one_offset(offset, size());
273 }
274 idx_t get_next_zero_offset(idx_t offset) const {
275 return get_next_zero_offset(offset, size());
276 }
277
278 // Like "get_next_one_offset", except requires that "r_index" is
279 // aligned to bitsizeof(bm_word_t).
280 idx_t get_next_one_offset_aligned_right(idx_t l_index, idx_t r_index) const;
281
282 // Returns the number of bits set in the bitmap.
283 idx_t count_one_bits() const;
284
285 // Set operations.
286 void set_union(const BitMap& bits);
287 void set_difference(const BitMap& bits);
288 void set_intersection(const BitMap& bits);
289 // Returns true iff "this" is a superset of "bits".
290 bool contains(const BitMap& bits) const;
291 // Returns true iff "this and "bits" have a non-empty intersection.
292 bool intersects(const BitMap& bits) const;
293
294 // Returns result of whether this map changed
295 // during the operation
296 bool set_union_with_result(const BitMap& bits);
297 bool set_difference_with_result(const BitMap& bits);
298 bool set_intersection_with_result(const BitMap& bits);
299
300 void set_from(const BitMap& bits);
|
178 _size = size;
179 }
180
181 // Protected constructor and destructor.
182 BitMap(bm_word_t* map, idx_t size_in_bits) : _map(map), _size(size_in_bits) {}
183 ~BitMap() {}
184
185 public:
186 // Pretouch the entire range of memory this BitMap covers.
187 void pretouch();
188
189 // Accessing
190 static idx_t calc_size_in_words(size_t size_in_bits) {
191 return word_index(size_in_bits + BitsPerWord - 1);
192 }
193
194 static idx_t calc_size_in_bytes(size_t size_in_bits) {
195 return calc_size_in_words(size_in_bits) * BytesPerWord;
196 }
197
198 // Size, in number of bits, of this map.
199 idx_t size() const { return _size; }
200 idx_t size_in_words() const { return calc_size_in_words(size()); }
201 idx_t size_in_bytes() const { return calc_size_in_bytes(size()); }
202
203 bool at(idx_t index) const {
204 verify_index(index);
205 return (*word_addr(index) & bit_mask(index)) != 0;
206 }
207
208 // Align bit index up or down to the next bitmap word boundary, or check
209 // alignment.
210 static idx_t word_align_up(idx_t bit) {
211 return align_up(bit, BitsPerWord);
212 }
213 static idx_t word_align_down(idx_t bit) {
214 return align_down(bit, BitsPerWord);
215 }
216 static bool is_word_aligned(idx_t bit) {
217 return word_align_up(bit) == bit;
218 }
237 void clear_range (idx_t beg, idx_t end);
238 void set_large_range (idx_t beg, idx_t end);
239 void clear_large_range (idx_t beg, idx_t end);
240 void at_put_range(idx_t beg, idx_t end, bool value);
241 void par_at_put_range(idx_t beg, idx_t end, bool value);
242 void at_put_large_range(idx_t beg, idx_t end, bool value);
243 void par_at_put_large_range(idx_t beg, idx_t end, bool value);
244
245 // Update a range of bits, using a hint about the size. Currently only
246 // inlines the predominant case of a 1-bit range. Works best when hint is a
247 // compile-time constant.
248 void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
249 void clear_range(idx_t beg, idx_t end, RangeSizeHint hint);
250 void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint);
251 void par_clear_range (idx_t beg, idx_t end, RangeSizeHint hint);
252
253 // Clearing
254 void clear_large();
255 inline void clear();
256
257 // Iteration support [leftIndex, rightIndex). Returns "true" if the iteration completed, false
258 // if the iteration terminated early (because the closure "blk" returned
259 // false).
260 bool iterate(BitMapClosure* blk, idx_t leftIndex, idx_t rightIndex) const;
261 bool iterate(BitMapClosure* blk) const {
262 // call the version that takes an interval
263 return iterate(blk, 0, size());
264 }
265
266 // Looking for 1's and 0's at indices equal to or greater than "l_index",
267 // stopping if none has been found before "r_index", and returning
268 // "r_index" (which must be at most "size") in that case.
269 idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const;
270 idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const;
271
272 idx_t get_next_one_offset(idx_t offset) const {
273 return get_next_one_offset(offset, size());
274 }
275 idx_t get_next_zero_offset(idx_t offset) const {
276 return get_next_zero_offset(offset, size());
277 }
278
279 // Like "get_next_one_offset", except requires that "r_index" is
280 // aligned to bitsizeof(bm_word_t).
281 idx_t get_next_one_offset_aligned_right(idx_t l_index, idx_t r_index) const;
282
283 // Returns the number of bits set between [l_index, r_index) in the bitmap.
284 idx_t count_one_bits(idx_t l_index, idx_t r_index) const;
285
286 // Returns the number of bits set in the bitmap.
287 idx_t count_one_bits() const;
288
289 // Set operations.
290 void set_union(const BitMap& bits);
291 void set_difference(const BitMap& bits);
292 void set_intersection(const BitMap& bits);
293 // Returns true iff "this" is a superset of "bits".
294 bool contains(const BitMap& bits) const;
295 // Returns true iff "this and "bits" have a non-empty intersection.
296 bool intersects(const BitMap& bits) const;
297
298 // Returns result of whether this map changed
299 // during the operation
300 bool set_union_with_result(const BitMap& bits);
301 bool set_difference_with_result(const BitMap& bits);
302 bool set_intersection_with_result(const BitMap& bits);
303
304 void set_from(const BitMap& bits);
|