| /* |
| * Copyright (c) 2001, 2007, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| * |
| */ |
| |
| package sun.jvm.hotspot.utilities; |
| |
| import sun.jvm.hotspot.debugger.*; |
| |
| /** Manages a bitmap of the specified bit size */ |
| public class BitMap { |
| public BitMap(int sizeInBits) { |
| this.size = sizeInBits; |
| int nofWords = sizeInWords(); |
| data = new int[nofWords]; |
| } |
| |
| public int size() { |
| return size; |
| } |
| |
| // Accessors |
| public boolean at(int offset) { |
| if (Assert.ASSERTS_ENABLED) { |
| Assert.that(offset>=0 && offset < size(), "BitMap index out of bounds"); |
| } |
| return Bits.isSetNthBit(wordFor(offset), offset % bitsPerWord); |
| } |
| |
| public void atPut(int offset, boolean value) { |
| int index = indexFor(offset); |
| int pos = offset % bitsPerWord; |
| if (value) { |
| data[index] = Bits.setNthBit(data[index], pos); |
| } else { |
| data[index] = Bits.clearNthBit(data[index], pos); |
| } |
| } |
| |
| public void set_size(int value) { |
| size = value; |
| } |
| |
| public void set_map(Address addr) { |
| for (int i=0; i<sizeInWords(); i++) { |
| data[i] = (int) addr.getCIntegerAt(0, bytesPerWord, true); |
| addr = addr.addOffsetTo(bytesPerWord); |
| } |
| |
| } |
| |
| public void clear() { |
| for (int i = 0; i < sizeInWords(); i++) { |
| data[i] = Bits.NoBits; |
| } |
| } |
| |
| public void iterate(BitMapClosure blk) { |
| for (int index = 0; index < sizeInWords(); index++) { |
| int rest = data[index]; |
| for (int offset = index * bitsPerWord; rest != Bits.NoBits; offset++) { |
| if (rest % 2 == 1) { |
| if (offset < size()) { |
| blk.doBit(offset); |
| } else { |
| return; // Passed end of map |
| } |
| } |
| rest = rest >>> 1; |
| } |
| } |
| } |
| |
| /** Sets this bitmap to the logical union of it and the |
| argument. Both bitmaps must be the same size. Returns true if a |
| change was caused in this bitmap. */ |
| public boolean setUnion(BitMap other) { |
| if (Assert.ASSERTS_ENABLED) { |
| Assert.that(size() == other.size(), "must have same size"); |
| } |
| boolean changed = false; |
| for (int index = 0; index < sizeInWords(); index++) { |
| int temp = data[index] | other.data[index]; |
| changed = changed || (temp != data[index]); |
| data[index] = temp; |
| } |
| return changed; |
| } |
| |
| /** Sets this bitmap to the logical intersection of it and the |
| argument. Both bitmaps must be the same size. */ |
| public void setIntersection(BitMap other) { |
| if (Assert.ASSERTS_ENABLED) { |
| Assert.that(size() == other.size(), "must have same size"); |
| } |
| for (int index = 0; index < sizeInWords(); index++) { |
| data[index] = data[index] & (other.data[index]); |
| } |
| } |
| |
| /** Sets this bitmap to the contents of the argument. Both bitmaps |
| must be the same size. */ |
| public void setFrom(BitMap other) { |
| if (Assert.ASSERTS_ENABLED) { |
| Assert.that(size() == other.size(), "must have same size"); |
| } |
| for (int index = 0; index < sizeInWords(); index++) { |
| data[index] = other.data[index]; |
| } |
| } |
| |
| /** Sets this bitmap to the logical difference between it and the |
| argument; that is, any bits that are set in the argument are |
| cleared in this bitmap. Both bitmaps must be the same size. |
| Returns true if a change was caused in this bitmap. */ |
| public boolean setDifference(BitMap other) { |
| if (Assert.ASSERTS_ENABLED) { |
| Assert.that(size() == other.size(), "must have same size"); |
| } |
| boolean changed = false; |
| for (int index = 0; index < sizeInWords(); index++) { |
| int temp = data[index] & ~(other.data[index]); |
| changed = changed || (temp != data[index]); |
| data[index] = temp; |
| } |
| return changed; |
| } |
| |
| /** Both bitmaps must be the same size. */ |
| public boolean isSame(BitMap other) { |
| if (Assert.ASSERTS_ENABLED) { |
| Assert.that(size() == other.size(), "must have same size"); |
| } |
| for (int index = 0; index < sizeInWords(); index++) { |
| if (data[index] != (other.data[index])) return false; |
| } |
| return true; |
| } |
| |
| public int getNextOneOffset(int l_offset, int r_offset) { |
| if (l_offset == r_offset) { |
| return l_offset; |
| } |
| |
| int index = indexFor(l_offset); |
| int r_index = indexFor(r_offset); |
| int res_offset = l_offset; |
| |
| int pos = bitInWord(res_offset); |
| int res = data[index] >> pos; |
| |
| if (res != 0) { |
| // find the position of the 1-bit |
| for (; (res & 1) == 0; res_offset++) { |
| res = res >> 1; |
| } |
| return res_offset; |
| } |
| // skip over all word length 0-bit runs |
| for (index++; index < r_index; index++) { |
| res = data[index]; |
| if (res != 0) { |
| // found a 1, return the offset |
| for (res_offset = index * bitsPerWord; (res & 1) == 0; res_offset++) { |
| res = res >> 1; |
| } |
| return res_offset; |
| } |
| } |
| return r_offset; |
| } |
| |
| //---------------------------------------------------------------------- |
| // Internals only below this point |
| // |
| private int size; // in bits |
| private int[] data; |
| private static final int bitsPerWord = 32; |
| private static final int bytesPerWord = 4; |
| |
| private int sizeInWords() { |
| return (size() + bitsPerWord - 1) / bitsPerWord; |
| } |
| |
| private int indexFor(int offset) { |
| return offset / bitsPerWord; |
| } |
| |
| private int wordFor(int offset) { |
| return data[offset / bitsPerWord]; |
| } |
| |
| private int bitInWord(int offset) { |
| return offset & (bitsPerWord - 1); |
| } |
| } |