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