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 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;
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;
37 import java.util.concurrent.ConcurrentMap;
38 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
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.
44 * @author Roman Levenstein <romixlev@gmail.com>
46 * @param <K> the type of keys maintained by this map
47 * @param <V> the type of mapped values
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;
58 private final EntrySet entrySet = new EntrySet();
59 private final Equivalence<? super K> equiv;
60 private final boolean readOnly;
62 private volatile Object root;
64 private TrieMap(final INode<K, V> r, final Equivalence<? super K> equiv, final boolean readOnly) {
67 this.readOnly = readOnly;
70 TrieMap(final Equivalence<? super K> equiv) {
71 this(newRootNode(), equiv, false);
75 this(Equivalence.equals());
78 /* internal methods */
80 final Equivalence<? super K> equiv() {
84 private static <K,V> INode<K, V> newRootNode() {
85 final Gen gen = new Gen();
86 return new INode<>(gen, new CNode<>(gen));
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);
94 // FIXME: abort = false by default
95 final INode<K, V> readRoot(final boolean abort) {
96 return RDCSS_READ_ROOT(abort);
99 final INode<K, V> readRoot() {
100 return RDCSS_READ_ROOT(false);
103 final INode<K, V> RDCSS_READ_ROOT() {
104 return RDCSS_READ_ROOT(false);
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;
113 checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
114 return RDCSS_Complete(abort);
117 private INode<K, V> RDCSS_Complete(final boolean abort) {
119 final Object r = /* READ */root;
120 if (r instanceof INode) {
121 return (INode<K, V>) r;
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;
131 if (CAS_ROOT(desc, ov)) {
135 // Tail recursion: return RDCSS_Complete(abort);
139 final MainNode<K, V> oldmain = ov.gcasRead(this);
140 if (oldmain == exp) {
141 if (CAS_ROOT(desc, nv)) {
142 desc.committed = true;
146 // Tail recursion: return RDCSS_Complete(abort);
150 if (CAS_ROOT(desc, ov)) {
154 // Tail recursion: return RDCSS_Complete(abort);
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;
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);
176 private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
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);
186 private V lookuphc(final K k, final int hc) {
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);
196 private Optional<V> removehc(final K k, final V v, final int hc) {
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);
207 * Ensure this instance is read-write, throw UnsupportedOperationException
208 * otherwise. Used by Map-type methods for quick check.
210 private void ensureReadWrite() {
212 throw new UnsupportedOperationException("Attempted to modify a read-only view");
216 boolean isReadOnly() {
223 * Returns a snapshot of this TrieMap. This operation is lock-free and
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.
232 public TrieMap<K, V> snapshot() {
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);
240 // Tail recursion: return snapshot();
245 * Returns a read-only snapshot of this TrieMap. This operation is lock-free
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.
255 * This method is used by other methods such as `size` and `iterator`.
257 public TrieMap<K, V> readOnlySnapshot() {
258 // Is it a snapshot of a read-only snapshot?
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);
270 // Tail recursion: return readOnlySnapshot();
275 public void clear() {
278 final INode<K, V> r = RDCSS_READ_ROOT();
279 success = RDCSS_ROOT(r, r.gcasRead(this), newRootNode());
283 int computeHash(final K k) {
284 return equiv.hash(k);
287 boolean equal(final K k1, final K k2) {
288 return equiv.equivalent(k1, k2);
292 public V get(final Object key) {
293 final K k = (K) checkNotNull(key);
294 return lookuphc(k, computeHash(k));
298 public V put(final K key, final V value) {
300 final K k = checkNotNull(key);
301 return insertifhc(k, computeHash(k), checkNotNull(value), null).orElse(null);
304 void add(final K key, final V value) {
305 final K k = checkNotNull(key);
306 inserthc(k, computeHash(k), checkNotNull(value));
310 public V remove(final Object key) {
312 final K k = (K) checkNotNull(key);
313 return removehc(k, (V) null, computeHash(k)).orElse(null);
317 public V putIfAbsent(final K key, final V value) {
319 final K k = checkNotNull(key);
320 return insertifhc(k, computeHash(k), checkNotNull(value), ABSENT).orElse(null);
324 public boolean remove(final Object key, final Object v) {
326 final K k = (K) checkNotNull(key);
327 return removehc(k, (V) checkNotNull(v), computeHash(k)).isPresent();
331 public boolean replace(final K key, final V oldValue, final V newValue) {
333 final K k = checkNotNull(key);
334 return insertifhc(k, computeHash(k), checkNotNull(newValue), checkNotNull(oldValue)).isPresent();
338 public V replace(final K key, final V value) {
340 final K k = checkNotNull(key);
341 return insertifhc (k, computeHash(k), checkNotNull(value), PRESENT).orElse(null);
345 * Return an iterator over a TrieMap.
347 * If this is a read-only snapshot, it would return a read-only iterator.
349 * If it is the original TrieMap or a non-readonly snapshot, it would return
350 * an iterator that would allow for updates.
354 Iterator<Entry<K, V>> iterator() {
355 return readOnly ? new TrieMapReadOnlyIterator<>(0, this) : new TrieMapIterator<>(0, this);
359 * Return an iterator over a TrieMap.
360 * This is a read-only iterator.
364 Iterator<Entry<K, V>> readOnlyIterator() {
365 return new TrieMapReadOnlyIterator<>(0, readOnly ? this : readOnlySnapshot());
368 private int cachedSize() {
369 INode<K, V> r = RDCSS_READ_ROOT ();
370 return r.cachedSize (this);
375 return readOnly ? cachedSize() : readOnlySnapshot().size();
379 public boolean containsKey(final Object key) {
380 return get(key) != null;
384 public Set<Entry<K, V>> entrySet() {
388 private Object writeReplace() throws ObjectStreamException {
389 return new ExternalForm(this);
392 private static final class RDCSS_Descriptor<K, V> {
394 MainNode<K, V> expectedmain;
396 volatile boolean committed = false;
398 RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
400 this.expectedmain = expectedmain;
406 * This iterator is a read-only one and does not allow for any update
407 * operations on the underlying data structure.
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);
417 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
418 this (level, ct, true);
422 assert (ct.isReadOnly ());
427 public void remove () {
428 throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
432 Entry<K, V> nextEntry(final Entry<K, V> rr) {
433 // Return non-updatable entry
438 private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
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 EntryNode<K, V> current = null;
447 private Entry<K, V> lastReturned = null;
449 TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
452 this.mustInit = mustInit;
458 TrieMapIterator (final int level, final TrieMap<K, V> ct) {
459 this (level, ct, true);
464 public boolean hasNext() {
465 return (current != null) || (subiter != null);
469 public Entry<K, V> next() {
471 throw new NoSuchElementException();
474 Entry<K, V> r = null;
475 if (subiter != null) {
485 final Entry<K, V> rr = r;
486 return nextEntry(rr);
491 Entry<K, V> nextEntry(final Entry<K, V> rr) {
492 return new Entry<K, V>() {
493 private V updated = null;
501 public V getValue () {
502 return (updated == null) ? rr.getValue (): updated;
506 public V setValue (final V value) {
508 return ct.replace (getKey (), value);
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;
518 stack [depth] = cn.array;
519 stackpos [depth] = -1;
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();
526 } else if (m == null) {
532 private void checkSubiter () {
533 if (!subiter.hasNext ()) {
541 // assert (ct.isReadOnly ());
542 INode<K, V> r = ct.RDCSS_READ_ROOT ();
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);
566 protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
567 return new TrieMapIterator<> (_lev, _ct, _mustInit);
570 protected void dupTo (final TrieMapIterator<K, V> it) {
571 it.level = this.level;
573 it.depth = this.depth;
574 it.current = this.current;
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);
580 // this one needs to be evaluated
581 if (this.subiter == null) {
584 List<Entry<K, V>> lst = toList (this.subiter);
585 this.subiter = lst.iterator ();
586 it.subiter = lst.iterator ();
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.
594 // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
596 // // the case where an LNode is being iterated
602 // } else if (depth == -1) {
607 // while (d <= depth) {
608 // val rem = stack(d).length - 1 - stackpos(d)
610 // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
613 // val it = newIterator(level + 1, ct, false)
614 // it.stack(0) = arr2
615 // it.stackpos(0) = -1
617 // it.advance() // <-- fix it
619 // return Seq(this, it)
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());
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"));
644 public void remove() {
645 checkState(lastReturned != null);
646 ct.remove(lastReturned.getKey());
652 * Support for EntrySet operations required by the Map interface
654 private final class EntrySet extends AbstractSet<Entry<K, V>> {
656 public Iterator<Entry<K, V>> iterator() {
657 return TrieMap.this.iterator ();
661 public final boolean contains(final Object o) {
662 if (!(o instanceof Entry)) {
666 final Entry<?, ?> e = (Entry<?, ?>) o;
667 if (e.getKey() == null) {
670 final V v = get(e.getKey());
671 return v != null && v.equals(e.getValue());
675 public final boolean remove(final Object o) {
676 if (!(o instanceof Entry)) {
679 final Entry<?, ?> e = (Entry<K, V>) o;
680 final Object key = e.getKey();
684 final Object value = e.getValue();
689 return TrieMap.this.remove(key, value);
693 public final int size () {
694 return Iterators.size(iterator());
698 public final void clear () {
699 TrieMap.this.clear ();