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 static com.google.common.base.Preconditions.checkNotNull;
  19 import static com.google.common.base.Preconditions.checkState;
  20 import static org.opendaylight.yangtools.triemap.LookupResult.RESTART;
  21
  22 import com.google.common.annotations.Beta;
  23 import java.io.ObjectStreamException;
  24 import java.io.Serializable;
  25 import java.util.AbstractMap;
  26 import java.util.AbstractSet;
  27 import java.util.ArrayList;
  28 import java.util.Iterator;
  29 import java.util.List;
  30 import java.util.NoSuchElementException;
  31 import java.util.Optional;
  32 import java.util.Set;
  33 import java.util.concurrent.ConcurrentMap;
  34
  35 /***
  36  * This is a port of Scala's TrieMap class from the Scala Collections library. This implementation does not support
  37  * null keys nor null values.
  38  *
  39  * @author Aleksandar Prokopec (original Scala implementation)
  40  * @author Roman Levenstein (original Java 6 port)
  41  * @author Robert Varga
  42  *
  43  * @param <K> the type of keys maintained by this map
  44  * @param <V> the type of mapped values
  45  */
  46 @Beta
  47 public abstract class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
  48     private static final long serialVersionUID = 1L;
  49
  50     /**
  51      * EntrySet
  52      */
  53     private final EntrySet entrySet = new EntrySet();
  54     private final Equivalence<? super K> equiv;
  55
  56     TrieMap(final Equivalence<? super K> equiv) {
  57         this.equiv = equiv;
  58     }
  59
  60     public static <K, V> TrieMap<K, V> create() {
  61         return new MutableTrieMap<>(Equivalence.equals());
  62     }
  63
  64     /**
  65      * Returns a snapshot of this TrieMap. This operation is lock-free and
  66      * linearizable.
  67      *
  68      * The snapshot is lazily updated - the first time some branch in the
  69      * snapshot or this TrieMap are accessed, they are rewritten. This means
  70      * that the work of rebuilding both the snapshot and this TrieMap is
  71      * distributed across all the threads doing updates or accesses subsequent
  72      * to the snapshot creation.
  73      */
  74     public abstract TrieMap<K, V> mutableSnapshot();
  75
  76     /**
  77      * Returns a read-only snapshot of this TrieMap. This operation is lock-free
  78      * and linearizable.
  79      *
  80      * The snapshot is lazily updated - the first time some branch of this
  81      * TrieMap are accessed, it is rewritten. The work of creating the snapshot
  82      * is thus distributed across subsequent updates and accesses on this
  83      * TrieMap by all threads. Note that the snapshot itself is never rewritten
  84      * unlike when calling the `snapshot` method, but the obtained snapshot
  85      * cannot be modified.
  86      *
  87      * This method is used by other methods such as `size` and `iterator`.
  88      */
  89     public abstract ImmutableTrieMap<K, V> immutableSnapshot();
  90
  91     @Override
  92     public final boolean containsKey(final Object key) {
  93         return get(key) != null;
  94     }
  95
  96     @Override
  97     public final boolean containsValue(final Object value) {
  98         return super.containsValue(checkNotNull(value));
  99     }
 100
 101     @Override
 102     public final Set<Entry<K, V>> entrySet() {
 103         return entrySet;
 104     }
 105
 106     @Override
 107     public final V get(final Object key) {
 108         @SuppressWarnings("unchecked")
 109         final K k = (K) checkNotNull(key);
 110         return lookuphc(k, computeHash(k));
 111     }
 112
 113     @Override
 114     public abstract void clear();
 115
 116     @Override
 117     public abstract V put(K key, V value);
 118
 119     @Override
 120     public abstract V putIfAbsent(K key, V value);
 121
 122     @Override
 123     public abstract V remove(Object key);
 124
 125     @Override
 126     public abstract boolean remove(Object key, Object value);
 127
 128     @Override
 129     public abstract boolean replace(K key, V oldValue, V newValue);
 130
 131     @Override
 132     public abstract V replace(K key, V value);
 133
 134     @Override
 135     public abstract int size();
 136
 137     /* internal methods implemented by subclasses */
 138
 139     abstract boolean isReadOnly();
 140
 141     abstract INode<K, V> RDCSS_READ_ROOT(boolean abort);
 142
 143     /* internal methods provided for subclasses */
 144
 145     @SuppressWarnings("null")
 146     static <V> V toNullable(final Optional<V> opt) {
 147         return opt.orElse(null);
 148     }
 149
 150     final int computeHash(final K k) {
 151         return equiv.hash(k);
 152     }
 153
 154     final Object writeReplace() throws ObjectStreamException {
 155         return new SerializationProxy(immutableSnapshot(), isReadOnly());
 156     }
 157
 158     /* package-protected utility methods */
 159
 160     final Equivalence<? super K> equiv() {
 161         return equiv;
 162     }
 163
 164     final INode<K, V> readRoot() {
 165         return RDCSS_READ_ROOT(false);
 166     }
 167
 168     // FIXME: abort = false by default
 169     final INode<K, V> readRoot(final boolean abort) {
 170         return RDCSS_READ_ROOT(abort);
 171     }
 172
 173     final INode<K, V> RDCSS_READ_ROOT() {
 174         return RDCSS_READ_ROOT(false);
 175     }
 176
 177     final boolean equal(final K k1, final K k2) {
 178         return equiv.equivalent(k1, k2);
 179     }
 180
 181     /* private implementation methods */
 182
 183     @SuppressWarnings("unchecked")
 184     private V lookuphc(final K k, final int hc) {
 185         Object res;
 186         do {
 187             // Keep looping as long as RESTART is being indicated
 188             res = RDCSS_READ_ROOT().rec_lookup(k, hc, 0, null, this);
 189         } while (res == RESTART);
 190
 191         return (V) res;
 192     }
 193
 194     /**
 195      * Return an iterator over a TrieMap.
 196      *
 197      * If this is a read-only snapshot, it would return a read-only iterator.
 198      *
 199      * If it is the original TrieMap or a non-readonly snapshot, it would return
 200      * an iterator that would allow for updates.
 201      *
 202      * @return
 203      */
 204     Iterator<Entry<K, V>> iterator() {
 205         // FIXME: it would be nice to have a ReadWriteTrieMap with read-only iterator
 206         return isReadOnly() ? new TrieMapReadOnlyIterator<>(0, this) : new TrieMapIterator<>(0, this);
 207     }
 208
 209     /**
 210      * Return an iterator over a TrieMap.
 211      * This is a read-only iterator.
 212      *
 213      * @return
 214      */
 215     final Iterator<Entry<K, V>> readOnlyIterator() {
 216         return new TrieMapReadOnlyIterator<>(0, immutableSnapshot());
 217     }
 218
 219     /**
 220      * This iterator is a read-only one and does not allow for any update
 221      * operations on the underlying data structure.
 222      *
 223      * @param <K>
 224      * @param <V>
 225      */
 226     private static final class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
 227         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
 228             super (level, ct, mustInit);
 229         }
 230
 231         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
 232             this (level, ct, true);
 233         }
 234         @Override
 235         void initialize () {
 236             assert (ct.isReadOnly ());
 237             super.initialize ();
 238         }
 239
 240         @Override
 241         public void remove () {
 242             throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
 243         }
 244
 245         @Override
 246         Entry<K, V> nextEntry(final Entry<K, V> rr) {
 247             // Return non-updatable entry
 248             return rr;
 249         }
 250     }
 251
 252     private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
 253         private int level;
 254         protected TrieMap<K, V> ct;
 255         private final boolean mustInit;
 256         private final BasicNode[][] stack = new BasicNode[7][];
 257         private final int[] stackpos = new int[7];
 258         private int depth = -1;
 259         private Iterator<Entry<K, V>> subiter = null;
 260         private EntryNode<K, V> current = null;
 261         private Entry<K, V> lastReturned = null;
 262
 263         TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
 264             this.level = level;
 265             this.ct = ct;
 266             this.mustInit = mustInit;
 267             if (this.mustInit) {
 268                 initialize ();
 269             }
 270         }
 271
 272         TrieMapIterator (final int level, final TrieMap<K, V> ct) {
 273             this (level, ct, true);
 274         }
 275
 276
 277         @Override
 278         public boolean hasNext() {
 279             return (current != null) || (subiter != null);
 280         }
 281
 282         @Override
 283         public Entry<K, V> next() {
 284             if (!hasNext()) {
 285                 throw new NoSuchElementException();
 286             }
 287
 288             final Entry<K, V> r;
 289             if (subiter != null) {
 290                 r = subiter.next();
 291                 checkSubiter();
 292             } else {
 293                 r = current;
 294                 advance();
 295             }
 296
 297             lastReturned = r;
 298             if (r != null) {
 299                 final Entry<K, V> rr = r;
 300                 return nextEntry(rr);
 301             }
 302             return r;
 303         }
 304
 305         Entry<K, V> nextEntry(final Entry<K, V> rr) {
 306             return new Entry<K, V>() {
 307                 @SuppressWarnings("null")
 308                 private V updated = null;
 309
 310                 @Override
 311                 public K getKey () {
 312                     return rr.getKey ();
 313                 }
 314
 315                 @Override
 316                 public V getValue () {
 317                     return (updated == null) ? rr.getValue (): updated;
 318                 }
 319
 320                 @Override
 321                 public V setValue (final V value) {
 322                     updated = value;
 323                     return ct.replace (getKey (), value);
 324                 }
 325             };
 326         }
 327
 328         private void readin (final INode<K, V> in) {
 329             MainNode<K, V> m = in.gcasRead (ct);
 330             if (m instanceof CNode) {
 331                 CNode<K, V> cn = (CNode<K, V>) m;
 332                 depth += 1;
 333                 stack [depth] = cn.array;
 334                 stackpos [depth] = -1;
 335                 advance ();
 336             } else if (m instanceof TNode) {
 337                 current = (TNode<K, V>) m;
 338             } else if (m instanceof LNode) {
 339                 subiter = ((LNode<K, V>) m).iterator();
 340                 checkSubiter ();
 341             } else if (m == null) {
 342                 current = null;
 343             }
 344         }
 345
 346         // @inline
 347         private void checkSubiter () {
 348             if (!subiter.hasNext ()) {
 349                 subiter = null;
 350                 advance ();
 351             }
 352         }
 353
 354         // @inline
 355         void initialize () {
 356 //            assert (ct.isReadOnly ());
 357             readin(ct.RDCSS_READ_ROOT());
 358         }
 359
 360         void advance () {
 361             if (depth >= 0) {
 362                 int npos = stackpos [depth] + 1;
 363                 if (npos < stack [depth].length) {
 364                     stackpos [depth] = npos;
 365                     BasicNode elem = stack [depth] [npos];
 366                     if (elem instanceof SNode) {
 367                         current = (SNode<K, V>) elem;
 368                     } else if (elem instanceof INode) {
 369                         readin ((INode<K, V>) elem);
 370                     }
 371                 } else {
 372                     depth -= 1;
 373                     advance ();
 374                 }
 375             } else {
 376                 current = null;
 377             }
 378         }
 379
 380         protected TrieMapIterator<K, V> newIterator(final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
 381             return new TrieMapIterator<> (_lev, _ct, _mustInit);
 382         }
 383
 384         protected void dupTo(final TrieMapIterator<K, V> it) {
 385             it.level = this.level;
 386             it.ct = this.ct;
 387             it.depth = this.depth;
 388             it.current = this.current;
 389
 390             // these need a deep copy
 391             System.arraycopy (this.stack, 0, it.stack, 0, 7);
 392             System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
 393
 394             // this one needs to be evaluated
 395             if (this.subiter == null) {
 396                 it.subiter = null;
 397             } else {
 398                 List<Entry<K, V>> lst = toList (this.subiter);
 399                 this.subiter = lst.iterator ();
 400                 it.subiter = lst.iterator ();
 401             }
 402         }
 403
 404         // /** Returns a sequence of iterators over subsets of this iterator.
 405         // * It's used to ease the implementation of splitters for a parallel
 406         // version of the TrieMap.
 407         // */
 408         // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
 409         // null) {
 410         // // the case where an LNode is being iterated
 411         // val it = subiter
 412         // subiter = null
 413         // advance()
 414         // this.level += 1
 415         // Seq(it, this)
 416         // } else if (depth == -1) {
 417         // this.level += 1
 418         // Seq(this)
 419         // } else {
 420         // var d = 0
 421         // while (d <= depth) {
 422         // val rem = stack(d).length - 1 - stackpos(d)
 423         // if (rem > 0) {
 424         // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
 425         // stack(d) = arr1
 426         // stackpos(d) = -1
 427         // val it = newIterator(level + 1, ct, false)
 428         // it.stack(0) = arr2
 429         // it.stackpos(0) = -1
 430         // it.depth = 0
 431         // it.advance() // <-- fix it
 432         // this.level += 1
 433         // return Seq(this, it)
 434         // }
 435         // d += 1
 436         // }
 437         // this.level += 1
 438         // Seq(this)
 439         // }
 440
 441         private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
 442             ArrayList<Entry<K, V>> list = new ArrayList<> ();
 443             while (it.hasNext ()) {
 444                 list.add (it.next());
 445             }
 446             return list;
 447         }
 448
 449         @Override
 450         public void remove() {
 451             checkState(lastReturned != null);
 452             ct.remove(lastReturned.getKey());
 453             lastReturned = null;
 454         }
 455     }
 456
 457     /***
 458      * Support for EntrySet operations required by the Map interface
 459      */
 460     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 461         @Override
 462         public Iterator<Entry<K, V>> iterator() {
 463             return TrieMap.this.iterator ();
 464         }
 465
 466         @Override
 467         public final boolean contains(final Object o) {
 468             if (!(o instanceof Entry)) {
 469                 return false;
 470             }
 471
 472             final Entry<?, ?> e = (Entry<?, ?>) o;
 473             if (e.getKey() == null) {
 474                 return false;
 475             }
 476             final V v = get(e.getKey());
 477             return v != null && v.equals(e.getValue());
 478         }
 479
 480         @Override
 481         public final boolean remove(final Object o) {
 482             if (!(o instanceof Entry)) {
 483                 return false;
 484             }
 485             final Entry<?, ?> e = (Entry<?, ?>) o;
 486             final Object key = e.getKey();
 487             if (key == null) {
 488                 return false;
 489             }
 490             final Object value = e.getValue();
 491             if (value == null) {
 492                 return false;
 493             }
 494
 495             return TrieMap.this.remove(key, value);
 496         }
 497
 498         @Override
 499         public final int size () {
 500             return TrieMap.this.size();
 501         }
 502
 503         @Override
 504         public final void clear () {
 505             TrieMap.this.clear ();
 506         }
 507     }
 508 }