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 org.graalvm.compiler.graph;
  24 
  25 import java.util.ArrayDeque;
  26 import java.util.Iterator;
  27 import java.util.Queue;
  28 
  29 public 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 }