|
0
|
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
|
|
|
25 inline 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
|
|
|
46 inline 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
|
|
|
67 inline BitMap::idx_t
|
|
|
68 BitMap::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 }
|
