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