BUG-7464: Refactor KVNode

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

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java
index de389bb1b75699dfe6f62a5c11c59169da992cd2..ba6109eea76de4900e364390c00ec2a59766b428 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java
@@ -15,31 +15,64 @@
  */
 package org.opendaylight.yangtools.triemap;
 
-final class CNode<K, V> extends CNodeBase<K, V> {
+import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
+
+final class CNode<K, V> extends MainNode<K, V> {
+    @SuppressWarnings("rawtypes")
+    private static final AtomicIntegerFieldUpdater<CNode> CSIZE_UPDATER = AtomicIntegerFieldUpdater.newUpdater(
+        CNode.class, "csize");
+
+    private static final BasicNode[] EMPTY_ARRAY = new BasicNode[0];
+    private static final int NO_SIZE = -1;
 
     final int bitmap;
     final BasicNode[] array;
     final Gen gen;
 
-    CNode(final int bitmap, final BasicNode[] array, final Gen gen) {
+    private volatile int csize = NO_SIZE;
+
+    private CNode(final Gen gen, final int bitmap, final BasicNode... array) {
         this.bitmap = bitmap;
         this.array = array;
         this.gen = gen;
     }
 
+    CNode(final Gen gen) {
+        this(gen, 0, EMPTY_ARRAY);
+    }
+
+    static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
+            final int lev, final Gen gen) {
+        if (lev >= 35) {
+            return new LNode<>(x.k, x.v, y.k, y.v);
+        }
+
+        final int xidx = (xhc >>> lev) & 0x1f;
+        final int yidx = (yhc >>> lev) & 0x1f;
+        final int bmp = (1 << xidx) | (1 << yidx);
+
+        if (xidx == yidx) {
+            INode<K, V> subinode = new INode<>(gen, dual(x, xhc, y, yhc, lev + 5, gen));
+            return new CNode<>(gen, bmp, subinode);
+        }
+
+        return xidx < yidx ? new CNode<>(gen, bmp, x, y) : new CNode<>(gen, bmp, y, x);
+    }
+
     // this should only be called from within read-only snapshots
     @Override
-    public int cachedSize(final Object ct) {
-        final int currsz = READ_SIZE();
-        if (currsz != -1) {
-            return currsz;
+    int cachedSize(final TrieMap<K, V> ct) {
+        int sz = csize;
+        if (sz == NO_SIZE) {
+            // We have not computed the size yet, do that now
+            sz = computeSize(ct);
+            if (!CSIZE_UPDATER.compareAndSet(this, NO_SIZE, sz)) {
+                // We have been pre-empted by some else: read the result
+                sz = csize;
+            }
         }
 
-        final int sz = computeSize((TrieMap<K, V>) ct);
-        while (READ_SIZE () == -1) {
-            CAS_SIZE (-1, sz);
-        }
-        return READ_SIZE ();
+        return sz;
     }
 
     // lends itself towards being parallelizable by choosing
@@ -64,7 +97,7 @@ final class CNode<K, V> extends CNodeBase<K, V> {
             if (elem instanceof SNode) {
                 sz += 1;
             } else if (elem instanceof INode) {
-                sz += ((INode<K, V>) elem).cachedSize (ct);
+                sz += ((INode<K, V>) elem).cachedSize(ct);
             }
             i += 1;
         }
@@ -76,7 +109,7 @@ final class CNode<K, V> extends CNodeBase<K, V> {
         BasicNode[] narr = new BasicNode[len];
         System.arraycopy(array, 0, narr, 0, len);
         narr[pos] = nn;
-        return new CNode<>(bitmap, narr, gen);
+        return new CNode<>(gen, bitmap, narr);
     }
 
     CNode<K, V> removedAt(final int pos, final int flag, final Gen gen) {
@@ -85,7 +118,7 @@ final class CNode<K, V> extends CNodeBase<K, V> {
         BasicNode[] narr = new BasicNode[len - 1];
         System.arraycopy(arr, 0, narr, 0, pos);
         System.arraycopy(arr, pos + 1, narr, pos, len - pos - 1);
-        return new CNode<>(bitmap ^ flag, narr, gen);
+        return new CNode<>(gen, bitmap ^ flag, narr);
     }
 
     CNode<K, V> insertedAt(final int pos, final int flag, final BasicNode nn, final Gen gen) {
@@ -95,7 +128,7 @@ final class CNode<K, V> extends CNodeBase<K, V> {
         System.arraycopy(array, 0, narr, 0, pos);
         narr [pos] = nn;
         System.arraycopy(array, pos, narr, pos + 1, len - pos);
-        return new CNode<>(bmp | flag, narr, gen);
+        return new CNode<>(gen, bmp | flag, narr);
     }
 
     /**
@@ -112,12 +145,12 @@ final class CNode<K, V> extends CNodeBase<K, V> {
             if (elem instanceof INode) {
                 INode<K, V> in = (INode<K, V>) elem;
                 narr [i] = in.copyToGen(ngen, ct);
-            } else if (elem instanceof BasicNode) {
+            } else if (elem != null) {
                 narr [i] = elem;
             }
             i += 1;
         }
-        return new CNode<>(bitmap, narr, ngen);
+        return new CNode<>(ngen, bitmap, narr);
     }
 
     private BasicNode resurrect(final INode<K, V> inode, final Object inodemain) {
@@ -131,15 +164,14 @@ final class CNode<K, V> extends CNodeBase<K, V> {
 
     MainNode<K, V> toContracted(final int lev) {
         if (array.length == 1 && lev > 0) {
-            if (array [0] instanceof SNode) {
-                SNode<K, V> sn = (SNode<K, V>) array[0];
+            if (array[0] instanceof SNode) {
+                final SNode<K, V> sn = (SNode<K, V>) array[0];
                 return sn.copyTombed();
-            } else {
-                return this;
             }
-        } else {
             return this;
         }
+
+        return this;
     }
 
     // - if the branching factor is 1 for this CNode, and the child
@@ -166,7 +198,7 @@ final class CNode<K, V> extends CNodeBase<K, V> {
             i += 1;
         }
 
-        return new CNode<K, V> (bmp, tmparray, gen).toContracted (lev);
+        return new CNode<K, V>(gen, bmp, tmparray).toContracted(lev);
     }
 
     @Override
@@ -207,27 +239,4 @@ final class CNode<K, V> extends CNodeBase<K, V> {
         // elems.sorted.mkString(", "))
         return "CNode";
     }
-
-    static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
-            final int lev, final Gen gen) {
-        if (lev < 35) {
-            int xidx = (xhc >>> lev) & 0x1f;
-            int yidx = (yhc >>> lev) & 0x1f;
-            int bmp = (1 << xidx) | (1 << yidx);
-
-            if (xidx == yidx) {
-                INode<K, V> subinode = new INode<>(gen);// (TrieMap.inodeupdater)
-                subinode.mainnode = dual (x, xhc, y, yhc, lev + 5, gen);
-                return new CNode<>(bmp, new BasicNode[] { subinode }, gen);
-            } else {
-                if (xidx < yidx) {
-                    return new CNode<>(bmp, new BasicNode[] { x, y }, gen);
-                } else {
-                    return new CNode<>(bmp, new BasicNode[] { y, x }, gen);
-                }
-            }
-        } else {
-            return new LNode<>(x.k, x.v, y.k, y.v);
-        }
-    }
 }