third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java

   1 /*
   2  * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
   3  *
   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
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16 package org.opendaylight.yangtools.triemap;
  17
  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;
  29 import java.util.Map;
  30 import java.util.Optional;
  31 import java.util.Set;
  32 import java.util.concurrent.ConcurrentMap;
  33 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  34
  35 /***
  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.
  38  *
  39  * @author Roman Levenstein &lt;romixlev@gmail.com&gt;
  40  *
  41  * @param <K>
  42  * @param <V>
  43  */
  44 @SuppressWarnings({"unchecked", "rawtypes", "unused"})
  45 public final class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
  46     private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER =
  47             AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root");
  48     private static final long serialVersionUID = 1L;
  49     private static final Field READONLY_FIELD;
  50
  51     static {
  52         final Field f;
  53         try {
  54             f = TrieMap.class.getDeclaredField("readOnly");
  55         } catch (NoSuchFieldException e) {
  56             throw new ExceptionInInitializerError(e);
  57         } catch (SecurityException e) {
  58             throw new ExceptionInInitializerError(e);
  59         }
  60         f.setAccessible(true);
  61         READONLY_FIELD = f;
  62     }
  63
  64     /**
  65      * EntrySet
  66      */
  67     private transient final EntrySet entrySet = new EntrySet ();
  68
  69     private final Equivalence<? super K> equiv;
  70
  71     private transient volatile Object root;
  72     private final transient boolean readOnly;
  73
  74     TrieMap(final INode<K, V> r, final Equivalence<? super K> equiv, final boolean readOnly) {
  75         this.root = r;
  76         this.equiv = equiv;
  77         this.readOnly = readOnly;
  78     }
  79
  80     public TrieMap() {
  81         this(newRootNode(), Equivalence.equals(), false);
  82     }
  83
  84     /* internal methods */
  85
  86     private static <K,V> INode<K, V> newRootNode() {
  87         final Gen gen = new Gen();
  88         return new INode<>(gen, new CNode<>(gen));
  89     }
  90
  91     final boolean CAS_ROOT (final Object ov, final Object nv) {
  92         if (isReadOnly()) {
  93             throw new IllegalStateException("Attempted to modify a read-only snapshot");
  94         }
  95         return ROOT_UPDATER.compareAndSet (this, ov, nv);
  96     }
  97
  98     // FIXME: abort = false by default
  99     final INode<K, V> readRoot(final boolean abort) {
 100         return RDCSS_READ_ROOT(abort);
 101     }
 102
 103     final INode<K, V> readRoot() {
 104         return RDCSS_READ_ROOT(false);
 105     }
 106
 107     final INode<K, V> RDCSS_READ_ROOT() {
 108         return RDCSS_READ_ROOT(false);
 109     }
 110
 111     final INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
 112         final Object r = /* READ */root;
 113         if (r instanceof INode) {
 114             return (INode<K, V>) r;
 115         } else if (r instanceof RDCSS_Descriptor) {
 116             return RDCSS_Complete (abort);
 117         } else {
 118             throw new IllegalStateException("Unhandled root " + r);
 119         }
 120     }
 121
 122     private INode<K, V> RDCSS_Complete(final boolean abort) {
 123         while (true) {
 124             final Object v = /* READ */root;
 125             if (v instanceof INode) {
 126                 return (INode<K, V>) v;
 127             }
 128
 129             if (v instanceof RDCSS_Descriptor) {
 130                 final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
 131                 final INode<K, V> ov = desc.old;
 132                 final MainNode<K, V> exp = desc.expectedmain;
 133                 final INode<K, V> nv = desc.nv;
 134
 135                 if (abort) {
 136                     if (CAS_ROOT(desc, ov)) {
 137                         return ov;
 138                     }
 139
 140                     // Tail recursion: return RDCSS_Complete(abort);
 141                     continue;
 142                 }
 143
 144                 final MainNode<K, V> oldmain = ov.gcasRead(this);
 145                 if (oldmain == exp) {
 146                     if (CAS_ROOT(desc, nv)) {
 147                         desc.committed = true;
 148                         return nv;
 149                     }
 150
 151                     // Tail recursion: return RDCSS_Complete(abort);
 152                     continue;
 153                 }
 154
 155                 if (CAS_ROOT(desc, ov)) {
 156                     return ov;
 157                 }
 158
 159                 // Tail recursion: return RDCSS_Complete(abort);
 160                 continue;
 161             }
 162
 163             throw new IllegalStateException("Unexpected root " + v);
 164         }
 165     }
 166
 167     private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 168         final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
 169         if (CAS_ROOT(ov, desc)) {
 170             RDCSS_Complete(false);
 171             return /* READ */desc.committed;
 172         }
 173
 174         return false;
 175     }
 176
 177     private void inserthc(final K k, final int hc, final V v) {
 178         while (true) {
 179             final INode<K, V> r = RDCSS_READ_ROOT();
 180             if (r.rec_insert(k, v, hc, 0, null, r.gen, this)) {
 181                 // Successful, we are done
 182                 return;
 183             }
 184
 185             // Tail recursion: inserthc(k, hc, v);
 186         }
 187     }
 188
 189     private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
 190         while (true) {
 191             final INode<K, V> r = RDCSS_READ_ROOT();
 192             final Optional<V> ret = r.rec_insertif(k, v, hc, cond, 0, null, r.gen, this);
 193             if (ret != null) {
 194                 return ret;
 195             }
 196
 197             // Tail recursion: return insertifhc(k, hc, v, cond);
 198         }
 199     }
 200
 201     private Object lookuphc(final K k, final int hc) {
 202         while (true) {
 203             final INode<K, V> r = RDCSS_READ_ROOT ();
 204             final Object res = r.rec_lookup(k, hc, 0, null, r.gen, this);
 205             if (!INode.RESTART.equals(res)) {
 206                 return res;
 207             }
 208
 209             // Tail recursion: lookuphc(k, hc)
 210         }
 211     }
 212
 213     private Optional<V> removehc(final K k, final V v, final int hc) {
 214         while (true) {
 215             final INode<K, V> r = RDCSS_READ_ROOT();
 216             final Optional<V> res = r.rec_remove(k, v, hc, 0, null, r.gen, this);
 217             if (res != null) {
 218                 return res;
 219             }
 220
 221             // Tail recursion: return removehc(k, v, hc);
 222         }
 223     }
 224
 225     /**
 226      * Ensure this instance is read-write, throw UnsupportedOperationException
 227      * otherwise. Used by Map-type methods for quick check.
 228      */
 229     private void ensureReadWrite() {
 230         if (isReadOnly()) {
 231             throw new UnsupportedOperationException("Attempted to modify a read-only view");
 232         }
 233     }
 234
 235     boolean isReadOnly() {
 236         return readOnly;
 237     }
 238
 239     boolean nonReadOnly() {
 240         return !readOnly;
 241     }
 242
 243     /* public methods */
 244
 245     /**
 246      * Returns a snapshot of this TrieMap. This operation is lock-free and
 247      * linearizable.
 248      *
 249      * The snapshot is lazily updated - the first time some branch in the
 250      * snapshot or this TrieMap are accessed, they are rewritten. This means
 251      * that the work of rebuilding both the snapshot and this TrieMap is
 252      * distributed across all the threads doing updates or accesses subsequent
 253      * to the snapshot creation.
 254      */
 255     public TrieMap<K, V> snapshot() {
 256         while (true) {
 257             final INode<K, V> r = RDCSS_READ_ROOT();
 258             final MainNode<K, V> expmain = r.gcasRead(this);
 259             if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this))) {
 260                 return new TrieMap<> (r.copyToGen(new Gen(), this), equiv, readOnly);
 261             }
 262
 263             // Tail recursion: return snapshot();
 264         }
 265     }
 266
 267     /**
 268      * Returns a read-only snapshot of this TrieMap. This operation is lock-free
 269      * and linearizable.
 270      *
 271      * The snapshot is lazily updated - the first time some branch of this
 272      * TrieMap are accessed, it is rewritten. The work of creating the snapshot
 273      * is thus distributed across subsequent updates and accesses on this
 274      * TrieMap by all threads. Note that the snapshot itself is never rewritten
 275      * unlike when calling the `snapshot` method, but the obtained snapshot
 276      * cannot be modified.
 277      *
 278      * This method is used by other methods such as `size` and `iterator`.
 279      */
 280     public TrieMap<K, V> readOnlySnapshot() {
 281         // Is it a snapshot of a read-only snapshot?
 282         if (isReadOnly()) {
 283             return this;
 284         }
 285
 286         while (true) {
 287             final INode<K, V> r = RDCSS_READ_ROOT();
 288             final MainNode<K, V> expmain = r.gcasRead(this);
 289             if (RDCSS_ROOT(r, expmain, r.copyToGen (new Gen(), this))) {
 290                 return new TrieMap<>(r, equiv, true);
 291             }
 292
 293             // Tail recursion: return readOnlySnapshot();
 294         }
 295     }
 296
 297     @Override
 298     public void clear() {
 299         while (true) {
 300             final INode<K, V> r = RDCSS_READ_ROOT();
 301             if (RDCSS_ROOT(r, r.gcasRead(this), newRootNode())) {
 302                 return;
 303             }
 304         }
 305     }
 306
 307     int computeHash(final K k) {
 308         return equiv.hash(k);
 309     }
 310
 311     boolean equal(final K k1, final K k2) {
 312         return equiv.equivalent(k1, k2);
 313     }
 314
 315     V lookup(final K k) {
 316         final int hc = computeHash (k);
 317 //        return (V) lookuphc (k, hc);
 318         final Object o = lookuphc (k, hc);
 319         if (o instanceof Optional) {
 320             return ((Optional<V>) o).orElse(null);
 321         }
 322
 323         return (V)o;
 324     }
 325
 326     @Override
 327     public V get(final Object k) {
 328         return lookup((K)k);
 329     }
 330
 331     @Override
 332     public V put(final K key, final V value) {
 333         ensureReadWrite();
 334         final int hc = computeHash(key);
 335         return insertifhc (key, hc, value, null).orElse(null);
 336     }
 337
 338     TrieMap<K, V> add(final K k, final V v) {
 339         final int hc = computeHash (k);
 340         inserthc (k, hc, v);
 341         return this;
 342     }
 343
 344     @Override
 345     public V remove(final Object k) {
 346         ensureReadWrite();
 347         final int hc = computeHash ((K)k);
 348         return removehc ((K)k, (V) null, hc).orElse(null);
 349     }
 350
 351     @Override
 352     public V putIfAbsent(final K k, final V v) {
 353         ensureReadWrite();
 354         final int hc = computeHash (k);
 355         return insertifhc (k, hc, v, INode.KEY_ABSENT).orElse(null);
 356     }
 357
 358     @Override
 359     public boolean remove(final Object k, final Object v) {
 360         ensureReadWrite();
 361         final int hc = computeHash ((K)k);
 362         return removehc((K)k, (V)v, hc).isPresent();
 363     }
 364
 365     @Override
 366     public boolean replace(final K k, final V oldvalue, final V newvalue) {
 367         ensureReadWrite();
 368         final int hc = computeHash (k);
 369         return insertifhc (k, hc, newvalue, oldvalue).isPresent();
 370     }
 371
 372     @Override
 373     public V replace(final K k, final V v) {
 374         ensureReadWrite();
 375         final int hc = computeHash (k);
 376         return insertifhc (k, hc, v, INode.KEY_PRESENT).orElse(null);
 377     }
 378
 379     /***
 380      * Return an iterator over a TrieMap.
 381      *
 382      * If this is a read-only snapshot, it would return a read-only iterator.
 383      *
 384      * If it is the original TrieMap or a non-readonly snapshot, it would return
 385      * an iterator that would allow for updates.
 386      *
 387      * @return
 388      */
 389     Iterator<Entry<K, V>> iterator () {
 390         if (!nonReadOnly()) {
 391             return readOnlySnapshot().readOnlyIterator();
 392         }
 393
 394         return new TrieMapIterator<> (0, this);
 395     }
 396
 397     /***
 398      * Return an iterator over a TrieMap.
 399      * This is a read-only iterator.
 400      *
 401      * @return
 402      */
 403     Iterator<Entry<K, V>> readOnlyIterator () {
 404         if (nonReadOnly()) {
 405             return readOnlySnapshot().readOnlyIterator();
 406         }
 407
 408         return new TrieMapReadOnlyIterator<>(0, this);
 409     }
 410
 411     private int cachedSize() {
 412         INode<K, V> r = RDCSS_READ_ROOT ();
 413         return r.cachedSize (this);
 414     }
 415
 416     @Override
 417     public int size() {
 418         if (nonReadOnly()) {
 419             return readOnlySnapshot().size ();
 420         }
 421
 422         return cachedSize();
 423     }
 424
 425     @Override
 426     public boolean containsKey(final Object key) {
 427         return lookup((K) key) != null;
 428     }
 429
 430     @Override
 431     public Set<Entry<K, V>> entrySet() {
 432         return entrySet;
 433     }
 434
 435     private static final class RDCSS_Descriptor<K, V> {
 436         INode<K, V> old;
 437         MainNode<K, V> expectedmain;
 438         INode<K, V> nv;
 439         volatile boolean committed = false;
 440
 441         RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 442             this.old = old;
 443             this.expectedmain = expectedmain;
 444             this.nv = nv;
 445         }
 446     }
 447
 448     /***
 449      * This iterator is a read-only one and does not allow for any update
 450      * operations on the underlying data structure.
 451      *
 452      * @param <K>
 453      * @param <V>
 454      */
 455     private static final class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
 456         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
 457             super (level, ct, mustInit);
 458         }
 459
 460         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
 461             this (level, ct, true);
 462         }
 463         @Override
 464         void initialize () {
 465             assert (ct.isReadOnly ());
 466             super.initialize ();
 467         }
 468
 469         @Override
 470         public void remove () {
 471             throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
 472         }
 473
 474         @Override
 475         Entry<K, V> nextEntry(final Entry<K, V> rr) {
 476             // Return non-updatable entry
 477             return rr;
 478         }
 479     }
 480
 481     private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
 482         private int level;
 483         protected TrieMap<K, V> ct;
 484         private final boolean mustInit;
 485         private final BasicNode[][] stack = new BasicNode[7][];
 486         private final int[] stackpos = new int[7];
 487         private int depth = -1;
 488         private Iterator<Entry<K, V>> subiter = null;
 489         private KVNode<K, V> current = null;
 490         private Entry<K, V> lastReturned = null;
 491
 492         TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
 493             this.level = level;
 494             this.ct = ct;
 495             this.mustInit = mustInit;
 496             if (this.mustInit) {
 497                 initialize ();
 498             }
 499         }
 500
 501         TrieMapIterator (final int level, final TrieMap<K, V> ct) {
 502             this (level, ct, true);
 503         }
 504
 505
 506         @Override
 507         public boolean hasNext () {
 508             return (current != null) || (subiter != null);
 509         }
 510
 511         @Override
 512         public Entry<K, V> next () {
 513             if (hasNext ()) {
 514                 Entry<K, V> r = null;
 515                 if (subiter != null) {
 516                     r = subiter.next ();
 517                     checkSubiter ();
 518                 } else {
 519                     r = current.kvPair ();
 520                     advance ();
 521                 }
 522
 523                 lastReturned = r;
 524                 if (r != null) {
 525                     final Entry<K, V> rr = r;
 526                     return nextEntry(rr);
 527                 }
 528                 return r;
 529             } else {
 530                 // return Iterator.empty ().next ();
 531                 return null;
 532             }
 533         }
 534
 535         Entry<K, V> nextEntry(final Entry<K, V> rr) {
 536             return new Entry<K, V>() {
 537                 private V updated = null;
 538
 539                 @Override
 540                 public K getKey () {
 541                     return rr.getKey ();
 542                 }
 543
 544                 @Override
 545                 public V getValue () {
 546                     return (updated == null)?rr.getValue (): updated;
 547                 }
 548
 549                 @Override
 550                 public V setValue (final V value) {
 551                     updated = value;
 552                     return ct.replace (getKey (), value);
 553                 }
 554             };
 555         }
 556
 557         private void readin (final INode<K, V> in) {
 558             MainNode<K, V> m = in.gcasRead (ct);
 559             if (m instanceof CNode) {
 560                 CNode<K, V> cn = (CNode<K, V>) m;
 561                 depth += 1;
 562                 stack [depth] = cn.array;
 563                 stackpos [depth] = -1;
 564                 advance ();
 565             } else if (m instanceof TNode) {
 566                 current = (TNode<K, V>) m;
 567             } else if (m instanceof LNode) {
 568                 subiter = ((LNode<K, V>) m).iterator();
 569                 checkSubiter ();
 570             } else if (m == null) {
 571                 current = null;
 572             }
 573         }
 574
 575         // @inline
 576         private void checkSubiter () {
 577             if (!subiter.hasNext ()) {
 578                 subiter = null;
 579                 advance ();
 580             }
 581         }
 582
 583         // @inline
 584         void initialize () {
 585 //            assert (ct.isReadOnly ());
 586             INode<K, V> r = ct.RDCSS_READ_ROOT ();
 587             readin (r);
 588         }
 589
 590         void advance () {
 591             if (depth >= 0) {
 592                 int npos = stackpos [depth] + 1;
 593                 if (npos < stack [depth].length) {
 594                     stackpos [depth] = npos;
 595                     BasicNode elem = stack [depth] [npos];
 596                     if (elem instanceof SNode) {
 597                         current = (SNode<K, V>) elem;
 598                     } else if (elem instanceof INode) {
 599                         readin ((INode<K, V>) elem);
 600                     }
 601                 } else {
 602                     depth -= 1;
 603                     advance ();
 604                 }
 605             } else {
 606                 current = null;
 607             }
 608         }
 609
 610         protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
 611             return new TrieMapIterator<> (_lev, _ct, _mustInit);
 612         }
 613
 614         protected void dupTo (final TrieMapIterator<K, V> it) {
 615             it.level = this.level;
 616             it.ct = this.ct;
 617             it.depth = this.depth;
 618             it.current = this.current;
 619
 620             // these need a deep copy
 621             System.arraycopy (this.stack, 0, it.stack, 0, 7);
 622             System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
 623
 624             // this one needs to be evaluated
 625             if (this.subiter == null) {
 626                 it.subiter = null;
 627             } else {
 628                 List<Entry<K, V>> lst = toList (this.subiter);
 629                 this.subiter = lst.iterator ();
 630                 it.subiter = lst.iterator ();
 631             }
 632         }
 633
 634         // /** Returns a sequence of iterators over subsets of this iterator.
 635         // * It's used to ease the implementation of splitters for a parallel
 636         // version of the TrieMap.
 637         // */
 638         // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
 639         // null) {
 640         // // the case where an LNode is being iterated
 641         // val it = subiter
 642         // subiter = null
 643         // advance()
 644         // this.level += 1
 645         // Seq(it, this)
 646         // } else if (depth == -1) {
 647         // this.level += 1
 648         // Seq(this)
 649         // } else {
 650         // var d = 0
 651         // while (d <= depth) {
 652         // val rem = stack(d).length - 1 - stackpos(d)
 653         // if (rem > 0) {
 654         // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
 655         // stack(d) = arr1
 656         // stackpos(d) = -1
 657         // val it = newIterator(level + 1, ct, false)
 658         // it.stack(0) = arr2
 659         // it.stackpos(0) = -1
 660         // it.depth = 0
 661         // it.advance() // <-- fix it
 662         // this.level += 1
 663         // return Seq(this, it)
 664         // }
 665         // d += 1
 666         // }
 667         // this.level += 1
 668         // Seq(this)
 669         // }
 670
 671         private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
 672             ArrayList<Entry<K, V>> list = new ArrayList<> ();
 673             while (it.hasNext ()) {
 674                 list.add (it.next ());
 675             }
 676             return list;
 677         }
 678
 679         void printDebug () {
 680             System.out.println ("ctrie iterator");
 681             System.out.println (Arrays.toString (stackpos));
 682             System.out.println ("depth: " + depth);
 683             System.out.println ("curr.: " + current);
 684             // System.out.println(stack.mkString("\n"));
 685         }
 686
 687         @Override
 688         public void remove () {
 689             if (lastReturned != null) {
 690                 ct.remove (lastReturned.getKey ());
 691                 lastReturned = null;
 692             } else {
 693                 throw new IllegalStateException();
 694             }
 695         }
 696
 697     }
 698
 699     /***
 700      * Support for EntrySet operations required by the Map interface
 701      */
 702     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 703
 704         @Override
 705         public Iterator<Entry<K, V>> iterator () {
 706             return TrieMap.this.iterator ();
 707         }
 708
 709         @Override
 710         public final boolean contains (final Object o) {
 711             if (!(o instanceof Entry)) {
 712                 return false;
 713             }
 714             final Entry<K, V> e = (Entry<K, V>) o;
 715             final K k = e.getKey ();
 716             final V v = lookup (k);
 717             return v != null;
 718         }
 719
 720         @Override
 721         public final boolean remove (final Object o) {
 722             if (!(o instanceof Entry)) {
 723                 return false;
 724             }
 725             final Entry<K, V> e = (Entry<K, V>) o;
 726             final K k = e.getKey();
 727             return null != TrieMap.this.remove(k);
 728         }
 729
 730         @Override
 731         public final int size () {
 732             int size = 0;
 733             for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
 734                 size++;
 735             }
 736             return size;
 737         }
 738
 739         @Override
 740         public final void clear () {
 741             TrieMap.this.clear ();
 742         }
 743     }
 744
 745     private void readObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
 746         inputStream.defaultReadObject();
 747         this.root = newRootNode();
 748
 749         final boolean ro = inputStream.readBoolean();
 750         final int size = inputStream.readInt();
 751         for (int i = 0; i < size; ++i) {
 752             final K key = (K)inputStream.readObject();
 753             final V value = (V)inputStream.readObject();
 754             add(key, value);
 755         }
 756
 757         // Propagate the read-only bit
 758         try {
 759             READONLY_FIELD.setBoolean(this, ro);
 760         } catch (IllegalAccessException e) {
 761             throw new IOException("Failed to set read-only flag", e);
 762         }
 763     }
 764
 765     private void writeObject(final ObjectOutputStream outputStream) throws IOException {
 766         outputStream.defaultWriteObject();
 767
 768         final Map<K, V> ro = readOnlySnapshot();
 769         outputStream.writeBoolean(isReadOnly());
 770         outputStream.writeInt(ro.size());
 771
 772         for (Entry<K, V> e : ro.entrySet()) {
 773             outputStream.writeObject(e.getKey());
 774             outputStream.writeObject(e.getValue());
 775         }
 776     }
 777 }