BUG-7464: Make ListMap obey TrieMap equivalence

Sifting through ListMap needs to have same equality
as the TrieMap it belongs to. Pass down proper equivalence
in all cases.

Change-Id: I614fbf1ed433d35babbf8b63e7cdee58280e356f
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.java
index acb37df8acc5df9afa36d1de91dfc2f98112b563..bc2a4d000a614d96bebbdcce550787f04de5d1a0 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.java
@@ -301,13 +301,13 @@ final class INode<K, V> extends BasicNode {
                 // 3) an l-node
                 final LNode<K, V> ln = (LNode<K, V>) m;
                 if (cond == null) {
-                    final Optional<V> optv = ln.get(k);
+                    final Optional<V> optv = ln.get(ct.equiv(), k);
                     if (insertln(ln, k, v, ct)) {
                         return optv;
                     }
                     return null;
                 } else if (cond == ABSENT) {
-                    final Optional<V> t = ln.get(k);
+                    final Optional<V> t = ln.get(ct.equiv(),k);
                     if (t.isPresent()) {
                         return t;
                     }
@@ -316,7 +316,7 @@ final class INode<K, V> extends BasicNode {
                     }
                     return null;
                 } else if (cond == PRESENT) {
-                    final Optional<V> t = ln.get(k);
+                    final Optional<V> t = ln.get(ct.equiv(),k);
                     if (!t.isPresent()) {
                         return t;
                     }
@@ -325,7 +325,7 @@ final class INode<K, V> extends BasicNode {
                     }
                     return null;
                 } else {
-                    final Optional<V> t = ln.get(k);
+                    final Optional<V> t = ln.get(ct.equiv(),k);
                     if (t.isPresent()) {
                         if (cond.equals(t.get())) {
                             if (insertln(ln, k, v, ct)) {
@@ -349,7 +349,7 @@ final class INode<K, V> extends BasicNode {
     }
 
     private boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
-        return GCAS(ln, ln.addChild(k, v), ct);
+        return GCAS(ln, ln.addChild(ct.equiv(), k, v), ct);
     }
 
     /**
@@ -407,7 +407,7 @@ final class INode<K, V> extends BasicNode {
                 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
             } else if (m instanceof LNode) {
                 // 5) an l-node
-                return ((LNode<K, V>) m).get(k).orElse(null);
+                return ((LNode<K, V>) m).get(ct.equiv(), k).orElse(null);
             } else {
                 throw new IllegalStateException("Unhandled node " + m);
             }
@@ -505,7 +505,7 @@ final class INode<K, V> extends BasicNode {
             return null;
         } else if (m instanceof LNode) {
             final LNode<K, V> ln = (LNode<K, V>) m;
-            final Optional<V> optv = ln.get(k);
+            final Optional<V> optv = ln.get(ct.equiv(), k);
 
             if (!optv.isPresent()) {
                 // Key was not found, hence no modification is needed
@@ -517,7 +517,7 @@ final class INode<K, V> extends BasicNode {
                 return Optional.empty();
             }
 
-            return GCAS(ln, ln.removeChild(k, hc, ct), ct) ? optv : null;
+            return GCAS(ln, ln.removeChild(ct.equiv(), k, hc), ct) ? optv : null;
         } else {
             throw new IllegalStateException("Unhandled node " + m);
         }

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java
index c393357ab8516280966019bf92e87399b323dd9d..17c3c3e74bc1a85608fe58d21ba9ab41ab947ed8 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java
@@ -30,14 +30,14 @@ final class LNode<K, V> extends MainNode<K, V> {
         this(ListMap.map(k1, v1, k2, v2));
     }
 
-    LNode<K, V> addChild(final K k, final V v) {
-        return new LNode<>(listmap.add(k, v));
+    LNode<K, V> addChild(final Equivalence<? super K> equiv, final K k, final V v) {
+        return new LNode<>(listmap.add(equiv, k, v));
     }
 
-    MainNode<K, V> removeChild(final K k, final int hc, final TrieMap<K, V> ct) {
+    MainNode<K, V> removeChild(final Equivalence<? super K> equiv, final K k, final int hc) {
         // We only ever create ListMaps with two or more entries,  and remove them as soon as they reach one element
         // (below), so we cannot observe a null return here.
-        final ListMap<K, V> map = listmap.remove(k);
+        final ListMap<K, V> map = listmap.remove(equiv, k);
         final Optional<Entry<K, V>> maybeKv = map.maybeSingleton();
         if (maybeKv.isPresent()) {
             final Entry<K, V> kv = maybeKv.get();
@@ -48,8 +48,8 @@ final class LNode<K, V> extends MainNode<K, V> {
         return new LNode<>(map);
     }
 
-    Optional<V> get(final K k) {
-        return listmap.get(k);
+    Optional<V> get(final Equivalence<? super K> equiv, final K k) {
+        return listmap.get(equiv, k);
     }
 
     @Override

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 84e411474ee19c6928d4e2df2df46134f5bb2734..b2f1c10af5f02b41934c609fbfe3c286416d6690 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
@@ -61,44 +61,41 @@ final class ListMap<K, V> {
         return sz;
     }
 
-    Optional<V> get(final K key) {
-        if (key.equals(k)) {
-            return Optional.of(v);
-        }
-
+    Optional<V> get(final Equivalence<? super K> equiv, final K 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 Optional.of(m.v);
+        ListMap<K, V> head = this;
+        do {
+            if (equiv.equivalent(head.k, key)) {
+                return Optional.of(head.v);
             }
-        }
+
+            head = head.next;
+        } while (head != null);
 
         return Optional.empty();
     }
 
-    ListMap<K,V> add(final K key, final V value) {
-        return new ListMap<>(key, value, remove(key));
+    ListMap<K,V> add(final Equivalence<? super K> equiv, final K key, final V value) {
+        return new ListMap<>(key, value, remove(equiv, key));
     }
 
-    ListMap<K, V> remove(final K key) {
-         if (!contains(key)) {
+    ListMap<K, V> remove(final Equivalence<? super K> equiv, final K key) {
+         if (!contains(equiv, key)) {
             return this;
         }
 
         return remove0(key);
     }
 
-    private boolean contains(final K key) {
-        if (key.equals(k)) {
-            return true;
-        }
-
+    private boolean contains(final Equivalence<? super K> equiv, final K 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)) {
+        ListMap<K, V> head = this;
+        do {
+            if (equiv.equivalent(head.k, key)) {
                 return true;
             }
-        }
+            head = head.next;
+        } while (head != null);
 
         return false;
     }

diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ListMapTest.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ListMapTest.java
index 6230134d9745f457b50c597226aa24a742dac42b..ffecafd9e9fc2db371e1518d0602b58908abc4f1 100644 (file)
--- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ListMapTest.java
+++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ListMapTest.java
@@ -31,10 +31,10 @@ public class ListMapTest {
 
         // 30K seems to be enough to trigger the problem locally
         for (int i = 3; i < 30000; ++i) {
-            map = map.add(i, Boolean.TRUE);
+            map = map.add(Equivalence.equals(), i, Boolean.TRUE);
         }
 
-        final Optional<Boolean> ret = map.get(0);
+        final Optional<Boolean> ret = map.get(Equivalence.equals(), 0);
         assertFalse(ret.isPresent());
     }