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