third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntries.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 /**
  19  * Similar to Scala's ListMap, this is a single-linked list of set of map entries. Aside from the Set contract, this
  20  * class fulfills the requirements for an immutable map entryset.
  21  *
  22  * @author Robert Varga
  23  *
  24  * @param <K> the type of keys
  25  * @param <V> the type of values
  26  */
  27 abstract class LNodeEntries<K, V> extends LNodeEntry<K, V> {
  28     private static final class Single<K, V> extends LNodeEntries<K, V> {
  29         Single(final K k, final V v) {
  30             super(k, v);
  31         }
  32
  33         @Override
  34         LNodeEntries<K, V> next() {
  35             return null;
  36         }
  37     }
  38
  39     private static final class Multiple<K, V> extends LNodeEntries<K, V> {
  40         // Modified during remove only, otherwise final
  41         LNodeEntries<K, V> next;
  42
  43         // Used in remove() only
  44         Multiple(final LNodeEntries<K, V> e) {
  45             this(e.getKey(), e.getValue(), null);
  46         }
  47
  48         Multiple(final K k, final V v, final LNodeEntries<K, V> next) {
  49             super(k, v);
  50             this.next = next;
  51         }
  52
  53         @Override
  54         LNodeEntries<K, V> next() {
  55             return next;
  56         }
  57     }
  58
  59     LNodeEntries(final K k, final V v) {
  60         super(k, v);
  61     }
  62
  63     static <K,V> LNodeEntries<K, V> map(final K k1, final V v1, final K k2, final V v2) {
  64         return new Multiple<>(k1, v1, new Single<>(k2, v2));
  65     }
  66
  67     /**
  68      * Return the remainder of this list. Useful for implementing Iterator-like contract. Null indicates there are no
  69      * more entries.
  70      *
  71      * @return Remainder of this list, or null if nothing remains
  72      */
  73     abstract LNodeEntries<K, V> next();
  74
  75     final LNodeEntry<K, V> findEntry(final Equivalence<? super K> equiv, final K key) {
  76         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  77         LNodeEntries<K, V> entry = this;
  78         do {
  79             if (equiv.equivalent(entry.getKey(), key)) {
  80                 return entry;
  81             }
  82
  83             entry = entry.next();
  84         } while (entry != null);
  85
  86         return null;
  87     }
  88
  89     final LNodeEntries<K,V> insert(final K key, final V value) {
  90         return new Multiple<>(key, value, this);
  91     }
  92
  93     final LNodeEntries<K, V> replace(final LNodeEntry<K, V> entry, final V v) {
  94         final LNodeEntries<K, V> removed;
  95         return (removed = remove(entry)) == null ? new Single<>(entry.getKey(), v)
  96                 : new Multiple<>(entry.getKey(), v, removed);
  97     }
  98
  99     final LNodeEntries<K, V> remove(final LNodeEntry<K, V> entry) {
 100         if (entry == this) {
 101             return next();
 102         }
 103
 104         // This will result in a list with a long tail, i.e last entry storing explicit null. Overhead is amortized
 105         // against the number of entries. We do not retain chains shorter than two, so the worst-case overhead is
 106         // half-a-reference for an entry.
 107         final Multiple<K, V> ret = new Multiple<>(this);
 108
 109         Multiple<K, V> last = ret;
 110         LNodeEntries<K, V> cur = next();
 111         while (cur != null) {
 112             // We cannot use equals() here, as it is wired to key equality and we must never compare entries based on
 113             // that property. This method is intended to remove a known reference, so identity is what we want.
 114             if (entry == cur) {
 115                 last.next = cur.next();
 116                 return ret;
 117             }
 118
 119             final Multiple<K, V> tmp = new Multiple<>(cur);
 120             last.next = tmp;
 121             last = tmp;
 122             cur = cur.next();
 123         }
 124
 125         throw new IllegalStateException(String.format("Entry %s not found", entry));
 126     }
 127 }