X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;f=third-party%2Ftriemap%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fyangtools%2Ftriemap%2FINode.java;h=94f10ce901df730d02d8ae4beca1b9c263586b60;hb=0f68d6090d71ae30873e25f137c0e277ce1a2eb8;hp=2e8efe65241282beb0e125e9e6a232d032ffa2b7;hpb=65bacf4e15665b41e84537ad3bf9adfe80c0d4d3;p=yangtools.git 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 2e8efe6524..94f10ce901 100644 --- 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,24 +15,19 @@ */ package org.opendaylight.yangtools.triemap; +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 java.util.Optional; import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; final class INode extends BasicNode { - static final Object KEY_PRESENT = new Object (); - static final Object KEY_ABSENT = new Object (); - - /** - * Virtual result for lookup methods indicating that the lookup needs to be restarted. This is a faster version - * of throwing a checked exception to control the restart. - */ - static final Object RESTART = new Object(); - @SuppressWarnings("rawtypes") private static final AtomicReferenceFieldUpdater MAINNODE_UPDATER = AtomicReferenceFieldUpdater.newUpdater(INode.class, MainNode.class, "mainnode"); - public final Gen gen; + private final Gen gen; private volatile MainNode mainnode; @@ -88,7 +83,7 @@ final class INode 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 ((ctr.gen == gen) && ct.nonReadOnly()) { + if (ctr.gen == gen && !ct.isReadOnly()) { // try to commit if (m.CAS_PREV(prev, null)) { return m; @@ -129,10 +124,15 @@ final class INode 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 parent, final Gen startgen, + boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode parent, final TrieMap ct) { + return rec_insert(k, v, hc, lev, parent, gen, ct); + } + + private boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode parent, + final Gen startgen, final TrieMap ct) { while (true) { - final MainNode m = GCAS_READ (ct); // use -Yinline! + final MainNode m = GCAS_READ(ct); // use -Yinline! if (m instanceof CNode) { // 1) a multiway node @@ -176,9 +176,9 @@ final class INode extends BasicNode { clean(parent, ct, lev - 5); return false; } else if (m instanceof LNode) { - LNode ln = (LNode) m; - MainNode nn = ln.inserted(k, v); - return GCAS(ln, nn, ct); + final LNode ln = (LNode) m; + final LNodeEntry 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); } @@ -199,6 +199,11 @@ final class INode extends BasicNode { * previous value bound to the key) */ Optional rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev, + final INode parent, final TrieMap ct) { + return rec_insertif(k, v, hc, cond, lev, parent, gen, ct); + } + + private Optional rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev, final INode parent, final Gen startgen, final TrieMap ct) { while (true) { final MainNode m = GCAS_READ(ct); // use -Yinline! @@ -246,7 +251,7 @@ final class INode extends BasicNode { } return null; - } else if (cond == INode.KEY_ABSENT) { + } else if (cond == ABSENT) { if (sn.hc == hc && ct.equal(sn.k, k)) { return Optional.of(sn.v); } @@ -259,7 +264,7 @@ final class INode extends BasicNode { } return null; - } else if (cond == INode.KEY_PRESENT) { + } 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)) { return Optional.of(sn.v); @@ -280,7 +285,7 @@ final class INode extends BasicNode { return Optional.empty(); } } - } else if (cond == null || cond == INode.KEY_ABSENT) { + } else if (cond == null || cond == ABSENT) { final CNode rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct); final CNode ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen); if (GCAS(cn, ncnode, ct)) { @@ -288,8 +293,6 @@ final class INode extends BasicNode { } return null; - } else if (cond == INode.KEY_PRESENT) { - return Optional.empty(); } else { return Optional.empty(); } @@ -299,45 +302,32 @@ final class INode extends BasicNode { } else if (m instanceof LNode) { // 3) an l-node final LNode ln = (LNode) m; + final LNodeEntry entry = ln.get(ct.equiv(), k); + if (cond == null) { - final Optional optv = ln.get(k); - if (insertln(ln, k, v, ct)) { - return optv; + if (entry != null) { + return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null; } - return null; - } else if (cond == INode.KEY_ABSENT) { - final Optional t = ln.get(k); - if (t.isPresent()) { - return t; + + return insertln(ln, k, v, ct) ? Optional.empty() : null; + } else if (cond == ABSENT) { + if (entry != null) { + return Optional.of(entry.value()); } - if (insertln(ln, k, v, ct)) { + + return insertln(ln, k, v, ct) ? Optional.empty() : null; + } else if (cond == PRESENT) { + if (entry == null) { return Optional.empty(); } - return null; - } else if (cond == INode.KEY_PRESENT) { - final Optional t = ln.get(k); - if (!t.isPresent()) { - return t; - } - if (insertln(ln, k, v, ct)) { - return t; - } - return null; - } else { - final Optional t = ln.get(k); - if (t.isPresent()) { - if (cond.equals(t.get())) { - if (insertln(ln, k, v, ct)) { - // Difference from Scala: we choose to reuse the object returned from LNode, - // as the identity of the value does not matter in this call graph. - return t; - } - return null; - } + return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null; + } else { + if (entry == null || !cond.equals(entry.value())) { + return Optional.empty(); } - return Optional.empty(); + return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null; } } else { throw new IllegalStateException("Unhandled node " + m); @@ -347,9 +337,12 @@ final class INode extends BasicNode { } } - boolean insertln(final LNode ln, final K k, final V v, final TrieMap ct) { - final LNode nn = ln.inserted (k, v); - return GCAS(ln, nn, ct); + private boolean insertln(final LNode ln, final K k, final V v, final TrieMap ct) { + return GCAS(ln, ln.insertChild(k, v), ct); + } + + private boolean replaceln(final LNode ln, final LNodeEntry entry, final V v, final TrieMap ct) { + return GCAS(ln, ln.replaceChild(entry, v), ct); } /** @@ -358,7 +351,11 @@ final class INode extends BasicNode { * @return null if no value has been found, RESTART if the operation * wasn't successful, or any other value otherwise */ - Object rec_lookup(final K k, final int hc, final int lev, final INode parent, final Gen startgen, + Object rec_lookup(final K k, final int hc, final int lev, final INode parent, final TrieMap ct) { + return rec_lookup(k, hc, lev, parent, gen, ct); + } + + private Object rec_lookup(final K k, final int hc, final int lev, final INode parent, final Gen startgen, final TrieMap ct) { while (true) { final MainNode m = GCAS_READ(ct); // use -Yinline! @@ -388,7 +385,6 @@ final class INode extends BasicNode { continue; } - // used to be throw RestartException return RESTART; } else if (sub instanceof SNode) { // 2) singleton node @@ -404,7 +400,8 @@ final class INode extends BasicNode { return cleanReadOnly((TNode) m, lev, parent, ct, k, hc); } else if (m instanceof LNode) { // 5) an l-node - return ((LNode) m).get(k).orElse(null); + final LNodeEntry entry = ((LNode) m).get(ct.equiv(), k); + return entry != null ? entry.value() : null; } else { throw new IllegalStateException("Unhandled node " + m); } @@ -415,17 +412,16 @@ final class INode extends BasicNode { private Object cleanReadOnly(final TNode tn, final int lev, final INode parent, final TrieMap ct, final K k, final int hc) { - if (ct.nonReadOnly()) { - // used to be throw RestartException - clean(parent, ct, lev - 5); - return RESTART; - } + if (ct.isReadOnly()) { + if (tn.hc == hc && ct.equal(tn.k, k)) { + return tn.v; + } - if (tn.hc == hc && ct.equal(tn.k, k)) { - return tn.v; + return null; } - return null; + clean(parent, ct, lev - 5); + return RESTART; } /** @@ -439,6 +435,11 @@ final class INode extends BasicNode { * value otherwise */ Optional rec_remove(final K k, final V v, final int hc, final int lev, final INode parent, + final TrieMap ct) { + return rec_remove(k, v, hc, lev, parent, gen, ct); + } + + private Optional rec_remove(final K k, final V v, final int hc, final int lev, final INode parent, final Gen startgen, final TrieMap ct) { final MainNode m = GCAS_READ(ct); // use -Yinline! @@ -498,28 +499,19 @@ final class INode extends BasicNode { return null; } else if (m instanceof LNode) { final LNode ln = (LNode) m; - if (v == null) { - final Optional optv = ln.get(k); - final MainNode nn = ln.removed(k, ct); - if (GCAS(ln, nn, ct)) { - return optv; - } - - return null; + final LNodeEntry entry = ln.get(ct.equiv(), k); + if (entry == null) { + // Key was not found, hence no modification is needed + return Optional.empty(); } - final Optional tmp = ln.get(k); - if (tmp.isPresent() && v.equals(tmp.get())) { - final MainNode nn = ln.removed(k, ct); - if (GCAS(ln, nn, ct)) { - return tmp; - } - - return null; + final V value = entry.value(); + if (v != null && !v.equals(value)) { + // Value does not match + return Optional.empty(); } - // Key not found or value does not match: we have not removed anything - return Optional.empty(); + return GCAS(ln, ln.removeChild(entry, hc), ct) ? Optional.of(value) : null; } else { throw new IllegalStateException("Unhandled node " + m); }