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.HASH_BITS;
19 import static org.opendaylight.yangtools.triemap.Constants.LEVEL_BITS;
21 import com.google.common.base.Verify;
22 import java.util.concurrent.ThreadLocalRandom;
24 final class CNode<K, V> extends MainNode<K, V> {
25 private static final BasicNode[] EMPTY_ARRAY = new BasicNode[0];
28 final BasicNode[] array;
31 // Since concurrent computation should lead to same results we can update this field without any synchronization.
32 private volatile int csize = NO_SIZE;
34 private CNode(final Gen gen, final int bitmap, final BasicNode... array) {
40 CNode(final Gen gen) {
41 this(gen, 0, EMPTY_ARRAY);
44 static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final K k, final V v, final int hc, final int lev,
46 return dual(x, x.hc, new SNode<>(k, v, hc), hc, lev, gen);
49 private static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
50 final int lev, final Gen gen) {
51 if (lev >= HASH_BITS) {
52 return new LNode<>(x.k, x.v, y.k, y.v);
55 final int xidx = (xhc >>> lev) & 0x1f;
56 final int yidx = (yhc >>> lev) & 0x1f;
57 final int bmp = (1 << xidx) | (1 << yidx);
60 return new CNode<>(gen, bmp, new INode<>(gen, dual(x, xhc, y, yhc, lev + LEVEL_BITS, gen)));
63 return xidx < yidx ? new CNode<>(gen, bmp, x, y) : new CNode<>(gen, bmp, y, x);
72 int size(final ImmutableTrieMap<?, ?> ct) {
74 return (sz = csize) != NO_SIZE ? sz : (csize = computeSize(ct));
77 // lends itself towards being parallelizable by choosing
78 // a random starting offset in the array
79 // => if there are concurrent size computations, they start
80 // at different positions, so they are more likely to
82 private int computeSize(final ImmutableTrieMap<?, ?> ct) {
83 final int len = array.length;
88 return elementSize(array[0], ct);
90 final int offset = ThreadLocalRandom.current().nextInt(len);
92 for (int i = offset; i < len; ++i) {
93 sz += elementSize(array[i], ct);
95 for (int i = 0; i < offset; ++i) {
96 sz += elementSize(array[i], ct);
102 private static int elementSize(final BasicNode elem, final ImmutableTrieMap<?, ?> ct) {
103 if (elem instanceof SNode) {
105 } else if (elem instanceof INode) {
106 return ((INode<?, ?>) elem).size(ct);
108 throw new IllegalStateException("Unhandled element " + elem);
112 CNode<K, V> updatedAt(final int pos, final BasicNode nn, final Gen gen) {
113 int len = array.length;
114 BasicNode[] narr = new BasicNode[len];
115 System.arraycopy(array, 0, narr, 0, len);
117 return new CNode<>(gen, bitmap, narr);
120 CNode<K, V> removedAt(final int pos, final int flag, final Gen gen) {
121 BasicNode[] arr = array;
122 int len = arr.length;
123 BasicNode[] narr = new BasicNode[len - 1];
124 System.arraycopy(arr, 0, narr, 0, pos);
125 System.arraycopy(arr, pos + 1, narr, pos, len - pos - 1);
126 return new CNode<>(gen, bitmap ^ flag, narr);
129 CNode<K, V> insertedAt(final int pos, final int flag, final BasicNode nn, final Gen gen) {
130 int len = array.length;
132 BasicNode[] narr = new BasicNode[len + 1];
133 System.arraycopy(array, 0, narr, 0, pos);
135 System.arraycopy(array, pos, narr, pos + 1, len - pos);
136 return new CNode<>(gen, bmp | flag, narr);
140 * Returns a copy of this cnode such that all the i-nodes below it are
141 * copied to the specified generation `ngen`.
143 CNode<K, V> renewed(final Gen ngen, final TrieMap<K, V> ct) {
145 final BasicNode[] arr = array;
146 final int len = arr.length;
147 final BasicNode[] narr = new BasicNode[len];
149 final BasicNode elem = arr[i];
150 if (elem instanceof INode) {
151 narr[i] = ((INode<?, ?>) elem).copyToGen(ngen, ct);
152 } else if (elem != null) {
157 return new CNode<>(ngen, bitmap, narr);
160 MainNode<K, V> toContracted(final int lev) {
161 if (array.length == 1 && lev > 0) {
162 if (array[0] instanceof SNode) {
163 return ((SNode<K, V>) array[0]).copyTombed();
171 // - if the branching factor is 1 for this CNode, and the child
172 // is a tombed SNode, returns its tombed version
173 // - otherwise, if there is at least one non-null node below,
174 // returns the version of this node with at least some null-inodes
175 // removed (those existing when the op began)
176 // - if there are only null-i-nodes below, returns null
177 MainNode<K, V> toCompressed(final TrieMap<?, ?> ct, final int lev, final Gen gen) {
180 BasicNode[] arr = array;
181 BasicNode[] tmparray = new BasicNode[arr.length];
182 while (i < arr.length) { // construct new bitmap
183 BasicNode sub = arr[i];
184 if (sub instanceof INode) {
185 final INode<?, ?> in = (INode<?, ?>) sub;
186 final MainNode<?, ?> inodemain = Verify.verifyNotNull(in.gcasRead(ct));
187 tmparray [i] = resurrect(in, inodemain);
188 } else if (sub instanceof SNode) {
194 return new CNode<K, V>(gen, bmp, tmparray).toContracted(lev);
197 private static BasicNode resurrect(final INode<?, ?> inode, final MainNode<?, ?> inodemain) {
198 return inodemain instanceof TNode ? ((TNode<?, ?>) inodemain).copyUntombed() : inode;
202 String string(final int lev) {
203 // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
204 // 1)).mkString("\n"));
209 * quiescently consistent - don't call concurrently to anything
212 // protected Seq<K,V> collectElems() {
214 // case sn: SNode[K, V] => Some(sn.kvPair)
215 // case in: INode[K, V] => in.mainnode match {
216 // case tn: TNode[K, V] => Some(tn.kvPair)
217 // case ln: LNode[K, V] => ln.listmap.toList
218 // case cn: CNode[K, V] => cn.collectElems
223 // protected Seq<String> collectLocalElems() {
224 // // array flatMap {
225 // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
226 // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
233 public String toString () {
234 // val elems = collectLocalElems
235 // "CNode(sz: %d; %s)".format(elems.size,
236 // elems.sorted.mkString(", "))