BUG-7464: Optimize LNode.removed()

[yangtools.git] / third-party / triemap / src / main / java / org / opendaylight / yangtools / triemap / ListMap.java

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
index 1522b6611fa72df49272e431b8436408e1f73b80..84e411474ee19c6928d4e2df2df46134f5bb2734 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
@@ -19,6 +19,7 @@ import java.util.AbstractMap.SimpleImmutableEntry;
 import java.util.Iterator;
 import java.util.Map.Entry;
 import java.util.NoSuchElementException;
+import java.util.Optional;
 
 /**
  * Mimic immutable ListMap in Scala
@@ -48,15 +49,31 @@ final class ListMap<K, V> {
         return new ListMap<>(k1, v1, new ListMap<>(k2, v2));
     }
 
+    Optional<Entry<K, V>> maybeSingleton() {
+        return next != null ? Optional.empty() : Optional.of(new SimpleImmutableEntry<>(k, v));
+    }
+
     int size() {
-        return next == null ? 1 : next.size() + 1;
+        int sz = 1;
+        for (ListMap<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
+            sz++;
+        }
+        return sz;
     }
 
-    Option<V> get(final K key) {
+    Optional<V> get(final K key) {
         if (key.equals(k)) {
-            return Option.makeOption(v);
+            return Optional.of(v);
+        }
+
+        // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
+        for (ListMap<K, V> m = next; m != null; m = m.next) {
+            if (key.equals(m.k)) {
+                return Optional.of(m.v);
+            }
         }
-        return next == null ? Option.makeOption() : next.get(key);
+
+        return Optional.empty();
     }
 
     ListMap<K,V> add(final K key, final V value) {
@@ -72,11 +89,18 @@ final class ListMap<K, V> {
     }
 
     private boolean contains(final K key) {
-        if (key.equals(this.k)) {
+        if (key.equals(k)) {
             return true;
         }
 
-        return next != null && next.contains(key);
+        // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
+        for (ListMap<K, V> m = next; m != null; m = m.next) {
+            if (key.equals(m.k)) {
+                return true;
+            }
+        }
+
+        return false;
     }
 
     private ListMap<K, V> remove0(final K key) {