137
138 void BitMap::clear_range(idx_t beg, idx_t end) {
139 verify_range(beg, end);
140
141 idx_t beg_full_word = word_index_round_up(beg);
142 idx_t end_full_word = word_index(end);
143
144 if (beg_full_word < end_full_word) {
145 // The range includes at least one full word.
146 clear_range_within_word(beg, bit_index(beg_full_word));
147 clear_range_of_words(beg_full_word, end_full_word);
148 clear_range_within_word(bit_index(end_full_word), end);
149 } else {
150 // The range spans at most 2 partial words.
151 idx_t boundary = MIN2(bit_index(beg_full_word), end);
152 clear_range_within_word(beg, boundary);
153 clear_range_within_word(boundary, end);
154 }
155 }
156
157 void BitMap::set_large_range(idx_t beg, idx_t end) {
158 verify_range(beg, end);
159
160 idx_t beg_full_word = word_index_round_up(beg);
161 idx_t end_full_word = word_index(end);
162
163 assert(end_full_word - beg_full_word >= 32,
164 "the range must include at least 32 bytes");
165
166 // The range includes at least one full word.
167 set_range_within_word(beg, bit_index(beg_full_word));
168 set_large_range_of_words(beg_full_word, end_full_word);
169 set_range_within_word(bit_index(end_full_word), end);
170 }
171
172 void BitMap::clear_large_range(idx_t beg, idx_t end) {
173 verify_range(beg, end);
174
175 idx_t beg_full_word = word_index_round_up(beg);
176 idx_t end_full_word = word_index(end);
177
178 assert(end_full_word - beg_full_word >= 32,
179 "the range must include at least 32 bytes");
180
181 // The range includes at least one full word.
182 clear_range_within_word(beg, bit_index(beg_full_word));
183 clear_large_range_of_words(beg_full_word, end_full_word);
184 clear_range_within_word(bit_index(end_full_word), end);
185 }
186
187 void BitMap::at_put(idx_t offset, bool value) {
188 if (value) {
189 set_bit(offset);
190 } else {
191 clear_bit(offset);
192 }
193 }
194
195 // Return true to indicate that this thread changed
196 // the bit, false to indicate that someone else did.
197 // In either case, the requested bit is in the
198 // requested state some time during the period that
199 // this thread is executing this call. More importantly,
247 par_put_range_within_word(beg, boundary, value);
248 par_put_range_within_word(boundary, end, value);
249 }
250
251 }
252
253 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
254 if (value) {
255 set_large_range(beg, end);
256 } else {
257 clear_large_range(beg, end);
258 }
259 }
260
261 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
262 verify_range(beg, end);
263
264 idx_t beg_full_word = word_index_round_up(beg);
265 idx_t end_full_word = word_index(end);
266
267 assert(end_full_word - beg_full_word >= 32,
268 "the range must include at least 32 bytes");
269
270 // The range includes at least one full word.
271 par_put_range_within_word(beg, bit_index(beg_full_word), value);
272 if (value) {
273 set_large_range_of_words(beg_full_word, end_full_word);
274 } else {
275 clear_large_range_of_words(beg_full_word, end_full_word);
276 }
277 par_put_range_within_word(bit_index(end_full_word), end, value);
278 }
279
280 bool BitMap::contains(const BitMap other) const {
281 assert(size() == other.size(), "must have same size");
282 bm_word_t* dest_map = map();
283 bm_word_t* other_map = other.map();
284 idx_t size = size_in_words();
285 for (idx_t index = 0; index < size_in_words(); index++) {
286 bm_word_t word_union = dest_map[index] | other_map[index];
287 // If this has more bits set than dest_map[index], then other is not a
288 // subset.
|
137
138 void BitMap::clear_range(idx_t beg, idx_t end) {
139 verify_range(beg, end);
140
141 idx_t beg_full_word = word_index_round_up(beg);
142 idx_t end_full_word = word_index(end);
143
144 if (beg_full_word < end_full_word) {
145 // The range includes at least one full word.
146 clear_range_within_word(beg, bit_index(beg_full_word));
147 clear_range_of_words(beg_full_word, end_full_word);
148 clear_range_within_word(bit_index(end_full_word), end);
149 } else {
150 // The range spans at most 2 partial words.
151 idx_t boundary = MIN2(bit_index(beg_full_word), end);
152 clear_range_within_word(beg, boundary);
153 clear_range_within_word(boundary, end);
154 }
155 }
156
157 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
158 // There is little point to call large version on small ranges.
159 // Need to check carefully, keeping potential idx_t underflow in mind.
160 // The threshold should be at least one word.
161 STATIC_ASSERT(small_range_words >= 1);
162 return (beg_full_word + small_range_words >= end_full_word);
163 }
164
165 void BitMap::set_large_range(idx_t beg, idx_t end) {
166 verify_range(beg, end);
167
168 idx_t beg_full_word = word_index_round_up(beg);
169 idx_t end_full_word = word_index(end);
170
171 if (is_small_range_of_words(beg_full_word, end_full_word)) {
172 set_range(beg, end);
173 return;
174 }
175
176 // The range includes at least one full word.
177 set_range_within_word(beg, bit_index(beg_full_word));
178 set_large_range_of_words(beg_full_word, end_full_word);
179 set_range_within_word(bit_index(end_full_word), end);
180 }
181
182 void BitMap::clear_large_range(idx_t beg, idx_t end) {
183 verify_range(beg, end);
184
185 idx_t beg_full_word = word_index_round_up(beg);
186 idx_t end_full_word = word_index(end);
187
188 if (is_small_range_of_words(beg_full_word, end_full_word)) {
189 clear_range(beg, end);
190 return;
191 }
192
193 // The range includes at least one full word.
194 clear_range_within_word(beg, bit_index(beg_full_word));
195 clear_large_range_of_words(beg_full_word, end_full_word);
196 clear_range_within_word(bit_index(end_full_word), end);
197 }
198
199 void BitMap::at_put(idx_t offset, bool value) {
200 if (value) {
201 set_bit(offset);
202 } else {
203 clear_bit(offset);
204 }
205 }
206
207 // Return true to indicate that this thread changed
208 // the bit, false to indicate that someone else did.
209 // In either case, the requested bit is in the
210 // requested state some time during the period that
211 // this thread is executing this call. More importantly,
259 par_put_range_within_word(beg, boundary, value);
260 par_put_range_within_word(boundary, end, value);
261 }
262
263 }
264
265 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
266 if (value) {
267 set_large_range(beg, end);
268 } else {
269 clear_large_range(beg, end);
270 }
271 }
272
273 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
274 verify_range(beg, end);
275
276 idx_t beg_full_word = word_index_round_up(beg);
277 idx_t end_full_word = word_index(end);
278
279 if (is_small_range_of_words(beg_full_word, end_full_word)) {
280 par_at_put_range(beg, end, value);
281 return;
282 }
283
284 // The range includes at least one full word.
285 par_put_range_within_word(beg, bit_index(beg_full_word), value);
286 if (value) {
287 set_large_range_of_words(beg_full_word, end_full_word);
288 } else {
289 clear_large_range_of_words(beg_full_word, end_full_word);
290 }
291 par_put_range_within_word(bit_index(end_full_word), end, value);
292 }
293
294 bool BitMap::contains(const BitMap other) const {
295 assert(size() == other.size(), "must have same size");
296 bm_word_t* dest_map = map();
297 bm_word_t* other_map = other.map();
298 idx_t size = size_in_words();
299 for (idx_t index = 0; index < size_in_words(); index++) {
300 bm_word_t word_union = dest_map[index] | other_map[index];
301 // If this has more bits set than dest_map[index], then other is not a
302 // subset.
|