Remove NormalizedNodePruner.SimpleStack 34/81234/2
authorRobert Varga <robert.varga@pantheon.tech>
Wed, 27 Mar 2019 22:51:57 +0000 (23:51 +0100)
committerRobert Varga <robert.varga@pantheon.tech>
Wed, 27 Mar 2019 23:02:06 +0000 (00:02 +0100)
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.

Change-Id: Ie59e2fb47f841e4e5fc08c3ab7e164ad0cb368ad
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>
opendaylight/md-sal/sal-clustering-commons/src/main/java/org/opendaylight/controller/cluster/datastore/node/utils/transformer/NormalizedNodePruner.java

index 1577f09..ecbaf1b 100644 (file)
@@ -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();
-        }
-    }
 }

©2013 OpenDaylight, A Linux Foundation Collaborative Project. All Rights Reserved.
OpenDaylight is a registered trademark of The OpenDaylight Project, Inc.
Linux Foundation and OpenDaylight are registered trademarks of the Linux Foundation.
Linux is a registered trademark of Linus Torvalds.