BUG-7464: Centralize implementation constants

We have a couple of constants: 5, 7 and 35 used in the codebase,
which are not explained anywhere. These are really derived from
the size of hash (32 bits) and size of bitmap (32 bits).

Centralize their definition in a new utility class, so they can
be documented and referenced uniformly.

Change-Id: I96433c3e72f41fb9bcfa6fa4a9552a7ff9202005
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 c185412ca0c44570879b233a1733bd046dda90b7..76141ade5ad01b9cece84992b06b9a5b96a744d4 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,6 +15,9 @@
  */
 package org.opendaylight.yangtools.triemap;
 
+import static org.opendaylight.yangtools.triemap.Constants.HASH_BITS;
+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;
@@ -50,7 +53,7 @@ final class CNode<K, V> extends MainNode<K, V> {
 
     private 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) {
+        if (lev >= HASH_BITS) {
             return new LNode<>(x.k, x.v, y.k, y.v);
         }
 
@@ -59,7 +62,7 @@ final class CNode<K, V> extends MainNode<K, V> {
         final int bmp = (1 << xidx) | (1 << yidx);
 
         if (xidx == yidx) {
-            return new CNode<>(gen, bmp, new INode<>(gen, dual(x, xhc, y, yhc, lev + 5, gen)));
+            return new CNode<>(gen, bmp, new INode<>(gen, dual(x, xhc, y, yhc, lev + LEVEL_BITS, gen)));
         }
 
         return xidx < yidx ? new CNode<>(gen, bmp, x, y) : new CNode<>(gen, bmp, y, x);

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Constants.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Constants.java
new file mode 100644 (file)
index 0000000..af72936
--- /dev/null
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Constants.java
@@ -0,0 +1,58 @@
+/*
+ * (C) Copyright 2017 Pantheon Technologies, s.r.o. and others.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.opendaylight.yangtools.triemap;
+
+import static com.google.common.base.Verify.verify;
+
+import com.google.common.math.IntMath;
+import java.math.RoundingMode;
+
+/**
+ * Various implementation-specific constants shared across classes.
+ *
+ * @author Robert Varga
+ */
+final class Constants {
+    private Constants() {
+        throw new UnsupportedOperationException();
+    }
+
+    /**
+     * Size of the hash function, in bits.
+     */
+    static final int HASH_BITS = Integer.SIZE;
+
+    /**
+     * Size of the CNode bitmap, in bits.
+     */
+    static final int BITMAP_BITS = Integer.SIZE;
+
+    /**
+     * Number of hash bits consumed in each CNode level.
+     */
+    static final int LEVEL_BITS = 5;
+    static {
+        verify(LEVEL_BITS == IntMath.log2(BITMAP_BITS, RoundingMode.UNNECESSARY));
+    }
+
+    /**
+     * Maximum depth of a TrieMap.
+     */
+    static final int MAX_DEPTH = 7;
+    static {
+        verify(MAX_DEPTH == IntMath.divide(HASH_BITS, LEVEL_BITS, RoundingMode.CEILING));
+    }
+}

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 65e22fd6bd4a443ff817e8061a23a4c08e6ace24..a619894587e0caeaeba8f453537d2c3ccaeae594 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,6 +15,7 @@
  */
 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;
@@ -150,7 +151,7 @@ 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_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);
@@ -165,7 +166,7 @@ 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, k, v, hc, lev + 5, gen)), gen);
+                        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 {
@@ -174,7 +175,7 @@ final class INode<K, V> extends BasicNode {
                     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;
@@ -209,7 +210,7 @@ final class INode<K, V> extends BasicNode {
     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 + 5, gen)), gen);
+        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;
     }
 
@@ -235,7 +236,7 @@ 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)) {
@@ -295,7 +296,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
@@ -376,7 +377,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)) {
@@ -419,7 +420,7 @@ final class INode<K, V> extends BasicNode {
             return null;
         }
 
-        clean(parent, ct, lev - 5);
+        clean(parent, ct, lev - LEVEL_BITS);
         return RESTART;
     }
 
@@ -459,7 +460,7 @@ final class INode<K, V> extends BasicNode {
             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)) {
                         res = rec_remove(k, cond, hc, lev, parent, startgen, ct);
@@ -496,7 +497,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;
@@ -528,7 +529,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) {
@@ -541,7 +542,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);

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java
index 08b62e78422371db3ae6bbbc0416588987dd7772..39479d62c867e19ea9c2d0fe64cdc9abc861e022 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java
@@ -16,6 +16,7 @@
 package org.opendaylight.yangtools.triemap;
 
 import static com.google.common.base.Preconditions.checkState;
+import static org.opendaylight.yangtools.triemap.Constants.MAX_DEPTH;
 
 import java.util.ArrayList;
 import java.util.Iterator;
@@ -27,8 +28,8 @@ class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
     private int level;
     protected TrieMap<K, V> ct;
     private final boolean mustInit;
-    private final BasicNode[][] stack = new BasicNode[7][];
-    private final int[] stackpos = new int[7];
+    private final BasicNode[][] stack = new BasicNode[MAX_DEPTH][];
+    private final int[] stackpos = new int[MAX_DEPTH];
     private int depth = -1;
     private Iterator<Entry<K, V>> subiter = null;
     private EntryNode<K, V> current = null;