| /* |
| * Copyright 2005-2006 Sun Microsystems, Inc. All Rights Reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| * CA 95054 USA or visit www.sun.com if you need additional information or |
| * have any questions. |
| * |
| */ |
| |
| inline bool BitMap::par_set_bit(idx_t bit) { |
| verify_index(bit); |
| volatile idx_t* const addr = word_addr(bit); |
| const idx_t mask = bit_mask(bit); |
| idx_t old_val = *addr; |
| |
| do { |
| const idx_t new_val = old_val | mask; |
| if (new_val == old_val) { |
| return false; // Someone else beat us to it. |
| } |
| const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val, |
| (volatile void*) addr, |
| (void*) old_val); |
| if (cur_val == old_val) { |
| return true; // Success. |
| } |
| old_val = cur_val; // The value changed, try again. |
| } while (true); |
| } |
| |
| inline bool BitMap::par_clear_bit(idx_t bit) { |
| verify_index(bit); |
| volatile idx_t* const addr = word_addr(bit); |
| const idx_t mask = ~bit_mask(bit); |
| idx_t old_val = *addr; |
| |
| do { |
| const idx_t new_val = old_val & mask; |
| if (new_val == old_val) { |
| return false; // Someone else beat us to it. |
| } |
| const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val, |
| (volatile void*) addr, |
| (void*) old_val); |
| if (cur_val == old_val) { |
| return true; // Success. |
| } |
| old_val = cur_val; // The value changed, try again. |
| } while (true); |
| } |
| |
| inline BitMap::idx_t |
| BitMap::find_next_one_bit(idx_t beg_bit, idx_t end_bit) const |
| { |
| verify_range(beg_bit, end_bit); |
| assert(bit_in_word(end_bit) == 0, "end_bit not word-aligned"); |
| |
| if (beg_bit == end_bit) { |
| return beg_bit; |
| } |
| |
| idx_t index = word_index(beg_bit); |
| idx_t r_index = word_index(end_bit); |
| idx_t res_bit = beg_bit; |
| |
| // check bits including and to the _left_ of offset's position |
| idx_t res = map(index) >> bit_in_word(res_bit); |
| if (res != (uintptr_t) NoBits) { |
| // find the position of the 1-bit |
| for (; !(res & 1); res_bit++) { |
| res = res >> 1; |
| } |
| assert(res_bit >= beg_bit && res_bit < end_bit, "just checking"); |
| return res_bit; |
| } |
| // skip over all word length 0-bit runs |
| for (index++; index < r_index; index++) { |
| res = map(index); |
| if (res != (uintptr_t) NoBits) { |
| // found a 1, return the offset |
| for (res_bit = bit_index(index); !(res & 1); res_bit++) { |
| res = res >> 1; |
| } |
| assert(res & 1, "tautology; see loop condition"); |
| assert(res_bit >= beg_bit && res_bit < end_bit, "just checking"); |
| return res_bit; |
| } |
| } |
| return end_bit; |
| } |