changeset 7344:66c0dd07e288

Modify the conc-Node spliterator forEach and tryAdvance from using the call stack to using an explicit (Deque) stack and a depth first search to find leaf nodes. This avoids stack overflow expceptions with tryAdvance and forEach for right-balanced or degenerate treess. This also avoids the internal creation of n spliterators when using tryAdvance, where n is the depth of the tree.
author psandoz
date Mon, 18 Feb 2013 15:09:19 +0100
parents 07984401133f
children cc01521c9211
files src/share/classes/java/util/stream/Nodes.java
diffstat 1 files changed, 108 insertions(+), 38 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/stream/Nodes.java	Fri Feb 15 17:30:05 2013 -0800
+++ b/src/share/classes/java/util/stream/Nodes.java	Mon Feb 18 15:09:19 2013 +0100
@@ -24,8 +24,10 @@
  */
 package java.util.stream;
 
+import java.util.ArrayDeque;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.Deque;
 import java.util.List;
 import java.util.Objects;
 import java.util.Spliterator;
@@ -837,28 +839,80 @@
         // null if no partial traversal has occurred
         protected S tryAdvanceSpliterator;
 
+        // node stack used when traversing to search and find leaf nodes
+        // null if no partial traversal has occurred
+        private Deque<N> tryAdvanceStack;
+
         private InternalNodeSpliterator(N curNode) {
             this.curNode = curNode;
         }
 
-        protected boolean internalTryAdvance(C consumer) {
+        /**
+         * Initiate a stack containing, in left-to-right order, the child nodes covered by this spliterator
+         */
+        protected final Deque<N> initStack() {
+            // Bias size to the case where leaf nodes are close to this node
+            // 8 is the minimum initial capacity for the ArrayDeque implementation
+            Deque<N> stack = new ArrayDeque<>(8);
+            for (int i = curNode.getChildCount() - 1; i >= curChildIndex; i--)
+                stack.addFirst((N) curNode.getChild(i));
+            return stack;
+        }
+
+        /**
+         * Depth first search, in left-to-right order, of the node tree, using an explicit stack, to find
+         * the next non-empty leaf node.
+         */
+        protected final N findNextLeafNode(Deque<N> stack) {
+            N n = null;
+            while ((n = stack.pollFirst()) != null) {
+                if (n.getChildCount() == 0) {
+                    if (n.count() > 0)
+                        return n;
+                } else {
+                    for (int i = n.getChildCount() - 1; i >= 0; i--)
+                        stack.addFirst((N) n.getChild(i));
+                }
+            }
+
+            return null;
+        }
+
+        protected final boolean internalTryAdvance(C consumer) {
             if (curNode == null)
                 return false;
 
             if (tryAdvanceSpliterator == null) {
-                tryAdvanceSpliterator = lastNodeSpliterator != null
-                                        ? lastNodeSpliterator
-                                        : (S) curNode.getChild(curChildIndex).spliterator();
+                if (lastNodeSpliterator == null) {
+                    // Initiate the node stack
+                    tryAdvanceStack = initStack();
+                    N leaf = findNextLeafNode(tryAdvanceStack);
+                    if (leaf != null)
+                        tryAdvanceSpliterator = (S) leaf.spliterator();
+                    else {
+                        // A non-empty leaf node was not found
+                        // No elements to traverse
+                        curNode = null;
+                        return false;
+                    }
+                }
+                else
+                    tryAdvanceSpliterator = lastNodeSpliterator;
             }
 
             boolean hasNext = tryAdvance(tryAdvanceSpliterator, consumer);
             if (!hasNext) {
-                while (!hasNext && ++curChildIndex < curNode.getChildCount()) {
-                    tryAdvanceSpliterator = (S) curNode.getChild(curChildIndex).spliterator();
-                    hasNext = tryAdvance(tryAdvanceSpliterator, consumer);
+                if (lastNodeSpliterator == null) {
+                    // Advance to the spliterator of the next non-empty leaf node
+                    Node<T> leaf = findNextLeafNode(tryAdvanceStack);
+                    if (leaf != null) {
+                        tryAdvanceSpliterator = (S) leaf.spliterator();
+                        // Since the node is not-empty the spliterator can be advanced
+                        return tryAdvance(tryAdvanceSpliterator, consumer);
+                    }
                 }
-                if (!hasNext)
-                    curNode = null;
+                // No more elements to traverse
+                curNode = null;
             }
             return hasNext;
         }
@@ -897,12 +951,8 @@
                 return lastNodeSpliterator.estimateSize();
             else {
                 long size = 0;
-                for (int i = curChildIndex; i < curNode.getChildCount(); i++) {
-                    long thisSize = curNode.getChild(i).count();
-                    if (thisSize == -1)
-                        return -1;
+                for (int i = curChildIndex; i < curNode.getChildCount(); i++)
                     size += curNode.getChild(i).count();
-                }
                 return size;
             }
         }
@@ -933,13 +983,18 @@
                     return;
 
                 if (tryAdvanceSpliterator == null) {
-                    if (lastNodeSpliterator != null)
+                    if (lastNodeSpliterator == null) {
+                        Deque<Node<T>> stack = initStack();
+                        Node<T> leaf;
+                        while ((leaf = findNextLeafNode(stack)) != null) {
+                            leaf.forEach(consumer);
+                        }
+                        curNode = null;
+                    }
+                    else
                         lastNodeSpliterator.forEach(consumer);
-                    else
-                        for (int i = curChildIndex; i < curNode.getChildCount(); i++)
-                            curNode.getChild(i).forEach(consumer);
-                    curNode = null;
-                } else
+                }
+                else
                     while(tryAdvance(consumer)) { }
             }
         }
