161 BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const {
162 assert(l_offset <= size(), "BitMap index out of bounds");
163 assert(r_offset <= size(), "BitMap index out of bounds");
164 assert(l_offset <= r_offset, "l_offset > r_offset ?");
165
166 if (l_offset == r_offset) {
167 return l_offset;
168 }
169 idx_t index = word_index(l_offset);
170 idx_t r_index = word_index(r_offset-1) + 1;
171 idx_t res_offset = l_offset;
172
173 // check bits including and to the _left_ of offset's position
174 idx_t pos = bit_in_word(res_offset);
175 idx_t res = map(index) >> pos;
176 if (res != (uintptr_t)NoBits) {
177 // find the position of the 1-bit
178 for (; !(res & 1); res_offset++) {
179 res = res >> 1;
180 }
181 assert(res_offset >= l_offset &&
182 res_offset < r_offset, "just checking");
183 return MIN2(res_offset, r_offset);
184 }
185 // skip over all word length 0-bit runs
186 for (index++; index < r_index; index++) {
187 res = map(index);
188 if (res != (uintptr_t)NoBits) {
189 // found a 1, return the offset
190 for (res_offset = bit_index(index); !(res & 1); res_offset++) {
191 res = res >> 1;
192 }
193 assert(res & 1, "tautology; see loop condition");
194 assert(res_offset >= l_offset, "just checking");
195 return MIN2(res_offset, r_offset);
196 }
197 }
198 return r_offset;
199 }
200
201 inline BitMap::idx_t
202 BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const {
|
161 BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const {
162 assert(l_offset <= size(), "BitMap index out of bounds");
163 assert(r_offset <= size(), "BitMap index out of bounds");
164 assert(l_offset <= r_offset, "l_offset > r_offset ?");
165
166 if (l_offset == r_offset) {
167 return l_offset;
168 }
169 idx_t index = word_index(l_offset);
170 idx_t r_index = word_index(r_offset-1) + 1;
171 idx_t res_offset = l_offset;
172
173 // check bits including and to the _left_ of offset's position
174 idx_t pos = bit_in_word(res_offset);
175 idx_t res = map(index) >> pos;
176 if (res != (uintptr_t)NoBits) {
177 // find the position of the 1-bit
178 for (; !(res & 1); res_offset++) {
179 res = res >> 1;
180 }
181
182 // In the following assert, checking that res_offset is strictly
183 // less than r_offset is too strong. Consider the case where
184 // l_offset is bit 15 and r_offset is bit 17 of the same map word,
185 // and where bits [18:17:16:15] == [01:00:00:00]. The calculation
186 // above would yield the offset of bit 18. All we can assert is that
187 // res_offset is strictly less than size() since we know that there
188 // are set bits at offsets above, but in the same map word as, r_offset
189 // The bits in the range (r_offset:l_offset] are all 0.
190 assert(res_offset >= l_offset && res_offset < size(), "just checking");
191 return MIN2(res_offset, r_offset);
192 }
193 // skip over all word length 0-bit runs
194 for (index++; index < r_index; index++) {
195 res = map(index);
196 if (res != (uintptr_t)NoBits) {
197 // found a 1, return the offset
198 for (res_offset = bit_index(index); !(res & 1); res_offset++) {
199 res = res >> 1;
200 }
201 assert(res & 1, "tautology; see loop condition");
202 assert(res_offset >= l_offset, "just checking");
203 return MIN2(res_offset, r_offset);
204 }
205 }
206 return r_offset;
207 }
208
209 inline BitMap::idx_t
210 BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const {
|