private boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
final Gen startgen, final TrieMap<K, V> ct) {
while (true) {
- final MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
+ final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
if (m instanceof CNode) {
// 1) a multiway node
clean(parent, ct, lev - 5);
return false;
} else if (m instanceof LNode) {
- return insertln((LNode<K, V>) m, k, v, ct);
+ final LNode<K, V> ln = (LNode<K, V>) m;
+ final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
+ return entry != null ? replaceln(ln, entry, v, ct) : insertln(ln, k, v, ct);
} else {
throw new IllegalStateException("Unhandled node " + m);
}
} else if (m instanceof LNode) {
// 3) an l-node
final LNode<K, V> ln = (LNode<K, V>) m;
+ final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
+
if (cond == null) {
- final Optional<V> optv = ln.get(ct.equiv(), k);
- if (insertln(ln, k, v, ct)) {
- return optv;
+ if (entry != null) {
+ return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
}
- return null;
+
+ return insertln(ln, k, v, ct) ? Optional.empty() : null;
} else if (cond == ABSENT) {
- final Optional<V> t = ln.get(ct.equiv(),k);
- if (t.isPresent()) {
- return t;
+ if (entry != null) {
+ return Optional.of(entry.value());
}
- if (insertln(ln, k, v, ct)) {
- return Optional.empty();
- }
- return null;
+
+ return insertln(ln, k, v, ct) ? Optional.empty() : null;
} else if (cond == PRESENT) {
- final Optional<V> t = ln.get(ct.equiv(),k);
- if (!t.isPresent()) {
- return t;
- }
- if (insertln(ln, k, v, ct)) {
- return t;
+ if (entry == null) {
+ return Optional.empty();
}
- return null;
- } else {
- final Optional<V> t = ln.get(ct.equiv(),k);
- if (t.isPresent()) {
- if (cond.equals(t.get())) {
- if (insertln(ln, k, v, ct)) {
- // 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 replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
+ } else {
+ if (entry == null || !cond.equals(entry.value())) {
+ return Optional.empty();
}
- return Optional.empty();
+ return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
}
} else {
throw new IllegalStateException("Unhandled node " + m);
}
private boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
- return GCAS(ln, ln.addChild(ct.equiv(), k, v), ct);
+ return GCAS(ln, ln.insertChild(k, v), ct);
+ }
+
+ private boolean replaceln(final LNode<K, V> ln, final LNodeEntry<K, V> entry, final V v, final TrieMap<K, V> ct) {
+ return GCAS(ln, ln.replaceChild(entry, v), ct);
}
/**
return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
} else if (m instanceof LNode) {
// 5) an l-node
- return ((LNode<K, V>) m).get(ct.equiv(), k).orElse(null);
+ final LNodeEntry<K, V> entry = ((LNode<K, V>) m).get(ct.equiv(), k);
+ return entry != null ? entry.value() : null;
} else {
throw new IllegalStateException("Unhandled node " + m);
}
return null;
} else if (m instanceof LNode) {
final LNode<K, V> ln = (LNode<K, V>) m;
- final Optional<V> optv = ln.get(ct.equiv(), k);
-
- if (!optv.isPresent()) {
+ final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
+ if (entry == null) {
// Key was not found, hence no modification is needed
return Optional.empty();
}
- if (v != null && !v.equals(optv.get())) {
+ final V value = entry.value();
+ if (v != null && !v.equals(value)) {
// Value does not match
return Optional.empty();
}
- return GCAS(ln, ln.removeChild(ct.equiv(), k, hc), ct) ? optv : null;
+ return GCAS(ln, ln.removeChild(entry, hc), ct) ? Optional.of(value) : null;
} else {
throw new IllegalStateException("Unhandled node " + m);
}
import java.util.Optional;
final class LNode<K, V> extends MainNode<K, V> {
- private final ListMap<K, V> listmap;
+ private final LNodeEntries<K, V> listmap;
- private LNode(final ListMap<K, V> listmap) {
+ private LNode(final LNodeEntries<K, V> listmap) {
this.listmap = listmap;
}
LNode(final K k1, final V v1, final K k2, final V v2) {
- this(ListMap.map(k1, v1, k2, v2));
+ this(LNodeEntries.map(k1, v1, k2, v2));
}
- LNode<K, V> addChild(final Equivalence<? super K> equiv, final K k, final V v) {
- return new LNode<>(listmap.add(equiv, k, v));
+ LNode<K, V> insertChild( final K k, final V v) {
+ return new LNode<>(listmap.insert(k, v));
}
- MainNode<K, V> removeChild(final Equivalence<? super K> equiv, final K k, final int hc) {
+ MainNode<K, V> removeChild(final LNodeEntry<K, V> entry, final int hc) {
// We only ever create ListMaps with two or more entries, and remove them as soon as they reach one element
// (below), so we cannot observe a null return here.
- final ListMap<K, V> map = listmap.remove(equiv, k);
+ final LNodeEntries<K, V> map = listmap.remove(entry);
final Optional<Entry<K, V>> maybeKv = map.maybeSingleton();
if (maybeKv.isPresent()) {
final Entry<K, V> kv = maybeKv.get();
return new LNode<>(map);
}
- Optional<V> get(final Equivalence<? super K> equiv, final K k) {
- return listmap.get(equiv, k);
+ MainNode<K, V> replaceChild(final LNodeEntry<K, V> entry, final V v) {
+ return new LNode<>(listmap.replace(entry, v));
+ }
+
+ LNodeEntry<K, V> get(final Equivalence<? super K> equiv, final K k) {
+ return listmap.findEntry(equiv, k);
}
@Override
Iterator<Entry<K, V>> iterator() {
return listmap.iterator();
}
+
+
}
\ No newline at end of file
--- /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 java.util.AbstractMap.SimpleImmutableEntry;
+import java.util.Iterator;
+import java.util.Map.Entry;
+import java.util.NoSuchElementException;
+import java.util.Optional;
+
+/**
+ * Similar to Scala's ListMap. Stores a linked set of entries, guaranteed to contain unique entry keys.
+ *
+ * @author Robert Varga
+ *
+ * @param <K> the type of keys
+ * @param <V> the type of values
+ */
+final class LNodeEntries<K, V> extends LNodeEntry<K, V> {
+ // Modified during remove0 only
+ private LNodeEntries<K, V> next;
+
+ private LNodeEntries(final K k, final V v) {
+ this(k, v, null);
+ }
+
+ private LNodeEntries(final K k, final V v, final LNodeEntries<K, V> next) {
+ super(k, v);
+ this.next = next;
+ }
+
+ static <K,V> LNodeEntries<K, V> map(final K k1, final V v1, final K k2, final V v2) {
+ return new LNodeEntries<>(k1, v1, new LNodeEntries<>(k2, v2));
+ }
+
+ Optional<Entry<K, V>> maybeSingleton() {
+ return next != null ? Optional.empty() : Optional.of(new SimpleImmutableEntry<>(key(), value()));
+ }
+
+ int size() {
+ int sz = 1;
+ for (LNodeEntries<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
+ sz++;
+ }
+ return sz;
+ }
+
+ LNodeEntry<K, V> findEntry(final Equivalence<? super K> equiv, final K key) {
+ // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
+ LNodeEntries<K, V> head = this;
+ do {
+ if (equiv.equivalent(head.key(), key)) {
+ return head;
+ }
+
+ head = head.next;
+ } while (head != null);
+
+ return null;
+ }
+
+ LNodeEntries<K,V> insert(final K key, final V value) {
+ return new LNodeEntries<>(key, value, this);
+ }
+
+ LNodeEntries<K, V> replace(final LNodeEntry<K, V> entry, final V v) {
+ return new LNodeEntries<>(entry.key(), v, remove(entry));
+ }
+
+ LNodeEntries<K, V> remove(final LNodeEntry<K, V> entry) {
+ if (entry == this) {
+ return next;
+ }
+
+ final LNodeEntries<K, V> ret = new LNodeEntries<>(key(), value());
+
+ LNodeEntries<K, V> last = ret;
+ LNodeEntries<K, V> cur = next;
+ while (cur != null) {
+ if (entry.equals(cur)) {
+ last.next = cur.next;
+ return ret;
+ }
+
+ last.next = new LNodeEntries<>(cur.key(), cur.value());
+ last = last.next;
+ cur = cur.next;
+ }
+
+ throw new IllegalStateException("Entry " + entry + " not found in entries " + this);
+ }
+
+ Iterator<Entry<K, V>> iterator() {
+ return new NodeIterator<>(this);
+ }
+
+ static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
+ private LNodeEntries<K, V> n;
+
+ NodeIterator(final LNodeEntries<K, V> n) {
+ this.n = n;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return n != null;
+ }
+
+ @Override
+ public Entry<K, V> next() {
+ if (n == null) {
+ throw new NoSuchElementException();
+ }
+
+ final Entry<K, V> res = new SimpleImmutableEntry<>(n.key(), n.value());
+ n = n.next;
+ return res;
+ }
+ }
+}
--- /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;
+
+/**
+ * A single entry in {@link LNodeEntries}.
+ *
+ * @author Robert Varga
+ *
+ * @param <K> the type of key
+ * @param <V> the type of value
+ */
+abstract class LNodeEntry<K, V> {
+ private final V value;
+ private final K key;
+
+ LNodeEntry(final K key, final V value) {
+ this.value = value;
+ this.key = key;
+ }
+
+ final K key() {
+ return key;
+ }
+
+ final V value() {
+ return value;
+ }
+
+}
+++ /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 java.util.AbstractMap.SimpleImmutableEntry;
-import java.util.Iterator;
-import java.util.Map.Entry;
-import java.util.NoSuchElementException;
-import java.util.Optional;
-
-/**
- * Mimic immutable ListMap in Scala
- *
- * @author Roman Levenstein <romixlev@gmail.com>
- *
- * @param <V>
- */
-final class ListMap<K, V> {
- private final K k;
- private final V v;
-
- // Modified during remove0 only
- private ListMap<K, V> next;
-
- private ListMap(final K k, final V v) {
- this(k, v, null);
- }
-
- private ListMap(final K k, final V v, final ListMap<K, V> next) {
- this.k = k;
- this.v = v;
- this.next = next;
- }
-
- static <K,V> ListMap<K, V> map(final K k1, final V v1, final K k2, final V v2) {
- return new ListMap<>(k1, v1, new ListMap<>(k2, v2));
- }
-
- Optional<Entry<K, V>> maybeSingleton() {
- return next != null ? Optional.empty() : Optional.of(new SimpleImmutableEntry<>(k, v));
- }
-
- int size() {
- int sz = 1;
- for (ListMap<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
- sz++;
- }
- return sz;
- }
-
- Optional<V> get(final Equivalence<? super K> equiv, final K key) {
- // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
- ListMap<K, V> head = this;
- do {
- if (equiv.equivalent(head.k, key)) {
- return Optional.of(head.v);
- }
-
- head = head.next;
- } while (head != null);
-
- return Optional.empty();
- }
-
- ListMap<K,V> add(final Equivalence<? super K> equiv, final K key, final V value) {
- return new ListMap<>(key, value, remove(equiv, key));
- }
-
- ListMap<K, V> remove(final Equivalence<? super K> equiv, final K key) {
- if (!contains(equiv, key)) {
- return this;
- }
-
- return remove0(key);
- }
-
- private boolean contains(final Equivalence<? super K> equiv, final K key) {
- // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
- ListMap<K, V> head = this;
- do {
- if (equiv.equivalent(head.k, key)) {
- return true;
- }
- head = head.next;
- } while (head != null);
-
- return false;
- }
-
- private ListMap<K, V> remove0(final K key) {
- ListMap<K, V> n = this;
- ListMap<K, V> ret = null;
- ListMap<K, V> lastN = null;
- while (n != null) {
- if (key.equals(n.k)) {
- n = n.next;
- continue;
- }
-
- if (ret != null) {
- lastN.next = new ListMap<>(n.k, n.v);
- lastN = lastN.next;
- } else {
- ret = new ListMap<>(n.k, n.v);
- lastN = ret;
- }
- n = n.next;
- }
- return ret;
- }
-
- Iterator<Entry<K, V>> iterator() {
- return new NodeIterator<>(this);
- }
-
- static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
- private ListMap<K, V> n;
-
- NodeIterator(final ListMap<K, V> n) {
- this.n = n;
- }
-
- @Override
- public boolean hasNext() {
- return n != null;
- }
-
- @Override
- public Entry<K, V> next() {
- if (n == null) {
- throw new NoSuchElementException();
- }
-
- final Entry<K, V> res = new SimpleImmutableEntry<>(n.k, n.v);
- n = n.next;
- return res;
- }
- }
-}
*
* @author Roman Levenstein <romixlev@gmail.com>
*
- * @param <K>
- * @param <V>
+ * @param <K> the type of keys maintained by this map
+ * @param <V> the type of mapped values
*/
@SuppressWarnings({"unchecked", "rawtypes", "unused"})
public final class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
*/
package org.opendaylight.yangtools.triemap;
-import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
-import java.util.Optional;
import org.junit.Test;
public class ListMapTest {
-
/**
* Test if Listmap.get() does not cause stack overflow.
*/
@Test
public void testGetOverflow() {
- ListMap<Integer, Boolean> map = ListMap.map(1, Boolean.TRUE, 2, Boolean.TRUE);
+ LNodeEntries<Integer, Boolean> map = LNodeEntries.map(1, Boolean.TRUE, 2, Boolean.TRUE);
// 30K seems to be enough to trigger the problem locally
for (int i = 3; i < 30000; ++i) {
- map = map.add(Equivalence.equals(), i, Boolean.TRUE);
+ map = map.insert(i, Boolean.TRUE);
}
- final Optional<Boolean> ret = map.get(Equivalence.equals(), 0);
- assertFalse(ret.isPresent());
+ assertNull(map.findEntry(Equivalence.equals(), 0));
}
-
}
Code Review / yangtools.git / commitdiff