binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapLookupState.java

   1 /*
   2  * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.mdsal.binding.dom.codec.impl;
   9
  10 import static java.util.Objects.requireNonNull;
  11 import static org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingList.OBJ_AA;
  12
  13 import com.google.common.collect.AbstractIterator;
  14 import com.google.common.collect.Iterators;
  15 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
  16 import java.lang.invoke.MethodHandles;
  17 import java.lang.invoke.VarHandle;
  18 import java.util.AbstractSet;
  19 import java.util.Iterator;
  20 import java.util.Map;
  21 import java.util.Map.Entry;
  22 import java.util.Optional;
  23 import java.util.concurrent.ConcurrentHashMap;
  24 import org.eclipse.jdt.annotation.NonNull;
  25 import org.eclipse.jdt.annotation.Nullable;
  26 import org.opendaylight.yangtools.concepts.Immutable;
  27 import org.opendaylight.yangtools.yang.binding.DataObject;
  28 import org.opendaylight.yangtools.yang.binding.Key;
  29 import org.opendaylight.yangtools.yang.binding.KeyAware;
  30 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
  31
  32 /**
  33  * {@link LazyBindingMap.State} optimized for lookup access, mainly via {@link Map#values()}. Note that this
  34  * implementation, while being effectively immutable, does not guarantee stable iteration order.
  35  *
  36  * @param <K> key type
  37  * @param <V> value type
  38  */
  39 final class LazyBindingMapLookupState<K extends Key<V>, V extends DataObject & KeyAware<K>>
  40         extends LazyBindingMap.State<K, V> {
  41     private static final VarHandle VALUES;
  42
  43     static {
  44         try {
  45             VALUES = MethodHandles.lookup().findVarHandle(LazyBindingMapLookupState.class, "values", Values.class);
  46         } catch (NoSuchFieldException | IllegalAccessException e) {
  47             throw new ExceptionInInitializerError(e);
  48         }
  49     }
  50
  51     // Primary storage of transformed nodes
  52     private final ConcurrentHashMap<K, V> objects = new ConcurrentHashMap<>();
  53     private final LazyBindingMap<K, V> map;
  54
  55     // Used via the varhandle above
  56     @SuppressWarnings("unused")
  57     @SuppressFBWarnings(value = "UUF_UNUSED_FIELD", justification = "https://github.com/spotbugs/spotbugs/issues/2749")
  58     private volatile Values<K, V> values;
  59
  60     LazyBindingMapLookupState(final LazyBindingMap<K, V> map) {
  61         this.map = requireNonNull(map);
  62     }
  63
  64     @Override
  65     boolean containsKey(final Object key) {
  66         // If we have the value, that is always accurate. Otherwise we have to attempt to load from DOM data and see
  67         // what the result is.
  68         return objects.containsKey(key) || loadKey(key) != null;
  69     }
  70
  71     @Override
  72     V get(final Object key) {
  73         final V existing;
  74         // Perform a lookup first, otherwise try to load the key from DOM data
  75         return (existing = objects.get(key)) != null ? existing : loadKey(key);
  76     }
  77
  78     @Override
  79     KeySet<K, V> keySet() {
  80         return new KeySet<>(values());
  81     }
  82
  83     @Override
  84     Values<K, V> values() {
  85         final Values<K, V> ret;
  86         return (ret = (Values<K, V>) VALUES.getAcquire(this)) != null ? ret : loadValues();
  87     }
  88
  89     @Override
  90     EntrySet<K, V> entrySet() {
  91         return new EntrySet<>(values());
  92     }
  93
  94     private @Nullable V loadKey(final @NonNull Object key) {
  95         final Optional<V> opt = map.lookupValue(key);
  96         if (opt.isEmpty()) {
  97             return null;
  98         }
  99
 100         // Here is a conundrum: which key do we use?
 101         //
 102         // We have the lookup key readily available, which means faster insert at the expense of having duplicates once
 103         // the looked-up object is accessed. On the other hand we could use ret.key(), which forces population of key
 104         // properties and the key itself.
 105         //
 106         // Opt for the provided key, as it is likely the user will end up looking at other properties of the returned
 107         // object.
 108         //
 109         // This leaves the option for lookupValue() to use the key to initialize object's cache fields, so that we end
 110         // up reflecting the same key instance as well as reuse key's components as object values. The case for that
 111         // needs to be justified, though, as it ends up doing more work upfront unrelated to what the caller is about
 112         // to do.
 113         return putIfAbsent((K) key, opt.orElseThrow());
 114     }
 115
 116     private @NonNull V putIfAbsent(final @NonNull K key, final @NonNull V value) {
 117         final V existing = objects.putIfAbsent(key, value);
 118         return existing == null ? value : existing;
 119     }
 120
 121     @SuppressWarnings("unchecked")
 122     private @NonNull Values<K, V> loadValues() {
 123         final Values<K, V> ret = new Values<>(this);
 124         final Object witness;
 125         return (witness = VALUES.compareAndExchangeRelease(this, null, ret)) == null ? ret : (Values<K, V>) witness;
 126     }
 127
 128     private static final class EntrySet<K extends Key<V>, V extends DataObject & KeyAware<K>>
 129             extends AbstractSet<Entry<K, V>> implements Immutable {
 130         private final Values<K, V> values;
 131
 132         EntrySet(final Values<K, V> values) {
 133             this.values = requireNonNull(values);
 134         }
 135
 136         @Override
 137         public Iterator<Entry<K, V>> iterator() {
 138             return values.entryIterator();
 139         }
 140
 141         @Override
 142         public int size() {
 143             return values.size();
 144         }
 145
 146         @Override
 147         @SuppressWarnings("checkstyle:parameterName")
 148         public boolean contains(final Object o) {
 149             // Key/Value are related, asking whether we have a particular Entry is asking whether values contain that
 150             // the entry's value
 151             return values.contains(((Entry<?, ?>)o).getValue());
 152         }
 153
 154         @Override
 155         @SuppressWarnings("checkstyle:equalsHashCode")
 156         public boolean equals(final Object obj) {
 157             // Fast check due to us not wasting a field for this value
 158             return obj instanceof EntrySet && values == ((EntrySet<?, ?>) obj).values || super.equals(obj);
 159         }
 160     }
 161
 162     private static final class KeySet<K extends Key<V>, V extends DataObject & KeyAware<K>>
 163             extends AbstractSet<K> implements Immutable {
 164         private final Values<K, V> values;
 165
 166         KeySet(final Values<K, V> values) {
 167             this.values = requireNonNull(values);
 168         }
 169
 170         @Override
 171         public Iterator<K> iterator() {
 172             return values.keyIterator();
 173         }
 174
 175         @Override
 176         public int size() {
 177             return values.size();
 178         }
 179
 180         @Override
 181         @SuppressWarnings("checkstyle:parameterName")
 182         public boolean contains(final Object o) {
 183             return values.map().containsKey(o);
 184         }
 185
 186         @Override
 187         @SuppressWarnings("checkstyle:equalsHashCode")
 188         public boolean equals(final Object obj) {
 189             // Fast check due to us not wasting a field for this value
 190             return obj instanceof KeySet && values == ((KeySet<?, ?>) obj).values || super.equals(obj);
 191         }
 192     }
 193
 194     private static final class Values<K extends Key<V>, V extends DataObject & KeyAware<K>>
 195             extends AbstractSet<V> implements Immutable {
 196         private final LazyBindingMapLookupState<K, V> state;
 197
 198         // Temporary storage for translated objects. We first initialize this to DOM values, so that we know what
 199         // objects we need to visit. As we iterate through them, we pick the source from here, then run them through
 200         // decode, then reconcile with the lookup map and finally store them back here.
 201         //
 202         // Once at least one iterator has gone through the entire entire array, we throw it away, as at that point
 203         // the primary storage is guaranteed to have all the same objects. We then free this array and switch to using
 204         // views on top of primary storage instead.
 205         //
 206         // This has the side-effect of changing iteration order once one of the iterators has made a complete pass.
 207         // While it may be counter-intuitive, we opt for the added memory efficiency and squirm just right to say
 208         // this is okay for Immutable contract :)
 209         @SuppressFBWarnings(value = "VO_VOLATILE_REFERENCE_TO_ARRAY",
 210                 justification = "The ref should really be volatile. This class does not access elements directly.")
 211         private volatile Object[] objects;
 212
 213         Values(final LazyBindingMapLookupState<K, V> state) {
 214             this.state = requireNonNull(state);
 215             objects = map().mapNode().body().toArray();
 216         }
 217
 218         @Override
 219         public Iterator<V> iterator() {
 220             final Object[] local = objects;
 221             // When we have null objects it means we have everyone in state.objects
 222             return local == null ? Iterators.unmodifiableIterator(state.objects.values().iterator())
 223                     : new ValuesIter<>(this, local);
 224         }
 225
 226         @Override
 227         @SuppressWarnings("checkstyle:parameterName")
 228         public boolean contains(final Object o) {
 229             return map().containsValue(o);
 230         }
 231
 232         @Override
 233         public int size() {
 234             return map().size();
 235         }
 236
 237         Iterator<Entry<K, V>> entryIterator() {
 238             final Object[] local = objects;
 239             // When we have null objects it means we have everyone in state.objects
 240             return local == null ? Iterators.unmodifiableIterator(state.objects.entrySet().iterator())
 241                     : Iterators.transform(new ValuesIter<>(this, local), value -> Map.entry(value.key(), value));
 242         }
 243
 244         Iterator<K> keyIterator() {
 245             final Object[] local = objects;
 246             // When we have null objects it means we have everyone in state.objects
 247             return local == null ? Iterators.unmodifiableIterator(state.objects.keySet().iterator())
 248                     : Iterators.transform(new ValuesIter<>(this, local), KeyAware::key);
 249         }
 250
 251         LazyBindingMap<K, V> map() {
 252             return state.map;
 253         }
 254
 255         void fullyIterated() {
 256             // We have iterated over all objects. Clear them to indicate further access should go through state.objects
 257             objects = null;
 258         }
 259     }
 260
 261     private static final class ValuesIter<K extends Key<V>, V extends DataObject & KeyAware<K>>
 262             extends AbstractIterator<V> {
 263         private final Values<K, V> values;
 264         private final Object[] objects;
 265         private int nextOffset;
 266
 267         ValuesIter(final Values<K, V> values, final Object[] objects) {
 268             this.values = requireNonNull(values);
 269             this.objects = requireNonNull(objects);
 270         }
 271
 272         @Override
 273         protected V computeNext() {
 274             if (nextOffset < objects.length) {
 275                 return objectAt(nextOffset++);
 276             }
 277             values.fullyIterated();
 278             return endOfData();
 279         }
 280
 281         private @NonNull V objectAt(final int offset) {
 282             final Object obj = OBJ_AA.getAcquire(objects, offset);
 283             return obj instanceof MapEntryNode ? loadObjectAt(offset, (MapEntryNode) obj) : (V) obj;
 284         }
 285
 286         private @NonNull V loadObjectAt(final int offset, final MapEntryNode obj) {
 287             final LazyBindingMapLookupState<K, V> local = values.state;
 288             final V created = local.map.createValue(obj);
 289             final V ret = local.putIfAbsent(created.key(), created);
 290             final Object witness;
 291             return (witness = OBJ_AA.compareAndExchangeRelease(objects, offset, obj, ret)) == obj ? ret : (V) witness;
 292         }
 293     }
 294 }