/*
 * 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
/** 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.
/** 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.
/** 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.
/** 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.
/** 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.
/** 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); } }