Return-Path: X-Original-To: apmail-jackrabbit-oak-commits-archive@minotaur.apache.org Delivered-To: apmail-jackrabbit-oak-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id BECDD97B0 for ; Thu, 5 Apr 2012 15:16:23 +0000 (UTC) Received: (qmail 15361 invoked by uid 500); 5 Apr 2012 15:16:23 -0000 Delivered-To: apmail-jackrabbit-oak-commits-archive@jackrabbit.apache.org Received: (qmail 15336 invoked by uid 500); 5 Apr 2012 15:16:23 -0000 Mailing-List: contact oak-commits-help@jackrabbit.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: oak-commits@jackrabbit.apache.org Delivered-To: mailing list oak-commits@jackrabbit.apache.org Received: (qmail 15312 invoked by uid 99); 5 Apr 2012 15:16:23 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 05 Apr 2012 15:16:23 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 05 Apr 2012 15:16:19 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id DCDB523888EA; Thu, 5 Apr 2012 15:15:57 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1309895 - in /jackrabbit/oak/trunk/oak-core/src: main/java/org/apache/jackrabbit/oak/kernel/ test/java/org/apache/jackrabbit/oak/kernel/ Date: Thu, 05 Apr 2012 15:15:57 -0000 To: oak-commits@jackrabbit.apache.org From: mduerig@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120405151557.DCDB523888EA@eris.apache.org> Author: mduerig Date: Thu Apr 5 15:15:57 2012 New Revision: 1309895 URL: http://svn.apache.org/viewvc?rev=1309895&view=rev Log: OAK-9: Internal tree builder Remove offset and size parameters from getChildNodes and replace with page wise loading from backend Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/kernel/TransientNodeState.java jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorFuzzTest.java jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorTest.java Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/kernel/TransientNodeState.java URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/kernel/TransientNodeState.java?rev=1309895&r1=1309894&r2=1309895&view=diff ============================================================================== --- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/kernel/TransientNodeState.java (original) +++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/kernel/TransientNodeState.java Thu Apr 5 15:15:57 2012 @@ -25,15 +25,21 @@ import org.apache.commons.collections.it import org.apache.jackrabbit.mk.model.ChildNodeEntry; import org.apache.jackrabbit.mk.model.NodeState; import org.apache.jackrabbit.mk.model.PropertyState; +import org.apache.jackrabbit.oak.kernel.TransientNodeState.Iterators.PagedIterator; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; +import java.util.NoSuchElementException; import java.util.Set; -import static org.apache.jackrabbit.oak.kernel.TransientNodeState.Iterators.*; +import static org.apache.jackrabbit.oak.kernel.TransientNodeState.Iterators.Function1; +import static org.apache.jackrabbit.oak.kernel.TransientNodeState.Iterators.Predicate; +import static org.apache.jackrabbit.oak.kernel.TransientNodeState.Iterators.add; +import static org.apache.jackrabbit.oak.kernel.TransientNodeState.Iterators.filter; +import static org.apache.jackrabbit.oak.kernel.TransientNodeState.Iterators.map; /** * A transient node state represents a node being edited. All edit operations are @@ -286,12 +292,7 @@ public class TransientNodeState { * the returned iterable. * @return An {@code Iterable} for all child node states */ - public Iterable getChildNodes(long offset, int count) { - // Persisted child node states - final Iterable persisted = persistentState == null - ? null - : persistentState.getChildNodeEntries(offset, count); - + public Iterable getChildNodes() { // Copy od removed child node states final Set removed = new HashSet(); removed.addAll(removedNodes); @@ -307,13 +308,12 @@ public class TransientNodeState { @Override public Iterator iterator() { // persisted entries - Iterator nodes = persisted == null - ? Iterators.empty() - : persisted.iterator(); + final Iterator persisted = + getPersistedChildNodeEntries(persistentState); // persisted entries - removed entries Iterator persistedMinusRemovedEntries = - filter(nodes, new Predicate() { + filter(persisted, new Predicate() { @Override public boolean evaluate(ChildNodeEntry entry) { return !removed.contains(entry.getName()); @@ -498,6 +498,30 @@ public class TransientNodeState { return persistentState != null && persistentState.getProperty(name) != null; } + /** + * Iterator over all persisted child node entries of the given + * {@code persistentState}. This iterator reads the child node entries page wise + * with a page size of 1024 items. + * @param persistentState persistent state for retrieving the child node entries from + * @return iterator of child node entries + */ + private static Iterator getPersistedChildNodeEntries( + final NodeState persistentState) { + + if (persistentState == null) { + return Iterators.empty(); + } + else { + return Iterators.flatten( + new PagedIterator(1024) { + @Override + protected Iterator getPage(long pos, int size) { + return persistentState.getChildNodeEntries(pos, size).iterator(); + } + }); + } + } + // TODO: move to a more suitable location static final class Iterators { private Iterators() { } @@ -591,5 +615,108 @@ public class TransientNodeState { public interface Function1 { T apply(S argument); } + + /** + * Flattens an iterator of iterators into a single iterator. + * @param iterators + * @param + * @return + */ + public static Iterator flatten( + final Iterator> iterators) { + + return new Iterator() { + private Iterator current; + + @Override + public boolean hasNext() { + if (current != null && current.hasNext()) { + return true; + } + else if (!iterators.hasNext()) { + return false; + } + else { + do { + current = iterators.next(); + } while (!current.hasNext() && iterators.hasNext()); + return current.hasNext(); + } + } + + @Override + public T next() { + if (!hasNext()) { + throw new NoSuchElementException(); + } + + return current.next(); + } + + @Override + public void remove() { + if (current == null) { + throw new IllegalStateException(); + } + + current.remove(); + } + }; + } + + /** + * A {@code PagedIterator} is an iterator of several pages. A page itself is + * an iterator. The abstract {@code getPage} method is called whenever this + * iterator needs to fetch another page.

