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         return (V) lookuphc(k, computeHash(k));
 317     }
 318
 319     @Override
 320     public V get(final Object k) {
 321         return lookup((K)k);
 322     }
 323
 324     @Override
 325     public V put(final K key, final V value) {
 326         ensureReadWrite();
 327         final int hc = computeHash(key);
 328         return insertifhc (key, hc, value, null).orElse(null);
 329     }
 330
 331     TrieMap<K, V> add(final K k, final V v) {
 332         final int hc = computeHash (k);
 333         inserthc (k, hc, v);
 334         return this;
 335     }
 336
 337     @Override
 338     public V remove(final Object k) {
 339         ensureReadWrite();
 340         final int hc = computeHash ((K)k);
 341         return removehc ((K)k, (V) null, hc).orElse(null);
 342     }
 343
 344     @Override
 345     public V putIfAbsent(final K k, final V v) {
 346         ensureReadWrite();
 347         final int hc = computeHash (k);
 348         return insertifhc (k, hc, v, INode.KEY_ABSENT).orElse(null);
 349     }
 350
 351     @Override
 352     public boolean remove(final Object k, final Object v) {
 353         ensureReadWrite();
 354         final int hc = computeHash ((K)k);
 355         return removehc((K)k, (V)v, hc).isPresent();
 356     }
 357
 358     @Override
 359     public boolean replace(final K k, final V oldvalue, final V newvalue) {
 360         ensureReadWrite();
 361         final int hc = computeHash (k);
 362         return insertifhc (k, hc, newvalue, oldvalue).isPresent();
 363     }
 364
 365     @Override
 366     public V replace(final K k, final V v) {
 367         ensureReadWrite();
 368         final int hc = computeHash (k);
 369         return insertifhc (k, hc, v, INode.KEY_PRESENT).orElse(null);
 370     }
 371
 372     /***
 373      * Return an iterator over a TrieMap.
 374      *
 375      * If this is a read-only snapshot, it would return a read-only iterator.
 376      *
 377      * If it is the original TrieMap or a non-readonly snapshot, it would return
 378      * an iterator that would allow for updates.
 379      *
 380      * @return
 381      */
 382     Iterator<Entry<K, V>> iterator () {
 383         if (!nonReadOnly()) {
 384             return readOnlySnapshot().readOnlyIterator();
 385         }
 386
 387         return new TrieMapIterator<> (0, this);
 388     }
 389
 390     /***
 391      * Return an iterator over a TrieMap.
 392      * This is a read-only iterator.
 393      *
 394      * @return
 395      */
 396     Iterator<Entry<K, V>> readOnlyIterator () {
 397         if (nonReadOnly()) {
 398             return readOnlySnapshot().readOnlyIterator();
 399         }
 400
 401         return new TrieMapReadOnlyIterator<>(0, this);
 402     }
 403
 404     private int cachedSize() {
 405         INode<K, V> r = RDCSS_READ_ROOT ();
 406         return r.cachedSize (this);
 407     }
 408
 409     @Override
 410     public int size() {
 411         if (nonReadOnly()) {
 412             return readOnlySnapshot().size ();
 413         }
 414
 415         return cachedSize();
 416     }
 417
 418     @Override
 419     public boolean containsKey(final Object key) {
 420         return lookup((K) key) != null;
 421     }
 422
 423     @Override
 424     public Set<Entry<K, V>> entrySet() {
 425         return entrySet;
 426     }
 427
 428     private static final class RDCSS_Descriptor<K, V> {
 429         INode<K, V> old;
 430         MainNode<K, V> expectedmain;
 431         INode<K, V> nv;
 432         volatile boolean committed = false;
 433
 434         RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 435             this.old = old;
 436             this.expectedmain = expectedmain;
 437             this.nv = nv;
 438         }
 439     }
 440
 441     /***
 442      * This iterator is a read-only one and does not allow for any update
 443      * operations on the underlying data structure.
 444      *
 445      * @param <K>
 446      * @param <V>
 447      */
 448     private static final class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
 449         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
 450             super (level, ct, mustInit);
 451         }
 452
 453         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
 454             this (level, ct, true);
 455         }
 456         @Override
 457         void initialize () {
 458             assert (ct.isReadOnly ());
 459             super.initialize ();
 460         }
 461
 462         @Override
 463         public void remove () {
 464             throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
 465         }
 466
 467         @Override
 468         Entry<K, V> nextEntry(final Entry<K, V> rr) {
 469             // Return non-updatable entry
 470             return rr;
 471         }
 472     }
 473
 474     private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
 475         private int level;
 476         protected TrieMap<K, V> ct;
 477         private final boolean mustInit;
 478         private final BasicNode[][] stack = new BasicNode[7][];
 479         private final int[] stackpos = new int[7];
 480         private int depth = -1;
 481         private Iterator<Entry<K, V>> subiter = null;
 482         private KVNode<K, V> current = null;
 483         private Entry<K, V> lastReturned = null;
 484
 485         TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
 486             this.level = level;
 487             this.ct = ct;
 488             this.mustInit = mustInit;
 489             if (this.mustInit) {
 490                 initialize ();
 491             }
 492         }
 493
 494         TrieMapIterator (final int level, final TrieMap<K, V> ct) {
 495             this (level, ct, true);
 496         }
 497
 498
 499         @Override
 500         public boolean hasNext () {
 501             return (current != null) || (subiter != null);
 502         }
 503
 504         @Override
 505         public Entry<K, V> next () {
 506             if (hasNext ()) {
 507                 Entry<K, V> r = null;
 508                 if (subiter != null) {
 509                     r = subiter.next ();
 510                     checkSubiter ();
 511                 } else {
 512                     r = current.kvPair ();
 513                     advance ();
 514                 }
 515
 516                 lastReturned = r;
 517                 if (r != null) {
 518                     final Entry<K, V> rr = r;
 519                     return nextEntry(rr);
 520                 }
 521                 return r;
 522             } else {
 523                 // return Iterator.empty ().next ();
 524                 return null;
 525             }
 526         }
 527
 528         Entry<K, V> nextEntry(final Entry<K, V> rr) {
 529             return new Entry<K, V>() {
 530                 private V updated = null;
 531
 532                 @Override
 533                 public K getKey () {
 534                     return rr.getKey ();
 535                 }
 536
 537                 @Override
 538                 public V getValue () {
 539                     return (updated == null)?rr.getValue (): updated;
 540                 }
 541
 542                 @Override
 543                 public V setValue (final V value) {
 544                     updated = value;
 545                     return ct.replace (getKey (), value);
 546                 }
 547             };
 548         }
 549
 550         private void readin (final INode<K, V> in) {
 551             MainNode<K, V> m = in.gcasRead (ct);
 552             if (m instanceof CNode) {
 553                 CNode<K, V> cn = (CNode<K, V>) m;
 554                 depth += 1;
 555                 stack [depth] = cn.array;
 556                 stackpos [depth] = -1;
 557                 advance ();
 558             } else if (m instanceof TNode) {
 559                 current = (TNode<K, V>) m;
 560             } else if (m instanceof LNode) {
 561                 subiter = ((LNode<K, V>) m).iterator();
 562                 checkSubiter ();
 563             } else if (m == null) {
 564                 current = null;
 565             }
 566         }
 567
 568         // @inline
 569         private void checkSubiter () {
 570             if (!subiter.hasNext ()) {
 571                 subiter = null;
 572                 advance ();
 573             }
 574         }
 575
 576         // @inline
 577         void initialize () {
 578 //            assert (ct.isReadOnly ());
 579             INode<K, V> r = ct.RDCSS_READ_ROOT ();
 580             readin (r);
 581         }
 582
 583         void advance () {
 584             if (depth >= 0) {
 585                 int npos = stackpos [depth] + 1;
 586                 if (npos < stack [depth].length) {
 587                     stackpos [depth] = npos;
 588                     BasicNode elem = stack [depth] [npos];
 589                     if (elem instanceof SNode) {
 590                         current = (SNode<K, V>) elem;
 591                     } else if (elem instanceof INode) {
 592                         readin ((INode<K, V>) elem);
 593                     }
 594                 } else {
 595                     depth -= 1;
 596                     advance ();
 597                 }
 598             } else {
 599                 current = null;
 600             }
 601         }
 602
 603         protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
 604             return new TrieMapIterator<> (_lev, _ct, _mustInit);
 605         }
 606
 607         protected void dupTo (final TrieMapIterator<K, V> it) {
 608             it.level = this.level;
 609             it.ct = this.ct;
 610             it.depth = this.depth;
 611             it.current = this.current;
 612
 613             // these need a deep copy
 614             System.arraycopy (this.stack, 0, it.stack, 0, 7);
 615             System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
 616
 617             // this one needs to be evaluated
 618             if (this.subiter == null) {
 619                 it.subiter = null;
 620             } else {
 621                 List<Entry<K, V>> lst = toList (this.subiter);
 622                 this.subiter = lst.iterator ();
 623                 it.subiter = lst.iterator ();
 624             }
 625         }
 626
 627         // /** Returns a sequence of iterators over subsets of this iterator.
 628         // * It's used to ease the implementation of splitters for a parallel
 629         // version of the TrieMap.
 630         // */
 631         // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
 632         // null) {
 633         // // the case where an LNode is being iterated
 634         // val it = subiter
 635         // subiter = null
 636         // advance()
 637         // this.level += 1
 638         // Seq(it, this)
 639         // } else if (depth == -1) {
 640         // this.level += 1
 641         // Seq(this)
 642         // } else {
 643         // var d = 0
 644         // while (d <= depth) {
 645         // val rem = stack(d).length - 1 - stackpos(d)
 646         // if (rem > 0) {
 647         // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
 648         // stack(d) = arr1
 649         // stackpos(d) = -1
 650         // val it = newIterator(level + 1, ct, false)
 651         // it.stack(0) = arr2
 652         // it.stackpos(0) = -1
 653         // it.depth = 0
 654         // it.advance() // <-- fix it
 655         // this.level += 1
 656         // return Seq(this, it)
 657         // }
 658         // d += 1
 659         // }
 660         // this.level += 1
 661         // Seq(this)
 662         // }
 663
 664         private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
 665             ArrayList<Entry<K, V>> list = new ArrayList<> ();
 666             while (it.hasNext ()) {
 667                 list.add (it.next ());
 668             }
 669             return list;
 670         }
 671
 672         void printDebug () {
 673             System.out.println ("ctrie iterator");
 674             System.out.println (Arrays.toString (stackpos));
 675             System.out.println ("depth: " + depth);
 676             System.out.println ("curr.: " + current);
 677             // System.out.println(stack.mkString("\n"));
 678         }
 679
 680         @Override
 681         public void remove () {
 682             if (lastReturned != null) {
 683                 ct.remove (lastReturned.getKey ());
 684                 lastReturned = null;
 685             } else {
 686                 throw new IllegalStateException();
 687             }
 688         }
 689
 690     }
 691
 692     /***
 693      * Support for EntrySet operations required by the Map interface
 694      */
 695     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 696
 697         @Override
 698         public Iterator<Entry<K, V>> iterator () {
 699             return TrieMap.this.iterator ();
 700         }
 701
 702         @Override
 703         public final boolean contains (final Object o) {
 704             if (!(o instanceof Entry)) {
 705                 return false;
 706             }
 707             final Entry<K, V> e = (Entry<K, V>) o;
 708             final K k = e.getKey ();
 709             final V v = lookup (k);
 710             return v != null;
 711         }
 712
 713         @Override
 714         public final boolean remove (final Object o) {
 715             if (!(o instanceof Entry)) {
 716                 return false;
 717             }
 718             final Entry<K, V> e = (Entry<K, V>) o;
 719             final K k = e.getKey();
 720             return null != TrieMap.this.remove(k);
 721         }
 722
 723         @Override
 724         public final int size () {
 725             int size = 0;
 726             for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
 727                 size++;
 728             }
 729             return size;
 730         }
 731
 732         @Override
 733         public final void clear () {
 734             TrieMap.this.clear ();
 735         }
 736     }
 737
 738     private void readObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
 739         inputStream.defaultReadObject();
 740         this.root = newRootNode();
 741
 742         final boolean ro = inputStream.readBoolean();
 743         final int size = inputStream.readInt();
 744         for (int i = 0; i < size; ++i) {
 745             final K key = (K)inputStream.readObject();
 746             final V value = (V)inputStream.readObject();
 747             add(key, value);
 748         }
 749
 750         // Propagate the read-only bit
 751         try {
 752             READONLY_FIELD.setBoolean(this, ro);
 753         } catch (IllegalAccessException e) {
 754             throw new IOException("Failed to set read-only flag", e);
 755         }
 756     }
 757
 758     private void writeObject(final ObjectOutputStream outputStream) throws IOException {
 759         outputStream.defaultWriteObject();
 760
 761         final Map<K, V> ro = readOnlySnapshot();
 762         outputStream.writeBoolean(isReadOnly());
 763         outputStream.writeInt(ro.size());
 764
 765         for (Entry<K, V> e : ro.entrySet()) {
 766             outputStream.writeObject(e.getKey());
 767             outputStream.writeObject(e.getValue());
 768         }
 769     }
 770 }