LNode<K, V> ln = (LNode<K, V>) m;
MainNode<K, V> nn = ln.inserted(k, v);
return GCAS(ln, nn, ct);
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
throw new RuntimeException ("Should not happen");
return Option.makeOption();// None;
} else {
- if (sn.hc == hc && ct.equal(sn.k, k) && sn.v == cond) {
+ if (sn.hc == hc && ct.equal(sn.k, k) && cond.equals(sn.v)) {
if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
return Option.makeOption(sn.v);
}
return null;
} else if (cond == INode.KEY_PRESENT) {
return Option.makeOption(); // None;
- }
- else {
+ } else {
return Option.makeOption(); // None
}
} else if (m instanceof TNode) {
return null;
} else if (cond == INode.KEY_ABSENT) {
final Option<V> t = ln.get(k);
- if (t != null) {
+ if (t.nonEmpty()) {
return t;
}
if (insertln(ln, k, v, ct)) {
return null;
} else if (cond == INode.KEY_PRESENT) {
final Option<V> t = ln.get(k);
- if (t == null) {
- return null; // None
+ if (!t.nonEmpty()) {
+ return t;
}
if (insertln(ln, k, v, ct)) {
return t;
return null;
} else {
final Option<V> t = ln.get(k);
- if (t != null) {
- if (((Some<V>) t).get() == cond) {
+ if (t instanceof Some) {
+ final Some<V> s = (Some<V>) t;
+ if (cond.equals(s.get())) {
if (insertln(ln, k, v, ct)) {
- return new Some<>((V) cond);
+ // Difference from Scala: we choose to reuse the object returned from LNode,
+ // as the identity of the value does not matter in this call graph.
+ return t;
}
return null;
}
- return Option.makeOption();
}
+
+ return Option.makeOption();
}
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
- // throw new RuntimeException ("Should not happen");
+ throw new RuntimeException("Should never happen");
}
}
} else if (m instanceof LNode) {
// 5) an l-node
return ((LNode<K, V>) m).get(k);
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
throw new RuntimeException ("Should not happen");
final Option<V> tmp = ln.get(k);
if (tmp instanceof Some) {
final Some<V> tmp1 = (Some<V>) tmp;
- if (tmp1.get() == v) {
+ if (v.equals(tmp1.get())) {
final MainNode<K, V> nn = ln.removed(k, ct);
if (GCAS(ln, nn, ct)) {
return tmp;
return null;
}
}
+
+ // Key not found or value does not match: we have not removed anything
+ return Option.makeOption();
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
- throw new RuntimeException ("Should not happen");
}
private void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
*/
package org.opendaylight.yangtools.triemap;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertSame;
+
+import java.util.Map;
import java.util.concurrent.ConcurrentMap;
import org.junit.Test;
TestHelper.assertTrue (Integer.valueOf (i).equals (map.putIfAbsent (i, i)));
}
}
+
+ @Test
+ public void testConflictingHash() {
+ final ZeroHashInt k1 = new ZeroHashInt(1);
+ final ZeroHashInt k2 = new ZeroHashInt(2);
+ final ZeroHashInt k3 = new ZeroHashInt(3);
+ final ZeroHashInt k3dup = new ZeroHashInt(3);
+ final ZeroHashInt v1 = new ZeroHashInt(4);
+ final ZeroHashInt v2 = new ZeroHashInt(5);
+ final ZeroHashInt v3 = new ZeroHashInt(6);
+
+ final Map<ZeroHashInt, ZeroHashInt> map = new TrieMap<>();
+ // Pre-populate an LNode
+ assertNull(map.putIfAbsent(k1, v1));
+ assertNull(map.putIfAbsent(k2, v2));
+ assertNull(map.putIfAbsent(k3, v3));
+
+ // Check with identical key
+ assertSame(v3, map.putIfAbsent(k3, v3));
+ // Check with equivalent key
+ assertSame(v3, map.putIfAbsent(k3dup, v3));
+ }
}
*/
package org.opendaylight.yangtools.triemap;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Map;
import java.util.concurrent.ConcurrentMap;
import org.junit.Test;
@Test
public void testConcurrentMapRemove () {
- final ConcurrentMap<Object, Object> map = new TrieMap<> ();
+ final ConcurrentMap<Integer, Object> map = new TrieMap<>();
for (int i = 128; i < COUNT; i++) {
- TestHelper.assertFalse (map.remove (i, i));
- TestHelper.assertTrue (null == map.put (i, i));
- TestHelper.assertFalse (map.remove (i, "lol"));
- TestHelper.assertTrue (map.containsKey (i));
- TestHelper.assertTrue (map.remove (i, i));
- TestHelper.assertFalse (map.containsKey (i));
- TestHelper.assertTrue (null == map.put (i, i));
+ assertFalse(map.remove(i, i));
+ assertNull(map.put(i, i));
+ assertFalse(map.remove(i, "lol"));
+ assertTrue(map.containsKey(i));
+ assertTrue(map.remove(i, i));
+ assertFalse(map.containsKey(i));
+ assertNull(map.put(i, i));
}
}
+
+ @Test
+ public void testConflictingHash() {
+ final ZeroHashInt k1 = new ZeroHashInt(1);
+ final ZeroHashInt k2 = new ZeroHashInt(2);
+ final ZeroHashInt k3 = new ZeroHashInt(3);
+ final ZeroHashInt k3dup = new ZeroHashInt(3);
+ final ZeroHashInt v1 = new ZeroHashInt(4);
+ final ZeroHashInt v2 = new ZeroHashInt(5);
+ final ZeroHashInt v3 = new ZeroHashInt(6);
+ final ZeroHashInt v3dup = new ZeroHashInt(6);
+
+ final Map<ZeroHashInt, ZeroHashInt> map = new TrieMap<>();
+ // Pre-populate an LNode
+ assertNull(map.putIfAbsent(k1, v1));
+ assertNull(map.putIfAbsent(k2, v2));
+ assertNull(map.putIfAbsent(k3, v3));
+
+ assertFalse(map.remove(k3, v2));
+ assertTrue(map.remove(k3dup, v3dup));
+ }
}
*/
package org.opendaylight.yangtools.triemap;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Map;
import java.util.concurrent.ConcurrentMap;
import org.junit.Test;
@Test
public void testConcurrentMapReplace () {
- final ConcurrentMap<Object, Object> map = new TrieMap<> ();
+ final ConcurrentMap<Integer, Object> map = new TrieMap<>();
for (int i = 0; i < COUNT; i++) {
- TestHelper.assertTrue (null == map.replace (i, "lol"));
- TestHelper.assertFalse (map.replace (i, i, "lol2"));
- TestHelper.assertTrue (null == map.put (i, i));
- TestHelper.assertTrue (Integer.valueOf (i).equals (map.replace (i, "lol")));
- TestHelper.assertFalse (map.replace (i, i, "lol2"));
- TestHelper.assertTrue (map.replace (i, "lol", i));
+ assertNull(map.replace(i, "lol"));
+ assertFalse(map.replace(i, i, "lol2"));
+ assertNull(map.put(i, i));
+ assertEquals(Integer.valueOf(i), map.replace(i, "lol"));
+ assertFalse(map.replace(i, i, "lol2"));
+ assertTrue(map.replace(i, "lol", i));
}
}
+
+ @Test
+ public void testConflictingHash() {
+ final ZeroHashInt k1 = new ZeroHashInt(1);
+ final ZeroHashInt k2 = new ZeroHashInt(2);
+ final ZeroHashInt k3 = new ZeroHashInt(3);
+ final ZeroHashInt k3dup = new ZeroHashInt(3);
+ final ZeroHashInt v1 = new ZeroHashInt(4);
+ final ZeroHashInt v2 = new ZeroHashInt(5);
+ final ZeroHashInt v3 = new ZeroHashInt(6);
+ final ZeroHashInt v3dup = new ZeroHashInt(6);
+ final ZeroHashInt k4 = new ZeroHashInt(7);
+
+ final Map<ZeroHashInt, ZeroHashInt> map = new TrieMap<>();
+ assertNull(map.put(k3, v3));
+
+ // First check for SNode
+ assertNull(map.replace(k1, v1));
+ assertFalse(map.replace(k1, v1, v2));
+ assertFalse(map.replace(k3, v1, v3));
+ assertFalse(map.replace(k3dup, v1, v3dup));
+ assertTrue(map.replace(k3dup, v3dup, v1));
+ assertTrue(map.replace(k3dup, v1, v3));
+
+ // Bump up to LNode
+ assertNull(map.put(k1, v1));
+ assertNull(map.put(k2, v2));
+
+ // Completely mismatched
+ assertFalse(map.replace(k1, v2, v3));
+
+ // Identical value match
+ assertTrue(map.replace(k2, v2, v3));
+ // Equivalent value match
+ assertTrue(map.replace(k2, v3dup, v2));
+
+ // Equivalent match
+ assertTrue(map.replace(k3dup, v3dup, v2));
+
+ // No match
+ assertNull(map.replace(k4, v1));
+ assertFalse(map.replace(k4, v1, v2));
+ }
}
*/
package org.opendaylight.yangtools.triemap;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
import org.junit.Test;
public class TestDelete {
@Test
public void testDelete () {
- final TrieMap<Object, Object> bt = new TrieMap<> ();
+ final TrieMap<Integer, Integer> bt = new TrieMap<> ();
for (int i = 0; i < 10000; i++) {
- TestHelper.assertEquals (null, bt.put (Integer.valueOf (i), Integer.valueOf (i)));
- final Object lookup = bt.lookup (Integer.valueOf (i));
- TestHelper.assertEquals (Integer.valueOf (i), lookup);
+ assertNull(bt.put(Integer.valueOf(i), Integer.valueOf(i)));
+ assertEquals(Integer.valueOf(i), bt.lookup(Integer.valueOf(i)));
}
- checkAddInsert (bt, 536);
- checkAddInsert (bt, 4341);
- checkAddInsert (bt, 8437);
+ checkAddInsert(bt, 536);
+ checkAddInsert(bt, 4341);
+ checkAddInsert(bt, 8437);
for (int i = 0; i < 10000; i++) {
- boolean removed = null != bt.remove(Integer.valueOf (i));
- TestHelper.assertEquals (Boolean.TRUE, Boolean.valueOf (removed));
- final Object lookup = bt.lookup (Integer.valueOf (i));
- TestHelper.assertEquals (null, lookup);
+ boolean removed = null != bt.remove(Integer.valueOf(i));
+ assertTrue(removed);
+ final Object lookup = bt.lookup (Integer.valueOf(i));
+ assertNull(lookup);
}
bt.toString ();
}
- private static void checkAddInsert (final TrieMap<Object, Object> bt, final int k) {
- final Integer v = Integer.valueOf (k);
+ /**
+ * Test if the Map.remove(Object, Object) method works correctly for hash collisions, which are handled by LNode.
+ */
+ @Test
+ public void testRemoveObjectLNode() {
+ final TrieMap<ZeroHashInt, ZeroHashInt> bt = new TrieMap<> ();
+
+ for (int i = 0; i < 100; i++) {
+ final ZeroHashInt v = new ZeroHashInt(i);
+ assertNull(bt.put(v, v));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ final ZeroHashInt v = new ZeroHashInt(i);
+ assertTrue(bt.remove(v, v));
+ }
+ }
+
+ private static void checkAddInsert (final TrieMap<Integer, Integer> bt, final int k) {
+ final Integer v = Integer.valueOf(k);
bt.remove (v);
- Object foundV = bt.lookup (v);
- TestHelper.assertEquals (null, foundV);
- TestHelper.assertEquals (null, bt.put (v, v));
- foundV = bt.lookup (v);
- TestHelper.assertEquals (v, foundV);
-
- TestHelper.assertEquals (v, bt.put (v, Integer.valueOf (-1)));
- TestHelper.assertEquals (Integer.valueOf (-1), bt.put (v, v));
+ Object foundV = bt.lookup(v);
+ assertNull(foundV);
+ assertNull(bt.put (v, v));
+ foundV = bt.lookup(v);
+ assertEquals(v, foundV);
+
+ assertEquals(v, bt.put(v, Integer.valueOf(-1)));
+ assertEquals(Integer.valueOf(-1), bt.put(v, v));
}
}
--- /dev/null
+/*
+ * (C) Copyright 2016 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 com.google.common.base.MoreObjects;
+
+/**
+ * Utility key/value class which attacks the hasing function, causing all objects to be put into a single bucket.
+ *
+ * @author Robert Varga
+ */
+final class ZeroHashInt {
+ private final int i;
+
+ ZeroHashInt(final int i) {
+ this.i = i;
+ }
+
+ @Override
+ public int hashCode() {
+ return 0;
+ }
+
+ @Override
+ public boolean equals(final Object o) {
+ return o instanceof ZeroHashInt && i == ((ZeroHashInt) o).i;
+ }
+
+ @Override
+ public String toString() {
+ return MoreObjects.toStringHelper(this).add("i", i).add("identity", System.identityHashCode(this)).toString();
+ }
+}
Code Review / yangtools.git / commitdiff