From b505e991213130edd7b70718fca16d911adf8bfd Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Sun, 1 Jan 2017 22:07:09 +0100 Subject: [PATCH 1/1] BUG-7464: Improve Map contract compliance Add explicit precondition guards against null keys and values and fix iterators not currectly throwing exceptions. Also make sure entrySet().contains() and remove() operations do not throw, but return correct results. Change-Id: I645686112ebb3675b73349d0c3096a3901243522 Signed-off-by: Robert Varga --- .../yangtools/triemap/TrieMap.java | 209 +++++++++--------- .../yangtools/triemap/TestDelete.java | 29 +++ .../yangtools/triemap/TestInsert.java | 15 ++ .../yangtools/triemap/TestMapIterator.java | 21 ++ 4 files changed, 168 insertions(+), 106 deletions(-) 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 acb944ede4..feb9539338 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 @@ -15,7 +15,10 @@ */ package org.opendaylight.yangtools.triemap; -import com.google.common.base.Preconditions; +import static com.google.common.base.Preconditions.checkNotNull; +import static com.google.common.base.Preconditions.checkState; + +import com.google.common.collect.Iterators; import java.io.ObjectStreamException; import java.io.Serializable; import java.util.AbstractMap; @@ -24,6 +27,7 @@ import java.util.ArrayList; import java.util.Arrays; 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; @@ -79,7 +83,7 @@ public final class TrieMap extends AbstractMap implements Concurrent } final boolean CAS_ROOT(final Object ov, final Object nv) { - Preconditions.checkState(!readOnly, "Attempted to modify a read-only snapshot"); + checkState(!readOnly, "Attempted to modify a read-only snapshot"); return ROOT_UPDATER.compareAndSet (this, ov, nv); } @@ -100,55 +104,50 @@ public final class TrieMap extends AbstractMap implements Concurrent final Object r = /* READ */root; if (r instanceof INode) { return (INode) r; - } else if (r instanceof RDCSS_Descriptor) { - return RDCSS_Complete (abort); - } else { - throw new IllegalStateException("Unhandled root " + r); } + + checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r); + return RDCSS_Complete(abort); } private INode RDCSS_Complete(final boolean abort) { while (true) { - final Object v = /* READ */root; - if (v instanceof INode) { - return (INode) v; + final Object r = /* READ */root; + if (r instanceof INode) { + return (INode) r; } - if (v instanceof RDCSS_Descriptor) { - final RDCSS_Descriptor desc = (RDCSS_Descriptor) v; - final INode ov = desc.old; - final MainNode exp = desc.expectedmain; - final INode nv = desc.nv; - - if (abort) { - if (CAS_ROOT(desc, ov)) { - return ov; - } + checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r); + final RDCSS_Descriptor desc = (RDCSS_Descriptor) r; + final INode ov = desc.old; + final MainNode exp = desc.expectedmain; + final INode nv = desc.nv; - // Tail recursion: return RDCSS_Complete(abort); - continue; + if (abort) { + if (CAS_ROOT(desc, ov)) { + return ov; } - final MainNode oldmain = ov.gcasRead(this); - if (oldmain == exp) { - if (CAS_ROOT(desc, nv)) { - desc.committed = true; - return nv; - } - - // Tail recursion: return RDCSS_Complete(abort); - continue; - } + // Tail recursion: return RDCSS_Complete(abort); + continue; + } - if (CAS_ROOT(desc, ov)) { - return ov; + final MainNode oldmain = ov.gcasRead(this); + if (oldmain == exp) { + if (CAS_ROOT(desc, nv)) { + desc.committed = true; + return nv; } // Tail recursion: return RDCSS_Complete(abort); continue; } - throw new IllegalStateException("Unexpected root " + v); + if (CAS_ROOT(desc, ov)) { + return ov; + } + + // Tail recursion: return RDCSS_Complete(abort); } } @@ -296,59 +295,57 @@ public final class TrieMap extends AbstractMap implements Concurrent return equiv.equivalent(k1, k2); } - V lookup(final K k) { - return (V) lookuphc(k, computeHash(k)); - } - @Override - public V get(final Object k) { - return lookup((K)k); + public V get(final Object key) { + final K k = (K) checkNotNull(key); + return (V) lookuphc(k, computeHash(k)); } @Override public V put(final K key, final V value) { ensureReadWrite(); - final int hc = computeHash(key); - return insertifhc (key, hc, value, null).orElse(null); + final K k = checkNotNull(key); + return insertifhc(k, computeHash(k), checkNotNull(value), null).orElse(null); } - void add(final K k, final V v) { - inserthc(k, computeHash(k), v); + void add(final K key, final V value) { + final K k = checkNotNull(key); + inserthc(k, computeHash(k), checkNotNull(value)); } @Override - public V remove(final Object k) { + public V remove(final Object key) { ensureReadWrite(); - final int hc = computeHash ((K)k); - return removehc ((K)k, (V) null, hc).orElse(null); + final K k = (K) checkNotNull(key); + return removehc(k, (V) null, computeHash(k)).orElse(null); } @Override - public V putIfAbsent(final K k, final V v) { + public V putIfAbsent(final K key, final V value) { ensureReadWrite(); - final int hc = computeHash (k); - return insertifhc (k, hc, v, INode.KEY_ABSENT).orElse(null); + final K k = checkNotNull(key); + return insertifhc(k, computeHash(k), checkNotNull(value), INode.KEY_ABSENT).orElse(null); } @Override - public boolean remove(final Object k, final Object v) { + public boolean remove(final Object key, final Object v) { ensureReadWrite(); - final int hc = computeHash ((K)k); - return removehc((K)k, (V)v, hc).isPresent(); + final K k = (K) checkNotNull(key); + return removehc(k, (V) checkNotNull(v), computeHash(k)).isPresent(); } @Override - public boolean replace(final K k, final V oldvalue, final V newvalue) { + public boolean replace(final K key, final V oldValue, final V newValue) { ensureReadWrite(); - final int hc = computeHash (k); - return insertifhc (k, hc, newvalue, oldvalue).isPresent(); + final K k = checkNotNull(key); + return insertifhc(k, computeHash(k), checkNotNull(newValue), checkNotNull(oldValue)).isPresent(); } @Override - public V replace(final K k, final V v) { + public V replace(final K key, final V value) { ensureReadWrite(); - final int hc = computeHash (k); - return insertifhc (k, hc, v, INode.KEY_PRESENT).orElse(null); + final K k = checkNotNull(key); + return insertifhc (k, computeHash(k), checkNotNull(value), INode.KEY_PRESENT).orElse(null); } /*** @@ -387,7 +384,7 @@ public final class TrieMap extends AbstractMap implements Concurrent @Override public boolean containsKey(final Object key) { - return lookup((K) key) != null; + return get(key) != null; } @Override @@ -471,32 +468,31 @@ public final class TrieMap extends AbstractMap implements Concurrent @Override - public boolean hasNext () { + public boolean hasNext() { return (current != null) || (subiter != null); } @Override - public Entry next () { - if (hasNext ()) { - Entry r = null; - if (subiter != null) { - r = subiter.next (); - checkSubiter (); - } else { - r = current.kvPair (); - advance (); - } + public Entry next() { + if (!hasNext()) { + throw new NoSuchElementException(); + } - lastReturned = r; - if (r != null) { - final Entry rr = r; - return nextEntry(rr); - } - return r; + Entry r = null; + if (subiter != null) { + r = subiter.next (); + checkSubiter (); } else { - // return Iterator.empty ().next (); - return null; + r = current.kvPair (); + advance (); } + + lastReturned = r; + if (r != null) { + final Entry rr = r; + return nextEntry(rr); + } + return r; } Entry nextEntry(final Entry rr) { @@ -510,7 +506,7 @@ public final class TrieMap extends AbstractMap implements Concurrent @Override public V getValue () { - return (updated == null)?rr.getValue (): updated; + return (updated == null) ? rr.getValue (): updated; } @Override @@ -638,7 +634,7 @@ public final class TrieMap extends AbstractMap implements Concurrent private List> toList (final Iterator> it) { ArrayList> list = new ArrayList<> (); while (it.hasNext ()) { - list.add (it.next ()); + list.add (it.next()); } return list; } @@ -652,55 +648,57 @@ public final class TrieMap extends AbstractMap implements Concurrent } @Override - public void remove () { - if (lastReturned != null) { - ct.remove (lastReturned.getKey ()); - lastReturned = null; - } else { - throw new IllegalStateException(); - } + 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 () { + public Iterator> iterator() { return TrieMap.this.iterator (); } @Override - public final boolean contains (final Object o) { + public final boolean contains(final Object o) { if (!(o instanceof Entry)) { return false; } - final Entry e = (Entry) o; - final K k = e.getKey (); - final V v = lookup (k); - return v != null; + + 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) { + public final boolean remove(final Object o) { if (!(o instanceof Entry)) { return false; } - final Entry e = (Entry) o; - final K k = e.getKey(); - return null != TrieMap.this.remove(k); + 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 () { - int size = 0; - for (final Iterator i = iterator (); i.hasNext (); i.next ()) { - size++; - } - return size; + return Iterators.size(iterator()); } @Override @@ -708,5 +706,4 @@ public final class TrieMap extends AbstractMap implements Concurrent TrieMap.this.clear (); } } - } diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java index 4f3cda74fb..98e7e27fef 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java @@ -22,6 +22,35 @@ import static org.junit.Assert.assertTrue; import org.junit.Test; public class TestDelete { + @Test(expected = NullPointerException.class) + public void testNullSimple() { + new TrieMap<>().remove(null); + } + + @Test(expected = NullPointerException.class) + public void testNullKey() { + new TrieMap<>().remove(null, ""); + } + + @Test(expected = NullPointerException.class) + public void testNullValue() { + new TrieMap<>().remove("", null); + } + + @Test(expected = NullPointerException.class) + public void testNullBoth() { + new TrieMap<>().remove(null, null); + } + + @Test + public void testClear() { + final TrieMap bt = new TrieMap<>(); + bt.put(1, 1); + bt.clear(); + assertTrue(bt.isEmpty()); + assertEquals(0, bt.size()); + } + @Test public void testDelete () { final TrieMap bt = new TrieMap<> (); diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java index 81f66e869d..bf3813b7f7 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java @@ -38,4 +38,19 @@ public class TestInsert { bt.toString(); } + + @Test(expected = NullPointerException.class) + public void testNullKey() { + new TrieMap<>().put(null, ""); + } + + @Test(expected = NullPointerException.class) + public void testNullValue() { + new TrieMap<>().put("", null); + } + + @Test(expected = NullPointerException.class) + public void testNullBoth() { + new TrieMap<>().put(null, null); + } } diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java index f697b1d1cc..7d8e549014 100644 --- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java +++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java @@ -25,6 +25,7 @@ import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; +import java.util.NoSuchElementException; import java.util.Random; import java.util.Set; import org.junit.Test; @@ -75,4 +76,24 @@ public class TestMapIterator { assertTrue(bt.isEmpty ()); } } + + private static void failAdvance(final Iterator it) { + assertFalse(it.hasNext()); + it.next(); + } + + @Test(expected = NoSuchElementException.class) + public void testEmptyIterator() { + failAdvance(new TrieMap<>().iterator()); + } + + @Test(expected = NoSuchElementException.class) + public void testEmptyReadOnlyIterator() { + failAdvance(new TrieMap<>().readOnlyIterator()); + } + + @Test(expected = NoSuchElementException.class) + public void testEmptyReadOnlySnapshotIterator() { + failAdvance(new TrieMap<>().readOnlySnapshot().iterator()); + } } -- 2.36.6