2 * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
16 package org.opendaylight.yangtools.triemap;
18 final class INode<K, V> extends INodeBase<K, V> {
19 static final Object KEY_PRESENT = new Object ();
20 static final Object KEY_ABSENT = new Object ();
22 static <K,V> INode<K,V> newRootNode() {
24 CNode<K, V> cn = new CNode<> (0, new BasicNode[] {}, gen);
25 return new INode<>(cn, gen);
28 private INode(final MainNode<K, V> bn, final Gen g) {
37 void WRITE(final MainNode<K, V> nval) {
38 INodeBase.updater.set(this, nval);
41 boolean CAS(final MainNode<K, V> old, final MainNode<K, V> n) {
42 return INodeBase.updater.compareAndSet(this, old, n);
45 MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
49 MainNode<K, V> GCAS_READ(final TrieMap<K, V> ct) {
50 MainNode<K, V> m = /* READ */mainnode;
51 MainNode<K, V> prevval = /* READ */m.prev;
52 if (prevval == null) {
55 return GCAS_Complete(m, ct);
59 private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<K, V> ct) {
65 MainNode<K, V> prev = /* READ */m.prev;
66 INode<K, V> ctr = ct.readRoot(true);
72 if (prev instanceof FailedNode) {
73 // try to commit to previous value
74 FailedNode<K, V> fn = (FailedNode<K, V>) prev;
75 if (CAS(m, fn.prev)) {
79 // return GCAS_Complete (/* READ */mainnode, ct);
80 m = /* READ */mainnode;
83 } else if (prev instanceof MainNode) {
84 // Assume that you've read the root from the generation
86 // Assume that the snapshot algorithm is correct.
87 // ==> you can only reach nodes in generations <= G.
89 // We know that `ctr.gen` is >= G.
90 // ==> if `ctr.gen` = `gen` then they are both equal to
92 // ==> otherwise, we know that either `ctr.gen` > G,
96 if ((ctr.gen == gen) && ct.nonReadOnly()) {
98 if (m.CAS_PREV(prev, null)) {
101 // return GCAS_Complete (m, ct);
107 m.CAS_PREV(prev, new FailedNode<>(prev));
108 return GCAS_Complete(/* READ */mainnode, ct);
112 throw new RuntimeException ("Should not happen");
116 boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
119 GCAS_Complete (n, ct);
120 return /* READ */n.prev == null;
126 private boolean equal(final K k1, final K k2, final TrieMap<K, V> ct) {
127 return ct.equality().equiv(k1, k2);
130 private INode<K, V> inode(final MainNode<K, V> cn) {
131 INode<K, V> nin = new INode<>(gen);
136 INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
137 INode<K, V> nin = new INode<>(ngen);
138 MainNode<K, V> main = GCAS_READ(ct);
144 * Inserts a key value pair, overwriting the old pair if the keys match.
146 * @return true if successful, false otherwise
148 boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
149 final TrieMap<K, V> ct) {
151 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
153 if (m instanceof CNode) {
154 // 1) a multiway node
155 CNode<K, V> cn = (CNode<K, V>) m;
156 int idx = (hc >>> lev) & 0x1f;
160 int pos = Integer.bitCount(bmp & mask);
161 if ((bmp & flag) != 0) {
163 BasicNode cnAtPos = cn.array[pos];
164 if (cnAtPos instanceof INode) {
165 INode<K, V> in = (INode<K, V>) cnAtPos;
166 if (startgen == in.gen) {
167 return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
169 if (GCAS (cn, cn.renewed(startgen, ct), ct)) {
170 // return rec_insert (k, v, hc, lev, parent,
178 } else if (cnAtPos instanceof SNode) {
179 SNode<K, V> sn = (SNode<K, V>) cnAtPos;
180 if (sn.hc == hc && equal(sn.k, k, ct)) {
181 return GCAS (cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
183 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
184 MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
185 hc, lev + 5, gen)), gen);
186 return GCAS (cn, nn, ct);
190 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
191 MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<> (k, v, hc), gen);
192 return GCAS (cn, ncnode, ct);
194 } else if (m instanceof TNode) {
195 clean(parent, ct, lev - 5);
197 } else if (m instanceof LNode) {
198 LNode<K, V> ln = (LNode<K, V>) m;
199 MainNode<K, V> nn = ln.inserted(k, v);
200 return GCAS(ln, nn, ct);
203 throw new RuntimeException ("Should not happen");
208 * Inserts a new key value pair, given that a specific condition is met.
211 * null - don't care if the key was there
212 * KEY_ABSENT - key wasn't there
213 * KEY_PRESENT - key was there
214 * other value `v` - key must be bound to `v`
215 * @return null if unsuccessful, Option[V] otherwise (indicating
216 * previous value bound to the key)
218 Option<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
219 final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
221 MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
223 if (m instanceof CNode) {
224 // 1) a multiway node
225 CNode<K, V> cn = (CNode<K, V>) m;
226 int idx = (hc >>> lev) & 0x1f;
230 int pos = Integer.bitCount(bmp & mask);
232 if ((bmp & flag) != 0) {
234 BasicNode cnAtPos = cn.array [pos];
235 if (cnAtPos instanceof INode) {
236 INode<K, V> in = (INode<K, V>) cnAtPos;
237 if (startgen == in.gen) {
238 return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
240 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
241 // return rec_insertif (k, v, hc, cond, lev,
242 // parent, startgen, ct);
249 } else if (cnAtPos instanceof SNode) {
250 SNode<K, V> sn = (SNode<K, V>) cnAtPos;
252 if (sn.hc == hc && equal(sn.k, k, ct)) {
253 if (GCAS(cn, cn.updatedAt(pos, new SNode<> (k, v, hc), gen), ct)) {
254 return Option.makeOption(sn.v);
259 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
260 MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
261 new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
262 if (GCAS(cn, nn, ct)) {
263 return Option.makeOption(); // None;
269 } else if (cond == INode.KEY_ABSENT) {
270 if (sn.hc == hc && equal (sn.k, k, ct)) {
271 return Option.makeOption(sn.v);
273 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
274 MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
275 new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
276 if (GCAS(cn, nn, ct)) {
277 return Option.makeOption(); // None
282 } else if (cond == INode.KEY_PRESENT) {
283 if (sn.hc == hc && equal (sn.k, k, ct)) {
284 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
285 return Option.makeOption(sn.v);
292 return Option.makeOption();// None;
295 if (sn.hc == hc && equal (sn.k, k, ct) && sn.v == cond) {
296 if (GCAS(cn, cn.updatedAt (pos, new SNode<>(k, v, hc), gen), ct)) {
297 return Option.makeOption(sn.v);
303 return Option.makeOption(); // None
308 } else if (cond == null || cond == INode.KEY_ABSENT) {
309 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
310 CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
311 if (GCAS(cn, ncnode, ct)) {
312 return Option.makeOption(); // None
316 } else if (cond == INode.KEY_PRESENT) {
317 return Option.makeOption(); // None;
320 return Option.makeOption(); // None
322 } else if (m instanceof TNode) {
323 clean(parent, ct, lev - 5);
325 } else if (m instanceof LNode) {
327 LNode<K, V> ln = (LNode<K, V>) m;
329 Option<V> optv = ln.get(k);
330 if (insertln(ln, k, v, ct)) {
335 } else if (cond == INode.KEY_ABSENT) {
336 Option<V> t = ln.get(k);
338 if (insertln(ln, k, v, ct)) {
339 return Option.makeOption();// None
346 } else if (cond == INode.KEY_PRESENT) {
347 Option<V> t = ln.get(k);
349 if (insertln(ln, k, v, ct)) {
358 Option<V> t = ln.get (k);
360 if (((Some<V>) t).get() == cond) {
361 if (insertln(ln, k, v, ct)) {
362 return new Some<>((V) cond);
367 return Option.makeOption ();
373 // throw new RuntimeException ("Should not happen");
377 boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
378 LNode<K, V> nn = ln.inserted (k, v);
379 return GCAS (ln, nn, ct);
383 * Looks up the value associated with the key.
385 * @return null if no value has been found, RESTART if the operation
386 * wasn't successful, or any other value otherwise
388 Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
389 final TrieMap<K, V> ct) {
391 MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
393 if (m instanceof CNode) {
395 final CNode<K, V> cn = (CNode<K, V>) m;
396 int idx = (hc >>> lev) & 0x1f;
399 if ((bmp & flag) == 0) {
400 return null; // 1a) bitmap shows no binding
401 } else { // 1b) bitmap contains a value - descend
402 int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
403 final BasicNode sub = cn.array[pos];
404 if (sub instanceof INode) {
405 INode<K, V> in = (INode<K, V>) sub;
406 if (ct.isReadOnly() || (startgen == ((INodeBase<K, V>) sub).gen)) {
407 return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
409 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
410 // return rec_lookup (k, hc, lev, parent,
415 return RESTART; // used to be throw
419 } else if (sub instanceof SNode) {
421 SNode<K, V> sn = (SNode<K, V>) sub;
422 if (((SNode) sub).hc == hc && equal (sn.k, k, ct)) {
429 } else if (m instanceof TNode) {
431 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
432 } else if (m instanceof LNode) {
434 Option<V> tmp = ((LNode<K, V>) m).get (k);
435 return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
438 throw new RuntimeException ("Should not happen");
442 private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
443 final TrieMap<K, V> ct, final K k, final int hc) {
444 if (ct.nonReadOnly()) {
445 clean(parent, ct, lev - 5);
446 return RESTART; // used to be throw RestartException
448 if (tn.hc == hc && equal(tn.k, k, ct)) {
457 * Removes the key associated with the given value.
460 * if null, will remove the key irregardless of the value;
461 * otherwise removes only if binding contains that exact key
463 * @return null if not successful, an Option[V] indicating the previous
466 Option<V> rec_remove(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
467 final Gen startgen, final TrieMap<K, V> ct) {
468 MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
470 if (m instanceof CNode) {
471 CNode<K, V> cn = (CNode<K, V>) m;
472 int idx = (hc >>> lev) & 0x1f;
475 if ((bmp & flag) == 0) {
476 return Option.makeOption();
478 int pos = Integer.bitCount(bmp & (flag - 1));
479 BasicNode sub = cn.array [pos];
480 Option<V> res = null;
481 if (sub instanceof INode) {
482 INode<K, V> in = (INode<K, V>) sub;
483 if (startgen == in.gen) {
484 res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
486 if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
487 res = rec_remove(k, v, hc, lev, parent, startgen, ct);
493 } else if (sub instanceof SNode) {
494 SNode<K, V> sn = (SNode<K, V>) sub;
495 if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || v.equals(sn.v))) {
496 MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
497 if (GCAS(cn, ncn, ct)) {
498 res = Option.makeOption(sn.v);
503 res = Option.makeOption ();
507 if (res instanceof None || (res == null)) {
510 if (parent != null) { // never tomb at root
511 MainNode<K, V> n = GCAS_READ(ct);
512 if (n instanceof TNode) {
513 cleanParent(n, parent, ct, hc, lev, startgen);
520 } else if (m instanceof TNode) {
521 clean(parent, ct, lev - 5);
523 } else if (m instanceof LNode) {
524 LNode<K, V> ln = (LNode<K, V>) m;
526 Option<V> optv = ln.get(k);
527 MainNode<K, V> nn = ln.removed(k, ct);
528 if (GCAS (ln, nn, ct)) {
534 Option<V> tmp = ln.get(k);
535 if (tmp instanceof Some) {
536 Some<V> tmp1 = (Some<V>) tmp;
537 if (tmp1.get () == v) {
538 MainNode<K, V> nn = ln.removed(k, ct);
539 if (GCAS(ln, nn, ct)) {
548 throw new RuntimeException ("Should not happen");
551 void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
552 final int lev, final Gen startgen) {
554 MainNode<K, V> pm = parent.GCAS_READ(ct);
555 if (pm instanceof CNode) {
556 CNode<K, V> cn = (CNode<K, V>) pm;
557 int idx = (hc >>> (lev - 5)) & 0x1f;
560 if ((bmp & flag) == 0) {
561 // somebody already removed this i-node, we're done
563 int pos = Integer.bitCount(bmp & (flag - 1));
564 BasicNode sub = cn.array[pos];
566 if (nonlive instanceof TNode) {
567 TNode<K, V> tn = (TNode<K, V>) nonlive;
568 MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed (), gen).toContracted (lev - 5);
569 if (!parent.GCAS(cn, ncn, ct)) {
570 if (ct.readRoot().gen == startgen) {
571 // cleanParent (nonlive, parent, ct, hc,
581 // parent is no longer a cnode, we're done
587 private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
588 MainNode<K, V> m = nd.GCAS_READ(ct);
589 if (m instanceof CNode) {
590 CNode<K, V> cn = (CNode<K, V>) m;
591 nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
595 boolean isNullInode(final TrieMap<K, V> ct) {
596 return GCAS_READ(ct) == null;
599 int cachedSize(final TrieMap<K, V> ct) {
600 MainNode<K, V> m = GCAS_READ(ct);
601 return m.cachedSize(ct);
604 // /* this is a quiescent method! */
605 // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
607 // case null => "<null>"
608 // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
610 // case cn: CNode[_, _] => cn.string(lev)
611 // case ln: LNode[_, _] => ln.string(lev)
612 // case x => "<elem: %s>".format(x)
616 String string(final int lev) {