third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/AbstractIterator.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 org.opendaylight.yangtools.triemap.Constants.MAX_DEPTH;
  19
  20 import java.util.Iterator;
  21 import java.util.Map.Entry;
  22 import java.util.NoSuchElementException;
  23
  24 /**
  25  * Abstract base class for iterators supporting {@link AbstractEntrySet} subclasses.
  26  *
  27  * @author Robert Varga
  28  *
  29  * @param <K> the type of entry keys
  30  * @param <V> the type of entry values
  31  */
  32 abstract class AbstractIterator<K, V> implements Iterator<Entry<K, V>> {
  33     private final BasicNode[][] nodeStack = new BasicNode[MAX_DEPTH][];
  34     private final int[] positionStack = new int[MAX_DEPTH];
  35     private final TrieMap<K, V> map;
  36
  37     private LNodeEntries<K, V> lnode;
  38     private EntryNode<K, V> current;
  39     private int depth = -1;
  40
  41     AbstractIterator(final ImmutableTrieMap<K, V> map) {
  42         this.map = map;
  43         readin(map.RDCSS_READ_ROOT());
  44     }
  45
  46     @Override
  47     public final boolean hasNext() {
  48         return current != null || lnode != null;
  49     }
  50
  51     @Override
  52     public final Entry<K, V> next() {
  53         final Entry<K, V> entry;
  54
  55         // Check LNode iterator first
  56         if (lnode != null) {
  57             entry = lnode;
  58             lnode = lnode.next();
  59             if (lnode == null) {
  60                 advance();
  61             }
  62         } else {
  63             entry = current;
  64             advance();
  65         }
  66
  67         if (entry == null) {
  68             throw new NoSuchElementException();
  69         }
  70
  71         return wrapEntry(entry);
  72     }
  73
  74     /**
  75      * Wrap entry so it can be presented to the user.
  76      *
  77      * @param entry An immutable entry, guaranteed to be non-null
  78      * @return Wrapped entry, may not be null
  79      */
  80     abstract Entry<K, V> wrapEntry(Entry<K, V> entry);
  81
  82     /**
  83      * Read the contents of an INode's main node.
  84      *
  85      * @param in INode to be read.
  86      */
  87     private void readin(final INode<K, V> in) {
  88         final MainNode<K, V> m = in.gcasRead(map);
  89         if (m instanceof CNode) {
  90             // Enter the next level
  91             final CNode<K, V> cn = (CNode<K, V>) m;
  92             depth++;
  93             nodeStack[depth] = cn.array;
  94             positionStack[depth] = -1;
  95             advance();
  96         } else if (m instanceof TNode) {
  97             current = (TNode<K, V>) m;
  98         } else if (m instanceof LNode) {
  99             lnode = ((LNode<K, V>) m).entries();
 100         } else if (m == null) {
 101             current = null;
 102         }
 103     }
 104
 105     private void advance() {
 106         if (depth >= 0) {
 107             int npos = positionStack[depth] + 1;
 108             if (npos < nodeStack[depth].length) {
 109                 positionStack [depth] = npos;
 110                 BasicNode elem = nodeStack[depth][npos];
 111                 if (elem instanceof SNode) {
 112                     current = (SNode<K, V>) elem;
 113                 } else if (elem instanceof INode) {
 114                     readin((INode<K, V>) elem);
 115                 }
 116             } else {
 117                 depth -= 1;
 118                 advance();
 119             }
 120         } else {
 121             current = null;
 122         }
 123     }
 124 }