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 static org.opendaylight.yangtools.triemap.Constants.LEVEL_BITS;
19 import static org.opendaylight.yangtools.triemap.LookupResult.RESTART;
20 import static org.opendaylight.yangtools.triemap.PresencePredicate.ABSENT;
21 import static org.opendaylight.yangtools.triemap.PresencePredicate.PRESENT;
23 import com.google.common.base.VerifyException;
24 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
25 import java.util.Optional;
26 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
28 final class INode<K, V> extends BasicNode {
29 @SuppressWarnings("rawtypes")
30 private static final AtomicReferenceFieldUpdater<INode, MainNode> MAINNODE_UPDATER =
31 AtomicReferenceFieldUpdater.newUpdater(INode.class, MainNode.class, "mainnode");
33 private final Gen gen;
35 private volatile MainNode<K, V> mainnode;
37 INode(final Gen gen, final MainNode<K, V> mainnode) {
39 this.mainnode = mainnode;
42 MainNode<K, V> gcasRead(final TrieMap<?, ?> ct) {
46 private MainNode<K, V> GCAS_READ(final TrieMap<?, ?> ct) {
47 MainNode<K, V> m = /* READ */ mainnode;
48 MainNode<K, V> prevval = /* READ */ m.READ_PREV();
49 if (prevval == null) {
53 return GCAS_Complete(m, ct);
56 private MainNode<K, V> GCAS_Complete(final MainNode<K, V> oldmain, final TrieMap<?, ?> ct) {
57 MainNode<K, V> m = oldmain;
60 final MainNode<K, V> prev = /* READ */ m.READ_PREV();
61 final INode<?, ?> ctr = ct.readRoot(true);
66 if (prev instanceof FailedNode) {
67 // try to commit to previous value
68 FailedNode<K, V> fn = (FailedNode<K, V>) prev;
69 if (MAINNODE_UPDATER.compareAndSet(this, m, fn.READ_PREV())) {
70 return fn.READ_PREV();
73 // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
74 m = /* READ */ mainnode;
78 // Assume that you've read the root from the generation G.
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 G.
84 // ==> otherwise, we know that either `ctr.gen` > G, `gen` < G,
86 if (ctr.gen == gen && !ct.isReadOnly()) {
88 if (m.CAS_PREV(prev, null)) {
92 // Tail recursion: return GCAS_Complete(m, ct);
97 m.CAS_PREV(prev, new FailedNode<>(prev));
99 // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
100 m = /* READ */ mainnode;
106 private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<?, ?> ct) {
108 if (MAINNODE_UPDATER.compareAndSet(this, old, n)) {
109 GCAS_Complete(n, ct);
110 return /* READ */ n.READ_PREV() == null;
116 private INode<K, V> inode(final MainNode<K, V> cn) {
117 return new INode<>(gen, cn);
120 INode<K, V> copyToGen(final Gen ngen, final TrieMap<?, ?> ct) {
121 return new INode<>(ngen, GCAS_READ(ct));
125 * Inserts a key value pair, overwriting the old pair if the keys match.
127 * @return true if successful, false otherwise
129 boolean rec_insert(final K key, final V value, final int hc, final int lev, final INode<K, V> parent,
130 final TrieMap<K, V> ct) {
131 return rec_insert(key, value, hc, lev, parent, gen, ct);
134 private boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
135 final Gen startgen, final TrieMap<K, V> ct) {
137 final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
139 if (m instanceof CNode) {
140 // 1) a multiway node
141 final CNode<K, V> cn = (CNode<K, V>) m;
142 final int idx = (hc >>> lev) & 0x1f;
143 final int flag = 1 << idx;
144 final int bmp = cn.bitmap;
145 final int mask = flag - 1;
146 final int pos = Integer.bitCount(bmp & mask);
148 if ((bmp & flag) != 0) {
150 final BasicNode cnAtPos = cn.array[pos];
151 if (cnAtPos instanceof INode) {
152 final INode<K, V> in = (INode<K, V>) cnAtPos;
153 if (startgen == in.gen) {
154 return in.rec_insert(k, v, hc, lev + LEVEL_BITS, this, startgen, ct);
156 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
157 // Tail recursion: return rec_insert(k, v, hc, lev, parent, startgen, ct);
162 } else if (cnAtPos instanceof SNode) {
163 final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
164 if (sn.hc == hc && ct.equal(sn.key, k)) {
165 return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
168 final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
169 final MainNode<K, V> nn = rn.updatedAt(pos, inode(
170 CNode.dual(sn, k, v, hc, lev + LEVEL_BITS, gen)), gen);
171 return GCAS(cn, nn, ct);
173 throw CNode.invalidElement(cnAtPos);
177 final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
178 final MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
179 return GCAS(cn, ncnode, ct);
180 } else if (m instanceof TNode) {
181 clean(parent, ct, lev - LEVEL_BITS);
183 } else if (m instanceof LNode) {
184 final LNode<K, V> ln = (LNode<K, V>) m;
185 final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
186 return entry != null ? replaceln(ln, entry, v, ct) : insertln(ln, k, v, ct);
188 throw invalidElement(m);
193 private static VerifyException invalidElement(final BasicNode elem) {
194 throw new VerifyException("An INode can host only a CNode, a TNode or an LNode, not " + elem);
197 @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
198 justification = "Returning null Optional indicates the need to restart.")
199 private Optional<V> insertDual(final TrieMap<K, V> ct, final CNode<K, V> cn, final int pos, final SNode<K, V> sn,
200 final K k, final V v, final int hc, final int lev) {
201 final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
202 final MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, k, v, hc, lev + LEVEL_BITS, gen)), gen);
203 return GCAS(cn, nn, ct) ? Optional.empty() : null;
207 * Inserts a new key value pair, given that a specific condition is met.
210 * null - don't care if the key was there
211 * KEY_ABSENT - key wasn't there
212 * KEY_PRESENT - key was there
213 * other value `v` - key must be bound to `v`
214 * @return null if unsuccessful, Option[V] otherwise (indicating
215 * previous value bound to the key)
217 Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
218 final INode<K, V> parent, final TrieMap<K, V> ct) {
219 return rec_insertif(k, v, hc, cond, lev, parent, gen, ct);
222 @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
223 justification = "Returning null Optional indicates the need to restart.")
224 private Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
225 final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
227 final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
229 if (m instanceof CNode) {
230 // 1) a multiway node
231 final CNode<K, V> cn = (CNode<K, V>) m;
232 final int idx = (hc >>> lev) & 0x1f;
233 final int flag = 1 << idx;
234 final int bmp = cn.bitmap;
235 final int mask = flag - 1;
236 final int pos = Integer.bitCount(bmp & mask);
238 if ((bmp & flag) != 0) {
240 final BasicNode cnAtPos = cn.array[pos];
241 if (cnAtPos instanceof INode) {
242 final INode<K, V> in = (INode<K, V>) cnAtPos;
243 if (startgen == in.gen) {
244 return in.rec_insertif(k, v, hc, cond, lev + LEVEL_BITS, this, startgen, ct);
247 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
248 // Tail recursion: return rec_insertif(k, v, hc, cond, lev, parent, startgen, ct);
253 } else if (cnAtPos instanceof SNode) {
254 final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
256 if (sn.hc == hc && ct.equal(sn.key, k)) {
257 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
258 return Optional.of(sn.value);
264 return insertDual(ct, cn, pos, sn, k, v, hc, lev);
265 } else if (cond == ABSENT) {
266 if (sn.hc == hc && ct.equal(sn.key, k)) {
267 return Optional.of(sn.value);
270 return insertDual(ct, cn, pos, sn, k, v, hc, lev);
271 } else if (cond == PRESENT) {
272 if (sn.hc == hc && ct.equal(sn.key, k)) {
273 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
274 return Optional.of(sn.value);
279 return Optional.empty();
281 if (sn.hc == hc && ct.equal(sn.key, k) && cond.equals(sn.value)) {
282 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
283 return Optional.of(sn.value);
289 return Optional.empty();
292 throw CNode.invalidElement(cnAtPos);
294 } else if (cond == null || cond == ABSENT) {
295 final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
296 final CNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
297 if (GCAS(cn, ncnode, ct)) {
298 return Optional.empty();
303 return Optional.empty();
305 } else if (m instanceof TNode) {
306 clean(parent, ct, lev - LEVEL_BITS);
308 } else if (m instanceof LNode) {
310 final LNode<K, V> ln = (LNode<K, V>) m;
311 final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
315 return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null;
318 return insertln(ln, k, v, ct) ? Optional.empty() : null;
319 } else if (cond == ABSENT) {
321 return Optional.of(entry.getValue());
324 return insertln(ln, k, v, ct) ? Optional.empty() : null;
325 } else if (cond == PRESENT) {
327 return Optional.empty();
330 return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null;
332 if (entry == null || !cond.equals(entry.getValue())) {
333 return Optional.empty();
336 return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null;
339 throw invalidElement(m);
344 private boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
345 return GCAS(ln, ln.insertChild(k, v), ct);
348 private boolean replaceln(final LNode<K, V> ln, final LNodeEntry<K, V> entry, final V v, final TrieMap<K, V> ct) {
349 return GCAS(ln, ln.replaceChild(entry, v), ct);
353 * Looks up the value associated with the key.
355 * @return null if no value has been found, RESTART if the operation
356 * wasn't successful, or any other value otherwise
358 Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct) {
359 return rec_lookup(k, hc, lev, parent, gen, ct);
362 private Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
363 final TrieMap<K, V> ct) {
365 final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
367 if (m instanceof CNode) {
369 final CNode<K, V> cn = (CNode<K, V>) m;
370 final int idx = (hc >>> lev) & 0x1f;
371 final int flag = 1 << idx;
372 final int bmp = cn.bitmap;
374 if ((bmp & flag) == 0) {
375 // 1a) bitmap shows no binding
379 // 1b) bitmap contains a value - descend
380 final int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
381 final BasicNode sub = cn.array[pos];
382 if (sub instanceof INode) {
383 final INode<K, V> in = (INode<K, V>) sub;
384 if (ct.isReadOnly() || (startgen == in.gen)) {
385 return in.rec_lookup(k, hc, lev + LEVEL_BITS, this, startgen, ct);
388 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
389 // Tail recursion: return rec_lookup(k, hc, lev, parent, startgen, ct);
394 } else if (sub instanceof SNode) {
396 final SNode<K, V> sn = (SNode<K, V>) sub;
397 if (sn.hc == hc && ct.equal(sn.key, k)) {
403 throw CNode.invalidElement(sub);
405 } else if (m instanceof TNode) {
407 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
408 } else if (m instanceof LNode) {
410 final LNodeEntry<K, V> entry = ((LNode<K, V>) m).get(ct.equiv(), k);
411 return entry != null ? entry.getValue() : null;
413 throw invalidElement(m);
418 private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
419 final TrieMap<K, V> ct, final K k, final int hc) {
420 if (ct.isReadOnly()) {
421 if (tn.hc == hc && ct.equal(tn.key, k)) {
428 clean(parent, ct, lev - LEVEL_BITS);
433 * Removes the key associated with the given value.
436 * if null, will remove the key regardless of the value;
437 * otherwise removes only if binding contains that exact key
439 * @return null if not successful, an Optional indicating the previous
442 Optional<V> rec_remove(final K k, final Object cond, final int hc, final int lev, final INode<K, V> parent,
443 final TrieMap<K, V> ct) {
444 return rec_remove(k, cond, hc, lev, parent, gen, ct);
447 @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
448 justification = "Returning null Optional indicates the need to restart.")
449 private Optional<V> rec_remove(final K k, final Object cond, final int hc, final int lev, final INode<K, V> parent,
450 final Gen startgen, final TrieMap<K, V> ct) {
451 final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
453 if (m instanceof CNode) {
454 final CNode<K, V> cn = (CNode<K, V>) m;
455 final int idx = (hc >>> lev) & 0x1f;
456 final int bmp = cn.bitmap;
457 final int flag = 1 << idx;
458 if ((bmp & flag) == 0) {
459 return Optional.empty();
462 final int pos = Integer.bitCount(bmp & (flag - 1));
463 final BasicNode sub = cn.array[pos];
464 final Optional<V> res;
465 if (sub instanceof INode) {
466 final INode<K, V> in = (INode<K, V>) sub;
467 if (startgen == in.gen) {
468 res = in.rec_remove(k, cond, hc, lev + LEVEL_BITS, this, startgen, ct);
470 if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
471 res = rec_remove(k, cond, hc, lev, parent, startgen, ct);
476 } else if (sub instanceof SNode) {
477 final SNode<K, V> sn = (SNode<K, V>) sub;
478 if (sn.hc == hc && ct.equal(sn.key, k) && (cond == null || cond.equals(sn.value))) {
479 final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
480 if (GCAS(cn, ncn, ct)) {
481 res = Optional.of(sn.value);
486 res = Optional.empty();
489 throw CNode.invalidElement(sub);
492 if (res == null || !res.isPresent()) {
496 if (parent != null) {
497 // never tomb at root
498 final MainNode<K, V> n = GCAS_READ(ct);
499 if (n instanceof TNode) {
500 cleanParent(n, parent, ct, hc, lev, startgen);
505 } else if (m instanceof TNode) {
506 clean(parent, ct, lev - LEVEL_BITS);
508 } else if (m instanceof LNode) {
509 final LNode<K, V> ln = (LNode<K, V>) m;
510 final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
512 // Key was not found, hence no modification is needed
513 return Optional.empty();
516 final V value = entry.getValue();
517 if (cond != null && !cond.equals(value)) {
518 // Value does not match
519 return Optional.empty();
522 return GCAS(ln, ln.removeChild(entry, hc), ct) ? Optional.of(value) : null;
524 throw invalidElement(m);
528 private void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
529 final int lev, final Gen startgen) {
531 final MainNode<K, V> pm = parent.GCAS_READ(ct);
532 if ((!(pm instanceof CNode))) {
533 // parent is no longer a cnode, we're done
537 final CNode<K, V> cn = (CNode<K, V>) pm;
538 final int idx = (hc >>> (lev - LEVEL_BITS)) & 0x1f;
539 final int bmp = cn.bitmap;
540 final int flag = 1 << idx;
541 if ((bmp & flag) == 0) {
542 // somebody already removed this i-node, we're done
546 final int pos = Integer.bitCount(bmp & (flag - 1));
547 final BasicNode sub = cn.array[pos];
549 if (nonlive instanceof TNode) {
550 final TNode<?, ?> tn = (TNode<?, ?>) nonlive;
551 final MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - LEVEL_BITS);
552 if (!parent.GCAS(cn, ncn, ct)) {
553 if (ct.readRoot().gen == startgen) {
554 // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
564 private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
565 final MainNode<K, V> m = nd.GCAS_READ(ct);
566 if (m instanceof CNode) {
567 final CNode<K, V> cn = (CNode<K, V>) m;
568 nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
572 int size(final ImmutableTrieMap<?, ?> ct) {
573 return GCAS_READ(ct).size(ct);
576 // /* this is a quiescent method! */
577 // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
579 // case null => "<null>"
580 // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
582 // case cn: CNode[_, _] => cn.string(lev)
583 // case ln: LNode[_, _] => ln.string(lev)
584 // case x => "<elem: %s>".format(x)
588 String string(final int lev) {