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