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