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