bitMap.inline.hpp revision 0:a61af66fc99e 
1/*
2 * Copyright 2005-2006 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
24
25inline bool BitMap::par_set_bit(idx_t bit) {
26  verify_index(bit);
27  volatile idx_t* const addr = word_addr(bit);
28  const idx_t mask = bit_mask(bit);
29  idx_t old_val = *addr;
30
31  do {
32    const idx_t new_val = old_val | mask;
33    if (new_val == old_val) {
34      return false;     // Someone else beat us to it.
35    }
36    const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
37                                                      (volatile void*) addr,
38                                                      (void*) old_val);
39    if (cur_val == old_val) {
40      return true;      // Success.
41    }
42    old_val = cur_val;  // The value changed, try again.
43  } while (true);
44}
45
46inline bool BitMap::par_clear_bit(idx_t bit) {
47  verify_index(bit);
48  volatile idx_t* const addr = word_addr(bit);
49  const idx_t mask = ~bit_mask(bit);
50  idx_t old_val = *addr;
51
52  do {
53    const idx_t new_val = old_val & mask;
54    if (new_val == old_val) {
55      return false;     // Someone else beat us to it.
56    }
57    const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
58                                                      (volatile void*) addr,
59                                                      (void*) old_val);
60    if (cur_val == old_val) {
61      return true;      // Success.
62    }
63    old_val = cur_val;  // The value changed, try again.
64  } while (true);
65}
66
67inline BitMap::idx_t
68BitMap::find_next_one_bit(idx_t beg_bit, idx_t end_bit) const
69{
70  verify_range(beg_bit, end_bit);
71  assert(bit_in_word(end_bit) == 0, "end_bit not word-aligned");
72
73  if (beg_bit == end_bit) {
74    return beg_bit;
75  }
76
77  idx_t   index = word_index(beg_bit);
78  idx_t r_index = word_index(end_bit);
79  idx_t res_bit = beg_bit;
80
81  // check bits including and to the _left_ of offset's position
82  idx_t res = map(index) >> bit_in_word(res_bit);
83  if (res != (uintptr_t) NoBits) {
84    // find the position of the 1-bit
85    for (; !(res & 1); res_bit++) {
86      res = res >> 1;
87    }
88    assert(res_bit >= beg_bit && res_bit < end_bit, "just checking");
89    return res_bit;
90  }
91  // skip over all word length 0-bit runs
92  for (index++; index < r_index; index++) {
93    res = map(index);
94    if (res != (uintptr_t) NoBits) {
95      // found a 1, return the offset
96      for (res_bit = bit_index(index); !(res & 1); res_bit++) {
97        res = res >> 1;
98      }
99      assert(res & 1, "tautology; see loop condition");
100      assert(res_bit >= beg_bit && res_bit < end_bit, "just checking");
101      return res_bit;
102    }
103  }
104  return end_bit;
105}
106