+ * + * Lazy flattening (e.g. with {@link Iterators#flatten(java.util.Iterator)} + * results in an iterator which does batch reading from its back end. + * + * @param + */ + public abstract static class PagedIterator + implements Iterator> { + + private final int pageSize; + private long pos; + private Iterator current; + + protected PagedIterator(int pageSize) { + this.pageSize = pageSize; + } + + /** + * @param pos start index + * @param size maximal number of elements + * @return iterator starting at index {@code pos} containing at most {@code size} elements. + */ + protected abstract Iterator getPage(long pos, int size); + + @Override + public boolean hasNext() { + if (current == null) { + current = getPage(pos, pageSize); + pos += pageSize; + } + + return current.hasNext(); + } + + @Override + public Iterator next() { + if (!hasNext()) { + throw new NoSuchElementException(); + } + Iterator e = current; + current = null; + return e; + } + + @Override + public void remove() { + throw new UnsupportedOperationException("remove"); + } + } + } } Modified: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorFuzzTest.java URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorFuzzTest.java?rev=1309895&r1=1309894&r2=1309895&view=diff ============================================================================== --- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorFuzzTest.java (original) +++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorFuzzTest.java Thu Apr 5 15:15:57 2012 @@ -439,7 +439,7 @@ public class KernelNodeStateEditorFuzzTe assertEquals(property1, state2.getProperty(property1.getName())); } - for (TransientNodeState node1 : state1.getChildNodes(0, -1)) { + for (TransientNodeState node1 : state1.getChildNodes()) { checkEqual(node1, state2.getChildNode(node1.getName())); } } Modified: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorTest.java URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorTest.java?rev=1309895&r1=1309894&r2=1309895&view=diff ============================================================================== --- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorTest.java (original) +++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStateEditorTest.java Thu Apr 5 15:15:57 2012 @@ -90,7 +90,7 @@ public class KernelNodeStateEditorTest { public void getNodes() { KernelNodeStateEditor editor = new KernelNodeStateEditor(state); TransientNodeState transientState = editor.getTransientState(); - Iterable nodes = transientState.getChildNodes(0, -1); + Iterable nodes = transientState.getChildNodes(); Set expectedPaths = new HashSet(); Collections.addAll(expectedPaths, "x", "y", "z"); @@ -291,5 +291,26 @@ public class KernelNodeStateEditorTest { transientState.setProperty(new KernelPropertyState("a", value)); assertEquals(4, transientState.getPropertyCount()); } + + @Test + public void largeChildNodeList() { + KernelNodeStateEditor editor = new KernelNodeStateEditor(state); + + editor.addNode("large"); + editor = editor.edit("large"); + for (int c = 0; c < 10000; c++) { + editor.addNode("n" + c); + } + + KernelNodeState newState = editor.mergeInto(microkernel, state); + editor = new KernelNodeStateEditor(newState); + editor = editor.edit("large"); + + int c = 0; + for (TransientNodeState q : editor.getTransientState().getChildNodes()) { + assertEquals("n" + c++, q.getName()); + } + + } }