third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/CNode.java

   1 /*
   2  * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
   3  *
   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
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16 package org.opendaylight.yangtools.triemap;
  17
  18 import static org.opendaylight.yangtools.triemap.Constants.HASH_BITS;
  19 import static org.opendaylight.yangtools.triemap.Constants.LEVEL_BITS;
  20
  21 import com.google.common.base.Verify;
  22 import com.google.common.base.VerifyException;
  23 import java.util.concurrent.ThreadLocalRandom;
  24
  25 final class CNode<K, V> extends MainNode<K, V> {
  26     private static final BasicNode[] EMPTY_ARRAY = new BasicNode[0];
  27
  28     final int bitmap;
  29     final BasicNode[] array;
  30     final Gen gen;
  31
  32     // Since concurrent computation should lead to same results we can update this field without any synchronization.
  33     private volatile int csize = NO_SIZE;
  34
  35     private CNode(final Gen gen, final int bitmap, final BasicNode... array) {
  36         this.bitmap = bitmap;
  37         this.array = array;
  38         this.gen = gen;
  39     }
  40
  41     CNode(final Gen gen) {
  42         this(gen, 0, EMPTY_ARRAY);
  43     }
  44
  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,
  46             final Gen gen) {
  47         return dual(x, x.hc, new SNode<>(key, value, hc), hc, lev, gen);
  48     }
  49
  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);
  54         }
  55
  56         final int xidx = (xhc >>> lev) & 0x1f;
  57         final int yidx = (yhc >>> lev) & 0x1f;
  58         final int bmp = (1 << xidx) | (1 << yidx);
  59
  60         if (xidx == yidx) {
  61             return new CNode<>(gen, bmp, new INode<>(gen, dual(x, xhc, y, yhc, lev + LEVEL_BITS, gen)));
  62         }
  63
  64         return xidx < yidx ? new CNode<>(gen, bmp, x, y) : new CNode<>(gen, bmp, y, x);
  65     }
  66
  67     @Override
  68     int trySize() {
  69         return csize;
  70     }
  71
  72     @Override
  73     int size(final ImmutableTrieMap<?, ?> ct) {
  74         int sz;
  75         return (sz = csize) != NO_SIZE ? sz : (csize = computeSize(ct));
  76     }
  77
  78     static VerifyException invalidElement(final BasicNode elem) {
  79         throw new VerifyException("A CNode can contain only CNodes and SNodes, not " + elem);
  80     }
  81
  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
  86     // to be independent
  87     private int computeSize(final ImmutableTrieMap<?, ?> ct) {
  88         final int len = array.length;
  89         switch (len) {
  90             case 0:
  91                 return 0;
  92             case 1:
  93                 return elementSize(array[0], ct);
  94             default:
  95                 final int offset = ThreadLocalRandom.current().nextInt(len);
  96                 int sz = 0;
  97                 for (int i = offset; i < len; ++i) {
  98                     sz += elementSize(array[i], ct);
  99                 }
 100                 for (int i = 0; i < offset; ++i) {
 101                     sz += elementSize(array[i], ct);
 102                 }
 103                 return sz;
 104         }
 105     }
 106
 107     private static int elementSize(final BasicNode elem, final ImmutableTrieMap<?, ?> ct) {
 108         if (elem instanceof SNode) {
 109             return 1;
 110         } else if (elem instanceof INode) {
 111             return ((INode<?, ?>) elem).size(ct);
 112         } else {
 113             throw invalidElement(elem);
 114         }
 115     }
 116
 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);
 121         narr[pos] = nn;
 122         return new CNode<>(gen, bitmap, narr);
 123     }
 124
 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);
 132     }
 133
 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);
 138         narr [pos] = nn;
 139         System.arraycopy(array, pos, narr, pos + 1, len - pos);
 140         return new CNode<>(gen, bitmap | flag, narr);
 141     }
 142
 143     /**
 144      * Returns a copy of this cnode such that all the i-nodes below it are
 145      * copied to the specified generation `ngen`.
 146      */
 147     CNode<K, V> renewed(final Gen ngen, final TrieMap<K, V> ct) {
 148         int i = 0;
 149         final BasicNode[] arr = array;
 150         final int len = arr.length;
 151         final BasicNode[] narr = new BasicNode[len];
 152         while (i < 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) {
 157                 narr[i] = elem;
 158             }
 159             i += 1;
 160         }
 161         return new CNode<>(ngen, bitmap, narr);
 162     }
 163
 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();
 168             }
 169             return this;
 170         }
 171
 172         return this;
 173     }
 174
 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) {
 182         int bmp = bitmap;
 183         int i = 0;
 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) {
 193                 tmparray [i] = sub;
 194             }
 195             i += 1;
 196         }
 197
 198         return new CNode<K, V>(gen, bmp, tmparray).toContracted(lev);
 199     }
 200
 201     private static BasicNode resurrect(final INode<?, ?> inode, final MainNode<?, ?> inodemain) {
 202         return inodemain instanceof TNode ? ((TNode<?, ?>) inodemain).copyUntombed() : inode;
 203     }
 204
 205     @Override
 206     String string(final int lev) {
 207         // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
 208         // 1)).mkString("\n"));
 209         return "CNode";
 210     }
 211
 212     /*
 213      * quiescently consistent - don't call concurrently to anything
 214      * involving a GCAS!!
 215      */
 216     // protected Seq<K,V> collectElems() {
 217     // array flatMap {
 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
 223     // }
 224     // }
 225     // }
 226
 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 +
 231     // ")")
 232     // // }
 233     // return null;
 234     // }
 235
 236     @Override
 237     public String toString() {
 238         // val elems = collectLocalElems
 239         // "CNode(sz: %d; %s)".format(elems.size,
 240         // elems.sorted.mkString(", "))
 241         return "CNode";
 242     }
 243 }