001/*
002 * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.graph;
024
025import java.util.*;
026
027import com.oracle.graal.graph.iterators.*;
028
029public final class NodeBitMap implements NodeIterable<Node> {
030    private static final int SHIFT = 6;
031
032    private long[] bits;
033    private int nodeCount;
034    private final NodeIdAccessor nodeIdAccessor;
035    private int counter;
036
037    public NodeBitMap(Graph graph) {
038        nodeCount = graph.nodeIdCount();
039        bits = new long[sizeForNodeCount(nodeCount)];
040        this.nodeIdAccessor = new NodeIdAccessor(graph);
041    }
042
043    private static int sizeForNodeCount(int nodeCount) {
044        return (nodeCount + Long.SIZE - 1) >> SHIFT;
045    }
046
047    public int getCounter() {
048        return counter;
049    }
050
051    private NodeBitMap(NodeBitMap other) {
052        this.bits = other.bits.clone();
053        this.nodeCount = other.nodeCount;
054        this.nodeIdAccessor = other.nodeIdAccessor;
055    }
056
057    public Graph graph() {
058        return nodeIdAccessor.getGraph();
059    }
060
061    public boolean isNew(Node node) {
062        return nodeIdAccessor.getNodeId(node) >= nodeCount;
063    }
064
065    public boolean isMarked(Node node) {
066        assert check(node, false);
067        int id = nodeIdAccessor.getNodeId(node);
068        return isMarked(id);
069    }
070
071    public boolean checkAndMarkInc(Node node) {
072        if (!isMarked(node)) {
073            this.counter++;
074            this.mark(node);
075            return true;
076        } else {
077            return false;
078        }
079    }
080
081    public boolean isMarked(int id) {
082        return (bits[id >> SHIFT] & (1L << id)) != 0;
083    }
084
085    public boolean isMarkedAndGrow(Node node) {
086        assert check(node, true);
087        int id = nodeIdAccessor.getNodeId(node);
088        checkGrow(id);
089        return isMarked(id);
090    }
091
092    public void mark(Node node) {
093        assert check(node, false);
094        int id = nodeIdAccessor.getNodeId(node);
095        bits[id >> SHIFT] |= (1L << id);
096    }
097
098    public void markAndGrow(Node node) {
099        assert check(node, true);
100        int id = nodeIdAccessor.getNodeId(node);
101        checkGrow(id);
102        bits[id >> SHIFT] |= (1L << id);
103    }
104
105    public void clear(Node node) {
106        assert check(node, false);
107        int id = nodeIdAccessor.getNodeId(node);
108        bits[id >> SHIFT] &= ~(1L << id);
109    }
110
111    public void clearAndGrow(Node node) {
112        assert check(node, true);
113        int id = nodeIdAccessor.getNodeId(node);
114        checkGrow(id);
115        bits[id >> SHIFT] &= ~(1L << id);
116    }
117
118    private void checkGrow(int id) {
119        if (id >= nodeCount) {
120            if ((id >> SHIFT) >= bits.length) {
121                grow();
122            } else {
123                nodeCount = id + 1;
124            }
125        }
126    }
127
128    public void clearAll() {
129        Arrays.fill(bits, 0);
130    }
131
132    public void intersect(NodeBitMap other) {
133        assert graph() == other.graph();
134        int commonLength = Math.min(bits.length, other.bits.length);
135        for (int i = commonLength; i < bits.length; i++) {
136            bits[i] = 0;
137        }
138        for (int i = 0; i < commonLength; i++) {
139            bits[i] &= other.bits[i];
140        }
141    }
142
143    public void grow() {
144        nodeCount = Math.max(nodeCount, graph().nodeIdCount());
145        int newLength = sizeForNodeCount(nodeCount);
146        if (newLength > bits.length) {
147            newLength = Math.max(newLength, (bits.length * 3 / 2) + 1);
148            bits = Arrays.copyOf(bits, newLength);
149        }
150    }
151
152    private boolean check(Node node, boolean grow) {
153        assert node.graph() == graph() : "this node is not part of the graph";
154        assert grow || !isNew(node) : "node was added to the graph after creating the node bitmap: " + node;
155        assert node.isAlive() : "node is deleted!";
156        return true;
157    }
158
159    public <T extends Node> void markAll(Iterable<T> nodes) {
160        for (Node node : nodes) {
161            mark(node);
162        }
163    }
164
165    private static class MarkedNodeIterator implements Iterator<Node> {
166
167        private final NodeBitMap visited;
168        private Iterator<Node> nodes;
169        private Node nextNode;
170
171        public MarkedNodeIterator(NodeBitMap visited, Iterator<Node> nodes) {
172            this.visited = visited;
173            this.nodes = nodes;
174            forward();
175        }
176
177        private void forward() {
178            do {
179                if (!nodes.hasNext()) {
180                    nextNode = null;
181                    return;
182                }
183                nextNode = nodes.next();
184                if (visited.isNew(nextNode)) {
185                    nextNode = null;
186                    return;
187                }
188            } while (!visited.isMarked(nextNode));
189        }
190
191        @Override
192        public boolean hasNext() {
193            return nextNode != null;
194        }
195
196        @Override
197        public Node next() {
198            try {
199                return nextNode;
200            } finally {
201                forward();
202            }
203        }
204
205        @Override
206        public void remove() {
207            throw new UnsupportedOperationException();
208        }
209
210    }
211
212    @Override
213    public Iterator<Node> iterator() {
214        return new MarkedNodeIterator(NodeBitMap.this, graph().getNodes().iterator());
215    }
216
217    public NodeBitMap copy() {
218        return new NodeBitMap(this);
219    }
220
221    @Override
222    public NodeIterable<Node> distinct() {
223        return this;
224    }
225
226    @Override
227    public int count() {
228        int count = 0;
229        for (long l : bits) {
230            count += Long.bitCount(l);
231        }
232        return count;
233    }
234
235    @Override
236    public boolean contains(Node node) {
237        return isMarked(node);
238    }
239
240    @Override
241    public String toString() {
242        return snapshot().toString();
243    }
244}