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 import java.util.Optional;
20 final class INode<K, V> extends INodeBase<K, V> {
21 static final Object KEY_PRESENT = new Object ();
22 static final Object KEY_ABSENT = new Object ();
25 * Virtual result for lookup methods indicating that the lookup needs to be restarted. This is a faster version
26 * of throwing a checked exception to control the restart.
28 static final Object RESTART = new Object();
30 INode(final Gen gen, final MainNode<K, V> bn) {
34 MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
38 MainNode<K, V> GCAS_READ(final TrieMap<K, V> ct) {
39 MainNode<K, V> m = /* READ */ READ();
40 MainNode<K, V> prevval = /* READ */ m.READ_PREV();
41 if (prevval == null) {
45 return GCAS_Complete(m, ct);
48 private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<K, V> ct) {
55 final MainNode<K, V> prev = /* READ */ m.READ_PREV();
56 final INode<K, V> ctr = ct.readRoot(true);
61 if (prev instanceof FailedNode) {
62 // try to commit to previous value
63 FailedNode<K, V> fn = (FailedNode<K, V>) prev;
64 if (CAS(m, fn.READ_PREV())) {
65 return fn.READ_PREV();
68 // Tail recursion: return GCAS_Complete (/* READ */ READ(), ct);
69 m = /* READ */ READ();
73 // Assume that you've read the root from the generation G.
74 // Assume that the snapshot algorithm is correct.
75 // ==> you can only reach nodes in generations <= G.
77 // We know that `ctr.gen` is >= G.
78 // ==> if `ctr.gen` = `gen` then they are both equal to G.
79 // ==> otherwise, we know that either `ctr.gen` > G, `gen` < G,
81 if ((ctr.gen == gen) && ct.nonReadOnly()) {
83 if (m.CAS_PREV(prev, null)) {
87 // Tail recursion: return GCAS_Complete (m, ct);
92 m.CAS_PREV(prev, new FailedNode<>(prev));
94 // Tail recursion: return GCAS_Complete(/* READ */ READ(), ct);
95 m = /* READ */ READ();
99 private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
102 GCAS_Complete(n, ct);
103 return /* READ */ n.READ_PREV() == null;
109 private INode<K, V> inode(final MainNode<K, V> cn) {
110 return new INode<>(gen, cn);
113 INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
114 return new INode<>(ngen, GCAS_READ(ct));
118 * Inserts a key value pair, overwriting the old pair if the keys match.
120 * @return true if successful, false otherwise
122 boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
123 final TrieMap<K, V> ct) {
125 final MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
127 if (m instanceof CNode) {
128 // 1) a multiway node
129 final CNode<K, V> cn = (CNode<K, V>) m;
130 final int idx = (hc >>> lev) & 0x1f;
131 final int flag = 1 << idx;
132 final int bmp = cn.bitmap;
133 final int mask = flag - 1;
134 final int pos = Integer.bitCount(bmp & mask);
135 if ((bmp & flag) != 0) {
137 final BasicNode cnAtPos = cn.array[pos];
138 if (cnAtPos instanceof INode) {
139 final INode<K, V> in = (INode<K, V>) cnAtPos;
140 if (startgen == in.gen) {
141 return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
143 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
144 // Tail recursion: return rec_insert (k, v, hc, lev, parent, startgen, ct);
149 } else if (cnAtPos instanceof SNode) {
150 final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
151 if (sn.hc == hc && ct.equal(sn.k, k)) {
152 return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
155 final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
156 final MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
157 hc, lev + 5, gen)), gen);
158 return GCAS (cn, nn, ct);
161 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
162 MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<> (k, v, hc), gen);
163 return GCAS (cn, ncnode, ct);
165 } else if (m instanceof TNode) {
166 clean(parent, ct, lev - 5);
168 } else if (m instanceof LNode) {
169 LNode<K, V> ln = (LNode<K, V>) m;
170 MainNode<K, V> nn = ln.inserted(k, v);
171 return GCAS(ln, nn, ct);
173 throw new IllegalStateException("Unhandled node " + m);
176 throw new RuntimeException ("Should not happen");
181 * Inserts a new key value pair, given that a specific condition is met.
184 * null - don't care if the key was there
185 * KEY_ABSENT - key wasn't there
186 * KEY_PRESENT - key was there
187 * other value `v` - key must be bound to `v`
188 * @return null if unsuccessful, Option[V] otherwise (indicating
189 * previous value bound to the key)
191 Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
192 final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
194 final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
196 if (m instanceof CNode) {
197 // 1) a multiway node
198 final CNode<K, V> cn = (CNode<K, V>) m;
199 final int idx = (hc >>> lev) & 0x1f;
200 final int flag = 1 << idx;
201 final int bmp = cn.bitmap;
202 final int mask = flag - 1;
203 final int pos = Integer.bitCount(bmp & mask);
205 if ((bmp & flag) != 0) {
207 final BasicNode cnAtPos = cn.array[pos];
208 if (cnAtPos instanceof INode) {
209 final INode<K, V> in = (INode<K, V>) cnAtPos;
210 if (startgen == in.gen) {
211 return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
214 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
215 // Tail recursion: return rec_insertif (k, v, hc, cond, lev, parent, startgen, ct);
220 } else if (cnAtPos instanceof SNode) {
221 final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
223 if (sn.hc == hc && ct.equal(sn.k, k)) {
224 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
225 return Optional.of(sn.v);
231 final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
232 final MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
233 new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
234 if (GCAS(cn, nn, ct)) {
235 return Optional.empty();
239 } else if (cond == INode.KEY_ABSENT) {
240 if (sn.hc == hc && ct.equal(sn.k, k)) {
241 return Optional.of(sn.v);
244 final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
245 final MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
246 new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
247 if (GCAS(cn, nn, ct)) {
248 return Optional.empty();
252 } else if (cond == INode.KEY_PRESENT) {
253 if (sn.hc == hc && ct.equal(sn.k, k)) {
254 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
255 return Optional.of(sn.v);
260 return Optional.empty();
262 if (sn.hc == hc && ct.equal(sn.k, k) && cond.equals(sn.v)) {
263 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
264 return Optional.of(sn.v);
270 return Optional.empty();
273 } else if (cond == null || cond == INode.KEY_ABSENT) {
274 final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
275 final CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
276 if (GCAS(cn, ncnode, ct)) {
277 return Optional.empty();
281 } else if (cond == INode.KEY_PRESENT) {
282 return Optional.empty();
284 return Optional.empty();
286 } else if (m instanceof TNode) {
287 clean(parent, ct, lev - 5);
289 } else if (m instanceof LNode) {
291 final LNode<K, V> ln = (LNode<K, V>) m;
293 final Optional<V> optv = ln.get(k);
294 if (insertln(ln, k, v, ct)) {
298 } else if (cond == INode.KEY_ABSENT) {
299 final Optional<V> t = ln.get(k);
303 if (insertln(ln, k, v, ct)) {
304 return Optional.empty();
307 } else if (cond == INode.KEY_PRESENT) {
308 final Optional<V> t = ln.get(k);
309 if (!t.isPresent()) {
312 if (insertln(ln, k, v, ct)) {
317 final Optional<V> t = ln.get(k);
319 if (cond.equals(t.get())) {
320 if (insertln(ln, k, v, ct)) {
321 // Difference from Scala: we choose to reuse the object returned from LNode,
322 // as the identity of the value does not matter in this call graph.
330 return Optional.empty();
333 throw new IllegalStateException("Unhandled node " + m);
336 throw new RuntimeException("Should never happen");
340 boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
341 final LNode<K, V> nn = ln.inserted (k, v);
342 return GCAS(ln, nn, ct);
346 * Looks up the value associated with the key.
348 * @return null if no value has been found, RESTART if the operation
349 * wasn't successful, or any other value otherwise
351 Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
352 final TrieMap<K, V> ct) {
354 final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
356 if (m instanceof CNode) {
358 final CNode<K, V> cn = (CNode<K, V>) m;
359 final int idx = (hc >>> lev) & 0x1f;
360 final int flag = 1 << idx;
361 final int bmp = cn.bitmap;
362 if ((bmp & flag) == 0) {
363 // 1a) bitmap shows no binding
367 // 1b) bitmap contains a value - descend
368 final int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
369 final BasicNode sub = cn.array[pos];
370 if (sub instanceof INode) {
371 final INode<K, V> in = (INode<K, V>) sub;
372 if (ct.isReadOnly() || (startgen == in.gen)) {
373 return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
376 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
377 // Tail recursion: return rec_lookup(k, hc, lev, parent, startgen, ct);
381 // used to be throw RestartException
383 } else if (sub instanceof SNode) {
385 final SNode<K, V> sn = (SNode<K, V>) sub;
386 if (sn.hc == hc && ct.equal(sn.k, k)) {
392 } else if (m instanceof TNode) {
394 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
395 } else if (m instanceof LNode) {
397 return ((LNode<K, V>) m).get(k);
399 throw new IllegalStateException("Unhandled node " + m);
402 throw new RuntimeException ("Should not happen");
406 private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
407 final TrieMap<K, V> ct, final K k, final int hc) {
408 if (ct.nonReadOnly()) {
409 // used to be throw RestartException
410 clean(parent, ct, lev - 5);
414 if (tn.hc == hc && ct.equal(tn.k, k)) {
422 * Removes the key associated with the given value.
425 * if null, will remove the key regardless of the value;
426 * otherwise removes only if binding contains that exact key
428 * @return null if not successful, an Option[V] indicating the previous
431 Optional<V> rec_remove(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
432 final Gen startgen, final TrieMap<K, V> ct) {
433 final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
435 if (m instanceof CNode) {
436 final CNode<K, V> cn = (CNode<K, V>) m;
437 final int idx = (hc >>> lev) & 0x1f;
438 final int bmp = cn.bitmap;
439 final int flag = 1 << idx;
440 if ((bmp & flag) == 0) {
441 return Optional.empty();
444 final int pos = Integer.bitCount(bmp & (flag - 1));
445 final BasicNode sub = cn.array[pos];
446 Optional<V> res = null;
447 if (sub instanceof INode) {
448 final INode<K, V> in = (INode<K, V>) sub;
449 if (startgen == in.gen) {
450 res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
452 if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
453 res = rec_remove(k, v, hc, lev, parent, startgen, ct);
459 } else if (sub instanceof SNode) {
460 final SNode<K, V> sn = (SNode<K, V>) sub;
461 if (sn.hc == hc && ct.equal(sn.k, k) && (v == null || v.equals(sn.v))) {
462 final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
463 if (GCAS(cn, ncn, ct)) {
464 res = Optional.of(sn.v);
469 res = Optional.empty();
473 if (res == null || !res.isPresent()) {
477 if (parent != null) {
478 // never tomb at root
479 final MainNode<K, V> n = GCAS_READ(ct);
480 if (n instanceof TNode) {
481 cleanParent(n, parent, ct, hc, lev, startgen);
486 } else if (m instanceof TNode) {
487 clean(parent, ct, lev - 5);
489 } else if (m instanceof LNode) {
490 final LNode<K, V> ln = (LNode<K, V>) m;
492 final Optional<V> optv = ln.get(k);
493 final MainNode<K, V> nn = ln.removed(k, ct);
494 if (GCAS(ln, nn, ct)) {
501 final Optional<V> tmp = ln.get(k);
502 if (tmp.isPresent() && v.equals(tmp.get())) {
503 final MainNode<K, V> nn = ln.removed(k, ct);
504 if (GCAS(ln, nn, ct)) {
511 // Key not found or value does not match: we have not removed anything
512 return Optional.empty();
514 throw new IllegalStateException("Unhandled node " + m);
518 private void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
519 final int lev, final Gen startgen) {
521 final MainNode<K, V> pm = parent.GCAS_READ(ct);
522 if ((!(pm instanceof CNode))) {
523 // parent is no longer a cnode, we're done
527 final CNode<K, V> cn = (CNode<K, V>) pm;
528 final int idx = (hc >>> (lev - 5)) & 0x1f;
529 final int bmp = cn.bitmap;
530 final int flag = 1 << idx;
531 if ((bmp & flag) == 0) {
532 // somebody already removed this i-node, we're done
536 final int pos = Integer.bitCount(bmp & (flag - 1));
537 final BasicNode sub = cn.array[pos];
539 if (nonlive instanceof TNode) {
540 final TNode<K, V> tn = (TNode<K, V>) nonlive;
541 MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - 5);
542 if (!parent.GCAS(cn, ncn, ct)) {
543 if (ct.readRoot().gen == startgen) {
544 // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
554 private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
555 final MainNode<K, V> m = nd.GCAS_READ(ct);
556 if (m instanceof CNode) {
557 final CNode<K, V> cn = (CNode<K, V>) m;
558 nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
562 int cachedSize(final TrieMap<K, V> ct) {
563 MainNode<K, V> m = GCAS_READ(ct);
564 return m.cachedSize(ct);
567 // /* this is a quiescent method! */
568 // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
570 // case null => "<null>"
571 // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
573 // case cn: CNode[_, _] => cn.string(lev)
574 // case ln: LNode[_, _] => ln.string(lev)
575 // case x => "<elem: %s>".format(x)
579 String string(final int lev) {