This is an automated email from the ASF dual-hosted git repository. joerghoh pushed a commit to branch OAK-11607-AbstractTree in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git
commit 65e1ac1d3ece278389057c4bcb3570866792f25f Author: Joerg Hoh <[email protected]> AuthorDate: Fri Mar 14 14:46:38 2025 +0100 OAK-11607 for ordered nodetypes read the child node names lazily --- .../tree/impl/OrderedChildnameIterable.java | 118 +++++++++++++++++++++ .../tree/impl/OrderedChildnameIterableTest.java | 47 ++++++++ 2 files changed, 165 insertions(+) diff --git a/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterable.java b/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterable.java new file mode 100644 index 0000000000..916c29bacc --- /dev/null +++ b/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterable.java @@ -0,0 +1,118 @@ +package org.apache.jackrabbit.oak.plugins.tree.impl; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Set; + +/** + * Return the childrenNames in the order defined by the orderedChildren iterator, and merges it + * with the existing children defined by allChildren. + * + * This implementation focuses on being as lazy as possible; especially consuming the + * allChildren iterator can be slow. + */ + +public class OrderedChildnameIterable implements Iterable<String> { + + final OrderedChildnameIterator iter; + + public OrderedChildnameIterable (Iterable<String> orderedChildren, Iterable<String> allChildren) { + iter = new OrderedChildnameIterator(orderedChildren,allChildren); + } + + @Override + public Iterator<String> iterator() { + return iter; + } + + public class OrderedChildnameIterator implements Iterator<String> { + + final Iterator<String> orderedChildren; + final Iterator<String> allChildren; + + private String nextResult; + + // lazily populated by elements from the allChildren iterable + private final Set<String> allChildrenSet = new HashSet<>(); + + private final List<String> nonOrderedChildren = new ArrayList<>(); + private Iterator<String> nonOrderedChildrenIterator = null; + + public OrderedChildnameIterator (Iterable<String> orderedChildren, Iterable<String> allChildren) { + this.orderedChildren = orderedChildren.iterator(); + this.allChildren = allChildren.iterator(); + nextResult = getNextElement(); + } + + String getNextElement() { + String elem = null; + + if (orderedChildren.hasNext()) { + elem = getNextOrderedChild(); + if (elem != null) { + return elem; + } + } + // if the flow comes here, all orderedChildren have already been consumed, and the + // nonOrderedChildren list is no longer changed, so it's safe to create the iterator here + if (nonOrderedChildrenIterator == null) { + nonOrderedChildrenIterator = nonOrderedChildren.iterator(); + } + // return all children which have already been read into the nonOrderedChildren list + if (nonOrderedChildrenIterator.hasNext()) { + return nonOrderedChildrenIterator.next(); + } + // return all children which have not been consumed from the allChildren iterator yet + if (allChildren.hasNext()) { + return allChildren.next(); + } + // all iterators consumed, no children anymore + return null; + } + + /** + * Consume the next element from the orderedChild list + * @return null if no ordered child can be retrieved, otherwise the next ordered child name + */ + String getNextOrderedChild() { + String current = null; + // check that this element is actually present in the allChildren iterable + while (current == null && orderedChildren.hasNext()) { + current = orderedChildren.next(); + if (isOrderedChildPresent(current)) { + return current; + } + } + return null; + } + + boolean isOrderedChildPresent(String orderedChildName) { + // read from the allChildren iterator until it's a hit or exhausted + while (!nonOrderedChildren.contains(orderedChildName) && allChildren.hasNext()) { + nonOrderedChildren.add(allChildren.next()); + } + if (nonOrderedChildren.contains(orderedChildName)) { + // remove it from the list, as it is returned early + nonOrderedChildren.remove(orderedChildName); + return true; + } else { + return false; + } + } + + @Override + public boolean hasNext() { + return nextResult != null; + } + + @Override + public String next() { + String n = nextResult; + nextResult = getNextElement(); + return n; + } + + } +} diff --git a/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterableTest.java b/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterableTest.java new file mode 100644 index 0000000000..f1dc5a9807 --- /dev/null +++ b/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterableTest.java @@ -0,0 +1,47 @@ +package org.apache.jackrabbit.oak.plugins.tree.impl; + +import java.util.ArrayList; +import java.util.List; + +import org.junit.Assert; +import org.junit.Test; + +public class OrderedChildnameIterableTest { + + static final List<String> ALL_CHILDREN = List.of("1","2","3","4","5"); + + List<String> iterableToList(Iterable<String> iter) { + List<String> result = new ArrayList<>(); + iter.iterator().forEachRemaining(result::add); + return result; + } + + @Test + public void noOrderedChildren() { + // all children are returned in their order + OrderedChildnameIterable iterable = new OrderedChildnameIterable(List.of(),ALL_CHILDREN); + Assert.assertEquals(ALL_CHILDREN, iterableToList(iterable)); + } + + @Test + public void orderedChildren() { + // only 2 child nodes ordered, return them up front + OrderedChildnameIterable iterable = new OrderedChildnameIterable(List.of("4","5"),ALL_CHILDREN); + Assert.assertEquals(List.of("4","5","1","2","3"), iterableToList(iterable)); + } + + @Test + public void orderedChildrenWithNonExistingOrderedChild() { + // the ordered list contains a non-existing childname, which is not part of children list + OrderedChildnameIterable iterable = new OrderedChildnameIterable(List.of("4","5","nonexisting"),ALL_CHILDREN); + Assert.assertEquals(List.of("4","5","1","2","3"), iterableToList(iterable)); + } + + @Test + public void onlyOrderedChildrenAvailable() { + // the orderedChildren property is populated, but no children are available + OrderedChildnameIterable iterable = new OrderedChildnameIterable(List.of("1","2"),List.of()); + Assert.assertEquals(List.of(), iterableToList(iterable)); + } + +}
