X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;f=third-party%2Ftriemap%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fyangtools%2Ftriemap%2FTrieMapIterator.java;fp=third-party%2Ftriemap%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fyangtools%2Ftriemap%2FTrieMapIterator.java;h=08b62e78422371db3ae6bbbc0416588987dd7772;hb=9da32d0061cb13e57ff39b2f884753cc5f69adf3;hp=0000000000000000000000000000000000000000;hpb=5f7479eeea883485aeb64db74787f26d4f3e7870;p=yangtools.git

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java
new file mode 100644
index 0000000000..08b62e7842
--- /dev/null
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java
@@ -0,0 +1,229 @@
+/*
+ * (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