third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.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 com.google.common.base.Preconditions;
  19 import java.io.ObjectStreamException;
  20 import java.io.Serializable;
  21 import java.util.AbstractMap;
  22 import java.util.AbstractSet;
  23 import java.util.ArrayList;
  24 import java.util.Arrays;
  25 import java.util.Iterator;
  26 import java.util.List;
  27 import java.util.Optional;
  28 import java.util.Set;
  29 import java.util.concurrent.ConcurrentMap;
  30 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  31
  32 /***
  33  * This is a port of Scala's TrieMap class from the Scala Collections library. This implementation does not support
  34  * null keys nor null values.
  35  *
  36  * @author Roman Levenstein &lt;romixlev@gmail.com&gt;
  37  *
  38  * @param <K>
  39  * @param <V>
  40  */
  41 @SuppressWarnings({"unchecked", "rawtypes", "unused"})
  42 public final class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
  43     private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER =
  44             AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root");
  45     private static final long serialVersionUID = 1L;
  46
  47     /**
  48      * EntrySet
  49      */
  50     private final EntrySet entrySet = new EntrySet();
  51     private final Equivalence<? super K> equiv;
  52     private final boolean readOnly;
  53
  54     private volatile Object root;
  55
  56     private TrieMap(final INode<K, V> r, final Equivalence<? super K> equiv, final boolean readOnly) {
  57         this.root = r;
  58         this.equiv = equiv;
  59         this.readOnly = readOnly;
  60     }
  61
  62     TrieMap(final Equivalence<? super K> equiv) {
  63         this(newRootNode(), equiv, false);
  64     }
  65
  66     public TrieMap() {
  67         this(Equivalence.equals());
  68     }
  69
  70     /* internal methods */
  71
  72     final Equivalence<? super K> equiv() {
  73         return equiv;
  74     }
  75
  76     private static <K,V> INode<K, V> newRootNode() {
  77         final Gen gen = new Gen();
  78         return new INode<>(gen, new CNode<>(gen));
  79     }
  80
  81     final boolean CAS_ROOT(final Object ov, final Object nv) {
  82         Preconditions.checkState(!readOnly, "Attempted to modify a read-only snapshot");
  83         return ROOT_UPDATER.compareAndSet (this, ov, nv);
  84     }
  85
  86     // FIXME: abort = false by default
  87     final INode<K, V> readRoot(final boolean abort) {
  88         return RDCSS_READ_ROOT(abort);
  89     }
  90
  91     final INode<K, V> readRoot() {
  92         return RDCSS_READ_ROOT(false);
  93     }
  94
  95     final INode<K, V> RDCSS_READ_ROOT() {
  96         return RDCSS_READ_ROOT(false);
  97     }
  98
  99     final INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
 100         final Object r = /* READ */root;
 101         if (r instanceof INode) {
 102             return (INode<K, V>) r;
 103         } else if (r instanceof RDCSS_Descriptor) {
 104             return RDCSS_Complete (abort);
 105         } else {
 106             throw new IllegalStateException("Unhandled root " + r);
 107         }
 108     }
 109
 110     private INode<K, V> RDCSS_Complete(final boolean abort) {
 111         while (true) {
 112             final Object v = /* READ */root;
 113             if (v instanceof INode) {
 114                 return (INode<K, V>) v;
 115             }
 116
 117             if (v instanceof RDCSS_Descriptor) {
 118                 final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
 119                 final INode<K, V> ov = desc.old;
 120                 final MainNode<K, V> exp = desc.expectedmain;
 121                 final INode<K, V> nv = desc.nv;
 122
 123                 if (abort) {
 124                     if (CAS_ROOT(desc, ov)) {
 125                         return ov;
 126                     }
 127
 128                     // Tail recursion: return RDCSS_Complete(abort);
 129                     continue;
 130                 }
 131
 132                 final MainNode<K, V> oldmain = ov.gcasRead(this);
 133                 if (oldmain == exp) {
 134                     if (CAS_ROOT(desc, nv)) {
 135                         desc.committed = true;
 136                         return nv;
 137                     }
 138
 139                     // Tail recursion: return RDCSS_Complete(abort);
 140                     continue;
 141                 }
 142
 143                 if (CAS_ROOT(desc, ov)) {
 144                     return ov;
 145                 }
 146
 147                 // Tail recursion: return RDCSS_Complete(abort);
 148                 continue;
 149             }
 150
 151             throw new IllegalStateException("Unexpected root " + v);
 152         }
 153     }
 154
 155     private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 156         final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
 157         if (CAS_ROOT(ov, desc)) {
 158             RDCSS_Complete(false);
 159             return /* READ */desc.committed;
 160         }
 161
 162         return false;
 163     }
 164
 165     private void inserthc(final K k, final int hc, final V v) {
 166         while (true) {
 167             final INode<K, V> r = RDCSS_READ_ROOT();
 168             if (r.rec_insert(k, v, hc, 0, null, r.gen, this)) {
 169                 // Successful, we are done
 170                 return;
 171             }
 172
 173             // Tail recursion: inserthc(k, hc, v);
 174         }
 175     }
 176
 177     private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
 178         while (true) {
 179             final INode<K, V> r = RDCSS_READ_ROOT();
 180             final Optional<V> ret = r.rec_insertif(k, v, hc, cond, 0, null, r.gen, this);
 181             if (ret != null) {
 182                 return ret;
 183             }
 184
 185             // Tail recursion: return insertifhc(k, hc, v, cond);
 186         }
 187     }
 188
 189     private Object lookuphc(final K k, final int hc) {
 190         while (true) {
 191             final INode<K, V> r = RDCSS_READ_ROOT ();
 192             final Object res = r.rec_lookup(k, hc, 0, null, r.gen, this);
 193             if (!INode.RESTART.equals(res)) {
 194                 return res;
 195             }
 196
 197             // Tail recursion: lookuphc(k, hc)
 198         }
 199     }
 200
 201     private Optional<V> removehc(final K k, final V v, final int hc) {
 202         while (true) {
 203             final INode<K, V> r = RDCSS_READ_ROOT();
 204             final Optional<V> res = r.rec_remove(k, v, hc, 0, null, r.gen, this);
 205             if (res != null) {
 206                 return res;
 207             }
 208
 209             // Tail recursion: return removehc(k, v, hc);
 210         }
 211     }
 212
 213     /**
 214      * Ensure this instance is read-write, throw UnsupportedOperationException
 215      * otherwise. Used by Map-type methods for quick check.
 216      */
 217     private void ensureReadWrite() {
 218         if (readOnly) {
 219             throw new UnsupportedOperationException("Attempted to modify a read-only view");
 220         }
 221     }
 222
 223     boolean isReadOnly() {
 224         return readOnly;
 225     }
 226
 227     /* public methods */
 228
 229     /**
 230      * Returns a snapshot of this TrieMap. This operation is lock-free and
 231      * linearizable.
 232      *
 233      * The snapshot is lazily updated - the first time some branch in the
 234      * snapshot or this TrieMap are accessed, they are rewritten. This means
 235      * that the work of rebuilding both the snapshot and this TrieMap is
 236      * distributed across all the threads doing updates or accesses subsequent
 237      * to the snapshot creation.
 238      */
 239     public TrieMap<K, V> snapshot() {
 240         while (true) {
 241             final INode<K, V> r = RDCSS_READ_ROOT();
 242             final MainNode<K, V> expmain = r.gcasRead(this);
 243             if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this))) {
 244                 return new TrieMap<> (r.copyToGen(new Gen(), this), equiv, readOnly);
 245             }
 246
 247             // Tail recursion: return snapshot();
 248         }
 249     }
 250
 251     /**
 252      * Returns a read-only snapshot of this TrieMap. This operation is lock-free
 253      * and linearizable.
 254      *
 255      * The snapshot is lazily updated - the first time some branch of this
 256      * TrieMap are accessed, it is rewritten. The work of creating the snapshot
 257      * is thus distributed across subsequent updates and accesses on this
 258      * TrieMap by all threads. Note that the snapshot itself is never rewritten
 259      * unlike when calling the `snapshot` method, but the obtained snapshot
 260      * cannot be modified.
 261      *
 262      * This method is used by other methods such as `size` and `iterator`.
 263      */
 264     public TrieMap<K, V> readOnlySnapshot() {
 265         // Is it a snapshot of a read-only snapshot?
 266         if (readOnly) {
 267             return this;
 268         }
 269
 270         while (true) {
 271             final INode<K, V> r = RDCSS_READ_ROOT();
 272             final MainNode<K, V> expmain = r.gcasRead(this);
 273             if (RDCSS_ROOT(r, expmain, r.copyToGen (new Gen(), this))) {
 274                 return new TrieMap<>(r, equiv, true);
 275             }
 276
 277             // Tail recursion: return readOnlySnapshot();
 278         }
 279     }
 280
 281     @Override
 282     public void clear() {
 283         while (true) {
 284             final INode<K, V> r = RDCSS_READ_ROOT();
 285             if (RDCSS_ROOT(r, r.gcasRead(this), newRootNode())) {
 286                 return;
 287             }
 288         }
 289     }
 290
 291     int computeHash(final K k) {
 292         return equiv.hash(k);
 293     }
 294
 295     boolean equal(final K k1, final K k2) {
 296         return equiv.equivalent(k1, k2);
 297     }
 298
 299     V lookup(final K k) {
 300         return (V) lookuphc(k, computeHash(k));
 301     }
 302
 303     @Override
 304     public V get(final Object k) {
 305         return lookup((K)k);
 306     }
 307
 308     @Override
 309     public V put(final K key, final V value) {
 310         ensureReadWrite();
 311         final int hc = computeHash(key);
 312         return insertifhc (key, hc, value, null).orElse(null);
 313     }
 314
 315     void add(final K k, final V v) {
 316         inserthc(k, computeHash(k), v);
 317     }
 318
 319     @Override
 320     public V remove(final Object k) {
 321         ensureReadWrite();
 322         final int hc = computeHash ((K)k);
 323         return removehc ((K)k, (V) null, hc).orElse(null);
 324     }
 325
 326     @Override
 327     public V putIfAbsent(final K k, final V v) {
 328         ensureReadWrite();
 329         final int hc = computeHash (k);
 330         return insertifhc (k, hc, v, INode.KEY_ABSENT).orElse(null);
 331     }
 332
 333     @Override
 334     public boolean remove(final Object k, final Object v) {
 335         ensureReadWrite();
 336         final int hc = computeHash ((K)k);
 337         return removehc((K)k, (V)v, hc).isPresent();
 338     }
 339
 340     @Override
 341     public boolean replace(final K k, final V oldvalue, final V newvalue) {
 342         ensureReadWrite();
 343         final int hc = computeHash (k);
 344         return insertifhc (k, hc, newvalue, oldvalue).isPresent();
 345     }
 346
 347     @Override
 348     public V replace(final K k, final V v) {
 349         ensureReadWrite();
 350         final int hc = computeHash (k);
 351         return insertifhc (k, hc, v, INode.KEY_PRESENT).orElse(null);
 352     }
 353
 354     /***
 355      * Return an iterator over a TrieMap.
 356      *
 357      * If this is a read-only snapshot, it would return a read-only iterator.
 358      *
 359      * If it is the original TrieMap or a non-readonly snapshot, it would return
 360      * an iterator that would allow for updates.
 361      *
 362      * @return
 363      */
 364     Iterator<Entry<K, V>> iterator() {
 365         return readOnly ? new TrieMapReadOnlyIterator<>(0, this) : new TrieMapIterator<>(0, this);
 366     }
 367
 368     /***
 369      * Return an iterator over a TrieMap.
 370      * This is a read-only iterator.
 371      *
 372      * @return
 373      */
 374     Iterator<Entry<K, V>> readOnlyIterator() {
 375         return new TrieMapReadOnlyIterator<>(0, readOnly ? this : readOnlySnapshot());
 376     }
 377
 378     private int cachedSize() {
 379         INode<K, V> r = RDCSS_READ_ROOT ();
 380         return r.cachedSize (this);
 381     }
 382
 383     @Override
 384     public int size() {
 385         return readOnly ? cachedSize() : readOnlySnapshot().size();
 386     }
 387
 388     @Override
 389     public boolean containsKey(final Object key) {
 390         return lookup((K) key) != null;
 391     }
 392
 393     @Override
 394     public Set<Entry<K, V>> entrySet() {
 395         return entrySet;
 396     }
 397
 398     private Object writeReplace() throws ObjectStreamException {
 399         return new ExternalForm(this);
 400     }
 401
 402     private static final class RDCSS_Descriptor<K, V> {
 403         INode<K, V> old;
 404         MainNode<K, V> expectedmain;
 405         INode<K, V> nv;
 406         volatile boolean committed = false;
 407
 408         RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 409             this.old = old;
 410             this.expectedmain = expectedmain;
 411             this.nv = nv;
 412         }
 413     }
 414
 415     /***
 416      * This iterator is a read-only one and does not allow for any update
 417      * operations on the underlying data structure.
 418      *
 419      * @param <K>
 420      * @param <V>
 421      */
 422     private static final class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
 423         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
 424             super (level, ct, mustInit);
 425         }
 426
 427         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
 428             this (level, ct, true);
 429         }
 430         @Override
 431         void initialize () {
 432             assert (ct.isReadOnly ());
 433             super.initialize ();
 434         }
 435
 436         @Override
 437         public void remove () {
 438             throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
 439         }
 440
 441         @Override
 442         Entry<K, V> nextEntry(final Entry<K, V> rr) {
 443             // Return non-updatable entry
 444             return rr;
 445         }
 446     }
 447
 448     private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
 449         private int level;
 450         protected TrieMap<K, V> ct;
 451         private final boolean mustInit;
 452         private final BasicNode[][] stack = new BasicNode[7][];
 453         private final int[] stackpos = new int[7];
 454         private int depth = -1;
 455         private Iterator<Entry<K, V>> subiter = null;
 456         private KVNode<K, V> current = null;
 457         private Entry<K, V> lastReturned = null;
 458
 459         TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
 460             this.level = level;
 461             this.ct = ct;
 462             this.mustInit = mustInit;
 463             if (this.mustInit) {
 464                 initialize ();
 465             }
 466         }
 467
 468         TrieMapIterator (final int level, final TrieMap<K, V> ct) {
 469             this (level, ct, true);
 470         }
 471
 472
 473         @Override
 474         public boolean hasNext () {
 475             return (current != null) || (subiter != null);
 476         }
 477
 478         @Override
 479         public Entry<K, V> next () {
 480             if (hasNext ()) {
 481                 Entry<K, V> r = null;
 482                 if (subiter != null) {
 483                     r = subiter.next ();
 484                     checkSubiter ();
 485                 } else {
 486                     r = current.kvPair ();
 487                     advance ();
 488                 }
 489
 490                 lastReturned = r;
 491                 if (r != null) {
 492                     final Entry<K, V> rr = r;
 493                     return nextEntry(rr);
 494                 }
 495                 return r;
 496             } else {
 497                 // return Iterator.empty ().next ();
 498                 return null;
 499             }
 500         }
 501
 502         Entry<K, V> nextEntry(final Entry<K, V> rr) {
 503             return new Entry<K, V>() {
 504                 private V updated = null;
 505
 506                 @Override
 507                 public K getKey () {
 508                     return rr.getKey ();
 509                 }
 510
 511                 @Override
 512                 public V getValue () {
 513                     return (updated == null)?rr.getValue (): updated;
 514                 }
 515
 516                 @Override
 517                 public V setValue (final V value) {
 518                     updated = value;
 519                     return ct.replace (getKey (), value);
 520                 }
 521             };
 522         }
 523
 524         private void readin (final INode<K, V> in) {
 525             MainNode<K, V> m = in.gcasRead (ct);
 526             if (m instanceof CNode) {
 527                 CNode<K, V> cn = (CNode<K, V>) m;
 528                 depth += 1;
 529                 stack [depth] = cn.array;
 530                 stackpos [depth] = -1;
 531                 advance ();
 532             } else if (m instanceof TNode) {
 533                 current = (TNode<K, V>) m;
 534             } else if (m instanceof LNode) {
 535                 subiter = ((LNode<K, V>) m).iterator();
 536                 checkSubiter ();
 537             } else if (m == null) {
 538                 current = null;
 539             }
 540         }
 541
 542         // @inline
 543         private void checkSubiter () {
 544             if (!subiter.hasNext ()) {
 545                 subiter = null;
 546                 advance ();
 547             }
 548         }
 549
 550         // @inline
 551         void initialize () {
 552 //            assert (ct.isReadOnly ());
 553             INode<K, V> r = ct.RDCSS_READ_ROOT ();
 554             readin (r);
 555         }
 556
 557         void advance () {
 558             if (depth >= 0) {
 559                 int npos = stackpos [depth] + 1;
 560                 if (npos < stack [depth].length) {
 561                     stackpos [depth] = npos;
 562                     BasicNode elem = stack [depth] [npos];
 563                     if (elem instanceof SNode) {
 564                         current = (SNode<K, V>) elem;
 565                     } else if (elem instanceof INode) {
 566                         readin ((INode<K, V>) elem);
 567                     }
 568                 } else {
 569                     depth -= 1;
 570                     advance ();
 571                 }
 572             } else {
 573                 current = null;
 574             }
 575         }
 576
 577         protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
 578             return new TrieMapIterator<> (_lev, _ct, _mustInit);
 579         }
 580
 581         protected void dupTo (final TrieMapIterator<K, V> it) {
 582             it.level = this.level;
 583             it.ct = this.ct;
 584             it.depth = this.depth;
 585             it.current = this.current;
 586
 587             // these need a deep copy
 588             System.arraycopy (this.stack, 0, it.stack, 0, 7);
 589             System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
 590
 591             // this one needs to be evaluated
 592             if (this.subiter == null) {
 593                 it.subiter = null;
 594             } else {
 595                 List<Entry<K, V>> lst = toList (this.subiter);
 596                 this.subiter = lst.iterator ();
 597                 it.subiter = lst.iterator ();
 598             }
 599         }
 600
 601         // /** Returns a sequence of iterators over subsets of this iterator.
 602         // * It's used to ease the implementation of splitters for a parallel
 603         // version of the TrieMap.
 604         // */
 605         // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
 606         // null) {
 607         // // the case where an LNode is being iterated
 608         // val it = subiter
 609         // subiter = null
 610         // advance()
 611         // this.level += 1
 612         // Seq(it, this)
 613         // } else if (depth == -1) {
 614         // this.level += 1
 615         // Seq(this)
 616         // } else {
 617         // var d = 0
 618         // while (d <= depth) {
 619         // val rem = stack(d).length - 1 - stackpos(d)
 620         // if (rem > 0) {
 621         // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
 622         // stack(d) = arr1
 623         // stackpos(d) = -1
 624         // val it = newIterator(level + 1, ct, false)
 625         // it.stack(0) = arr2
 626         // it.stackpos(0) = -1
 627         // it.depth = 0
 628         // it.advance() // <-- fix it
 629         // this.level += 1
 630         // return Seq(this, it)
 631         // }
 632         // d += 1
 633         // }
 634         // this.level += 1
 635         // Seq(this)
 636         // }
 637
 638         private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
 639             ArrayList<Entry<K, V>> list = new ArrayList<> ();
 640             while (it.hasNext ()) {
 641                 list.add (it.next ());
 642             }
 643             return list;
 644         }
 645
 646         void printDebug () {
 647             System.out.println ("ctrie iterator");
 648             System.out.println (Arrays.toString (stackpos));
 649             System.out.println ("depth: " + depth);
 650             System.out.println ("curr.: " + current);
 651             // System.out.println(stack.mkString("\n"));
 652         }
 653
 654         @Override
 655         public void remove () {
 656             if (lastReturned != null) {
 657                 ct.remove (lastReturned.getKey ());
 658                 lastReturned = null;
 659             } else {
 660                 throw new IllegalStateException();
 661             }
 662         }
 663
 664     }
 665
 666     /***
 667      * Support for EntrySet operations required by the Map interface
 668      */
 669     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 670
 671         @Override
 672         public Iterator<Entry<K, V>> iterator () {
 673             return TrieMap.this.iterator ();
 674         }
 675
 676         @Override
 677         public final boolean contains (final Object o) {
 678             if (!(o instanceof Entry)) {
 679                 return false;
 680             }
 681             final Entry<K, V> e = (Entry<K, V>) o;
 682             final K k = e.getKey ();
 683             final V v = lookup (k);
 684             return v != null;
 685         }
 686
 687         @Override
 688         public final boolean remove (final Object o) {
 689             if (!(o instanceof Entry)) {
 690                 return false;
 691             }
 692             final Entry<K, V> e = (Entry<K, V>) o;
 693             final K k = e.getKey();
 694             return null != TrieMap.this.remove(k);
 695         }
 696
 697         @Override
 698         public final int size () {
 699             int size = 0;
 700             for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
 701                 size++;
 702             }
 703             return size;
 704         }
 705
 706         @Override
 707         public final void clear () {
 708             TrieMap.this.clear ();
 709         }
 710     }
 711
 712 }