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