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 CNode<K, V> extends CNodeBase<K, V> {
21 final BasicNode[] array;
24 CNode(final int bitmap, final BasicNode[] array, final Gen gen) {
30 // this should only be called from within read-only snapshots
32 int cachedSize(final TrieMap<K, V> ct) {
33 final int currsz = READ_SIZE();
38 final int sz = computeSize(ct);
39 while (READ_SIZE () == -1) {
45 // lends itself towards being parallelizable by choosing
46 // a random starting offset in the array
47 // => if there are concurrent size computations, they start
48 // at different positions, so they are more likely to
50 private int computeSize(final TrieMap<K, V> ct) {
53 // final int offset = (array.length > 0) ?
54 // // util.Random.nextInt(array.length) /* <-- benchmarks show that
55 // // this causes observable contention */
56 // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
61 while (i < array.length) {
62 int pos = (i + offset) % array.length;
63 BasicNode elem = array [pos];
64 if (elem instanceof SNode) {
66 } else if (elem instanceof INode) {
67 sz += ((INode<K, V>) elem).cachedSize (ct);
74 CNode<K, V> updatedAt(final int pos, final BasicNode nn, final Gen gen) {
75 int len = array.length;
76 BasicNode[] narr = new BasicNode[len];
77 System.arraycopy(array, 0, narr, 0, len);
79 return new CNode<>(bitmap, narr, gen);
82 CNode<K, V> removedAt(final int pos, final int flag, final Gen gen) {
83 BasicNode[] arr = array;
85 BasicNode[] narr = new BasicNode[len - 1];
86 System.arraycopy(arr, 0, narr, 0, pos);
87 System.arraycopy(arr, pos + 1, narr, pos, len - pos - 1);
88 return new CNode<>(bitmap ^ flag, narr, gen);
91 CNode<K, V> insertedAt(final int pos, final int flag, final BasicNode nn, final Gen gen) {
92 int len = array.length;
94 BasicNode[] narr = new BasicNode[len + 1];
95 System.arraycopy(array, 0, narr, 0, pos);
97 System.arraycopy(array, pos, narr, pos + 1, len - pos);
98 return new CNode<>(bmp | flag, narr, gen);
102 * Returns a copy of this cnode such that all the i-nodes below it are
103 * copied to the specified generation `ngen`.
105 CNode<K, V> renewed(final Gen ngen, final TrieMap<K, V> ct) {
107 BasicNode[] arr = array;
108 int len = arr.length;
109 BasicNode[] narr = new BasicNode[len];
111 BasicNode elem = arr[i];
112 if (elem instanceof INode) {
113 INode<K, V> in = (INode<K, V>) elem;
114 narr [i] = in.copyToGen(ngen, ct);
115 } else if (elem instanceof BasicNode) {
120 return new CNode<>(bitmap, narr, ngen);
123 private BasicNode resurrect(final INode<K, V> inode, final Object inodemain) {
124 if (inodemain instanceof TNode) {
125 TNode<K, V> tn = (TNode<K, V>) inodemain;
126 return tn.copyUntombed();
132 MainNode<K, V> toContracted(final int lev) {
133 if (array.length == 1 && lev > 0) {
134 if (array [0] instanceof SNode) {
135 SNode<K, V> sn = (SNode<K, V>) array[0];
136 return sn.copyTombed();
145 // - if the branching factor is 1 for this CNode, and the child
146 // is a tombed SNode, returns its tombed version
147 // - otherwise, if there is at least one non-null node below,
148 // returns the version of this node with at least some null-inodes
149 // removed (those existing when the op began)
150 // - if there are only null-i-nodes below, returns null
151 MainNode<K, V> toCompressed(final TrieMap<K, V> ct, final int lev, final Gen gen) {
154 BasicNode[] arr = array;
155 BasicNode[] tmparray = new BasicNode[arr.length];
156 while (i < arr.length) { // construct new bitmap
157 BasicNode sub = arr[i];
158 if (sub instanceof INode) {
159 INode<K, V> in = (INode<K, V>) sub;
160 MainNode<K, V> inodemain = in.gcasRead (ct);
161 assert (inodemain != null);
162 tmparray [i] = resurrect (in, inodemain);
163 } else if (sub instanceof SNode) {
169 return new CNode<K, V> (bmp, tmparray, gen).toContracted (lev);
173 String string(final int lev) {
174 // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
175 // 1)).mkString("\n"));
180 * quiescently consistent - don't call concurrently to anything
183 // protected Seq<K,V> collectElems() {
185 // case sn: SNode[K, V] => Some(sn.kvPair)
186 // case in: INode[K, V] => in.mainnode match {
187 // case tn: TNode[K, V] => Some(tn.kvPair)
188 // case ln: LNode[K, V] => ln.listmap.toList
189 // case cn: CNode[K, V] => cn.collectElems
194 // protected Seq<String> collectLocalElems() {
195 // // array flatMap {
196 // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
197 // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
204 public String toString () {
205 // val elems = collectLocalElems
206 // "CNode(sz: %d; %s)".format(elems.size,
207 // elems.sorted.mkString(", "))
211 static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
212 final int lev, final Gen gen) {
214 int xidx = (xhc >>> lev) & 0x1f;
215 int yidx = (yhc >>> lev) & 0x1f;
216 int bmp = (1 << xidx) | (1 << yidx);
219 INode<K, V> subinode = new INode<>(gen);// (TrieMap.inodeupdater)
220 subinode.mainnode = dual (x, xhc, y, yhc, lev + 5, gen);
221 return new CNode<>(bmp, new BasicNode[] { subinode }, gen);
224 return new CNode<>(bmp, new BasicNode[] { x, y }, gen);
226 return new CNode<>(bmp, new BasicNode[] { y, x }, gen);
230 return new LNode<>(x.k, x.v, y.k, y.v);