--- /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.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 <K> the type of entry keys
+ * @param <V> the type of entry values
+ */
+abstract class AbstractIterator<K, V> implements Iterator<Entry<K, V>> {
+ private final BasicNode[][] nodeStack = new BasicNode[MAX_DEPTH][];
+ private final int[] positionStack = new int[MAX_DEPTH];
+ private final TrieMap<K, V> map;
+
+ private LNodeEntries<K, V> lnode;
+ private EntryNode<K, V> current;
+ private int depth = -1;
+
+ AbstractIterator(final ImmutableTrieMap<K, V> map) {
+ this.map = map;
+ readin(map.RDCSS_READ_ROOT());
+ }
+
+ @Override
+ public final boolean hasNext() {
+ return current != null || lnode != null;
+ }
+
+ @Override
+ public final Entry<K, V> next() {
+ final Entry<K, V> 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<K, V> wrapEntry(Entry<K, V> entry);
+
+ /**
+ * Read the contents of an INode's main node.
+ *
+ * @param in INode to be read.
+ */
+ private void readin(final INode<K, V> in) {
+ final MainNode<K, V> m = in.gcasRead(map);
+ if (m instanceof CNode) {
+ // Enter the next level
+ final CNode<K, V> cn = (CNode<K, V>) m;
+ depth++;
+ nodeStack[depth] = cn.array;
+ positionStack[depth] = -1;
+ advance();
+ } else if (m instanceof TNode) {
+ current = (TNode<K, V>) m;
+ } else if (m instanceof LNode) {
+ lnode = ((LNode<K, V>) 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<K, V>) elem;
+ } else if (elem instanceof INode) {
+ readin((INode<K, V>) elem);
+ }
+ } else {
+ depth -= 1;
+ advance();
+ }
+ } else {
+ current = null;
+ }
+ }
+}
\ No newline at end of file
--- /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 java.util.Map.Entry;
+
+/**
+ * Specialized immutable iterator for use with {@link ImmutableEntrySet}.
+ *
+ * @author Robert Varga
+ *
+ * @param <K> the type of entry keys
+ * @param <V> the type of entry values
+ */
+final class ImmutableIterator<K, V> extends AbstractIterator<K, V> {
+ ImmutableIterator(final ImmutableTrieMap<K, V> map) {
+ super(map);
+ }
+
+ @Override
+ Entry<K, V> wrapEntry(final Entry<K, V> entry) {
+ return entry;
+ }
+}
import com.google.common.annotations.Beta;
import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
-import java.util.Iterator;
import java.util.Map;
import java.util.function.BiFunction;
import java.util.function.Function;
return true;
}
+ @Override
+ ImmutableIterator<K, V> iterator() {
+ return immutableIterator();
+ }
+
@Override
INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
return root;
static UnsupportedOperationException unsupported() {
return new UnsupportedOperationException("Attempted to modify a read-only view");
}
-
- @Override
- Iterator<Entry<K, V>> iterator() {
- return immutableIterator();
- }
}
*/
package org.opendaylight.yangtools.triemap;
-import java.util.Iterator;
-import java.util.Map.Entry;
-
final class LNode<K, V> extends MainNode<K, V> {
- private final LNodeEntries<K, V> listmap;
+ // Internally-linked single list of of entries
+ private final LNodeEntries<K, V> entries;
+ private final int size;
- private LNode(final LNodeEntries<K, V> listmap) {
- this.listmap = listmap;
+ private LNode(final LNodeEntries<K, V> 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));
+ this(LNodeEntries.map(k1, v1, k2, v2), 2);
}
LNode<K, V> insertChild( final K k, final V v) {
- return new LNode<>(listmap.insert(k, v));
+ return new LNode<>(entries.insert(k, v), size + 1);
}
MainNode<K, V> removeChild(final LNodeEntry<K, V> entry, final int hc) {
- // We only ever create ListMaps with two or more entries, and remove them as soon as they reach one element
- // (below), so we cannot observe a null return here.
- final LNodeEntries<K, V> map = listmap.remove(entry);
- if (map.isSingle()) {
+ // 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<K, V> 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);
+ return new LNode<>(map, size - 1);
}
MainNode<K, V> replaceChild(final LNodeEntry<K, V> entry, final V v) {
- return new LNode<>(listmap.replace(entry, v));
+ return new LNode<>(entries.replace(entry, v), size);
}
LNodeEntry<K, V> get(final Equivalence<? super K> equiv, final K k) {
- return listmap.findEntry(equiv, k);
+ return entries.findEntry(equiv, k);
+ }
+
+ LNodeEntries<K, V> entries() {
+ return entries;
}
@Override
int cachedSize(final TrieMap<?, ?> ct) {
- return listmap.size();
+ return size;
}
@Override
// (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
return "LNode";
}
-
- Iterator<Entry<K, V>> iterator() {
- return listmap.iterator();
- }
-}
\ No newline at end of file
+}
*/
package org.opendaylight.yangtools.triemap;
-import java.util.Iterator;
-import java.util.Map.Entry;
-import java.util.NoSuchElementException;
-
/**
- * Similar to Scala's ListMap. Stores a linked set of entries, guaranteed to contain unique entry keys.
+ * Similar to Scala's ListMap, this is a single-linked list of set of map entries. Aside from the Set contract, this
+ * class fulfills the requirements for an immutable map entryset.
*
* @author Robert Varga
*
super(k, v);
}
- @Override
- boolean isSingle() {
- return true;
- }
-
@Override
LNodeEntries<K, V> next() {
return null;
}
private static final class Multiple<K, V> extends LNodeEntries<K, V> {
- // Modified during remove only
+ // Modified during remove only, otherwise final
LNodeEntries<K, V> next;
// Used in remove() only
this.next = next;
}
- @Override
- boolean isSingle() {
- return next == null;
- }
-
@Override
LNodeEntries<K, V> next() {
return next;
return new Multiple<>(k1, v1, new Single<>(k2, v2));
}
- abstract boolean isSingle();
-
+ /**
+ * 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<K, V> next();
final LNodeEntry<K, V> findEntry(final Equivalence<? super K> equiv, final K key) {
}
final LNodeEntries<K, V> replace(final LNodeEntry<K, V> entry, final V v) {
- final LNodeEntries<K, V> removed = remove(entry);
- return removed == null ? new Single<>(entry.getKey(), v) : new Multiple<>(entry.getKey(), v, removed);
+ final LNodeEntries<K, V> removed;
+ return (removed = remove(entry)) == null ? new Single<>(entry.getKey(), v)
+ : new Multiple<>(entry.getKey(), v, removed);
}
final LNodeEntries<K, V> remove(final LNodeEntry<K, V> entry) {
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<K, V> ret = new Multiple<>(this);
Multiple<K, V> last = ret;
LNodeEntries<K, V> cur = next();
while (cur != null) {
- // We cannot use equals() here, as it is wired to key/value equality,
- // which we really do not want.
+ // 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;
throw new IllegalStateException(String.format("Entry %s not found", entry));
}
-
- // No need to specialize these two methods, as they are invoked only from a stable LNode, at which point it is
- // guaranteed to be a Multiple.
- final int size() {
- int sz = 1;
- for (LNodeEntries<?, ?> wlk = next(); wlk != null; wlk = wlk.next()) {
- sz++;
- }
- return sz;
- }
-
- final Iterator<Entry<K, V>> iterator() {
- return new NodeIterator<>(this);
- }
-
- static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
- private LNodeEntries<K, V> n;
-
- NodeIterator(final LNodeEntries<K, V> n) {
- this.n = n;
- }
-
- @Override
- public boolean hasNext() {
- return n != null;
- }
-
- @Override
- public Entry<K, V> next() {
- if (n == null) {
- throw new NoSuchElementException();
- }
-
- final Entry<K, V> res = n;
- n = n.next();
- return res;
- }
- }
}
--- /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 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 <K> the type of entry keys
+ * @param <V> the type of entry values
+ */
+final class MutableIterator<K, V> extends AbstractIterator<K, V> {
+ private final MutableTrieMap<K, V> mutable;
+
+ private Entry<K, V> lastReturned;
+
+ MutableIterator(final MutableTrieMap<K, V> map) {
+ super(map.immutableSnapshot());
+ this.mutable = map;
+ }
+
+ @Override
+ public void remove() {
+ checkState(lastReturned != null);
+ mutable.remove(lastReturned.getKey());
+ lastReturned = null;
+ }
+
+ @Override
+ Entry<K, V> wrapEntry(final Entry<K, V> 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<K, V> implements Entry<K, V> {
+ private final MutableTrieMap<K, V> map;
+ private final Entry<K, V> delegate;
+
+ @SuppressWarnings("null")
+ private V newValue = null;
+
+ MutableEntry(final MutableTrieMap<K, V> map, final Entry<K, V> 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 o) {
+ return EntryUtil.equal(o, getKey(), getValue());
+ }
+
+ @Override
+ public String toString() {
+ return EntryUtil.string(getKey(), getValue());
+ }
+ }
+}
import com.google.common.annotations.Beta;
import com.google.common.base.Verify;
import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
-import java.util.Iterator;
import java.util.Optional;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
return new MutableEntrySet<>(this);
}
+ @Override
+ MutableIterator<K, V> iterator() {
+ return new MutableIterator<>(this);
+ }
+
@Override
boolean isReadOnly() {
return false;
this.nv = nv;
}
}
-
- @Override
- Iterator<Entry<K, V>> iterator() {
- return new TrieMapIterator<>(0, this);
- }
}
import java.io.ObjectStreamException;
import java.io.Serializable;
import java.util.AbstractMap;
-import java.util.Iterator;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
*
* @return
*/
- abstract Iterator<Entry<K, V>> iterator();
+ abstract AbstractIterator<K, V> iterator();
/* internal methods provided for subclasses */
*
* @return
*/
- final Iterator<Entry<K, V>> immutableIterator() {
- return new TrieMapReadOnlyIterator<>(0, immutableSnapshot());
+ final ImmutableIterator<K, V> immutableIterator() {
+ return new ImmutableIterator<>(immutableSnapshot());
}
@SuppressWarnings("null")
+++ /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 com.google.common.base.Preconditions.checkState;
-import static org.opendaylight.yangtools.triemap.Constants.MAX_DEPTH;
-
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map.Entry;
-import java.util.NoSuchElementException;
-
-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[MAX_DEPTH][];
- private final int[] stackpos = new int[MAX_DEPTH];
- 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;
- }
-}
\ No newline at end of file
+++ /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 java.util.Map.Entry;
-
-/**
- * This iterator is a read-only one and does not allow for any update
- * operations on the underlying data structure.
- *
- * @param <K> the type of keys
- * @param <V> the type of values
- */
-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;
- }
-}
\ No newline at end of file
public class TestMapIterator {
@Test
- public void testMapIterator () {
+ public void testMapIterator() {
final Random random = new Random();
for (int i = 0; i < 60 * 1000; i+= 400 + random.nextInt(400)) {
}
}
+ @Test
+ public void testMapImmutableIterator() {
+ final Random random = new Random();
+
+ for (int i = 0; i < 60 * 1000; i+= 400 + random.nextInt(400)) {
+ final Map<Integer, Integer> bt = TrieMap.create();
+ for (int j = 0; j < i; j++) {
+ assertNull(bt.put(Integer.valueOf(j), Integer.valueOf(j)));
+ }
+ int count = 0;
+ final Set<Integer> set = new HashSet<>();
+ for (final Entry<Integer, Integer> 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();
Code Review / yangtools.git / commitdiff