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