--- /dev/null
+/*
+ * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.opendaylight.yangtools.triemap;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+import com.google.common.annotations.Beta;
+import java.util.Map;
+import java.util.function.BiFunction;
+import java.util.function.Function;
+
+/**
+ * An immutable TrieMap
+ *
+ * @author Robert Varga
+ *
+ * @param <K> the type of keys maintained by this map
+ * @param <V> the type of mapped values
+ */
+@Beta
+public final class ImmutableTrieMap<K, V> extends TrieMap<K, V> {
+ private final INode<K, V> root;
+
+ ImmutableTrieMap(final INode<K, V> root, final Equivalence<? super K> equiv) {
+ super(equiv);
+ this.root = checkNotNull(root);
+ }
+
+ @Override
+ public void clear() {
+ throw unsupported();
+ }
+
+ @Override
+ public V compute(final K key, final BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ throw unsupported();
+ }
+
+ @Override
+ public V computeIfAbsent(final K key, final Function<? super K, ? extends V> mappingFunction) {
+ throw unsupported();
+ }
+
+ @Override
+ public V computeIfPresent(final K key, final BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ throw unsupported();
+ }
+
+ @Override
+ public V merge(final K key, final V value, final BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
+ throw unsupported();
+ }
+
+ @Override
+ public V put(final K key, final V value) {
+ throw unsupported();
+ }
+
+ @Override
+ public void putAll(final Map<? extends K, ? extends V> 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.cachedSize(this);
+ }
+
+ @Override
+ public final TrieMap<K, V> mutableSnapshot() {
+ return new MutableTrieMap<>(equiv(), new INode<>(new Gen(), root.gcasRead(this)));
+ }
+
+ @Override
+ public ImmutableTrieMap<K, V> immutableSnapshot() {
+ return this;
+ }
+
+ @Override
+ boolean isReadOnly() {
+ return true;
+ }
+
+ @Override
+ INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
+ return root;
+ }
+
+ private static UnsupportedOperationException unsupported() {
+ return new UnsupportedOperationException("Attempted to modify a read-only view");
+ }
+}
--- /dev/null
+/*
+ * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.opendaylight.yangtools.triemap;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+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 java.util.Optional;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+/**
+ * A mutable TrieMap.
+ *
+ * @author Robert Varga
+ *
+ * @param <K> the type of keys maintained by this map
+ * @param <V> the type of mapped values
+ */
+@Beta
+final class MutableTrieMap<K, V> extends TrieMap<K, V> {
+ @SuppressWarnings("rawtypes")
+ private static final AtomicReferenceFieldUpdater<MutableTrieMap, Object> ROOT_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(MutableTrieMap.class, Object.class, "root");
+
+ private volatile Object root;
+
+ MutableTrieMap(final Equivalence<? super K> equiv) {
+ this(equiv, newRootNode());
+ }
+
+ MutableTrieMap(final Equivalence<? super K> equiv, final INode<K, V> root) {
+ super(equiv);
+ this.root = checkNotNull(root);
+ }
+
+ @Override
+ public void clear() {
+ boolean success;
+ do {
+ final INode<K, V> r = RDCSS_READ_ROOT();
+ success = RDCSS_ROOT(r, r.gcasRead(this), newRootNode());
+ } while (!success);
+ }
+
+ @Override
+ public V put(final K key, final V value) {
+ final K k = checkNotNull(key);
+ return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), null));
+ }
+
+ @Override
+ public V putIfAbsent(final K key, final V value) {
+ final K k = checkNotNull(key);
+ return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), ABSENT));
+ }
+
+ @Override
+ public V remove(final Object key) {
+ @SuppressWarnings("unchecked")
+ final K k = (K) checkNotNull(key);
+ return toNullable(removehc(k, null, computeHash(k)));
+ }
+
+ @Override
+ public boolean remove(final Object key, final Object value) {
+ @SuppressWarnings("unchecked")
+ final K k = (K) checkNotNull(key);
+ return removehc(k, checkNotNull(value), computeHash(k)).isPresent();
+ }
+
+ @Override
+ public boolean replace(final K key, final V oldValue, final V newValue) {
+ final K k = checkNotNull(key);
+ return insertifhc(k, computeHash(k), checkNotNull(newValue), checkNotNull(oldValue)).isPresent();
+ }
+
+ @Override
+ public V replace(final K key, final V value) {
+ final K k = checkNotNull(key);
+ return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), PRESENT));
+ }
+
+ @Override
+ public int size() {
+ return immutableSnapshot().size();
+ }
+
+ @Override
+ public ImmutableTrieMap<K, V> immutableSnapshot() {
+ while (true) {
+ final INode<K, V> r = RDCSS_READ_ROOT();
+ final MainNode<K, V> expmain = r.gcasRead(this);
+ if (RDCSS_ROOT(r, expmain, r.copyToGen (new Gen(), this))) {
+ return new ImmutableTrieMap<>(r, equiv());
+ }
+
+ // Tail recursion: return readOnlySnapshot();
+ }
+ }
+
+ @Override
+ public MutableTrieMap<K, V> mutableSnapshot() {
+ while (true) {
+ final INode<K, V> r = RDCSS_READ_ROOT();
+ final MainNode<K, V> expmain = r.gcasRead(this);
+ if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this))) {
+ return new MutableTrieMap<>(equiv(), r.copyToGen(new Gen(), this));
+ }
+
+ // Tail recursion: return snapshot();
+ }
+ }
+
+ @Override
+ boolean isReadOnly() {
+ return false;
+ }
+
+ @Override
+ INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
+ final Object r = /* READ */ root;
+ if (r instanceof INode) {
+ return (INode<K, V>) 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 = checkNotNull(key);
+ inserthc(k, computeHash(k), checkNotNull(value));
+ }
+
+ private static <K,V> INode<K, V> newRootNode() {
+ final Gen gen = new Gen();
+ return new INode<>(gen, new CNode<>(gen));
+ }
+
+ private void inserthc(final K k, final int hc, final V v) {
+ // 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().rec_insert(k, v, hc, 0, null, this);
+ Verify.verify(success, "Concurrent modification during serialization of map %s", this);
+ }
+
+ private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
+ Optional<V> res;
+ do {
+ // Keep looping as long as we do not get a reply
+ res = RDCSS_READ_ROOT().rec_insertif(k, v, hc, cond, 0, null, this);
+ } while (res == null);
+
+ return res;
+ }
+
+ private Optional<V> removehc(final K k, final Object cond, final int hc) {
+ Optional<V> res;
+ do {
+ // Keep looping as long as we do not get a reply
+ res = RDCSS_READ_ROOT().rec_remove(k, 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<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
+ final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
+ if (CAS_ROOT(ov, desc)) {
+ RDCSS_Complete(false);
+ return /* READ */desc.committed;
+ }
+
+ return false;
+ }
+
+ private INode<K, V> RDCSS_Complete(final boolean abort) {
+ while (true) {
+ final Object r = /* READ */ root;
+ if (r instanceof INode) {
+ return (INode<K, V>) r;
+ }
+
+ checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
+ @SuppressWarnings("unchecked")
+ final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) r;
+ final INode<K, V> ov = desc.old;
+ final MainNode<K, V> exp = desc.expectedmain;
+ final INode<K, V> nv = desc.nv;
+
+ if (abort) {
+ if (CAS_ROOT(desc, ov)) {
+ return ov;
+ }
+
+ // Tail recursion: return RDCSS_Complete(abort);
+ continue;
+ }
+
+ final MainNode<K, V> 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<K, V> {
+ final INode<K, V> old;
+ final MainNode<K, V> expectedmain;
+ final INode<K, V> nv;
+
+ volatile boolean committed = false;
+
+ RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
+ this.old = old;
+ this.expectedmain = expectedmain;
+ this.nv = nv;
+ }
+ }
+}
*/
package org.opendaylight.yangtools.triemap;
-import com.google.common.base.Preconditions;
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+
import com.google.common.base.Verify;
import java.io.Externalizable;
import java.io.IOException;
*
* @author Robert Varga
*/
-final class ExternalForm implements Externalizable {
+final class SerializationProxy implements Externalizable {
private static final long serialVersionUID = 1L;
private TrieMap<Object, Object> map;
private boolean readOnly;
- public ExternalForm() {
+ public SerializationProxy() {
// For Externalizable
}
@SuppressWarnings({ "unchecked", "rawtypes" })
- ExternalForm(final TrieMap<?, ?> map) {
- this.map = ((TrieMap)map).readOnlySnapshot();
- this.readOnly = map.isReadOnly();
+ SerializationProxy(final ImmutableTrieMap<?, ?> map, final boolean readOnly) {
+ this.map = (TrieMap) checkNotNull(map);
+ this.readOnly = readOnly;
}
@Override
public void readExternal(final ObjectInput in) throws IOException, ClassNotFoundException {
@SuppressWarnings("unchecked")
final Equivalence<Object> equiv = (Equivalence<Object>) in.readObject();
- Preconditions.checkArgument(equiv != null);
- map = new TrieMap<>(equiv);
+ checkArgument(equiv != null);
+ final MutableTrieMap<Object, Object> tmp = new MutableTrieMap<>(equiv);
final int size = in.readInt();
+ checkArgument(size >= 0);
+
for (int i = 0; i < size; ++i) {
- map.add(in.readObject(), in.readObject());
+ tmp.add(in.readObject(), in.readObject());
}
- readOnly = in.readBoolean();
+ map = in.readBoolean() ? tmp.immutableSnapshot() : tmp;
}
private Object readResolve() throws ObjectStreamException {
- return Verify.verifyNotNull(readOnly ? map.readOnlySnapshot() : map);
+ return Verify.verifyNotNull(map);
}
}
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
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.Verify;
-import com.google.common.collect.Iterators;
+import com.google.common.annotations.Beta;
import java.io.ObjectStreamException;
import java.io.Serializable;
import java.util.AbstractMap;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
-import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
/***
* This is a port of Scala's TrieMap class from the Scala Collections library. This implementation does not support
* null keys nor null values.
*
- * @author Roman Levenstein <romixlev@gmail.com>
+ * @author Aleksandar Prokopec (original Scala implementation)
+ * @author Roman Levenstein (original Java 6 port)
+ * @author Robert Varga
*
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*/
-public final class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
- @SuppressWarnings("rawtypes")
- private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER =
- AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root");
+@Beta
+public abstract class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
private static final long serialVersionUID = 1L;
/**
*/
private final EntrySet entrySet = new EntrySet();
private final Equivalence<? super K> equiv;
- private final boolean readOnly;
-
- private volatile Object root;
-
- private TrieMap(final INode<K, V> r, final Equivalence<? super K> equiv, final boolean readOnly) {
- this.root = r;
- this.equiv = equiv;
- this.readOnly = readOnly;
- }
TrieMap(final Equivalence<? super K> equiv) {
- this(newRootNode(), equiv, false);
- }
-
- public TrieMap() {
- this(Equivalence.equals());
- }
-
- /* internal methods */
-
- final Equivalence<? super K> equiv() {
- return equiv;
- }
-
- private static <K,V> INode<K, V> newRootNode() {
- final Gen gen = new Gen();
- return new INode<>(gen, new CNode<>(gen));
- }
-
- private boolean CAS_ROOT(final Object ov, final Object nv) {
- checkState(!readOnly, "Attempted to modify a read-only snapshot");
- return ROOT_UPDATER.compareAndSet(this, ov, nv);
- }
-
- final INode<K, V> readRoot() {
- return RDCSS_READ_ROOT(false);
- }
-
- // FIXME: abort = false by default
- final INode<K, V> readRoot(final boolean abort) {
- return RDCSS_READ_ROOT(abort);
- }
-
- private final INode<K, V> RDCSS_READ_ROOT() {
- return RDCSS_READ_ROOT(false);
- }
-
- private final INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
- final Object r = /* READ */ root;
- if (r instanceof INode) {
- return (INode<K, V>) r;
- }
-
- checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
- return RDCSS_Complete(abort);
- }
-
- private INode<K, V> RDCSS_Complete(final boolean abort) {
- while (true) {
- final Object r = /* READ */ root;
- if (r instanceof INode) {
- return (INode<K, V>) r;
- }
-
- checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
- @SuppressWarnings("unchecked")
- final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) r;
- final INode<K, V> ov = desc.old;
- final MainNode<K, V> exp = desc.expectedmain;
- final INode<K, V> nv = desc.nv;
-
- if (abort) {
- if (CAS_ROOT(desc, ov)) {
- return ov;
- }
-
- // Tail recursion: return RDCSS_Complete(abort);
- continue;
- }
-
- final MainNode<K, V> 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 boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
- final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
- if (CAS_ROOT(ov, desc)) {
- RDCSS_Complete(false);
- return /* READ */desc.committed;
- }
-
- return false;
- }
-
- private void inserthc(final K k, final int hc, final V v) {
- // 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().rec_insert(k, v, hc, 0, null, this);
- Verify.verify(success, "Concurrent modification during serialization of map %s", this);
- }
-
- void add(final K key, final V value) {
- final K k = checkNotNull(key);
- inserthc(k, computeHash(k), checkNotNull(value));
- }
-
- private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
- Optional<V> res;
- do {
- // Keep looping as long as we do not get a reply
- res = RDCSS_READ_ROOT().rec_insertif(k, v, hc, cond, 0, null, this);
- } while (res == null);
-
- return res;
- }
-
- @SuppressWarnings("unchecked")
- private V lookuphc(final K k, final int hc) {
- Object res;
- do {
- // Keep looping as long as RESTART is being indicated
- res = RDCSS_READ_ROOT().rec_lookup(k, hc, 0, null, this);
- } while (res == RESTART);
-
- return (V) res;
- }
-
- private Optional<V> removehc(final K k, final Object cond, final int hc) {
- Optional<V> res;
- do {
- // Keep looping as long as we do not get a reply
- res = RDCSS_READ_ROOT().rec_remove(k, cond, hc, 0, null, this);
- } while (res == null);
-
- return res;
- }
-
- /**
- * Ensure this instance is read-write, throw UnsupportedOperationException
- * otherwise. Used by Map-type methods for quick check.
- */
- private void ensureReadWrite() {
- if (readOnly) {
- throw new UnsupportedOperationException("Attempted to modify a read-only view");
- }
+ this.equiv = equiv;
}
- boolean isReadOnly() {
- return readOnly;
+ public static <K, V> TrieMap<K, V> create() {
+ return new MutableTrieMap<>(Equivalence.equals());
}
- /* public methods */
-
/**
* Returns a snapshot of this TrieMap. This operation is lock-free and
* linearizable.
* distributed across all the threads doing updates or accesses subsequent
* to the snapshot creation.
*/
- public TrieMap<K, V> snapshot() {
- while (true) {
- final INode<K, V> r = RDCSS_READ_ROOT();
- final MainNode<K, V> expmain = r.gcasRead(this);
- if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this))) {
- return new TrieMap<> (r.copyToGen(new Gen(), this), equiv, readOnly);
- }
-
- // Tail recursion: return snapshot();
- }
- }
+ public abstract TrieMap<K, V> mutableSnapshot();
/**
* Returns a read-only snapshot of this TrieMap. This operation is lock-free
*
* This method is used by other methods such as `size` and `iterator`.
*/
- public TrieMap<K, V> readOnlySnapshot() {
- // Is it a snapshot of a read-only snapshot?
- if (readOnly) {
- return this;
- }
-
- while (true) {
- final INode<K, V> r = RDCSS_READ_ROOT();
- final MainNode<K, V> expmain = r.gcasRead(this);
- if (RDCSS_ROOT(r, expmain, r.copyToGen (new Gen(), this))) {
- return new TrieMap<>(r, equiv, true);
- }
-
- // Tail recursion: return readOnlySnapshot();
- }
- }
+ public abstract ImmutableTrieMap<K, V> immutableSnapshot();
@Override
- public void clear() {
- boolean success;
- do {
- final INode<K, V> r = RDCSS_READ_ROOT();
- success = RDCSS_ROOT(r, r.gcasRead(this), newRootNode());
- } while (!success);
+ public final boolean containsKey(final Object key) {
+ return get(key) != null;
}
- int computeHash(final K k) {
- return equiv.hash(k);
+ @Override
+ public final boolean containsValue(final Object value) {
+ return super.containsValue(checkNotNull(value));
}
- boolean equal(final K k1, final K k2) {
- return equiv.equivalent(k1, k2);
+ @Override
+ public final Set<Entry<K, V>> entrySet() {
+ return entrySet;
}
@Override
- public V get(final Object key) {
+ public final V get(final Object key) {
@SuppressWarnings("unchecked")
final K k = (K) checkNotNull(key);
return lookuphc(k, computeHash(k));
}
+ @Override
+ public abstract void clear();
+
+ @Override
+ public abstract V put(K key, V value);
+
+ @Override
+ public abstract V putIfAbsent(K key, V value);
+
+ @Override
+ public abstract V remove(Object key);
+
+ @Override
+ public abstract boolean remove(Object key, Object value);
+
+ @Override
+ public abstract boolean replace(K key, V oldValue, V newValue);
+
+ @Override
+ public abstract V replace(K key, V value);
+
+ @Override
+ public abstract int size();
+
+ /* internal methods implemented by subclasses */
+
+ abstract boolean isReadOnly();
+
+ abstract INode<K, V> RDCSS_READ_ROOT(boolean abort);
+
+ /* internal methods provided for subclasses */
+
@SuppressWarnings("null")
- private static <V> V toNullable(final Optional<V> opt) {
+ static <V> V toNullable(final Optional<V> opt) {
return opt.orElse(null);
}
- @Override
- public V put(final K key, final V value) {
- ensureReadWrite();
- final K k = checkNotNull(key);
- return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), null));
+ final int computeHash(final K k) {
+ return equiv.hash(k);
}
- @Override
- public V remove(final Object key) {
- ensureReadWrite();
- @SuppressWarnings("unchecked")
- final K k = (K) checkNotNull(key);
- return toNullable(removehc(k, null, computeHash(k)));
+ final Object writeReplace() throws ObjectStreamException {
+ return new SerializationProxy(immutableSnapshot(), isReadOnly());
}
- @Override
- public V putIfAbsent(final K key, final V value) {
- ensureReadWrite();
- final K k = checkNotNull(key);
- return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), ABSENT));
+ /* package-protected utility methods */
+
+ final Equivalence<? super K> equiv() {
+ return equiv;
}
- @Override
- public boolean remove(final Object key, final Object v) {
- ensureReadWrite();
- @SuppressWarnings("unchecked")
- final K k = (K) checkNotNull(key);
- return removehc(k, checkNotNull(v), computeHash(k)).isPresent();
+ final INode<K, V> readRoot() {
+ return RDCSS_READ_ROOT(false);
}
- @Override
- public boolean replace(final K key, final V oldValue, final V newValue) {
- ensureReadWrite();
- final K k = checkNotNull(key);
- return insertifhc(k, computeHash(k), checkNotNull(newValue), checkNotNull(oldValue)).isPresent();
+ // FIXME: abort = false by default
+ final INode<K, V> readRoot(final boolean abort) {
+ return RDCSS_READ_ROOT(abort);
}
- @Override
- public V replace(final K key, final V value) {
- ensureReadWrite();
- final K k = checkNotNull(key);
- return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), PRESENT));
+ final INode<K, V> RDCSS_READ_ROOT() {
+ return RDCSS_READ_ROOT(false);
}
- /***
+ final boolean equal(final K k1, final K k2) {
+ return equiv.equivalent(k1, k2);
+ }
+
+ /* private implementation methods */
+
+ @SuppressWarnings("unchecked")
+ private V lookuphc(final K k, final int hc) {
+ Object res;
+ do {
+ // Keep looping as long as RESTART is being indicated
+ res = RDCSS_READ_ROOT().rec_lookup(k, hc, 0, null, this);
+ } while (res == RESTART);
+
+ return (V) res;
+ }
+
+ /**
* Return an iterator over a TrieMap.
*
* If this is a read-only snapshot, it would return a read-only iterator.
* @return
*/
Iterator<Entry<K, V>> iterator() {
- return readOnly ? new TrieMapReadOnlyIterator<>(0, this) : new TrieMapIterator<>(0, this);
+ // FIXME: it would be nice to have a ReadWriteTrieMap with read-only iterator
+ return isReadOnly() ? new TrieMapReadOnlyIterator<>(0, this) : new TrieMapIterator<>(0, this);
}
- /***
+ /**
* Return an iterator over a TrieMap.
* This is a read-only iterator.
*
* @return
*/
- Iterator<Entry<K, V>> readOnlyIterator() {
- return new TrieMapReadOnlyIterator<>(0, readOnly ? this : readOnlySnapshot());
- }
-
- private int cachedSize() {
- return RDCSS_READ_ROOT().cachedSize (this);
- }
-
- @Override
- public int size() {
- return readOnly ? cachedSize() : readOnlySnapshot().size();
- }
-
- @Override
- public boolean containsKey(final Object key) {
- return get(key) != null;
- }
-
- @Override
- public Set<Entry<K, V>> entrySet() {
- return entrySet;
+ final Iterator<Entry<K, V>> readOnlyIterator() {
+ return new TrieMapReadOnlyIterator<>(0, immutableSnapshot());
}
- private Object writeReplace() throws ObjectStreamException {
- return new ExternalForm(this);
- }
-
- private static final class RDCSS_Descriptor<K, V> {
- INode<K, V> old;
- MainNode<K, V> expectedmain;
- INode<K, V> nv;
- volatile boolean committed = false;
-
- RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
- this.old = old;
- this.expectedmain = expectedmain;
- this.nv = nv;
- }
- }
-
- /***
+ /**
* This iterator is a read-only one and does not allow for any update
* operations on the underlying data structure.
*
@Override
public final int size () {
- return Iterators.size(iterator());
+ return TrieMap.this.size();
}
@Override
--- /dev/null
+/*
+ * (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.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Map;
+import org.junit.Before;
+import org.junit.Test;
+
+public class SnapshotTest {
+ private TrieMap<String, String> map;
+
+ @Before
+ public void setUp() {
+ map = TrieMap.create();
+ map.put("k1", "v1");
+ map.put("k2", "v2");
+ }
+
+ private static void assertMutableIsolation(final Map<String, String> m1, final Map<String, String> m2) {
+ assertTrue(m2.containsKey("k1"));
+ assertTrue(m2.containsKey("k2"));
+
+ m1.remove("k1");
+ assertFalse(m1.containsKey("k1"));
+ assertTrue(m2.containsKey("k1"));
+
+ m2.remove("k2");
+ assertFalse(m1.containsKey("k1"));
+ assertTrue(m2.containsKey("k1"));
+
+ assertEquals(1, m1.size());
+ assertEquals(1, m2.size());
+ }
+
+ @Test
+ public void testMutableSnapshotIsolation() {
+ assertMutableIsolation(map, map.mutableSnapshot());
+ }
+
+ @Test
+ public void testMutableSnapshotIsolationAcrossImmutable() {
+ final TrieMap<String, String> snap = map.immutableSnapshot();
+ assertTrue(snap.containsKey("k1"));
+ assertTrue(snap.containsKey("k2"));
+
+ assertMutableIsolation(map, snap.mutableSnapshot());
+
+ assertTrue(snap.containsKey("k1"));
+ assertTrue(snap.containsKey("k2"));
+
+ }
+}
public class TestCNodeFlagCollision {
@Test
public void testCNodeFlagCollision () {
- final Map<Integer, Object> map = new TrieMap<>();
+ final Map<Integer, Object> map = TrieMap.create();
final Integer z15169 = Integer.valueOf(15169);
final Integer z28336 = Integer.valueOf(28336);
@Test
public void testCNodeInsertionIncorrectOrder () {
- final Map<Integer, Integer> map = new TrieMap<>();
+ final Map<Integer, Integer> map = TrieMap.create();
final Integer z3884 = Integer.valueOf(3884);
final Integer z4266 = Integer.valueOf(4266);
map.put(z3884, z3884);
@Test
public void testConcurrentMapPutIfAbsent () {
- final ConcurrentMap<Object, Object> map = new TrieMap<>();
+ final ConcurrentMap<Object, Object> map = TrieMap.create();
for (int i = 0; i < COUNT; i++) {
assertNull(map.putIfAbsent (i, i));
final ZeroHashInt v2 = new ZeroHashInt(5);
final ZeroHashInt v3 = new ZeroHashInt(6);
- final Map<ZeroHashInt, ZeroHashInt> map = new TrieMap<>();
+ final Map<ZeroHashInt, ZeroHashInt> map = TrieMap.create();
// Pre-populate an LNode
assertNull(map.putIfAbsent(k1, v1));
assertNull(map.putIfAbsent(k2, v2));
@Test
public void testConcurrentMapRemove () {
- final ConcurrentMap<Integer, Object> map = new TrieMap<>();
+ final ConcurrentMap<Integer, Object> map = TrieMap.create();
for (int i = 128; i < COUNT; i++) {
assertFalse(map.remove(i, i));
final ZeroHashInt v3 = new ZeroHashInt(6);
final ZeroHashInt v3dup = new ZeroHashInt(6);
- final Map<ZeroHashInt, ZeroHashInt> map = new TrieMap<>();
+ final Map<ZeroHashInt, ZeroHashInt> map = TrieMap.create();
// Pre-populate an LNode
assertNull(map.putIfAbsent(k1, v1));
assertNull(map.putIfAbsent(k2, v2));
@Test
public void testConcurrentMapReplace () {
- final ConcurrentMap<Integer, Object> map = new TrieMap<>();
+ final ConcurrentMap<Integer, Object> map = TrieMap.create();
for (int i = 0; i < COUNT; i++) {
assertNull(map.replace(i, "lol"));
final ZeroHashInt v3dup = new ZeroHashInt(6);
final ZeroHashInt k4 = new ZeroHashInt(7);
- final Map<ZeroHashInt, ZeroHashInt> map = new TrieMap<>();
+ final Map<ZeroHashInt, ZeroHashInt> map = TrieMap.create();
assertNull(map.put(k3, v3));
// First check for SNode
public class TestDelete {
@Test(expected = NullPointerException.class)
public void testNullSimple() {
- new TrieMap<>().remove(null);
+ TrieMap.create().remove(null);
}
@Test(expected = NullPointerException.class)
public void testNullKey() {
- new TrieMap<>().remove(null, "");
+ TrieMap.create().remove(null, "");
}
@Test(expected = NullPointerException.class)
public void testNullValue() {
- new TrieMap<>().remove("", null);
+ TrieMap.create().remove("", null);
}
@Test(expected = NullPointerException.class)
public void testNullBoth() {
- new TrieMap<>().remove(null, null);
+ TrieMap.create().remove(null, null);
}
@Test
public void testClear() {
- final TrieMap<Integer, Integer> bt = new TrieMap<>();
+ final TrieMap<Integer, Integer> bt = TrieMap.create();
bt.put(1, 1);
bt.clear();
assertTrue(bt.isEmpty());
@Test
public void testDelete () {
- final TrieMap<Integer, Integer> bt = new TrieMap<> ();
+ final TrieMap<Integer, Integer> bt = TrieMap.create();
for (int i = 0; i < 10000; i++) {
assertNull(bt.put(Integer.valueOf(i), Integer.valueOf(i)));
*/
@Test
public void testRemoveObjectLNode() {
- final TrieMap<ZeroHashInt, ZeroHashInt> bt = new TrieMap<> ();
+ final TrieMap<ZeroHashInt, ZeroHashInt> bt = TrieMap.create();
for (int i = 0; i < 100; i++) {
final ZeroHashInt v = new ZeroHashInt(i);
public class TestHashCollisions {
@Test
public void testHashCollisions () {
- final TrieMap<Object, Object> bt = new TrieMap<>();
+ final TrieMap<Object, Object> bt = TrieMap.create();
insertStrings(bt);
insertChars(bt);
@Test
public void testHashCollisionsRemove() {
- final Map<Object, Object> bt = new TrieMap<>();
+ final Map<Object, Object> bt = TrieMap.create();
for (int j = 0; j < COUNT; j++) {
for (final Object o : TestMultiThreadMapIterator.getObjects(j)) {
@Test
public void testHashCollisionsRemoveIterator () {
- final Map<Object, Object> bt = new TrieMap<>();
+ final Map<Object, Object> bt = TrieMap.create();
for (int j = 0; j < COUNT; j++) {
bt.put(Integer.valueOf(j), Integer.valueOf(j));
}
public class TestInsert {
@Test
public void testInsert () {
- final TrieMap<Object, Object> bt = new TrieMap<>();
+ final TrieMap<Object, Object> bt = TrieMap.create();
assertNull(bt.put("a", "a"));
assertNull(bt.put("b", "b"));
assertNull(bt.put("c", "b"));
@Test(expected = NullPointerException.class)
public void testNullKey() {
- new TrieMap<>().put(null, "");
+ TrieMap.create().put(null, "");
}
@Test(expected = NullPointerException.class)
public void testNullValue() {
- new TrieMap<>().put("", null);
+ TrieMap.create().put("", null);
}
@Test(expected = NullPointerException.class)
public void testNullBoth() {
- new TrieMap<>().put(null, null);
+ TrieMap.create().put(null, null);
}
}
final Stopwatch watch = Stopwatch.createStarted();
for (int i = 0; i < COUNT; ++i) {
- maps[i] = new TrieMap<>();
+ maps[i] = TrieMap.create();
}
watch.stop();
final Random random = new Random();
for (int i = 0; i < 60 * 1000; i+= 400 + random.nextInt(400)) {
- final Map<Integer, Integer> bt = new TrieMap <>();
+ final Map<Integer, Integer> bt = TrieMap.create();
for (int j = 0; j < i; j++) {
assertNull(bt.put(Integer.valueOf(j), Integer.valueOf(j)));
}
@Test(expected = NoSuchElementException.class)
public void testEmptyIterator() {
- failAdvance(new TrieMap<>().iterator());
+ failAdvance(TrieMap.create().iterator());
}
@Test(expected = NoSuchElementException.class)
public void testEmptyReadOnlyIterator() {
- failAdvance(new TrieMap<>().readOnlyIterator());
+ failAdvance(TrieMap.create().readOnlyIterator());
}
@Test(expected = NoSuchElementException.class)
public void testEmptyReadOnlySnapshotIterator() {
- failAdvance(new TrieMap<>().readOnlySnapshot().iterator());
+ failAdvance( TrieMap.create().immutableSnapshot().iterator());
}
}
@Test
public void testMultiThreadAddDelete () throws InterruptedException {
for (int j = 0; j < RETRIES; j++) {
- final Map<Object, Object> bt = new TrieMap<>();
+ final Map<Object, Object> bt = TrieMap.create();
{
final ExecutorService es = Executors.newFixedThreadPool(N_THREADS);
public void testMultiThreadInserts () throws InterruptedException{
final int nThreads = 2;
final ExecutorService es = Executors.newFixedThreadPool(nThreads);
- final TrieMap<Object, Object> bt = new TrieMap<>();
+ final TrieMap<Object, Object> bt = TrieMap.create();
for (int i = 0; i < nThreads; i++) {
final int threadNo = i;
es.execute (() -> {
@Test
public void testMultiThreadMapIterator () throws InterruptedException {
- final Map<Object, Object> bt = new TrieMap<>();
+ final Map<Object, Object> bt = TrieMap.create();
for (int j = 0; j < 50 * 1000; j++) {
for (final Object o : getObjects(j)) {
bt.put (o, o);
@Before
public void setUp() {
- bt = new TrieMap<>();
+ bt = TrieMap.create();
for (int j = 0; j < MAP_SIZE; j++) {
assertNull(bt.put(Integer.valueOf(j), Integer.valueOf(j)));
}
@Test(expected = UnsupportedOperationException.class)
public void testReadOnlySnapshotReadOnlyIteratorSet() {
- trySet(bt.readOnlySnapshot().readOnlyIterator());
+ trySet(bt.immutableSnapshot().readOnlyIterator());
}
@Test(expected = UnsupportedOperationException.class)
public void testReadOnlySnapshotReadOnlyIteratorRemove() {
- tryRemove(bt.readOnlySnapshot().readOnlyIterator());
+ tryRemove(bt.immutableSnapshot().readOnlyIterator());
}
@Test(expected = UnsupportedOperationException.class)
public void testReadOnlySnapshotIteratorSet() {
- trySet(bt.readOnlySnapshot().iterator());
+ trySet(bt.immutableSnapshot().iterator());
}
@Test(expected = UnsupportedOperationException.class)
public void testReadOnlySnapshotIteratorRemove() {
- tryRemove(bt.readOnlySnapshot().iterator());
+ tryRemove(bt.immutableSnapshot().iterator());
}
@Test
@Test
public void testSnapshotIterator () {
- TrieMap<Integer, Integer> snapshot = bt.snapshot();
+ TrieMap<Integer, Integer> snapshot = bt.mutableSnapshot();
Iterator<Entry<Integer, Integer>> it = snapshot.iterator();
it.next().setValue(0);
it.remove();
public class TestSerialization {
@Test
public void testSerialization() throws IOException, ClassNotFoundException {
- TrieMap<String, String> map = new TrieMap<>();
+ TrieMap<String, String> map = TrieMap.create();
map.put("dude-0", "tom");
map.put("dude-1", "john");
map.put("dude-3", "ravi");
map.put("dude-4", "alex");
- TrieMap<String, String> expected = map.readOnlySnapshot();
+ TrieMap<String, String> expected = map.immutableSnapshot();
final ByteArrayOutputStream bos = new ByteArrayOutputStream();
final ObjectOutputStream oos = new ObjectOutputStream(bos);
Code Review / yangtools.git / commitdiff