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