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 static class INode<K, V> extends INodeBase<K, V> {
79 static final Object KEY_PRESENT = new Object ();
80 static final Object KEY_ABSENT = new Object ();
82 static <K,V> INode<K,V> newRootNode () {
84 CNode<K, V> cn = new CNode<> (0, new BasicNode[] {}, gen);
85 return new INode<>(cn, gen);
88 public INode (final MainNode<K, V> bn, final Gen g) {
93 public INode (final Gen g) {
97 final void WRITE (final MainNode<K, V> nval) {
98 INodeBase.updater.set (this, nval);
101 final boolean CAS (final MainNode<K, V> old, final MainNode<K, V> n) {
102 return INodeBase.updater.compareAndSet (this, old, n);
105 final MainNode<K, V> gcasRead (final TrieMap<K, V> ct) {
106 return GCAS_READ (ct);
109 final MainNode<K, V> GCAS_READ (final TrieMap<K, V> ct) {
110 MainNode<K, V> m = /* READ */mainnode;
111 MainNode<K, V> prevval = /* READ */m.prev;
112 if (prevval == null) {
115 return GCAS_Complete (m, ct);
119 private MainNode<K, V> GCAS_Complete (MainNode<K, V> m, final TrieMap<K, V> ct) {
125 MainNode<K, V> prev = /* READ */m.prev;
126 INode<K, V> ctr = ct.readRoot (true);
132 if (prev instanceof FailedNode) {
133 // try to commit to previous value
134 FailedNode<K, V> fn = (FailedNode<K, V>) prev;
135 if (CAS (m, fn.prev)) {
139 // return GCAS_Complete (/* READ */mainnode, ct);
140 m = /* READ */mainnode;
143 } else if (prev instanceof MainNode) {
144 // Assume that you've read the root from the generation
146 // Assume that the snapshot algorithm is correct.
147 // ==> you can only reach nodes in generations <= G.
148 // ==> `gen` is <= G.
149 // We know that `ctr.gen` is >= G.
150 // ==> if `ctr.gen` = `gen` then they are both equal to
152 // ==> otherwise, we know that either `ctr.gen` > G,
156 if ((ctr.gen == gen) && ct.nonReadOnly ()) {
158 if (m.CAS_PREV (prev, null)) {
161 // return GCAS_Complete (m, ct);
167 m.CAS_PREV (prev, new FailedNode<> (prev));
168 return GCAS_Complete (/* READ */mainnode, ct);
172 throw new RuntimeException ("Should not happen");
176 final boolean GCAS (final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
179 GCAS_Complete (n, ct);
180 return /* READ */n.prev == null;
186 private boolean equal (final K k1, final K k2, final TrieMap<K, V> ct) {
187 return ct.equality ().equiv (k1, k2);
190 private INode<K, V> inode (final MainNode<K, V> cn) {
191 INode<K, V> nin = new INode<> (gen);
196 final INode<K, V> copyToGen (final Gen ngen, final TrieMap<K, V> ct) {
197 INode<K, V> nin = new INode<> (ngen);
198 MainNode<K, V> main = GCAS_READ (ct);
204 * Inserts a key value pair, overwriting the old pair if the keys match.
206 * @return true if successful, false otherwise
208 final boolean rec_insert (final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
210 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
212 if (m instanceof CNode) {
213 // 1) a multiway node
214 CNode<K, V> cn = (CNode<K, V>) m;
215 int idx = (hc >>> lev) & 0x1f;
219 int pos = Integer.bitCount (bmp & mask);
220 if ((bmp & flag) != 0) {
222 BasicNode cnAtPos = cn.array [pos];
223 if (cnAtPos instanceof INode) {
224 INode<K, V> in = (INode<K, V>) cnAtPos;
225 if (startgen == in.gen) {
226 return in.rec_insert (k, v, hc, lev + 5, this, startgen, ct);
228 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
229 // return rec_insert (k, v, hc, lev, parent,
237 } else if (cnAtPos instanceof SNode) {
238 SNode<K, V> sn = (SNode<K, V>) cnAtPos;
239 if (sn.hc == hc && equal (sn.k, k, ct)) {
240 return GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct);
242 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
243 MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
244 return GCAS (cn, nn, ct);
248 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
249 MainNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<> (k, v, hc), gen);
250 return GCAS (cn, ncnode, ct);
252 } else if (m instanceof TNode) {
253 clean (parent, ct, lev - 5);
255 } else if (m instanceof LNode) {
256 LNode<K, V> ln = (LNode<K, V>) m;
257 MainNode<K, V> nn = ln.inserted (k, v);
258 return GCAS (ln, nn, ct);
261 throw new RuntimeException ("Should not happen");
266 * Inserts a new key value pair, given that a specific condition is met.
269 * null - don't care if the key was there
270 * KEY_ABSENT - key wasn't there
271 * KEY_PRESENT - key was there
272 * other value `v` - key must be bound to `v`
273 * @return null if unsuccessful, Option[V] otherwise (indicating
274 * previous value bound to the key)
276 final Option<V> rec_insertif (final K k, final V v, final int hc, final Object cond, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
278 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
280 if (m instanceof CNode) {
281 // 1) a multiway node
282 CNode<K, V> cn = (CNode<K, V>) m;
283 int idx = (hc >>> lev) & 0x1f;
287 int pos = Integer.bitCount (bmp & mask);
289 if ((bmp & flag) != 0) {
291 BasicNode cnAtPos = cn.array [pos];
292 if (cnAtPos instanceof INode) {
293 INode<K, V> in = (INode<K, V>) cnAtPos;
294 if (startgen == in.gen) {
295 return in.rec_insertif (k, v, hc, cond, lev + 5, this, startgen, ct);
297 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
298 // return rec_insertif (k, v, hc, cond, lev,
299 // parent, startgen, ct);
306 } else if (cnAtPos instanceof SNode) {
307 SNode<K, V> sn = (SNode<K, V>) cnAtPos;
309 if (sn.hc == hc && equal (sn.k, k, ct)) {
310 if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
311 return Option.makeOption(sn.v);
316 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
317 MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
318 if (GCAS (cn, nn, ct)) {
319 return Option.makeOption(); // None;
325 } else if (cond == INode.KEY_ABSENT) {
326 if (sn.hc == hc && equal (sn.k, k, ct)) {
327 return Option.makeOption(sn.v);
329 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
330 MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
331 if (GCAS (cn, nn, ct)) {
332 return Option.makeOption (); // None
337 } else if (cond == INode.KEY_PRESENT) {
338 if (sn.hc == hc && equal (sn.k, k, ct)) {
339 if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
340 return Option.makeOption (sn.v);
347 return Option.makeOption ();// None;
350 if (sn.hc == hc && equal (sn.k, k, ct) && sn.v == cond) {
351 if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
352 return Option.makeOption (sn.v);
358 return Option.makeOption (); // None
363 } else if (cond == null || cond == INode.KEY_ABSENT) {
364 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
365 CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<> (k, v, hc), gen);
366 if (GCAS (cn, ncnode, ct)) {
367 return Option.makeOption ();// None
371 } else if (cond == INode.KEY_PRESENT) {
372 return Option.makeOption ();// None;
375 return Option.makeOption (); // None
377 } else if (m instanceof TNode) {
378 clean (parent, ct, lev - 5);
380 } else if (m instanceof LNode) {
382 LNode<K, V> ln = (LNode<K, V>) m;
384 Option<V> optv = ln.get (k);
385 if (insertln (ln, k, v, ct)) {
390 } else if (cond == INode.KEY_ABSENT) {
391 Option<V> t = ln.get (k);
393 if (insertln (ln, k, v, ct)) {
394 return Option.makeOption ();// None
401 } else if (cond == INode.KEY_PRESENT) {
402 Option<V> t = ln.get (k);
404 if (insertln (ln, k, v, ct)) {
414 Option<V> t = ln.get (k);
416 if (((Some<V>) t).get () == cond) {
417 if (insertln (ln, k, v, ct)) {
418 return new Some<> ((V) cond);
424 return Option.makeOption ();
430 // throw new RuntimeException ("Should not happen");
434 final boolean insertln (final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
435 LNode<K, V> nn = ln.inserted (k, v);
436 return GCAS (ln, nn, ct);
440 * Looks up the value associated with the key.
442 * @return null if no value has been found, RESTART if the operation
443 * wasn't successful, or any other value otherwise
445 final Object rec_lookup (final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
447 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
449 if (m instanceof CNode) {
451 final CNode<K, V> cn = (CNode<K, V>) m;
452 int idx = (hc >>> lev) & 0x1f;
455 if ((bmp & flag) == 0) {
456 return null; // 1a) bitmap shows no binding
457 } else { // 1b) bitmap contains a value - descend
458 int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount (bmp & (flag - 1));
459 final BasicNode sub = cn.array [pos];
460 if (sub instanceof INode) {
461 INode<K, V> in = (INode<K, V>) sub;
462 if (ct.isReadOnly () || (startgen == ((INodeBase<K, V>) sub).gen)) {
463 return in.rec_lookup (k, hc, lev + 5, this, startgen, ct);
465 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
466 // return rec_lookup (k, hc, lev, parent,
472 return RESTART; // used to be throw
476 } else if (sub instanceof SNode) {
478 SNode<K, V> sn = (SNode<K, V>) sub;
479 if (((SNode) sub).hc == hc && equal (sn.k, k, ct)) {
486 } else if (m instanceof TNode) {
488 return cleanReadOnly ((TNode<K, V>) m, lev, parent, ct, k, hc);
489 } else if (m instanceof LNode) {
491 Option<V> tmp = ((LNode<K, V>) m).get (k);
492 return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
495 throw new RuntimeException ("Should not happen");
499 private Object cleanReadOnly (final TNode<K, V> tn, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct, final K k, final int hc) {
500 if (ct.nonReadOnly ()) {
501 clean (parent, ct, lev - 5);
502 return RESTART; // used to be throw RestartException
504 if (tn.hc == hc && equal(tn.k, k, ct)) {
513 * Removes the key associated with the given value.
516 * if null, will remove the key irregardless of the value;
517 * otherwise removes only if binding contains that exact key
519 * @return null if not successful, an Option[V] indicating the previous
522 final Option<V> rec_remove (final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
523 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
525 if (m instanceof CNode) {
526 CNode<K, V> cn = (CNode<K, V>) m;
527 int idx = (hc >>> lev) & 0x1f;
530 if ((bmp & flag) == 0) {
531 return Option.makeOption ();
533 int pos = Integer.bitCount (bmp & (flag - 1));
534 BasicNode sub = cn.array [pos];
535 Option<V> res = null;
536 if (sub instanceof INode) {
537 INode<K, V> in = (INode<K, V>) sub;
538 if (startgen == in.gen) {
539 res = in.rec_remove (k, v, hc, lev + 5, this, startgen, ct);
541 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
542 res = rec_remove (k, v, hc, lev, parent, startgen, ct);
548 } else if (sub instanceof SNode) {
549 SNode<K, V> sn = (SNode<K, V>) sub;
550 if (sn.hc == hc && equal (sn.k, k, ct) && (v == null || v.equals(sn.v))) {
551 MainNode<K, V> ncn = cn.removedAt (pos, flag, gen).toContracted (lev);
552 if (GCAS (cn, ncn, ct)) {
553 res = Option.makeOption (sn.v);
558 res = Option.makeOption ();
562 if (res instanceof None || (res == null)) {
565 if (parent != null) { // never tomb at root
566 MainNode<K, V> n = GCAS_READ (ct);
567 if (n instanceof TNode) {
568 cleanParent (n, parent, ct, hc, lev, startgen);
575 } else if (m instanceof TNode) {
576 clean (parent, ct, lev - 5);
578 } else if (m instanceof LNode) {
579 LNode<K, V> ln = (LNode<K, V>) m;
581 Option<V> optv = ln.get (k);
582 MainNode<K, V> nn = ln.removed (k, ct);
583 if (GCAS (ln, nn, ct)) {
589 Option<V> tmp = ln.get (k);
590 if (tmp instanceof Some) {
591 Some<V> tmp1 = (Some<V>) tmp;
592 if (tmp1.get () == v) {
593 MainNode<K, V> nn = ln.removed (k, ct);
594 if (GCAS (ln, nn, ct)) {
603 throw new RuntimeException ("Should not happen");
606 void cleanParent (final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc, final int lev, final Gen startgen) {
608 MainNode<K, V> pm = parent.GCAS_READ (ct);
609 if (pm instanceof CNode) {
610 CNode<K, V> cn = (CNode<K, V>) pm;
611 int idx = (hc >>> (lev - 5)) & 0x1f;
614 if ((bmp & flag) == 0) {
615 } // somebody already removed this i-node, we're done
617 int pos = Integer.bitCount (bmp & (flag - 1));
618 BasicNode sub = cn.array [pos];
620 if (nonlive instanceof TNode) {
621 TNode<K, V> tn = (TNode<K, V>) nonlive;
622 MainNode<K, V> ncn = cn.updatedAt (pos, tn.copyUntombed (), gen).toContracted (lev - 5);
623 if (!parent.GCAS (cn, ncn, ct)) {
624 if (ct.readRoot ().gen == startgen) {
625 // cleanParent (nonlive, parent, ct, hc,
635 // parent is no longer a cnode, we're done
641 private void clean (final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
642 MainNode<K, V> m = nd.GCAS_READ (ct);
643 if (m instanceof CNode) {
644 CNode<K, V> cn = (CNode<K, V>) m;
645 nd.GCAS (cn, cn.toCompressed (ct, lev, gen), ct);
649 final boolean isNullInode (final TrieMap<K, V> ct) {
650 return GCAS_READ (ct) == null;
653 final int cachedSize (final TrieMap<K, V> ct) {
654 MainNode<K, V> m = GCAS_READ (ct);
655 return m.cachedSize (ct);
658 // /* this is a quiescent method! */
659 // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
661 // case null => "<null>"
662 // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
664 // case cn: CNode[_, _] => cn.string(lev)
665 // case ln: LNode[_, _] => ln.string(lev)
666 // case x => "<elem: %s>".format(x)
670 public String string (final int lev) {
676 private static final class FailedNode<K, V> extends MainNode<K, V> {
679 FailedNode (final MainNode<K, V> p) {
685 public String string (final int lev) {
686 throw new UnsupportedOperationException ();
690 public int cachedSize (final Object ct) {
691 throw new UnsupportedOperationException ();
695 public String toString () {
696 return String.format ("FailedNode(%s)", p);
700 private interface KVNode<K, V> {
701 Map.Entry<K, V> kvPair ();
704 private static final class SNode<K, V> extends BasicNode implements KVNode<K, V> {
709 SNode (final K k, final V v, final int hc) {
715 final SNode<K, V> copy() {
716 return new SNode<> (k, v, hc);
719 final TNode<K, V> copyTombed () {
720 return new TNode<> (k, v, hc);
723 final SNode<K, V> copyUntombed () {
724 return new SNode<> (k, v, hc);
728 final public Map.Entry<K, V> kvPair () {
729 return new SimpleImmutableEntry<> (k, v);
733 final public String string (final int lev) {
734 // (" " * lev) + "SNode(%s, %s, %x)".format(k, v, hc);
739 private static final class TNode<K, V> extends MainNode<K, V> implements KVNode<K, V> {
744 TNode (final K k, final V v, final int hc) {
750 final TNode<K, V> copy () {
751 return new TNode<> (k, v, hc);
754 final TNode<K, V> copyTombed () {
755 return new TNode<> (k, v, hc);
758 final SNode<K, V> copyUntombed () {
759 return new SNode<> (k, v, hc);
763 final public Map.Entry<K, V> kvPair () {
764 return new SimpleImmutableEntry<> (k, v);
768 final public int cachedSize (final Object ct) {
773 final public String string (final int lev) {
774 // (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc);
779 private final static class LNode<K, V> extends MainNode<K, V> {
780 final ListMap<K, V> listmap;
782 public LNode (final ListMap<K, V> listmap) {
783 this.listmap = listmap;
786 public LNode(final K k, final V v) {
787 this (ListMap.map (k, v));
790 public LNode (final K k1, final V v1, final K k2, final V v2) {
791 this (ListMap.map (k1, v1, k2, v2));
794 LNode<K, V> inserted (final K k, final V v) {
795 return new LNode<> (listmap.add (k, v));
798 MainNode<K, V> removed (final K k, final TrieMap<K, V> ct) {
799 ListMap<K, V> updmap = listmap.remove (k);
800 if (updmap.size () > 1) {
801 return new LNode<> (updmap);
803 Entry<K, V> kv = updmap.iterator ().next ();
804 // create it tombed so that it gets compressed on subsequent
806 return new TNode<> (kv.getKey (), kv.getValue (), ct.computeHash (kv.getKey ()));
810 Option<V> get (final K k) {
811 return listmap.get (k);
815 public int cachedSize (final Object ct) {
816 return listmap.size ();
820 public String string (final int lev) {
821 // (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
826 private static final class CNode<K, V> extends CNodeBase<K, V> {
829 final BasicNode[] array;
832 CNode (final int bitmap, final BasicNode[] array, final Gen gen) {
833 this.bitmap = bitmap;
838 // this should only be called from within read-only snapshots
840 final public int cachedSize (final Object ct) {
841 int currsz = READ_SIZE ();
845 int sz = computeSize ((TrieMap<K, V>) ct);
846 while (READ_SIZE () == -1) {
853 // lends itself towards being parallelizable by choosing
854 // a random starting offset in the array
855 // => if there are concurrent size computations, they start
856 // at different positions, so they are more likely to
858 private int computeSize (final TrieMap<K, V> ct) {
861 // final int offset = (array.length > 0) ?
862 // // util.Random.nextInt(array.length) /* <-- benchmarks show that
863 // // this causes observable contention */
864 // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
868 final int offset = 0;
869 while (i < array.length) {
870 int pos = (i + offset) % array.length;
871 BasicNode elem = array [pos];
872 if (elem instanceof SNode) {
874 } else if (elem instanceof INode) {
875 sz += ((INode<K, V>) elem).cachedSize (ct);
882 final CNode<K, V> updatedAt (final int pos, final BasicNode nn, final Gen gen) {
883 int len = array.length;
884 BasicNode[] narr = new BasicNode[len];
885 System.arraycopy (array, 0, narr, 0, len);
887 return new CNode<> (bitmap, narr, gen);
890 final CNode<K, V> removedAt (final int pos, final int flag, final Gen gen) {
891 BasicNode[] arr = array;
892 int len = arr.length;
893 BasicNode[] narr = new BasicNode[len - 1];
894 System.arraycopy (arr, 0, narr, 0, pos);
895 System.arraycopy (arr, pos + 1, narr, pos, len - pos - 1);
896 return new CNode<> (bitmap ^ flag, narr, gen);
899 final CNode<K, V> insertedAt (final int pos, final int flag, final BasicNode nn, final Gen gen) {
900 int len = array.length;
902 BasicNode[] narr = new BasicNode[len + 1];
903 System.arraycopy (array, 0, narr, 0, pos);
905 System.arraycopy (array, pos, narr, pos + 1, len - pos);
906 return new CNode<> (bmp | flag, narr, gen);
910 * Returns a copy of this cnode such that all the i-nodes below it are
911 * copied to the specified generation `ngen`.
913 final CNode<K, V> renewed (final Gen ngen, final TrieMap<K, V> ct) {
915 BasicNode[] arr = array;
916 int len = arr.length;
917 BasicNode[] narr = new BasicNode[len];
919 BasicNode elem = arr [i];
920 if (elem instanceof INode) {
921 INode<K, V> in = (INode<K, V>) elem;
922 narr [i] = in.copyToGen (ngen, ct);
923 } else if (elem instanceof BasicNode) {
928 return new CNode<> (bitmap, narr, ngen);
931 private BasicNode resurrect (final INode<K, V> inode, final Object inodemain) {
932 if (inodemain instanceof TNode) {
933 TNode<K, V> tn = (TNode<K, V>) inodemain;
934 return tn.copyUntombed ();
940 final MainNode<K, V> toContracted (final int lev) {
941 if (array.length == 1 && lev > 0) {
942 if (array [0] instanceof SNode) {
943 SNode<K, V> sn = (SNode<K, V>) array [0];
944 return sn.copyTombed ();
954 // - if the branching factor is 1 for this CNode, and the child
955 // is a tombed SNode, returns its tombed version
956 // - otherwise, if there is at least one non-null node below,
957 // returns the version of this node with at least some null-inodes
958 // removed (those existing when the op began)
959 // - if there are only null-i-nodes below, returns null
960 final MainNode<K, V> toCompressed (final TrieMap<K, V> ct, final int lev, final Gen gen) {
963 BasicNode[] arr = array;
964 BasicNode[] tmparray = new BasicNode[arr.length];
965 while (i < arr.length) { // construct new bitmap
966 BasicNode sub = arr [i];
967 if (sub instanceof INode) {
968 INode<K, V> in = (INode<K, V>) sub;
969 MainNode<K, V> inodemain = in.gcasRead (ct);
970 assert (inodemain != null);
971 tmparray [i] = resurrect (in, inodemain);
972 } else if (sub instanceof SNode) {
978 return new CNode<K, V> (bmp, tmparray, gen).toContracted (lev);
982 public String string (final int lev) {
983 // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
984 // 1)).mkString("\n"));
989 * quiescently consistent - don't call concurrently to anything
992 // protected Seq<K,V> collectElems() {
994 // case sn: SNode[K, V] => Some(sn.kvPair)
995 // case in: INode[K, V] => in.mainnode match {
996 // case tn: TNode[K, V] => Some(tn.kvPair)
997 // case ln: LNode[K, V] => ln.listmap.toList
998 // case cn: CNode[K, V] => cn.collectElems
1003 // protected Seq<String> collectLocalElems() {
1004 // // array flatMap {
1005 // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
1006 // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
1013 public String toString () {
1014 // val elems = collectLocalElems
1015 // "CNode(sz: %d; %s)".format(elems.size,
1016 // elems.sorted.mkString(", "))
1020 static <K, V> MainNode<K,V> dual (final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc, final int lev, final Gen gen) {
1022 int xidx = (xhc >>> lev) & 0x1f;
1023 int yidx = (yhc >>> lev) & 0x1f;
1024 int bmp = (1 << xidx) | (1 << yidx);
1027 INode<K, V> subinode = new INode<> (gen);// (TrieMap.inodeupdater)
1028 subinode.mainnode = dual (x, xhc, y, yhc, lev + 5, gen);
1029 return new CNode<> (bmp, new BasicNode[] { subinode }, gen);
1032 return new CNode<> (bmp, new BasicNode[] { x, y }, gen);
1034 return new CNode<> (bmp, new BasicNode[] { y, x }, gen);
1038 return new LNode<> (x.k, x.v, y.k, y.v);
1044 private static class RDCSS_Descriptor<K, V> {
1046 MainNode<K, V> expectedmain;
1048 volatile boolean committed = false;
1050 public RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
1052 this.expectedmain = expectedmain;
1058 private static class Equiv<K> implements Serializable {
1059 private static final long serialVersionUID = 1L;
1061 public boolean equiv (final K k1, final K k2) {
1062 return k1.equals (k2);
1065 static Equiv universal = new Equiv ();
1068 private static interface Hashing<K> extends Serializable {
1069 public int hash (K k);
1072 static class Default<K> implements Hashing<K> {
1073 private static final long serialVersionUID = 1L;
1076 public int hash (final K k) {
1077 int h = k.hashCode ();
1078 // This function ensures that hashCodes that differ only by
1079 // constant multiples at each bit position have a bounded
1080 // number of collisions (approximately 8 at default load factor).
1081 h ^= (h >>> 20) ^ (h >>> 12);
1082 h ^= (h >>> 7) ^ (h >>> 4);
1087 private final Hashing<K> hashingobj;
1088 private final Equiv<K> equalityobj;
1090 Hashing<K> hashing () {
1094 Equiv<K> equality () {
1098 private transient volatile Object root;
1099 private final transient boolean readOnly;
1101 TrieMap (final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
1102 this.hashingobj = hashf;
1103 this.equalityobj = ef;
1104 this.readOnly = readOnly;
1107 TrieMap (final Object r, final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
1108 this(hashf, ef, readOnly);
1112 public TrieMap (final Hashing<K> hashf, final Equiv<K> ef) {
1113 this(INode.newRootNode(), hashf, ef, false);
1117 this (new Default<K> (), Equiv.universal);
1120 /* internal methods */
1122 // private void writeObject(java.io.ObjectOutputStream out) {
1123 // out.writeObject(hashf);
1124 // out.writeObject(ef);
1126 // Iterator it = iterator();
1127 // while (it.hasNext) {
1128 // val (k, v) = it.next();
1129 // out.writeObject(k);
1130 // out.writeObject(v);
1132 // out.writeObject(TrieMapSerializationEnd);
1135 // private TrieMap readObject(java.io.ObjectInputStream in) {
1136 // root = INode.newRootNode();
1137 // rootupdater = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class,
1138 // Object.class, "root");
1140 // hashingobj = in.readObject();
1141 // equalityobj = in.readObject();
1143 // Object obj = null;
1145 // obj = in.readObject();
1146 // if (obj != TrieMapSerializationEnd) {
1148 // V = (V)in.readObject();
1151 // } while (obj != TrieMapSerializationEnd);
1154 final boolean CAS_ROOT (final Object ov, final Object nv) {
1156 throw new IllegalStateException("Attempted to modify a read-only snapshot");
1158 return ROOT_UPDATER.compareAndSet (this, ov, nv);
1161 // FIXME: abort = false by default
1162 final INode<K, V> readRoot (final boolean abort) {
1163 return RDCSS_READ_ROOT (abort);
1166 final INode<K, V> readRoot () {
1167 return RDCSS_READ_ROOT (false);
1170 final INode<K, V> RDCSS_READ_ROOT () {
1171 return RDCSS_READ_ROOT (false);
1174 final INode<K, V> RDCSS_READ_ROOT (final boolean abort) {
1175 Object r = /* READ */root;
1176 if (r instanceof INode) {
1177 return (INode<K, V>) r;
1178 } else if (r instanceof RDCSS_Descriptor) {
1179 return RDCSS_Complete (abort);
1181 throw new RuntimeException ("Should not happen");
1184 private final INode<K, V> RDCSS_Complete (final boolean abort) {
1186 Object v = /* READ */root;
1187 if (v instanceof INode) {
1188 return (INode<K, V>) v;
1189 } else if (v instanceof RDCSS_Descriptor) {
1190 RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
1191 INode<K, V> ov = desc.old;
1192 MainNode<K, V> exp = desc.expectedmain;
1193 INode<K, V> nv = desc.nv;
1196 if (CAS_ROOT (desc, ov)) {
1199 // return RDCSS_Complete (abort);
1204 MainNode<K, V> oldmain = ov.gcasRead (this);
1205 if (oldmain == exp) {
1206 if (CAS_ROOT (desc, nv)) {
1207 desc.committed = true;
1210 // return RDCSS_Complete (abort);
1215 if (CAS_ROOT (desc, ov)) {
1218 // return RDCSS_Complete (abort);
1227 throw new RuntimeException ("Should not happen");
1231 private boolean RDCSS_ROOT (final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
1232 RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
1233 if (CAS_ROOT (ov, desc)) {
1234 RDCSS_Complete (false);
1235 return /* READ */desc.committed;
1241 private void inserthc (final K k, final int hc, final V v) {
1243 INode<K, V> r = RDCSS_READ_ROOT ();
1244 if (!r.rec_insert (k, v, hc, 0, null, r.gen, this)) {
1245 // inserthc (k, hc, v);
1253 private Option<V> insertifhc (final K k, final int hc, final V v, final Object cond) {
1255 INode<K, V> r = RDCSS_READ_ROOT ();
1257 Option<V> ret = r.rec_insertif (k, v, hc, cond, 0, null, r.gen, this);
1259 // return insertifhc (k, hc, v, cond);
1268 private Object lookuphc (final K k, final int hc) {
1270 INode<K, V> r = RDCSS_READ_ROOT ();
1271 Object res = r.rec_lookup (k, hc, 0, null, r.gen, this);
1272 if (res == INodeBase.RESTART) {
1273 // return lookuphc (k, hc);
1282 private Option<V> removehc (final K k, final V v, final int hc) {
1284 INode<K, V> r = RDCSS_READ_ROOT ();
1285 Option<V> res = r.rec_remove (k, v, hc, 0, null, r.gen, this);
1289 // return removehc (k, v, hc);
1297 * Ensure this instance is read-write, throw UnsupportedOperationException
1298 * otherwise. Used by Map-type methods for quick check.
1300 private void ensureReadWrite() {
1302 throw new UnsupportedOperationException("Attempted to modify a read-only view");
1306 public String string () {
1307 // RDCSS_READ_ROOT().string(0);
1311 /* public methods */
1313 // public Seq<V> seq() {
1317 // override def par = new ParTrieMap(this)
1319 // static TrieMap empty() {
1320 // return new TrieMap();
1323 final boolean isReadOnly () {
1327 final boolean nonReadOnly () {
1332 * Returns a snapshot of this TrieMap. This operation is lock-free and
1335 * The snapshot is lazily updated - the first time some branch in the
1336 * snapshot or this TrieMap are accessed, they are rewritten. This means
1337 * that the work of rebuilding both the snapshot and this TrieMap is
1338 * distributed across all the threads doing updates or accesses subsequent
1339 * to the snapshot creation.
1342 final public TrieMap<K, V> snapshot () {
1344 INode<K, V> r = RDCSS_READ_ROOT ();
1345 final MainNode<K, V> expmain = r.gcasRead (this);
1346 if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
1347 return new TrieMap<> (r.copyToGen (new Gen (), this), hashing (), equality (), readOnly);
1349 // return snapshot ();
1357 * Returns a read-only snapshot of this TrieMap. This operation is lock-free
1360 * The snapshot is lazily updated - the first time some branch of this
1361 * TrieMap are accessed, it is rewritten. The work of creating the snapshot
1362 * is thus distributed across subsequent updates and accesses on this
1363 * TrieMap by all threads. Note that the snapshot itself is never rewritten
1364 * unlike when calling the `snapshot` method, but the obtained snapshot
1365 * cannot be modified.
1367 * This method is used by other methods such as `size` and `iterator`.
1369 final public TrieMap<K, V> readOnlySnapshot () {
1370 // Is it a snapshot of a read-only snapshot?
1371 if(!nonReadOnly ()) {
1376 INode<K, V> r = RDCSS_READ_ROOT ();
1377 MainNode<K, V> expmain = r.gcasRead (this);
1378 if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
1379 return new TrieMap<> (r, hashing (), equality (), true);
1381 // return readOnlySnapshot ();
1388 final public void clear () {
1390 INode<K, V> r = RDCSS_READ_ROOT ();
1391 if (!RDCSS_ROOT (r, r.gcasRead (this), INode.<K, V>newRootNode ())) {
1400 int computeHash (final K k) {
1401 return hashingobj.hash (k);
1404 final V lookup (final K k) {
1405 int hc = computeHash (k);
1406 // return (V) lookuphc (k, hc);
1407 Object o = lookuphc (k, hc);
1408 if(o instanceof Some) {
1409 return ((Some<V>)o).get ();
1410 } else if(o instanceof None) {
1417 final V apply (final K k) {
1418 int hc = computeHash (k);
1419 Object res = lookuphc (k, hc);
1421 throw new NoSuchElementException ();
1427 // final public Option<V> get (K k) {
1428 // int hc = computeHash (k);
1429 // return Option.makeOption ((V)lookuphc (k, hc));
1433 final public V get (final Object k) {
1434 return lookup((K)k);
1437 final public Option<V> putOpt(final Object key, final Object value) {
1438 int hc = computeHash ((K)key);
1439 return insertifhc ((K)key, hc, (V)value, null);
1443 final public V put (final Object key, final Object value) {
1445 int hc = computeHash ((K)key);
1446 Option<V> ov = insertifhc ((K)key, hc, (V)value, null);
1447 if(ov instanceof Some) {
1448 Some<V> sv = (Some<V>)ov;
1455 final public void update (final K k, final V v) {
1456 int hc = computeHash (k);
1457 inserthc (k, hc, v);
1460 final public TrieMap<K, V> add (final K k, final V v) {
1465 final Option<V> removeOpt (final K k) {
1466 int hc = computeHash (k);
1467 return removehc (k, (V) null, hc);
1471 final public V remove (final Object k) {
1473 int hc = computeHash ((K)k);
1474 Option<V> ov = removehc ((K)k, (V) null, hc);
1475 if(ov instanceof Some) {
1476 Some<V> sv = (Some<V>)ov;
1483 // final public TrieMap<K, V> remove (Object k) {
1484 // removeOpt ((K)k);
1488 final public Option<V> putIfAbsentOpt (final K k, final V v) {
1489 int hc = computeHash (k);
1490 return insertifhc (k, hc, v, INode.KEY_ABSENT);
1494 final public V putIfAbsent (final Object k, final Object v) {
1496 int hc = computeHash ((K)k);
1497 Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_ABSENT);
1498 if(ov instanceof Some) {
1499 Some<V> sv = (Some<V>)ov;
1507 public boolean remove (final Object k, final Object v) {
1509 int hc = computeHash ((K)k);
1510 return removehc ((K)k, (V)v, hc).nonEmpty ();
1514 public boolean replace (final K k, final V oldvalue, final V newvalue) {
1516 int hc = computeHash (k);
1517 return insertifhc (k, hc, newvalue, oldvalue).nonEmpty ();
1520 public Option<V> replaceOpt (final K k, final V v) {
1521 int hc = computeHash (k);
1522 return insertifhc (k, hc, v, INode.KEY_PRESENT);
1526 public V replace (final Object k, final Object v) {
1528 int hc = computeHash ((K)k);
1529 Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_PRESENT);
1530 if(ov instanceof Some) {
1531 Some<V> sv = (Some<V>)ov;
1539 * Return an iterator over a TrieMap.
1541 * If this is a read-only snapshot, it would return a read-only iterator.
1543 * If it is the original TrieMap or a non-readonly snapshot, it would return
1544 * an iterator that would allow for updates.
1548 public Iterator<Map.Entry<K, V>> iterator () {
1549 if (!nonReadOnly ()) {
1550 return readOnlySnapshot ().readOnlyIterator ();
1552 return new TrieMapIterator<> (0, this);
1557 * Return an iterator over a TrieMap.
1558 * This is a read-only iterator.
1562 public Iterator<Map.Entry<K, V>> readOnlyIterator () {
1563 if (nonReadOnly ()) {
1564 return readOnlySnapshot ().readOnlyIterator ();
1566 return new TrieMapReadOnlyIterator<> (0, this);
1570 private int cachedSize () {
1571 INode<K, V> r = RDCSS_READ_ROOT ();
1572 return r.cachedSize (this);
1576 public int size () {
1577 if (nonReadOnly ()) {
1578 return readOnlySnapshot ().size ();
1580 return cachedSize ();
1584 String stringPrefix () {
1589 * This iterator is a read-only one and does not allow for any update
1590 * operations on the underlying data structure.
1595 private static class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
1596 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
1597 super (level, ct, mustInit);
1600 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
1601 this (level, ct, true);
1604 void initialize () {
1605 assert (ct.isReadOnly ());
1606 super.initialize ();
1610 public void remove () {
1611 throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
1615 Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
1616 // Return non-updatable entry
1621 private static class TrieMapIterator<K, V> implements java.util.Iterator<Map.Entry<K, V>> {
1623 protected TrieMap<K, V> ct;
1624 private final boolean mustInit;
1625 private final BasicNode[][] stack = new BasicNode[7][];
1626 private final int[] stackpos = new int[7];
1627 private int depth = -1;
1628 private Iterator<Map.Entry<K, V>> subiter = null;
1629 private KVNode<K, V> current = null;
1630 private Map.Entry<K, V> lastReturned = null;
1632 TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
1635 this.mustInit = mustInit;
1636 if (this.mustInit) {
1641 TrieMapIterator (final int level, final TrieMap<K, V> ct) {
1642 this (level, ct, true);
1647 public boolean hasNext () {
1648 return (current != null) || (subiter != null);
1652 public Map.Entry<K, V> next () {
1654 Map.Entry<K, V> r = null;
1655 if (subiter != null) {
1656 r = subiter.next ();
1659 r = current.kvPair ();
1664 if(r instanceof Map.Entry) {
1665 final Map.Entry<K, V> rr = r;
1666 return nextEntry(rr);
1670 // return Iterator.empty ().next ();
1675 Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
1676 return new Map.Entry<K, V>() {
1677 private V updated = null;
1680 public K getKey () {
1681 return rr.getKey ();
1685 public V getValue () {
1686 return (updated == null)?rr.getValue (): updated;
1690 public V setValue (final V value) {
1692 return ct.replace (getKey (), value);
1697 private void readin (final INode<K, V> in) {
1698 MainNode<K, V> m = in.gcasRead (ct);
1699 if (m instanceof CNode) {
1700 CNode<K, V> cn = (CNode<K, V>) m;
1702 stack [depth] = cn.array;
1703 stackpos [depth] = -1;
1705 } else if (m instanceof TNode) {
1706 current = (TNode<K, V>) m;
1707 } else if (m instanceof LNode) {
1708 subiter = ((LNode<K, V>) m).listmap.iterator ();
1710 } else if (m == null) {
1716 private void checkSubiter () {
1717 if (!subiter.hasNext ()) {
1724 void initialize () {
1725 // assert (ct.isReadOnly ());
1726 INode<K, V> r = ct.RDCSS_READ_ROOT ();
1732 int npos = stackpos [depth] + 1;
1733 if (npos < stack [depth].length) {
1734 stackpos [depth] = npos;
1735 BasicNode elem = stack [depth] [npos];
1736 if (elem instanceof SNode) {
1737 current = (SNode<K, V>) elem;
1738 } else if (elem instanceof INode) {
1739 readin ((INode<K, V>) elem);
1750 protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
1751 return new TrieMapIterator<> (_lev, _ct, _mustInit);
1754 protected void dupTo (final TrieMapIterator<K, V> it) {
1755 it.level = this.level;
1757 it.depth = this.depth;
1758 it.current = this.current;
1760 // these need a deep copy
1761 System.arraycopy (this.stack, 0, it.stack, 0, 7);
1762 System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
1764 // this one needs to be evaluated
1765 if (this.subiter == null) {
1768 List<Map.Entry<K, V>> lst = toList (this.subiter);
1769 this.subiter = lst.iterator ();
1770 it.subiter = lst.iterator ();
1774 // /** Returns a sequence of iterators over subsets of this iterator.
1775 // * It's used to ease the implementation of splitters for a parallel
1776 // version of the TrieMap.
1778 // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
1780 // // the case where an LNode is being iterated
1786 // } else if (depth == -1) {
1791 // while (d <= depth) {
1792 // val rem = stack(d).length - 1 - stackpos(d)
1794 // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
1797 // val it = newIterator(level + 1, ct, false)
1798 // it.stack(0) = arr2
1799 // it.stackpos(0) = -1
1801 // it.advance() // <-- fix it
1803 // return Seq(this, it)
1811 private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
1812 ArrayList<Entry<K, V>> list = new ArrayList<> ();
1813 while (it.hasNext ()) {
1814 list.add (it.next ());
1819 void printDebug () {
1820 System.out.println ("ctrie iterator");
1821 System.out.println (Arrays.toString (stackpos));
1822 System.out.println ("depth: " + depth);
1823 System.out.println ("curr.: " + current);
1824 // System.out.println(stack.mkString("\n"));
1828 public void remove () {
1829 if (lastReturned != null) {
1830 ct.remove (lastReturned.getKey ());
1831 lastReturned = null;
1833 throw new IllegalStateException();
1839 /** Only used for ctrie serialization. */
1840 // @SerialVersionUID(0L - 7237891413820527142L)
1841 private static long TrieMapSerializationEnd = 0L - 7237891413820527142L;
1845 public boolean containsKey (final Object key) {
1846 return lookup ((K) key) != null;
1851 public Set<Map.Entry<K, V>> entrySet () {
1856 * Support for EntrySet operations required by the Map interface
1859 final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1862 public Iterator<Map.Entry<K, V>> iterator () {
1863 return TrieMap.this.iterator ();
1867 public final boolean contains (final Object o) {
1868 if (!(o instanceof Map.Entry)) {
1871 final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
1872 final K k = e.getKey ();
1873 final V v = lookup (k);
1878 public final boolean remove (final Object o) {
1879 if (!(o instanceof Map.Entry)) {
1882 final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
1883 final K k = e.getKey ();
1884 return null != TrieMap.this.remove (k);
1888 public final int size () {
1890 for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
1897 public final void clear () {
1898 TrieMap.this.clear ();
1902 private void readObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
1903 inputStream.defaultReadObject();
1904 this.root = INode.newRootNode();
1906 final boolean ro = inputStream.readBoolean();
1907 final int size = inputStream.readInt();
1908 for (int i = 0; i < size; ++i) {
1909 final K key = (K)inputStream.readObject();
1910 final V value = (V)inputStream.readObject();
1914 // Propagate the read-only bit
1916 READONLY_FIELD.setBoolean(this, ro);
1917 } catch (IllegalAccessException e) {
1918 throw new IOException("Failed to set read-only flag", e);
1922 private void writeObject(final ObjectOutputStream outputStream) throws IOException {
1923 outputStream.defaultWriteObject();
1925 final Map<K, V> ro = readOnlySnapshot();
1926 outputStream.writeBoolean(isReadOnly());
1927 outputStream.writeInt(ro.size());
1929 for (Entry<K, V> e : ro.entrySet()) {
1930 outputStream.writeObject(e.getKey());
1931 outputStream.writeObject(e.getValue());