Code Review / yangtools.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | review | tree
raw | inline | side by side
BUG-7464: update INode.GCAS_Complete()
[yangtools.git] / third-party / triemap / src / main / java / org / opendaylight / yangtools / triemap / INode.java
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 b86d4c4152003eaf0c54850f62ef83b5d4c49342..23046ed0e835f5148c6003ce2b14708ee4666ff5 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
@@ -15,10 +15,13 @@
  */
 package org.opendaylight.yangtools.triemap;
 
+import static org.opendaylight.yangtools.triemap.Constants.LEVEL_BITS;
 import static org.opendaylight.yangtools.triemap.LookupResult.RESTART;
 import static org.opendaylight.yangtools.triemap.PresencePredicate.ABSENT;
 import static org.opendaylight.yangtools.triemap.PresencePredicate.PRESENT;
 
+import com.google.common.base.VerifyException;
+import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
 import java.util.Optional;
 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
 
@@ -50,15 +53,12 @@ final class INode<K, V> extends BasicNode {
         return GCAS_Complete(m, ct);
     }
 
-    private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<?, ?> ct) {
-        while (true) {
-            if (m == null) {
-                return null;
-            }
-
+    private MainNode<K, V> GCAS_Complete(final MainNode<K, V> oldmain, final TrieMap<?, ?> ct) {
+        MainNode<K, V> m = oldmain;
+        while (m != null) {
             // complete the GCAS
             final MainNode<K, V> prev = /* READ */ m.READ_PREV();
-            final Gen rdgen = ct.readRoot(true).gen;
+            final INode<?, ?> ctr = ct.readRoot(true);
             if (prev == null) {
                 return m;
             }
@@ -70,7 +70,7 @@ final class INode<K, V> extends BasicNode {
                     return fn.READ_PREV();
                 }
 
-                // Tail recursion: return GCAS_Complete (/* READ */ mainnode, ct);
+                // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
                 m = /* READ */ mainnode;
                 continue;
             }
@@ -83,13 +83,13 @@ final class INode<K, V> extends BasicNode {
             // ==> if `ctr.gen` = `gen` then they are both equal to G.
             // ==> otherwise, we know that either `ctr.gen` > G, `gen` < G,
             // or both
-            if (rdgen == gen && !ct.isReadOnly()) {
+            if (ctr.gen == gen && !ct.isReadOnly()) {
                 // try to commit
                 if (m.CAS_PREV(prev, null)) {
                     return m;
                 }
 
-                // Tail recursion: return GCAS_Complete (m, ct);
+                // Tail recursion: return GCAS_Complete(m, ct);
                 continue;
             }
 
@@ -99,6 +99,8 @@ final class INode<K, V> extends BasicNode {
             // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
             m = /* READ */ mainnode;
         }
+
+        return null;
     }
 
     private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<?, ?> ct) {
@@ -124,9 +126,9 @@ final class INode<K, V> extends BasicNode {
      *
      * @return true if successful, false otherwise
      */
-    boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
+    boolean rec_insert(final K key, final V value, final int hc, final int lev, final INode<K, V> parent,
             final TrieMap<K, V> ct) {
-        return rec_insert(k, v, hc, lev, parent, gen, ct);
+        return rec_insert(key, value, hc, lev, parent, gen, ct);
     }
 
     private boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
@@ -142,16 +144,17 @@ final class INode<K, V> extends BasicNode {
                 final int bmp = cn.bitmap;
                 final int mask = flag - 1;
                 final int pos = Integer.bitCount(bmp & mask);
+
                 if ((bmp & flag) != 0) {
                     // 1a) insert below
                     final BasicNode cnAtPos = cn.array[pos];
                     if (cnAtPos instanceof INode) {
                         final INode<K, V> in = (INode<K, V>) cnAtPos;
                         if (startgen == in.gen) {
-                            return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
+                            return in.rec_insert(k, v, hc, lev + LEVEL_BITS, this, startgen, ct);
                         }
                         if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
-                            // Tail recursion: return rec_insert (k, v, hc, lev, parent, startgen, ct);
+                            // Tail recursion: return rec_insert(k, v, hc, lev, parent, startgen, ct);
                             continue;
                         }
 
@@ -163,30 +166,43 @@ final class INode<K, V> extends BasicNode {
                         }
 
                         final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                        final MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
-                                hc, lev + 5, gen)), gen);
-                        return GCAS (cn, nn, ct);
+                        final MainNode<K, V> nn = rn.updatedAt(pos, inode(
+                            CNode.dual(sn, k, v, hc, lev + LEVEL_BITS, gen)), gen);
+                        return GCAS(cn, nn, ct);
+                    } else {
+                        throw CNode.invalidElement(cnAtPos);
                     }
-                } else {
-                    final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                    final MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
-                    return GCAS (cn, ncnode, ct);
                 }
+
+                final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+                final MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
+                return GCAS(cn, ncnode, ct);
             } else if (m instanceof TNode) {
-                clean(parent, ct, lev - 5);
+                clean(parent, ct, lev - LEVEL_BITS);
                 return false;
             } else if (m instanceof LNode) {
                 final LNode<K, V> ln = (LNode<K, V>) m;
                 final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
                 return entry != null ? replaceln(ln, entry, v, ct) : insertln(ln, k, v, ct);
             } else {
-                throw new IllegalStateException("Unhandled node " + m);
+                throw invalidElement(m);
             }
-
-            throw new RuntimeException ("Should not happen");
         }
     }
 
