binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapIterState.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.ImmutableMap;
  15 import com.google.common.collect.Iterators;
  16 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
  17 import java.lang.invoke.MethodHandles;
  18 import java.lang.invoke.MethodHandles.Lookup;
  19 import java.lang.invoke.VarHandle;
  20 import java.util.AbstractSet;
  21 import java.util.Iterator;
  22 import java.util.Map;
  23 import java.util.Map.Entry;
  24 import org.eclipse.jdt.annotation.NonNull;
  25 import org.opendaylight.yangtools.concepts.Immutable;
  26 import org.opendaylight.yangtools.yang.binding.DataObject;
  27 import org.opendaylight.yangtools.yang.binding.Key;
  28 import org.opendaylight.yangtools.yang.binding.KeyAware;
  29 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
  30 import org.slf4j.Logger;
  31 import org.slf4j.LoggerFactory;
  32
  33 /**
  34  * {@link LazyBindingMap.State} optimized for iterator access, mainly via {@link Map#values()}.
  35  *
  36  * @param <K> key type
  37  * @param <V> value type
  38  */
  39 final class LazyBindingMapIterState<K extends Key<V>, V extends DataObject & KeyAware<K>>
  40         extends LazyBindingMap.State<K, V> {
  41     private static final Logger LOG = LoggerFactory.getLogger(LazyBindingMapIterState.class);
  42     private static final VarHandle ENTRY_SET;
  43     private static final VarHandle KEY_SET;
  44     private static final VarHandle LOOKUP_MAP;
  45
  46     static {
  47         final Lookup lookup = MethodHandles.lookup();
  48         try {
  49             ENTRY_SET = lookup.findVarHandle(LazyBindingMapIterState.class, "entrySet", EntrySet.class);
  50             KEY_SET = lookup.findVarHandle(LazyBindingMapIterState.class, "keySet", KeySet.class);
  51             LOOKUP_MAP = lookup.findVarHandle(LazyBindingMapIterState.class, "lookupMap", ImmutableMap.class);
  52         } catch (NoSuchFieldException | IllegalAccessException e) {
  53             throw new ExceptionInInitializerError(e);
  54         }
  55     }
  56
  57     // Primary storage of transformed nodes. Other views are derived from this.
  58     private final @NonNull Values<K, V> values;
  59
  60     // Secondary views derived from values, used via varhandles above
  61     @SuppressWarnings("unused")
  62     @SuppressFBWarnings(value = "UUF_UNUSED_FIELD", justification = "https://github.com/spotbugs/spotbugs/issues/2749")
  63     private volatile KeySet<K, V> keySet;
  64     @SuppressWarnings("unused")
  65     @SuppressFBWarnings(value = "UUF_UNUSED_FIELD", justification = "https://github.com/spotbugs/spotbugs/issues/2749")
  66     private volatile EntrySet<K, V> entrySet;
  67
  68     // Lookup map, instantiated on demand, used via varhandle above
  69     @SuppressWarnings("unused")
  70     @SuppressFBWarnings(value = "URF_UNREAD_FIELD", justification = "https://github.com/spotbugs/spotbugs/issues/2749")
  71     private volatile ImmutableMap<K, V> lookupMap;
  72
  73     LazyBindingMapIterState(final LazyBindingMap<K, V> map) {
  74         values = new Values<>(map);
  75     }
  76
  77     @Override
  78     boolean containsKey(final Object key) {
  79         return lookupMap().containsKey(key);
  80     }
  81
  82     @Override
  83     V get(final Object key) {
  84         return lookupMap().get(key);
  85     }
  86
  87     @Override
  88     Values<K, V> values() {
  89         return values;
  90     }
  91
  92     @Override
  93     EntrySet<K, V> entrySet() {
  94         final EntrySet<K, V> ret;
  95         return (ret = (EntrySet<K, V>) ENTRY_SET.getAcquire(this)) != null ? ret : loadEntrySet();
  96     }
  97
  98     @Override
  99     KeySet<K, V> keySet() {
 100         final KeySet<K, V> ret;
 101         return (ret = (KeySet<K, V>) KEY_SET.getAcquire(this)) != null ? ret : loadKeySet();
 102     }
 103
 104     private @NonNull ImmutableMap<K, V> lookupMap() {
 105         final ImmutableMap<K, V> ret;
 106         return (ret = (ImmutableMap<K, V>) LOOKUP_MAP.getAcquire(this)) != null ? ret : loadLookupMap();
 107     }
 108
 109     // TODO: this is not exactly efficient, as we are forcing full materialization. We also take a lock here, as we
 110     //       do not want multiple threads indexing the same thing. Perhaps this should work with the LookupState
 111     //       somehow, so that we have a shared object view and two indices?
 112     private synchronized @NonNull ImmutableMap<K, V> loadLookupMap() {
 113         ImmutableMap<K, V> ret = (ImmutableMap<K, V>) LOOKUP_MAP.getAcquire(this);
 114         if (ret == null) {
 115             lookupMap = ret = ImmutableMap.copyOf(entrySet());
 116             if (LOG.isTraceEnabled()) {
 117                 LOG.trace("Inefficient instantiation of lookup secondary", new Throwable());
 118             }
 119         }
 120         return ret;
 121     }
 122
 123     @SuppressWarnings("unchecked")
 124     private @NonNull EntrySet<K, V> loadEntrySet() {
 125         final EntrySet<K, V> ret = new EntrySet<>(values);
 126         final Object witness;
 127         return (witness = ENTRY_SET.compareAndExchangeRelease(this, null, ret)) == null ? ret
 128                 : (EntrySet<K, V>) witness;
 129     }
 130
 131     @SuppressWarnings("unchecked")
 132     private @NonNull KeySet<K, V> loadKeySet() {
 133         final KeySet<K, V> ret = new KeySet<>(values);
 134         final Object witness;
 135         return (witness = KEY_SET.compareAndExchangeRelease(this, null, ret)) == null ? ret : (KeySet<K, V>) witness;
 136     }
 137
 138     private static final class EntrySet<K extends Key<V>, V extends DataObject & KeyAware<K>>
 139             extends AbstractSet<Entry<K, V>> implements Immutable {
 140         private final Values<K, V> values;
 141
 142         EntrySet(final Values<K, V> values) {
 143             this.values = requireNonNull(values);
 144         }
 145
 146         @Override
 147         public int size() {
 148             return values.size();
 149         }
 150
 151         @Override
 152         public Iterator<Entry<K, V>> iterator() {
 153             return Iterators.transform(values.iterator(), value -> Map.entry(value.key(), value));
 154         }
 155
 156         @Override
 157         @SuppressWarnings("checkstyle:parameterName")
 158         public boolean contains(final Object o) {
 159             // Key/Value are related, asking whether we have a particular Entry is asking whether values contain that
 160             // the entry's value
 161             return values.contains(((Entry<?, ?>)o).getValue());
 162         }
 163     }
 164
 165     private static final class KeySet<K extends Key<V>, V extends DataObject & KeyAware<K>>
 166             extends AbstractSet<K> implements Immutable {
 167         private final Values<K, V> values;
 168
 169         KeySet(final Values<K, V> values) {
 170             this.values = requireNonNull(values);
 171         }
 172
 173         @Override
 174         public int size() {
 175             return values.size();
 176         }
 177
 178         @Override
 179         public Iterator<K> iterator() {
 180             return Iterators.transform(values.iterator(), KeyAware::key);
 181         }
 182
 183         @Override
 184         @SuppressWarnings("checkstyle:parameterName")
 185         public boolean contains(final Object o) {
 186             return values.map.containsKey(o);
 187         }
 188     }
 189
 190     /*
 191      * Lazily-populated translation of DOM values to binding values. This class is not completely lazy, as we allocate
 192      * the array to hold all values upfront and populate it with MapEntry nodes. That allows us to perform lock-free
 193      * access, as we just end up CASing MapEntryNodes with their Binding replacements.
 194      */
 195     private static final class Values<K extends Key<V>, V extends DataObject & KeyAware<K>>
 196             extends AbstractSet<V> implements Immutable {
 197         private final LazyBindingMap<K, V> map;
 198         private final Object[] objects;
 199
 200         Values(final LazyBindingMap<K, V> map) {
 201             this.map = requireNonNull(map);
 202             objects = map.mapNode().body().toArray();
 203         }
 204
 205         @Override
 206         public Iterator<V> iterator() {
 207             return new AbstractIterator<>() {
 208                 private int nextOffset;
 209
 210                 @Override
 211                 protected V computeNext() {
 212                     return nextOffset < objects.length ? objectAt(nextOffset++) : endOfData();
 213                 }
 214             };
 215         }
 216
 217         @Override
 218         @SuppressWarnings("checkstyle:parameterName")
 219         public boolean contains(final Object o) {
 220             return map.containsValue(o);
 221         }
 222
 223         @Override
 224         public int size() {
 225             return map.size();
 226         }
 227
 228         @NonNull V objectAt(final int offset) {
 229             final Object obj = OBJ_AA.getAcquire(objects, offset);
 230             return obj instanceof MapEntryNode ? loadObjectAt(offset, (MapEntryNode) obj) : (V) obj;
 231         }
 232
 233         private @NonNull V loadObjectAt(final int offset, final MapEntryNode obj) {
 234             final V ret = map.createValue(obj);
 235             final Object witness;
 236             return (witness = OBJ_AA.compareAndExchangeRelease(objects, offset, obj, ret)) == obj ? ret : (V) witness;
 237         }
 238     }
 239 }