@@ -967,13 +1022,18 @@
                     return;
 
                 if (tryAdvanceSpliterator == null) {
-                    if (lastNodeSpliterator != null)
+                    if (lastNodeSpliterator == null) {
+                        Deque<Node.OfInt> stack = initStack();
+                        Node.OfInt leaf;
+                        while ((leaf = findNextLeafNode(stack)) != null) {
+                            leaf.forEach(consumer);
+                        }
+                        curNode = null;
+                    }
+                    else
                         lastNodeSpliterator.forEach(consumer);
-                    else
-                        for (int i = curChildIndex; i < curNode.getChildCount(); i++)
-                            curNode.getChild(i).forEach(consumer);
-                    curNode = null;
-                } else
+                }
+                else
                     while(tryAdvance(consumer)) { }
             }
         }
@@ -1001,13 +1061,18 @@
                     return;
 
                 if (tryAdvanceSpliterator == null) {
-                    if (lastNodeSpliterator != null)
+                    if (lastNodeSpliterator == null) {
+                        Deque<Node.OfLong> stack = initStack();
+                        Node.OfLong leaf;
+                        while ((leaf = findNextLeafNode(stack)) != null) {
+                            leaf.forEach(consumer);
+                        }
+                        curNode = null;
+                    }
+                    else
                         lastNodeSpliterator.forEach(consumer);
-                    else
-                        for (int i = curChildIndex; i < curNode.getChildCount(); i++)
-                            curNode.getChild(i).forEach(consumer);
-                    curNode = null;
-                } else
+                }
+                else
                     while(tryAdvance(consumer)) { }
             }
         }
@@ -1035,13 +1100,18 @@
                     return;
 
                 if (tryAdvanceSpliterator == null) {
-                    if (lastNodeSpliterator != null)
+                    if (lastNodeSpliterator == null) {
+                        Deque<Node.OfDouble> stack = initStack();
+                        Node.OfDouble leaf;
+                        while ((leaf = findNextLeafNode(stack)) != null) {
+                            leaf.forEach(consumer);
+                        }
+                        curNode = null;
+                    }
+                    else
                         lastNodeSpliterator.forEach(consumer);
-                    else
-                        for (int i = curChildIndex; i < curNode.getChildCount(); i++)
-                            curNode.getChild(i).forEach(consumer);
-                    curNode = null;
-                } else
+                }
+                else
                     while(tryAdvance(consumer)) { }
             }
         }