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