1 /*
   2  * Copyright (c) 2011, 2017, 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.Iterator;
  26 import java.util.NoSuchElementException;
  27 
  28 class TypedGraphNodeIterator<T extends IterableNodeType> implements Iterator<T> {
  29 
  30     private final Graph graph;
  31     private final int[] ids;
  32     private final Node[] current;
  33 
  34     private int currentIdIndex;
  35     private boolean needsForward;
  36 
  37     TypedGraphNodeIterator(NodeClass<?> clazz, Graph graph) {
  38         this.graph = graph;
  39         ids = clazz.iterableIds();
  40         currentIdIndex = 0;
  41         current = new Node[ids.length];
  42         needsForward = true;
  43     }
  44 
  45     private Node findNext() {
  46         if (needsForward) {
  47             forward();
  48         } else {
  49             Node c = current();
  50             Node afterDeleted = graph.getIterableNodeNext(c);
  51             if (afterDeleted == null) {
  52                 needsForward = true;
  53             } else if (c != afterDeleted) {
  54                 setCurrent(afterDeleted);
  55             }
  56         }
  57         if (needsForward) {
  58             return null;
  59         }
  60         return current();
  61     }
  62 
  63     private void forward() {
  64         needsForward = false;
  65         int startIdx = currentIdIndex;
  66         while (true) {
  67             Node next;
  68             if (current() == null) {
  69                 next = graph.getIterableNodeStart(ids[currentIdIndex]);
  70             } else {
  71                 next = graph.getIterableNodeNext(current().typeCacheNext);
  72             }
  73             if (next == null) {
  74                 currentIdIndex++;
  75                 if (currentIdIndex >= ids.length) {
  76                     currentIdIndex = 0;
  77                 }
  78                 if (currentIdIndex == startIdx) {
  79                     needsForward = true;
  80                     return;
  81                 }
  82             } else {
  83                 setCurrent(next);
  84                 break;
  85             }
  86         }
  87     }
  88 
  89     private Node current() {
  90         return current[currentIdIndex];
  91     }
  92 
  93     private void setCurrent(Node n) {
  94         current[currentIdIndex] = n;
  95     }
  96 
  97     @Override
  98     public boolean hasNext() {
  99         return findNext() != null;
 100     }
 101 
 102     @Override
 103     @SuppressWarnings("unchecked")
 104     public T next() {
 105         Node result = findNext();
 106         if (result == null) {
 107             throw new NoSuchElementException();
 108         }
 109         needsForward = true;
 110         return (T) result;
 111     }
 112 
 113     @Override
 114     public void remove() {
 115         throw new UnsupportedOperationException();
 116     }
 117 }