BitMap.java

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