changeset 7539:eadbf7bcb6f8

Fork left and compute on right in loop to avoid potential stack overflows with right-balanced trees (e.g. those created from iterator-based spliterators).
author psandoz
date Tue, 26 Feb 2013 17:34:47 +0100
parents 0b8d535e6869
children 9619ab4afc70
files src/share/classes/java/util/stream/NodeUtils.java
diffstat 1 files changed, 170 insertions(+), 100 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/stream/NodeUtils.java	Tue Feb 26 16:24:08 2013 +0100
+++ b/src/share/classes/java/util/stream/NodeUtils.java	Tue Feb 26 17:34:47 2013 +0100
@@ -376,18 +376,29 @@
 
         @Override
         public void compute() {
-            Spliterator<T> split;
-            if (!AbstractTask.suggestSplit(helper, spliterator, targetSize) || ((split = spliterator.trySplit()) == null)) {
-                if (offset+length >= Streams.MAX_ARRAY_SIZE)
-                    throw new IllegalArgumentException("Stream size exceeds max array size");
-                helper.into(new ArraySink<>(array, (int) offset, (int) length), spliterator);
-                tryComplete();
-            }
-            else {
-                setPendingCount(1);
-                long thisSplitSize = split.estimateSize();
-                new SizedCollectorTask<>(this, split, offset, thisSplitSize).fork();
-                new SizedCollectorTask<>(this, spliterator, offset + thisSplitSize, length - thisSplitSize).compute();
+            doCompute(this);
+        }
+
+        private static <T, U> void doCompute(SizedCollectorTask<T, U> task) {
+            while (true) {
+                Spliterator<T> leftSplit;
+                if (!AbstractTask.suggestSplit(task.helper, task.spliterator, task.targetSize)
+                    || ((leftSplit = task.spliterator.trySplit()) == null)) {
+                    if (task.offset + task.length >= Streams.MAX_ARRAY_SIZE)
+                        throw new IllegalArgumentException("Stream size exceeds max array size");
+                    task.helper.into(new ArraySink<>(task.array, (int) task.offset,
+                                                     (int) task.length), task.spliterator);
+                    task.propagateCompletion();
+                    return;
+                }
+                else {
+                    task.setPendingCount(1);
+                    long leftSplitSize = leftSplit.estimateSize();
+                    new SizedCollectorTask<>(task, leftSplit,
+                                             task.offset, leftSplitSize).fork();
+                    task = new SizedCollectorTask<>(task, task.spliterator,
+                                                    task.offset + leftSplitSize, task.length - leftSplitSize);
+                }
             }
         }
     }
