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