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 ();
23 * Virtual result for lookup methods indicating that the lookup needs to be restarted. This is a faster version
24 * of throwing a checked exception to control the restart.
26 static final Object RESTART = new Object();
28 static <K,V> INode<K,V> newRootNode() {
30 CNode<K, V> cn = new CNode<> (0, new BasicNode[] {}, gen);
31 return new INode<>(gen, cn);
34 INode(final Gen gen, final MainNode<K, V> bn) {
38 MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
42 MainNode<K, V> GCAS_READ(final TrieMap<K, V> ct) {
43 MainNode<K, V> m = /* READ */ READ();
44 MainNode<K, V> prevval = /* READ */ m.READ_PREV();
45 if (prevval == null) {
48 return GCAS_Complete(m, ct);
52 private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<K, V> ct) {
58 MainNode<K, V> prev = /* READ */ m.READ_PREV();
59 INode<K, V> ctr = ct.readRoot(true);
65 if (prev instanceof FailedNode) {
66 // try to commit to previous value
67 FailedNode<K, V> fn = (FailedNode<K, V>) prev;
68 if (CAS(m, fn.READ_PREV())) {
69 return fn.READ_PREV();
72 // return GCAS_Complete (/* READ */mainnode, ct);
73 m = /* READ */ READ();
76 } else if (prev instanceof MainNode) {
77 // Assume that you've read the root from the generation
79 // Assume that the snapshot algorithm is correct.
80 // ==> you can only reach nodes in generations <= G.
82 // We know that `ctr.gen` is >= G.
83 // ==> if `ctr.gen` = `gen` then they are both equal to
85 // ==> otherwise, we know that either `ctr.gen` > G,
89 if ((ctr.gen == gen) && ct.nonReadOnly()) {
91 if (m.CAS_PREV(prev, null)) {
94 // return GCAS_Complete (m, ct);
100 m.CAS_PREV(prev, new FailedNode<>(prev));
101 return GCAS_Complete(/* READ */ READ(), ct);
105 throw new RuntimeException ("Should not happen");
109 boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
112 GCAS_Complete (n, ct);
113 return /* READ */ n.READ_PREV() == null;
119 private boolean equal(final K k1, final K k2, final TrieMap<K, V> ct) {
120 return ct.equality().equiv(k1, k2);
123 private INode<K, V> inode(final MainNode<K, V> cn) {
124 return new INode<>(gen, cn);
127 INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
128 return new INode<>(ngen, GCAS_READ(ct));
132 * Inserts a key value pair, overwriting the old pair if the keys match.
134 * @return true if successful, false otherwise
136 boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
137 final TrieMap<K, V> ct) {
139 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
141 if (m instanceof CNode) {
142 // 1) a multiway node
143 CNode<K, V> cn = (CNode<K, V>) m;
144 int idx = (hc >>> lev) & 0x1f;
148 int pos = Integer.bitCount(bmp & mask);
149 if ((bmp & flag) != 0) {
151 BasicNode cnAtPos = cn.array[pos];
152 if (cnAtPos instanceof INode) {
153 INode<K, V> in = (INode<K, V>) cnAtPos;
154 if (startgen == in.gen) {
155 return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
157 if (GCAS (cn, cn.renewed(startgen, ct), ct)) {
158 // return rec_insert (k, v, hc, lev, parent,
166 } else if (cnAtPos instanceof SNode) {
167 SNode<K, V> sn = (SNode<K, V>) cnAtPos;
168 if (sn.hc == hc && equal(sn.k, k, ct)) {
169 return GCAS (cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
171 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
172 MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
173 hc, lev + 5, gen)), gen);
174 return GCAS (cn, nn, ct);
178 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
179 MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<> (k, v, hc), gen);
180 return GCAS (cn, ncnode, ct);
182 } else if (m instanceof TNode) {
183 clean(parent, ct, lev - 5);
185 } else if (m instanceof LNode) {
186 LNode<K, V> ln = (LNode<K, V>) m;
187 MainNode<K, V> nn = ln.inserted(k, v);
188 return GCAS(ln, nn, ct);
191 throw new RuntimeException ("Should not happen");
196 * Inserts a new key value pair, given that a specific condition is met.
199 * null - don't care if the key was there
200 * KEY_ABSENT - key wasn't there
201 * KEY_PRESENT - key was there
202 * other value `v` - key must be bound to `v`
203 * @return null if unsuccessful, Option[V] otherwise (indicating
204 * previous value bound to the key)
206 Option<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
207 final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
209 MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
211 if (m instanceof CNode) {
212 // 1) a multiway node
213 CNode<K, V> cn = (CNode<K, V>) m;
214 int idx = (hc >>> lev) & 0x1f;
218 int pos = Integer.bitCount(bmp & mask);
220 if ((bmp & flag) != 0) {
222 BasicNode cnAtPos = cn.array [pos];
223 if (cnAtPos instanceof INode) {
224 INode<K, V> in = (INode<K, V>) cnAtPos;
225 if (startgen == in.gen) {
226 return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
228 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
229 // return rec_insertif (k, v, hc, cond, lev,
230 // parent, startgen, ct);
237 } else if (cnAtPos instanceof SNode) {
238 SNode<K, V> sn = (SNode<K, V>) cnAtPos;
240 if (sn.hc == hc && equal(sn.k, k, ct)) {
241 if (GCAS(cn, cn.updatedAt(pos, new SNode<> (k, v, hc), gen), ct)) {
242 return Option.makeOption(sn.v);
247 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
248 MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
249 new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
250 if (GCAS(cn, nn, ct)) {
251 return Option.makeOption(); // None;
257 } else if (cond == INode.KEY_ABSENT) {
258 if (sn.hc == hc && equal (sn.k, k, ct)) {
259 return Option.makeOption(sn.v);
261 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
262 MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
263 new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
264 if (GCAS(cn, nn, ct)) {
265 return Option.makeOption(); // None
270 } else if (cond == INode.KEY_PRESENT) {
271 if (sn.hc == hc && equal (sn.k, k, ct)) {
272 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
273 return Option.makeOption(sn.v);
280 return Option.makeOption();// None;
283 if (sn.hc == hc && equal (sn.k, k, ct) && sn.v == cond) {
284 if (GCAS(cn, cn.updatedAt (pos, new SNode<>(k, v, hc), gen), ct)) {
285 return Option.makeOption(sn.v);
291 return Option.makeOption(); // None
296 } else if (cond == null || cond == INode.KEY_ABSENT) {
297 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
298 CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
299 if (GCAS(cn, ncnode, ct)) {
300 return Option.makeOption(); // None
304 } else if (cond == INode.KEY_PRESENT) {
305 return Option.makeOption(); // None;
308 return Option.makeOption(); // None
310 } else if (m instanceof TNode) {
311 clean(parent, ct, lev - 5);
313 } else if (m instanceof LNode) {
315 LNode<K, V> ln = (LNode<K, V>) m;
317 Option<V> optv = ln.get(k);
318 if (insertln(ln, k, v, ct)) {
323 } else if (cond == INode.KEY_ABSENT) {
324 Option<V> t = ln.get(k);
326 if (insertln(ln, k, v, ct)) {
327 return Option.makeOption();// None
334 } else if (cond == INode.KEY_PRESENT) {
335 Option<V> t = ln.get(k);
337 if (insertln(ln, k, v, ct)) {
346 Option<V> t = ln.get (k);
348 if (((Some<V>) t).get() == cond) {
349 if (insertln(ln, k, v, ct)) {
350 return new Some<>((V) cond);
355 return Option.makeOption ();
361 // throw new RuntimeException ("Should not happen");
365 boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
366 LNode<K, V> nn = ln.inserted (k, v);
367 return GCAS (ln, nn, ct);
371 * Looks up the value associated with the key.
373 * @return null if no value has been found, RESTART if the operation
374 * wasn't successful, or any other value otherwise
376 Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
377 final TrieMap<K, V> ct) {
379 MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
381 if (m instanceof CNode) {
383 final CNode<K, V> cn = (CNode<K, V>) m;
384 int idx = (hc >>> lev) & 0x1f;
387 if ((bmp & flag) == 0) {
388 return null; // 1a) bitmap shows no binding
389 } else { // 1b) bitmap contains a value - descend
390 int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
391 final BasicNode sub = cn.array[pos];
392 if (sub instanceof INode) {
393 INode<K, V> in = (INode<K, V>) sub;
394 if (ct.isReadOnly() || (startgen == ((INodeBase<K, V>) sub).gen)) {
395 return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
397 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
398 // return rec_lookup (k, hc, lev, parent,
403 return RESTART; // used to be throw RestartException
406 } else if (sub instanceof SNode) {
408 SNode<K, V> sn = (SNode<K, V>) sub;
409 if (((SNode) sub).hc == hc && equal (sn.k, k, ct)) {
416 } else if (m instanceof TNode) {
418 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
419 } else if (m instanceof LNode) {
421 Option<V> tmp = ((LNode<K, V>) m).get (k);
422 return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
425 throw new RuntimeException ("Should not happen");
429 private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
430 final TrieMap<K, V> ct, final K k, final int hc) {
431 if (ct.nonReadOnly()) {
432 clean(parent, ct, lev - 5);
433 return RESTART; // used to be throw RestartException
435 if (tn.hc == hc && equal(tn.k, k, ct)) {
444 * Removes the key associated with the given value.
447 * if null, will remove the key irregardless of the value;
448 * otherwise removes only if binding contains that exact key
450 * @return null if not successful, an Option[V] indicating the previous
453 Option<V> rec_remove(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
454 final Gen startgen, final TrieMap<K, V> ct) {
455 MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
457 if (m instanceof CNode) {
458 CNode<K, V> cn = (CNode<K, V>) m;
459 int idx = (hc >>> lev) & 0x1f;
462 if ((bmp & flag) == 0) {
463 return Option.makeOption();
465 int pos = Integer.bitCount(bmp & (flag - 1));
466 BasicNode sub = cn.array [pos];
467 Option<V> res = null;
468 if (sub instanceof INode) {
469 INode<K, V> in = (INode<K, V>) sub;
470 if (startgen == in.gen) {
471 res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
473 if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
474 res = rec_remove(k, v, hc, lev, parent, startgen, ct);
480 } else if (sub instanceof SNode) {
481 SNode<K, V> sn = (SNode<K, V>) sub;
482 if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || v.equals(sn.v))) {
483 MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
484 if (GCAS(cn, ncn, ct)) {
485 res = Option.makeOption(sn.v);
490 res = Option.makeOption ();
494 if (res instanceof None || (res == null)) {
497 if (parent != null) { // never tomb at root
498 MainNode<K, V> n = GCAS_READ(ct);
499 if (n instanceof TNode) {
500 cleanParent(n, parent, ct, hc, lev, startgen);
507 } else if (m instanceof TNode) {
508 clean(parent, ct, lev - 5);
510 } else if (m instanceof LNode) {
511 LNode<K, V> ln = (LNode<K, V>) m;
513 Option<V> optv = ln.get(k);
514 MainNode<K, V> nn = ln.removed(k, ct);
515 if (GCAS (ln, nn, ct)) {
521 Option<V> tmp = ln.get(k);
522 if (tmp instanceof Some) {
523 Some<V> tmp1 = (Some<V>) tmp;
524 if (tmp1.get () == v) {
525 MainNode<K, V> nn = ln.removed(k, ct);
526 if (GCAS(ln, nn, ct)) {
535 throw new RuntimeException ("Should not happen");
538 void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
539 final int lev, final Gen startgen) {
541 MainNode<K, V> pm = parent.GCAS_READ(ct);
542 if (pm instanceof CNode) {
543 CNode<K, V> cn = (CNode<K, V>) pm;
544 int idx = (hc >>> (lev - 5)) & 0x1f;
547 if ((bmp & flag) == 0) {
548 // somebody already removed this i-node, we're done
550 int pos = Integer.bitCount(bmp & (flag - 1));
551 BasicNode sub = cn.array[pos];
553 if (nonlive instanceof TNode) {
554 TNode<K, V> tn = (TNode<K, V>) nonlive;
555 MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed (), gen).toContracted (lev - 5);
556 if (!parent.GCAS(cn, ncn, ct)) {
557 if (ct.readRoot().gen == startgen) {
558 // cleanParent (nonlive, parent, ct, hc,
568 // parent is no longer a cnode, we're done
574 private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
575 MainNode<K, V> m = nd.GCAS_READ(ct);
576 if (m instanceof CNode) {
577 CNode<K, V> cn = (CNode<K, V>) m;
578 nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
582 boolean isNullInode(final TrieMap<K, V> ct) {
583 return GCAS_READ(ct) == null;
586 int cachedSize(final TrieMap<K, V> ct) {
587 MainNode<K, V> m = GCAS_READ(ct);
588 return m.cachedSize(ct);
591 // /* this is a quiescent method! */
592 // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
594 // case null => "<null>"
595 // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
597 // case cn: CNode[_, _] => cn.string(lev)
598 // case ln: LNode[_, _] => ln.string(lev)
599 // case x => "<elem: %s>".format(x)
603 String string(final int lev) {