- private static 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 KVNode<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();
- }
-
- Entry<K, V> r = null;
- if (subiter != null) {
- r = subiter.next ();
- checkSubiter ();
- } else {
- r = current.kvPair ();
- 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>() {
- 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 ());
- INode<K, V> r = ct.RDCSS_READ_ROOT ();
- readin (r);
- }
-
- 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;
- }
-
- void printDebug () {
- System.out.println ("ctrie iterator");
- System.out.println (Arrays.toString (stackpos));
- System.out.println ("depth: " + depth);
- System.out.println ("curr.: " + current);
- // System.out.println(stack.mkString("\n"));
- }
-
- @Override
- public void remove() {
- checkState(lastReturned != null);
- ct.remove(lastReturned.getKey());
- lastReturned = null;
- }