annotate src/share/vm/utilities/bitMap.inline.hpp @ 0:a61af66fc99e

Initial load
author duke
date Sat, 01 Dec 2007 00:00:00 +0000
parents
children 37f87013dfd8
rev   line source
duke@0 1 /*
duke@0 2 * Copyright 2005-2006 Sun Microsystems, Inc. All Rights Reserved.
duke@0 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@0 4 *
duke@0 5 * This code is free software; you can redistribute it and/or modify it
duke@0 6 * under the terms of the GNU General Public License version 2 only, as
duke@0 7 * published by the Free Software Foundation.
duke@0 8 *
duke@0 9 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@0 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@0 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@0 12 * version 2 for more details (a copy is included in the LICENSE file that
duke@0 13 * accompanied this code).
duke@0 14 *
duke@0 15 * You should have received a copy of the GNU General Public License version
duke@0 16 * 2 along with this work; if not, write to the Free Software Foundation,
duke@0 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@0 18 *
duke@0 19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
duke@0 20 * CA 95054 USA or visit www.sun.com if you need additional information or
duke@0 21 * have any questions.
duke@0 22 *
duke@0 23 */
duke@0 24
duke@0 25 inline bool BitMap::par_set_bit(idx_t bit) {
duke@0 26 verify_index(bit);
duke@0 27 volatile idx_t* const addr = word_addr(bit);
duke@0 28 const idx_t mask = bit_mask(bit);
duke@0 29 idx_t old_val = *addr;
duke@0 30
duke@0 31 do {
duke@0 32 const idx_t new_val = old_val | mask;
duke@0 33 if (new_val == old_val) {
duke@0 34 return false; // Someone else beat us to it.
duke@0 35 }
duke@0 36 const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
duke@0 37 (volatile void*) addr,
duke@0 38 (void*) old_val);
duke@0 39 if (cur_val == old_val) {
duke@0 40 return true; // Success.
duke@0 41 }
duke@0 42 old_val = cur_val; // The value changed, try again.
duke@0 43 } while (true);
duke@0 44 }
duke@0 45
duke@0 46 inline bool BitMap::par_clear_bit(idx_t bit) {
duke@0 47 verify_index(bit);
duke@0 48 volatile idx_t* const addr = word_addr(bit);
duke@0 49 const idx_t mask = ~bit_mask(bit);
duke@0 50 idx_t old_val = *addr;
duke@0 51
duke@0 52 do {
duke@0 53 const idx_t new_val = old_val & mask;
duke@0 54 if (new_val == old_val) {
duke@0 55 return false; // Someone else beat us to it.
duke@0 56 }
duke@0 57 const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
duke@0 58 (volatile void*) addr,
duke@0 59 (void*) old_val);
duke@0 60 if (cur_val == old_val) {
duke@0 61 return true; // Success.
duke@0 62 }
duke@0 63 old_val = cur_val; // The value changed, try again.
duke@0 64 } while (true);
duke@0 65 }
duke@0 66
duke@0 67 inline BitMap::idx_t
duke@0 68 BitMap::find_next_one_bit(idx_t beg_bit, idx_t end_bit) const
duke@0 69 {
duke@0 70 verify_range(beg_bit, end_bit);
duke@0 71 assert(bit_in_word(end_bit) == 0, "end_bit not word-aligned");
duke@0 72
duke@0 73 if (beg_bit == end_bit) {
duke@0 74 return beg_bit;
duke@0 75 }
duke@0 76
duke@0 77 idx_t index = word_index(beg_bit);
duke@0 78 idx_t r_index = word_index(end_bit);
duke@0 79 idx_t res_bit = beg_bit;
duke@0 80
duke@0 81 // check bits including and to the _left_ of offset's position
duke@0 82 idx_t res = map(index) >> bit_in_word(res_bit);
duke@0 83 if (res != (uintptr_t) NoBits) {
duke@0 84 // find the position of the 1-bit
duke@0 85 for (; !(res & 1); res_bit++) {
duke@0 86 res = res >> 1;
duke@0 87 }
duke@0 88 assert(res_bit >= beg_bit && res_bit < end_bit, "just checking");
duke@0 89 return res_bit;
duke@0 90 }
duke@0 91 // skip over all word length 0-bit runs
duke@0 92 for (index++; index < r_index; index++) {
duke@0 93 res = map(index);
duke@0 94 if (res != (uintptr_t) NoBits) {
duke@0 95 // found a 1, return the offset
duke@0 96 for (res_bit = bit_index(index); !(res & 1); res_bit++) {
duke@0 97 res = res >> 1;
duke@0 98 }
duke@0 99 assert(res & 1, "tautology; see loop condition");
duke@0 100 assert(res_bit >= beg_bit && res_bit < end_bit, "just checking");
duke@0 101 return res_bit;
duke@0 102 }
duke@0 103 }
duke@0 104 return end_bit;
duke@0 105 }