BUG-7464: Add MainNode.trySize()

Having the ability to estimate size will be useful for Spliterators,
add a method for reading the currently-cached value without actually
computing it.

Also rename cachedSize() to size() and make it enforce being called
with an immutable snapshot. For CNodes this allows us to get rid
of atomic access to the size field, as the order of updates and
visibility propagation of size does not matter -- all concurrent
computations will arrive at the same result. The worst that can
happen we spend more time computing computing the value.

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

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 76141ade5ad01b9cece84992b06b9a5b96a744d4..2b3885443032b74da154a6d999785d1d1cc79945 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
@@ -20,20 +20,15 @@ import static org.opendaylight.yangtools.triemap.Constants.LEVEL_BITS;
 
 import com.google.common.base.Verify;
 import java.util.concurrent.ThreadLocalRandom;
-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;
 
+    // Since concurrent computation should lead to same results we can update this field without any synchronization.
     private volatile int csize = NO_SIZE;
 
     private CNode(final Gen gen, final int bitmap, final BasicNode... array) {
@@ -68,20 +63,15 @@ final class CNode<K, V> extends MainNode<K, V> {
         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
-    int cachedSize(final TrieMap<?, ?> 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;
-            }
-        }
+    int trySize() {
+        return csize;
+    }
 
-        return sz;
+    @Override
+    int size(final ImmutableTrieMap<?, ?> ct) {
+        int sz;
+        return (sz = csize) != NO_SIZE ? sz : (csize = computeSize(ct));
     }
 
     // lends itself towards being parallelizable by choosing
@@ -89,7 +79,7 @@ final class CNode<K, V> extends MainNode<K, V> {
     // => if there are concurrent size computations, they start
     // at different positions, so they are more likely to
     // to be independent
-    private int computeSize(final TrieMap<?, ?> ct) {
+    private int computeSize(final ImmutableTrieMap<?, ?> ct) {
         final int len = array.length;
         switch (len) {
             case 0:
@@ -109,11 +99,11 @@ final class CNode<K, V> extends MainNode<K, V> {
         }
     }
 
-    private static int elementSize(final BasicNode elem, final TrieMap<?, ?> ct) {
+    private static int elementSize(final BasicNode elem, final ImmutableTrieMap<?, ?> ct) {
         if (elem instanceof SNode) {
             return 1;
         } else if (elem instanceof INode) {
-            return ((INode<?, ?>) elem).cachedSize(ct);
+            return ((INode<?, ?>) elem).size(ct);
         } else {
             throw new IllegalStateException("Unhandled element " + elem);
         }

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/FailedNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/FailedNode.java
index a2ac9ca90cf8d6b702533c8fefe22c35226ec109..ae292d5721c5d77c87b0dd0e7e2f83950d7ac559 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/FailedNode.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/FailedNode.java
@@ -29,7 +29,12 @@ final class FailedNode<K, V> extends MainNode<K, V> {
     }
 
     @Override
-    int cachedSize(final TrieMap<?, ?> ct) {
+    int trySize() {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    int size(final ImmutableTrieMap<?, ?> ct) {
         throw new UnsupportedOperationException();
     }
 
@@ -37,4 +42,5 @@ final class FailedNode<K, V> extends MainNode<K, V> {
     public String toString() {
         return "FailedNode(" + p + ")";
     }
+
 }
\ No newline at end of file

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 a619894587e0caeaeba8f453537d2c3ccaeae594..e8584cf087a56e534fa7e2a630e48c88330af72f 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
@@ -563,8 +563,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! */

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableTrieMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableTrieMap.java
index 17391cfcfb4ab798c45e3171c923333761e0725e..e6c29b6bdede7d31f2c9f52750c9c38ac77943dd 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableTrieMap.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableTrieMap.java
@@ -105,7 +105,7 @@ public final class ImmutableTrieMap<K, V> extends TrieMap<K, V> {
 
     @Override
     public int size() {
-        return root.cachedSize(this);
+        return root.size(this);
     }
 
     @Override

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 b4a32244466042debb13ed32e0a9019ed5747601..e7905ac4e843e7c99db20d3b05e09e910926d8a3 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
@@ -61,7 +61,12 @@ final class LNode<K, V> extends MainNode<K, V> {
     }
 
     @Override
-    int cachedSize(final TrieMap<?, ?> ct) {
+    int trySize() {
+        return size;
+    }
+
+    @Override
+    int size(final ImmutableTrieMap<?, ?> ct) {
         return size;
     }
 

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MainNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MainNode.java
index ac0af2f417f6daf3c2b5895cf581a657de2b6c99..eb18b7fd7ae27f9dc50eb6b72243bad45845d835 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MainNode.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MainNode.java
@@ -18,6 +18,8 @@ package org.opendaylight.yangtools.triemap;
 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
 
 abstract class MainNode<K, V> extends BasicNode {
+    static final int NO_SIZE = -1;
+
     @SuppressWarnings("rawtypes")
     private static final AtomicReferenceFieldUpdater<MainNode, MainNode> PREV_UPDATER =
         AtomicReferenceFieldUpdater.newUpdater(MainNode.class, MainNode.class, "prev");
@@ -32,7 +34,19 @@ abstract class MainNode<K, V> extends BasicNode {
         this.prev = prev;
     }
 
-    abstract int cachedSize(TrieMap<?, ?> ct);
+    /**
+     * Return the number of entries in this node, or {@link #NO_SIZE} if it is not known.
+     */
+    abstract int trySize();
+
+    /**
+     * Return the number of entries in this node, traversing it if need be. This method should be invoked only
+     * on immutable snapshots.
+     *
+     * @param ct TrieMap reference
+     * @return The actual number of entries.
+     */
+    abstract int size(ImmutableTrieMap<?, ?> ct);
 
     final boolean CAS_PREV(final MainNode<K, V> oldval, final MainNode<K, V> nval) {
         return PREV_UPDATER.compareAndSet(this, oldval, nval);

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TNode.java
index 86afdfa15b451b7c7f9c94f8655a9fe04aca0223..9cdfb974d0b0644a3c7e3be619347a473c6ded57 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TNode.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TNode.java
@@ -41,7 +41,12 @@ final class TNode<K, V> extends MainNode<K, V> implements EntryNode<K, V> {
     }
 
     @Override
-    int cachedSize(final TrieMap<?, ?> ct) {
+    int trySize() {
+        return 1;
+    }
+
+    @Override
+    int size(final ImmutableTrieMap<?, ?> ct) {
         return 1;
     }