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