--- /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;
+
+final class CNode<K, V> extends CNodeBase<K, V> {
+
+ final int bitmap;
+ final BasicNode[] array;
+ final Gen gen;
+
+ CNode(final int bitmap, final BasicNode[] array, final Gen gen) {
+ this.bitmap = bitmap;
+ this.array = array;
+ this.gen = gen;
+ }
+
+ // this should only be called from within read-only snapshots
+ @Override
+ public int cachedSize(final Object ct) {
+ final int currsz = READ_SIZE();
+ if (currsz != -1) {
+ return currsz;
+ }
+
+ final int sz = computeSize((TrieMap<K, V>) ct);
+ while (READ_SIZE () == -1) {
+ CAS_SIZE (-1, sz);
+ }
+ return READ_SIZE ();
+ }
+
+ // lends itself towards being parallelizable by choosing
+ // a random starting offset in the array
+ // => if there are concurrent size computations, they start
+ // at different positions, so they are more likely to
+ // to be independent
+ private int computeSize(final TrieMap<K, V> ct) {
+ int i = 0;
+ int sz = 0;
+ // final int offset = (array.length > 0) ?
+ // // util.Random.nextInt(array.length) /* <-- benchmarks show that
+ // // this causes observable contention */
+ // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
+ // array.length)
+ // : 0;
+
+ final int offset = 0;
+ while (i < array.length) {
+ int pos = (i + offset) % array.length;
+ BasicNode elem = array [pos];
+ if (elem instanceof SNode) {
+ sz += 1;
+ } else if (elem instanceof INode) {
+ sz += ((INode<K, V>) elem).cachedSize (ct);
+ }
+ i += 1;
+ }
+ return sz;
+ }
+
+ CNode<K, V> updatedAt(final int pos, final BasicNode nn, final Gen gen) {
+ int len = array.length;
+ BasicNode[] narr = new BasicNode[len];
+ System.arraycopy(array, 0, narr, 0, len);
+ narr[pos] = nn;
+ return new CNode<>(bitmap, narr, gen);
+ }
+
+ CNode<K, V> removedAt(final int pos, final int flag, final Gen gen) {
+ BasicNode[] arr = array;
+ int len = arr.length;
+ BasicNode[] narr = new BasicNode[len - 1];
+ System.arraycopy(arr, 0, narr, 0, pos);
+ System.arraycopy(arr, pos + 1, narr, pos, len - pos - 1);
+ return new CNode<>(bitmap ^ flag, narr, gen);
+ }
+
+ CNode<K, V> insertedAt(final int pos, final int flag, final BasicNode nn, final Gen gen) {
+ int len = array.length;
+ int bmp = bitmap;
+ BasicNode[] narr = new BasicNode[len + 1];
+ System.arraycopy(array, 0, narr, 0, pos);
+ narr [pos] = nn;
+ System.arraycopy(array, pos, narr, pos + 1, len - pos);
+ return new CNode<>(bmp | flag, narr, gen);
+ }
+
+ /**
+ * Returns a copy of this cnode such that all the i-nodes below it are
+ * copied to the specified generation `ngen`.
+ */
+ CNode<K, V> renewed(final Gen ngen, final TrieMap<K, V> ct) {
+ int i = 0;
+ BasicNode[] arr = array;
+ int len = arr.length;
+ BasicNode[] narr = new BasicNode[len];
+ while (i < len) {
+ BasicNode elem = arr[i];
+ if (elem instanceof INode) {
+ INode<K, V> in = (INode<K, V>) elem;
+ narr [i] = in.copyToGen(ngen, ct);
+ } else if (elem instanceof BasicNode) {
+ narr [i] = elem;
+ }
+ i += 1;
+ }
+ return new CNode<>(bitmap, narr, ngen);
+ }
+
+ private BasicNode resurrect(final INode<K, V> inode, final Object inodemain) {
+ if (inodemain instanceof TNode) {
+ TNode<K, V> tn = (TNode<K, V>) inodemain;
+ return tn.copyUntombed();
+ }
+
+ return inode;
+ }
+
+ MainNode<K, V> toContracted(final int lev) {
+ if (array.length == 1 && lev > 0) {
+ if (array [0] instanceof SNode) {
+ SNode<K, V> sn = (SNode<K, V>) array[0];
+ return sn.copyTombed();
+ } else {
+ return this;
+ }
+ } else {
+ return this;
+ }
+ }
+
+ // - if the branching factor is 1 for this CNode, and the child
+ // is a tombed SNode, returns its tombed version
+ // - otherwise, if there is at least one non-null node below,
+ // returns the version of this node with at least some null-inodes
+ // removed (those existing when the op began)
+ // - if there are only null-i-nodes below, returns null
+ MainNode<K, V> toCompressed(final TrieMap<K, V> ct, final int lev, final Gen gen) {
+ int bmp = bitmap;
+ int i = 0;
+ BasicNode[] arr = array;
+ BasicNode[] tmparray = new BasicNode[arr.length];
+ while (i < arr.length) { // construct new bitmap
+ BasicNode sub = arr[i];
+ if (sub instanceof INode) {
+ INode<K, V> in = (INode<K, V>) sub;
+ MainNode<K, V> inodemain = in.gcasRead (ct);
+ assert (inodemain != null);
+ tmparray [i] = resurrect (in, inodemain);
+ } else if (sub instanceof SNode) {
+ tmparray [i] = sub;
+ }
+ i += 1;
+ }
+
+ return new CNode<K, V> (bmp, tmparray, gen).toContracted (lev);
+ }
+
+ @Override
+ String string(final int lev) {
+ // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
+ // 1)).mkString("\n"));
+ return "CNode";
+ }
+
+ /*
+ * quiescently consistent - don't call concurrently to anything
+ * involving a GCAS!!
+ */
+ // protected Seq<K,V> collectElems() {
+ // array flatMap {
+ // case sn: SNode[K, V] => Some(sn.kvPair)
+ // case in: INode[K, V] => in.mainnode match {
+ // case tn: TNode[K, V] => Some(tn.kvPair)
+ // case ln: LNode[K, V] => ln.listmap.toList
+ // case cn: CNode[K, V] => cn.collectElems
+ // }
+ // }
+ // }
+
+ // protected Seq<String> collectLocalElems() {
+ // // array flatMap {
+ // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
+ // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
+ // ")")
+ // // }
+ // return null;
+ // }
+
+ @Override
+ public String toString () {
+ // val elems = collectLocalElems
+ // "CNode(sz: %d; %s)".format(elems.size,
+ // elems.sorted.mkString(", "))
+ return "CNode";
+ }
+
+ static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
+ final int lev, final Gen gen) {
+ if (lev < 35) {
+ int xidx = (xhc >>> lev) & 0x1f;
+ int yidx = (yhc >>> lev) & 0x1f;
+ int bmp = (1 << xidx) | (1 << yidx);
+
+ if (xidx == yidx) {
+ INode<K, V> subinode = new INode<>(gen);// (TrieMap.inodeupdater)
+ subinode.mainnode = dual (x, xhc, y, yhc, lev + 5, gen);
+ return new CNode<>(bmp, new BasicNode[] { subinode }, gen);
+ } else {
+ if (xidx < yidx) {
+ return new CNode<>(bmp, new BasicNode[] { x, y }, gen);
+ } else {
+ return new CNode<>(bmp, new BasicNode[] { y, x }, gen);
+ }
+ }
+ } else {
+ return new LNode<>(x.k, x.v, y.k, y.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 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;
+
+final class FailedNode<K, V> extends MainNode<K, V> {
+ private final MainNode<K, V> p;
+
+ FailedNode (final MainNode<K, V> p) {
+ this.p = p;
+ WRITE_PREV (p);
+ }
+
+ @Override
+ String string(final int lev) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public int cachedSize(final Object ct) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public String toString() {
+ return "FailedNode(" + p + ")";
+ }
+}
\ 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;
+
+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
--- /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;
+
+final class INode<K, V> extends INodeBase<K, V> {
+ static final Object KEY_PRESENT = new Object ();
+ static final Object KEY_ABSENT = new Object ();
+
+ static <K,V> INode<K,V> newRootNode() {
+ Gen gen = new Gen ();
+ CNode<K, V> cn = new CNode<> (0, new BasicNode[] {}, gen);
+ return new INode<>(cn, gen);
+ }
+
+ private INode(final MainNode<K, V> bn, final Gen g) {
+ super(g);
+ WRITE(bn);
+ }
+
+ INode(final Gen g) {
+ this(null, g);
+ }
+
+ void WRITE(final MainNode<K, V> nval) {
+ INodeBase.updater.set(this, nval);
+ }
+
+ boolean CAS(final MainNode<K, V> old, final MainNode<K, V> n) {
+ return INodeBase.updater.compareAndSet(this, old, n);
+ }
+
+ MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
+ return GCAS_READ(ct);
+ }
+
+ MainNode<K, V> GCAS_READ(final TrieMap<K, V> ct) {
+ MainNode<K, V> m = /* READ */mainnode;
+ MainNode<K, V> prevval = /* READ */m.prev;
+ if (prevval == null) {
+ return m;
+ } else {
+ return GCAS_Complete(m, ct);
+ }
+ }
+
+ private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<K, V> ct) {
+ while (true) {
+ if (m == null) {
+ return null;
+ } else {
+ // complete the GCAS
+ MainNode<K, V> prev = /* READ */m.prev;
+ INode<K, V> ctr = ct.readRoot(true);
+
+ if (prev == null) {
+ return m;
+ }
+
+ if (prev instanceof FailedNode) {
+ // try to commit to previous value
+ FailedNode<K, V> fn = (FailedNode<K, V>) prev;
+ if (CAS(m, fn.prev)) {
+ return fn.prev;
+ } else {
+ // Tailrec
+ // return GCAS_Complete (/* READ */mainnode, ct);
+ m = /* READ */mainnode;
+ continue;
+ }
+ } else if (prev instanceof MainNode) {
+ // Assume that you've read the root from the generation
+ // G.
+ // Assume that the snapshot algorithm is correct.
+ // ==> you can only reach nodes in generations <= G.
+ // ==> `gen` is <= G.
+ // We know that `ctr.gen` is >= G.
+ // ==> if `ctr.gen` = `gen` then they are both equal to
+ // G.
+ // ==> otherwise, we know that either `ctr.gen` > G,
+ // `gen` <
+ // G,
+ // or both
+ if ((ctr.gen == gen) && ct.nonReadOnly()) {
+ // try to commit
+ if (m.CAS_PREV(prev, null)) {
+ return m;
+ } else {
+ // return GCAS_Complete (m, ct);
+ // tailrec
+ continue;
+ }
+ } else {
+ // try to abort
+ m.CAS_PREV(prev, new FailedNode<>(prev));
+ return GCAS_Complete(/* READ */mainnode, ct);
+ }
+ }
+ }
+ throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
+ n.WRITE_PREV (old);
+ if (CAS (old, n)) {
+ GCAS_Complete (n, ct);
+ return /* READ */n.prev == null;
+ } else {
+ return false;
+ }
+ }
+
+ private 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) {
+ INode<K, V> nin = new INode<>(gen);
+ nin.WRITE(cn);
+ return nin;
+ }
+
+ INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
+ INode<K, V> nin = new INode<>(ngen);
+ MainNode<K, V> main = GCAS_READ(ct);
+ nin.WRITE(main);
+ return nin;
+ }
+
+ /**
+ * Inserts a key value pair, overwriting the old pair if the keys match.
+ *
+ * @return true if successful, false otherwise
+ */
+ 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) {
+ MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
+
+ if (m instanceof CNode) {
+ // 1) a multiway node
+ CNode<K, V> cn = (CNode<K, V>) m;
+ int idx = (hc >>> lev) & 0x1f;
+ int flag = 1 << idx;
+ int bmp = cn.bitmap;
+ int mask = flag - 1;
+ int pos = Integer.bitCount(bmp & mask);
+ if ((bmp & flag) != 0) {
+ // 1a) insert below
+ BasicNode cnAtPos = cn.array[pos];
+ if (cnAtPos instanceof INode) {
+ INode<K, V> in = (INode<K, V>) cnAtPos;
+ if (startgen == in.gen) {
+ return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
+ } else {
+ if (GCAS (cn, cn.renewed(startgen, ct), ct)) {
+ // return rec_insert (k, v, hc, lev, parent,
+ // startgen, ct);
+ // tailrec
+ continue;
+ } else {
+ return false;
+ }
+ }
+ } else if (cnAtPos instanceof SNode) {
+ SNode<K, V> sn = (SNode<K, V>) cnAtPos;
+ if (sn.hc == hc && equal(sn.k, k, ct)) {
+ return GCAS (cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
+ } else {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+ MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
+ hc, lev + 5, gen)), gen);
+ return GCAS (cn, nn, ct);
+ }
+ }
+ } else {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
+ MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<> (k, v, hc), gen);
+ return GCAS (cn, ncnode, ct);
+ }
+ } else if (m instanceof TNode) {
+ clean(parent, ct, lev - 5);
+ return false;
+ } else if (m instanceof LNode) {
+ LNode<K, V> ln = (LNode<K, V>) m;
+ MainNode<K, V> nn = ln.inserted(k, v);
+ return GCAS(ln, nn, ct);
+ }
+
+ throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ /**
+ * Inserts a new key value pair, given that a specific condition is met.
+ *
+ * @param cond
+ * null - don't care if the key was there
+ * KEY_ABSENT - key wasn't there
+ * KEY_PRESENT - key was there
+ * other value `v` - key must be bound to `v`
+ * @return null if unsuccessful, Option[V] otherwise (indicating
+ * previous value bound to the key)
+ */
+ Option<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
+ final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
+ while (true) {
+ MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
+
+ if (m instanceof CNode) {
+ // 1) a multiway node
+ CNode<K, V> cn = (CNode<K, V>) m;
+ int idx = (hc >>> lev) & 0x1f;
+ int flag = 1 << idx;
+ int bmp = cn.bitmap;
+ int mask = flag - 1;
+ int pos = Integer.bitCount(bmp & mask);
+
+ if ((bmp & flag) != 0) {
+ // 1a) insert below
+ BasicNode cnAtPos = cn.array [pos];
+ if (cnAtPos instanceof INode) {
+ INode<K, V> in = (INode<K, V>) cnAtPos;
+ if (startgen == in.gen) {
+ return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
+ } else {
+ if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
+ // return rec_insertif (k, v, hc, cond, lev,
+ // parent, startgen, ct);
+ // tailrec
+ continue;
+ } else {
+ return null;
+ }
+ }
+ } else if (cnAtPos instanceof SNode) {
+ SNode<K, V> sn = (SNode<K, V>) cnAtPos;
+ if (cond == null) {
+ if (sn.hc == hc && equal(sn.k, k, ct)) {
+ if (GCAS(cn, cn.updatedAt(pos, new SNode<> (k, v, hc), gen), ct)) {
+ return Option.makeOption(sn.v);
+ } else {
+ return null;
+ }
+ } else {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+ MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
+ new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
+ if (GCAS(cn, nn, ct)) {
+ return Option.makeOption(); // None;
+ } else {
+ return null;
+ }
+ }
+
+ } else if (cond == INode.KEY_ABSENT) {
+ if (sn.hc == hc && equal (sn.k, k, ct)) {
+ return Option.makeOption(sn.v);
+ } else {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
+ MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
+ new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
+ if (GCAS(cn, nn, ct)) {
+ return Option.makeOption(); // None
+ } else {
+ return null;
+ }
+ }
+ } else if (cond == INode.KEY_PRESENT) {
+ if (sn.hc == hc && equal (sn.k, k, ct)) {
+ if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
+ return Option.makeOption(sn.v);
+ } else {
+ return null;
+ }
+
+ }
+ else {
+ return Option.makeOption();// None;
+ }
+ } else {
+ if (sn.hc == hc && equal (sn.k, k, ct) && sn.v == cond) {
+ if (GCAS(cn, cn.updatedAt (pos, new SNode<>(k, v, hc), gen), ct)) {
+ return Option.makeOption(sn.v);
+ } else {
+ return null;
+ }
+ }
+ else {
+ return Option.makeOption(); // None
+ }
+ }
+
+ }
+ } else if (cond == null || cond == INode.KEY_ABSENT) {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+ CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
+ if (GCAS(cn, ncnode, ct)) {
+ return Option.makeOption(); // None
+ } else {
+ return null;
+ }
+ } else if (cond == INode.KEY_PRESENT) {
+ return Option.makeOption(); // None;
+ }
+ else {
+ return Option.makeOption(); // None
+ }
+ } else if (m instanceof TNode) {
+ clean(parent, ct, lev - 5);
+ return null;
+ } else if (m instanceof LNode) {
+ // 3) an l-node
+ LNode<K, V> ln = (LNode<K, V>) m;
+ if (cond == null) {
+ Option<V> optv = ln.get(k);
+ if (insertln(ln, k, v, ct)) {
+ return optv;
+ } else {
+ return null;
+ }
+ } else if (cond == INode.KEY_ABSENT) {
+ Option<V> t = ln.get(k);
+ if (t == null) {
+ if (insertln(ln, k, v, ct)) {
+ return Option.makeOption();// None
+ } else {
+ return null;
+ }
+ } else {
+ return t;
+ }
+ } else if (cond == INode.KEY_PRESENT) {
+ Option<V> t = ln.get(k);
+ if (t != null) {
+ if (insertln(ln, k, v, ct)) {
+ return t;
+ } else {
+ return null;
+ }
+ } else {
+ return null; // None
+ }
+ } else {
+ Option<V> t = ln.get (k);
+ if (t != null) {
+ if (((Some<V>) t).get() == cond) {
+ if (insertln(ln, k, v, ct)) {
+ return new Some<>((V) cond);
+ } else {
+ return null;
+ }
+ } else {
+ return Option.makeOption ();
+ }
+ }
+ }
+ }
+
+ // throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
+ LNode<K, V> nn = ln.inserted (k, v);
+ return GCAS (ln, nn, ct);
+ }
+
+ /**
+ * Looks up the value associated with the key.
+ *
+ * @return null if no value has been found, RESTART if the operation
+ * wasn't successful, or any other value otherwise
+ */
+ Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
+ final TrieMap<K, V> ct) {
+ while (true) {
+ MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
+
+ if (m instanceof CNode) {
+ // 1) a multinode
+ final CNode<K, V> cn = (CNode<K, V>) m;
+ int idx = (hc >>> lev) & 0x1f;
+ int flag = 1 << idx;
+ int bmp = cn.bitmap;
+ if ((bmp & flag) == 0) {
+ return null; // 1a) bitmap shows no binding
+ } else { // 1b) bitmap contains a value - descend
+ int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
+ final BasicNode sub = cn.array[pos];
+ if (sub instanceof INode) {
+ INode<K, V> in = (INode<K, V>) sub;
+ if (ct.isReadOnly() || (startgen == ((INodeBase<K, V>) sub).gen)) {
+ return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
+ } else {
+ if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
+ // return rec_lookup (k, hc, lev, parent,
+ // startgen, ct);
+ // Tailrec
+ continue;
+ } else {
+ return RESTART; // used to be throw
+ // RestartException
+ }
+ }
+ } else if (sub instanceof SNode) {
+ // 2) singleton node
+ SNode<K, V> sn = (SNode<K, V>) sub;
+ if (((SNode) sub).hc == hc && equal (sn.k, k, ct)) {
+ return sn.v;
+ } else {
+ return null;
+ }
+ }
+ }
+ } else if (m instanceof TNode) {
+ // 3) non-live node
+ return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
+ } else if (m instanceof LNode) {
+ // 5) an l-node
+ Option<V> tmp = ((LNode<K, V>) m).get (k);
+ return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
+ }
+
+ throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
+ final TrieMap<K, V> ct, final K k, final int hc) {
+ if (ct.nonReadOnly()) {
+ clean(parent, ct, lev - 5);
+ return RESTART; // used to be throw RestartException
+ } else {
+ if (tn.hc == hc && equal(tn.k, k, ct)) {
+ return tn.v;
+ } else {
+ return null;
+ }
+ }
+ }
+
+ /**
+ * Removes the key associated with the given value.
+ *
+ * @param v
+ * if null, will remove the key irregardless of the value;
+ * otherwise removes only if binding contains that exact key
+ * and value
+ * @return null if not successful, an Option[V] indicating the previous
+ * value otherwise
+ */
+ Option<V> rec_remove(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) {
+ MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
+
+ if (m instanceof CNode) {
+ CNode<K, V> cn = (CNode<K, V>) m;
+ int idx = (hc >>> lev) & 0x1f;
+ int bmp = cn.bitmap;
+ int flag = 1 << idx;
+ if ((bmp & flag) == 0) {
+ return Option.makeOption();
+ } else {
+ int pos = Integer.bitCount(bmp & (flag - 1));
+ BasicNode sub = cn.array [pos];
+ Option<V> res = null;
+ if (sub instanceof INode) {
+ INode<K, V> in = (INode<K, V>) sub;
+ if (startgen == in.gen) {
+ res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
+ } else {
+ if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
+ res = rec_remove(k, v, hc, lev, parent, startgen, ct);
+ } else {
+ res = null;
+ }
+ }
+
+ } else if (sub instanceof SNode) {
+ SNode<K, V> sn = (SNode<K, V>) sub;
+ if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || v.equals(sn.v))) {
+ MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
+ if (GCAS(cn, ncn, ct)) {
+ res = Option.makeOption(sn.v);
+ } else {
+ res = null;
+ }
+ } else {
+ res = Option.makeOption ();
+ }
+ }
+
+ if (res instanceof None || (res == null)) {
+ return res;
+ } else {
+ if (parent != null) { // never tomb at root
+ MainNode<K, V> n = GCAS_READ(ct);
+ if (n instanceof TNode) {
+ cleanParent(n, parent, ct, hc, lev, startgen);
+ }
+ }
+
+ return res;
+ }
+ }
+ } else if (m instanceof TNode) {
+ clean(parent, ct, lev - 5);
+ return null;
+ } else if (m instanceof LNode) {
+ LNode<K, V> ln = (LNode<K, V>) m;
+ if (v == null) {
+ Option<V> optv = ln.get(k);
+ MainNode<K, V> nn = ln.removed(k, ct);
+ if (GCAS (ln, nn, ct)) {
+ return optv;
+ } else {
+ return null;
+ }
+ } else {
+ Option<V> tmp = ln.get(k);
+ if (tmp instanceof Some) {
+ Some<V> tmp1 = (Some<V>) tmp;
+ if (tmp1.get () == v) {
+ MainNode<K, V> nn = ln.removed(k, ct);
+ if (GCAS(ln, nn, ct)) {
+ return tmp;
+ } else {
+ return null;
+ }
+ }
+ }
+ }
+ }
+ throw new RuntimeException ("Should not happen");
+ }
+
+ void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
+ final int lev, final Gen startgen) {
+ while (true) {
+ MainNode<K, V> pm = parent.GCAS_READ(ct);
+ if (pm instanceof CNode) {
+ CNode<K, V> cn = (CNode<K, V>) pm;
+ int idx = (hc >>> (lev - 5)) & 0x1f;
+ int bmp = cn.bitmap;
+ int flag = 1 << idx;
+ if ((bmp & flag) == 0) {
+ // somebody already removed this i-node, we're done
+ } else {
+ int pos = Integer.bitCount(bmp & (flag - 1));
+ BasicNode sub = cn.array[pos];
+ if (sub == this) {
+ if (nonlive instanceof TNode) {
+ TNode<K, V> tn = (TNode<K, V>) nonlive;
+ MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed (), gen).toContracted (lev - 5);
+ if (!parent.GCAS(cn, ncn, ct)) {
+ if (ct.readRoot().gen == startgen) {
+ // cleanParent (nonlive, parent, ct, hc,
+ // lev, startgen);
+ // tailrec
+ continue;
+ }
+ }
+ }
+ }
+ }
+ } else {
+ // parent is no longer a cnode, we're done
+ }
+ break;
+ }
+ }
+
+ private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
+ MainNode<K, V> m = nd.GCAS_READ(ct);
+ if (m instanceof CNode) {
+ CNode<K, V> cn = (CNode<K, V>) m;
+ nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
+ }
+ }
+
+ boolean isNullInode(final TrieMap<K, V> ct) {
+ return GCAS_READ(ct) == null;
+ }
+
+ int cachedSize(final TrieMap<K, V> ct) {
+ MainNode<K, V> m = GCAS_READ(ct);
+ return m.cachedSize(ct);
+ }
+
+ // /* this is a quiescent method! */
+ // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
+ // match {
+ // case null => "<null>"
+ // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
+ // tn.hc)
+ // case cn: CNode[_, _] => cn.string(lev)
+ // case ln: LNode[_, _] => ln.string(lev)
+ // case x => "<elem: %s>".format(x)
+ // })
+
+ @Override
+ String string(final int lev) {
+ return "INode";
+ }
+}
\ 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.Map.Entry;
+
+interface KVNode<K, V> {
+ Entry<K, V> kvPair();
+}
--- /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.Map.Entry;
+
+final class LNode<K, V> extends MainNode<K, V> {
+ final ListMap<K, V> listmap;
+
+ LNode(final ListMap<K, V> listmap) {
+ this.listmap = listmap;
+ }
+
+ LNode(final K k, final V v) {
+ this(ListMap.map(k, v));
+ }
+
+ LNode(final K k1, final V v1, final K k2, final V v2) {
+ this(ListMap.map(k1, v1, k2, v2));
+ }
+
+ LNode<K, V> inserted(final K k, final V v) {
+ return new LNode<> (listmap.add (k, v));
+ }
+
+ MainNode<K, V> removed (final K k, final TrieMap<K, V> ct) {
+ ListMap<K, V> updmap = listmap.remove(k);
+ if (updmap.size () > 1) {
+ return new LNode<> (updmap);
+ }
+
+ final Entry<K, V> kv = updmap.iterator().next();
+ // create it tombed so that it gets compressed on subsequent accesses
+ return new TNode<>(kv.getKey(), kv.getValue(), ct.computeHash(kv.getKey()));
+ }
+
+ Option<V> get(final K k) {
+ return listmap.get(k);
+ }
+
+ @Override
+ public int cachedSize(final Object ct) {
+ return listmap.size();
+ }
+
+ @Override
+ String string(final int lev) {
+ // (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
+ return "LNode";
+ }
+}
\ 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.Map.Entry;
+
+final class SNode<K, V> extends BasicNode implements KVNode<K, V> {
+ final K k;
+ final V v;
+ final int hc;
+
+ SNode(final K k, final V v, final int hc) {
+ this.k = k;
+ this.v = v;
+ this.hc = hc;
+ }
+
+ SNode<K, V> copy() {
+ return new SNode<>(k, v, hc);
+ }
+
+ TNode<K, V> copyTombed() {
+ return new TNode<>(k, v, hc);
+ }
+
+ SNode<K, V> copyUntombed() {
+ return new SNode<>(k, v, hc);
+ }
+
+ @Override
+ public Entry<K, V> kvPair() {
+ return new SimpleImmutableEntry<>(k, v);
+ }
+
+ @Override
+ String string(final int lev) {
+ // (" " * lev) + "SNode(%s, %s, %x)".format(k, v, hc);
+ return "SNode";
+ }
+}
\ 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.Map.Entry;
+
+final class TNode<K, V> extends MainNode<K, V> implements KVNode<K, V> {
+ final K k;
+ final V v;
+ final int hc;
+
+ TNode (final K k, final V v, final int hc) {
+ this.k = k;
+ this.v = v;
+ this.hc = hc;
+ }
+
+ TNode<K, V> copy () {
+ return new TNode<>(k, v, hc);
+ }
+
+ TNode<K, V> copyTombed () {
+ return new TNode<>(k, v, hc);
+ }
+
+ SNode<K, V> copyUntombed () {
+ return new SNode<>(k, v, hc);
+ }
+
+ @Override
+ public Entry<K, V> kvPair () {
+ return new SimpleImmutableEntry<>(k, v);
+ }
+
+ @Override
+ public int cachedSize(final Object ct) {
+ return 1;
+ }
+
+ @Override
+ String string(final int lev) {
+ // (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc);
+ return "TNode";
+ }
+}
\ No newline at end of file
// }
// }
- static class INode<K, V> extends INodeBase<K, V> {
- static final Object KEY_PRESENT = new Object ();
- static final Object KEY_ABSENT = new Object ();
-
- static <K,V> INode<K,V> newRootNode () {
- Gen gen = new Gen ();
- CNode<K, V> cn = new CNode<> (0, new BasicNode[] {}, gen);
- return new INode<>(cn, gen);
- }
-
- public INode (final MainNode<K, V> bn, final Gen g) {
- super (g);
- WRITE (bn);
- }
-
- public INode (final Gen g) {
- this (null, g);
- }
-
- final void WRITE (final MainNode<K, V> nval) {
- INodeBase.updater.set (this, nval);
- }
-
- final boolean CAS (final MainNode<K, V> old, final MainNode<K, V> n) {
- return INodeBase.updater.compareAndSet (this, old, n);
- }
-
- final MainNode<K, V> gcasRead (final TrieMap<K, V> ct) {
- return GCAS_READ (ct);
- }
-
- final MainNode<K, V> GCAS_READ (final TrieMap<K, V> ct) {
- MainNode<K, V> m = /* READ */mainnode;
- MainNode<K, V> prevval = /* READ */m.prev;
- if (prevval == null) {
- return m;
- } else {
- return GCAS_Complete (m, ct);
- }
- }
-
- private MainNode<K, V> GCAS_Complete (MainNode<K, V> m, final TrieMap<K, V> ct) {
- while (true) {
- if (m == null) {
- return null;
- } else {
- // complete the GCAS
- MainNode<K, V> prev = /* READ */m.prev;
- INode<K, V> ctr = ct.readRoot (true);
-
- if (prev == null) {
- return m;
- }
-
- if (prev instanceof FailedNode) {
- // try to commit to previous value
- FailedNode<K, V> fn = (FailedNode<K, V>) prev;
- if (CAS (m, fn.prev)) {
- return fn.prev;
- } else {
- // Tailrec
- // return GCAS_Complete (/* READ */mainnode, ct);
- m = /* READ */mainnode;
- continue;
- }
- } else if (prev instanceof MainNode) {
- // Assume that you've read the root from the generation
- // G.
- // Assume that the snapshot algorithm is correct.
- // ==> you can only reach nodes in generations <= G.
- // ==> `gen` is <= G.
- // We know that `ctr.gen` is >= G.
- // ==> if `ctr.gen` = `gen` then they are both equal to
- // G.
- // ==> otherwise, we know that either `ctr.gen` > G,
- // `gen` <
- // G,
- // or both
- if ((ctr.gen == gen) && ct.nonReadOnly ()) {
- // try to commit
- if (m.CAS_PREV (prev, null)) {
- return m;
- } else {
- // return GCAS_Complete (m, ct);
- // tailrec
- continue;
- }
- } else {
- // try to abort
- m.CAS_PREV (prev, new FailedNode<> (prev));
- return GCAS_Complete (/* READ */mainnode, ct);
- }
- }
- }
- throw new RuntimeException ("Should not happen");
- }
- }
-
- final boolean GCAS (final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
- n.WRITE_PREV (old);
- if (CAS (old, n)) {
- GCAS_Complete (n, ct);
- return /* READ */n.prev == null;
- } else {
- return false;
- }
- }
-
- private 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) {
- INode<K, V> nin = new INode<> (gen);
- nin.WRITE (cn);
- return nin;
- }
-
- final INode<K, V> copyToGen (final Gen ngen, final TrieMap<K, V> ct) {
- INode<K, V> nin = new INode<> (ngen);
- MainNode<K, V> main = GCAS_READ (ct);
- nin.WRITE (main);
- return nin;
- }
-
- /**
- * Inserts a key value pair, overwriting the old pair if the keys match.
- *
- * @return true if successful, false otherwise
- */
- final 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) {
- MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
-
- if (m instanceof CNode) {
- // 1) a multiway node
- CNode<K, V> cn = (CNode<K, V>) m;
- int idx = (hc >>> lev) & 0x1f;
- int flag = 1 << idx;
- int bmp = cn.bitmap;
- int mask = flag - 1;
- int pos = Integer.bitCount (bmp & mask);
- if ((bmp & flag) != 0) {
- // 1a) insert below
- BasicNode cnAtPos = cn.array [pos];
- if (cnAtPos instanceof INode) {
- INode<K, V> in = (INode<K, V>) cnAtPos;
- if (startgen == in.gen) {
- return in.rec_insert (k, v, hc, lev + 5, this, startgen, ct);
- } else {
- if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
- // return rec_insert (k, v, hc, lev, parent,
- // startgen, ct);
- // tailrec
- continue;
- } else {
- return false;
- }
- }
- } else if (cnAtPos instanceof SNode) {
- SNode<K, V> sn = (SNode<K, V>) cnAtPos;
- if (sn.hc == hc && equal (sn.k, k, ct)) {
- return GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct);
- } else {
- CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
- MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
- return GCAS (cn, nn, ct);
- }
- }
- } else {
- CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
- MainNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<> (k, v, hc), gen);
- return GCAS (cn, ncnode, ct);
- }
- } else if (m instanceof TNode) {
- clean (parent, ct, lev - 5);
- return false;
- } else if (m instanceof LNode) {
- LNode<K, V> ln = (LNode<K, V>) m;
- MainNode<K, V> nn = ln.inserted (k, v);
- return GCAS (ln, nn, ct);
- }
-
- throw new RuntimeException ("Should not happen");
- }
- }
-
- /**
- * Inserts a new key value pair, given that a specific condition is met.
- *
- * @param cond
- * null - don't care if the key was there
- * KEY_ABSENT - key wasn't there
- * KEY_PRESENT - key was there
- * other value `v` - key must be bound to `v`
- * @return null if unsuccessful, Option[V] otherwise (indicating
- * previous value bound to the key)
- */
- final Option<V> rec_insertif (final K k, final V v, final int hc, final Object cond, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
- while (true) {
- MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
-
- if (m instanceof CNode) {
- // 1) a multiway node
- CNode<K, V> cn = (CNode<K, V>) m;
- int idx = (hc >>> lev) & 0x1f;
- int flag = 1 << idx;
- int bmp = cn.bitmap;
- int mask = flag - 1;
- int pos = Integer.bitCount (bmp & mask);
-
- if ((bmp & flag) != 0) {
- // 1a) insert below
- BasicNode cnAtPos = cn.array [pos];
- if (cnAtPos instanceof INode) {
- INode<K, V> in = (INode<K, V>) cnAtPos;
- if (startgen == in.gen) {
- return in.rec_insertif (k, v, hc, cond, lev + 5, this, startgen, ct);
- } else {
- if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
- // return rec_insertif (k, v, hc, cond, lev,
- // parent, startgen, ct);
- // tailrec
- continue;
- } else {
- return null;
- }
- }
- } else if (cnAtPos instanceof SNode) {
- SNode<K, V> sn = (SNode<K, V>) cnAtPos;
- if (cond == null) {
- if (sn.hc == hc && equal (sn.k, k, ct)) {
- if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
- return Option.makeOption(sn.v);
- } else {
- return null;
- }
- } else {
- CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
- MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
- if (GCAS (cn, nn, ct)) {
- return Option.makeOption(); // None;
- } else {
- return null;
- }
- }
-
- } else if (cond == INode.KEY_ABSENT) {
- if (sn.hc == hc && equal (sn.k, k, ct)) {
- return Option.makeOption(sn.v);
- } else {
- CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
- MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
- if (GCAS (cn, nn, ct)) {
- return Option.makeOption (); // None
- } else {
- return null;
- }
- }
- } else if (cond == INode.KEY_PRESENT) {
- if (sn.hc == hc && equal (sn.k, k, ct)) {
- if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
- return Option.makeOption (sn.v);
- } else {
- return null;
- }
-
- }
- else {
- return Option.makeOption ();// None;
- }
- } else {
- if (sn.hc == hc && equal (sn.k, k, ct) && sn.v == cond) {
- if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
- return Option.makeOption (sn.v);
- } else {
- return null;
- }
- }
- else {
- return Option.makeOption (); // None
- }
- }
-
- }
- } else if (cond == null || cond == INode.KEY_ABSENT) {
- CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
- CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<> (k, v, hc), gen);
- if (GCAS (cn, ncnode, ct)) {
- return Option.makeOption ();// None
- } else {
- return null;
- }
- } else if (cond == INode.KEY_PRESENT) {
- return Option.makeOption ();// None;
- }
- else {
- return Option.makeOption (); // None
- }
- } else if (m instanceof TNode) {
- clean (parent, ct, lev - 5);
- return null;
- } else if (m instanceof LNode) {
- // 3) an l-node
- LNode<K, V> ln = (LNode<K, V>) m;
- if (cond == null) {
- Option<V> optv = ln.get (k);
- if (insertln (ln, k, v, ct)) {
- return optv;
- } else {
- return null;
- }
- } else if (cond == INode.KEY_ABSENT) {
- Option<V> t = ln.get (k);
- if (t == null) {
- if (insertln (ln, k, v, ct)) {
- return Option.makeOption ();// None
- } else {
- return null;
- }
- } else {
- return t;
- }
- } else if (cond == INode.KEY_PRESENT) {
- Option<V> t = ln.get (k);
- if (t != null) {
- if (insertln (ln, k, v, ct)) {
- return t;
- } else {
- return null;
- }
- }
- else {
- return null; // None
- }
- } else {
- Option<V> t = ln.get (k);
- if (t != null) {
- if (((Some<V>) t).get () == cond) {
- if (insertln (ln, k, v, ct)) {
- return new Some<> ((V) cond);
- } else {
- return null;
- }
-
- } else {
- return Option.makeOption ();
- }
- }
- }
- }
-
-// throw new RuntimeException ("Should not happen");
- }
- }
-
- final boolean insertln (final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
- LNode<K, V> nn = ln.inserted (k, v);
- return GCAS (ln, nn, ct);
- }
-
- /**
- * Looks up the value associated with the key.
- *
- * @return null if no value has been found, RESTART if the operation
- * wasn't successful, or any other value otherwise
- */
- final Object rec_lookup (final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
- while (true) {
- MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
-
- if (m instanceof CNode) {
- // 1) a multinode
- final CNode<K, V> cn = (CNode<K, V>) m;
- int idx = (hc >>> lev) & 0x1f;
- int flag = 1 << idx;
- int bmp = cn.bitmap;
- if ((bmp & flag) == 0) {
- return null; // 1a) bitmap shows no binding
- } else { // 1b) bitmap contains a value - descend
- int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount (bmp & (flag - 1));
- final BasicNode sub = cn.array [pos];
- if (sub instanceof INode) {
- INode<K, V> in = (INode<K, V>) sub;
- if (ct.isReadOnly () || (startgen == ((INodeBase<K, V>) sub).gen)) {
- return in.rec_lookup (k, hc, lev + 5, this, startgen, ct);
- } else {
- if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
- // return rec_lookup (k, hc, lev, parent,
- // startgen, ct);
- // Tailrec
- continue;
- }
- else {
- return RESTART; // used to be throw
- // RestartException
- }
- }
- } else if (sub instanceof SNode) {
- // 2) singleton node
- SNode<K, V> sn = (SNode<K, V>) sub;
- if (((SNode) sub).hc == hc && equal (sn.k, k, ct)) {
- return sn.v;
- } else {
- return null;
- }
- }
- }
- } else if (m instanceof TNode) {
- // 3) non-live node
- return cleanReadOnly ((TNode<K, V>) m, lev, parent, ct, k, hc);
- } else if (m instanceof LNode) {
- // 5) an l-node
- Option<V> tmp = ((LNode<K, V>) m).get (k);
- return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
- }
-
- throw new RuntimeException ("Should not happen");
- }
- }
-
- private Object cleanReadOnly (final TNode<K, V> tn, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct, final K k, final int hc) {
- if (ct.nonReadOnly ()) {
- clean (parent, ct, lev - 5);
- return RESTART; // used to be throw RestartException
- } else {
- if (tn.hc == hc && equal(tn.k, k, ct)) {
- return tn.v;
- } else {
- return null;
- }
- }
- }
-
- /**
- * Removes the key associated with the given value.
- *
- * @param v
- * if null, will remove the key irregardless of the value;
- * otherwise removes only if binding contains that exact key
- * and value
- * @return null if not successful, an Option[V] indicating the previous
- * value otherwise
- */
- final Option<V> rec_remove (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) {
- MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
-
- if (m instanceof CNode) {
- CNode<K, V> cn = (CNode<K, V>) m;
- int idx = (hc >>> lev) & 0x1f;
- int bmp = cn.bitmap;
- int flag = 1 << idx;
- if ((bmp & flag) == 0) {
- return Option.makeOption ();
- } else {
- int pos = Integer.bitCount (bmp & (flag - 1));
- BasicNode sub = cn.array [pos];
- Option<V> res = null;
- if (sub instanceof INode) {
- INode<K, V> in = (INode<K, V>) sub;
- if (startgen == in.gen) {
- res = in.rec_remove (k, v, hc, lev + 5, this, startgen, ct);
- } else {
- if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
- res = rec_remove (k, v, hc, lev, parent, startgen, ct);
- } else {
- res = null;
- }
- }
-
- } else if (sub instanceof SNode) {
- SNode<K, V> sn = (SNode<K, V>) sub;
- if (sn.hc == hc && equal (sn.k, k, ct) && (v == null || v.equals(sn.v))) {
- MainNode<K, V> ncn = cn.removedAt (pos, flag, gen).toContracted (lev);
- if (GCAS (cn, ncn, ct)) {
- res = Option.makeOption (sn.v);
- } else {
- res = null;
- }
- } else {
- res = Option.makeOption ();
- }
- }
-
- if (res instanceof None || (res == null)) {
- return res;
- } else {
- if (parent != null) { // never tomb at root
- MainNode<K, V> n = GCAS_READ (ct);
- if (n instanceof TNode) {
- cleanParent (n, parent, ct, hc, lev, startgen);
- }
- }
-
- return res;
- }
- }
- } else if (m instanceof TNode) {
- clean (parent, ct, lev - 5);
- return null;
- } else if (m instanceof LNode) {
- LNode<K, V> ln = (LNode<K, V>) m;
- if (v == null) {
- Option<V> optv = ln.get (k);
- MainNode<K, V> nn = ln.removed (k, ct);
- if (GCAS (ln, nn, ct)) {
- return optv;
- } else {
- return null;
- }
- } else {
- Option<V> tmp = ln.get (k);
- if (tmp instanceof Some) {
- Some<V> tmp1 = (Some<V>) tmp;
- if (tmp1.get () == v) {
- MainNode<K, V> nn = ln.removed (k, ct);
- if (GCAS (ln, nn, ct)) {
- return tmp;
- } else {
- return null;
- }
- }
- }
- }
- }
- throw new RuntimeException ("Should not happen");
- }
-
- void cleanParent (final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc, final int lev, final Gen startgen) {
- while (true) {
- MainNode<K, V> pm = parent.GCAS_READ (ct);
- if (pm instanceof CNode) {
- CNode<K, V> cn = (CNode<K, V>) pm;
- int idx = (hc >>> (lev - 5)) & 0x1f;
- int bmp = cn.bitmap;
- int flag = 1 << idx;
- if ((bmp & flag) == 0) {
- } // somebody already removed this i-node, we're done
- else {
- int pos = Integer.bitCount (bmp & (flag - 1));
- BasicNode sub = cn.array [pos];
- if (sub == this) {
- if (nonlive instanceof TNode) {
- TNode<K, V> tn = (TNode<K, V>) nonlive;
- MainNode<K, V> ncn = cn.updatedAt (pos, tn.copyUntombed (), gen).toContracted (lev - 5);
- if (!parent.GCAS (cn, ncn, ct)) {
- if (ct.readRoot ().gen == startgen) {
- // cleanParent (nonlive, parent, ct, hc,
- // lev, startgen);
- // tailrec
- continue;
- }
- }
- }
- }
- }
- } else {
- // parent is no longer a cnode, we're done
- }
- break;
- }
- }
-
- private void clean (final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
- MainNode<K, V> m = nd.GCAS_READ (ct);
- if (m instanceof CNode) {
- CNode<K, V> cn = (CNode<K, V>) m;
- nd.GCAS (cn, cn.toCompressed (ct, lev, gen), ct);
- }
- }
-
- final boolean isNullInode (final TrieMap<K, V> ct) {
- return GCAS_READ (ct) == null;
- }
-
- final int cachedSize (final TrieMap<K, V> ct) {
- MainNode<K, V> m = GCAS_READ (ct);
- return m.cachedSize (ct);
- }
-
- // /* this is a quiescent method! */
- // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
- // match {
- // case null => "<null>"
- // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
- // tn.hc)
- // case cn: CNode[_, _] => cn.string(lev)
- // case ln: LNode[_, _] => ln.string(lev)
- // case x => "<elem: %s>".format(x)
- // })
-
- @Override
- public String string (final int lev) {
- return "INode";
- }
-
- }
-
- private static final class FailedNode<K, V> extends MainNode<K, V> {
- MainNode<K, V> p;
-
- FailedNode (final MainNode<K, V> p) {
- this.p = p;
- WRITE_PREV (p);
- }
-
- @Override
- public String string (final int lev) {
- throw new UnsupportedOperationException ();
- }
-
- @Override
- public int cachedSize (final Object ct) {
- throw new UnsupportedOperationException ();
- }
-
- @Override
- public String toString () {
- return String.format ("FailedNode(%s)", p);
- }
- }
-
- private interface KVNode<K, V> {
- Map.Entry<K, V> kvPair ();
- }
-
- private static final class SNode<K, V> extends BasicNode implements KVNode<K, V> {
- final K k;
- final V v;
- final int hc;
-
- SNode (final K k, final V v, final int hc) {
- this.k = k;
- this.v = v;
- this.hc = hc;
- }
-
- final SNode<K, V> copy() {
- return new SNode<> (k, v, hc);
- }
-
- final TNode<K, V> copyTombed () {
- return new TNode<> (k, v, hc);
- }
-
- final SNode<K, V> copyUntombed () {
- return new SNode<> (k, v, hc);
- }
-
- @Override
- final public Map.Entry<K, V> kvPair () {
- return new SimpleImmutableEntry<> (k, v);
- }
-
- @Override
- final public String string (final int lev) {
- // (" " * lev) + "SNode(%s, %s, %x)".format(k, v, hc);
- return "SNode";
- }
- }
-
- private static final class TNode<K, V> extends MainNode<K, V> implements KVNode<K, V> {
- final K k;
- final V v;
- final int hc;
-
- TNode (final K k, final V v, final int hc) {
- this.k = k;
- this.v = v;
- this.hc = hc;
- }
-
- final TNode<K, V> copy () {
- return new TNode<> (k, v, hc);
- }
-
- final TNode<K, V> copyTombed () {
- return new TNode<> (k, v, hc);
- }
-
- final SNode<K, V> copyUntombed () {
- return new SNode<> (k, v, hc);
- }
-
- @Override
- final public Map.Entry<K, V> kvPair () {
- return new SimpleImmutableEntry<> (k, v);
- }
-
- @Override
- final public int cachedSize (final Object ct) {
- return 1;
- }
-
- @Override
- final public String string (final int lev) {
- // (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc);
- return "TNode";
- }
- }
-
- private final static class LNode<K, V> extends MainNode<K, V> {
- final ListMap<K, V> listmap;
-
- public LNode (final ListMap<K, V> listmap) {
- this.listmap = listmap;
- }
-
- public LNode(final K k, final V v) {
- this (ListMap.map (k, v));
- }
-
- public LNode (final K k1, final V v1, final K k2, final V v2) {
- this (ListMap.map (k1, v1, k2, v2));
- }
-
- LNode<K, V> inserted (final K k, final V v) {
- return new LNode<> (listmap.add (k, v));
- }
-
- MainNode<K, V> removed (final K k, final TrieMap<K, V> ct) {
- ListMap<K, V> updmap = listmap.remove (k);
- if (updmap.size () > 1) {
- return new LNode<> (updmap);
- } else {
- Entry<K, V> kv = updmap.iterator ().next ();
- // create it tombed so that it gets compressed on subsequent
- // accesses
- return new TNode<> (kv.getKey (), kv.getValue (), ct.computeHash (kv.getKey ()));
- }
- }
-
- Option<V> get (final K k) {
- return listmap.get (k);
- }
-
- @Override
- public int cachedSize (final Object ct) {
- return listmap.size ();
- }
-
- @Override
- public String string (final int lev) {
- // (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
- return "LNode";
- }
- }
-
- private static final class CNode<K, V> extends CNodeBase<K, V> {
-
- final int bitmap;
- final BasicNode[] array;
- final Gen gen;
-
- CNode (final int bitmap, final BasicNode[] array, final Gen gen) {
- this.bitmap = bitmap;
- this.array = array;
- this.gen = gen;
- }
-
- // this should only be called from within read-only snapshots
- @Override
- final public int cachedSize (final Object ct) {
- int currsz = READ_SIZE ();
- if (currsz != -1) {
- return currsz;
- } else {
- int sz = computeSize ((TrieMap<K, V>) ct);
- while (READ_SIZE () == -1) {
- CAS_SIZE (-1, sz);
- }
- return READ_SIZE ();
- }
- }
-
- // lends itself towards being parallelizable by choosing
- // a random starting offset in the array
- // => if there are concurrent size computations, they start
- // at different positions, so they are more likely to
- // to be independent
- private int computeSize (final TrieMap<K, V> ct) {
- int i = 0;
- int sz = 0;
- // final int offset = (array.length > 0) ?
- // // util.Random.nextInt(array.length) /* <-- benchmarks show that
- // // this causes observable contention */
- // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
- // array.length)
- // : 0;
-
- final int offset = 0;
- while (i < array.length) {
- int pos = (i + offset) % array.length;
- BasicNode elem = array [pos];
- if (elem instanceof SNode) {
- sz += 1;
- } else if (elem instanceof INode) {
- sz += ((INode<K, V>) elem).cachedSize (ct);
- }
- i += 1;
- }
- return sz;
- }
-
- final CNode<K, V> updatedAt (final int pos, final BasicNode nn, final Gen gen) {
- int len = array.length;
- BasicNode[] narr = new BasicNode[len];
- System.arraycopy (array, 0, narr, 0, len);
- narr [pos] = nn;
- return new CNode<> (bitmap, narr, gen);
- }
-
- final CNode<K, V> removedAt (final int pos, final int flag, final Gen gen) {
- BasicNode[] arr = array;
- int len = arr.length;
- BasicNode[] narr = new BasicNode[len - 1];
- System.arraycopy (arr, 0, narr, 0, pos);
- System.arraycopy (arr, pos + 1, narr, pos, len - pos - 1);
- return new CNode<> (bitmap ^ flag, narr, gen);
- }
-
- final CNode<K, V> insertedAt (final int pos, final int flag, final BasicNode nn, final Gen gen) {
- int len = array.length;
- int bmp = bitmap;
- BasicNode[] narr = new BasicNode[len + 1];
- System.arraycopy (array, 0, narr, 0, pos);
- narr [pos] = nn;
- System.arraycopy (array, pos, narr, pos + 1, len - pos);
- return new CNode<> (bmp | flag, narr, gen);
- }
-
- /**
- * Returns a copy of this cnode such that all the i-nodes below it are
- * copied to the specified generation `ngen`.
- */
- final CNode<K, V> renewed (final Gen ngen, final TrieMap<K, V> ct) {
- int i = 0;
- BasicNode[] arr = array;
- int len = arr.length;
- BasicNode[] narr = new BasicNode[len];
- while (i < len) {
- BasicNode elem = arr [i];
- if (elem instanceof INode) {
- INode<K, V> in = (INode<K, V>) elem;
- narr [i] = in.copyToGen (ngen, ct);
- } else if (elem instanceof BasicNode) {
- narr [i] = elem;
- }
- i += 1;
- }
- return new CNode<> (bitmap, narr, ngen);
- }
-
- private BasicNode resurrect (final INode<K, V> inode, final Object inodemain) {
- if (inodemain instanceof TNode) {
- TNode<K, V> tn = (TNode<K, V>) inodemain;
- return tn.copyUntombed ();
- } else {
- return inode;
- }
- }
-
- final MainNode<K, V> toContracted (final int lev) {
- if (array.length == 1 && lev > 0) {
- if (array [0] instanceof SNode) {
- SNode<K, V> sn = (SNode<K, V>) array [0];
- return sn.copyTombed ();
- } else {
- return this;
- }
-
- } else {
- return this;
- }
- }
-
- // - if the branching factor is 1 for this CNode, and the child
- // is a tombed SNode, returns its tombed version
- // - otherwise, if there is at least one non-null node below,
- // returns the version of this node with at least some null-inodes
- // removed (those existing when the op began)
- // - if there are only null-i-nodes below, returns null
- final MainNode<K, V> toCompressed (final TrieMap<K, V> ct, final int lev, final Gen gen) {
- int bmp = bitmap;
- int i = 0;
- BasicNode[] arr = array;
- BasicNode[] tmparray = new BasicNode[arr.length];
- while (i < arr.length) { // construct new bitmap
- BasicNode sub = arr [i];
- if (sub instanceof INode) {
- INode<K, V> in = (INode<K, V>) sub;
- MainNode<K, V> inodemain = in.gcasRead (ct);
- assert (inodemain != null);
- tmparray [i] = resurrect (in, inodemain);
- } else if (sub instanceof SNode) {
- tmparray [i] = sub;
- }
- i += 1;
- }
-
- return new CNode<K, V> (bmp, tmparray, gen).toContracted (lev);
- }
-
- @Override
- public String string (final int lev) {
- // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
- // 1)).mkString("\n"));
- return "CNode";
- }
-
- /*
- * quiescently consistent - don't call concurrently to anything
- * involving a GCAS!!
- */
- // protected Seq<K,V> collectElems() {
- // array flatMap {
- // case sn: SNode[K, V] => Some(sn.kvPair)
- // case in: INode[K, V] => in.mainnode match {
- // case tn: TNode[K, V] => Some(tn.kvPair)
- // case ln: LNode[K, V] => ln.listmap.toList
- // case cn: CNode[K, V] => cn.collectElems
- // }
- // }
- // }
-
- // protected Seq<String> collectLocalElems() {
- // // array flatMap {
- // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
- // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
- // ")")
- // // }
- // return null;
- // }
-
- @Override
- public String toString () {
- // val elems = collectLocalElems
- // "CNode(sz: %d; %s)".format(elems.size,
- // elems.sorted.mkString(", "))
- return "CNode";
- }
-
- static <K, V> MainNode<K,V> dual (final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc, final int lev, final Gen gen) {
- if (lev < 35) {
- int xidx = (xhc >>> lev) & 0x1f;
- int yidx = (yhc >>> lev) & 0x1f;
- int bmp = (1 << xidx) | (1 << yidx);
-
- if (xidx == yidx) {
- INode<K, V> subinode = new INode<> (gen);// (TrieMap.inodeupdater)
- subinode.mainnode = dual (x, xhc, y, yhc, lev + 5, gen);
- return new CNode<> (bmp, new BasicNode[] { subinode }, gen);
- } else {
- if (xidx < yidx) {
- return new CNode<> (bmp, new BasicNode[] { x, y }, gen);
- } else {
- return new CNode<> (bmp, new BasicNode[] { y, x }, gen);
- }
- }
- } else {
- return new LNode<> (x.k, x.v, y.k, y.v);
- }
- }
-
- }
-
private static class RDCSS_Descriptor<K, V> {
INode<K, V> old;
MainNode<K, V> expectedmain;
this.expectedmain = expectedmain;
this.nv = nv;
}
-
- }
-
- private static class Equiv<K> implements Serializable {
- private static final long serialVersionUID = 1L;
-
- public boolean equiv (final K k1, final K k2) {
- return k1.equals (k2);
- }
-
- static Equiv universal = new Equiv ();
- }
-
- private static interface Hashing<K> extends Serializable {
- public int hash (K k);
- }
-
- 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;
- }
}
private final Hashing<K> hashingobj;
}
public TrieMap () {
- this (new Default<K> (), Equiv.universal);
+ this (new Hashing.Default<K>(), Equiv.universal);
}
/* internal methods */
Code Review / yangtools.git / commitdiff