128 } |
128 } |
129 } |
129 } |
130 |
130 |
131 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) { |
131 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) { |
132 bm_word_t* map = _map; |
132 bm_word_t* map = _map; |
133 for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0; |
133 for (idx_t i = beg; i < end; ++i) map[i] = ~(bm_word_t)0; |
134 } |
134 } |
135 |
135 |
136 |
136 |
137 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) { |
137 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) { |
138 bm_word_t* map = _map; |
138 bm_word_t* map = _map; |
170 idx_t r_index = word_index(r_offset-1) + 1; |
170 idx_t r_index = word_index(r_offset-1) + 1; |
171 idx_t res_offset = l_offset; |
171 idx_t res_offset = l_offset; |
172 |
172 |
173 // check bits including and to the _left_ of offset's position |
173 // check bits including and to the _left_ of offset's position |
174 idx_t pos = bit_in_word(res_offset); |
174 idx_t pos = bit_in_word(res_offset); |
175 idx_t res = map(index) >> pos; |
175 bm_word_t res = map(index) >> pos; |
176 if (res != (uintptr_t)NoBits) { |
176 if (res != 0) { |
177 // find the position of the 1-bit |
177 // find the position of the 1-bit |
178 for (; !(res & 1); res_offset++) { |
178 for (; !(res & 1); res_offset++) { |
179 res = res >> 1; |
179 res = res >> 1; |
180 } |
180 } |
181 |
181 |
205 return MIN2(res_offset, r_offset); |
205 return MIN2(res_offset, r_offset); |
206 } |
206 } |
207 // skip over all word length 0-bit runs |
207 // skip over all word length 0-bit runs |
208 for (index++; index < r_index; index++) { |
208 for (index++; index < r_index; index++) { |
209 res = map(index); |
209 res = map(index); |
210 if (res != (uintptr_t)NoBits) { |
210 if (res != 0) { |
211 // found a 1, return the offset |
211 // found a 1, return the offset |
212 for (res_offset = bit_index(index); !(res & 1); res_offset++) { |
212 for (res_offset = bit_index(index); !(res & 1); res_offset++) { |
213 res = res >> 1; |
213 res = res >> 1; |
214 } |
214 } |
215 assert(res & 1, "tautology; see loop condition"); |
215 assert(res & 1, "tautology; see loop condition"); |
233 idx_t r_index = word_index(r_offset-1) + 1; |
233 idx_t r_index = word_index(r_offset-1) + 1; |
234 idx_t res_offset = l_offset; |
234 idx_t res_offset = l_offset; |
235 |
235 |
236 // check bits including and to the _left_ of offset's position |
236 // check bits including and to the _left_ of offset's position |
237 idx_t pos = res_offset & (BitsPerWord - 1); |
237 idx_t pos = res_offset & (BitsPerWord - 1); |
238 idx_t res = (map(index) >> pos) | left_n_bits((int)pos); |
238 bm_word_t res = (map(index) >> pos) | left_n_bits((int)pos); |
239 |
239 |
240 if (res != (uintptr_t)AllBits) { |
240 if (res != ~(bm_word_t)0) { |
241 // find the position of the 0-bit |
241 // find the position of the 0-bit |
242 for (; res & 1; res_offset++) { |
242 for (; res & 1; res_offset++) { |
243 res = res >> 1; |
243 res = res >> 1; |
244 } |
244 } |
245 assert(res_offset >= l_offset, "just checking"); |
245 assert(res_offset >= l_offset, "just checking"); |
246 return MIN2(res_offset, r_offset); |
246 return MIN2(res_offset, r_offset); |
247 } |
247 } |
248 // skip over all word length 1-bit runs |
248 // skip over all word length 1-bit runs |
249 for (index++; index < r_index; index++) { |
249 for (index++; index < r_index; index++) { |
250 res = map(index); |
250 res = map(index); |
251 if (res != (uintptr_t)AllBits) { |
251 if (res != ~(bm_word_t)0) { |
252 // found a 0, return the offset |
252 // found a 0, return the offset |
253 for (res_offset = index << LogBitsPerWord; res & 1; |
253 for (res_offset = index << LogBitsPerWord; res & 1; |
254 res_offset++) { |
254 res_offset++) { |
255 res = res >> 1; |
255 res = res >> 1; |
256 } |
256 } |
275 idx_t index = word_index(l_offset); |
275 idx_t index = word_index(l_offset); |
276 idx_t r_index = word_index(r_offset); |
276 idx_t r_index = word_index(r_offset); |
277 idx_t res_offset = l_offset; |
277 idx_t res_offset = l_offset; |
278 |
278 |
279 // check bits including and to the _left_ of offset's position |
279 // check bits including and to the _left_ of offset's position |
280 idx_t res = map(index) >> bit_in_word(res_offset); |
280 bm_word_t res = map(index) >> bit_in_word(res_offset); |
281 if (res != (uintptr_t)NoBits) { |
281 if (res != 0) { |
282 // find the position of the 1-bit |
282 // find the position of the 1-bit |
283 for (; !(res & 1); res_offset++) { |
283 for (; !(res & 1); res_offset++) { |
284 res = res >> 1; |
284 res = res >> 1; |
285 } |
285 } |
286 assert(res_offset >= l_offset && |
286 assert(res_offset >= l_offset && |
288 return res_offset; |
288 return res_offset; |
289 } |
289 } |
290 // skip over all word length 0-bit runs |
290 // skip over all word length 0-bit runs |
291 for (index++; index < r_index; index++) { |
291 for (index++; index < r_index; index++) { |
292 res = map(index); |
292 res = map(index); |
293 if (res != (uintptr_t)NoBits) { |
293 if (res != 0) { |
294 // found a 1, return the offset |
294 // found a 1, return the offset |
295 for (res_offset = bit_index(index); !(res & 1); res_offset++) { |
295 for (res_offset = bit_index(index); !(res & 1); res_offset++) { |
296 res = res >> 1; |
296 res = res >> 1; |
297 } |
297 } |
298 assert(res & 1, "tautology; see loop condition"); |
298 assert(res & 1, "tautology; see loop condition"); |
319 } |
319 } |
320 return mask; |
320 return mask; |
321 } |
321 } |
322 |
322 |
323 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) { |
323 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) { |
324 memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t)); |
324 memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(bm_word_t)); |
325 } |
325 } |
326 |
326 |
327 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) { |
327 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) { |
328 memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t)); |
328 memset(_map + beg, 0, (end - beg) * sizeof(bm_word_t)); |
329 } |
329 } |
330 |
330 |
331 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const { |
331 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const { |
332 idx_t bit_rounded_up = bit + (BitsPerWord - 1); |
332 idx_t bit_rounded_up = bit + (BitsPerWord - 1); |
333 // Check for integer arithmetic overflow. |
333 // Check for integer arithmetic overflow. |