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