third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java

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