{C,I}NodeBase are just field holders for their sole subclasses.
This arrangement comes from Scala, where the Base classes are implemented
in Java and the rest of the code is in Scala.
Remove both base classes by inlining the fields into CNode/INode.
Change-Id: I349f1e1eeeb4301a1d6175ca5e16e7127ae1b540
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>
*/
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;
+ private volatile int csize = NO_SIZE;
+
private CNode(final Gen gen, final int bitmap, final BasicNode... array) {
this.bitmap = bitmap;
this.array = array;
// this should only be called from within read-only snapshots
@Override
int cachedSize(final TrieMap<K, V> ct) {
- final int currsz = READ_SIZE();
- if (currsz != -1) {
- return currsz;
+ 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(ct);
- while (READ_SIZE () == -1) {
- CAS_SIZE (-1, sz);
- }
- return READ_SIZE ();
+ return sz;
}
// lends itself towards being parallelizable by choosing
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;
}
+++ /dev/null
-/*
- * (C) Copyright 2016 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 java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
-
-abstract class CNodeBase<K, V> extends MainNode<K, V> {
- @SuppressWarnings("rawtypes")
- private static final AtomicIntegerFieldUpdater<CNodeBase> CSIZE_UPDATER =
- AtomicIntegerFieldUpdater.newUpdater(CNodeBase.class, "csize");
-
- private volatile int csize = -1;
-
- final boolean CAS_SIZE(final int oldval, final int nval) {
- return CSIZE_UPDATER.compareAndSet(this, oldval, nval);
- }
-
- final int READ_SIZE() {
- return csize;
- }
-}
package org.opendaylight.yangtools.triemap;
import java.util.Optional;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
-final class INode<K, V> extends INodeBase<K, V> {
+final class INode<K, V> extends BasicNode {
static final Object KEY_PRESENT = new Object ();
static final Object KEY_ABSENT = new Object ();
*/
static final Object RESTART = new Object();
- INode(final Gen gen, final MainNode<K, V> bn) {
- super(gen, bn);
+ @SuppressWarnings("rawtypes")
+ private static final AtomicReferenceFieldUpdater<INode, MainNode> MAINNODE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(INode.class, MainNode.class, "mainnode");
+
+ public final Gen gen;
+
+ private volatile MainNode<K, V> mainnode;
+
+ INode(final Gen gen, final MainNode<K, V> mainnode) {
+ this.gen = gen;
+ this.mainnode = mainnode;
}
MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
}
MainNode<K, V> GCAS_READ(final TrieMap<K, V> ct) {
- MainNode<K, V> m = /* READ */ READ();
+ MainNode<K, V> m = /* READ */ mainnode;
MainNode<K, V> prevval = /* READ */ m.READ_PREV();
if (prevval == null) {
return m;
if (prev instanceof FailedNode) {
// try to commit to previous value
FailedNode<K, V> fn = (FailedNode<K, V>) prev;
- if (CAS(m, fn.READ_PREV())) {
+ if (MAINNODE_UPDATER.compareAndSet(this, m, fn.READ_PREV())) {
return fn.READ_PREV();
}
- // Tail recursion: return GCAS_Complete (/* READ */ READ(), ct);
- m = /* READ */ READ();
+ // Tail recursion: return GCAS_Complete (/* READ */ mainnode, ct);
+ m = /* READ */ mainnode;
continue;
}
// try to abort
m.CAS_PREV(prev, new FailedNode<>(prev));
- // Tail recursion: return GCAS_Complete(/* READ */ READ(), ct);
- m = /* READ */ READ();
+ // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
+ m = /* READ */ mainnode;
}
}
private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
n.WRITE_PREV(old);
- if (CAS(old, n)) {
+ if (MAINNODE_UPDATER.compareAndSet(this, old, n)) {
GCAS_Complete(n, ct);
return /* READ */ n.READ_PREV() == null;
}
+++ /dev/null
-/*
- * (C) Copyright 2016 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 java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
-
-abstract class INodeBase<K, V> extends BasicNode {
-
- @SuppressWarnings("rawtypes")
- private static final AtomicReferenceFieldUpdater<INodeBase, MainNode> MAINNODE_UPDATER =
- AtomicReferenceFieldUpdater.newUpdater(INodeBase.class, MainNode.class, "mainnode");
-
- public final Gen gen;
-
- private volatile MainNode<K, V> mainnode;
-
- INodeBase(final Gen generation, final MainNode<K, V> mainnode) {
- gen = generation;
- this.mainnode = mainnode;
- }
-
- final boolean CAS(final MainNode<K, V> old, final MainNode<K, V> n) {
- return MAINNODE_UPDATER.compareAndSet(this, old, n);
- }
-
- final MainNode<K, V> READ() {
- return mainnode;
- }
-}