From 9da32d0061cb13e57ff39b2f884753cc5f69adf3 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Tue, 3 Jan 2017 03:02:29 +0100 Subject: [PATCH 1/1] BUG-7464: Split out entryset and iterator classes This is a preparatory patch, splitting out support classes so they can be fixed up and refactored as needed. Change-Id: Ib7b994f2f4e114ec0a56d8930e7ba7320e18201c Signed-off-by: Robert Varga --- .../yangtools/triemap/EntrySet.java | 84 +++++ .../yangtools/triemap/TrieMap.java | 299 +----------------- .../yangtools/triemap/TrieMapIterator.java | 229 ++++++++++++++ .../triemap/TrieMapReadOnlyIterator.java | 51 +++ 4 files changed, 366 insertions(+), 297 deletions(-) create mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntrySet.java create mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapIterator.java create mode 100644 third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapReadOnlyIterator.java diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntrySet.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntrySet.java new file mode 100644 index 0000000000..6e7d69de2a --- /dev/null +++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/EntrySet.java @@ -0,0 +1,84 @@ +/* + * (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.checkNotNull; + +import java.util.AbstractSet; +import java.util.Iterator; +import java.util.Map.Entry; + +/*** + * Support for EntrySet operations required by the Map interface + * + * @param the type of keys + * @param the type of values + */ +final class EntrySet extends AbstractSet> { + private final TrieMap map; + + EntrySet(final TrieMap map) { + this.map = checkNotNull(map); + } + + @Override + public Iterator> iterator() { + return map.iterator(); + } + + @Override + public boolean contains(final Object o) { + if (!(o instanceof Entry)) { + return false; + } + + final Entry e = (Entry) o; + if (e.getKey() == null) { + return false; + } + final V v = map.get(e.getKey()); + return v != null && v.equals(e.getValue()); + } + + @Override + public boolean remove(final Object o) { + if (!(o instanceof Entry)) { + return false; + } + + final Entry e = (Entry) o; + final Object key = e.getKey(); + if (key == null) { + return false; + } + final Object value = e.getValue(); + if (value == null) { + return false; + } + + return map.remove(key, value); + } + + @Override + public final int size() { + return map.size(); + } + + @Override + public final void clear() { + map.clear(); + } +} diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java index 94347299a0..0aacd4f5f7 100644 --- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java +++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java @@ -16,18 +16,13 @@ package org.opendaylight.yangtools.triemap; import static com.google.common.base.Preconditions.checkNotNull; -import static com.google.common.base.Preconditions.checkState; import static org.opendaylight.yangtools.triemap.LookupResult.RESTART; import com.google.common.annotations.Beta; import java.io.ObjectStreamException; import java.io.Serializable; import java.util.AbstractMap; -import java.util.AbstractSet; -import java.util.ArrayList; import java.util.Iterator; -import java.util.List; -import java.util.NoSuchElementException; import java.util.Optional; import java.util.Set; import java.util.concurrent.ConcurrentMap; @@ -50,7 +45,7 @@ public abstract class TrieMap extends AbstractMap implements Concurr /** * EntrySet */ - private final EntrySet entrySet = new EntrySet(); + private final EntrySet entrySet = new EntrySet<>(this); private final Equivalence equiv; TrieMap(final Equivalence equiv) { @@ -201,7 +196,7 @@ public abstract class TrieMap extends AbstractMap implements Concurr * * @return */ - Iterator> iterator() { + final Iterator> iterator() { // FIXME: it would be nice to have a ReadWriteTrieMap with read-only iterator return isReadOnly() ? new TrieMapReadOnlyIterator<>(0, this) : new TrieMapIterator<>(0, this); } @@ -215,294 +210,4 @@ public abstract class TrieMap extends AbstractMap implements Concurr final Iterator> readOnlyIterator() { return new TrieMapReadOnlyIterator<>(0, immutableSnapshot()); } - - /** - * This iterator is a read-only one and does not allow for any update - * operations on the underlying data structure. - * - * @param - * @param - */ - private static final class TrieMapReadOnlyIterator extends TrieMapIterator { - TrieMapReadOnlyIterator (final int level, final TrieMap ct, final boolean mustInit) { - super (level, ct, mustInit); - } - - TrieMapReadOnlyIterator (final int level, final TrieMap ct) { - this (level, ct, true); - } - @Override - void initialize () { - assert (ct.isReadOnly ()); - super.initialize (); - } - - @Override - public void remove () { - throw new UnsupportedOperationException ("Operation not supported for read-only iterators"); - } - - @Override - Entry nextEntry(final Entry rr) { - // Return non-updatable entry - return rr; - } - } - - private static class TrieMapIterator implements Iterator> { - private int level; - protected TrieMap 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> subiter = null; - private EntryNode current = null; - private Entry lastReturned = null; - - TrieMapIterator (final int level, final TrieMap ct, final boolean mustInit) { - this.level = level; - this.ct = ct; - this.mustInit = mustInit; - if (this.mustInit) { - initialize (); - } - } - - TrieMapIterator (final int level, final TrieMap ct) { - this (level, ct, true); - } - - - @Override - public boolean hasNext() { - return (current != null) || (subiter != null); - } - - @Override - public Entry next() { - if (!hasNext()) { - throw new NoSuchElementException(); - } - - final Entry r; - if (subiter != null) { - r = subiter.next(); - checkSubiter(); - } else { - r = current; - advance(); - } - - lastReturned = r; - if (r != null) { - final Entry rr = r; - return nextEntry(rr); - } - return r; - } - - Entry nextEntry(final Entry rr) { - return new Entry() { - @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 in) { - MainNode m = in.gcasRead (ct); - if (m instanceof CNode) { - CNode cn = (CNode) m; - depth += 1; - stack [depth] = cn.array; - stackpos [depth] = -1; - advance (); - } else if (m instanceof TNode) { - current = (TNode) m; - } else if (m instanceof LNode) { - subiter = ((LNode) 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) elem; - } else if (elem instanceof INode) { - readin ((INode) elem); - } - } else { - depth -= 1; - advance (); - } - } else { - current = null; - } - } - - protected TrieMapIterator newIterator(final int _lev, final TrieMap _ct, final boolean _mustInit) { - return new TrieMapIterator<> (_lev, _ct, _mustInit); - } - - protected void dupTo(final TrieMapIterator 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> 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> toList (final Iterator> it) { - ArrayList> 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; - } - } - - /*** - * Support for EntrySet operations required by the Map interface - */ - private final class EntrySet extends AbstractSet> { - @Override - public Iterator> iterator() { - return TrieMap.this.iterator (); - } - - @Override - public final boolean contains(final Object o) { - if (!(o instanceof Entry)) { - return false; - } - - final Entry e = (Entry) o; - if (e.getKey() == null) { - return false; - } - final V v = get(e.getKey()); - return v != null && v.equals(e.getValue()); - } - - @Override - public final boolean remove(final Object o) { - if (!(o instanceof Entry)) { - return false; - } - final Entry e = (Entry) o; - final Object key = e.getKey(); - if (key == null) { - return false; - } - final Object value = e.getValue(); - if (value == null) { - return false; - } - - return TrieMap.this.remove(key, value); - } - - @Override - public final int size () { - return TrieMap.this.size(); - } - - @Override - public final void clear () { - TrieMap.this.clear (); - } - } } 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 implements Iterator> { + private int level; + protected TrieMap 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> subiter = null; + private EntryNode current = null; + private Entry lastReturned = null; + + TrieMapIterator (final int level, final TrieMap ct, final boolean mustInit) { + this.level = level; + this.ct = ct; + this.mustInit = mustInit; + if (this.mustInit) { + initialize (); + } + } + + TrieMapIterator (final int level, final TrieMap ct) { + this (level, ct, true); + } + + + @Override + public boolean hasNext() { + return (current != null) || (subiter != null); + } + + @Override + public Entry next() { + if (!hasNext()) { + throw new NoSuchElementException(); + } + + final Entry r; + if (subiter != null) { + r = subiter.next(); + checkSubiter(); + } else { + r = current; + advance(); + } + + lastReturned = r; + if (r != null) { + final Entry rr = r; + return nextEntry(rr); + } + return r; + } + + Entry nextEntry(final Entry rr) { + return new Entry() { + @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 in) { + MainNode m = in.gcasRead (ct); + if (m instanceof CNode) { + CNode cn = (CNode) m; + depth += 1; + stack [depth] = cn.array; + stackpos [depth] = -1; + advance (); + } else if (m instanceof TNode) { + current = (TNode) m; + } else if (m instanceof LNode) { + subiter = ((LNode) 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) elem; + } else if (elem instanceof INode) { + readin ((INode) elem); + } + } else { + depth -= 1; + advance (); + } + } else { + current = null; + } + } + + protected TrieMapIterator newIterator(final int _lev, final TrieMap _ct, final boolean _mustInit) { + return new TrieMapIterator<> (_lev, _ct, _mustInit); + } + + protected void dupTo(final TrieMapIterator 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> 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> toList (final Iterator> it) { + ArrayList> 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 diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapReadOnlyIterator.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapReadOnlyIterator.java new file mode 100644 index 0000000000..9899bef313 --- /dev/null +++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMapReadOnlyIterator.java @@ -0,0 +1,51 @@ +/* + * (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 java.util.Map.Entry; + +/** + * This iterator is a read-only one and does not allow for any update + * operations on the underlying data structure. + * + * @param the type of keys + * @param the type of values + */ +final class TrieMapReadOnlyIterator extends TrieMapIterator { + TrieMapReadOnlyIterator (final int level, final TrieMap ct, final boolean mustInit) { + super (level, ct, mustInit); + } + + TrieMapReadOnlyIterator (final int level, final TrieMap ct) { + this (level, ct, true); + } + @Override + void initialize () { + assert (ct.isReadOnly ()); + super.initialize (); + } + + @Override + public void remove () { + throw new UnsupportedOperationException ("Operation not supported for read-only iterators"); + } + + @Override + Entry nextEntry(final Entry rr) { + // Return non-updatable entry + return rr; + } +} \ No newline at end of file -- 2.36.6