1 /*
2  * Copyright (c) 2009, 2020, 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 
bitIndex(int slotIndex, int bitWithinSlotIndex)37     private int bitIndex(int slotIndex, int bitWithinSlotIndex) {
38         return slotIndex * bitsPerSlot + bitWithinSlotIndex;
39     }
40 
verifyBitWithinSlotIndex(int index)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         long nBits = (long) sizeInSlots * bitsPerSlot;
48         if (nBits > Integer.MAX_VALUE) {
49             // Avoids issues where (sizeInSlots * bitsPerSlot) wraps around to a positive integer
50             throw new OutOfMemoryError("Cannot allocate a BitSet for " + nBits + " bits");
51         }
52         map = new BitSet(sizeInSlots * bitsPerSlot);
53         this.bitsPerSlot = bitsPerSlot;
54     }
55 
sizeInBits()56     public int sizeInBits() {
57         return map.size();
58     }
59 
60     // Returns number of full slots that have been allocated
sizeInSlots()61     public int sizeInSlots() {
62         return map.size() / bitsPerSlot;
63     }
64 
isValidIndex(int slotIndex, int bitWithinSlotIndex)65     public boolean isValidIndex(int slotIndex, int bitWithinSlotIndex) {
66         assert verifyBitWithinSlotIndex(bitWithinSlotIndex);
67         return (bitIndex(slotIndex, bitWithinSlotIndex) < sizeInBits());
68     }
69 
at(int slotIndex, int bitWithinSlotIndex)70     public boolean at(int slotIndex, int bitWithinSlotIndex) {
71         assert verifyBitWithinSlotIndex(bitWithinSlotIndex);
72         return map.get(bitIndex(slotIndex, bitWithinSlotIndex));
73     }
74 
setBit(int slotIndex, int bitWithinSlotIndex)75     public void setBit(int slotIndex, int bitWithinSlotIndex) {
76         assert verifyBitWithinSlotIndex(bitWithinSlotIndex);
77         map.set(bitIndex(slotIndex, bitWithinSlotIndex));
78     }
79 
clearBit(int slotIndex, int bitWithinSlotIndex)80     public void clearBit(int slotIndex, int bitWithinSlotIndex) {
81         assert verifyBitWithinSlotIndex(bitWithinSlotIndex);
82         map.clear(bitIndex(slotIndex, bitWithinSlotIndex));
83     }
84 
atPutGrow(int slotIndex, int bitWithinSlotIndex, boolean value)85     public void atPutGrow(int slotIndex, int bitWithinSlotIndex, boolean value) {
86         int size = sizeInSlots();
87         if (size <= slotIndex) {
88             while (size <= slotIndex) {
89                 size *= 2;
90             }
91             BitSet newBitMap = new BitSet(size * bitsPerSlot);
92             newBitMap.or(map);
93             map = newBitMap;
94         }
95 
96         if (value) {
97             setBit(slotIndex, bitWithinSlotIndex);
98         } else {
99             clearBit(slotIndex, bitWithinSlotIndex);
100         }
101     }
102 
clear()103     public void clear() {
104         map.clear();
105     }
106 }
107