Mercurial > hg > openjdk > lambda > jdk

changeset 7539:eadbf7bcb6f8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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, 174 insertions(+), 104 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);
-
-                final ToArrayTask<T> firstTask = new ToArrayTask<>(this, node.getChild(0), offset);
-                int size = (int) firstTask.node.count();
+            doCompute(this);
+        }
 
-                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();
+        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;
                 }
-                firstTask.compute();
-            } else {
-                node.copyInto(array, offset);
-                tryComplete();
+                else {
+                    task.setPendingCount(task.node.getChildCount() - 1);
+
+                    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);
+                }
             }
         }
     }
@@ -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);
-
-                final IntToArrayTask firstTask = new IntToArrayTask(this, node.getChild(0), offset);
-                int size = (int) firstTask.node.count();
+            doCompute(this);
+        }
 
-                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();
+        private static void doCompute(IntToArrayTask task) {
+            while (true) {
+                if (task.node.getChildCount() == 0) {
+                    task.node.copyInto(task.array, task.offset);
+                    task.propagateCompletion();
+                    return;
                 }
-                firstTask.compute();
-            }
-            else {
-                node.copyInto(array, offset);
-                tryComplete();
+                else {
+                    task.setPendingCount(task.node.getChildCount() - 1);
+
+                    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);
+                }
             }
         }
     }
@@ -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);
-
-                final LongToArrayTask firstTask = new LongToArrayTask(this, node.getChild(0), offset);
-                int size = (int) firstTask.node.count();
+            doCompute(this);
+        }
 
-                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();
+        private static void doCompute(LongToArrayTask task) {
+            while (true) {
+                if (task.node.getChildCount() == 0) {
+                    task.node.copyInto(task.array, task.offset);
+                    task.propagateCompletion();
+                    return;
                 }
-                firstTask.compute();
-            }
-            else {
-                node.copyInto(array, offset);
-                tryComplete();
+                else {
+                    task.setPendingCount(task.node.getChildCount() - 1);
+
+                    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);
+                }
             }
         }
     }
@@ -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);
-
-                final DoubleToArrayTask firstTask = new DoubleToArrayTask(this, node.getChild(0), offset);
-                int size = (int) firstTask.node.count();
+            doCompute(this);
+        }
 
-                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();
+        private static void doCompute(DoubleToArrayTask task) {
+            while (true) {
+                if (task.node.getChildCount() == 0) {
+                    task.node.copyInto(task.array, task.offset);
+                    task.propagateCompletion();
+                    return;
                 }
-                firstTask.compute();
-            }
-            else {
-                node.copyInto(array, offset);
-                tryComplete();
+                else {
+                    task.setPendingCount(task.node.getChildCount() - 1);
+
+                    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);
+                }
             }
         }
     }