2 * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 package org.opendaylight.yangtools.triemap;
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;
29 import java.util.concurrent.ConcurrentMap;
30 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
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.
36 * @author Roman Levenstein <romixlev@gmail.com>
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;
50 private final EntrySet entrySet = new EntrySet();
51 private final Equivalence<? super K> equiv;
52 private final boolean readOnly;
54 private volatile Object root;
56 private TrieMap(final INode<K, V> r, final Equivalence<? super K> equiv, final boolean readOnly) {
59 this.readOnly = readOnly;
62 TrieMap(final Equivalence<? super K> equiv) {
63 this(newRootNode(), equiv, false);
67 this(Equivalence.equals());
70 /* internal methods */
72 final Equivalence<? super K> equiv() {
76 private static <K,V> INode<K, V> newRootNode() {
77 final Gen gen = new Gen();
78 return new INode<>(gen, new CNode<>(gen));
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);
86 // FIXME: abort = false by default
87 final INode<K, V> readRoot(final boolean abort) {
88 return RDCSS_READ_ROOT(abort);
91 final INode<K, V> readRoot() {
92 return RDCSS_READ_ROOT(false);
95 final INode<K, V> RDCSS_READ_ROOT() {
96 return RDCSS_READ_ROOT(false);
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);
106 throw new IllegalStateException("Unhandled root " + r);
110 private INode<K, V> RDCSS_Complete(final boolean abort) {
112 final Object v = /* READ */root;
113 if (v instanceof INode) {
114 return (INode<K, V>) v;
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;
124 if (CAS_ROOT(desc, ov)) {
128 // Tail recursion: return RDCSS_Complete(abort);
132 final MainNode<K, V> oldmain = ov.gcasRead(this);
133 if (oldmain == exp) {
134 if (CAS_ROOT(desc, nv)) {
135 desc.committed = true;
139 // Tail recursion: return RDCSS_Complete(abort);
143 if (CAS_ROOT(desc, ov)) {
147 // Tail recursion: return RDCSS_Complete(abort);
151 throw new IllegalStateException("Unexpected root " + v);
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;
165 private void inserthc(final K k, final int hc, final V v) {
167 final INode<K, V> r = RDCSS_READ_ROOT();
168 if (r.rec_insert(k, v, hc, 0, null, this)) {
169 // Successful, we are done
173 // Tail recursion: inserthc(k, hc, v);
177 private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
179 final INode<K, V> r = RDCSS_READ_ROOT();
180 final Optional<V> ret = r.rec_insertif(k, v, hc, cond, 0, null, this);
185 // Tail recursion: return insertifhc(k, hc, v, cond);
189 private Object lookuphc(final K k, final int hc) {
191 final INode<K, V> r = RDCSS_READ_ROOT();
192 final Object res = r.rec_lookup(k, hc, 0, null, this);
193 if (!INode.RESTART.equals(res)) {
197 // Tail recursion: lookuphc(k, hc)
201 private Optional<V> removehc(final K k, final V v, final int hc) {
203 final INode<K, V> r = RDCSS_READ_ROOT();
204 final Optional<V> res = r.rec_remove(k, v, hc, 0, null, this);
209 // Tail recursion: return removehc(k, v, hc);
214 * Ensure this instance is read-write, throw UnsupportedOperationException
215 * otherwise. Used by Map-type methods for quick check.
217 private void ensureReadWrite() {
219 throw new UnsupportedOperationException("Attempted to modify a read-only view");
223 boolean isReadOnly() {
230 * Returns a snapshot of this TrieMap. This operation is lock-free and
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.
239 public TrieMap<K, V> snapshot() {
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);
247 // Tail recursion: return snapshot();
252 * Returns a read-only snapshot of this TrieMap. This operation is lock-free
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.
262 * This method is used by other methods such as `size` and `iterator`.
264 public TrieMap<K, V> readOnlySnapshot() {
265 // Is it a snapshot of a read-only snapshot?
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);
277 // Tail recursion: return readOnlySnapshot();
282 public void clear() {
284 final INode<K, V> r = RDCSS_READ_ROOT();
285 if (RDCSS_ROOT(r, r.gcasRead(this), newRootNode())) {
291 int computeHash(final K k) {
292 return equiv.hash(k);
295 boolean equal(final K k1, final K k2) {
296 return equiv.equivalent(k1, k2);
299 V lookup(final K k) {
300 return (V) lookuphc(k, computeHash(k));
304 public V get(final Object k) {
309 public V put(final K key, final V value) {
311 final int hc = computeHash(key);
312 return insertifhc (key, hc, value, null).orElse(null);
315 void add(final K k, final V v) {
316 inserthc(k, computeHash(k), v);
320 public V remove(final Object k) {
322 final int hc = computeHash ((K)k);
323 return removehc ((K)k, (V) null, hc).orElse(null);
327 public V putIfAbsent(final K k, final V v) {
329 final int hc = computeHash (k);
330 return insertifhc (k, hc, v, INode.KEY_ABSENT).orElse(null);
334 public boolean remove(final Object k, final Object v) {
336 final int hc = computeHash ((K)k);
337 return removehc((K)k, (V)v, hc).isPresent();
341 public boolean replace(final K k, final V oldvalue, final V newvalue) {
343 final int hc = computeHash (k);
344 return insertifhc (k, hc, newvalue, oldvalue).isPresent();
348 public V replace(final K k, final V v) {
350 final int hc = computeHash (k);
351 return insertifhc (k, hc, v, INode.KEY_PRESENT).orElse(null);
355 * Return an iterator over a TrieMap.
357 * If this is a read-only snapshot, it would return a read-only iterator.
359 * If it is the original TrieMap or a non-readonly snapshot, it would return
360 * an iterator that would allow for updates.
364 Iterator<Entry<K, V>> iterator() {
365 return readOnly ? new TrieMapReadOnlyIterator<>(0, this) : new TrieMapIterator<>(0, this);
369 * Return an iterator over a TrieMap.
370 * This is a read-only iterator.
374 Iterator<Entry<K, V>> readOnlyIterator() {
375 return new TrieMapReadOnlyIterator<>(0, readOnly ? this : readOnlySnapshot());
378 private int cachedSize() {
379 INode<K, V> r = RDCSS_READ_ROOT ();
380 return r.cachedSize (this);
385 return readOnly ? cachedSize() : readOnlySnapshot().size();
389 public boolean containsKey(final Object key) {
390 return lookup((K) key) != null;
394 public Set<Entry<K, V>> entrySet() {
398 private Object writeReplace() throws ObjectStreamException {
399 return new ExternalForm(this);
402 private static final class RDCSS_Descriptor<K, V> {
404 MainNode<K, V> expectedmain;
406 volatile boolean committed = false;
408 RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
410 this.expectedmain = expectedmain;
416 * This iterator is a read-only one and does not allow for any update
417 * operations on the underlying data structure.
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);
427 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
428 this (level, ct, true);
432 assert (ct.isReadOnly ());
437 public void remove () {
438 throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
442 Entry<K, V> nextEntry(final Entry<K, V> rr) {
443 // Return non-updatable entry
448 private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
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;
459 TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
462 this.mustInit = mustInit;
468 TrieMapIterator (final int level, final TrieMap<K, V> ct) {
469 this (level, ct, true);
474 public boolean hasNext () {
475 return (current != null) || (subiter != null);
479 public Entry<K, V> next () {
481 Entry<K, V> r = null;
482 if (subiter != null) {
486 r = current.kvPair ();
492 final Entry<K, V> rr = r;
493 return nextEntry(rr);
497 // return Iterator.empty ().next ();
502 Entry<K, V> nextEntry(final Entry<K, V> rr) {
503 return new Entry<K, V>() {
504 private V updated = null;
512 public V getValue () {
513 return (updated == null)?rr.getValue (): updated;
517 public V setValue (final V value) {
519 return ct.replace (getKey (), value);
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;
529 stack [depth] = cn.array;
530 stackpos [depth] = -1;
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();
537 } else if (m == null) {
543 private void checkSubiter () {
544 if (!subiter.hasNext ()) {
552 // assert (ct.isReadOnly ());
553 INode<K, V> r = ct.RDCSS_READ_ROOT ();
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);
577 protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
578 return new TrieMapIterator<> (_lev, _ct, _mustInit);
581 protected void dupTo (final TrieMapIterator<K, V> it) {
582 it.level = this.level;
584 it.depth = this.depth;
585 it.current = this.current;
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);
591 // this one needs to be evaluated
592 if (this.subiter == null) {
595 List<Entry<K, V>> lst = toList (this.subiter);
596 this.subiter = lst.iterator ();
597 it.subiter = lst.iterator ();
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.
605 // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
607 // // the case where an LNode is being iterated
613 // } else if (depth == -1) {
618 // while (d <= depth) {
619 // val rem = stack(d).length - 1 - stackpos(d)
621 // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
624 // val it = newIterator(level + 1, ct, false)
625 // it.stack(0) = arr2
626 // it.stackpos(0) = -1
628 // it.advance() // <-- fix it
630 // return Seq(this, it)
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 ());
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"));
655 public void remove () {
656 if (lastReturned != null) {
657 ct.remove (lastReturned.getKey ());
660 throw new IllegalStateException();
667 * Support for EntrySet operations required by the Map interface
669 private final class EntrySet extends AbstractSet<Entry<K, V>> {
672 public Iterator<Entry<K, V>> iterator () {
673 return TrieMap.this.iterator ();
677 public final boolean contains (final Object o) {
678 if (!(o instanceof Entry)) {
681 final Entry<K, V> e = (Entry<K, V>) o;
682 final K k = e.getKey ();
683 final V v = lookup (k);
688 public final boolean remove (final Object o) {
689 if (!(o instanceof Entry)) {
692 final Entry<K, V> e = (Entry<K, V>) o;
693 final K k = e.getKey();
694 return null != TrieMap.this.remove(k);
698 public final int size () {
700 for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
707 public final void clear () {
708 TrieMap.this.clear ();