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