changeset 6350:52fe21edb93b

a better spined list implementation.
author mduigou
date Wed, 24 Oct 2012 12:27:58 -0700
parents f6366de3394c
children e4101c3658cc
files src/share/classes/java/util/streams/ops/Nodes.java
diffstat 1 files changed, 340 insertions(+), 174 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/streams/ops/Nodes.java	Wed Oct 24 15:44:14 2012 -0400
+++ b/src/share/classes/java/util/streams/ops/Nodes.java	Wed Oct 24 12:27:58 2012 -0700
@@ -203,9 +203,7 @@
 
         @Override
         public T[] asArray() {
-            T[] array = (T[]) new Object[c.size()];
-            copyInto(array, 0);
-            return array;
+            return (T[]) c.toArray();
         }
 
         // Traversable
@@ -469,7 +467,7 @@
      * @return the node builder.
      */
     public static <T> NodeBuilder<T> makeVariableSizeBuilder() {
-        return new SimpleSpinedNodeBuilder<>();
+        return new SpinedNodeBuilder<>();
     }
 
     private static class FixedNodeBuilder<T> extends ArrayNode<T> implements NodeBuilder.Fixed<T> {
@@ -528,8 +526,6 @@
             }
         }
 
-        //
-
         @Override
         public int hashCode() {
             return Nodes.hashCode(this);
@@ -548,177 +544,91 @@
         }
     }
 
