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