|
0
|
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 }
|
