Mercurial > hg > truffle

comparison agent/src/share/classes/sun/jvm/hotspot/utilities/BitMap.java @ 0:a61af66fc99e jdk7-b24

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial load
author duke
date Sat, 01 Dec 2007 00:00:00 +0000
parents
children c18cbe5936b8
comparison
equal deleted inserted replaced
-1:000000000000 0:a61af66fc99e
1 /*
2 * Copyright 2001-2007 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 package sun.jvm.hotspot.utilities;
26
27 import sun.jvm.hotspot.debugger.*;
28
29 /** Manages a bitmap of the specified bit size */
30 public class BitMap {
31 public BitMap(int sizeInBits) {
32 this.size = sizeInBits;
33 int nofWords = sizeInWords();
34 data = new int[nofWords];
35 }
36
37 public int size() {
38 return size;
39 }
40
41 // Accessors
42 public boolean at(int offset) {
43 if (Assert.ASSERTS_ENABLED) {
44 Assert.that(offset>=0 && offset < size(), "BitMap index out of bounds");
45 }
46 return Bits.isSetNthBit(wordFor(offset), offset % bitsPerWord);
47 }
48
49 public void atPut(int offset, boolean value) {
50 int index = indexFor(offset);
51 int pos = offset % bitsPerWord;
52 if (value) {
53 data[index] = Bits.setNthBit(data[index], pos);
54 } else {
55 data[index] = Bits.clearNthBit(data[index], pos);
56 }
57 }
58
59 public void set_size(int value) {
60 size = value;
61 }
62
63 public void set_map(Address addr) {
64 for (int i=0; i<sizeInWords(); i++) {
65 data[i] = (int) addr.getCIntegerAt(0, bytesPerWord, true);
66 addr = addr.addOffsetTo(bytesPerWord);
67 }
68
69 }
70
71 public void clear() {
72 for (int i = 0; i < sizeInWords(); i++) {
73 data[i] = Bits.NoBits;
74 }
75 }
76
77 public void iterate(BitMapClosure blk) {
78 for (int index = 0; index < sizeInWords(); index++) {
79 int rest = data[index];
80 for (int offset = index * bitsPerWord; rest != Bits.NoBits; offset++) {
81 if (rest % 2 == 1) {
82 if (offset < size()) {
83 blk.doBit(offset);
84 } else {
85 return; // Passed end of map
86 }
87 }
88 rest = rest >>> 1;
89 }
90 }
91 }
92
93 /** Sets this bitmap to the logical union of it and the
94 argument. Both bitmaps must be the same size. Returns true if a
95 change was caused in this bitmap. */
96 public boolean setUnion(BitMap other) {
97 if (Assert.ASSERTS_ENABLED) {
98 Assert.that(size() == other.size(), "must have same size");
99 }
100 boolean changed = false;
101 for (int index = 0; index < sizeInWords(); index++) {
102 int temp = data[index] | other.data[index];
103 changed = changed || (temp != data[index]);
104 data[index] = temp;
105 }
106 return changed;
107 }
108
109 /** Sets this bitmap to the logical intersection of it and the
110 argument. Both bitmaps must be the same size. */
111 public void setIntersection(BitMap other) {
112 if (Assert.ASSERTS_ENABLED) {
113 Assert.that(size() == other.size(), "must have same size");
114 }
115 for (int index = 0; index < sizeInWords(); index++) {
116 data[index] = data[index] & (other.data[index]);
117 }
118 }
119
120 /** Sets this bitmap to the contents of the argument. Both bitmaps
121 must be the same size. */
122 public void setFrom(BitMap other) {
123 if (Assert.ASSERTS_ENABLED) {
124 Assert.that(size() == other.size(), "must have same size");
125 }
126 for (int index = 0; index < sizeInWords(); index++) {
127 data[index] = other.data[index];
128 }
129 }
130
131 /** Sets this bitmap to the logical difference between it and the
132 argument; that is, any bits that are set in the argument are
133 cleared in this bitmap. Both bitmaps must be the same size.
134 Returns true if a change was caused in this bitmap. */
135 public boolean setDifference(BitMap other) {
136 if (Assert.ASSERTS_ENABLED) {
137 Assert.that(size() == other.size(), "must have same size");
138 }
139 boolean changed = false;
140 for (int index = 0; index < sizeInWords(); index++) {
141 int temp = data[index] & ~(other.data[index]);
142 changed = changed || (temp != data[index]);
143 data[index] = temp;
144 }
145 return changed;
146 }
147
148 /** Both bitmaps must be the same size. */
149 public boolean isSame(BitMap other) {
150 if (Assert.ASSERTS_ENABLED) {
151 Assert.that(size() == other.size(), "must have same size");
152 }
153 for (int index = 0; index < sizeInWords(); index++) {
154 if (data[index] != (other.data[index])) return false;
155 }
156 return true;
157 }
158
159 public int getNextOneOffset(int l_offset, int r_offset) {
160 if (l_offset == r_offset) {
161 return l_offset;
162 }
163
164 int index = indexFor(l_offset);
165 int r_index = indexFor(r_offset);
166 int res_offset = l_offset;
167
168 int pos = bitInWord(res_offset);
169 int res = data[index] >> pos;
170
171 if (res != 0) {
172 // find the position of the 1-bit
173 for (; (res & 1) == 0; res_offset++) {
174 res = res >> 1;
175 }
176 return res_offset;
177 }
178 // skip over all word length 0-bit runs
179 for (index++; index < r_index; index++) {
180 res = data[index];
181 if (res != 0) {
182 // found a 1, return the offset
183 for (res_offset = index * bitsPerWord; (res & 1) == 0; res_offset++) {
184 res = res >> 1;
185 }
186 return res_offset;
187 }
188 }
189 return r_offset;
190 }
191
192 //----------------------------------------------------------------------
193 // Internals only below this point
194 //
195 private int size; // in bits
196 private int[] data;
197 private static final int bitsPerWord = 32;
198 private static final int bytesPerWord = 4;
199
200 private int sizeInWords() {
201 return (size() + bitsPerWord - 1) / bitsPerWord;
202 }
203
204 private int indexFor(int offset) {
205 return offset / bitsPerWord;
206 }
207
208 private int wordFor(int offset) {
209 return data[offset / bitsPerWord];
210 }
211
212 private int bitInWord(int offset) {
213 return offset & (bitsPerWord - 1);
214 }
215 }