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