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 java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
  19
  20 final class CNode<K, V> extends MainNode<K, V> {
  21     @SuppressWarnings("rawtypes")
  22     private static final AtomicIntegerFieldUpdater<CNode> CSIZE_UPDATER = AtomicIntegerFieldUpdater.newUpdater(
  23         CNode.class, "csize");
  24
  25     private static final BasicNode[] EMPTY_ARRAY = new BasicNode[0];
  26     private static final int NO_SIZE = -1;
  27
  28     final int bitmap;
  29     final BasicNode[] array;
  30     final Gen gen;
  31
  32     private volatile int csize = NO_SIZE;
  33
  34     private CNode(final Gen gen, final int bitmap, final BasicNode... array) {
  35         this.bitmap = bitmap;
  36         this.array = array;
  37         this.gen = gen;
  38     }
  39
  40     CNode(final Gen gen) {
  41         this(gen, 0, EMPTY_ARRAY);
  42     }
  43
  44     static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
  45             final int lev, final Gen gen) {
  46         if (lev >= 35) {
  47             return new LNode<>(x.k, x.v, y.k, y.v);
  48         }
  49
  50         final int xidx = (xhc >>> lev) & 0x1f;
  51         final int yidx = (yhc >>> lev) & 0x1f;
  52         final int bmp = (1 << xidx) | (1 << yidx);
  53
  54         if (xidx == yidx) {
  55             INode<K, V> subinode = new INode<>(gen, dual(x, xhc, y, yhc, lev + 5, gen));
  56             return new CNode<>(gen, bmp, subinode);
  57         }
  58
  59         return xidx < yidx ? new CNode<>(gen, bmp, x, y) : new CNode<>(gen, bmp, y, x);
  60     }
  61
  62     // this should only be called from within read-only snapshots
  63     @Override
  64     int cachedSize(final TrieMap<K, V> ct) {
  65         int sz = csize;
  66         if (sz == NO_SIZE) {
  67             // We have not computed the size yet, do that now
  68             sz = computeSize(ct);
  69             if (!CSIZE_UPDATER.compareAndSet(this, NO_SIZE, sz)) {
  70                 // We have been pre-empted by some else: read the result
  71                 sz = csize;
  72             }
  73         }
  74
  75         return sz;
  76     }
  77
  78     // lends itself towards being parallelizable by choosing
  79     // a random starting offset in the array
  80     // => if there are concurrent size computations, they start
  81     // at different positions, so they are more likely to
  82     // to be independent
  83     private int computeSize(final TrieMap<K, V> ct) {
  84         int i = 0;
  85         int sz = 0;
  86         // final int offset = (array.length > 0) ?
  87         // // util.Random.nextInt(array.length) /* <-- benchmarks show that
  88         // // this causes observable contention */
  89         // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
  90         // array.length)
  91         // : 0;
  92
  93         final int offset = 0;
  94         while (i < array.length) {
  95             int pos = (i + offset) % array.length;
  96             BasicNode elem = array [pos];
  97             if (elem instanceof SNode) {
  98                 sz += 1;
  99             } else if (elem instanceof INode) {
 100                 sz += ((INode<K, V>) elem).cachedSize(ct);
 101             }
 102             i += 1;
 103         }
 104         return sz;
 105     }
 106
 107     CNode<K, V> updatedAt(final int pos, final BasicNode nn, final Gen gen) {
 108         int len = array.length;
 109         BasicNode[] narr = new BasicNode[len];
 110         System.arraycopy(array, 0, narr, 0, len);
 111         narr[pos] = nn;
 112         return new CNode<>(gen, bitmap, narr);
 113     }
 114
 115     CNode<K, V> removedAt(final int pos, final int flag, final Gen gen) {
 116         BasicNode[] arr = array;
 117         int len = arr.length;
 118         BasicNode[] narr = new BasicNode[len - 1];
 119         System.arraycopy(arr, 0, narr, 0, pos);
 120         System.arraycopy(arr, pos + 1, narr, pos, len - pos - 1);
 121         return new CNode<>(gen, bitmap ^ flag, narr);
 122     }
 123
 124     CNode<K, V> insertedAt(final int pos, final int flag, final BasicNode nn, final Gen gen) {
 125         int len = array.length;
 126         int bmp = bitmap;
 127         BasicNode[] narr = new BasicNode[len + 1];
 128         System.arraycopy(array, 0, narr, 0, pos);
 129         narr [pos] = nn;
 130         System.arraycopy(array, pos, narr, pos + 1, len - pos);
 131         return new CNode<>(gen, bmp | flag, narr);
 132     }
 133
 134     /**
 135      * Returns a copy of this cnode such that all the i-nodes below it are
 136      * copied to the specified generation `ngen`.
 137      */
 138     CNode<K, V> renewed(final Gen ngen, final TrieMap<K, V> ct) {
 139         int i = 0;
 140         BasicNode[] arr = array;
 141         int len = arr.length;
 142         BasicNode[] narr = new BasicNode[len];
 143         while (i < len) {
 144             BasicNode elem = arr[i];
 145             if (elem instanceof INode) {
 146                 INode<K, V> in = (INode<K, V>) elem;
 147                 narr [i] = in.copyToGen(ngen, ct);
 148             } else if (elem != null) {
 149                 narr [i] = elem;
 150             }
 151             i += 1;
 152         }
 153         return new CNode<>(ngen, bitmap, narr);
 154     }
 155
 156     private BasicNode resurrect(final INode<K, V> inode, final Object inodemain) {
 157         if (inodemain instanceof TNode) {
 158             TNode<K, V> tn = (TNode<K, V>) inodemain;
 159             return tn.copyUntombed();
 160         }
 161
 162         return inode;
 163     }
 164
 165     MainNode<K, V> toContracted(final int lev) {
 166         if (array.length == 1 && lev > 0) {
 167             if (array[0] instanceof SNode) {
 168                 final SNode<K, V> sn = (SNode<K, V>) array[0];
 169                 return sn.copyTombed();
 170             }
 171             return this;
 172         }
 173
 174         return this;
 175     }
 176
 177     // - if the branching factor is 1 for this CNode, and the child
 178     // is a tombed SNode, returns its tombed version
 179     // - otherwise, if there is at least one non-null node below,
 180     // returns the version of this node with at least some null-inodes
 181     // removed (those existing when the op began)
 182     // - if there are only null-i-nodes below, returns null
 183     MainNode<K, V> toCompressed(final TrieMap<K, V> ct, final int lev, final Gen gen) {
 184         int bmp = bitmap;
 185         int i = 0;
 186         BasicNode[] arr = array;
 187         BasicNode[] tmparray = new BasicNode[arr.length];
 188         while (i < arr.length) { // construct new bitmap
 189             BasicNode sub = arr[i];
 190             if (sub instanceof INode) {
 191                 INode<K, V> in = (INode<K, V>) sub;
 192                 MainNode<K, V> inodemain = in.gcasRead (ct);
 193                 assert (inodemain != null);
 194                 tmparray [i] = resurrect (in, inodemain);
 195             } else if (sub instanceof SNode) {
 196                 tmparray [i] = sub;
 197             }
 198             i += 1;
 199         }
 200
 201         return new CNode<K, V>(gen, bmp, tmparray).toContracted(lev);
 202     }
 203
 204     @Override
 205     String string(final int lev) {
 206         // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
 207         // 1)).mkString("\n"));
 208         return "CNode";
 209     }
 210
 211     /*
 212      * quiescently consistent - don't call concurrently to anything
 213      * involving a GCAS!!
 214      */
 215     // protected Seq<K,V> collectElems() {
 216     // array flatMap {
 217     // case sn: SNode[K, V] => Some(sn.kvPair)
 218     // case in: INode[K, V] => in.mainnode match {
 219     // case tn: TNode[K, V] => Some(tn.kvPair)
 220     // case ln: LNode[K, V] => ln.listmap.toList
 221     // case cn: CNode[K, V] => cn.collectElems
 222     // }
 223     // }
 224     // }
 225
 226     // protected Seq<String> collectLocalElems() {
 227     // // array flatMap {
 228     // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
 229     // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
 230     // ")")
 231     // // }
 232     // return null;
 233     // }
 234
 235     @Override
 236     public String toString () {
 237         // val elems = collectLocalElems
 238         // "CNode(sz: %d; %s)".format(elems.size,
 239         // elems.sorted.mkString(", "))
 240         return "CNode";
 241     }
 242 }