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 com.google.common.base.VerifyException;
23 import java.util.concurrent.ThreadLocalRandom;
25 final class CNode<K, V> extends MainNode<K, V> {
26 private static final BasicNode[] EMPTY_ARRAY = new BasicNode[0];
29 final BasicNode[] array;
32 // Since concurrent computation should lead to same results we can update this field without any synchronization.
33 private volatile int csize = NO_SIZE;
35 private CNode(final Gen gen, final int bitmap, final BasicNode... array) {
41 CNode(final Gen gen) {
42 this(gen, 0, EMPTY_ARRAY);
45 static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final K key, final V value, final int hc, final int lev,
47 return dual(x, x.hc, new SNode<>(key, value, hc), hc, lev, gen);
50 private static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
51 final int lev, final Gen gen) {
52 if (lev >= HASH_BITS) {
53 return new LNode<>(x.key, x.value, y.key, y.value);
56 final int xidx = (xhc >>> lev) & 0x1f;
57 final int yidx = (yhc >>> lev) & 0x1f;
58 final int bmp = (1 << xidx) | (1 << yidx);
61 return new CNode<>(gen, bmp, new INode<>(gen, dual(x, xhc, y, yhc, lev + LEVEL_BITS, gen)));
64 return xidx < yidx ? new CNode<>(gen, bmp, x, y) : new CNode<>(gen, bmp, y, x);
73 int size(final ImmutableTrieMap<?, ?> ct) {
75 return (sz = csize) != NO_SIZE ? sz : (csize = computeSize(ct));
78 static VerifyException invalidElement(final BasicNode elem) {
79 throw new VerifyException("A CNode can contain only CNodes and SNodes, not " + elem);
82 // lends itself towards being parallelizable by choosing
83 // a random starting offset in the array
84 // => if there are concurrent size computations, they start
85 // at different positions, so they are more likely to
87 private int computeSize(final ImmutableTrieMap<?, ?> ct) {
88 final int len = array.length;
93 return elementSize(array[0], ct);
95 final int offset = ThreadLocalRandom.current().nextInt(len);
97 for (int i = offset; i < len; ++i) {
98 sz += elementSize(array[i], ct);
100 for (int i = 0; i < offset; ++i) {
101 sz += elementSize(array[i], ct);
107 private static int elementSize(final BasicNode elem, final ImmutableTrieMap<?, ?> ct) {
108 if (elem instanceof SNode) {
110 } else if (elem instanceof INode) {
111 return ((INode<?, ?>) elem).size(ct);
113 throw invalidElement(elem);
117 CNode<K, V> updatedAt(final int pos, final BasicNode nn, final Gen gen) {
118 int len = array.length;
119 BasicNode[] narr = new BasicNode[len];
120 System.arraycopy(array, 0, narr, 0, len);
122 return new CNode<>(gen, bitmap, narr);
125 CNode<K, V> removedAt(final int pos, final int flag, final Gen gen) {
126 BasicNode[] arr = array;
127 int len = arr.length;
128 BasicNode[] narr = new BasicNode[len - 1];
129 System.arraycopy(arr, 0, narr, 0, pos);
130 System.arraycopy(arr, pos + 1, narr, pos, len - pos - 1);
131 return new CNode<>(gen, bitmap ^ flag, narr);
134 CNode<K, V> insertedAt(final int pos, final int flag, final BasicNode nn, final Gen gen) {
135 int len = array.length;
136 BasicNode[] narr = new BasicNode[len + 1];
137 System.arraycopy(array, 0, narr, 0, pos);
139 System.arraycopy(array, pos, narr, pos + 1, len - pos);
140 return new CNode<>(gen, bitmap | flag, narr);
144 * Returns a copy of this cnode such that all the i-nodes below it are
145 * copied to the specified generation `ngen`.
147 CNode<K, V> renewed(final Gen ngen, final TrieMap<K, V> ct) {
149 final BasicNode[] arr = array;
150 final int len = arr.length;
151 final BasicNode[] narr = new BasicNode[len];
153 final BasicNode elem = arr[i];
154 if (elem instanceof INode) {
155 narr[i] = ((INode<?, ?>) elem).copyToGen(ngen, ct);
156 } else if (elem != null) {
161 return new CNode<>(ngen, bitmap, narr);
164 MainNode<K, V> toContracted(final int lev) {
165 if (array.length == 1 && lev > 0) {
166 if (array[0] instanceof SNode) {
167 return ((SNode<K, V>) array[0]).copyTombed();
175 // - if the branching factor is 1 for this CNode, and the child
176 // is a tombed SNode, returns its tombed version
177 // - otherwise, if there is at least one non-null node below,
178 // returns the version of this node with at least some null-inodes
179 // removed (those existing when the op began)
180 // - if there are only null-i-nodes below, returns null
181 MainNode<K, V> toCompressed(final TrieMap<?, ?> ct, final int lev, final Gen gen) {
184 BasicNode[] arr = array;
185 BasicNode[] tmparray = new BasicNode[arr.length];
186 while (i < arr.length) { // construct new bitmap
187 BasicNode sub = arr[i];
188 if (sub instanceof INode) {
189 final INode<?, ?> in = (INode<?, ?>) sub;
190 final MainNode<?, ?> inodemain = Verify.verifyNotNull(in.gcasRead(ct));
191 tmparray [i] = resurrect(in, inodemain);
192 } else if (sub instanceof SNode) {
198 return new CNode<K, V>(gen, bmp, tmparray).toContracted(lev);
201 private static BasicNode resurrect(final INode<?, ?> inode, final MainNode<?, ?> inodemain) {
202 return inodemain instanceof TNode ? ((TNode<?, ?>) inodemain).copyUntombed() : inode;
206 String string(final int lev) {
207 // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
208 // 1)).mkString("\n"));
213 * quiescently consistent - don't call concurrently to anything
216 // protected Seq<K,V> collectElems() {
218 // case sn: SNode[K, V] => Some(sn.kvPair)
219 // case in: INode[K, V] => in.mainnode match {
220 // case tn: TNode[K, V] => Some(tn.kvPair)
221 // case ln: LNode[K, V] => ln.listmap.toList
222 // case cn: CNode[K, V] => cn.collectElems
227 // protected Seq<String> collectLocalElems() {
228 // // array flatMap {
229 // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
230 // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
237 public String toString() {
238 // val elems = collectLocalElems
239 // "CNode(sz: %d; %s)".format(elems.size,
240 // elems.sorted.mkString(", "))