@@ -412,21 +423,28 @@
 
         @Override
         public void compute() {
-            if (node.getChildCount() > 0) {
-                setPendingCount(node.getChildCount() - 1);
+            doCompute(this);
+        }
 
-                final ToArrayTask<T> firstTask = new ToArrayTask<>(this, node.getChild(0), offset);
-                int size = (int) firstTask.node.count();
+        private static <T> void doCompute(ToArrayTask<T> task) {
+            while (true) {
+                if (task.node.getChildCount() == 0) {
+                    task.node.copyInto(task.array, task.offset);
+                    task.propagateCompletion();
+                    return;
+                }
+                else {
+                    task.setPendingCount(task.node.getChildCount() - 1);
 
-                for (int i = 1; i < node.getChildCount(); i++) {
-                    final ToArrayTask<T> task = new ToArrayTask<>(this, node.getChild(i), offset + size);
-                    size += task.node.count();
-                    task.fork();
+                    int size = 0;
+                    int i = 0;
+                    for (;i < task.node.getChildCount() - 1; i++) {
+                        ToArrayTask<T> leftTask = new ToArrayTask<>(task, task.node.getChild(i), task.offset + size);
+                        size += leftTask.node.count();
+                        leftTask.fork();
+                    }
+                    task = new ToArrayTask<>(task, task.node.getChild(i), task.offset + size);
                 }
-                firstTask.compute();
-            } else {
-                node.copyInto(array, offset);
-                tryComplete();
             }
         }
     }
@@ -541,20 +559,32 @@
 
         @Override
         public void compute() {
-            Spliterator<T> split;
-            if (!AbstractTask.suggestSplit(helper, spliterator, targetSize) || ((split = spliterator.trySplit()) == null)) {
-                if (offset+length >= Streams.MAX_ARRAY_SIZE)
-                    throw new IllegalArgumentException("Stream size exceeds max array size");
-                helper.into(new IntArraySink(array, (int) offset, (int) length), spliterator);
-                tryComplete();
-            }
-            else {
-                setPendingCount(1);
-                long thisSplitSize = split.estimateSize();
-                new IntSizedCollectorTask<>(this, split, offset, thisSplitSize).fork();
-                new IntSizedCollectorTask<>(this, spliterator, offset + thisSplitSize, length - thisSplitSize).compute();
+            doCompute(this);
+        }
+
+        private static <T> void doCompute(IntSizedCollectorTask<T> task) {
+            while (true) {
+                Spliterator<T> leftSplit;
+                if (!AbstractTask.suggestSplit(task.helper, task.spliterator, task.targetSize)
+                    || ((leftSplit = task.spliterator.trySplit()) == null)) {
+                    if (task.offset + task.length >= Streams.MAX_ARRAY_SIZE)
+                        throw new IllegalArgumentException("Stream size exceeds max array size");
+                    task.helper.into(new IntArraySink(task.array, (int) task.offset,
+                                                     (int) task.length), task.spliterator);
+                    task.propagateCompletion();
+                    return;
+                }
+                else {
+                    task.setPendingCount(1);
+                    long leftSplitSize = leftSplit.estimateSize();
+                    new IntSizedCollectorTask<>(task, leftSplit,
+                                                task.offset, leftSplitSize).fork();
+                    task = new IntSizedCollectorTask<>(task, task.spliterator,
+                                                       task.offset + leftSplitSize, task.length - leftSplitSize);
+                }
             }
         }
+
     }
 
     private static final class IntToArrayTask extends CountedCompleter<Void> {
@@ -577,22 +607,28 @@
 
         @Override
         public void compute() {
-            if (node.getChildCount() > 0) {
-                setPendingCount(node.getChildCount() - 1);
+            doCompute(this);
+        }
 
-                final IntToArrayTask firstTask = new IntToArrayTask(this, node.getChild(0), offset);
-                int size = (int) firstTask.node.count();
+        private static void doCompute(IntToArrayTask task) {
+            while (true) {
+                if (task.node.getChildCount() == 0) {
+                    task.node.copyInto(task.array, task.offset);
+                    task.propagateCompletion();
+                    return;
+                }
+                else {
+                    task.setPendingCount(task.node.getChildCount() - 1);
 
-                for (int i = 1; i < node.getChildCount(); i++) {
-                    final IntToArrayTask task = new IntToArrayTask(this, node.getChild(i), offset + size);
-                    size += task.node.count();
-                    task.fork();
+                    int size = 0;
+                    int i = 0;
+                    for (;i < task.node.getChildCount() - 1; i++) {
+                        IntToArrayTask leftTask = new IntToArrayTask(task, task.node.getChild(i), task.offset + size);
+                        size += leftTask.node.count();
+                        leftTask.fork();
+                    }
+                    task = new IntToArrayTask(task, task.node.getChild(i), task.offset + size);
                 }
-                firstTask.compute();
-            }
-            else {
-                node.copyInto(array, offset);
-                tryComplete();
             }
         }
     }
@@ -703,20 +739,31 @@
 
         @Override
         public void compute() {
-            Spliterator<T> split;
-            if (!AbstractTask.suggestSplit(helper, spliterator, targetSize) || ((split = spliterator.trySplit()) == null)) {
-                if (offset+length >= Streams.MAX_ARRAY_SIZE)
-                    throw new IllegalArgumentException("Stream size exceeds max array size");
-                helper.into(new LongArraySink(array, (int) offset, (int) length), spliterator);
-                tryComplete();
+            doCompute(this);
+        }
+
+        private static <T> void doCompute(LongSizedCollectorTask<T> task) {
+            while (true) {
+                Spliterator<T> leftSplit;
+                if (!AbstractTask.suggestSplit(task.helper, task.spliterator, task.targetSize)
+                    || ((leftSplit = task.spliterator.trySplit()) == null)) {
+                    if (task.offset + task.length >= Streams.MAX_ARRAY_SIZE)
+                        throw new IllegalArgumentException("Stream size exceeds max array size");
+                    task.helper.into(new LongArraySink(task.array, (int) task.offset,
+                                                      (int) task.length), task.spliterator);
+                    task.propagateCompletion();
+                    return;
+                }
+                else {
+                    task.setPendingCount(1);
+                    long leftSplitSize = leftSplit.estimateSize();
+                    new LongSizedCollectorTask<>(task, leftSplit,
+                                                 task.offset, leftSplitSize).fork();
+                    task = new LongSizedCollectorTask<>(task, task.spliterator,
+                                                        task.offset + leftSplitSize, task.length - leftSplitSize);
+                }
             }
-            else {
-                setPendingCount(1);
-                long thisSplitSize = split.estimateSize();
-                new LongSizedCollectorTask<>(this, split, offset, thisSplitSize).fork();
-                new LongSizedCollectorTask<>(this, spliterator, offset + thisSplitSize, length - thisSplitSize).compute();
-            }
-        }
+        }        
     }
 
     private static final class LongToArrayTask extends CountedCompleter<Void> {
@@ -739,22 +786,28 @@
 
         @Override
         public void compute() {
-            if (node.getChildCount() > 0) {
-                setPendingCount(node.getChildCount() - 1);
+            doCompute(this);
+        }
 
-                final LongToArrayTask firstTask = new LongToArrayTask(this, node.getChild(0), offset);
-                int size = (int) firstTask.node.count();
+        private static void doCompute(LongToArrayTask task) {
+            while (true) {
+                if (task.node.getChildCount() == 0) {
+                    task.node.copyInto(task.array, task.offset);
+                    task.propagateCompletion();
+                    return;
+                }
+                else {
+                    task.setPendingCount(task.node.getChildCount() - 1);
 
-                for (int i = 1; i < node.getChildCount(); i++) {
-                    final LongToArrayTask task = new LongToArrayTask(this, node.getChild(i), offset + size);
-                    size += task.node.count();
-                    task.fork();
+                    int size = 0;
+                    int i = 0;
+                    for (;i < task.node.getChildCount() - 1; i++) {
+                        LongToArrayTask leftTask = new LongToArrayTask(task, task.node.getChild(i), task.offset + size);
+                        size += leftTask.node.count();
+                        leftTask.fork();
+                    }
+                    task = new LongToArrayTask(task, task.node.getChild(i), task.offset + size);
                 }
-                firstTask.compute();
-            }
-            else {
-                node.copyInto(array, offset);
-                tryComplete();
             }
         }
     }
@@ -865,18 +918,29 @@
 
         @Override
         public void compute() {
-            Spliterator<T> split ;
-            if (!AbstractTask.suggestSplit(helper, spliterator, targetSize) || ((split = spliterator.trySplit()) == null)) {
-                if (offset+length >= Streams.MAX_ARRAY_SIZE)
-                    throw new IllegalArgumentException("Stream size exceeds max array size");
-                helper.into(new DoubleArraySink(array, (int) offset, (int) length), spliterator);
-                tryComplete();
-            }
-            else {
-                setPendingCount(1);
-                long thisSplitSize = split.estimateSize();
-                new DoubleSizedCollectorTask<>(this, split, offset, thisSplitSize).fork();
-                new DoubleSizedCollectorTask<>(this, spliterator, offset + thisSplitSize, length - thisSplitSize).compute();
+            doCompute(this);
+        }
+
+        private static <T> void doCompute(DoubleSizedCollectorTask<T> task) {
+            while (true) {
+                Spliterator<T> leftSplit;
+                if (!AbstractTask.suggestSplit(task.helper, task.spliterator, task.targetSize)
+                    || ((leftSplit = task.spliterator.trySplit()) == null)) {
+                    if (task.offset + task.length >= Streams.MAX_ARRAY_SIZE)
+                        throw new IllegalArgumentException("Stream size exceeds max array size");
+                    task.helper.into(new DoubleArraySink(task.array, (int) task.offset,
+                                                      (int) task.length), task.spliterator);
+                    task.propagateCompletion();
+                    return;
+                }
+                else {
+                    task.setPendingCount(1);
+                    long leftSplitSize = leftSplit.estimateSize();
+                    new DoubleSizedCollectorTask<>(task, leftSplit,
+                                                   task.offset, leftSplitSize).fork();
+                    task = new DoubleSizedCollectorTask<>(task, task.spliterator,
+                                                          task.offset + leftSplitSize, task.length - leftSplitSize);
+                }
             }
         }
     }
@@ -901,22 +965,28 @@
 
         @Override
         public void compute() {
-            if (node.getChildCount() > 0) {
-                setPendingCount(node.getChildCount() - 1);
+            doCompute(this);
+        }
 
-                final DoubleToArrayTask firstTask = new DoubleToArrayTask(this, node.getChild(0), offset);
-                int size = (int) firstTask.node.count();
+        private static void doCompute(DoubleToArrayTask task) {
+            while (true) {
+                if (task.node.getChildCount() == 0) {
+                    task.node.copyInto(task.array, task.offset);
+                    task.propagateCompletion();
+                    return;
+                }
+                else {
+                    task.setPendingCount(task.node.getChildCount() - 1);
 
-                for (int i = 1; i < node.getChildCount(); i++) {
-                    final DoubleToArrayTask task = new DoubleToArrayTask(this, node.getChild(i), offset + size);
-                    size += task.node.count();
-                    task.fork();
+                    int size = 0;
+                    int i = 0;
+                    for (;i < task.node.getChildCount() - 1; i++) {
+                        DoubleToArrayTask leftTask = new DoubleToArrayTask(task, task.node.getChild(i), task.offset + size);
+                        size += leftTask.node.count();
+                        leftTask.fork();
+                    }
+                    task = new DoubleToArrayTask(task, task.node.getChild(i), task.offset + size);
                 }
-                firstTask.compute();
-            }
-            else {
-                node.copyInto(array, offset);
-                tryComplete();
             }
         }
     }