third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java

   1 /*
   2  * (C) Copyright 2017 Pantheon Technologies, s.r.o. and others.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package org.opendaylight.yangtools.triemap;
  17
  18 import static com.google.common.base.Preconditions.checkState;
  19
  20 import java.util.ArrayList;
  21 import java.util.Iterator;
  22 import java.util.List;
  23 import java.util.Map.Entry;
  24 import java.util.NoSuchElementException;
  25
  26 class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
  27     private int level;
  28     protected TrieMap<K, V> ct;
  29     private final boolean mustInit;
  30     private final BasicNode[][] stack = new BasicNode[7][];
  31     private final int[] stackpos = new int[7];
  32     private int depth = -1;
  33     private Iterator<Entry<K, V>> subiter = null;
  34     private EntryNode<K, V> current = null;
  35     private Entry<K, V> lastReturned = null;
  36
  37     TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
  38         this.level = level;
  39         this.ct = ct;
  40         this.mustInit = mustInit;
  41         if (this.mustInit) {
  42             initialize ();
  43         }
  44     }
  45
  46     TrieMapIterator (final int level, final TrieMap<K, V> ct) {
  47         this (level, ct, true);
  48     }
  49
  50
  51     @Override
  52     public boolean hasNext() {
  53         return (current != null) || (subiter != null);
  54     }
  55
  56     @Override
  57     public Entry<K, V> next() {
  58         if (!hasNext()) {
  59             throw new NoSuchElementException();
  60         }
  61
  62         final Entry<K, V> r;
  63         if (subiter != null) {
  64             r = subiter.next();
  65             checkSubiter();
  66         } else {
  67             r = current;
  68             advance();
  69         }
  70
  71         lastReturned = r;
  72         if (r != null) {
  73             final Entry<K, V> rr = r;
  74             return nextEntry(rr);
  75         }
  76         return r;
  77     }
  78
  79     Entry<K, V> nextEntry(final Entry<K, V> rr) {
  80         return new Entry<K, V>() {
  81             @SuppressWarnings("null")
  82             private V updated = null;
  83
  84             @Override
  85             public K getKey () {
  86                 return rr.getKey ();
  87             }
  88
  89             @Override
  90             public V getValue () {
  91                 return (updated == null) ? rr.getValue (): updated;
  92             }
  93
  94             @Override
  95             public V setValue (final V value) {
  96                 updated = value;
  97                 return ct.replace (getKey (), value);
  98             }
  99         };
 100     }
 101
 102     private void readin (final INode<K, V> in) {
 103         MainNode<K, V> m = in.gcasRead (ct);
 104         if (m instanceof CNode) {
 105             CNode<K, V> cn = (CNode<K, V>) m;
 106             depth += 1;
 107             stack [depth] = cn.array;
 108             stackpos [depth] = -1;
 109             advance ();
 110         } else if (m instanceof TNode) {
 111             current = (TNode<K, V>) m;
 112         } else if (m instanceof LNode) {
 113             subiter = ((LNode<K, V>) m).iterator();
 114             checkSubiter ();
 115         } else if (m == null) {
 116             current = null;
 117         }
 118     }
 119
 120     // @inline
 121     private void checkSubiter () {
 122         if (!subiter.hasNext ()) {
 123             subiter = null;
 124             advance ();
 125         }
 126     }
 127
 128     // @inline
 129     void initialize () {
 130         // assert (ct.isReadOnly());
 131         readin(ct.RDCSS_READ_ROOT());
 132     }
 133
 134     void advance () {
 135         if (depth >= 0) {
 136             int npos = stackpos [depth] + 1;
 137             if (npos < stack [depth].length) {
 138                 stackpos [depth] = npos;
 139                 BasicNode elem = stack [depth] [npos];
 140                 if (elem instanceof SNode) {
 141                     current = (SNode<K, V>) elem;
 142                 } else if (elem instanceof INode) {
 143                     readin ((INode<K, V>) elem);
 144                 }
 145             } else {
 146                 depth -= 1;
 147                 advance ();
 148             }
 149         } else {
 150             current = null;
 151         }
 152     }
 153
 154     protected TrieMapIterator<K, V> newIterator(final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
 155         return new TrieMapIterator<> (_lev, _ct, _mustInit);
 156     }
 157
 158     protected void dupTo(final TrieMapIterator<K, V> it) {
 159         it.level = this.level;
 160         it.ct = this.ct;
 161         it.depth = this.depth;
 162         it.current = this.current;
 163
 164         // these need a deep copy
 165         System.arraycopy (this.stack, 0, it.stack, 0, 7);
 166         System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
 167
 168         // this one needs to be evaluated
 169         if (this.subiter == null) {
 170             it.subiter = null;
 171         } else {
 172             List<Entry<K, V>> lst = toList (this.subiter);
 173             this.subiter = lst.iterator ();
 174             it.subiter = lst.iterator ();
 175         }
 176     }
 177
 178     // /** Returns a sequence of iterators over subsets of this iterator.
 179     // * It's used to ease the implementation of splitters for a parallel
 180     // version of the TrieMap.
 181     // */
 182     // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
 183     // null) {
 184     // // the case where an LNode is being iterated
 185     // val it = subiter
 186     // subiter = null
 187     // advance()
 188     // this.level += 1
 189     // Seq(it, this)
 190     // } else if (depth == -1) {
 191     // this.level += 1
 192     // Seq(this)
 193     // } else {
 194     // var d = 0
 195     // while (d <= depth) {
 196     // val rem = stack(d).length - 1 - stackpos(d)
 197     // if (rem > 0) {
 198     // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
 199     // stack(d) = arr1
 200     // stackpos(d) = -1
 201     // val it = newIterator(level + 1, ct, false)
 202     // it.stack(0) = arr2
 203     // it.stackpos(0) = -1
 204     // it.depth = 0
 205     // it.advance() // <-- fix it
 206     // this.level += 1
 207     // return Seq(this, it)
 208     // }
 209     // d += 1
 210     // }
 211     // this.level += 1
 212     // Seq(this)
 213     // }
 214
 215     private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
 216         ArrayList<Entry<K, V>> list = new ArrayList<> ();
 217         while (it.hasNext ()) {
 218             list.add (it.next());
 219         }
 220         return list;
 221     }
 222
 223     @Override
 224     public void remove() {
 225         checkState(lastReturned != null);
 226         ct.remove(lastReturned.getKey());
 227         lastReturned = null;
 228     }
 229 }