--- /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 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[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;
+ }
+}
\ No newline at end of file
Code Review / yangtools.git / blobdiff