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;
30 import java.util.NoSuchElementException;
32 import java.util.concurrent.ConcurrentMap;
33 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
36 * This is a port of Scala's TrieMap class from the Scala Collections library.
38 * @author Roman Levenstein <romixlev@gmail.com>
43 @SuppressWarnings({"unchecked", "rawtypes", "unused"})
44 public class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
45 private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root");
46 private static final long serialVersionUID = 1L;
47 private static final Field READONLY_FIELD;
48 private static final TrieMap EMPTY = new TrieMap();
53 f = TrieMap.class.getDeclaredField("readOnly");
54 } catch (NoSuchFieldException e) {
55 throw new ExceptionInInitializerError(e);
56 } catch (SecurityException e) {
57 throw new ExceptionInInitializerError(e);
59 f.setAccessible(true);
66 private transient final EntrySet entrySet = new EntrySet ();
68 public static <K,V> TrieMap<K,V> empty () {
72 // static class MangledHashing<K> extends Hashing<K> {
74 // return util.hashing.byteswap32(k);
78 private static class RDCSS_Descriptor<K, V> {
80 MainNode<K, V> expectedmain;
82 volatile boolean committed = false;
84 public RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
86 this.expectedmain = expectedmain;
91 private final Hashing<K> hashingobj;
92 private final Equiv<K> equalityobj;
94 Hashing<K> hashing () {
98 Equiv<K> equality () {
102 private transient volatile Object root;
103 private final transient boolean readOnly;
105 TrieMap (final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
106 this.hashingobj = hashf;
107 this.equalityobj = ef;
108 this.readOnly = readOnly;
111 TrieMap (final Object r, final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
112 this(hashf, ef, readOnly);
116 public TrieMap (final Hashing<K> hashf, final Equiv<K> ef) {
117 this(INode.newRootNode(), hashf, ef, false);
121 this (new Hashing.Default<K>(), Equiv.universal);
124 /* internal methods */
126 // private void writeObject(java.io.ObjectOutputStream out) {
127 // out.writeObject(hashf);
128 // out.writeObject(ef);
130 // Iterator it = iterator();
131 // while (it.hasNext) {
132 // val (k, v) = it.next();
133 // out.writeObject(k);
134 // out.writeObject(v);
136 // out.writeObject(TrieMapSerializationEnd);
139 // private TrieMap readObject(java.io.ObjectInputStream in) {
140 // root = INode.newRootNode();
141 // rootupdater = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class,
142 // Object.class, "root");
144 // hashingobj = in.readObject();
145 // equalityobj = in.readObject();
147 // Object obj = null;
149 // obj = in.readObject();
150 // if (obj != TrieMapSerializationEnd) {
152 // V = (V)in.readObject();
155 // } while (obj != TrieMapSerializationEnd);
158 final boolean CAS_ROOT (final Object ov, final Object nv) {
160 throw new IllegalStateException("Attempted to modify a read-only snapshot");
162 return ROOT_UPDATER.compareAndSet (this, ov, nv);
165 // FIXME: abort = false by default
166 final INode<K, V> readRoot (final boolean abort) {
167 return RDCSS_READ_ROOT (abort);
170 final INode<K, V> readRoot () {
171 return RDCSS_READ_ROOT (false);
174 final INode<K, V> RDCSS_READ_ROOT () {
175 return RDCSS_READ_ROOT (false);
178 final INode<K, V> RDCSS_READ_ROOT (final boolean abort) {
179 Object r = /* READ */root;
180 if (r instanceof INode) {
181 return (INode<K, V>) r;
182 } else if (r instanceof RDCSS_Descriptor) {
183 return RDCSS_Complete (abort);
185 throw new RuntimeException ("Should not happen");
188 private final INode<K, V> RDCSS_Complete (final boolean abort) {
190 Object v = /* READ */root;
191 if (v instanceof INode) {
192 return (INode<K, V>) v;
193 } else if (v instanceof RDCSS_Descriptor) {
194 RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
195 INode<K, V> ov = desc.old;
196 MainNode<K, V> exp = desc.expectedmain;
197 INode<K, V> nv = desc.nv;
200 if (CAS_ROOT (desc, ov)) {
203 // return RDCSS_Complete (abort);
208 MainNode<K, V> oldmain = ov.gcasRead (this);
209 if (oldmain == exp) {
210 if (CAS_ROOT (desc, nv)) {
211 desc.committed = true;
214 // return RDCSS_Complete (abort);
219 if (CAS_ROOT (desc, ov)) {
222 // return RDCSS_Complete (abort);
231 throw new RuntimeException ("Should not happen");
235 private boolean RDCSS_ROOT (final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
236 RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
237 if (CAS_ROOT (ov, desc)) {
238 RDCSS_Complete (false);
239 return /* READ */desc.committed;
245 private void inserthc (final K k, final int hc, final V v) {
247 INode<K, V> r = RDCSS_READ_ROOT ();
248 if (!r.rec_insert (k, v, hc, 0, null, r.gen, this)) {
249 // inserthc (k, hc, v);
257 private Option<V> insertifhc (final K k, final int hc, final V v, final Object cond) {
259 INode<K, V> r = RDCSS_READ_ROOT ();
261 Option<V> ret = r.rec_insertif (k, v, hc, cond, 0, null, r.gen, this);
263 // return insertifhc (k, hc, v, cond);
272 private Object lookuphc(final K k, final int hc) {
274 final INode<K, V> r = RDCSS_READ_ROOT ();
275 final Object res = r.rec_lookup(k, hc, 0, null, r.gen, this);
276 if (!INode.RESTART.equals(res)) {
280 // Tail recursion: lookuphc(k, hc)
284 private Option<V> removehc (final K k, final V v, final int hc) {
286 INode<K, V> r = RDCSS_READ_ROOT ();
287 Option<V> res = r.rec_remove (k, v, hc, 0, null, r.gen, this);
291 // return removehc (k, v, hc);
299 * Ensure this instance is read-write, throw UnsupportedOperationException
300 * otherwise. Used by Map-type methods for quick check.
302 private void ensureReadWrite() {
304 throw new UnsupportedOperationException("Attempted to modify a read-only view");
308 public String string () {
309 // RDCSS_READ_ROOT().string(0);
315 // public Seq<V> seq() {
319 // override def par = new ParTrieMap(this)
321 // static TrieMap empty() {
322 // return new TrieMap();
325 final boolean isReadOnly () {
329 final boolean nonReadOnly () {
334 * Returns a snapshot of this TrieMap. This operation is lock-free and
337 * The snapshot is lazily updated - the first time some branch in the
338 * snapshot or this TrieMap are accessed, they are rewritten. This means
339 * that the work of rebuilding both the snapshot and this TrieMap is
340 * distributed across all the threads doing updates or accesses subsequent
341 * to the snapshot creation.
344 final public TrieMap<K, V> snapshot () {
346 INode<K, V> r = RDCSS_READ_ROOT ();
347 final MainNode<K, V> expmain = r.gcasRead (this);
348 if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
349 return new TrieMap<> (r.copyToGen (new Gen (), this), hashing (), equality (), readOnly);
351 // return snapshot ();
359 * Returns a read-only snapshot of this TrieMap. This operation is lock-free
362 * The snapshot is lazily updated - the first time some branch of this
363 * TrieMap are accessed, it is rewritten. The work of creating the snapshot
364 * is thus distributed across subsequent updates and accesses on this
365 * TrieMap by all threads. Note that the snapshot itself is never rewritten
366 * unlike when calling the `snapshot` method, but the obtained snapshot
367 * cannot be modified.
369 * This method is used by other methods such as `size` and `iterator`.
371 final public TrieMap<K, V> readOnlySnapshot () {
372 // Is it a snapshot of a read-only snapshot?
373 if(!nonReadOnly ()) {
378 INode<K, V> r = RDCSS_READ_ROOT ();
379 MainNode<K, V> expmain = r.gcasRead (this);
380 if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
381 return new TrieMap<> (r, hashing (), equality (), true);
383 // return readOnlySnapshot ();
390 final public void clear () {
392 INode<K, V> r = RDCSS_READ_ROOT ();
393 if (!RDCSS_ROOT (r, r.gcasRead (this), INode.<K, V>newRootNode ())) {
402 int computeHash (final K k) {
403 return hashingobj.hash (k);
406 final V lookup (final K k) {
407 int hc = computeHash (k);
408 // return (V) lookuphc (k, hc);
409 Object o = lookuphc (k, hc);
410 if(o instanceof Some) {
411 return ((Some<V>)o).get ();
412 } else if(o instanceof None) {
419 final V apply (final K k) {
420 int hc = computeHash (k);
421 Object res = lookuphc (k, hc);
423 throw new NoSuchElementException ();
429 // final public Option<V> get (K k) {
430 // int hc = computeHash (k);
431 // return Option.makeOption ((V)lookuphc (k, hc));
435 final public V get (final Object k) {
439 final public Option<V> putOpt(final Object key, final Object value) {
440 int hc = computeHash ((K)key);
441 return insertifhc ((K)key, hc, (V)value, null);
445 final public V put (final Object key, final Object value) {
447 int hc = computeHash ((K)key);
448 Option<V> ov = insertifhc ((K)key, hc, (V)value, null);
449 if(ov instanceof Some) {
450 Some<V> sv = (Some<V>)ov;
457 final public void update (final K k, final V v) {
458 int hc = computeHash (k);
462 final public TrieMap<K, V> add (final K k, final V v) {
467 final Option<V> removeOpt (final K k) {
468 int hc = computeHash (k);
469 return removehc (k, (V) null, hc);
473 final public V remove (final Object k) {
475 int hc = computeHash ((K)k);
476 Option<V> ov = removehc ((K)k, (V) null, hc);
477 if(ov instanceof Some) {
478 Some<V> sv = (Some<V>)ov;
485 // final public TrieMap<K, V> remove (Object k) {
490 final public Option<V> putIfAbsentOpt (final K k, final V v) {
491 int hc = computeHash (k);
492 return insertifhc (k, hc, v, INode.KEY_ABSENT);
496 final public V putIfAbsent (final Object k, final Object v) {
498 int hc = computeHash ((K)k);
499 Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_ABSENT);
500 if(ov instanceof Some) {
501 Some<V> sv = (Some<V>)ov;
509 public boolean remove (final Object k, final Object v) {
511 int hc = computeHash ((K)k);
512 return removehc ((K)k, (V)v, hc).nonEmpty ();
516 public boolean replace (final K k, final V oldvalue, final V newvalue) {
518 int hc = computeHash (k);
519 return insertifhc (k, hc, newvalue, oldvalue).nonEmpty ();
522 public Option<V> replaceOpt (final K k, final V v) {
523 int hc = computeHash (k);
524 return insertifhc (k, hc, v, INode.KEY_PRESENT);
528 public V replace (final Object k, final Object v) {
530 int hc = computeHash ((K)k);
531 Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_PRESENT);
532 if(ov instanceof Some) {
533 Some<V> sv = (Some<V>)ov;
541 * Return an iterator over a TrieMap.
543 * If this is a read-only snapshot, it would return a read-only iterator.
545 * If it is the original TrieMap or a non-readonly snapshot, it would return
546 * an iterator that would allow for updates.
550 public Iterator<Map.Entry<K, V>> iterator () {
551 if (!nonReadOnly ()) {
552 return readOnlySnapshot ().readOnlyIterator ();
554 return new TrieMapIterator<> (0, this);
559 * Return an iterator over a TrieMap.
560 * This is a read-only iterator.
564 public Iterator<Map.Entry<K, V>> readOnlyIterator () {
565 if (nonReadOnly ()) {
566 return readOnlySnapshot ().readOnlyIterator ();
568 return new TrieMapReadOnlyIterator<> (0, this);
572 private int cachedSize () {
573 INode<K, V> r = RDCSS_READ_ROOT ();
574 return r.cachedSize (this);
579 if (nonReadOnly ()) {
580 return readOnlySnapshot ().size ();
582 return cachedSize ();
586 String stringPrefix () {
591 * This iterator is a read-only one and does not allow for any update
592 * operations on the underlying data structure.
597 private static class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
598 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
599 super (level, ct, mustInit);
602 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
603 this (level, ct, true);
607 assert (ct.isReadOnly ());
612 public void remove () {
613 throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
617 Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
618 // Return non-updatable entry
623 private static class TrieMapIterator<K, V> implements java.util.Iterator<Map.Entry<K, V>> {
625 protected TrieMap<K, V> ct;
626 private final boolean mustInit;
627 private final BasicNode[][] stack = new BasicNode[7][];
628 private final int[] stackpos = new int[7];
629 private int depth = -1;
630 private Iterator<Map.Entry<K, V>> subiter = null;
631 private KVNode<K, V> current = null;
632 private Map.Entry<K, V> lastReturned = null;
634 TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
637 this.mustInit = mustInit;
643 TrieMapIterator (final int level, final TrieMap<K, V> ct) {
644 this (level, ct, true);
649 public boolean hasNext () {
650 return (current != null) || (subiter != null);
654 public Map.Entry<K, V> next () {
656 Map.Entry<K, V> r = null;
657 if (subiter != null) {
661 r = current.kvPair ();
666 if(r instanceof Map.Entry) {
667 final Map.Entry<K, V> rr = r;
668 return nextEntry(rr);
672 // return Iterator.empty ().next ();
677 Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
678 return new Map.Entry<K, V>() {
679 private V updated = null;
687 public V getValue () {
688 return (updated == null)?rr.getValue (): updated;
692 public V setValue (final V value) {
694 return ct.replace (getKey (), value);
699 private void readin (final INode<K, V> in) {
700 MainNode<K, V> m = in.gcasRead (ct);
701 if (m instanceof CNode) {
702 CNode<K, V> cn = (CNode<K, V>) m;
704 stack [depth] = cn.array;
705 stackpos [depth] = -1;
707 } else if (m instanceof TNode) {
708 current = (TNode<K, V>) m;
709 } else if (m instanceof LNode) {
710 subiter = ((LNode<K, V>) m).iterator();
712 } else if (m == null) {
718 private void checkSubiter () {
719 if (!subiter.hasNext ()) {
727 // assert (ct.isReadOnly ());
728 INode<K, V> r = ct.RDCSS_READ_ROOT ();
734 int npos = stackpos [depth] + 1;
735 if (npos < stack [depth].length) {
736 stackpos [depth] = npos;
737 BasicNode elem = stack [depth] [npos];
738 if (elem instanceof SNode) {
739 current = (SNode<K, V>) elem;
740 } else if (elem instanceof INode) {
741 readin ((INode<K, V>) elem);
752 protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
753 return new TrieMapIterator<> (_lev, _ct, _mustInit);
756 protected void dupTo (final TrieMapIterator<K, V> it) {
757 it.level = this.level;
759 it.depth = this.depth;
760 it.current = this.current;
762 // these need a deep copy
763 System.arraycopy (this.stack, 0, it.stack, 0, 7);
764 System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
766 // this one needs to be evaluated
767 if (this.subiter == null) {
770 List<Map.Entry<K, V>> lst = toList (this.subiter);
771 this.subiter = lst.iterator ();
772 it.subiter = lst.iterator ();
776 // /** Returns a sequence of iterators over subsets of this iterator.
777 // * It's used to ease the implementation of splitters for a parallel
778 // version of the TrieMap.
780 // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
782 // // the case where an LNode is being iterated
788 // } else if (depth == -1) {
793 // while (d <= depth) {
794 // val rem = stack(d).length - 1 - stackpos(d)
796 // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
799 // val it = newIterator(level + 1, ct, false)
800 // it.stack(0) = arr2
801 // it.stackpos(0) = -1
803 // it.advance() // <-- fix it
805 // return Seq(this, it)
813 private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
814 ArrayList<Entry<K, V>> list = new ArrayList<> ();
815 while (it.hasNext ()) {
816 list.add (it.next ());
822 System.out.println ("ctrie iterator");
823 System.out.println (Arrays.toString (stackpos));
824 System.out.println ("depth: " + depth);
825 System.out.println ("curr.: " + current);
826 // System.out.println(stack.mkString("\n"));
830 public void remove () {
831 if (lastReturned != null) {
832 ct.remove (lastReturned.getKey ());
835 throw new IllegalStateException();
841 /** Only used for ctrie serialization. */
842 // @SerialVersionUID(0L - 7237891413820527142L)
843 private static long TrieMapSerializationEnd = 0L - 7237891413820527142L;
847 public boolean containsKey (final Object key) {
848 return lookup ((K) key) != null;
853 public Set<Map.Entry<K, V>> entrySet () {
858 * Support for EntrySet operations required by the Map interface
861 final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
864 public Iterator<Map.Entry<K, V>> iterator () {
865 return TrieMap.this.iterator ();
869 public final boolean contains (final Object o) {
870 if (!(o instanceof Map.Entry)) {
873 final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
874 final K k = e.getKey ();
875 final V v = lookup (k);
880 public final boolean remove (final Object o) {
881 if (!(o instanceof Map.Entry)) {
884 final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
885 final K k = e.getKey ();
886 return null != TrieMap.this.remove (k);
890 public final int size () {
892 for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
899 public final void clear () {
900 TrieMap.this.clear ();
904 private void readObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
905 inputStream.defaultReadObject();
906 this.root = INode.newRootNode();
908 final boolean ro = inputStream.readBoolean();
909 final int size = inputStream.readInt();
910 for (int i = 0; i < size; ++i) {
911 final K key = (K)inputStream.readObject();
912 final V value = (V)inputStream.readObject();
916 // Propagate the read-only bit
918 READONLY_FIELD.setBoolean(this, ro);
919 } catch (IllegalAccessException e) {
920 throw new IOException("Failed to set read-only flag", e);
924 private void writeObject(final ObjectOutputStream outputStream) throws IOException {
925 outputStream.defaultWriteObject();
927 final Map<K, V> ro = readOnlySnapshot();
928 outputStream.writeBoolean(isReadOnly());
929 outputStream.writeInt(ro.size());
931 for (Entry<K, V> e : ro.entrySet()) {
932 outputStream.writeObject(e.getKey());
933 outputStream.writeObject(e.getValue());