1 /*
   2  * Copyright (c) 2009, 2011, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.core.common.util;
  26 
  27 import java.util.BitSet;
  28 
  29 /**
  30  * This class implements a two-dimensional bitmap.
  31  */
  32 public final class BitMap2D {
  33 
  34     private BitSet map;
  35     private final int bitsPerSlot;
  36 
  37     private int bitIndex(int slotIndex, int bitWithinSlotIndex) {
  38         return slotIndex * bitsPerSlot + bitWithinSlotIndex;
  39     }
  40 
  41     private boolean verifyBitWithinSlotIndex(int index) {
  42         assert index < bitsPerSlot : "index " + index + " is out of bounds " + bitsPerSlot;
  43         return true;
  44     }
  45 
  46     public BitMap2D(int sizeInSlots, int bitsPerSlot) {
  47         map = new BitSet(sizeInSlots * bitsPerSlot);
  48         this.bitsPerSlot = bitsPerSlot;
  49     }
  50 
  51     public int sizeInBits() {
  52         return map.size();
  53     }
  54 
  55     // Returns number of full slots that have been allocated
  56     public int sizeInSlots() {
  57         return map.size() / bitsPerSlot;
  58     }
  59 
  60     public boolean isValidIndex(int slotIndex, int bitWithinSlotIndex) {
  61         assert verifyBitWithinSlotIndex(bitWithinSlotIndex);
  62         return (bitIndex(slotIndex, bitWithinSlotIndex) < sizeInBits());
  63     }
  64 
  65     public boolean at(int slotIndex, int bitWithinSlotIndex) {
  66         assert verifyBitWithinSlotIndex(bitWithinSlotIndex);
  67         return map.get(bitIndex(slotIndex, bitWithinSlotIndex));
  68     }
  69 
  70     public void setBit(int slotIndex, int bitWithinSlotIndex) {
  71         assert verifyBitWithinSlotIndex(bitWithinSlotIndex);
  72         map.set(bitIndex(slotIndex, bitWithinSlotIndex));
  73     }
  74 
  75     public void clearBit(int slotIndex, int bitWithinSlotIndex) {
  76         assert verifyBitWithinSlotIndex(bitWithinSlotIndex);
  77         map.clear(bitIndex(slotIndex, bitWithinSlotIndex));
  78     }
  79 
  80     public void atPutGrow(int slotIndex, int bitWithinSlotIndex, boolean value) {
  81         int size = sizeInSlots();
  82         if (size <= slotIndex) {
  83             while (size <= slotIndex) {
  84                 size *= 2;
  85             }
  86             BitSet newBitMap = new BitSet(size * bitsPerSlot);
  87             newBitMap.or(map);
  88             map = newBitMap;
  89         }
  90 
  91         if (value) {
  92             setBit(slotIndex, bitWithinSlotIndex);
  93         } else {
  94             clearBit(slotIndex, bitWithinSlotIndex);
  95         }
  96     }
  97 
  98     public void clear() {
  99         map.clear();
 100     }
 101 }