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 */
23package org.graalvm.compiler.core.common.util;
24
25import java.util.BitSet;
26
27/**
28 * This class implements a two-dimensional bitmap.
29 */
30public 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}
100