From 7dc59ccbdd4fea87fe9719f8095547b8321079f8 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Mon, 10 Sep 2018 22:12:14 +0200 Subject: [PATCH] Migrate to tech.pantheon.TrieMap TrieMap has a new how outside of yangtools, use that source and provide a compatibility wrapper. JIRA: YANGTOOLS-902 Change-Id: Ifcc27f1dddd0e4f97ee992618bd2941c7c2821bc Signed-off-by: Robert Varga --- common/util/pom.xml | 9 +- .../yangtools/util/MapAdaptor.java | 4 +- .../yangtools/util/ReadOnlyTrieMap.java | 4 +- .../yangtools/util/ReadWriteTrieMap.java | 4 +- .../yangtools/util/ReadWriteTrieMapTest.java | 4 +- features/odl-triemap/pom.xml | 14 +- .../odl-triemap/src/main/feature/feature.xml | 1 + third-party/triemap/pom.xml | 16 + .../yangtools/triemap/AbstractEntrySet.java | 73 --- .../yangtools/triemap/AbstractIterator.java | 124 ---- .../yangtools/triemap/AbstractKeySet.java | 81 --- .../yangtools/triemap/BasicNode.java | 20 - .../opendaylight/yangtools/triemap/CNode.java | 212 ------- .../yangtools/triemap/Constants.java | 57 -- .../yangtools/triemap/EntryNode.java | 33 - .../yangtools/triemap/EntryUtil.java | 55 -- .../yangtools/triemap/Equivalence.java | 84 --- .../yangtools/triemap/FailedNode.java | 41 -- .../opendaylight/yangtools/triemap/Gen.java | 20 - .../opendaylight/yangtools/triemap/INode.java | 573 ------------------ .../yangtools/triemap/ImmutableEntrySet.java | 70 --- .../yangtools/triemap/ImmutableIterator.java | 37 -- .../yangtools/triemap/ImmutableKeySet.java | 70 --- .../yangtools/triemap/ImmutableTrieMap.java | 116 +--- .../opendaylight/yangtools/triemap/LNode.java | 72 --- .../yangtools/triemap/LNodeEntries.java | 129 ---- .../yangtools/triemap/LNodeEntry.java | 69 --- .../yangtools/triemap/LookupResult.java | 26 - .../yangtools/triemap/MainNode.java | 62 -- .../yangtools/triemap/MutableEntrySet.java | 81 --- .../yangtools/triemap/MutableIterator.java | 123 ---- .../yangtools/triemap/MutableKeySet.java | 69 --- .../yangtools/triemap/MutableTrieMap.java | 236 +------- .../yangtools/triemap/PresencePredicate.java | 27 - .../opendaylight/yangtools/triemap/SNode.java | 68 --- .../yangtools/triemap/SerializationProxy.java | 83 --- .../opendaylight/yangtools/triemap/TNode.java | 78 --- .../yangtools/triemap/TrieMap.java | 168 +++-- .../yangtools/triemap/LNodeEntriesTest.java | 37 -- .../yangtools/triemap/SnapshotTest.java | 1 + .../triemap/TestCNodeFlagCollision.java | 1 + .../TestCNodeInsertionIncorrectOrder.java | 1 + .../triemap/TestConcurrentMapPutIfAbsent.java | 60 -- .../triemap/TestConcurrentMapRemove.java | 64 -- .../triemap/TestConcurrentMapReplace.java | 86 --- .../yangtools/triemap/TestDelete.java | 107 ---- .../yangtools/triemap/TestHashCollisions.java | 1 + .../triemap/TestHashCollisionsRemove.java | 1 + .../TestHashCollisionsRemoveIterator.java | 1 + .../yangtools/triemap/TestInsert.java | 1 + .../triemap/TestInstantiationSpeed.java | 67 -- .../yangtools/triemap/TestMapIterator.java | 126 ---- .../triemap/TestMultiThreadAddDelete.java | 24 +- .../triemap/TestMultiThreadInserts.java | 1 + .../triemap/TestMultiThreadMapIterator.java | 1 + .../TestReadOnlyAndUpdatableIterators.java | 105 ---- .../yangtools/triemap/TestSerialization.java | 1 + .../yangtools/triemap/ZeroHashInt.java | 46 -- 58 files changed, 151 insertions(+), 3594 deletions(-) delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractEntrySet.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractIterator.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractKeySet.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/BasicNode.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Constants.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntryNode.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntryUtil.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Equivalence.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/FailedNode.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Gen.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableEntrySet.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableIterator.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableKeySet.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntries.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntry.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LookupResult.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MainNode.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableEntrySet.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableIterator.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableKeySet.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/PresencePredicate.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/SNode.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/SerializationProxy.java delete mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TNode.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/LNodeEntriesTest.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapPutIfAbsent.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapRemove.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapReplace.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInstantiationSpeed.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestReadOnlyAndUpdatableIterators.java delete mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ZeroHashInt.java diff --git a/common/util/pom.xml b/common/util/pom.xml index 5bf9c7c0e7..68bacdad49 100644 --- a/common/util/pom.xml +++ b/common/util/pom.xml @@ -27,6 +27,13 @@ + + tech.pantheon.triemap + bom + 1.0.0 + import + pom + org.opendaylight.yangtools yangtools-artifacts @@ -43,7 +50,7 @@ concepts - org.opendaylight.yangtools + tech.pantheon.triemap triemap diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java b/common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java index 1198df67ac..eee8287f19 100644 --- a/common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java +++ b/common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java @@ -15,10 +15,10 @@ import java.util.Collections; import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; -import org.opendaylight.yangtools.triemap.MutableTrieMap; -import org.opendaylight.yangtools.triemap.TrieMap; import org.slf4j.Logger; import org.slf4j.LoggerFactory; +import tech.pantheon.triemap.MutableTrieMap; +import tech.pantheon.triemap.TrieMap; /** * A simple layer on top of maps, which performs snapshot mediation and optimization of diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/ReadOnlyTrieMap.java b/common/util/src/main/java/org/opendaylight/yangtools/util/ReadOnlyTrieMap.java index fe2091a80c..c0402840b7 100644 --- a/common/util/src/main/java/org/opendaylight/yangtools/util/ReadOnlyTrieMap.java +++ b/common/util/src/main/java/org/opendaylight/yangtools/util/ReadOnlyTrieMap.java @@ -12,10 +12,10 @@ import static java.util.Objects.requireNonNull; import com.google.common.collect.ForwardingMap; import java.util.Map; import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; -import org.opendaylight.yangtools.triemap.ImmutableTrieMap; -import org.opendaylight.yangtools.triemap.MutableTrieMap; import org.slf4j.Logger; import org.slf4j.LoggerFactory; +import tech.pantheon.triemap.ImmutableTrieMap; +import tech.pantheon.triemap.MutableTrieMap; /** * A read-only facade in front of a TrieMap. This is what we give out from diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/ReadWriteTrieMap.java b/common/util/src/main/java/org/opendaylight/yangtools/util/ReadWriteTrieMap.java index f532d2433c..702fd00730 100644 --- a/common/util/src/main/java/org/opendaylight/yangtools/util/ReadWriteTrieMap.java +++ b/common/util/src/main/java/org/opendaylight/yangtools/util/ReadWriteTrieMap.java @@ -15,10 +15,10 @@ import java.util.Collections; import java.util.Map; import java.util.Set; import javax.annotation.Nonnull; -import org.opendaylight.yangtools.triemap.MutableTrieMap; -import org.opendaylight.yangtools.triemap.TrieMap; import org.slf4j.Logger; import org.slf4j.LoggerFactory; +import tech.pantheon.triemap.MutableTrieMap; +import tech.pantheon.triemap.TrieMap; /** * A TrieMap facade tracking modifications. Since we change structures based on diff --git a/common/util/src/test/java/org/opendaylight/yangtools/util/ReadWriteTrieMapTest.java b/common/util/src/test/java/org/opendaylight/yangtools/util/ReadWriteTrieMapTest.java index d7f79056f6..c78b1d7f60 100644 --- a/common/util/src/test/java/org/opendaylight/yangtools/util/ReadWriteTrieMapTest.java +++ b/common/util/src/test/java/org/opendaylight/yangtools/util/ReadWriteTrieMapTest.java @@ -19,8 +19,8 @@ import java.util.Map; import java.util.Map.Entry; import java.util.Set; import org.junit.Test; -import org.opendaylight.yangtools.triemap.MutableTrieMap; -import org.opendaylight.yangtools.triemap.TrieMap; +import tech.pantheon.triemap.MutableTrieMap; +import tech.pantheon.triemap.TrieMap; public class ReadWriteTrieMapTest { diff --git a/features/odl-triemap/pom.xml b/features/odl-triemap/pom.xml index 9769838171..03bcd5ae23 100644 --- a/features/odl-triemap/pom.xml +++ b/features/odl-triemap/pom.xml @@ -25,6 +25,13 @@ + + tech.pantheon.triemap + bom + 1.0.0 + import + pom + org.opendaylight.yangtools yangtools-artifacts @@ -39,7 +46,12 @@ org.opendaylight.odlparent odl-guava - 4.0.0 + xml + features + + + tech.pantheon.triemap + pt-triemap xml features diff --git a/features/odl-triemap/src/main/feature/feature.xml b/features/odl-triemap/src/main/feature/feature.xml index baac20f01e..e4ab6c8580 100644 --- a/features/odl-triemap/src/main/feature/feature.xml +++ b/features/odl-triemap/src/main/feature/feature.xml @@ -2,5 +2,6 @@ odl-guava + pt-triemap diff --git a/third-party/triemap/pom.xml b/third-party/triemap/pom.xml index 1f22c64c77..e41e810d14 100644 --- a/third-party/triemap/pom.xml +++ b/third-party/triemap/pom.xml @@ -36,7 +36,23 @@ ${project.basedir}/../../target/jacoco.exec + + + + tech.pantheon.triemap + bom + 1.0.0 + import + pom + + + + + + tech.pantheon.triemap + triemap + com.google.guava guava diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractEntrySet.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractEntrySet.java deleted file mode 100644 index e82ba87a34..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractEntrySet.java +++ /dev/null @@ -1,73 +0,0 @@ -/* - * (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 java.util.Objects.requireNonNull; - -import java.util.AbstractSet; -import java.util.Map.Entry; -import java.util.Spliterator; -import java.util.Spliterators; - -/** - * Abstract base class for implementing {@link TrieMap} entry sets. - * - * @author Robert Varga - * - * @param the type of entry keys - * @param the type of entry values - */ -abstract class AbstractEntrySet extends AbstractSet> { - private final TrieMap map; - - AbstractEntrySet(final TrieMap map) { - this.map = requireNonNull(map); - } - - final TrieMap map() { - return map; - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public final boolean contains(final Object o) { - if (!(o instanceof Entry)) { - return false; - } - - final Entry e = (Entry) o; - final Object key = e.getKey(); - if (key == null) { - return false; - } - - final V v = map.get(key); - return v != null && v.equals(e.getValue()); - } - - @Override - public final int size() { - return map.size(); - } - - @Override - public final Spliterator> spliterator() { - // TODO: this is backed by an Iterator, we should be able to do better - return Spliterators.spliterator(map.immutableIterator(), Long.MAX_VALUE, characteristics()); - } - - abstract int characteristics(); -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractIterator.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractIterator.java deleted file mode 100644 index e13ddd651a..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractIterator.java +++ /dev/null @@ -1,124 +0,0 @@ -/* - * (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 org.opendaylight.yangtools.triemap.Constants.MAX_DEPTH; - -import java.util.Iterator; -import java.util.Map.Entry; -import java.util.NoSuchElementException; - -/** - * Abstract base class for iterators supporting {@link AbstractEntrySet} subclasses. - * - * @author Robert Varga - * - * @param the type of entry keys - * @param the type of entry values - */ -abstract class AbstractIterator implements Iterator> { - private final BasicNode[][] nodeStack = new BasicNode[MAX_DEPTH][]; - private final int[] positionStack = new int[MAX_DEPTH]; - private final TrieMap map; - - private LNodeEntries lnode; - private EntryNode current; - private int depth = -1; - - AbstractIterator(final ImmutableTrieMap map) { - this.map = map; - readin(map.RDCSS_READ_ROOT()); - } - - @Override - public final boolean hasNext() { - return current != null || lnode != null; - } - - @Override - public final Entry next() { - final Entry entry; - - // Check LNode iterator first - if (lnode != null) { - entry = lnode; - lnode = lnode.next(); - if (lnode == null) { - advance(); - } - } else { - entry = current; - advance(); - } - - if (entry == null) { - throw new NoSuchElementException(); - } - - return wrapEntry(entry); - } - - /** - * Wrap entry so it can be presented to the user. - * - * @param entry An immutable entry, guaranteed to be non-null - * @return Wrapped entry, may not be null - */ - abstract Entry wrapEntry(Entry entry); - - /** - * Read the contents of an INode's main node. - * - * @param in INode to be read. - */ - private void readin(final INode in) { - final MainNode m = in.gcasRead(map); - if (m instanceof CNode) { - // Enter the next level - final CNode cn = (CNode) m; - depth++; - nodeStack[depth] = cn.array; - positionStack[depth] = -1; - advance(); - } else if (m instanceof TNode) { - current = (TNode) m; - } else if (m instanceof LNode) { - lnode = ((LNode) m).entries(); - } else if (m == null) { - current = null; - } - } - - private void advance() { - if (depth >= 0) { - int npos = positionStack[depth] + 1; - if (npos < nodeStack[depth].length) { - positionStack [depth] = npos; - BasicNode elem = nodeStack[depth][npos]; - if (elem instanceof SNode) { - current = (SNode) elem; - } else if (elem instanceof INode) { - readin((INode) elem); - } - } else { - depth -= 1; - advance(); - } - } else { - current = null; - } - } -} \ No newline at end of file diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractKeySet.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractKeySet.java deleted file mode 100644 index 6ed480777f..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractKeySet.java +++ /dev/null @@ -1,81 +0,0 @@ -/* - * (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 static java.util.Objects.requireNonNull; - -import com.google.common.collect.Iterators; -import java.util.AbstractSet; -import java.util.Collection; -import java.util.Map.Entry; -import java.util.Spliterator; -import java.util.Spliterators; - -/** - * Abstract base class for key set views of a TrieMap. - * - * @author Robert Varga - * - * @param the type of keys - */ -abstract class AbstractKeySet extends AbstractSet { - private final TrieMap map; - - AbstractKeySet(final TrieMap map) { - this.map = requireNonNull(map); - } - - final TrieMap map() { - return map; - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public final boolean add(final K e) { - throw new UnsupportedOperationException(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public final boolean addAll(final Collection c) { - throw new UnsupportedOperationException(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public final boolean contains(final Object o) { - return map.containsKey(o); - } - - @Override - public final boolean isEmpty() { - return map.isEmpty(); - } - - @Override - public final int size() { - return map.size(); - } - - @Override - public final Spliterator spliterator() { - // TODO: this is backed by an Iterator, we should be able to do better - return Spliterators.spliterator(Iterators.transform(map().immutableIterator(), Entry::getKey), Long.MAX_VALUE, - spliteratorCharacteristics()); - } - - abstract int spliteratorCharacteristics(); -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/BasicNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/BasicNode.java deleted file mode 100644 index 289d719c6e..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/BasicNode.java +++ /dev/null @@ -1,20 +0,0 @@ -/* - * (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; - -abstract class BasicNode { - -} \ No newline at end of file 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 deleted file mode 100644 index 412d9f9fde..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java +++ /dev/null @@ -1,212 +0,0 @@ -/* - * (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 static org.opendaylight.yangtools.triemap.Constants.HASH_BITS; -import static org.opendaylight.yangtools.triemap.Constants.LEVEL_BITS; - -import com.google.common.base.Verify; -import com.google.common.base.VerifyException; -import java.util.concurrent.ThreadLocalRandom; - -final class CNode extends MainNode { - private static final BasicNode[] EMPTY_ARRAY = new BasicNode[0]; - - 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) { - this.bitmap = bitmap; - this.array = array; - this.gen = gen; - } - - CNode(final Gen gen) { - this(gen, 0, EMPTY_ARRAY); - } - - static MainNode dual(final SNode x, final K key, final V value, final int hc, final int lev, - final Gen gen) { - return dual(x, x.hc, new SNode<>(key, value, hc), hc, lev, gen); - } - - private static MainNode dual(final SNode x, final int xhc, final SNode y, final int yhc, - final int lev, final Gen gen) { - if (lev >= HASH_BITS) { - return new LNode<>(x.key, x.value, y.key, y.value); - } - - final int xidx = (xhc >>> lev) & 0x1f; - final int yidx = (yhc >>> lev) & 0x1f; - final int bmp = (1 << xidx) | (1 << yidx); - - if (xidx == yidx) { - 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); - } - - @Override - int trySize() { - return csize; - } - - @Override - int size(final ImmutableTrieMap ct) { - int sz; - return (sz = csize) != NO_SIZE ? sz : (csize = computeSize(ct)); - } - - static VerifyException invalidElement(final BasicNode elem) { - throw new VerifyException("A CNode can contain only CNodes and SNodes, not " + elem); - } - - // lends itself towards being parallelizable by choosing - // a random starting offset in the array - // => if there are concurrent size computations, they start - // at different positions, so they are more likely to - // to be independent - private int computeSize(final ImmutableTrieMap ct) { - final int len = array.length; - switch (len) { - case 0: - return 0; - case 1: - return elementSize(array[0], ct); - default: - final int offset = ThreadLocalRandom.current().nextInt(len); - int sz = 0; - for (int i = offset; i < len; ++i) { - sz += elementSize(array[i], ct); - } - for (int i = 0; i < offset; ++i) { - sz += elementSize(array[i], ct); - } - return sz; - } - } - - private static int elementSize(final BasicNode elem, final ImmutableTrieMap ct) { - if (elem instanceof SNode) { - return 1; - } else if (elem instanceof INode) { - return ((INode) elem).size(ct); - } else { - throw invalidElement(elem); - } - } - - CNode updatedAt(final int pos, final BasicNode nn, final Gen gen) { - int len = array.length; - BasicNode[] narr = new BasicNode[len]; - System.arraycopy(array, 0, narr, 0, len); - narr[pos] = nn; - return new CNode<>(gen, bitmap, narr); - } - - CNode removedAt(final int pos, final int flag, final Gen gen) { - BasicNode[] arr = array; - int len = arr.length; - 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<>(gen, bitmap ^ flag, narr); - } - - CNode insertedAt(final int pos, final int flag, final BasicNode nn, final Gen gen) { - int len = array.length; - BasicNode[] narr = new BasicNode[len + 1]; - System.arraycopy(array, 0, narr, 0, pos); - narr [pos] = nn; - System.arraycopy(array, pos, narr, pos + 1, len - pos); - return new CNode<>(gen, bitmap | flag, narr); - } - - /** - * Returns a copy of this cnode such that all the i-nodes below it are - * copied to the specified generation `ngen`. - */ - CNode renewed(final Gen ngen, final TrieMap ct) { - int i = 0; - final BasicNode[] arr = array; - final int len = arr.length; - final BasicNode[] narr = new BasicNode[len]; - while (i < len) { - final BasicNode elem = arr[i]; - if (elem instanceof INode) { - narr[i] = ((INode) elem).copyToGen(ngen, ct); - } else if (elem != null) { - narr[i] = elem; - } - i += 1; - } - return new CNode<>(ngen, bitmap, narr); - } - - MainNode toContracted(final int lev) { - if (array.length == 1 && lev > 0) { - if (array[0] instanceof SNode) { - return ((SNode) array[0]).copyTombed(); - } - return this; - } - - return this; - } - - // - if the branching factor is 1 for this CNode, and the child - // is a tombed SNode, returns its tombed version - // - otherwise, if there is at least one non-null node below, - // returns the version of this node with at least some null-inodes - // removed (those existing when the op began) - // - if there are only null-i-nodes below, returns null - MainNode toCompressed(final TrieMap ct, final int lev, final Gen gen) { - int bmp = bitmap; - int i = 0; - BasicNode[] arr = array; - BasicNode[] tmparray = new BasicNode[arr.length]; - while (i < arr.length) { // construct new bitmap - BasicNode sub = arr[i]; - if (sub instanceof INode) { - final INode in = (INode) sub; - final MainNode inodemain = Verify.verifyNotNull(in.gcasRead(ct)); - tmparray [i] = resurrect(in, inodemain); - } else if (sub instanceof SNode) { - tmparray [i] = sub; - } - i += 1; - } - - return new CNode(gen, bmp, tmparray).toContracted(lev); - } - - private static BasicNode resurrect(final INode inode, final MainNode inodemain) { - return inodemain instanceof TNode ? ((TNode) inodemain).copyUntombed() : inode; - } - - @Override - public String toString() { - // val elems = collectLocalElems - // "CNode(sz: %d; %s)".format(elems.size, - // elems.sorted.mkString(", ")) - return "CNode"; - } -} 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 deleted file mode 100644 index 931db16225..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Constants.java +++ /dev/null @@ -1,57 +0,0 @@ -/* - * (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; - - /** - * Maximum depth of a TrieMap. - */ - static final int MAX_DEPTH = 7; - - static { - verify(LEVEL_BITS == IntMath.log2(BITMAP_BITS, RoundingMode.UNNECESSARY)); - verify(MAX_DEPTH == IntMath.divide(HASH_BITS, LEVEL_BITS, RoundingMode.CEILING)); - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntryNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntryNode.java deleted file mode 100644 index 4f12ade4f9..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntryNode.java +++ /dev/null @@ -1,33 +0,0 @@ -/* - * (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 java.util.Map.Entry; - -/** - * Common marker interface for nodes which act as an immutable {@link Entry}. - * - * @author Robert Varga - * - * @param the type of key - * @param the type of value - */ -interface EntryNode extends Entry { - @Override - default V setValue(final V value) { - throw new UnsupportedOperationException(); - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntryUtil.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntryUtil.java deleted file mode 100644 index 6fe50d5597..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntryUtil.java +++ /dev/null @@ -1,55 +0,0 @@ -/* - * (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 java.util.Map.Entry; - -/** - * Utility methods for implementing {@link Entry} contract. - * - * @author Robert Varga - */ -final class EntryUtil { - private EntryUtil() { - throw new UnsupportedOperationException(); - } - - /** - * Utility implementing {@link Entry#equals(Object)}. - */ - static boolean equal(final Object obj, final Object key, final Object value) { - if (!(obj instanceof Entry)) { - return false; - } - - final Entry e = (Entry)obj; - return key.equals(e.getKey()) && value.equals(e.getValue()); - } - - /** - * Utility implementing {@link Entry#hashCode()}. - */ - static int hash(final Object key, final Object value) { - return key.hashCode() ^ value.hashCode(); - } - - /** - * Utility implementing {@link Entry#toString()}. - */ - static String string(final Object key, final Object value) { - return key + "=" + value; - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Equivalence.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Equivalence.java deleted file mode 100644 index 4923290ca7..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Equivalence.java +++ /dev/null @@ -1,84 +0,0 @@ -/* - * (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.io.Serializable; -import javax.annotation.Nonnull; - -/** - * Internal equivalence class, similar to {@link com.google.common.base.Equivalence}, but explicitly not handling - * nulls. We use equivalence only for keys, which are guaranteed to be non-null. - * - * @author Robert Varga - */ -abstract class Equivalence implements Serializable { - private static final long serialVersionUID = 1L; - - private static final class Equals extends Equivalence { - private static final long serialVersionUID = 1L; - - static final Equals INSTANCE = new Equals(); - - @Override - boolean equivalent(final Object a, final Object b) { - return a.equals(b); - } - - @Override - Object readResolve() { - return INSTANCE; - } - } - - private static final class Identity extends Equivalence { - private static final long serialVersionUID = 1L; - - static final Identity INSTANCE = new Identity(); - - @Override - boolean equivalent(final Object a, final Object b) { - return a == b; - } - - @Override - Object readResolve() { - return INSTANCE; - } - } - - static Equivalence equals() { - return Equals.INSTANCE; - } - - static Equivalence identity() { - return Identity.INSTANCE; - } - - final int hash(@Nonnull final T t) { - int h = t.hashCode(); - - // This function ensures that hashCodes that differ only by - // constant multiples at each bit position have a bounded - // number of collisions (approximately 8 at default load factor). - h ^= (h >>> 20) ^ (h >>> 12); - h ^= (h >>> 7) ^ (h >>> 4); - return h; - } - - abstract boolean equivalent(@Nonnull T a, @Nonnull T b); - - abstract Object readResolve(); -} 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 deleted file mode 100644 index 726bff9490..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/FailedNode.java +++ /dev/null @@ -1,41 +0,0 @@ -/* - * (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; - -final class FailedNode extends MainNode { - private final MainNode p; - - FailedNode(final MainNode p) { - super(p); - this.p = p; - } - - @Override - int trySize() { - throw new UnsupportedOperationException(); - } - - @Override - int size(final ImmutableTrieMap ct) { - throw new UnsupportedOperationException(); - } - - @Override - 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/Gen.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Gen.java deleted file mode 100644 index ef9d2d6f92..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/Gen.java +++ /dev/null @@ -1,20 +0,0 @@ -/* - * (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; - -final class Gen { - -} 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 deleted file mode 100644 index 701d608f95..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.java +++ /dev/null @@ -1,573 +0,0 @@ -/* - * (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 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; - -import com.google.common.base.VerifyException; -import edu.umd.cs.findbugs.annotations.SuppressFBWarnings; -import java.util.Optional; -import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; - -final class INode extends BasicNode { - @SuppressWarnings("rawtypes") - private static final AtomicReferenceFieldUpdater MAINNODE_UPDATER = - AtomicReferenceFieldUpdater.newUpdater(INode.class, MainNode.class, "mainnode"); - - private final Gen gen; - - private volatile MainNode mainnode; - - INode(final Gen gen, final MainNode mainnode) { - this.gen = gen; - this.mainnode = mainnode; - } - - MainNode gcasRead(final TrieMap ct) { - return GCAS_READ(ct); - } - - private MainNode GCAS_READ(final TrieMap ct) { - MainNode m = /* READ */ mainnode; - MainNode prevval = /* READ */ m.readPrev(); - if (prevval == null) { - return m; - } - - return GCAS_Complete(m, ct); - } - - private MainNode GCAS_Complete(final MainNode oldmain, final TrieMap ct) { - MainNode m = oldmain; - while (m != null) { - // complete the GCAS - final MainNode prev = /* READ */ m.readPrev(); - final INode ctr = ct.readRoot(true); - if (prev == null) { - return m; - } - - if (prev instanceof FailedNode) { - // try to commit to previous value - FailedNode fn = (FailedNode) prev; - if (MAINNODE_UPDATER.compareAndSet(this, m, fn.readPrev())) { - return fn.readPrev(); - } - - // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct); - m = /* READ */ mainnode; - continue; - } - - // Assume that you've read the root from the generation G. - // Assume that the snapshot algorithm is correct. - // ==> you can only reach nodes in generations <= G. - // ==> `gen` is <= G. - // We know that `ctr.gen` is >= G. - // ==> 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.isReadOnly()) { - // try to commit - if (m.casPrev(prev, null)) { - return m; - } - - // Tail recursion: return GCAS_Complete(m, ct); - continue; - } - - // try to abort - m.casPrev(prev, new FailedNode<>(prev)); - - // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct); - m = /* READ */ mainnode; - } - - return null; - } - - private boolean GCAS(final MainNode old, final MainNode n, final TrieMap ct) { - n.writePrev(old); - if (MAINNODE_UPDATER.compareAndSet(this, old, n)) { - GCAS_Complete(n, ct); - return /* READ */ n.readPrev() == null; - } - - return false; - } - - private INode inode(final MainNode cn) { - return new INode<>(gen, cn); - } - - INode copyToGen(final Gen ngen, final TrieMap ct) { - return new INode<>(ngen, GCAS_READ(ct)); - } - - /** - * Inserts a key value pair, overwriting the old pair if the keys match. - * - * @return true if successful, false otherwise - */ - boolean recInsert(final K key, final V value, final int hc, final int lev, final INode parent, - final TrieMap ct) { - return recInsert(key, value, hc, lev, parent, gen, ct); - } - - private boolean recInsert(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); - - if (m instanceof CNode) { - // 1) a multiway node - final CNode cn = (CNode) m; - final int idx = (hc >>> lev) & 0x1f; - final int flag = 1 << idx; - final int bmp = cn.bitmap; - final int mask = flag - 1; - final int pos = Integer.bitCount(bmp & mask); - - if ((bmp & flag) != 0) { - // 1a) insert below - final BasicNode cnAtPos = cn.array[pos]; - if (cnAtPos instanceof INode) { - final INode in = (INode) cnAtPos; - if (startgen == in.gen) { - return in.recInsert(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); - continue; - } - - return false; - } else if (cnAtPos instanceof SNode) { - final SNode sn = (SNode) cnAtPos; - if (sn.hc == hc && ct.equal(sn.key, k)) { - return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct); - } - - final CNode rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct); - final MainNode nn = rn.updatedAt(pos, inode( - CNode.dual(sn, k, v, hc, lev + LEVEL_BITS, gen)), gen); - return GCAS(cn, nn, ct); - } else { - throw CNode.invalidElement(cnAtPos); - } - } - - final CNode rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct); - final MainNode ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen); - return GCAS(cn, ncnode, ct); - } else if (m instanceof TNode) { - clean(parent, ct, lev - LEVEL_BITS); - return false; - } else if (m instanceof LNode) { - 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 invalidElement(m); - } - } - } - - private static VerifyException invalidElement(final BasicNode elem) { - throw new VerifyException("An INode can host only a CNode, a TNode or an LNode, not " + elem); - } - - @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL", - justification = "Returning null Optional indicates the need to restart.") - private Optional insertDual(final TrieMap ct, final CNode cn, final int pos, final SNode sn, - final K k, final V v, final int hc, final int lev) { - final CNode rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct); - final MainNode nn = rn.updatedAt(pos, inode(CNode.dual(sn, k, v, hc, lev + LEVEL_BITS, gen)), gen); - return GCAS(cn, nn, ct) ? Optional.empty() : null; - } - - /** - * Inserts a new key value pair, given that a specific condition is met. - * - * @param cond - * null - don't care if the key was there - * KEY_ABSENT - key wasn't there - * KEY_PRESENT - key was there - * other value `v` - key must be bound to `v` - * @return null if unsuccessful, Option[V] otherwise (indicating - * previous value bound to the key) - */ - Optional recInsertIf(final K k, final V v, final int hc, final Object cond, final int lev, - final INode parent, final TrieMap ct) { - return recInsertIf(k, v, hc, cond, lev, parent, gen, ct); - } - - @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL", - justification = "Returning null Optional indicates the need to restart.") - private Optional recInsertIf(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); - - if (m instanceof CNode) { - // 1) a multiway node - final CNode cn = (CNode) m; - final int idx = (hc >>> lev) & 0x1f; - final int flag = 1 << idx; - final int bmp = cn.bitmap; - final int mask = flag - 1; - final int pos = Integer.bitCount(bmp & mask); - - if ((bmp & flag) != 0) { - // 1a) insert below - final BasicNode cnAtPos = cn.array[pos]; - if (cnAtPos instanceof INode) { - final INode in = (INode) cnAtPos; - if (startgen == in.gen) { - return in.recInsertIf(k, v, hc, cond, lev + LEVEL_BITS, this, startgen, ct); - } - - if (GCAS(cn, cn.renewed(startgen, ct), ct)) { - // Tail recursion: return rec_insertif(k, v, hc, cond, lev, parent, startgen, ct); - continue; - } - - return null; - } else if (cnAtPos instanceof SNode) { - final SNode sn = (SNode) cnAtPos; - if (cond == null) { - if (sn.hc == hc && ct.equal(sn.key, k)) { - if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) { - return Optional.of(sn.value); - } - - return null; - } - - return insertDual(ct, cn, pos, sn, k, v, hc, lev); - } else if (cond == ABSENT) { - if (sn.hc == hc && ct.equal(sn.key, k)) { - return Optional.of(sn.value); - } - - return insertDual(ct, cn, pos, sn, k, v, hc, lev); - } else if (cond == PRESENT) { - if (sn.hc == hc && ct.equal(sn.key, k)) { - if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) { - return Optional.of(sn.value); - } - return null; - } - - return Optional.empty(); - } else { - if (sn.hc == hc && ct.equal(sn.key, k) && cond.equals(sn.value)) { - if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) { - return Optional.of(sn.value); - } - - return null; - } - - return Optional.empty(); - } - } else { - throw CNode.invalidElement(cnAtPos); - } - } 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)) { - return Optional.empty(); - } - - return null; - } else { - return Optional.empty(); - } - } else if (m instanceof TNode) { - clean(parent, ct, lev - LEVEL_BITS); - return null; - } 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) { - if (entry != null) { - return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null; - } - - return insertln(ln, k, v, ct) ? Optional.empty() : null; - } else if (cond == ABSENT) { - if (entry != null) { - return Optional.of(entry.getValue()); - } - - return insertln(ln, k, v, ct) ? Optional.empty() : null; - } else if (cond == PRESENT) { - if (entry == null) { - return Optional.empty(); - } - - return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null; - } else { - if (entry == null || !cond.equals(entry.getValue())) { - return Optional.empty(); - } - - return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null; - } - } else { - throw invalidElement(m); - } - } - } - - 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); - } - - /** - * Looks up the value associated with the key. - * - * @return null if no value has been found, RESTART if the operation - * wasn't successful, or any other value otherwise - */ - Object recLookup(final K k, final int hc, final int lev, final INode parent, final TrieMap ct) { - return recLookup(k, hc, lev, parent, gen, ct); - } - - private Object recLookup(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); - - if (m instanceof CNode) { - // 1) a multinode - final CNode cn = (CNode) m; - final int idx = (hc >>> lev) & 0x1f; - final int flag = 1 << idx; - final int bmp = cn.bitmap; - - if ((bmp & flag) == 0) { - // 1a) bitmap shows no binding - return null; - } - - // 1b) bitmap contains a value - descend - final int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1)); - final BasicNode sub = cn.array[pos]; - if (sub instanceof INode) { - final INode in = (INode) sub; - if (ct.isReadOnly() || (startgen == in.gen)) { - return in.recLookup(k, hc, lev + LEVEL_BITS, this, startgen, ct); - } - - if (GCAS(cn, cn.renewed(startgen, ct), ct)) { - // Tail recursion: return rec_lookup(k, hc, lev, parent, startgen, ct); - continue; - } - - return RESTART; - } else if (sub instanceof SNode) { - // 2) singleton node - final SNode sn = (SNode) sub; - if (sn.hc == hc && ct.equal(sn.key, k)) { - return sn.value; - } - - return null; - } else { - throw CNode.invalidElement(sub); - } - } else if (m instanceof TNode) { - // 3) non-live node - return cleanReadOnly((TNode) m, lev, parent, ct, k, hc); - } else if (m instanceof LNode) { - // 5) an l-node - final LNodeEntry entry = ((LNode) m).get(ct.equiv(), k); - return entry != null ? entry.getValue() : null; - } else { - throw invalidElement(m); - } - } - } - - private Object cleanReadOnly(final TNode tn, final int lev, final INode parent, - final TrieMap ct, final K k, final int hc) { - if (ct.isReadOnly()) { - if (tn.hc == hc && ct.equal(tn.key, k)) { - return tn.value; - } - - return null; - } - - clean(parent, ct, lev - LEVEL_BITS); - return RESTART; - } - - /** - * Removes the key associated with the given value. - * - * @param cond - * if null, will remove the key regardless of the value; - * otherwise removes only if binding contains that exact key - * and value - * @return null if not successful, an Optional indicating the previous - * value otherwise - */ - Optional recRemove(final K k, final Object cond, final int hc, final int lev, final INode parent, - final TrieMap ct) { - return recRemove(k, cond, hc, lev, parent, gen, ct); - } - - @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL", - justification = "Returning null Optional indicates the need to restart.") - private Optional recRemove(final K k, final Object cond, final int hc, final int lev, final INode parent, - final Gen startgen, final TrieMap ct) { - final MainNode m = GCAS_READ(ct); - - if (m instanceof CNode) { - final CNode cn = (CNode) m; - final int idx = (hc >>> lev) & 0x1f; - final int bmp = cn.bitmap; - final int flag = 1 << idx; - if ((bmp & flag) == 0) { - return Optional.empty(); - } - - final int pos = Integer.bitCount(bmp & (flag - 1)); - final BasicNode sub = cn.array[pos]; - final Optional res; - if (sub instanceof INode) { - final INode in = (INode) sub; - if (startgen == in.gen) { - res = in.recRemove(k, cond, hc, lev + LEVEL_BITS, this, startgen, ct); - } else { - if (GCAS(cn, cn.renewed(startgen, ct), ct)) { - res = recRemove(k, cond, hc, lev, parent, startgen, ct); - } else { - res = null; - } - } - } else if (sub instanceof SNode) { - final SNode sn = (SNode) sub; - if (sn.hc == hc && ct.equal(sn.key, k) && (cond == null || cond.equals(sn.value))) { - final MainNode ncn = cn.removedAt(pos, flag, gen).toContracted(lev); - if (GCAS(cn, ncn, ct)) { - res = Optional.of(sn.value); - } else { - res = null; - } - } else { - res = Optional.empty(); - } - } else { - throw CNode.invalidElement(sub); - } - - if (res == null || !res.isPresent()) { - return res; - } - - if (parent != null) { - // never tomb at root - final MainNode n = GCAS_READ(ct); - if (n instanceof TNode) { - cleanParent(n, parent, ct, hc, lev, startgen); - } - } - - return res; - } else if (m instanceof TNode) { - clean(parent, ct, lev - LEVEL_BITS); - return null; - } else if (m instanceof LNode) { - final LNode ln = (LNode) m; - final LNodeEntry entry = ln.get(ct.equiv(), k); - if (entry == null) { - // Key was not found, hence no modification is needed - return Optional.empty(); - } - - final V value = entry.getValue(); - if (cond != null && !cond.equals(value)) { - // Value does not match - return Optional.empty(); - } - - return GCAS(ln, ln.removeChild(entry, hc), ct) ? Optional.of(value) : null; - } else { - throw invalidElement(m); - } - } - - private void cleanParent(final Object nonlive, final INode parent, final TrieMap ct, final int hc, - final int lev, final Gen startgen) { - while (true) { - final MainNode pm = parent.GCAS_READ(ct); - if ((!(pm instanceof CNode))) { - // parent is no longer a cnode, we're done - return; - } - - final CNode cn = (CNode) pm; - final int idx = (hc >>> (lev - LEVEL_BITS)) & 0x1f; - final int bmp = cn.bitmap; - final int flag = 1 << idx; - if ((bmp & flag) == 0) { - // somebody already removed this i-node, we're done - return; - } - - final int pos = Integer.bitCount(bmp & (flag - 1)); - final BasicNode sub = cn.array[pos]; - if (sub == this && nonlive instanceof TNode) { - final TNode tn = (TNode) nonlive; - final MainNode 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); - continue; - } - } - } - break; - } - } - - private void clean(final INode nd, final TrieMap ct, final int lev) { - final MainNode m = nd.GCAS_READ(ct); - if (m instanceof CNode) { - final CNode cn = (CNode) m; - nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct); - } - } - - int size(final ImmutableTrieMap ct) { - return GCAS_READ(ct).size(ct); - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableEntrySet.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableEntrySet.java deleted file mode 100644 index e09e925e71..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableEntrySet.java +++ /dev/null @@ -1,70 +0,0 @@ -/* - * (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 org.opendaylight.yangtools.triemap.ImmutableTrieMap.unsupported; - -import java.util.Collection; -import java.util.Iterator; -import java.util.Map.Entry; -import java.util.Spliterator; - -/** - * {@link AbstractEntrySet} implementation guarding against attempts to mutate the underlying map. - * - * @author Robert Varga - * - * @param the type of entry keys - * @param the type of entry values - */ -final class ImmutableEntrySet extends AbstractEntrySet { - ImmutableEntrySet(final TrieMap map) { - super(map); - } - - @Override - public void clear() { - throw unsupported(); - } - - @Override - public Iterator> iterator() { - return map().immutableIterator(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean remove(final Object o) { - throw unsupported(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean removeAll(final Collection c) { - throw unsupported(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean retainAll(final Collection c) { - throw unsupported(); - } - - @Override - int characteristics() { - return Spliterator.DISTINCT | Spliterator.IMMUTABLE | Spliterator.NONNULL; - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableIterator.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableIterator.java deleted file mode 100644 index e079adb36a..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableIterator.java +++ /dev/null @@ -1,37 +0,0 @@ -/* - * (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 java.util.Map.Entry; - -/** - * Specialized immutable iterator for use with {@link ImmutableEntrySet}. - * - * @author Robert Varga - * - * @param the type of entry keys - * @param the type of entry values - */ -final class ImmutableIterator extends AbstractIterator { - ImmutableIterator(final ImmutableTrieMap map) { - super(map); - } - - @Override - Entry wrapEntry(final Entry entry) { - return entry; - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableKeySet.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableKeySet.java deleted file mode 100644 index bee8975e71..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ImmutableKeySet.java +++ /dev/null @@ -1,70 +0,0 @@ -/* - * (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 static org.opendaylight.yangtools.triemap.ImmutableTrieMap.unsupported; - -import com.google.common.collect.Iterators; -import java.util.Collection; -import java.util.Iterator; -import java.util.Map.Entry; -import java.util.Spliterator; - -/** - * An immutable view of a TrieMap's key set. - * - * @author Robert Varga - * - * @param the type of keys - */ -final class ImmutableKeySet extends AbstractKeySet { - ImmutableKeySet(final TrieMap map) { - super(map); - } - - @Override - public Iterator iterator() { - return Iterators.transform(map().immutableIterator(), Entry::getKey); - } - - @Override - public void clear() { - throw unsupported(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean remove(final Object o) { - throw unsupported(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean retainAll(final Collection c) { - throw unsupported(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean removeAll(final Collection c) { - throw unsupported(); - } - - @Override - int spliteratorCharacteristics() { - return Spliterator.DISTINCT | Spliterator.IMMUTABLE | Spliterator.NONNULL; - } -} 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 ae0a754389..fb267037cc 100644 --- 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 @@ -15,14 +15,6 @@ */ package org.opendaylight.yangtools.triemap; -import static java.util.Objects.requireNonNull; - -import com.google.common.annotations.Beta; -import edu.umd.cs.findbugs.annotations.SuppressFBWarnings; -import java.util.Map; -import java.util.function.BiFunction; -import java.util.function.Function; - /** * An immutable TrieMap. * @@ -30,121 +22,23 @@ import java.util.function.Function; * * @param the type of keys maintained by this map * @param the type of mapped values + * @deprecated use {@link tech.pantheon.triemap.ImmutableTrieMap} instead. */ -@Beta +@Deprecated public final class ImmutableTrieMap extends TrieMap { private static final long serialVersionUID = 1L; - @SuppressFBWarnings(value = "SE_BAD_FIELD", justification = "Handled by SerializationProxy") - private final INode root; - - ImmutableTrieMap(final INode root, final Equivalence equiv) { - super(equiv); - this.root = requireNonNull(root); - } - - @Override - public void clear() { - throw unsupported(); - } - - @Override - public V compute(final K key, final BiFunction remappingFunction) { - throw unsupported(); - } - - @Override - public V computeIfAbsent(final K key, final Function mappingFunction) { - throw unsupported(); - } - - @Override - public V computeIfPresent(final K key, final BiFunction remappingFunction) { - throw unsupported(); - } - - @Override - public V merge(final K key, final V value, final BiFunction remappingFunction) { - throw unsupported(); - } - - @Override - public V put(final K key, final V value) { - throw unsupported(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public void putAll(final Map m) { - throw unsupported(); - } - - @Override - public V putIfAbsent(final K key, final V value) { - throw unsupported(); - } - - @Override - public V remove(final Object key) { - throw unsupported(); - } - - @Override - public boolean remove(final Object key, final Object value) { - throw unsupported(); - } - - @Override - public boolean replace(final K key, final V oldValue, final V newValue) { - throw unsupported(); - } - - @Override - public V replace(final K key, final V value) { - throw unsupported(); - } - - @Override - public int size() { - return root.size(this); + ImmutableTrieMap(final tech.pantheon.triemap.ImmutableTrieMap delegate) { + super(delegate); } @Override public TrieMap mutableSnapshot() { - return new MutableTrieMap<>(equiv(), new INode<>(new Gen(), root.gcasRead(this))); + return new MutableTrieMap<>(delegate().mutableSnapshot()); } @Override public ImmutableTrieMap immutableSnapshot() { return this; } - - @Override - ImmutableEntrySet createEntrySet() { - return new ImmutableEntrySet<>(this); - } - - @Override - ImmutableKeySet createKeySet() { - return new ImmutableKeySet<>(this); - } - - @Override - boolean isReadOnly() { - return true; - } - - @Override - ImmutableIterator iterator() { - return immutableIterator(); - } - - @Override - INode RDCSS_READ_ROOT(final boolean abort) { - return root; - } - - static UnsupportedOperationException unsupported() { - return new UnsupportedOperationException("Attempted to modify a read-only view"); - } } 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 deleted file mode 100644 index 1235323f99..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNode.java +++ /dev/null @@ -1,72 +0,0 @@ -/* - * (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; - -final class LNode extends MainNode { - // Internally-linked single list of of entries - private final LNodeEntries entries; - private final int size; - - private LNode(final LNodeEntries entries, final int size) { - this.entries = entries; - this.size = size; - } - - LNode(final K k1, final V v1, final K k2, final V v2) { - this(LNodeEntries.map(k1, v1, k2, v2), 2); - } - - LNode insertChild(final K key, final V value) { - return new LNode<>(entries.insert(key, value), size + 1); - } - - MainNode removeChild(final LNodeEntry entry, final int hc) { - // While remove() can return null, that case will never happen here, as we are starting off with two entries - // so we cannot observe a null return here. - final LNodeEntries map = entries.remove(entry); - - // If the returned LNode would have only one element, we turn it into a TNode, hence above null return from - // remove() can never happen. - if (size == 2) { - // create it tombed so that it gets compressed on subsequent accesses - return new TNode<>(map.getKey(), map.getValue(), hc); - } - - return new LNode<>(map, size - 1); - } - - MainNode replaceChild(final LNodeEntry entry, final V value) { - return new LNode<>(entries.replace(entry, value), size); - } - - LNodeEntry get(final Equivalence equiv, final K key) { - return entries.findEntry(equiv, key); - } - - LNodeEntries entries() { - return entries; - } - - @Override - 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/LNodeEntries.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntries.java deleted file mode 100644 index 570205e7a9..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntries.java +++ /dev/null @@ -1,129 +0,0 @@ -/* - * (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 com.google.common.base.VerifyException; - -/** - * Similar to Scala's ListMap, this is a single-linked list of set of map entries. Aside from the java.util.Set - * contract, this class fulfills the requirements for an immutable map entryset. - * - * @author Robert Varga - * - * @param the type of keys - * @param the type of values - */ -abstract class LNodeEntries extends LNodeEntry { - private static final class Single extends LNodeEntries { - Single(final K key, final V value) { - super(key, value); - } - - @Override - LNodeEntries next() { - return null; - } - } - - private static final class Multiple extends LNodeEntries { - // Modified during remove only, otherwise final - LNodeEntries next; - - // Used in remove() only - Multiple(final LNodeEntries entry) { - this(entry.getKey(), entry.getValue(), null); - } - - Multiple(final K key, final V value, final LNodeEntries next) { - super(key, value); - this.next = next; - } - - @Override - LNodeEntries next() { - return next; - } - } - - LNodeEntries(final K key, final V value) { - super(key, value); - } - - static LNodeEntries map(final K k1, final V v1, final K k2, final V v2) { - return new Multiple<>(k1, v1, new Single<>(k2, v2)); - } - - /** - * Return the remainder of this list. Useful for implementing Iterator-like contract. Null indicates there are no - * more entries. - * - * @return Remainder of this list, or null if nothing remains - */ - abstract LNodeEntries next(); - - final LNodeEntry findEntry(final Equivalence equiv, final K key) { - // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails. - LNodeEntries entry = this; - do { - if (equiv.equivalent(entry.getKey(), key)) { - return entry; - } - - entry = entry.next(); - } while (entry != null); - - return null; - } - - final LNodeEntries insert(final K key, final V value) { - return new Multiple<>(key, value, this); - } - - final LNodeEntries replace(final LNodeEntry entry, final V value) { - final LNodeEntries removed; - return (removed = remove(entry)) == null ? new Single<>(entry.getKey(), value) - : new Multiple<>(entry.getKey(), value, removed); - } - - final LNodeEntries remove(final LNodeEntry entry) { - if (entry == this) { - return next(); - } - - // This will result in a list with a long tail, i.e last entry storing explicit null. Overhead is amortized - // against the number of entries. We do not retain chains shorter than two, so the worst-case overhead is - // half-a-reference for an entry. - final Multiple ret = new Multiple<>(this); - - Multiple last = ret; - LNodeEntries cur = next(); - while (cur != null) { - // We cannot use equals() here, as it is wired to key equality and we must never compare entries based on - // that property. This method is intended to remove a known reference, so identity is what we want. - if (entry == cur) { - last.next = cur.next(); - return ret; - } - - final Multiple tmp = new Multiple<>(cur); - last.next = tmp; - last = tmp; - cur = cur.next(); - } - - throw new VerifyException(String.format("Failed to find entry %s", entry)); - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntry.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntry.java deleted file mode 100644 index 6a72ccaae4..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntry.java +++ /dev/null @@ -1,69 +0,0 @@ -/* - * (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 edu.umd.cs.findbugs.annotations.SuppressFBWarnings; -import java.util.Map.Entry; - -/** - * A single entry in {@link LNodeEntries}, implements {@link Entry} in order to prevent instantiation of objects for - * iteration. - * - * @author Robert Varga - * - * @param the type of key - * @param the type of value - */ -abstract class LNodeEntry implements Entry { - private final K key; - private final V value; - - LNodeEntry(final K key, final V value) { - this.key = key; - this.value = value; - } - - @Override - public final K getKey() { - return key; - } - - @Override - public final V getValue() { - return value; - } - - @Override - public final V setValue(final V value) { - throw new UnsupportedOperationException(); - } - - @Override - public final int hashCode() { - return EntryUtil.hash(key, value); - } - - @SuppressFBWarnings(value = "EQ_UNUSUAL", justification = "Equality handled by utility methods") - @Override - public final boolean equals(final Object obj) { - return EntryUtil.equal(obj, key, value); - } - - @Override - public final String toString() { - return EntryUtil.string(key, value); - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LookupResult.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LookupResult.java deleted file mode 100644 index b9535e9cf8..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LookupResult.java +++ /dev/null @@ -1,26 +0,0 @@ -/* - * (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; - -/** - * 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 restart. - * - * @author Robert Varga - */ -enum LookupResult { - RESTART; -} 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 deleted file mode 100644 index b791b115d4..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MainNode.java +++ /dev/null @@ -1,62 +0,0 @@ -/* - * (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 MainNode extends BasicNode { - static final int NO_SIZE = -1; - - @SuppressWarnings("rawtypes") - private static final AtomicReferenceFieldUpdater PREV_UPDATER = - AtomicReferenceFieldUpdater.newUpdater(MainNode.class, MainNode.class, "prev"); - - private volatile MainNode prev; - - MainNode() { - this.prev = null; - } - - MainNode(final MainNode prev) { - this.prev = prev; - } - - /** - * 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 casPrev(final MainNode oldval, final MainNode nval) { - return PREV_UPDATER.compareAndSet(this, oldval, nval); - } - - final void writePrev(final MainNode nval) { - prev = nval; - } - - final MainNode readPrev() { - return prev; - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableEntrySet.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableEntrySet.java deleted file mode 100644 index 07f8310063..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableEntrySet.java +++ /dev/null @@ -1,81 +0,0 @@ -/* - * (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.Preconditions.checkArgument; - -import java.util.Iterator; -import java.util.Map.Entry; -import java.util.Spliterator; - -/** - * Support for EntrySet operations required by the Map interface. - * - * @param the type of keys - * @param the type of values - */ -final class MutableEntrySet extends AbstractEntrySet { - MutableEntrySet(final TrieMap map) { - super(map); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean add(final Entry e) { - final K k = e.getKey(); - checkArgument(k != null); - final V v = e.getValue(); - checkArgument(v != null); - - final V prev = map().putIfAbsent(k, v); - return prev == null || !v.equals(prev); - } - - @Override - public void clear() { - map().clear(); - } - - @Override - public Iterator> iterator() { - return map().iterator(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean remove(final Object o) { - if (!(o instanceof Entry)) { - return false; - } - - final Entry e = (Entry) o; - final Object key = e.getKey(); - if (key == null) { - return false; - } - final Object value = e.getValue(); - if (value == null) { - return false; - } - - return map().remove(key, value); - } - - @Override - int characteristics() { - return Spliterator.DISTINCT | Spliterator.CONCURRENT | Spliterator.NONNULL; - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableIterator.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableIterator.java deleted file mode 100644 index 20fb567b90..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableIterator.java +++ /dev/null @@ -1,123 +0,0 @@ -/* - * (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.Preconditions.checkState; - -import edu.umd.cs.findbugs.annotations.SuppressFBWarnings; -import java.util.Map.Entry; - -/** - * Specialized immutable iterator for use with {@link ImmutableEntrySet}. - * - * @author Robert Varga - * - * @param the type of entry keys - * @param the type of entry values - */ -final class MutableIterator extends AbstractIterator { - private final MutableTrieMap mutable; - - private Entry lastReturned; - - MutableIterator(final MutableTrieMap map) { - super(map.immutableSnapshot()); - this.mutable = map; - } - - @Override - public void remove() { - checkState(lastReturned != null); - mutable.remove(lastReturned.getKey()); - lastReturned = null; - } - - @Override - Entry wrapEntry(final Entry entry) { - lastReturned = entry; - return new MutableEntry<>(mutable, entry); - } - - /** - * A mutable view of an entry in the map. Since the backing map is concurrent, its {@link #getValue()} and - * {@link #setValue(Object)} methods cannot guarantee consistency with the base map and may produce surprising - * results when the map is concurrently modified, either directly or via another entry/iterator. - * - *

- * The behavior is similar to what Java 8's ConcurrentHashMap does, which is probably the most consistent handling - * of this case without requiring expensive and revalidation. - */ - private static final class MutableEntry implements Entry { - private final MutableTrieMap map; - private final Entry delegate; - - @SuppressWarnings("null") - private V newValue = null; - - MutableEntry(final MutableTrieMap map, final Entry delegate) { - this.map = map; - this.delegate = delegate; - } - - @Override - public K getKey() { - return delegate.getKey(); - } - - /** - * {@inheritDoc} - * - * @implSpec - * This implementation returns the most uptodate value we have observed via this entry. It does not reflect - * concurrent modifications, nor does it throw {@link IllegalStateException} if the entry is removed. - */ - @Override - public V getValue() { - return newValue != null ? newValue : delegate.getValue(); - } - - /** - * {@inheritDoc} - * - * @implSpec - * This implementation returns the most uptodate value we have observed via this entry. It does not reflect - * concurrent modifications, nor does it throw {@link IllegalStateException} if the entry is removed. - */ - @Override - public V setValue(final V value) { - final V ret = getValue(); - map.put(getKey(), value); - newValue = value; - return ret; - } - - @Override - public int hashCode() { - return EntryUtil.hash(getKey(), getValue()); - } - - @SuppressFBWarnings(value = "EQ_UNUSUAL", justification = "Equality handled by utility methods") - @Override - public boolean equals(final Object obj) { - return EntryUtil.equal(obj, getKey(), getValue()); - } - - @Override - public String toString() { - return EntryUtil.string(getKey(), getValue()); - } - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableKeySet.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableKeySet.java deleted file mode 100644 index 1910cb1ebf..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableKeySet.java +++ /dev/null @@ -1,69 +0,0 @@ -/* - * (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.Iterator; -import java.util.Spliterator; - -/** - * A mutable view of a TrieMap's key set. - * - * @author Robert Varga - * - * @param the type of keys - */ -final class MutableKeySet extends AbstractKeySet { - MutableKeySet(final MutableTrieMap map) { - super(map); - } - - @Override - public Iterator iterator() { - final AbstractIterator itr = map().iterator(); - return new Iterator() { - @Override - public boolean hasNext() { - return itr.hasNext(); - } - - @Override - public K next() { - return itr.next().getKey(); - } - - @Override - public void remove() { - itr.remove(); - } - }; - } - - @Override - public void clear() { - map().clear(); - } - - @Override - @SuppressWarnings("checkstyle:parameterName") - public boolean remove(final Object o) { - return map().remove(o) != null; - } - - @Override - int spliteratorCharacteristics() { - return Spliterator.DISTINCT | Spliterator.CONCURRENT | Spliterator.NONNULL; - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableTrieMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableTrieMap.java index adbf4997f0..31f749a6c2 100644 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableTrieMap.java +++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableTrieMap.java @@ -15,17 +15,6 @@ */ package org.opendaylight.yangtools.triemap; -import static com.google.common.base.Preconditions.checkState; -import static java.util.Objects.requireNonNull; -import static org.opendaylight.yangtools.triemap.PresencePredicate.ABSENT; -import static org.opendaylight.yangtools.triemap.PresencePredicate.PRESENT; - -import com.google.common.annotations.Beta; -import com.google.common.base.Verify; -import edu.umd.cs.findbugs.annotations.SuppressFBWarnings; -import java.util.Optional; -import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; - /** * A mutable TrieMap. * @@ -33,236 +22,23 @@ import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; * * @param the type of keys maintained by this map * @param the type of mapped values + * @deprecated use {@link tech.pantheon.triemap.MutableTrieMap} instead. */ -@Beta +@Deprecated public final class MutableTrieMap extends TrieMap { private static final long serialVersionUID = 1L; - @SuppressWarnings("rawtypes") - private static final AtomicReferenceFieldUpdater ROOT_UPDATER = - AtomicReferenceFieldUpdater.newUpdater(MutableTrieMap.class, Object.class, "root"); - - private volatile Object root; - - MutableTrieMap(final Equivalence equiv) { - this(equiv, newRootNode()); - } - - MutableTrieMap(final Equivalence equiv, final INode root) { - super(equiv); - this.root = requireNonNull(root); - } - - @Override - public void clear() { - INode r; - do { - r = RDCSS_READ_ROOT(); - } while (!RDCSS_ROOT(r, r.gcasRead(this), newRootNode())); - } - - @Override - public V put(final K key, final V value) { - final K k = requireNonNull(key); - return toNullable(insertifhc(k, computeHash(k), requireNonNull(value), null)); - } - - @Override - public V putIfAbsent(final K key, final V value) { - final K k = requireNonNull(key); - return toNullable(insertifhc(k, computeHash(k), requireNonNull(value), ABSENT)); - } - - @Override - public V remove(final Object key) { - @SuppressWarnings("unchecked") - final K k = (K) requireNonNull(key); - return toNullable(removehc(k, null, computeHash(k))); - } - - @SuppressFBWarnings(value = "NP_PARAMETER_MUST_BE_NONNULL_BUT_MARKED_AS_NULLABLE", - justification = "API contract allows null value, but we do not") - @Override - public boolean remove(final Object key, final Object value) { - @SuppressWarnings("unchecked") - final K k = (K) requireNonNull(key); - return removehc(k, requireNonNull(value), computeHash(k)).isPresent(); - } - - @Override - public boolean replace(final K key, final V oldValue, final V newValue) { - final K k = requireNonNull(key); - return insertifhc(k, computeHash(k), requireNonNull(newValue), requireNonNull(oldValue)).isPresent(); - } - - @Override - public V replace(final K key, final V value) { - final K k = requireNonNull(key); - return toNullable(insertifhc(k, computeHash(k), requireNonNull(value), PRESENT)); - } - - @Override - public int size() { - return immutableSnapshot().size(); - } - - private INode snapshot() { - INode r; - do { - r = RDCSS_READ_ROOT(); - } while (!RDCSS_ROOT(r, r.gcasRead(this), r.copyToGen(new Gen(), this))); - - return r; + MutableTrieMap(final tech.pantheon.triemap.MutableTrieMap delegate) { + super(delegate); } @Override public ImmutableTrieMap immutableSnapshot() { - return new ImmutableTrieMap<>(snapshot(), equiv()); + return new ImmutableTrieMap<>(delegate().immutableSnapshot()); } @Override public MutableTrieMap mutableSnapshot() { - return new MutableTrieMap<>(equiv(), snapshot().copyToGen(new Gen(), this)); - } - - @Override - MutableEntrySet createEntrySet() { - // FIXME: it would be nice to have a ReadWriteTrieMap with read-only iterator - // if (readOnlyEntrySet) return ImmutableEntrySet(this); - return new MutableEntrySet<>(this); - } - - @Override - MutableKeySet createKeySet() { - return new MutableKeySet<>(this); - } - - @Override - MutableIterator iterator() { - return new MutableIterator<>(this); - } - - @Override - boolean isReadOnly() { - return false; - } - - @Override - @SuppressWarnings("unchecked") - INode RDCSS_READ_ROOT(final boolean abort) { - final Object r = /* READ */ root; - if (r instanceof INode) { - return (INode) r; - } - - checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r); - return RDCSS_Complete(abort); - } - - void add(final K key, final V value) { - final K k = requireNonNull(key); - inserthc(k, computeHash(k), requireNonNull(value)); - } - - private static INode newRootNode() { - final Gen gen = new Gen(); - return new INode<>(gen, new CNode<>(gen)); - } - - private void inserthc(final K key, final int hc, final V value) { - // TODO: this is called from serialization only, which means we should not be observing any races, - // hence we should not need to pass down the entire tree, just equality (I think). - final boolean success = RDCSS_READ_ROOT().recInsert(key, value, hc, 0, null, this); - Verify.verify(success, "Concurrent modification during serialization of map %s", this); - } - - private Optional insertifhc(final K key, final int hc, final V value, final Object cond) { - Optional res; - do { - // Keep looping as long as we do not get a reply - res = RDCSS_READ_ROOT().recInsertIf(key, value, hc, cond, 0, null, this); - } while (res == null); - - return res; - } - - private Optional removehc(final K key, final Object cond, final int hc) { - Optional res; - do { - // Keep looping as long as we do not get a reply - res = RDCSS_READ_ROOT().recRemove(key, cond, hc, 0, null, this); - } while (res == null); - - return res; - } - - private boolean CAS_ROOT(final Object ov, final Object nv) { - return ROOT_UPDATER.compareAndSet(this, ov, nv); - } - - private boolean RDCSS_ROOT(final INode ov, final MainNode expectedmain, final INode nv) { - final RDCSS_Descriptor desc = new RDCSS_Descriptor<>(ov, expectedmain, nv); - if (CAS_ROOT(ov, desc)) { - RDCSS_Complete(false); - return /* READ */desc.committed; - } - - return false; - } - - @SuppressWarnings("unchecked") - private INode RDCSS_Complete(final boolean abort) { - while (true) { - final Object r = /* READ */ root; - if (r instanceof INode) { - return (INode) r; - } - - checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r); - final RDCSS_Descriptor desc = (RDCSS_Descriptor) r; - final INode ov = desc.old; - final MainNode exp = desc.expectedmain; - final INode nv = desc.nv; - - if (abort) { - if (CAS_ROOT(desc, ov)) { - return ov; - } - - // Tail recursion: return RDCSS_Complete(abort); - continue; - } - - final MainNode oldmain = ov.gcasRead(this); - if (oldmain == exp) { - if (CAS_ROOT(desc, nv)) { - desc.committed = true; - return nv; - } - - // Tail recursion: return RDCSS_Complete(abort); - continue; - } - - if (CAS_ROOT(desc, ov)) { - return ov; - } - - // Tail recursion: return RDCSS_Complete(abort); - } - } - - private static final class RDCSS_Descriptor { - final INode old; - final MainNode expectedmain; - final INode nv; - - volatile boolean committed = false; - - RDCSS_Descriptor(final INode old, final MainNode expectedmain, final INode nv) { - this.old = old; - this.expectedmain = expectedmain; - this.nv = nv; - } + return new MutableTrieMap<>(delegate().mutableSnapshot()); } } diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/PresencePredicate.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/PresencePredicate.java deleted file mode 100644 index 297b52bf17..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/PresencePredicate.java +++ /dev/null @@ -1,27 +0,0 @@ -/* - * (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; - -/** - * Presence predicate. These are specialized objects passed down from callers to indicate an assertion about - * whether a mapping is required. - * - * @author Robert Varga - */ -enum PresencePredicate { - ABSENT, - PRESENT; -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/SNode.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/SNode.java deleted file mode 100644 index 880b61ffd5..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/SNode.java +++ /dev/null @@ -1,68 +0,0 @@ -/* - * (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 edu.umd.cs.findbugs.annotations.SuppressFBWarnings; - -final class SNode extends BasicNode implements EntryNode { - final K key; - final V value; - final int hc; - - SNode(final K key, final V value, final int hc) { - this.key = key; - this.value = value; - this.hc = hc; - } - - SNode copy() { - return new SNode<>(key, value, hc); - } - - TNode copyTombed() { - return new TNode<>(key, value, hc); - } - - SNode copyUntombed() { - return new SNode<>(key, value, hc); - } - - @Override - public K getKey() { - return key; - } - - @Override - public V getValue() { - return value; - } - - @Override - public int hashCode() { - return EntryUtil.hash(key, value); - } - - @SuppressFBWarnings(value = "EQ_UNUSUAL", justification = "Equality handled by utility methods") - @Override - public boolean equals(final Object obj) { - return EntryUtil.equal(obj, key, value); - } - - @Override - public String toString() { - return EntryUtil.string(key, value); - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/SerializationProxy.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/SerializationProxy.java deleted file mode 100644 index 3e00d85a76..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/SerializationProxy.java +++ /dev/null @@ -1,83 +0,0 @@ -/* - * (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.Preconditions.checkArgument; -import static java.util.Objects.requireNonNull; - -import com.google.common.base.Verify; -import java.io.Externalizable; -import java.io.IOException; -import java.io.ObjectInput; -import java.io.ObjectOutput; -import java.io.ObjectStreamException; -import java.util.Map.Entry; - -/** - * External serialization object for use with TrieMap objects. This hides the implementation details, such as object - * hierarchy. It also makes handling read-only snapshots more elegant. - * - * @author Robert Varga - */ -final class SerializationProxy implements Externalizable { - private static final long serialVersionUID = 1L; - - private TrieMap map; - private boolean readOnly; - - @SuppressWarnings("checkstyle:redundantModifier") - public SerializationProxy() { - // For Externalizable - } - - @SuppressWarnings({ "unchecked", "rawtypes" }) - SerializationProxy(final ImmutableTrieMap map, final boolean readOnly) { - this.map = (TrieMap) requireNonNull(map); - this.readOnly = readOnly; - } - - @Override - public void writeExternal(final ObjectOutput out) throws IOException { - out.writeObject(map.equiv()); - out.writeInt(map.size()); - for (Entry e : map.entrySet()) { - out.writeObject(e.getKey()); - out.writeObject(e.getValue()); - } - out.writeBoolean(readOnly); - } - - @Override - public void readExternal(final ObjectInput in) throws IOException, ClassNotFoundException { - @SuppressWarnings("unchecked") - final Equivalence equiv = (Equivalence) in.readObject(); - checkArgument(equiv != null); - - final MutableTrieMap tmp = new MutableTrieMap<>(equiv); - final int size = in.readInt(); - checkArgument(size >= 0); - - for (int i = 0; i < size; ++i) { - tmp.add(in.readObject(), in.readObject()); - } - - map = in.readBoolean() ? tmp.immutableSnapshot() : tmp; - } - - private Object readResolve() throws ObjectStreamException { - return Verify.verifyNotNull(map); - } -} 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 deleted file mode 100644 index aa6c7d9802..0000000000 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TNode.java +++ /dev/null @@ -1,78 +0,0 @@ -/* - * (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 edu.umd.cs.findbugs.annotations.SuppressFBWarnings; - -final class TNode extends MainNode implements EntryNode { - final K key; - final V value; - final int hc; - - TNode(final K key, final V value, final int hc) { - this.key = key; - this.value = value; - this.hc = hc; - } - - TNode copy() { - return new TNode<>(key, value, hc); - } - - TNode copyTombed() { - return new TNode<>(key, value, hc); - } - - SNode copyUntombed() { - return new SNode<>(key, value, hc); - } - - @Override - int trySize() { - return 1; - } - - @Override - int size(final ImmutableTrieMap ct) { - return 1; - } - - @Override - public K getKey() { - return key; - } - - @Override - public V getValue() { - return value; - } - - @Override - public int hashCode() { - return EntryUtil.hash(key, value); - } - - @SuppressFBWarnings(value = "EQ_UNUSUAL", justification = "Equality handled by utility methods") - @Override - public boolean equals(final Object obj) { - return EntryUtil.equal(obj, key, value); - } - - @Override - public String toString() { - return EntryUtil.string(key, value); - } -} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java index 503572bd1d..b5db32c495 100644 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java +++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java @@ -16,15 +16,15 @@ package org.opendaylight.yangtools.triemap; import static java.util.Objects.requireNonNull; -import static org.opendaylight.yangtools.triemap.LookupResult.RESTART; -import com.google.common.annotations.Beta; -import java.io.ObjectStreamException; +import com.google.common.collect.ForwardingObject; import java.io.Serializable; -import java.util.AbstractMap; -import java.util.Optional; +import java.util.Collection; +import java.util.Map; import java.util.Set; import java.util.concurrent.ConcurrentMap; +import java.util.function.BiFunction; +import java.util.function.Function; /** * This is a port of Scala's TrieMap class from the Scala Collections library. This implementation does not support @@ -36,22 +36,20 @@ import java.util.concurrent.ConcurrentMap; * * @param the type of keys maintained by this map * @param the type of mapped values + * @deprecated use {@link tech.pantheon.triemap.TrieMap} instead. */ -@Beta -public abstract class TrieMap extends AbstractMap implements ConcurrentMap, Serializable { +@Deprecated +public abstract class TrieMap extends ForwardingObject implements ConcurrentMap, Serializable { private static final long serialVersionUID = 1L; - private final Equivalence equiv; + private final tech.pantheon.triemap.TrieMap delegate; - private AbstractEntrySet entrySet; - private AbstractKeySet keySet; - - TrieMap(final Equivalence equiv) { - this.equiv = equiv; + TrieMap(final tech.pantheon.triemap.TrieMap delegate) { + this.delegate = requireNonNull(delegate); } public static MutableTrieMap create() { - return new MutableTrieMap<>(Equivalence.equals()); + return new MutableTrieMap<>(tech.pantheon.triemap.TrieMap.create()); } /** @@ -91,138 +89,118 @@ public abstract class TrieMap extends AbstractMap implements Concurr @Override public final boolean containsKey(final Object key) { - return get(key) != null; + return delegate.containsKey(key); } @Override public final boolean containsValue(final Object value) { - return super.containsValue(requireNonNull(value)); + return delegate.containsValue(value); } @Override public final Set> entrySet() { - final AbstractEntrySet ret; - return (ret = entrySet) != null ? ret : (entrySet = createEntrySet()); + return delegate.entrySet(); } @Override public final Set keySet() { - final AbstractKeySet ret; - return (ret = keySet) != null ? ret : (keySet = createKeySet()); + return delegate.keySet(); } @Override public final V get(final Object key) { - @SuppressWarnings("unchecked") - final K k = (K) requireNonNull(key); - return lookuphc(k, computeHash(k)); + return delegate.get(key); } @Override - public abstract void clear(); + public final void clear() { + delegate.clear(); + } @Override - public abstract V put(K key, V value); + public final V put(final K key, final V value) { + return delegate.put(key, value); + } @Override - public abstract V putIfAbsent(K key, V value); + public final V putIfAbsent(final K key, final V value) { + return delegate.putIfAbsent(key, value); + } @Override - public abstract V remove(Object key); + public final V remove(final Object key) { + return delegate.remove(key); + } @Override - public abstract boolean remove(Object key, Object value); + public final boolean remove(final Object key, final Object value) { + return delegate.remove(key, value); + } @Override - public abstract boolean replace(K key, V oldValue, V newValue); + public final boolean replace(final K key, final V oldValue, final V newValue) { + return delegate.replace(key, oldValue, newValue); + } @Override - public abstract V replace(K key, V value); + public final V replace(final K key, final V value) { + return delegate.replace(key, value); + } @Override - public abstract int size(); - - /* internal methods implemented by subclasses */ - - abstract AbstractEntrySet createEntrySet(); - - abstract AbstractKeySet createKeySet(); - - abstract boolean isReadOnly(); - - abstract INode RDCSS_READ_ROOT(boolean abort); - - /** - * Return an iterator over a TrieMap. - * - *

- * If this is a read-only snapshot, it would return a read-only iterator. - * - *

- * If it is the original TrieMap or a non-readonly snapshot, it would return - * an iterator that would allow for updates. - * - * @return An iterator. - */ - abstract AbstractIterator iterator(); - - /* internal methods provided for subclasses */ - - /** - * Return an iterator over a TrieMap. This is a read-only iterator. - * - * @return A read-only iterator. - */ - final ImmutableIterator immutableIterator() { - return new ImmutableIterator<>(immutableSnapshot()); + public final int size() { + return delegate.size(); } - @SuppressWarnings("null") - static V toNullable(final Optional opt) { - return opt.orElse(null); + @Override + public final boolean isEmpty() { + return delegate.isEmpty(); } - final int computeHash(final K key) { - return equiv.hash(key); + @Override + public final void putAll(final Map m) { + delegate.putAll(m); } - final Object writeReplace() throws ObjectStreamException { - return new SerializationProxy(immutableSnapshot(), isReadOnly()); + @Override + public final Collection values() { + return delegate.values(); } - /* package-protected utility methods */ - - final Equivalence equiv() { - return equiv; + @Override + public final V compute(final K key, final BiFunction remappingFunction) { + return delegate.compute(key, remappingFunction); } - final INode readRoot() { - return RDCSS_READ_ROOT(false); + @Override + public final V computeIfAbsent(final K key, final Function mappingFunction) { + return delegate.computeIfAbsent(key, mappingFunction); } - // FIXME: abort = false by default - final INode readRoot(final boolean abort) { - return RDCSS_READ_ROOT(abort); + @Override + public final V computeIfPresent(final K key, + final BiFunction remappingFunction) { + return delegate.computeIfPresent(key, remappingFunction); } - final INode RDCSS_READ_ROOT() { - return RDCSS_READ_ROOT(false); + @Override + public final V merge(final K key, final V value, + final BiFunction remappingFunction) { + return delegate.merge(key, value, remappingFunction); } - final boolean equal(final K k1, final K k2) { - return equiv.equivalent(k1, k2); + @Override + public final int hashCode() { + return delegate.hashCode(); } - /* private implementation methods */ - - @SuppressWarnings("unchecked") - private V lookuphc(final K key, final int hc) { - Object res; - do { - // Keep looping as long as RESTART is being indicated - res = RDCSS_READ_ROOT().recLookup(key, hc, 0, null, this); - } while (res == RESTART); + @Override + public final boolean equals(final Object o) { + return delegate.equals(o); + } - return (V) res; + @Override + protected final tech.pantheon.triemap.TrieMap delegate() { + return delegate; } } diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/LNodeEntriesTest.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/LNodeEntriesTest.java deleted file mode 100644 index 96e64794f9..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/LNodeEntriesTest.java +++ /dev/null @@ -1,37 +0,0 @@ -/* - * (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 static org.junit.Assert.assertNull; - -import org.junit.Test; - -public class LNodeEntriesTest { - /** - * Test if Listmap.get() does not cause stack overflow. - */ - @Test - public void testGetOverflow() { - LNodeEntries map = LNodeEntries.map(1, Boolean.TRUE, 2, Boolean.TRUE); - - // 30K seems to be enough to trigger the problem locally - for (int i = 3; i < 30000; ++i) { - map = map.insert(i, Boolean.TRUE); - } - - assertNull(map.findEntry(Equivalence.equals(), 0)); - } -} diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/SnapshotTest.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/SnapshotTest.java index bed17f245e..a77ab91aa8 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/SnapshotTest.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/SnapshotTest.java @@ -23,6 +23,7 @@ import java.util.Map; import org.junit.Before; import org.junit.Test; +@Deprecated public class SnapshotTest { private TrieMap map; diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestCNodeFlagCollision.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestCNodeFlagCollision.java index c99cc21b9e..c5d5ca6d2d 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestCNodeFlagCollision.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestCNodeFlagCollision.java @@ -21,6 +21,7 @@ import static org.junit.Assert.assertSame; import java.util.Map; import org.junit.Test; +@Deprecated public class TestCNodeFlagCollision { @Test public void testCNodeFlagCollision() { diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestCNodeInsertionIncorrectOrder.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestCNodeInsertionIncorrectOrder.java index 3c0f354768..9d34781f4a 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestCNodeInsertionIncorrectOrder.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestCNodeInsertionIncorrectOrder.java @@ -20,6 +20,7 @@ import static org.junit.Assert.assertSame; import java.util.Map; import org.junit.Test; +@Deprecated public class TestCNodeInsertionIncorrectOrder { @Test diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapPutIfAbsent.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapPutIfAbsent.java deleted file mode 100644 index 3c9ba14914..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapPutIfAbsent.java +++ /dev/null @@ -1,60 +0,0 @@ -/* - * (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 static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertNull; -import static org.junit.Assert.assertSame; - -import java.util.Map; -import java.util.concurrent.ConcurrentMap; -import org.junit.Test; - -public class TestConcurrentMapPutIfAbsent { - private static final int COUNT = 50 * 1000; - - @Test - public void testConcurrentMapPutIfAbsent() { - final ConcurrentMap map = TrieMap.create(); - - for (int i = 0; i < COUNT; i++) { - assertNull(map.putIfAbsent(i, i)); - assertEquals(Integer.valueOf(i), map.putIfAbsent(i, i)); - } - } - - @Test - public void testConflictingHash() { - final ZeroHashInt k1 = new ZeroHashInt(1); - final ZeroHashInt k2 = new ZeroHashInt(2); - final ZeroHashInt k3 = new ZeroHashInt(3); - final ZeroHashInt k3dup = new ZeroHashInt(3); - final ZeroHashInt v1 = new ZeroHashInt(4); - final ZeroHashInt v2 = new ZeroHashInt(5); - final ZeroHashInt v3 = new ZeroHashInt(6); - - final Map map = TrieMap.create(); - // Pre-populate an LNode - assertNull(map.putIfAbsent(k1, v1)); - assertNull(map.putIfAbsent(k2, v2)); - assertNull(map.putIfAbsent(k3, v3)); - - // Check with identical key - assertSame(v3, map.putIfAbsent(k3, v3)); - // Check with equivalent key - assertSame(v3, map.putIfAbsent(k3dup, v3)); - } -} diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapRemove.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapRemove.java deleted file mode 100644 index b4b9001580..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapRemove.java +++ /dev/null @@ -1,64 +0,0 @@ -/* - * (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 static org.junit.Assert.assertFalse; -import static org.junit.Assert.assertNull; -import static org.junit.Assert.assertTrue; - -import java.util.Map; -import java.util.concurrent.ConcurrentMap; -import org.junit.Test; - -public class TestConcurrentMapRemove { - private static final int COUNT = 50 * 1000; - - @Test - public void testConcurrentMapRemove() { - final ConcurrentMap map = TrieMap.create(); - - for (int i = 128; i < COUNT; i++) { - assertFalse(map.remove(i, i)); - assertNull(map.put(i, i)); - assertFalse(map.remove(i, "lol")); - assertTrue(map.containsKey(i)); - assertTrue(map.remove(i, i)); - assertFalse(map.containsKey(i)); - assertNull(map.put(i, i)); - } - } - - @Test - public void testConflictingHash() { - final ZeroHashInt k1 = new ZeroHashInt(1); - final ZeroHashInt k2 = new ZeroHashInt(2); - final ZeroHashInt k3 = new ZeroHashInt(3); - final ZeroHashInt k3dup = new ZeroHashInt(3); - final ZeroHashInt v1 = new ZeroHashInt(4); - final ZeroHashInt v2 = new ZeroHashInt(5); - final ZeroHashInt v3 = new ZeroHashInt(6); - final ZeroHashInt v3dup = new ZeroHashInt(6); - - final Map map = TrieMap.create(); - // Pre-populate an LNode - assertNull(map.putIfAbsent(k1, v1)); - assertNull(map.putIfAbsent(k2, v2)); - assertNull(map.putIfAbsent(k3, v3)); - - assertFalse(map.remove(k3, v2)); - assertTrue(map.remove(k3dup, v3dup)); - } -} diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapReplace.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapReplace.java deleted file mode 100644 index fe09e1acf9..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestConcurrentMapReplace.java +++ /dev/null @@ -1,86 +0,0 @@ -/* - * (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 static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertFalse; -import static org.junit.Assert.assertNull; -import static org.junit.Assert.assertTrue; - -import java.util.Map; -import java.util.concurrent.ConcurrentMap; -import org.junit.Test; - -public class TestConcurrentMapReplace { - private static final int COUNT = 50 * 1000; - - @Test - public void testConcurrentMapReplace() { - final ConcurrentMap map = TrieMap.create(); - - for (int i = 0; i < COUNT; i++) { - assertNull(map.replace(i, "lol")); - assertFalse(map.replace(i, i, "lol2")); - assertNull(map.put(i, i)); - assertEquals(Integer.valueOf(i), map.replace(i, "lol")); - assertFalse(map.replace(i, i, "lol2")); - assertTrue(map.replace(i, "lol", i)); - } - } - - @Test - public void testConflictingHash() { - final ZeroHashInt k1 = new ZeroHashInt(1); - final ZeroHashInt k2 = new ZeroHashInt(2); - final ZeroHashInt k3 = new ZeroHashInt(3); - final ZeroHashInt k3dup = new ZeroHashInt(3); - final ZeroHashInt v1 = new ZeroHashInt(4); - final ZeroHashInt v2 = new ZeroHashInt(5); - final ZeroHashInt v3 = new ZeroHashInt(6); - final ZeroHashInt v3dup = new ZeroHashInt(6); - final ZeroHashInt k4 = new ZeroHashInt(7); - - final Map map = TrieMap.create(); - assertNull(map.put(k3, v3)); - - // First check for SNode - assertNull(map.replace(k1, v1)); - assertFalse(map.replace(k1, v1, v2)); - assertFalse(map.replace(k3, v1, v3)); - assertFalse(map.replace(k3dup, v1, v3dup)); - assertTrue(map.replace(k3dup, v3dup, v1)); - assertTrue(map.replace(k3dup, v1, v3)); - - // Bump up to LNode - assertNull(map.put(k1, v1)); - assertNull(map.put(k2, v2)); - - // Completely mismatched - assertFalse(map.replace(k1, v2, v3)); - - // Identical value match - assertTrue(map.replace(k2, v2, v3)); - // Equivalent value match - assertTrue(map.replace(k2, v3dup, v2)); - - // Equivalent match - assertTrue(map.replace(k3dup, v3dup, v2)); - - // No match - assertNull(map.replace(k4, v1)); - assertFalse(map.replace(k4, v1, v2)); - } -} diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java deleted file mode 100644 index 23b70873fc..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java +++ /dev/null @@ -1,107 +0,0 @@ -/* - * (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 static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertNull; -import static org.junit.Assert.assertTrue; - -import org.junit.Test; - -public class TestDelete { - @Test(expected = NullPointerException.class) - public void testNullSimple() { - TrieMap.create().remove(null); - } - - @Test(expected = NullPointerException.class) - public void testNullKey() { - TrieMap.create().remove(null, ""); - } - - @Test(expected = NullPointerException.class) - public void testNullValue() { - TrieMap.create().remove("", null); - } - - @Test(expected = NullPointerException.class) - public void testNullBoth() { - TrieMap.create().remove(null, null); - } - - @Test - public void testClear() { - final TrieMap bt = TrieMap.create(); - bt.put(1, 1); - bt.clear(); - assertTrue(bt.isEmpty()); - assertEquals(0, bt.size()); - } - - @Test - public void testDelete() { - final TrieMap bt = TrieMap.create(); - - for (int i = 0; i < 10000; i++) { - assertNull(bt.put(Integer.valueOf(i), Integer.valueOf(i))); - assertEquals(Integer.valueOf(i), bt.get(Integer.valueOf(i))); - } - - checkAddInsert(bt, 536); - checkAddInsert(bt, 4341); - checkAddInsert(bt, 8437); - - for (int i = 0; i < 10000; i++) { - boolean removed = null != bt.remove(Integer.valueOf(i)); - assertTrue(removed); - final Object lookup = bt.get(Integer.valueOf(i)); - assertNull(lookup); - } - - bt.toString(); - } - - /** - * Test if the Map.remove(Object, Object) method works correctly for hash collisions, which are handled by LNode. - */ - @Test - public void testRemoveObjectLNode() { - final TrieMap bt = TrieMap.create(); - - for (int i = 0; i < 100; i++) { - final ZeroHashInt v = new ZeroHashInt(i); - assertNull(bt.put(v, v)); - } - - for (int i = 0; i < 100; i++) { - final ZeroHashInt v = new ZeroHashInt(i); - assertTrue(bt.remove(v, v)); - } - } - - private static void checkAddInsert(final TrieMap bt, final int k) { - final Integer v = Integer.valueOf(k); - bt.remove(v); - Integer foundV = bt.get(v); - assertNull(foundV); - assertNull(bt.put(v, v)); - foundV = bt.get(v); - assertEquals(v, foundV); - - assertEquals(v, bt.put(v, Integer.valueOf(-1))); - assertEquals(Integer.valueOf(-1), bt.put(v, v)); - } -} diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisions.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisions.java index 6884911075..2135af380c 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisions.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisions.java @@ -21,6 +21,7 @@ import static org.junit.Assert.assertNull; import org.junit.Test; +@Deprecated public class TestHashCollisions { @Test public void testHashCollisions() { diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisionsRemove.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisionsRemove.java index 74ae1f9b79..7d0962471d 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisionsRemove.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisionsRemove.java @@ -21,6 +21,7 @@ import static org.junit.Assert.assertTrue; import java.util.Map; import org.junit.Test; +@Deprecated public class TestHashCollisionsRemove { private static final int COUNT = 50000; diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisionsRemoveIterator.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisionsRemoveIterator.java index b564770dff..37f234eb00 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisionsRemoveIterator.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisionsRemoveIterator.java @@ -25,6 +25,7 @@ import java.util.Map; import java.util.Map.Entry; import org.junit.Test; +@Deprecated public class TestHashCollisionsRemoveIterator { private static final int COUNT = 50000; diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java index 9a4bc7175a..138b29e068 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java @@ -20,6 +20,7 @@ import static org.junit.Assert.assertNull; import org.junit.Test; +@Deprecated public class TestInsert { @Test public void testInsert() { diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInstantiationSpeed.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInstantiationSpeed.java deleted file mode 100644 index 52166037c7..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInstantiationSpeed.java +++ /dev/null @@ -1,67 +0,0 @@ -/* - * (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 com.google.common.base.Stopwatch; -import java.util.concurrent.TimeUnit; -import org.junit.Ignore; -import org.junit.Test; -import org.slf4j.Logger; -import org.slf4j.LoggerFactory; - -public class TestInstantiationSpeed { - private static final Logger LOG = LoggerFactory.getLogger(TestInstantiationSpeed.class); - private static final int COUNT = 1000000; - private static final int ITERATIONS = 10; - private static final int WARMUP = 10; - - private static Stopwatch runIteration() { - final TrieMap[] maps = new TrieMap[COUNT]; - - final Stopwatch watch = Stopwatch.createStarted(); - for (int i = 0; i < COUNT; ++i) { - maps[i] = TrieMap.create(); - } - watch.stop(); - - // Do not allow optimizations - LOG.trace("Maps: {}", (Object) maps); - return watch; - } - - private static long elapsedToNs(final Stopwatch watch) { - return watch.elapsed(TimeUnit.NANOSECONDS) / COUNT; - } - - @Ignore - @Test - public void testInstantiation() { - - for (int i = 0; i < WARMUP; ++i) { - final Stopwatch time = runIteration(); - LOG.debug("Warmup {} took {} ({} ns)", i, time, elapsedToNs(time)); - } - - long acc = 0; - for (int i = 0; i < ITERATIONS; ++i) { - final Stopwatch time = runIteration(); - LOG.debug("Iteration {} took {} ({} ns)", i, time, elapsedToNs(time)); - acc += time.elapsed(TimeUnit.NANOSECONDS); - } - - LOG.info("Instantiation cost {} ns", acc / ITERATIONS / COUNT); - } -} diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java deleted file mode 100644 index f3aaea8969..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java +++ /dev/null @@ -1,126 +0,0 @@ -/* - * (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 static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertFalse; -import static org.junit.Assert.assertNull; -import static org.junit.Assert.assertSame; -import static org.junit.Assert.assertTrue; - -import java.util.HashSet; -import java.util.Iterator; -import java.util.Map; -import java.util.Map.Entry; -import java.util.NoSuchElementException; -import java.util.Random; -import java.util.Set; -import org.junit.Test; - -public class TestMapIterator { - @Test - public void testMapIterator() { - final Random random = new Random(); - - for (int i = 0; i < 60 * 1000; i += 400 + random.nextInt(400)) { - final Map bt = TrieMap.create(); - for (int j = 0; j < i; j++) { - assertNull(bt.put(Integer.valueOf(j), Integer.valueOf(j))); - } - int count = 0; - final Set set = new HashSet<>(); - for (final Entry e : bt.entrySet()) { - set.add(e.getKey()); - count++; - } - for (final Integer j : set) { - assertTrue(bt.containsKey(j)); - } - for (final Integer j : bt.keySet()) { - assertTrue(set.contains(j)); - } - - assertEquals(i, count); - assertEquals(i, bt.size()); - - for (Entry e : bt.entrySet()) { - assertSame(e.getValue(), bt.get(e.getKey())); - e.setValue(e.getValue() + 1); - assertEquals((Object)e.getValue(), e.getKey() + 1); - assertEquals(e.getValue(), bt.get(e.getKey())); - e.setValue(e.getValue() - 1); - } - - final Iterator it = bt.keySet().iterator(); - while (it.hasNext()) { - final Integer k = it.next(); - assertTrue(bt.containsKey(k)); - it.remove(); - assertFalse(bt.containsKey(k)); - } - - assertEquals(0, bt.size()); - assertTrue(bt.isEmpty()); - } - } - - @Test - public void testMapImmutableIterator() { - final Random random = new Random(); - - for (int i = 0; i < 60 * 1000; i += 400 + random.nextInt(400)) { - final Map bt = TrieMap.create(); - for (int j = 0; j < i; j++) { - assertNull(bt.put(Integer.valueOf(j), Integer.valueOf(j))); - } - int count = 0; - final Set set = new HashSet<>(); - for (final Entry e : bt.entrySet()) { - set.add(e.getKey()); - count++; - } - for (final Integer j : set) { - assertTrue(bt.containsKey(j)); - } - for (final Integer j : bt.keySet()) { - assertTrue(set.contains(j)); - } - - assertEquals(i, count); - assertEquals(i, bt.size()); - } - } - - private static void failAdvance(final Iterator it) { - assertFalse(it.hasNext()); - it.next(); - } - - @Test(expected = NoSuchElementException.class) - public void testEmptyIterator() { - failAdvance(TrieMap.create().iterator()); - } - - @Test(expected = NoSuchElementException.class) - public void testEmptyReadOnlyIterator() { - failAdvance(TrieMap.create().immutableIterator()); - } - - @Test(expected = NoSuchElementException.class) - public void testEmptyReadOnlySnapshotIterator() { - failAdvance(TrieMap.create().immutableSnapshot().iterator()); - } -} diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadAddDelete.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadAddDelete.java index 4b2d78ad83..bbfe70ed3d 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadAddDelete.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadAddDelete.java @@ -27,6 +27,7 @@ import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; +@Deprecated public class TestMultiThreadAddDelete { private static final Logger LOG = LoggerFactory.getLogger(TestMultiThreadAddDelete.class); private static final int RETRIES = 1; @@ -81,19 +82,16 @@ public class TestMultiThreadAddDelete { final ExecutorService es = Executors.newFixedThreadPool(N_THREADS); for (int i = 0; i < N_THREADS; i++) { final int threadNo = i; - es.execute(new Runnable() { - @Override - public void run() { - for (int j = 0; j < COUNT; j++) { - if (j % N_THREADS == threadNo) { - bt.put(Integer.valueOf(j), Integer.valueOf(j)); - if (!bt.containsKey(Integer.valueOf(j))) { - LOG.error("Key {} not present", j); - } - bt.remove(Integer.valueOf(j)); - if (bt.containsKey(Integer.valueOf(j))) { - LOG.error("Key {} is still present", j); - } + es.execute(() -> { + for (int j1 = 0; j1 < COUNT; j1++) { + if (j1 % N_THREADS == threadNo) { + bt.put(Integer.valueOf(j1), Integer.valueOf(j1)); + if (!bt.containsKey(Integer.valueOf(j1))) { + LOG.error("Key {} not present", j1); + } + bt.remove(Integer.valueOf(j1)); + if (bt.containsKey(Integer.valueOf(j1))) { + LOG.error("Key {} is still present", j1); } } } diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadInserts.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadInserts.java index d113c6a0f9..d775e074fd 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadInserts.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadInserts.java @@ -22,6 +22,7 @@ import java.util.concurrent.Executors; import java.util.concurrent.TimeUnit; import org.junit.Test; +@Deprecated public class TestMultiThreadInserts { @Test public void testMultiThreadInserts() throws InterruptedException { diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadMapIterator.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadMapIterator.java index bd1fbdae87..1e2e1f9ecd 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadMapIterator.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMultiThreadMapIterator.java @@ -31,6 +31,7 @@ import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; +@Deprecated public class TestMultiThreadMapIterator { private static final Logger LOG = LoggerFactory.getLogger(TestMultiThreadMapIterator.class); private static final int NTHREADS = 7; diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestReadOnlyAndUpdatableIterators.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestReadOnlyAndUpdatableIterators.java deleted file mode 100644 index 4ac015a829..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestReadOnlyAndUpdatableIterators.java +++ /dev/null @@ -1,105 +0,0 @@ -/* - * (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 static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertNull; - -import java.util.Iterator; -import java.util.Map.Entry; -import org.junit.Before; -import org.junit.Test; - -/** - * Test that read-only iterators do not allow for any updates. - * Test that non read-only iterators allow for updates. - */ -public class TestReadOnlyAndUpdatableIterators { - private static final int MAP_SIZE = 200; - - private TrieMap bt; - - @Before - public void setUp() { - bt = TrieMap.create(); - for (int j = 0; j < MAP_SIZE; j++) { - assertNull(bt.put(Integer.valueOf(j), Integer.valueOf(j))); - } - } - - private static void trySet(final Iterator> it) { - it.next().setValue(0); - } - - private static void tryRemove(final Iterator it) { - it.next(); - it.remove(); - } - - @Test(expected = UnsupportedOperationException.class) - public void testReadOnlyIteratorSet() { - trySet(bt.immutableIterator()); - } - - @Test(expected = UnsupportedOperationException.class) - public void testReadOnlyIteratorRemove() { - tryRemove(bt.immutableIterator()); - } - - @Test(expected = UnsupportedOperationException.class) - public void testReadOnlySnapshotReadOnlyIteratorSet() { - trySet(bt.immutableSnapshot().immutableIterator()); - } - - @Test(expected = UnsupportedOperationException.class) - public void testReadOnlySnapshotReadOnlyIteratorRemove() { - tryRemove(bt.immutableSnapshot().immutableIterator()); - } - - @Test(expected = UnsupportedOperationException.class) - public void testReadOnlySnapshotIteratorSet() { - trySet(bt.immutableSnapshot().iterator()); - } - - @Test(expected = UnsupportedOperationException.class) - public void testReadOnlySnapshotIteratorRemove() { - tryRemove(bt.immutableSnapshot().iterator()); - } - - @Test - public void testIterator() { - Iterator> it = bt.iterator(); - it.next().setValue(0); - it.remove(); - - // All changes are done on the original map - assertEquals(MAP_SIZE - 1, bt.size()); - } - - @Test - public void testSnapshotIterator() { - TrieMap snapshot = bt.mutableSnapshot(); - Iterator> it = snapshot.iterator(); - it.next().setValue(0); - it.remove(); - - // All changes are done on the snapshot, not on the original map - // Map size should remain unchanged - assertEquals(MAP_SIZE, bt.size()); - // snapshot size was changed - assertEquals(MAP_SIZE - 1, snapshot.size()); - } -} diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestSerialization.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestSerialization.java index 0af3568abe..45c01e4ace 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestSerialization.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestSerialization.java @@ -23,6 +23,7 @@ import java.io.ObjectOutputStream; import org.junit.Assert; import org.junit.Test; +@Deprecated public class TestSerialization { @Test public void testSerialization() throws IOException, ClassNotFoundException { diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ZeroHashInt.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ZeroHashInt.java deleted file mode 100644 index e72a911d3d..0000000000 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ZeroHashInt.java +++ /dev/null @@ -1,46 +0,0 @@ -/* - * (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 com.google.common.base.MoreObjects; - -/** - * Utility key/value class which attacks the hasing function, causing all objects to be put into a single bucket. - * - * @author Robert Varga - */ -final class ZeroHashInt { - private final int i; - - ZeroHashInt(final int i) { - this.i = i; - } - - @Override - public int hashCode() { - return 0; - } - - @Override - public boolean equals(final Object o) { - return o instanceof ZeroHashInt && i == ((ZeroHashInt) o).i; - } - - @Override - public String toString() { - return MoreObjects.toStringHelper(this).add("i", i).add("identity", System.identityHashCode(this)).toString(); - } -} -- 2.36.6