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