<description>Java implementation of a concurrent trie hash map from Scala collections library</description>
<dependencies>
+ <dependency>
+ <groupId>com.google.guava</groupId>
+ <artifactId>guava</artifactId>
+ </dependency>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
+++ /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.io.Serializable;
-
-class Equiv<K> implements Serializable {
- private static final long serialVersionUID = 1L;
-
- static final Equiv universal = new Equiv();
-
- public boolean equiv(final K k1, final K k2) {
- return k1.equals(k2);
- }
-
-}
\ 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.io.Serializable;
+import javax.annotation.Nonnull;
+
+/**
+ * Internal equivalence class, similar to {@link com.google.common.base.Equivalence}, but explicitly not handling
+ * nulls. We use equivalence only for keys, which are guaranteed to be non-null.
+ *
+ * @author Robert Varga
+ */
+abstract class Equivalence<T> implements Serializable {
+ private static final long serialVersionUID = 1L;
+
+ private static final class Equals extends Equivalence<Object> {
+ private static final long serialVersionUID = 1L;
+
+ static final Equals INSTANCE = new Equals();
+
+ @Override
+ boolean equivalent(final Object a, final Object b) {
+ return a.equals(b);
+ }
+
+ @Override
+ Object readResolve() {
+ return INSTANCE;
+ }
+ }
+
+ private static final class Identity extends Equivalence<Object> {
+ private static final long serialVersionUID = 1L;
+
+ static final Identity INSTANCE = new Identity();
+
+ @Override
+ boolean equivalent(final Object a, final Object b) {
+ return a == b;
+ }
+
+ @Override
+ Object readResolve() {
+ return INSTANCE;
+ }
+ }
+
+ static Equivalence<Object> equals() {
+ return Equals.INSTANCE;
+ }
+
+ static Equivalence<Object> identity() {
+ return Identity.INSTANCE;
+ }
+
+ final int hash(@Nonnull final T t) {
+ int h = t.hashCode();
+
+ // This function ensures that hashCodes that differ only by
+ // constant multiples at each bit position have a bounded
+ // number of collisions (approximately 8 at default load factor).
+ h ^= (h >>> 20) ^ (h >>> 12);
+ h ^= (h >>> 7) ^ (h >>> 4);
+ return h;
+ }
+
+ abstract boolean equivalent(@Nonnull T a, @Nonnull T b);
+
+ abstract Object readResolve();
+}
+++ /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.io.Serializable;
-
-interface Hashing<K> extends Serializable {
-
- static class Default<K> implements Hashing<K> {
- private static final long serialVersionUID = 1L;
-
- @Override
- public int hash(final K k) {
- int h = k.hashCode();
-
- // This function ensures that hashCodes that differ only by
- // constant multiples at each bit position have a bounded
- // number of collisions (approximately 8 at default load factor).
- h ^= (h >>> 20) ^ (h >>> 12);
- h ^= (h >>> 7) ^ (h >>> 4);
- return h;
- }
- }
-
- int hash(K k);
-}
\ No newline at end of file
return false;
}
- private static <K, V> boolean equal(final K k1, final K k2, final TrieMap<K, V> ct) {
- return ct.equality().equiv(k1, k2);
- }
-
private INode<K, V> inode(final MainNode<K, V> cn) {
return new INode<>(gen, cn);
}
return false;
} else if (cnAtPos instanceof SNode) {
final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
- if (sn.hc == hc && equal(sn.k, k, ct)) {
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
}
} else if (cnAtPos instanceof SNode) {
final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
if (cond == null) {
- if (sn.hc == hc && equal(sn.k, k, ct)) {
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
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_ABSENT) {
- if (sn.hc == hc && equal(sn.k, k, ct)) {
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
return Option.makeOption(sn.v);
}
return null;
} else if (cond == INode.KEY_PRESENT) {
- if (sn.hc == hc && equal(sn.k, k, ct)) {
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
return Option.makeOption(sn.v);
}
return Option.makeOption();// None;
} else {
- if (sn.hc == hc && equal(sn.k, k, ct) && sn.v == cond) {
+ if (sn.hc == hc && ct.equal(sn.k, k) && sn.v == cond) {
if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
return Option.makeOption(sn.v);
}
} else if (sub instanceof SNode) {
// 2) singleton node
final SNode<K, V> sn = (SNode<K, V>) sub;
- if (sn.hc == hc && equal(sn.k, k, ct)) {
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
return sn.v;
}
return RESTART;
}
- if (tn.hc == hc && equal(tn.k, k, ct)) {
+ if (tn.hc == hc && ct.equal(tn.k, k)) {
return tn.v;
}
} else if (sub instanceof SNode) {
final SNode<K, V> sn = (SNode<K, V>) sub;
- if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || v.equals(sn.v))) {
+ if (sn.hc == hc && ct.equal(sn.k, k) && (v == null || v.equals(sn.v))) {
final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
if (GCAS(cn, ncn, ct)) {
res = Option.makeOption(sn.v);
}
}
- private final Hashing<K> hashingobj;
- private final Equiv<K> equalityobj;
-
- Hashing<K> hashing () {
- return hashingobj;
- }
-
- Equiv<K> equality () {
- return equalityobj;
- }
+ private final Equivalence<? super K> equiv;
private transient volatile Object root;
private final transient boolean readOnly;
- TrieMap (final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
- this.hashingobj = hashf;
- this.equalityobj = ef;
- this.readOnly = readOnly;
- }
-
- TrieMap (final Object r, final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
- this(hashf, ef, readOnly);
+ TrieMap (final Object r, final Equivalence<? super K> equiv, final boolean readOnly) {
this.root = r;
- }
+ this.equiv = equiv;
+ this.readOnly = readOnly;
- public TrieMap (final Hashing<K> hashf, final Equiv<K> ef) {
- this(newRootNode(), hashf, ef, false);
}
- public TrieMap () {
- this (new Hashing.Default<K>(), Equiv.universal);
+ public TrieMap() {
+ this(newRootNode(), Equivalence.equals(), false);
}
/* internal methods */
INode<K, V> r = RDCSS_READ_ROOT ();
final MainNode<K, V> expmain = r.gcasRead (this);
if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
- return new TrieMap<> (r.copyToGen (new Gen (), this), hashing (), equality (), readOnly);
+ return new TrieMap<> (r.copyToGen (new Gen (), this), equiv, readOnly);
} else {
// return snapshot ();
// tailrec
INode<K, V> r = RDCSS_READ_ROOT ();
MainNode<K, V> expmain = r.gcasRead (this);
if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
- return new TrieMap<> (r, hashing (), equality (), true);
+ return new TrieMap<> (r, equiv, true);
} else {
// return readOnlySnapshot ();
continue;
}
}
- // @inline
- int computeHash (final K k) {
- return hashingobj.hash (k);
+ int computeHash(final K k) {
+ return equiv.hash(k);
+ }
+
+ boolean equal(final K k1, final K k2) {
+ return equiv.equivalent(k1, k2);
}
final V lookup (final K k) {
Code Review / yangtools.git / commitdiff