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 java.io.IOException;
19 import java.io.ObjectInputStream;
20 import java.io.ObjectOutputStream;
21 import java.io.Serializable;
22 import java.lang.reflect.Field;
23 import java.util.AbstractMap;
24 import java.util.AbstractSet;
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.Iterator;
28 import java.util.List;
31 import java.util.concurrent.ConcurrentMap;
32 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
35 * This is a port of Scala's TrieMap class from the Scala Collections library.
37 * @author Roman Levenstein <romixlev@gmail.com>
42 @SuppressWarnings({"unchecked", "rawtypes", "unused"})
43 public class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
44 private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root");
45 private static final long serialVersionUID = 1L;
46 private static final Field READONLY_FIELD;
47 private static final TrieMap EMPTY = new TrieMap();
52 f = TrieMap.class.getDeclaredField("readOnly");
53 } catch (NoSuchFieldException e) {
54 throw new ExceptionInInitializerError(e);
55 } catch (SecurityException e) {
56 throw new ExceptionInInitializerError(e);
58 f.setAccessible(true);
65 private transient final EntrySet entrySet = new EntrySet ();
67 public static <K,V> TrieMap<K,V> empty () {
71 // static class MangledHashing<K> extends Hashing<K> {
73 // return util.hashing.byteswap32(k);
77 private static class RDCSS_Descriptor<K, V> {
79 MainNode<K, V> expectedmain;
81 volatile boolean committed = false;
83 public RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
85 this.expectedmain = expectedmain;
90 private final Equivalence<? super K> equiv;
92 private transient volatile Object root;
93 private final transient boolean readOnly;
95 TrieMap (final Object r, final Equivalence<? super K> equiv, final boolean readOnly) {
98 this.readOnly = readOnly;
103 this(newRootNode(), Equivalence.equals(), false);
106 /* internal methods */
108 // private void writeObject(java.io.ObjectOutputStream out) {
109 // out.writeObject(hashf);
110 // out.writeObject(ef);
112 // Iterator it = iterator();
113 // while (it.hasNext) {
114 // val (k, v) = it.next();
115 // out.writeObject(k);
116 // out.writeObject(v);
118 // out.writeObject(TrieMapSerializationEnd);
121 // private TrieMap readObject(java.io.ObjectInputStream in) {
122 // root = INode.newRootNode();
123 // rootupdater = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class,
124 // Object.class, "root");
126 // hashingobj = in.readObject();
127 // equalityobj = in.readObject();
129 // Object obj = null;
131 // obj = in.readObject();
132 // if (obj != TrieMapSerializationEnd) {
134 // V = (V)in.readObject();
137 // } while (obj != TrieMapSerializationEnd);
140 private static <K,V> INode<K,V> newRootNode() {
141 final Gen gen = new Gen();
142 return new INode<>(gen, new CNode<>(gen));
145 final boolean CAS_ROOT (final Object ov, final Object nv) {
147 throw new IllegalStateException("Attempted to modify a read-only snapshot");
149 return ROOT_UPDATER.compareAndSet (this, ov, nv);
152 // FIXME: abort = false by default
153 final INode<K, V> readRoot (final boolean abort) {
154 return RDCSS_READ_ROOT (abort);
157 final INode<K, V> readRoot () {
158 return RDCSS_READ_ROOT (false);
161 final INode<K, V> RDCSS_READ_ROOT () {
162 return RDCSS_READ_ROOT (false);
165 final INode<K, V> RDCSS_READ_ROOT (final boolean abort) {
166 Object r = /* READ */root;
167 if (r instanceof INode) {
168 return (INode<K, V>) r;
169 } else if (r instanceof RDCSS_Descriptor) {
170 return RDCSS_Complete (abort);
172 throw new RuntimeException ("Should not happen");
175 private final INode<K, V> RDCSS_Complete (final boolean abort) {
177 Object v = /* READ */root;
178 if (v instanceof INode) {
179 return (INode<K, V>) v;
180 } else if (v instanceof RDCSS_Descriptor) {
181 RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
182 INode<K, V> ov = desc.old;
183 MainNode<K, V> exp = desc.expectedmain;
184 INode<K, V> nv = desc.nv;
187 if (CAS_ROOT (desc, ov)) {
190 // return RDCSS_Complete (abort);
195 MainNode<K, V> oldmain = ov.gcasRead (this);
196 if (oldmain == exp) {
197 if (CAS_ROOT (desc, nv)) {
198 desc.committed = true;
201 // return RDCSS_Complete (abort);
206 if (CAS_ROOT (desc, ov)) {
209 // return RDCSS_Complete (abort);
218 throw new RuntimeException ("Should not happen");
222 private boolean RDCSS_ROOT (final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
223 RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
224 if (CAS_ROOT (ov, desc)) {
225 RDCSS_Complete (false);
226 return /* READ */desc.committed;
232 private void inserthc (final K k, final int hc, final V v) {
234 INode<K, V> r = RDCSS_READ_ROOT ();
235 if (!r.rec_insert (k, v, hc, 0, null, r.gen, this)) {
236 // inserthc (k, hc, v);
244 private Option<V> insertifhc (final K k, final int hc, final V v, final Object cond) {
246 INode<K, V> r = RDCSS_READ_ROOT ();
248 Option<V> ret = r.rec_insertif (k, v, hc, cond, 0, null, r.gen, this);
250 // return insertifhc (k, hc, v, cond);
259 private Object lookuphc(final K k, final int hc) {
261 final INode<K, V> r = RDCSS_READ_ROOT ();
262 final Object res = r.rec_lookup(k, hc, 0, null, r.gen, this);
263 if (!INode.RESTART.equals(res)) {
267 // Tail recursion: lookuphc(k, hc)
271 private Option<V> removehc (final K k, final V v, final int hc) {
273 INode<K, V> r = RDCSS_READ_ROOT ();
274 Option<V> res = r.rec_remove (k, v, hc, 0, null, r.gen, this);
278 // return removehc (k, v, hc);
286 * Ensure this instance is read-write, throw UnsupportedOperationException
287 * otherwise. Used by Map-type methods for quick check.
289 private void ensureReadWrite() {
291 throw new UnsupportedOperationException("Attempted to modify a read-only view");
295 public String string () {
296 // RDCSS_READ_ROOT().string(0);
302 // public Seq<V> seq() {
306 // override def par = new ParTrieMap(this)
308 // static TrieMap empty() {
309 // return new TrieMap();
312 final boolean isReadOnly () {
316 final boolean nonReadOnly () {
321 * Returns a snapshot of this TrieMap. This operation is lock-free and
324 * The snapshot is lazily updated - the first time some branch in the
325 * snapshot or this TrieMap are accessed, they are rewritten. This means
326 * that the work of rebuilding both the snapshot and this TrieMap is
327 * distributed across all the threads doing updates or accesses subsequent
328 * to the snapshot creation.
331 final public TrieMap<K, V> snapshot () {
333 INode<K, V> r = RDCSS_READ_ROOT ();
334 final MainNode<K, V> expmain = r.gcasRead (this);
335 if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
336 return new TrieMap<> (r.copyToGen (new Gen (), this), equiv, readOnly);
338 // return snapshot ();
346 * Returns a read-only snapshot of this TrieMap. This operation is lock-free
349 * The snapshot is lazily updated - the first time some branch of this
350 * TrieMap are accessed, it is rewritten. The work of creating the snapshot
351 * is thus distributed across subsequent updates and accesses on this
352 * TrieMap by all threads. Note that the snapshot itself is never rewritten
353 * unlike when calling the `snapshot` method, but the obtained snapshot
354 * cannot be modified.
356 * This method is used by other methods such as `size` and `iterator`.
358 final public TrieMap<K, V> readOnlySnapshot () {
359 // Is it a snapshot of a read-only snapshot?
360 if(!nonReadOnly ()) {
365 INode<K, V> r = RDCSS_READ_ROOT ();
366 MainNode<K, V> expmain = r.gcasRead (this);
367 if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
368 return new TrieMap<> (r, equiv, true);
370 // return readOnlySnapshot ();
377 final public void clear () {
379 INode<K, V> r = RDCSS_READ_ROOT ();
380 if (!RDCSS_ROOT(r, r.gcasRead(this), newRootNode())) {
388 int computeHash(final K k) {
389 return equiv.hash(k);
392 boolean equal(final K k1, final K k2) {
393 return equiv.equivalent(k1, k2);
396 final V lookup (final K k) {
397 int hc = computeHash (k);
398 // return (V) lookuphc (k, hc);
399 Object o = lookuphc (k, hc);
400 if(o instanceof Some) {
401 return ((Some<V>)o).get ();
402 } else if(o instanceof None) {
410 final public V get (final Object k) {
414 final public Option<V> putOpt(final Object key, final Object value) {
415 int hc = computeHash ((K)key);
416 return insertifhc ((K)key, hc, (V)value, null);
420 final public V put (final Object key, final Object value) {
422 int hc = computeHash ((K)key);
423 Option<V> ov = insertifhc ((K)key, hc, (V)value, null);
424 if(ov instanceof Some) {
425 Some<V> sv = (Some<V>)ov;
432 final public void update (final K k, final V v) {
433 int hc = computeHash (k);
437 final public TrieMap<K, V> add (final K k, final V v) {
442 final Option<V> removeOpt (final K k) {
443 int hc = computeHash (k);
444 return removehc (k, (V) null, hc);
448 final public V remove (final Object k) {
450 int hc = computeHash ((K)k);
451 Option<V> ov = removehc ((K)k, (V) null, hc);
452 if(ov instanceof Some) {
453 Some<V> sv = (Some<V>)ov;
460 // final public TrieMap<K, V> remove (Object k) {
465 final public Option<V> putIfAbsentOpt (final K k, final V v) {
466 int hc = computeHash (k);
467 return insertifhc (k, hc, v, INode.KEY_ABSENT);
471 final public V putIfAbsent (final Object k, final Object v) {
473 int hc = computeHash ((K)k);
474 Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_ABSENT);
475 if(ov instanceof Some) {
476 Some<V> sv = (Some<V>)ov;
484 public boolean remove (final Object k, final Object v) {
486 int hc = computeHash ((K)k);
487 return removehc ((K)k, (V)v, hc).nonEmpty ();
491 public boolean replace (final K k, final V oldvalue, final V newvalue) {
493 int hc = computeHash (k);
494 return insertifhc (k, hc, newvalue, oldvalue).nonEmpty ();
497 public Option<V> replaceOpt (final K k, final V v) {
498 int hc = computeHash (k);
499 return insertifhc (k, hc, v, INode.KEY_PRESENT);
503 public V replace (final Object k, final Object v) {
505 int hc = computeHash ((K)k);
506 Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_PRESENT);
507 if(ov instanceof Some) {
508 Some<V> sv = (Some<V>)ov;
516 * Return an iterator over a TrieMap.
518 * If this is a read-only snapshot, it would return a read-only iterator.
520 * If it is the original TrieMap or a non-readonly snapshot, it would return
521 * an iterator that would allow for updates.
525 public Iterator<Map.Entry<K, V>> iterator () {
526 if (!nonReadOnly ()) {
527 return readOnlySnapshot ().readOnlyIterator ();
529 return new TrieMapIterator<> (0, this);
534 * Return an iterator over a TrieMap.
535 * This is a read-only iterator.
539 public Iterator<Map.Entry<K, V>> readOnlyIterator () {
540 if (nonReadOnly ()) {
541 return readOnlySnapshot ().readOnlyIterator ();
543 return new TrieMapReadOnlyIterator<> (0, this);
547 private int cachedSize () {
548 INode<K, V> r = RDCSS_READ_ROOT ();
549 return r.cachedSize (this);
554 if (nonReadOnly ()) {
555 return readOnlySnapshot ().size ();
557 return cachedSize ();
561 String stringPrefix () {
566 * This iterator is a read-only one and does not allow for any update
567 * operations on the underlying data structure.
572 private static class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
573 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
574 super (level, ct, mustInit);
577 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
578 this (level, ct, true);
582 assert (ct.isReadOnly ());
587 public void remove () {
588 throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
592 Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
593 // Return non-updatable entry
598 private static class TrieMapIterator<K, V> implements java.util.Iterator<Map.Entry<K, V>> {
600 protected TrieMap<K, V> ct;
601 private final boolean mustInit;
602 private final BasicNode[][] stack = new BasicNode[7][];
603 private final int[] stackpos = new int[7];
604 private int depth = -1;
605 private Iterator<Map.Entry<K, V>> subiter = null;
606 private KVNode<K, V> current = null;
607 private Map.Entry<K, V> lastReturned = null;
609 TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
612 this.mustInit = mustInit;
618 TrieMapIterator (final int level, final TrieMap<K, V> ct) {
619 this (level, ct, true);
624 public boolean hasNext () {
625 return (current != null) || (subiter != null);
629 public Map.Entry<K, V> next () {
631 Map.Entry<K, V> r = null;
632 if (subiter != null) {
636 r = current.kvPair ();
642 final Map.Entry<K, V> rr = r;
643 return nextEntry(rr);
647 // return Iterator.empty ().next ();
652 Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
653 return new Map.Entry<K, V>() {
654 private V updated = null;
662 public V getValue () {
663 return (updated == null)?rr.getValue (): updated;
667 public V setValue (final V value) {
669 return ct.replace (getKey (), value);
674 private void readin (final INode<K, V> in) {
675 MainNode<K, V> m = in.gcasRead (ct);
676 if (m instanceof CNode) {
677 CNode<K, V> cn = (CNode<K, V>) m;
679 stack [depth] = cn.array;
680 stackpos [depth] = -1;
682 } else if (m instanceof TNode) {
683 current = (TNode<K, V>) m;
684 } else if (m instanceof LNode) {
685 subiter = ((LNode<K, V>) m).iterator();
687 } else if (m == null) {
693 private void checkSubiter () {
694 if (!subiter.hasNext ()) {
702 // assert (ct.isReadOnly ());
703 INode<K, V> r = ct.RDCSS_READ_ROOT ();
709 int npos = stackpos [depth] + 1;
710 if (npos < stack [depth].length) {
711 stackpos [depth] = npos;
712 BasicNode elem = stack [depth] [npos];
713 if (elem instanceof SNode) {
714 current = (SNode<K, V>) elem;
715 } else if (elem instanceof INode) {
716 readin ((INode<K, V>) elem);
727 protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
728 return new TrieMapIterator<> (_lev, _ct, _mustInit);
731 protected void dupTo (final TrieMapIterator<K, V> it) {
732 it.level = this.level;
734 it.depth = this.depth;
735 it.current = this.current;
737 // these need a deep copy
738 System.arraycopy (this.stack, 0, it.stack, 0, 7);
739 System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
741 // this one needs to be evaluated
742 if (this.subiter == null) {
745 List<Map.Entry<K, V>> lst = toList (this.subiter);
746 this.subiter = lst.iterator ();
747 it.subiter = lst.iterator ();
751 // /** Returns a sequence of iterators over subsets of this iterator.
752 // * It's used to ease the implementation of splitters for a parallel
753 // version of the TrieMap.
755 // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
757 // // the case where an LNode is being iterated
763 // } else if (depth == -1) {
768 // while (d <= depth) {
769 // val rem = stack(d).length - 1 - stackpos(d)
771 // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
774 // val it = newIterator(level + 1, ct, false)
775 // it.stack(0) = arr2
776 // it.stackpos(0) = -1
778 // it.advance() // <-- fix it
780 // return Seq(this, it)
788 private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
789 ArrayList<Entry<K, V>> list = new ArrayList<> ();
790 while (it.hasNext ()) {
791 list.add (it.next ());
797 System.out.println ("ctrie iterator");
798 System.out.println (Arrays.toString (stackpos));
799 System.out.println ("depth: " + depth);
800 System.out.println ("curr.: " + current);
801 // System.out.println(stack.mkString("\n"));
805 public void remove () {
806 if (lastReturned != null) {
807 ct.remove (lastReturned.getKey ());
810 throw new IllegalStateException();
816 /** Only used for ctrie serialization. */
817 // @SerialVersionUID(0L - 7237891413820527142L)
818 private static long TrieMapSerializationEnd = 0L - 7237891413820527142L;
822 public boolean containsKey (final Object key) {
823 return lookup ((K) key) != null;
828 public Set<Map.Entry<K, V>> entrySet () {
833 * Support for EntrySet operations required by the Map interface
836 final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
839 public Iterator<Map.Entry<K, V>> iterator () {
840 return TrieMap.this.iterator ();
844 public final boolean contains (final Object o) {
845 if (!(o instanceof Map.Entry)) {
848 final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
849 final K k = e.getKey ();
850 final V v = lookup (k);
855 public final boolean remove (final Object o) {
856 if (!(o instanceof Map.Entry)) {
859 final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
860 final K k = e.getKey ();
861 return null != TrieMap.this.remove (k);
865 public final int size () {
867 for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
874 public final void clear () {
875 TrieMap.this.clear ();
879 private void readObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
880 inputStream.defaultReadObject();
881 this.root = newRootNode();
883 final boolean ro = inputStream.readBoolean();
884 final int size = inputStream.readInt();
885 for (int i = 0; i < size; ++i) {
886 final K key = (K)inputStream.readObject();
887 final V value = (V)inputStream.readObject();
891 // Propagate the read-only bit
893 READONLY_FIELD.setBoolean(this, ro);
894 } catch (IllegalAccessException e) {
895 throw new IOException("Failed to set read-only flag", e);
899 private void writeObject(final ObjectOutputStream outputStream) throws IOException {
900 outputStream.defaultWriteObject();
902 final Map<K, V> ro = readOnlySnapshot();
903 outputStream.writeBoolean(isReadOnly());
904 outputStream.writeInt(ro.size());
906 for (Entry<K, V> e : ro.entrySet()) {
907 outputStream.writeObject(e.getKey());
908 outputStream.writeObject(e.getValue());