Do not use recursion in InMemoryDataTreeModification.ready()

This patch reworks the logic to eliminate the recursion in
ModifiedNode.seal(), opting for state-tracking class and simple loops.

Change-Id: I42ab781d84e6ebaccc3ff18c3bca6cebcff4573c
Signed-off-by: Robert Varga <rovarga@cisco.com>

diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/AbstractReadyIterator.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/AbstractReadyIterator.java
new file mode 100644 (file)
index 0000000..5591192
--- /dev/null
+++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/AbstractReadyIterator.java
@@ -0,0 +1,90 @@
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.yangtools.yang.data.impl.schema.tree;
+
+import com.google.common.base.Preconditions;
+import java.util.Collection;
+import java.util.Iterator;
+
+abstract class AbstractReadyIterator {
+    final Iterator<ModifiedNode> children;
+    final ModifiedNode node;
+
+    private AbstractReadyIterator(final ModifiedNode node, final Iterator<ModifiedNode> children) {
+        this.children = Preconditions.checkNotNull(children);
+        this.node = Preconditions.checkNotNull(node);
+    }
+
+    static AbstractReadyIterator create(final ModifiedNode root) {
+        return new RootReadyIterator(root, root.getChildren().iterator());
+    }
+
+    final AbstractReadyIterator process() {
+        // Walk all child nodes and remove any children which have not
+        // been modified. If a child
+        while (children.hasNext()) {
+            final ModifiedNode child = children.next();
+            final Collection<ModifiedNode> grandChildren = child.getChildren();
+            if (grandChildren.isEmpty()) {
+                child.seal();
+                if (child.getOperation() == LogicalOperation.NONE) {
+                    children.remove();
+                }
+            } else {
+                return new NestedReadyIterator(this, child, grandChildren.iterator());
+            }
+        }
+
+        node.seal();
+
+        // Remove from parent if we have one and this is a no-op
+        if (node.getOperation() == LogicalOperation.NONE) {
+            removeFromParent();
+        }
+        return getParent();
+    }
+
+    abstract AbstractReadyIterator getParent();
+    abstract void removeFromParent();
+
+    private static final class NestedReadyIterator extends AbstractReadyIterator {
+        private final AbstractReadyIterator parent;
+
+        private NestedReadyIterator(final AbstractReadyIterator parent, final ModifiedNode node, final Iterator<ModifiedNode> children) {
+            super(node, children);
+            this.parent = Preconditions.checkNotNull(parent);
+        }
+
+        @Override
+        AbstractReadyIterator getParent() {
+            return parent;
+        }
+
+        @Override
+        void removeFromParent() {
+            parent.children.remove();
+        }
+    }
+
+    private static final class RootReadyIterator extends AbstractReadyIterator {
+        private RootReadyIterator(final ModifiedNode node, final Iterator<ModifiedNode> children) {
+            super(node, children);
+        }
+
+        @Override
+        AbstractReadyIterator getParent() {
+            return null;
+        }
+
+        @Override
+        void removeFromParent() {
+            // No-op, since root node cannot be removed
+        }
+    }
+
+}
\ No newline at end of file

diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/InMemoryDataTreeModification.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/InMemoryDataTreeModification.java
index 2dda1b3f654fc38527d6849b674e6315f6540bad..f86c71249bc53b20f2b3a5586cc16b49302c58cb 100644 (file)
--- a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/InMemoryDataTreeModification.java
+++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/InMemoryDataTreeModification.java
@@ -148,7 +148,7 @@ final class InMemoryDataTreeModification implements DataTreeModification {
         ModifiedNode modification = rootNode;
 
         int i = 1;
-        for(PathArgument pathArg : path.getPathArguments()) {
+        for (PathArgument pathArg : path.getPathArguments()) {
             Optional<ModificationApplyOperation> potential = operation.getChild(pathArg);
             if (!potential.isPresent()) {
                 throw new IllegalArgumentException(String.format("Child %s is not present in schema tree.",
@@ -163,14 +163,6 @@ final class InMemoryDataTreeModification implements DataTreeModification {
         return OperationWithModification.from(operation, modification);
     }
 
-    @Override
-    public void ready() {
-        final boolean wasRunning = UPDATER.compareAndSet(this, 0, 1);
-        Preconditions.checkState(wasRunning, "Attempted to seal an already-sealed Data Tree.");
-
-        rootNode.seal();
-    }
-
     private void checkSealed() {
         Preconditions.checkState(sealed == 0, "Data Tree is sealed. No further modifications allowed.");
     }
@@ -248,4 +240,16 @@ final class InMemoryDataTreeModification implements DataTreeModification {
             applyNode(cursor, child);
         }
     }
+
+    @Override
+    public void ready() {
+        final boolean wasRunning = UPDATER.compareAndSet(this, 0, 1);
+        Preconditions.checkState(wasRunning, "Attempted to seal an already-sealed Data Tree.");
+
+        AbstractReadyIterator current = AbstractReadyIterator.create(rootNode);
+        do {
+            current = current.process();
+        } while (current != null);
+    }
+
 }

diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/ModifiedNode.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/ModifiedNode.java
index dbb1f419207553fff84da39f3bf5cea54e21634e..cdd5de01db4fda3a67df0404b7dddc8c7032a958 100644 (file)
--- a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/ModifiedNode.java
+++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/ModifiedNode.java
@@ -13,7 +13,6 @@ import com.google.common.base.Predicate;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
-import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.Map;
 import javax.annotation.Nonnull;
@@ -233,24 +232,11 @@ final class ModifiedNode extends NodeModification implements StoreTreeNode<Modif
     }
 
     /**
-     * Seal the modification node and prune any children which has not been
-     * modified.
+     * Seal the modification node.
      */
     void seal() {
         clearSnapshot();
 
-        // Walk all child nodes and remove any children which have not
-        // been modified.
-        final Iterator<ModifiedNode> it = children.values().iterator();
-        while (it.hasNext()) {
-            final ModifiedNode child = it.next();
-            child.seal();
-
-            if (child.operation == LogicalOperation.NONE) {
-                it.remove();
-            }
-        }
-
         // A TOUCH node without any children is a no-op
         if (operation == LogicalOperation.TOUCH && children.isEmpty()) {
             updateOperationType(LogicalOperation.NONE);