Mercurial > hg > truffle

comparison graal/com.oracle.max.graal.graph/src/com/oracle/graal/graph/NodeFlood.java @ 5059:ed559a528128

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Perform renames on files.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Thu, 08 Mar 2012 17:57:30 +0100
parents graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeFlood.java@bc8527f3071c
children 4ed4295ce15f
comparison
equal deleted inserted replaced
5058:26f8371c229c 5059:ed559a528128
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 */
23 package com.oracle.max.graal.graph;
24
25 import java.util.ArrayDeque;
26 import java.util.Iterator;
27 import java.util.Queue;
28
29
30 public class NodeFlood implements Iterable<Node> {
31 private final NodeBitMap visited;
32 private final Queue<Node> worklist;
33
34 public NodeFlood(Graph graph) {
35 visited = graph.createNodeBitMap();
36 worklist = new ArrayDeque<>();
37 }
38
39 public void add(Node node) {
40 if (node != null && !visited.isMarked(node)) {
41 visited.mark(node);
42 worklist.add(node);
43 }
44 }
45
46 public void addAll(Iterable<Node> nodes) {
47 for (Node node : nodes) {
48 this.add(node);
49 }
50 }
51
52 public boolean isMarked(Node node) {
53 return visited.isMarked(node);
54 }
55
56 public boolean isNew(Node node) {
57 return visited.isNew(node);
58 }
59
60 private static class QueueConsumingIterator implements Iterator<Node> {
61 private final Queue<Node> queue;
62
63 public QueueConsumingIterator(Queue<Node> queue) {
64 this.queue = queue;
65 }
66
67 @Override
68 public boolean hasNext() {
69 return !queue.isEmpty();
70 }
71
72 @Override
73 public Node next() {
74 return queue.remove();
75 }
76
77 @Override
78 public void remove() {
79 throw new UnsupportedOperationException();
80 }
81 }
82
83 @Override
84 public Iterator<Node> iterator() {
85 return new QueueConsumingIterator(worklist);
86 }
87
88 private static class UnmarkedNodeIterator implements Iterator<Node> {
89 private final NodeBitMap visited;
90 private Iterator<Node> nodes;
91 private Node nextNode;
92
93 public UnmarkedNodeIterator(NodeBitMap visited, Iterator<Node> nodes) {
94 this.visited = visited;
95 this.nodes = nodes;
96 forward();
97 }
98
99 private void forward() {
100 do {
101 if (!nodes.hasNext()) {
102 nextNode = null;
103 return;
104 }
105 nextNode = nodes.next();
106 } while (visited.isMarked(nextNode));
107 }
108
109 @Override
110 public boolean hasNext() {
111 return nextNode != null;
112 }
113
114 @Override
115 public Node next() {
116 try {
117 return nextNode;
118 } finally {
119 forward();
120 }
121 }
122
123 @Override
124 public void remove() {
125 throw new UnsupportedOperationException();
126 }
127 }
128
129 public Iterable<Node> unmarkedNodes() {
130 return new Iterable<Node>() {
131 @Override
132 public Iterator<Node> iterator() {
133 return new UnmarkedNodeIterator(visited, visited.graph().getNodes().iterator());
134 }
135 };
136 }
137 }