+    private static VerifyException invalidElement(final BasicNode elem) {
+        throw new VerifyException("An INode can host only a CNode, a TNode or an LNode, not " + elem);
+    }
+
+    @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
+            justification = "Returning null Optional indicates the need to restart.")
+    private Optional<V> insertDual(final TrieMap<K, V> ct, final CNode<K, V> cn, final int pos, final SNode<K, V> sn,
+            final K k, final V v, final int hc, final int lev) {
+        final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+        final MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, k, v, hc, lev + LEVEL_BITS, gen)), gen);
+        return GCAS(cn, nn, ct) ? Optional.empty() : null;
+    }
+
     /**
      * Inserts a new key value pair, given that a specific condition is met.
      *
@@ -203,6 +219,8 @@ final class INode<K, V> extends BasicNode {
         return rec_insertif(k, v, hc, cond, lev, parent, gen, ct);
     }
 
+    @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
+            justification = "Returning null Optional indicates the need to restart.")
     private Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
             final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
         while (true) {
@@ -223,11 +241,11 @@ final class INode<K, V> extends BasicNode {
                     if (cnAtPos instanceof INode) {
                         final INode<K, V> in = (INode<K, V>) cnAtPos;
                         if (startgen == in.gen) {
-                            return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
+                            return in.rec_insertif(k, v, hc, cond, lev + LEVEL_BITS, this, startgen, ct);
                         }
 
                         if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
-                            // Tail recursion: return rec_insertif (k, v, hc, cond, lev, parent, startgen, ct);
+                            // Tail recursion: return rec_insertif(k, v, hc, cond, lev, parent, startgen, ct);
                             continue;
                         }
 
@@ -243,27 +261,13 @@ final class INode<K, V> extends BasicNode {
                                 return null;
                             }
 
-                            final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                            final MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
-                                    new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
-                            if (GCAS(cn, nn, ct)) {
-                                return Optional.empty();
-                            }
-
-                            return null;
+                            return insertDual(ct, cn, pos, sn, k, v, hc, lev);
                         } else if (cond == ABSENT) {
                             if (sn.hc == hc && ct.equal(sn.k, k)) {
                                 return Optional.of(sn.v);
                             }
 
-                            final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                            final MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
-                                new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
-                            if (GCAS(cn, nn, ct)) {
-                                return Optional.empty();
-                            }
-
-                            return null;
+                            return insertDual(ct, cn, pos, sn, k, v, hc, lev);
                         } else if (cond == PRESENT) {
                             if (sn.hc == hc && ct.equal(sn.k, k)) {
                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
@@ -284,10 +288,12 @@ final class INode<K, V> extends BasicNode {
 
                             return Optional.empty();
                         }
+                    } else {
+                        throw CNode.invalidElement(cnAtPos);
                     }
                 } else if (cond == null || cond == ABSENT) {
                     final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                    final CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
+                    final CNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
                     if (GCAS(cn, ncnode, ct)) {
                         return Optional.empty();
                     }
@@ -297,7 +303,7 @@ final class INode<K, V> extends BasicNode {
                     return Optional.empty();
                 }
             } else if (m instanceof TNode) {
-                clean(parent, ct, lev - 5);
+                clean(parent, ct, lev - LEVEL_BITS);
                 return null;
             } else if (m instanceof LNode) {
                 // 3) an l-node
@@ -306,13 +312,13 @@ final class INode<K, V> extends BasicNode {
 
                 if (cond == null) {
                     if (entry != null) {
-                        return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
+                        return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null;
                     }
 
                     return insertln(ln, k, v, ct) ? Optional.empty() : null;
                 } else if (cond == ABSENT) {
                     if (entry != null) {
-                        return Optional.of(entry.value());
+                        return Optional.of(entry.getValue());
                     }
 
                     return insertln(ln, k, v, ct) ? Optional.empty() : null;
@@ -321,19 +327,17 @@ final class INode<K, V> extends BasicNode {
                         return Optional.empty();
                     }
 
-                    return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
+                    return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null;
                 } else {
-                    if (entry == null || !cond.equals(entry.value())) {
+                    if (entry == null || !cond.equals(entry.getValue())) {
                         return Optional.empty();
                     }
 
-                    return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
+                    return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null;
                 }
             } else {
-                throw new IllegalStateException("Unhandled node " + m);
+                throw invalidElement(m);
             }
-
-            throw new RuntimeException("Should never happen");
         }
     }
 
@@ -366,6 +370,7 @@ final class INode<K, V> extends BasicNode {
                 final int idx = (hc >>> lev) & 0x1f;
                 final int flag = 1 << idx;
                 final int bmp = cn.bitmap;
+
                 if ((bmp & flag) == 0) {
                     // 1a) bitmap shows no binding
                     return null;
@@ -377,7 +382,7 @@ final class INode<K, V> extends BasicNode {
                 if (sub instanceof INode) {
                     final INode<K, V> in = (INode<K, V>) sub;
                     if (ct.isReadOnly() || (startgen == in.gen)) {
-                        return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
+                        return in.rec_lookup(k, hc, lev + LEVEL_BITS, this, startgen, ct);
                     }
 
                     if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
@@ -394,6 +399,8 @@ final class INode<K, V> extends BasicNode {
                     }
 
                     return null;
+                } else {
+                    throw CNode.invalidElement(sub);
                 }
             } else if (m instanceof TNode) {
                 // 3) non-live node
@@ -401,12 +408,10 @@ final class INode<K, V> extends BasicNode {
             } else if (m instanceof LNode) {
                 // 5) an l-node
                 final LNodeEntry<K, V> entry = ((LNode<K, V>) m).get(ct.equiv(), k);
-                return entry != null ? entry.value() : null;
+                return entry != null ? entry.getValue() : null;
             } else {
-                throw new IllegalStateException("Unhandled node " + m);
+                throw invalidElement(m);
             }
-
-            throw new RuntimeException ("Should not happen");
         }
     }
 
@@ -420,7 +425,7 @@ final class INode<K, V> extends BasicNode {
             return null;
         }
 
-        clean(parent, ct, lev - 5);
+        clean(parent, ct, lev - LEVEL_BITS);
         return RESTART;
     }
 
@@ -439,6 +444,8 @@ final class INode<K, V> extends BasicNode {
         return rec_remove(k, cond, hc, lev, parent, gen, ct);
     }
 
+    @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
+            justification = "Returning null Optional indicates the need to restart.")
     private Optional<V> rec_remove(final K k, final Object cond, final int hc, final int lev, final INode<K, V> parent,
             final Gen startgen, final TrieMap<K, V> ct) {
         final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
@@ -454,19 +461,18 @@ final class INode<K, V> extends BasicNode {
 
             final int pos = Integer.bitCount(bmp & (flag - 1));
             final BasicNode sub = cn.array[pos];
-            Optional<V> res = null;
+            final Optional<V> res;
             if (sub instanceof INode) {
                 final INode<K, V> in = (INode<K, V>) sub;
                 if (startgen == in.gen) {
-                    res = in.rec_remove(k, cond, hc, lev + 5, this, startgen, ct);
+                    res = in.rec_remove(k, cond, hc, lev + LEVEL_BITS, this, startgen, ct);
                 } else {
-                    if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
+                    if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
                         res = rec_remove(k, cond, hc, lev, parent, startgen, ct);
                     } else {
                         res = null;
                     }
                 }
-
             } else if (sub instanceof SNode) {
                 final SNode<K, V> sn = (SNode<K, V>) sub;
                 if (sn.hc == hc && ct.equal(sn.k, k) && (cond == null || cond.equals(sn.v))) {
@@ -479,6 +485,8 @@ final class INode<K, V> extends BasicNode {
                 } else {
                     res = Optional.empty();
                 }
+            } else {
+                throw CNode.invalidElement(sub);
             }
 
             if (res == null || !res.isPresent()) {
@@ -495,7 +503,7 @@ final class INode<K, V> extends BasicNode {
 
             return res;
         } else if (m instanceof TNode) {
-            clean(parent, ct, lev - 5);
+            clean(parent, ct, lev - LEVEL_BITS);
             return null;
         } else if (m instanceof LNode) {
             final LNode<K, V> ln = (LNode<K, V>) m;
@@ -505,7 +513,7 @@ final class INode<K, V> extends BasicNode {
                 return Optional.empty();
             }
 
-            final V value = entry.value();
+            final V value = entry.getValue();
             if (cond != null && !cond.equals(value)) {
                 // Value does not match
                 return Optional.empty();
@@ -513,7 +521,7 @@ final class INode<K, V> extends BasicNode {
 
             return GCAS(ln, ln.removeChild(entry, hc), ct) ? Optional.of(value) : null;
         } else {
-            throw new IllegalStateException("Unhandled node " + m);
+            throw invalidElement(m);
         }
     }
 
@@ -527,7 +535,7 @@ final class INode<K, V> extends BasicNode {
             }
 
             final CNode<K, V> cn = (CNode<K, V>) pm;
-            final int idx = (hc >>> (lev - 5)) & 0x1f;
+            final int idx = (hc >>> (lev - LEVEL_BITS)) & 0x1f;
             final int bmp = cn.bitmap;
             final int flag = 1 << idx;
             if ((bmp & flag) == 0) {
@@ -540,7 +548,7 @@ final class INode<K, V> extends BasicNode {
             if (sub == this) {
                 if (nonlive instanceof TNode) {
                     final TNode<?, ?> tn = (TNode<?, ?>) nonlive;
-                    final MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - 5);
+                    final MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - LEVEL_BITS);
                     if (!parent.GCAS(cn, ncn, ct)) {
                         if (ct.readRoot().gen == startgen) {
                             // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
@@ -561,8 +569,8 @@ final class INode<K, V> extends BasicNode {
         }
     }
 
-    int cachedSize(final TrieMap<?, ?> ct) {
-        return GCAS_READ(ct).cachedSize(ct);
+    int size(final ImmutableTrieMap<?, ?> ct) {
+        return GCAS_READ(ct).size(ct);
     }
 
     // /* this is a quiescent method! */
@@ -580,4 +588,4 @@ final class INode<K, V> extends BasicNode {
     String string(final int lev) {
         return "INode";
     }
-}
\ No newline at end of file
+}
OpenDaylight YANG Tools