1 /*
2 * Copyright (c) 2005, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
205 return MIN2(res_offset, r_offset);
206 }
207 }
208 return r_offset;
209 }
210
211 inline BitMap::idx_t
212 BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const {
213 assert(l_offset <= size(), "BitMap index out of bounds");
214 assert(r_offset <= size(), "BitMap index out of bounds");
215 assert(l_offset <= r_offset, "l_offset > r_offset ?");
216
217 if (l_offset == r_offset) {
218 return l_offset;
219 }
220 idx_t index = word_index(l_offset);
221 idx_t r_index = word_index(r_offset-1) + 1;
222 idx_t res_offset = l_offset;
223
224 // check bits including and to the _left_ of offset's position
225 idx_t pos = res_offset & (BitsPerWord - 1);
226 bm_word_t res = (map(index) >> pos) | left_n_bits((int)pos);
227
228 if (res != ~(bm_word_t)0) {
229 // find the position of the 0-bit
230 for (; res & 1; res_offset++) {
231 res = res >> 1;
232 }
233 assert(res_offset >= l_offset, "just checking");
234 return MIN2(res_offset, r_offset);
235 }
236 // skip over all word length 1-bit runs
237 for (index++; index < r_index; index++) {
238 res = map(index);
239 if (res != ~(bm_word_t)0) {
240 // found a 0, return the offset
241 for (res_offset = index << LogBitsPerWord; res & 1;
242 res_offset++) {
243 res = res >> 1;
244 }
245 assert(!(res & 1), "tautology; see loop condition");
246 assert(res_offset >= l_offset, "just checking");
247 return MIN2(res_offset, r_offset);
248 }
249 }
250 return r_offset;
251 }
|
1 /*
2 * Copyright (c) 2005, 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
205 return MIN2(res_offset, r_offset);
206 }
207 }
208 return r_offset;
209 }
210
211 inline BitMap::idx_t
212 BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const {
213 assert(l_offset <= size(), "BitMap index out of bounds");
214 assert(r_offset <= size(), "BitMap index out of bounds");
215 assert(l_offset <= r_offset, "l_offset > r_offset ?");
216
217 if (l_offset == r_offset) {
218 return l_offset;
219 }
220 idx_t index = word_index(l_offset);
221 idx_t r_index = word_index(r_offset-1) + 1;
222 idx_t res_offset = l_offset;
223
224 // check bits including and to the _left_ of offset's position
225 idx_t pos = bit_in_word(res_offset);
226 bm_word_t res = ~map(index) >> pos; // flip bits and shift for l_offset
227
228 if (res != 0) {
229 // find the position of the 1-bit
230 for (; (res & 1) == 0; ++res_offset) {
231 res >>= 1;
232 }
233 assert(res_offset >= l_offset, "just checking");
234 return MIN2(res_offset, r_offset);
235 }
236 // skip over all word length 1-bit runs
237 for (index++; index < r_index; index++) {
238 res = map(index);
239 if (res != ~(bm_word_t)0) {
240 // found a 0, return the offset
241 for (res_offset = index << LogBitsPerWord; res & 1;
242 res_offset++) {
243 res = res >> 1;
244 }
245 assert(!(res & 1), "tautology; see loop condition");
246 assert(res_offset >= l_offset, "just checking");
247 return MIN2(res_offset, r_offset);
248 }
249 }
250 return r_offset;
251 }
|