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