1/*
2 * Copyright (c) 2011, 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.graph;
24
25import java.util.ArrayDeque;
26import java.util.Iterator;
27import java.util.Queue;
28
29public final class NodeFlood implements Iterable<Node> {
30
31    private final NodeBitMap visited;
32    private final Queue<Node> worklist;
33    private int totalMarkedCount;
34
35    public NodeFlood(Graph graph) {
36        visited = graph.createNodeBitMap();
37        worklist = new ArrayDeque<>();
38    }
39
40    public void add(Node node) {
41        if (node != null && !visited.isMarked(node)) {
42            visited.mark(node);
43            worklist.add(node);
44            totalMarkedCount++;
45        }
46    }
47
48    public int getTotalMarkedCount() {
49        return totalMarkedCount;
50    }
51
52    public void addAll(Iterable<? extends Node> nodes) {
53        for (Node node : nodes) {
54            this.add(node);
55        }
56    }
57
58    public NodeBitMap getVisited() {
59        return visited;
60    }
61
62    public boolean isMarked(Node node) {
63        return visited.isMarked(node);
64    }
65
66    public boolean isNew(Node node) {
67        return visited.isNew(node);
68    }
69
70    private static class QueueConsumingIterator implements Iterator<Node> {
71
72        private final Queue<Node> queue;
73
74        QueueConsumingIterator(Queue<Node> queue) {
75            this.queue = queue;
76        }
77
78        @Override
79        public boolean hasNext() {
80            return !queue.isEmpty();
81        }
82
83        @Override
84        public Node next() {
85            return queue.remove();
86        }
87
88        @Override
89        public void remove() {
90            throw new UnsupportedOperationException();
91        }
92    }
93
94    @Override
95    public Iterator<Node> iterator() {
96        return new QueueConsumingIterator(worklist);
97    }
98
99    private static class UnmarkedNodeIterator implements Iterator<Node> {
100
101        private final NodeBitMap visited;
102        private Iterator<Node> nodes;
103        private Node nextNode;
104
105        UnmarkedNodeIterator(NodeBitMap visited, Iterator<Node> nodes) {
106            this.visited = visited;
107            this.nodes = nodes;
108            forward();
109        }
110
111        private void forward() {
112            do {
113                if (!nodes.hasNext()) {
114                    nextNode = null;
115                    return;
116                }
117                nextNode = nodes.next();
118            } while (visited.isMarked(nextNode));
119        }
120
121        @Override
122        public boolean hasNext() {
123            return nextNode != null;
124        }
125
126        @Override
127        public Node next() {
128            try {
129                return nextNode;
130            } finally {
131                forward();
132            }
133        }
134
135        @Override
136        public void remove() {
137            throw new UnsupportedOperationException();
138        }
139    }
140
141    public Iterable<Node> unmarkedNodes() {
142        return new Iterable<Node>() {
143
144            @Override
145            public Iterator<Node> iterator() {
146                return new UnmarkedNodeIterator(visited, visited.graph().getNodes().iterator());
147            }
148        };
149    }
150}
151