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;
22 import com.google.common.annotations.Beta;
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.Iterator;
29 import java.util.List;
30 import java.util.NoSuchElementException;
31 import java.util.Optional;
33 import java.util.concurrent.ConcurrentMap;
36 * This is a port of Scala's TrieMap class from the Scala Collections library. This implementation does not support
37 * null keys nor null values.
39 * @author Aleksandar Prokopec (original Scala implementation)
40 * @author Roman Levenstein (original Java 6 port)
41 * @author Robert Varga
43 * @param <K> the type of keys maintained by this map
44 * @param <V> the type of mapped values
47 public abstract class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
48 private static final long serialVersionUID = 1L;
53 private final EntrySet entrySet = new EntrySet();
54 private final Equivalence<? super K> equiv;
56 TrieMap(final Equivalence<? super K> equiv) {
60 public static <K, V> TrieMap<K, V> create() {
61 return new MutableTrieMap<>(Equivalence.equals());
65 * Returns a snapshot of this TrieMap. This operation is lock-free and
68 * The snapshot is lazily updated - the first time some branch in the
69 * snapshot or this TrieMap are accessed, they are rewritten. This means
70 * that the work of rebuilding both the snapshot and this TrieMap is
71 * distributed across all the threads doing updates or accesses subsequent
72 * to the snapshot creation.
74 public abstract TrieMap<K, V> mutableSnapshot();
77 * Returns a read-only snapshot of this TrieMap. This operation is lock-free
80 * The snapshot is lazily updated - the first time some branch of this
81 * TrieMap are accessed, it is rewritten. The work of creating the snapshot
82 * is thus distributed across subsequent updates and accesses on this
83 * TrieMap by all threads. Note that the snapshot itself is never rewritten
84 * unlike when calling the `snapshot` method, but the obtained snapshot
87 * This method is used by other methods such as `size` and `iterator`.
89 public abstract ImmutableTrieMap<K, V> immutableSnapshot();
92 public final boolean containsKey(final Object key) {
93 return get(key) != null;
97 public final boolean containsValue(final Object value) {
98 return super.containsValue(checkNotNull(value));
102 public final Set<Entry<K, V>> entrySet() {
107 public final V get(final Object key) {
108 @SuppressWarnings("unchecked")
109 final K k = (K) checkNotNull(key);
110 return lookuphc(k, computeHash(k));
114 public abstract void clear();
117 public abstract V put(K key, V value);
120 public abstract V putIfAbsent(K key, V value);
123 public abstract V remove(Object key);
126 public abstract boolean remove(Object key, Object value);
129 public abstract boolean replace(K key, V oldValue, V newValue);
132 public abstract V replace(K key, V value);
135 public abstract int size();
137 /* internal methods implemented by subclasses */
139 abstract boolean isReadOnly();
141 abstract INode<K, V> RDCSS_READ_ROOT(boolean abort);
143 /* internal methods provided for subclasses */
145 @SuppressWarnings("null")
146 static <V> V toNullable(final Optional<V> opt) {
147 return opt.orElse(null);
150 final int computeHash(final K k) {
151 return equiv.hash(k);
154 final Object writeReplace() throws ObjectStreamException {
155 return new SerializationProxy(immutableSnapshot(), isReadOnly());
158 /* package-protected utility methods */
160 final Equivalence<? super K> equiv() {
164 final INode<K, V> readRoot() {
165 return RDCSS_READ_ROOT(false);
168 // FIXME: abort = false by default
169 final INode<K, V> readRoot(final boolean abort) {
170 return RDCSS_READ_ROOT(abort);
173 final INode<K, V> RDCSS_READ_ROOT() {
174 return RDCSS_READ_ROOT(false);
177 final boolean equal(final K k1, final K k2) {
178 return equiv.equivalent(k1, k2);
181 /* private implementation methods */
183 @SuppressWarnings("unchecked")
184 private V lookuphc(final K k, final int hc) {
187 // Keep looping as long as RESTART is being indicated
188 res = RDCSS_READ_ROOT().rec_lookup(k, hc, 0, null, this);
189 } while (res == RESTART);
195 * Return an iterator over a TrieMap.
197 * If this is a read-only snapshot, it would return a read-only iterator.
199 * If it is the original TrieMap or a non-readonly snapshot, it would return
200 * an iterator that would allow for updates.
204 Iterator<Entry<K, V>> iterator() {
205 // FIXME: it would be nice to have a ReadWriteTrieMap with read-only iterator
206 return isReadOnly() ? new TrieMapReadOnlyIterator<>(0, this) : new TrieMapIterator<>(0, this);
210 * Return an iterator over a TrieMap.
211 * This is a read-only iterator.
215 final Iterator<Entry<K, V>> readOnlyIterator() {
216 return new TrieMapReadOnlyIterator<>(0, immutableSnapshot());
220 * This iterator is a read-only one and does not allow for any update
221 * operations on the underlying data structure.
226 private static final class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
227 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
228 super (level, ct, mustInit);
231 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
232 this (level, ct, true);
236 assert (ct.isReadOnly ());
241 public void remove () {
242 throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
246 Entry<K, V> nextEntry(final Entry<K, V> rr) {
247 // Return non-updatable entry
252 private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
254 protected TrieMap<K, V> ct;
255 private final boolean mustInit;
256 private final BasicNode[][] stack = new BasicNode[7][];
257 private final int[] stackpos = new int[7];
258 private int depth = -1;
259 private Iterator<Entry<K, V>> subiter = null;
260 private EntryNode<K, V> current = null;
261 private Entry<K, V> lastReturned = null;
263 TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
266 this.mustInit = mustInit;
272 TrieMapIterator (final int level, final TrieMap<K, V> ct) {
273 this (level, ct, true);
278 public boolean hasNext() {
279 return (current != null) || (subiter != null);
283 public Entry<K, V> next() {
285 throw new NoSuchElementException();
289 if (subiter != null) {
299 final Entry<K, V> rr = r;
300 return nextEntry(rr);
305 Entry<K, V> nextEntry(final Entry<K, V> rr) {
306 return new Entry<K, V>() {
307 @SuppressWarnings("null")
308 private V updated = null;
316 public V getValue () {
317 return (updated == null) ? rr.getValue (): updated;
321 public V setValue (final V value) {
323 return ct.replace (getKey (), value);
328 private void readin (final INode<K, V> in) {
329 MainNode<K, V> m = in.gcasRead (ct);
330 if (m instanceof CNode) {
331 CNode<K, V> cn = (CNode<K, V>) m;
333 stack [depth] = cn.array;
334 stackpos [depth] = -1;
336 } else if (m instanceof TNode) {
337 current = (TNode<K, V>) m;
338 } else if (m instanceof LNode) {
339 subiter = ((LNode<K, V>) m).iterator();
341 } else if (m == null) {
347 private void checkSubiter () {
348 if (!subiter.hasNext ()) {
356 // assert (ct.isReadOnly ());
357 readin(ct.RDCSS_READ_ROOT());
362 int npos = stackpos [depth] + 1;
363 if (npos < stack [depth].length) {
364 stackpos [depth] = npos;
365 BasicNode elem = stack [depth] [npos];
366 if (elem instanceof SNode) {
367 current = (SNode<K, V>) elem;
368 } else if (elem instanceof INode) {
369 readin ((INode<K, V>) elem);
380 protected TrieMapIterator<K, V> newIterator(final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
381 return new TrieMapIterator<> (_lev, _ct, _mustInit);
384 protected void dupTo(final TrieMapIterator<K, V> it) {
385 it.level = this.level;
387 it.depth = this.depth;
388 it.current = this.current;
390 // these need a deep copy
391 System.arraycopy (this.stack, 0, it.stack, 0, 7);
392 System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
394 // this one needs to be evaluated
395 if (this.subiter == null) {
398 List<Entry<K, V>> lst = toList (this.subiter);
399 this.subiter = lst.iterator ();
400 it.subiter = lst.iterator ();
404 // /** Returns a sequence of iterators over subsets of this iterator.
405 // * It's used to ease the implementation of splitters for a parallel
406 // version of the TrieMap.
408 // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
410 // // the case where an LNode is being iterated
416 // } else if (depth == -1) {
421 // while (d <= depth) {
422 // val rem = stack(d).length - 1 - stackpos(d)
424 // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
427 // val it = newIterator(level + 1, ct, false)
428 // it.stack(0) = arr2
429 // it.stackpos(0) = -1
431 // it.advance() // <-- fix it
433 // return Seq(this, it)
441 private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
442 ArrayList<Entry<K, V>> list = new ArrayList<> ();
443 while (it.hasNext ()) {
444 list.add (it.next());
450 public void remove() {
451 checkState(lastReturned != null);
452 ct.remove(lastReturned.getKey());
458 * Support for EntrySet operations required by the Map interface
460 private final class EntrySet extends AbstractSet<Entry<K, V>> {
462 public Iterator<Entry<K, V>> iterator() {
463 return TrieMap.this.iterator ();
467 public final boolean contains(final Object o) {
468 if (!(o instanceof Entry)) {
472 final Entry<?, ?> e = (Entry<?, ?>) o;
473 if (e.getKey() == null) {
476 final V v = get(e.getKey());
477 return v != null && v.equals(e.getValue());
481 public final boolean remove(final Object o) {
482 if (!(o instanceof Entry)) {
485 final Entry<?, ?> e = (Entry<?, ?>) o;
486 final Object key = e.getKey();
490 final Object value = e.getValue();
495 return TrieMap.this.remove(key, value);
499 public final int size () {
500 return TrieMap.this.size();
504 public final void clear () {
505 TrieMap.this.clear ();