You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by jo...@apache.org on 2025/03/14 13:46:55 UTC

(jackrabbit-oak) branch OAK-11607-AbstractTree created (now 65e1ac1d3e)

This is an automated email from the ASF dual-hosted git repository.

joerghoh pushed a change to branch OAK-11607-AbstractTree
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git


      at 65e1ac1d3e OAK-11607 for ordered nodetypes read the child node names lazily

This branch includes the following new commits:

     new 65e1ac1d3e OAK-11607 for ordered nodetypes read the child node names lazily

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.



(jackrabbit-oak) 01/01: OAK-11607 for ordered nodetypes read the child node names lazily

Posted by jo...@apache.org.
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 <jh...@adobe.com>
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));
+    }
+
+}