Remove NormalizedNodePruner.SimpleStack

This custom implementation is highly inefficient, because:
1) peek/pop operations perform get(int) and remove(int) operations
   on ArrayList, which are highly inefficient O(N)
2) it allocates an object for each entry

Replace this class with a stock Deque, which takes care of the first
problem, as push/pop/peek are amortized O(1).

For implementation use an ArrayDeque, which takes care of the second
problem, as stack entries are reused.

JIRA: CONTROLLER-1887
Change-Id: Ie59e2fb47f841e4e5fc08c3ab7e164ad0cb368ad
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>
(cherry picked from commit 8e3fb7b97f23fe0aba388b295fbe45d67d21e91c)

diff --git a/opendaylight/md-sal/sal-clustering-commons/src/main/java/org/opendaylight/controller/cluster/datastore/node/utils/transformer/NormalizedNodePruner.java b/opendaylight/md-sal/sal-clustering-commons/src/main/java/org/opendaylight/controller/cluster/datastore/node/utils/transformer/NormalizedNodePruner.java
index 1577f0914706c75a874f8a68c94c6630a0a7fec9..ecbaf1bf582faa454456ed6563cbc411ee4dfc9c 100644 (file)
--- a/opendaylight/md-sal/sal-clustering-commons/src/main/java/org/opendaylight/controller/cluster/datastore/node/utils/transformer/NormalizedNodePruner.java
+++ b/opendaylight/md-sal/sal-clustering-commons/src/main/java/org/opendaylight/controller/cluster/datastore/node/utils/transformer/NormalizedNodePruner.java
@@ -9,11 +9,11 @@ package org.opendaylight.controller.cluster.datastore.node.utils.transformer;
 
 import static com.google.common.base.Preconditions.checkState;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Optional;
 import java.net.URI;
-import java.util.LinkedList;
-import java.util.List;
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.NoSuchElementException;
 import javax.xml.transform.dom.DOMSource;
 import org.opendaylight.yangtools.yang.common.QName;
 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
@@ -43,7 +43,7 @@ public class NormalizedNodePruner implements NormalizedNodeStreamWriter {
 
     public static final URI BASE_NAMESPACE = URI.create("urn:ietf:params:xml:ns:netconf:base:1.0");
 
-    private final SimpleStack<NormalizedNodeBuilderWrapper> stack = new SimpleStack<>();
+    private final Deque<NormalizedNodeBuilderWrapper> stack = new ArrayDeque<>();
     private final DataSchemaContextNode<?> nodePathSchemaNode;
 
     private NormalizedNode<?, ?> normalizedNode;
@@ -191,9 +191,12 @@ public class NormalizedNodePruner implements NormalizedNodeStreamWriter {
     public void endNode() {
         checkNotSealed();
 
-        NormalizedNodeBuilderWrapper child = stack.pop();
-
-        checkState(child != null, "endNode called on an empty stack");
+        final NormalizedNodeBuilderWrapper child;
+        try {
+            child = stack.pop();
+        } catch (NoSuchElementException e) {
+            throw new IllegalStateException("endNode called on an empty stack", e);
+        }
 
         if (!child.getSchema().isPresent()) {
             LOG.debug("Schema not found for {}", child.identifier());
@@ -266,32 +269,4 @@ public class NormalizedNodePruner implements NormalizedNodeStreamWriter {
 
         return schemaNode;
     }
-
-    @VisibleForTesting
-    static class SimpleStack<E> {
-        List<E> stack = new LinkedList<>();
-
-        void push(final E element) {
-            stack.add(element);
-        }
-
-        E pop() {
-            if (size() == 0) {
-                return null;
-            }
-            return stack.remove(stack.size() - 1);
-        }
-
-        E peek() {
-            if (size() == 0) {
-                return null;
-            }
-
-            return stack.get(stack.size() - 1);
-        }
-
-        int size() {
-            return stack.size();
-        }
-    }
 }