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.LookupResult.RESTART;
import com.google.common.annotations.Beta;
import java.io.ObjectStreamException;
import java.io.Serializable;
import java.util.AbstractMap;
-import java.util.AbstractSet;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-import java.util.NoSuchElementException;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
public abstract class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
private static final long serialVersionUID = 1L;
- /**
- * EntrySet
- */
- private final EntrySet entrySet = new EntrySet();
private final Equivalence<? super K> equiv;
+ private AbstractEntrySet<K, V> entrySet;
+ private AbstractKeySet<K> keySet;
+
TrieMap(final Equivalence<? super K> equiv) {
this.equiv = equiv;
}
@Override
public final Set<Entry<K, V>> entrySet() {
- return entrySet;
+ AbstractEntrySet<K, V> ret = entrySet;
+ if (ret == null) {
+ entrySet = ret = createEntrySet();
+ }
+ return ret;
+ }
+
+ @Override
+ public final Set<K> keySet() {
+ AbstractKeySet<K> ret = keySet;
+ if (ret == null) {
+ keySet = ret = createKeySet();
+ }
+ return ret;
}
@Override
/* internal methods implemented by subclasses */
+ abstract AbstractEntrySet<K, V> createEntrySet();
+
+ abstract AbstractKeySet<K> createKeySet();
+
abstract boolean isReadOnly();
abstract INode<K, V> 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
+ */
+ abstract AbstractIterator<K, V> iterator();
+
/* internal methods provided for subclasses */
+ /**
+ * Return an iterator over a TrieMap.
+ * This is a read-only iterator.
+ *
+ * @return
+ */
+ final ImmutableIterator<K, V> immutableIterator() {
+ return new ImmutableIterator<>(immutableSnapshot());
+ }
+
@SuppressWarnings("null")
static <V> V toNullable(final Optional<V> opt) {
return opt.orElse(null);
return (V) res;
}
-
- /**
- * 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
- */
- Iterator<Entry<K, V>> iterator() {
- // 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
- */
- final Iterator<Entry<K, V>> readOnlyIterator() {
- return new TrieMapReadOnlyIterator<>(0, immutableSnapshot());
- }
-
- /**
- * This iterator is a read-only one and does not allow for any update
- * operations on the underlying data structure.
- *
- * @param <K>
- * @param <V>
- */
- private static final class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
- TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
- super (level, ct, mustInit);
- }
-
- TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
- this (level, ct, true);
- }
- @Override
- void initialize () {
- assert (ct.isReadOnly ());
- super.initialize ();
- }
-
- @Override
- public void remove () {
- throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
- }
-
- @Override
- Entry<K, V> nextEntry(final Entry<K, V> rr) {
- // Return non-updatable entry
- return rr;
- }
- }
-
- private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
- private int level;
- protected TrieMap<K, V> ct;
- private final boolean mustInit;
- private final BasicNode[][] stack = new BasicNode[7][];
- private final int[] stackpos = new int[7];
- private int depth = -1;
- private Iterator<Entry<K, V>> subiter = null;
- private EntryNode<K, V> current = null;
- private Entry<K, V> lastReturned = null;
-
- TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
- this.level = level;
- this.ct = ct;
- this.mustInit = mustInit;
- if (this.mustInit) {
- initialize ();
- }
- }
-
- TrieMapIterator (final int level, final TrieMap<K, V> ct) {
- this (level, ct, true);
- }
-
-
- @Override
- public boolean hasNext() {
- return (current != null) || (subiter != null);
- }
-
- @Override
- public Entry<K, V> next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
-
- final Entry<K, V> r;
- if (subiter != null) {
- r = subiter.next();
- checkSubiter();
- } else {
- r = current;
- advance();
- }
-
- lastReturned = r;
- if (r != null) {
- final Entry<K, V> rr = r;
- return nextEntry(rr);
- }
- return r;
- }
-
- Entry<K, V> nextEntry(final Entry<K, V> rr) {
- return new Entry<K, V>() {
- @SuppressWarnings("null")
- private V updated = null;
-
- @Override
- public K getKey () {
- return rr.getKey ();
- }
-
- @Override
- public V getValue () {
- return (updated == null) ? rr.getValue (): updated;
- }
-
- @Override
- public V setValue (final V value) {
- updated = value;
- return ct.replace (getKey (), value);
- }
- };
- }
-
- private void readin (final INode<K, V> in) {
- MainNode<K, V> m = in.gcasRead (ct);
- if (m instanceof CNode) {
- CNode<K, V> cn = (CNode<K, V>) m;
- depth += 1;
- stack [depth] = cn.array;
- stackpos [depth] = -1;
- advance ();
- } else if (m instanceof TNode) {
- current = (TNode<K, V>) m;
- } else if (m instanceof LNode) {
- subiter = ((LNode<K, V>) m).iterator();
- checkSubiter ();
- } else if (m == null) {
- current = null;
- }
- }
-
- // @inline
- private void checkSubiter () {
- if (!subiter.hasNext ()) {
- subiter = null;
- advance ();
- }
- }
-
- // @inline
- void initialize () {
-// assert (ct.isReadOnly ());
- readin(ct.RDCSS_READ_ROOT());
- }
-
- void advance () {
- if (depth >= 0) {
- int npos = stackpos [depth] + 1;
- if (npos < stack [depth].length) {
- stackpos [depth] = npos;
- BasicNode elem = stack [depth] [npos];
- if (elem instanceof SNode) {
- current = (SNode<K, V>) elem;
- } else if (elem instanceof INode) {
- readin ((INode<K, V>) elem);
- }
- } else {
- depth -= 1;
- advance ();
- }
- } else {
- current = null;
- }
- }
-
- protected TrieMapIterator<K, V> newIterator(final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
- return new TrieMapIterator<> (_lev, _ct, _mustInit);
- }
-
- protected void dupTo(final TrieMapIterator<K, V> it) {
- it.level = this.level;
- it.ct = this.ct;
- it.depth = this.depth;
- it.current = this.current;
-
- // these need a deep copy
- System.arraycopy (this.stack, 0, it.stack, 0, 7);
- System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
-
- // this one needs to be evaluated
- if (this.subiter == null) {
- it.subiter = null;
- } else {
- List<Entry<K, V>> lst = toList (this.subiter);
- this.subiter = lst.iterator ();
- it.subiter = lst.iterator ();
- }
- }
-
- // /** Returns a sequence of iterators over subsets of this iterator.
- // * It's used to ease the implementation of splitters for a parallel
- // version of the TrieMap.
- // */
- // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
- // null) {
- // // the case where an LNode is being iterated
- // val it = subiter
- // subiter = null
- // advance()
- // this.level += 1
- // Seq(it, this)
- // } else if (depth == -1) {
- // this.level += 1
- // Seq(this)
- // } else {
- // var d = 0
- // while (d <= depth) {
- // val rem = stack(d).length - 1 - stackpos(d)
- // if (rem > 0) {
- // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
- // stack(d) = arr1
- // stackpos(d) = -1
- // val it = newIterator(level + 1, ct, false)
- // it.stack(0) = arr2
- // it.stackpos(0) = -1
- // it.depth = 0
- // it.advance() // <-- fix it
- // this.level += 1
- // return Seq(this, it)
- // }
- // d += 1
- // }
- // this.level += 1
- // Seq(this)
- // }
-
- private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
- ArrayList<Entry<K, V>> list = new ArrayList<> ();
- while (it.hasNext ()) {
- list.add (it.next());
- }
- return list;
- }
-
- @Override
- public void remove() {
- checkState(lastReturned != null);
- ct.remove(lastReturned.getKey());
- lastReturned = null;
- }
- }
-
- /***
- * Support for EntrySet operations required by the Map interface
- */
- private final class EntrySet extends AbstractSet<Entry<K, V>> {
- @Override
- public Iterator<Entry<K, V>> iterator() {
- return TrieMap.this.iterator ();
- }
-
- @Override
- public final boolean contains(final Object o) {
- if (!(o instanceof Entry)) {
- return false;
- }
-
- final Entry<?, ?> e = (Entry<?, ?>) o;
- if (e.getKey() == null) {
- return false;
- }
- final V v = get(e.getKey());
- return v != null && v.equals(e.getValue());
- }
-
- @Override
- public final 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 TrieMap.this.remove(key, value);
- }
-
- @Override
- public final int size () {
- return TrieMap.this.size();
- }
-
- @Override
- public final void clear () {
- TrieMap.this.clear ();
- }
- }
}
Code Review / yangtools.git / blobdiff