-    private static class SimpleSpinedNodeBuilder<T> implements NodeBuilder<T>, Node<T> {
+    static class SpinedList<T> extends AbstractCollection<T> implements Sized {
 
-        private final static int CHUNKS_SIZE = 32;
-        private final static int CHUNK_SIZE = 1024;
-        private T[][] chunks = (T[][])new Object[CHUNKS_SIZE][];
-        private int size = 0;
-        private int capacity = 0;
+        protected static final int MIN_CHUNK_SIZE_POWER = 4;
+        protected static final int MIN_CHUNK_SIZE = 1 << MIN_CHUNK_SIZE_POWER;
+        protected static final int MAX_CHUNK_SIZE_POWER = 30; // can't be 2 << 31 because array max is 2 << 31 - 8
+        protected static final int MAX_CHUNK_SIZE = 1 << MAX_CHUNK_SIZE_POWER;
+        protected static final int CHUNKS_PER_SIZE_POWER = 2;
+        protected static final int CHUNKS_PER_SIZE = 1 << CHUNKS_PER_SIZE_POWER;
+        protected static final int ADJUSTED_OFFSET = 1 << (MIN_CHUNK_SIZE_POWER + CHUNKS_PER_SIZE_POWER);
+        protected static final int MIN_SPINE_SIZE = 8; // @@@ something with object allocation overhead.
+        protected static final int MAX_SPINE_SIZE = (MAX_CHUNK_SIZE_POWER - MIN_CHUNK_SIZE_POWER + 1) * CHUNKS_PER_SIZE;
 
-        private SimpleSpinedNodeBuilder(int initialSize) {
+        protected T[][] spine = (T[][])new Object[MIN_SPINE_SIZE][];
+        protected int spineIndex = 0;
+        protected T[] chunk = spine[spineIndex] = (T[])new Object[MIN_CHUNK_SIZE];
+        protected int chunkIndex = 0;
+
+        private SpinedList(int initialSize) {
             ensureCapacity(initialSize);
         }
 
-        private SimpleSpinedNodeBuilder() {
-            this(16);
+        private SpinedList() {
+            this(MIN_CHUNK_SIZE);
         }
 
-        private void ensureCapacity(int capacity) {
-            while (this.capacity < capacity) {
-                int chunk = this.capacity / CHUNK_SIZE;
-                if (chunk >= chunks.length) {
-                    chunks = Arrays.copyOf(chunks, chunks.length + CHUNKS_SIZE);
-                }
+        protected final void ensureCapacity(long size) {
+            long adjusted = (Math.max(size, MIN_CHUNK_SIZE) - 1) + ADJUSTED_OFFSET;
+            int log2 = Long.SIZE - 1 - Long.numberOfLeadingZeros(adjusted);
+            int offset = (int) (((1L << (log2 - CHUNKS_PER_SIZE_POWER)) - 1) & adjusted);
+            int subchunk = (int) (adjusted - offset) >>> (log2 - CHUNKS_PER_SIZE_POWER) & (CHUNKS_PER_SIZE - 1);
+            int superchunk = (log2 - MIN_CHUNK_SIZE_POWER - CHUNKS_PER_SIZE_POWER) * CHUNKS_PER_SIZE;
+            int inChunk = superchunk + subchunk;
 
-                chunks[chunk] = (T[])new Object[CHUNK_SIZE];
-                this.capacity += CHUNK_SIZE;
+            if(inChunk > spine.length) {
+                spine = Arrays.copyOf(spine, Math.min(inChunk, MAX_SPINE_SIZE));
             }
         }
 
+        protected static long totalSizeForSpineIndex(int spineIndex) {
+            assert spineIndex >= 0 && spineIndex < MAX_SPINE_SIZE : "index exceeds limit";
+            long base = 1L << (MIN_CHUNK_SIZE_POWER + CHUNKS_PER_SIZE_POWER + ((spineIndex + 1) / CHUNKS_PER_SIZE));
+            long partial = ((spineIndex + 1) % CHUNKS_PER_SIZE) * (long)sizeForSpineIndex(spineIndex);
+
+            return base + partial - ADJUSTED_OFFSET;
+        }
+
+        protected static int sizeForSpineIndex(int spineIndex) {
+            assert spineIndex >= 0 && spineIndex < MAX_SPINE_SIZE : "index exceeds limit";
+            return 1 << (MIN_CHUNK_SIZE_POWER + (spineIndex / CHUNKS_PER_SIZE));
+        }
+
+        // <editor-fold desc="Object">
+
         @Override
-        public Node<T> build() {
-            return this;
+        public boolean equals(Object obj) {
+            if (!(obj instanceof Iterable)) {
+                return false;
+            }
+            return Nodes.equals(this, (Iterable<?>) obj);
         }
 
         @Override
-        public void forEachUpdate(UnaryOperator<T> f) {
-            int finalChunk = size / CHUNK_SIZE;
-            int finalIndex = size % CHUNK_SIZE;
-
-            for (int chunkIndex = 0; chunkIndex < finalChunk; chunkIndex++) {
-                T[] chunk = chunks[chunkIndex];
-                for (int i = 0; i < chunk.length; i++) {
-                    chunk[i] = f.operate(chunk[i]);
-                }
-            }
-
-            if (finalIndex > 0) {
-                // final chunk.
-                T[] partialChunk = chunks[finalChunk];
-                for (int index = 0; index < finalIndex; index++) {
-                    partialChunk[index] = f.operate(partialChunk[index]);
-                }
-            }
+        public int hashCode() {
+            return Nodes.hashCode(this);
         }
 
-        // Node
+        // </editor-fold>
 
-        @Override
-        public Node flatten() {
-            return this;
-        }
-
-        @Override
-        public Spliterator<T> spliterator() {
-            // @@@ Not very efficient
-            return Arrays.spliterator(asArray());
-        }
-
-        @Override
-        public void copyInto(T[] array, int offset) {
-            Objects.requireNonNull(array);
-            // @@@ Not very efficient
-            for (T t : this)
-                array[offset++] = t;
-        }
-
-        @Override
-        public T[] asArray() {
-            T[] result = (T[]) new Object[size];
-
-            int finalChunk = size / CHUNK_SIZE;
-            int finalIndex = size % CHUNK_SIZE;
-            int index = 0;
-            int chunk = 0;
-
-            // full chunks
-            while (chunk < finalChunk) {
-                System.arraycopy(chunks[chunk++], 0, result, index, CHUNK_SIZE);
-                index += CHUNK_SIZE;
-            }
-
-            // final bit.
-            System.arraycopy(chunks[chunk], 0, result, index, finalIndex);
-
-            return result;
-        }
-
-        // Sink
-
-        @Override
-        public void begin(int size) {
-            this.size = 0;
-            if (size >= 0) {
-                ensureCapacity(size);
-            }
-        }
-
-        @Override
-        public void accept(T t) {
-            int chunk = size / CHUNK_SIZE;
-            int inChunk = size % CHUNK_SIZE;
-            if (0 == inChunk) {
-                ensureCapacity(size + 1);
-            }
-
-            chunks[chunk][inChunk] = t;
-            size++;
-        }
-
-        @Override
-        public void end() {
-            // @@@ check begin(size) and size
-        }
-
-        // Sized
-
-        @Override
-        public int size() {
-            return size;
-        }
-
-        @Override
-        public boolean isEmpty() {
-            return size != 0;
-        }
-
-        // Traversable
-
-        @Override
-        public void forEach(Block<? super T> block) {
-            int finalChunk = size / CHUNK_SIZE;
-            int finalIndex = size % CHUNK_SIZE;
-
-            for (int chunk = 0; chunk < finalChunk; chunk++) {
-                for (T t : chunks[chunk]) {
-                    block.apply(t);
-                }
-            }
-
-            if (finalIndex > 0) {
-                // final chunk.
-                T[] partialChunk = chunks[finalChunk];
-                for (int index = 0; index < finalIndex; index++) {
-                    block.apply(partialChunk[index]);
-                }
-            }
-        }
-
-        // Iterable
+        // <editor-fold desc="Iterable">
 
         @Override
         public Iterator<T> iterator() {
-            return new Iterator<T>() {
-                final int finalChunk = size / CHUNK_SIZE;
-                final int finalIndex = size % CHUNK_SIZE;
+            return iterator(0);
+        }
 
-                int chunk = 0;
-                int index = 0;
+        private Iterator<T> iterator(int startChunk) {
+            Iterator<T> result = new Iterator<T>() {
+                int currentChunk = startChunk;
+                int currentIndex = 0;
 
                 @Override
                 public boolean hasNext() {
-                    return chunk < finalChunk || index < finalIndex;
+                    return currentChunk < SpinedList.this.spineIndex ||
+                            (currentChunk == SpinedList.this.spineIndex &&
+                            currentIndex <  SpinedList.this.chunkIndex);
                 }
 
                 @Override
@@ -727,58 +637,314 @@
                         throw new NoSuchElementException();
                     }
 
-                    T result = chunks[chunk][index++];
+                    T result = spine[currentChunk][currentIndex++];
 
-                    if (index == CHUNK_SIZE) {
-                        index = 0;
-                        chunk++;
+                    if (currentIndex == spine[currentChunk].length) {
+                        currentIndex = 0;
+                        currentChunk++;
                     }
 
                     return result;
                 }
             };
+
+            return result;
+        }
+
+        // </editor-fold>
+
+        // <editor-fold desc="Collection">
+
+        @Override
+        public boolean add(T t) {
+            if (chunkIndex == chunk.length) {
+                if (spineIndex + 1 == MAX_SPINE_SIZE) {
+                    throw new IllegalStateException("Unable to expand capacity");
+                }
+
+                spineIndex += 1;
+                if(spineIndex == spine.length) {
+                    spine = Arrays.copyOf(spine, Math.min(spine.length + MIN_SPINE_SIZE, MAX_SPINE_SIZE));
+                }
+
+                if(null == spine[spineIndex]) {
+                    spine[spineIndex] = (T[])new Object[SpinedList.sizeForSpineIndex(spineIndex)];
+                }
+
+                chunk = spine[spineIndex];
+                chunkIndex = 0;
+            }
+
+            chunk[chunkIndex++] = t;
+
+            return true;
+        }
+
+        @Override
+        public void clear() {
+            // clear current values.
+            for(T[] aChunk : spine) {
+                if(null != aChunk) {
+                    Arrays.fill(aChunk, null);
+                } else {
+                    // first null is done.
+                    break;
+                }
+            }
+
+            // reset position.
+            chunk = spine[spineIndex = 0];
+            chunkIndex = 0;
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return (spineIndex == 0) && (chunkIndex == 0);
+        }
+
+        @Override
+        public int size() {
+            return (spineIndex > 0)
+                    ? (int)Math.min(Integer.MAX_VALUE, totalSizeForSpineIndex(spineIndex - 1) + chunkIndex)
+                    : chunkIndex;
+        }
+
+        @Override
+        public Stream<T> stream() {
+            return Streams.stream(this, StreamOpFlags.IS_ORDERED, size());
+        }
+
+        @Override
+        public Stream<T> parallel() {
+            return Streams.parallel(spliterator(), StreamOpFlags.IS_ORDERED);
+        }
+
+        // </editor-fold>
+
+        // <editor-fold desc="List">
+
+//        @Override
+//        public T get(int index) {
+//            long adjusted = index + ADJUSTED_OFFSET;
+//            int log2 = Long.SIZE - 1 - Long.numberOfLeadingZeros(adjusted);
+//            int offset = (int) (((1L << (log2 - CHUNKS_PER_SIZE_POWER)) - 1) & adjusted);
+//            int subchunk = (int) (adjusted - offset) >>> (log2 - CHUNKS_PER_SIZE_POWER) & (CHUNKS_PER_SIZE - 1);
+//            int superchunk = (log2 - MIN_CHUNK_SIZE_POWER - CHUNKS_PER_SIZE_POWER) * CHUNKS_PER_SIZE;
+//            int inChunk = superchunk + subchunk;
+//
+//            return spine[inChunk][offset];
+//        }
+
+        // </editor-fold>
+
+        protected Spliterator<T> spliterator() {
+            return new Spliterator<T>() {
+                Iterator<T> iterator = null;
+                int spineStart = 0;
+                final Spliterator<T> finalChunkSpliterator = (0 != chunkIndex)
+                        ? Streams.spliterator(chunk, 0, chunkIndex)
+                        : Streams.emptySpliterator();
+
+                @Override
+                public int getSizeIfKnown() {
+                    int result = SpinedList.this.size();
+                    if(spineStart > 0) {
+                        result -= SpinedList.totalSizeForSpineIndex(spineStart - 1);
+                    }
+
+                    return result;
+                }
+
+                @Override
+                public Iterator<T> iterator() {
+                    if (null == iterator) {
+                        if(spineStart < spineIndex) {
+                            iterator = SpinedList.this.iterator(spineStart);
+                        } else {
+                            iterator = finalChunkSpliterator.iterator();
+                        }
+                    }
+
+                    return iterator;
+                }
+
+                @Override
+                public boolean isPredictableSplits() {
+                    return true;
+                }
+
+                @Override
+                public int getNaturalSplits() {
+                    return (null == iterator)
+                            ? spineIndex - spineStart + finalChunkSpliterator.getNaturalSplits()
+                            : 0;
+                }
+
+                @Override
+                public Spliterator<T> split() {
+                    if (null != iterator) {
+                        throw new IllegalStateException("split after starting traversal");
+                    }
+                    if (spineStart < spineIndex) {
+                        return Arrays.spliterator(spine[spineStart++]);
+                    } else {
+                        return finalChunkSpliterator.split();
+                    }
+                }
+            };
+        }
+   }
+
+    private static class SpinedNodeBuilder<T> extends SpinedList<T> implements Node<T>, NodeBuilder<T> {
+
+        private boolean building = false;
+
+        @Override
+        public Stream<T> stream() {
+            assert !building : "during building";
+            return super.stream();
+        }
+
+        @Override
+        public Stream<T> parallel() {
+            assert !building : "during building";
+            return super.parallel();
+        }
+
+        public Collection<T> asCollection() {
+            assert !building : "during building";
+            return this;
+        }
+
+        protected Iterator<T> iterator(int startChunk) {
+            assert !building : "during building";
+            return super.iterator(startChunk);
+        }
+
+        @Override
+        public Spliterator<T> spliterator() {
+            assert !building : "during building";
+            return super.spliterator();
+        }
+
+        @Override
+        public void forEach(Block<? super T> block) {
+            // completed chunks
+            for (int eachChunk = 0; eachChunk < spineIndex; eachChunk++) {
+                for (T t : spine[eachChunk]) {
+                    block.apply(t);
+                }
+            }
+
+            // current chunk
+            for (int index = 0; index < chunkIndex; index++) {
+                block.apply(chunk[index]);
+            }
+        }
+
+        @Override
+        public void forEachUpdate(UnaryOperator<T> f) {
+            for (int eachChunk = 0; eachChunk <= spineIndex; eachChunk++) {
+                T[] aChunk = spine[eachChunk];
+                int bounds = (eachChunk != spineIndex) ? aChunk.length : chunkIndex;
+                for (int element = 0; element < bounds; element++) {
+                    aChunk[element] = f.operate(aChunk[element]);
+                }
+            }
         }
 
         //
-
         @Override
-        public int hashCode() {
-            return Nodes.hashCode(this);
+        public void begin(int size) {
+            assert !building : "was already building";
+            building = true;
+            clear();
+            ensureCapacity(size);
         }
 
         @Override
-        public boolean equals(Object obj) {
-            if (!(obj instanceof NodeBuilder))
-                return false;
-            return Nodes.equals(this, (NodeBuilder) obj);
+        public void accept(T t) {
+            assert building : "not building";
+            add(t);
         }
 
         @Override
-        public String toString() {
-            return String.format("SimpleSpinedNodeBuilder[%s]", Arrays.toString(asArray()));
+        public void end() {
+            assert building : "was not building";
+            building = false;
+            // @@@ check begin(size) and size
+        }
+
+        @Override
+        public void copyInto(T[] array, int offset) {
+            assert !building : "during building";
+            int finalOffset = offset + size();
+            if (finalOffset > array.length || finalOffset < offset) {
+                throw new IndexOutOfBoundsException("does not fit");
+            }
+
+            // full chunks
+            for (int eachChunk = 0; eachChunk < spineIndex; eachChunk++) {
+                T[] aChunk = spine[eachChunk];
+                System.arraycopy(aChunk, 0, array, offset, aChunk.length);
+                offset += aChunk.length;
+            }
+
+            // final bit.
+            System.arraycopy(spine[spineIndex], 0, array, offset, chunkIndex);
+        }
+
+        @Override
+        public T[] asArray() {
+            assert !building : "during building";
+            T[] result = (T[]) new Object[size()]; // will fail for size == MAX_VALUE
+
+            copyInto(result, 0);
+
+            return result;
+        }
+
+        @Override
+        public Node<T> build() {
+            assert !building : "during building";
+            return this;
+        }
+
+        @Override
+        public Node flatten() {
+            return this;
         }
     }
 
-    private static boolean equals(NodeBuilder a, NodeBuilder b) {
-        if (a.size() != b.size())
-            return false;
+    private static boolean equals(Iterable<?> a, Iterable<?> b) {
+        Objects.requireNonNull(a);
+        Objects.requireNonNull(b);
+
+        if(a instanceof Sized && b instanceof Sized) {
+            if ( ((Sized) a).size() != ((Sized) b).size()) {
+                return false;
+            }
+        }
+
         Iterator it1 = a.iterator();
         Iterator it2 = b.iterator();
-        while (it1.hasNext()) {
+        while (it1.hasNext() && it2.hasNext()) {
             Object x1 = it1.next();
             Object x2 = it2.next();
-            if (!x1.equals(x2))
+
+            if (!Objects.equals(x1, x2)) {
                 return false;
+            }
         }
-        return true;
+
+        return !(it1.hasNext() || it2.hasNext());
     }
 
-    private static <T> int hashCode(NodeBuilder<T> sb) {
+    private static <T> int hashCode(Iterable<T> it) {
         int h = 0;
-        for (T t : sb) {
+        for (T t : it) {
             h = 31 * h + Objects.hashCode(t);
         }
         return h;
     }
-
 }