@Override
public void startMapEntryNode(final Identifier<?> key, final int childSizeHint) throws IOException {
duplicateSchemaEnter();
- NodeIdentifierWithPredicates identifier = ((KeyedListNodeCodecContext<?>) current()).serialize(key);
+ NodeIdentifierWithPredicates identifier = ((KeyedListNodeCodecContext<?, ?>) current()).serialize(key);
delegate.startMapEntryNode(identifier, childSizeHint);
}
private @NonNull Object loadKey(final VarHandle handle) {
verify(data instanceof MapEntryNode, "Unsupported value %s", data);
verify(context instanceof KeyedListNodeCodecContext, "Unexpected context %s", context);
- final Object obj = ((KeyedListNodeCodecContext<?>) context).deserialize(((MapEntryNode) data).getIdentifier());
+ final Object obj = ((KeyedListNodeCodecContext<?, ?>) context)
+ .deserialize(((MapEntryNode) data).getIdentifier());
// key is known to be non-null, no need to mask it
final Object witness = handle.compareAndExchangeRelease(this, null, obj);
return witness == null ? obj : witness;
import static java.util.Objects.requireNonNull;
import static org.opendaylight.mdsal.binding.spec.naming.BindingMapping.IDENTIFIABLE_KEY_NAME;
-import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableMap.Builder;
import java.lang.reflect.Method;
import java.util.List;
import java.util.Map;
import org.opendaylight.yangtools.yang.binding.InstanceIdentifier.IdentifiableItem;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifierWithPredicates;
-import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
import org.opendaylight.yangtools.yang.data.api.schema.MapNode;
import org.opendaylight.yangtools.yang.model.api.ListSchemaNode;
-abstract class KeyedListNodeCodecContext<D extends DataObject & Identifiable<?>> extends ListNodeCodecContext<D> {
- private static final class Ordered<D extends DataObject & Identifiable<?>> extends KeyedListNodeCodecContext<D> {
+abstract class KeyedListNodeCodecContext<I extends Identifier<D>, D extends DataObject & Identifiable<I>>
+ extends ListNodeCodecContext<D> {
+ private static final class Ordered<I extends Identifier<D>, D extends DataObject & Identifiable<I>>
+ extends KeyedListNodeCodecContext<I, D> {
Ordered(final DataContainerCodecPrototype<ListSchemaNode> prototype, final Method keyMethod,
final IdentifiableItemCodec codec) {
super(prototype, keyMethod, codec);
}
}
- private static final class Unordered<D extends DataObject & Identifiable<?>> extends KeyedListNodeCodecContext<D> {
+ static final class Unordered<I extends Identifier<D>, D extends DataObject & Identifiable<I>>
+ extends KeyedListNodeCodecContext<I, D> {
Unordered(final DataContainerCodecPrototype<ListSchemaNode> prototype, final Method keyMethod,
final IdentifiableItemCodec codec) {
super(prototype, keyMethod, codec);
}
@Override
- Map<?, D> fromMap(final MapNode map, final int size) {
- // FIXME: MDSAL-539: Make this a lazily-populated map
- final Builder<Object, D> builder = ImmutableMap.builderWithExpectedSize(size);
- for (MapEntryNode node : map.getValue()) {
- final D entry = createBindingProxy(node);
- builder.put(entry.key(), entry);
- }
- return builder.build();
+ Map<I, D> fromMap(final MapNode map, final int size) {
+ return LazyBindingMap.create(this, map, size);
}
}
* @param <E> the type of elements in this list
*/
final class LazyBindingList<E extends DataObject> extends AbstractList<E> implements Immutable, RandomAccess {
- private static final VarHandle OBJ_AA = MethodHandles.arrayElementVarHandle(Object[].class);
+ // Object array access variable handle
+ static final VarHandle OBJ_AA = MethodHandles.arrayElementVarHandle(Object[].class);
+
private static final Logger LOG = LoggerFactory.getLogger(LazyBindingList.class);
private static final String LAZY_CUTOFF_PROPERTY =
"org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingList.max-eager-elements";
--- /dev/null
+/*
+ * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.mdsal.binding.dom.codec.impl;
+
+import static java.util.Objects.requireNonNull;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableMap.Builder;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.VarHandle;
+import java.util.AbstractMap;
+import java.util.Collection;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
+import org.eclipse.jdt.annotation.NonNull;
+import org.opendaylight.mdsal.binding.dom.codec.impl.KeyedListNodeCodecContext.Unordered;
+import org.opendaylight.yangtools.concepts.Immutable;
+import org.opendaylight.yangtools.yang.binding.DataObject;
+import org.opendaylight.yangtools.yang.binding.Identifiable;
+import org.opendaylight.yangtools.yang.binding.Identifier;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifierWithPredicates;
+import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
+import org.opendaylight.yangtools.yang.data.api.schema.MapNode;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Lazily-populated Map of binding DTOs. This implementation acts as the main entry point, so that we can decide on the
+ * translation strategy we are going to use. We make that decision based on the first method that touches the mappings
+ * (or materializes a view).
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+final class LazyBindingMap<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends AbstractMap<K, V> implements Immutable {
+ private static final Logger LOG = LoggerFactory.getLogger(LazyBindingMap.class);
+ private static final String LAZY_CUTOFF_PROPERTY =
+ "org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingMap.max-eager-elements";
+ private static final int DEFAULT_LAZY_CUTOFF = 1;
+ @VisibleForTesting
+ static final int LAZY_CUTOFF;
+
+ private static final VarHandle STATE;
+
+ static {
+ try {
+ STATE = MethodHandles.lookup().findVarHandle(LazyBindingMap.class, "state",
+ State.class);
+ } catch (NoSuchFieldException | IllegalAccessException e) {
+ throw new ExceptionInInitializerError(e);
+ }
+
+ final int value = Integer.getInteger(LAZY_CUTOFF_PROPERTY, DEFAULT_LAZY_CUTOFF);
+ if (value < 0) {
+ LOG.info("Lazy population of maps disabled");
+ LAZY_CUTOFF = Integer.MAX_VALUE;
+ } else {
+ LOG.info("Using lazy population for maps larger than {} element(s)", value);
+ LAZY_CUTOFF = value;
+ }
+ }
+
+ private final @NonNull Unordered<K, V> codec;
+ private final @NonNull MapNode mapNode;
+
+ // Used via VarHandle above
+ @SuppressWarnings("unused")
+ private volatile State<K, V> state;
+
+ private LazyBindingMap(final Unordered<K, V> codec, final MapNode mapNode) {
+ this.codec = requireNonNull(codec);
+ this.mapNode = requireNonNull(mapNode);
+ }
+
+ static <K extends Identifier<V>, V extends DataObject & Identifiable<K>> @NonNull Map<K, V> create(
+ final Unordered<K, V> codec, final MapNode mapNode, final int size) {
+ if (size == 1) {
+ // Do not bother with lazy instantiation in case of a singleton
+ final V entry = codec.createBindingProxy(mapNode.getValue().iterator().next());
+ return Map.of(entry.key(), entry);
+ }
+ return size > LAZY_CUTOFF ? new LazyBindingMap<>(codec, mapNode) : eagerMap(codec, mapNode, size);
+ }
+
+ private static <K extends Identifier<V>, V extends DataObject & Identifiable<K>> @NonNull Map<K, V> eagerMap(
+ final Unordered<K, V> codec, final MapNode mapNode, final int size) {
+ final Builder<K, V> builder = ImmutableMap.builderWithExpectedSize(size);
+ for (MapEntryNode node : mapNode.getValue()) {
+ final V entry = codec.createBindingProxy(node);
+ builder.put(entry.key(), entry);
+ }
+ return builder.build();
+ }
+
+ @Override
+ public int size() {
+ return mapNode.size();
+ }
+
+ @Override
+ public V remove(final Object key) {
+ throw uoe();
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:parameterName")
+ public void putAll(final Map<? extends K, ? extends V> m) {
+ throw uoe();
+ }
+
+ @Override
+ public void clear() {
+ throw uoe();
+ }
+
+ @Override
+ public boolean containsKey(final Object key) {
+ return lookupState().containsKey(requireNonNull(key));
+ }
+
+ @Override
+ public boolean containsValue(final Object value) {
+ /*
+ * This implementation relies on the relationship specified by Identifiable/Identifier and its use in binding
+ * objects. The key is a wrapper object composed of a subset (or all) properties in the value, i.e. we have
+ * a partial index.
+ *
+ * Instead of performing an O(N) search, we extract the key from the value, look the for the corresponding
+ * mapping. If we find a mapping we check if the mapped value equals the the value being looked up.
+ *
+ * Note we prefer throwing ClassCastException/NullPointerException when presented with null or an object which
+ * cannot possibly be contained in this map.
+ */
+ final V cast = codec.getBindingClass().cast(requireNonNull(value));
+ final V found = get(cast.key());
+ return found != null && cast.equals(found);
+ }
+
+ @Override
+ public V get(final Object key) {
+ return lookupState().get(requireNonNull(key));
+ }
+
+ @Override
+ public Set<K> keySet() {
+ return iterState().keySet();
+ }
+
+ @Override
+ public Collection<V> values() {
+ return iterState().values();
+ }
+
+ @Override
+ public Set<Entry<K, V>> entrySet() {
+ return iterState().entrySet();
+ }
+
+ @NonNull V createValue(final MapEntryNode node) {
+ return codec.createBindingProxy(node);
+ }
+
+ Optional<V> lookupValue(final @NonNull Object key) {
+ final NodeIdentifierWithPredicates childId = codec.serialize((Identifier<?>) key);
+ return mapNode.getChild(childId).map(codec::createBindingProxy);
+ }
+
+ @NonNull MapNode mapNode() {
+ return mapNode;
+ }
+
+ private @NonNull State<K, V> lookupState() {
+ final State<K, V> local;
+ return (local = (State<K, V>) STATE.getAcquire(this)) != null ? local : loadLookup();
+ }
+
+ private @NonNull State<K, V> iterState() {
+ final State<K, V> local;
+ return (local = (State<K, V>) STATE.getAcquire(this)) != null ? local : loadIter();
+ }
+
+ @SuppressWarnings("unchecked")
+ private @NonNull State<K, V> loadLookup() {
+ final State<K, V> ret = new LazyBindingMapLookupState<>(this);
+ final Object witness;
+ return (witness = STATE.compareAndExchangeRelease(this, null, ret)) == null ? ret : (State<K, V>) witness;
+ }
+
+ @SuppressWarnings("unchecked")
+ private @NonNull State<K, V> loadIter() {
+ final State<K, V> ret = new LazyBindingMapIterState<>(this);
+ final Object witness;
+ return (witness = STATE.compareAndExchangeRelease(this, null, ret)) == null ? ret : (State<K, V>) witness;
+ }
+
+ private static UnsupportedOperationException uoe() {
+ return new UnsupportedOperationException("Modification is not supported");
+ }
+
+ abstract static class State<K extends Identifier<V>, V extends DataObject & Identifiable<K>> {
+ abstract boolean containsKey(@NonNull Object key);
+
+ abstract V get(@NonNull Object key);
+
+ abstract @NonNull Set<K> keySet();
+
+ abstract @NonNull Collection<V> values();
+
+ abstract @NonNull Set<Entry<K, V>> entrySet();
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.mdsal.binding.dom.codec.impl;
+
+import static java.util.Objects.requireNonNull;
+import static org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingList.OBJ_AA;
+
+import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Iterators;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.MethodHandles.Lookup;
+import java.lang.invoke.VarHandle;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Map.Entry;
+import org.eclipse.jdt.annotation.NonNull;
+import org.opendaylight.yangtools.concepts.Immutable;
+import org.opendaylight.yangtools.yang.binding.DataObject;
+import org.opendaylight.yangtools.yang.binding.Identifiable;
+import org.opendaylight.yangtools.yang.binding.Identifier;
+import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * {@link LazyBindingMap.State} optimized for iterator access, mainly via {@link Map#values()}.
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+final class LazyBindingMapIterState<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends LazyBindingMap.State<K, V> {
+ private static final Logger LOG = LoggerFactory.getLogger(LazyBindingMapIterState.class);
+ private static final VarHandle ENTRY_SET;
+ private static final VarHandle KEY_SET;
+ private static final VarHandle LOOKUP_MAP;
+
+ static {
+ final Lookup lookup = MethodHandles.lookup();
+ try {
+ ENTRY_SET = lookup.findVarHandle(LazyBindingMapIterState.class, "entrySet", EntrySet.class);
+ KEY_SET = lookup.findVarHandle(LazyBindingMapIterState.class, "keySet", KeySet.class);
+ LOOKUP_MAP = lookup.findVarHandle(LazyBindingMapIterState.class, "lookupMap", ImmutableMap.class);
+ } catch (NoSuchFieldException | IllegalAccessException e) {
+ throw new ExceptionInInitializerError(e);
+ }
+ }
+
+ // Primary storage of transformed nodes. Other views are derived from this.
+ private final @NonNull Values<K, V> values;
+
+ // Secondary views derived from values, used via varhandles above
+ @SuppressWarnings("unused")
+ private volatile KeySet<K, V> keySet;
+ @SuppressWarnings("unused")
+ private volatile EntrySet<K, V> entrySet;
+
+ // Lookup map, instantiated on demand, used via varhandle above
+ @SuppressWarnings("unused")
+ private volatile ImmutableMap<K, V> lookupMap;
+
+ LazyBindingMapIterState(final LazyBindingMap<K, V> map) {
+ values = new Values<>(map);
+ }
+
+ @Override
+ boolean containsKey(final Object key) {
+ return lookupMap().containsKey(key);
+ }
+
+ @Override
+ V get(final Object key) {
+ return lookupMap().get(key);
+ }
+
+ @Override
+ Values<K, V> values() {
+ return values;
+ }
+
+ @Override
+ EntrySet<K, V> entrySet() {
+ final EntrySet<K, V> ret;
+ return (ret = (EntrySet<K, V>) ENTRY_SET.getAcquire(this)) != null ? ret : loadEntrySet();
+ }
+
+ @Override
+ KeySet<K, V> keySet() {
+ final KeySet<K, V> ret;
+ return (ret = (KeySet<K, V>) KEY_SET.getAcquire(this)) != null ? ret : loadKeySet();
+ }
+
+ private @NonNull ImmutableMap<K, V> lookupMap() {
+ final ImmutableMap<K, V> ret;
+ return (ret = (ImmutableMap<K, V>) LOOKUP_MAP.getAcquire(this)) != null ? ret : loadLookupMap();
+ }
+
+ // TODO: this is not exactly efficient, as we are forcing full materialization. We also take a lock here, as we
+ // do not want multiple threads indexing the same thing. Perhaps this should work with the LookupState
+ // somehow, so that we have a shared object view and two indices?
+ private synchronized @NonNull ImmutableMap<K, V> loadLookupMap() {
+ ImmutableMap<K, V> ret = (ImmutableMap<K, V>) LOOKUP_MAP.getAcquire(this);
+ if (ret == null) {
+ lookupMap = ret = ImmutableMap.copyOf(entrySet());
+ if (LOG.isTraceEnabled()) {
+ LOG.trace("Inefficient instantiation of lookup secondary", new Throwable());
+ }
+ }
+ return ret;
+ }
+
+ @SuppressWarnings("unchecked")
+ private @NonNull EntrySet<K, V> loadEntrySet() {
+ final EntrySet<K, V> ret = new EntrySet<>(values);
+ final Object witness;
+ return (witness = ENTRY_SET.compareAndExchangeRelease(this, null, ret)) == null ? ret
+ : (EntrySet<K, V>) witness;
+ }
+
+ @SuppressWarnings("unchecked")
+ private @NonNull KeySet<K, V> loadKeySet() {
+ final KeySet<K, V> ret = new KeySet<>(values);
+ final Object witness;
+ return (witness = KEY_SET.compareAndExchangeRelease(this, null, ret)) == null ? ret : (KeySet<K, V>) witness;
+ }
+
+ private static final class EntrySet<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends AbstractSet<Entry<K, V>> implements Immutable {
+ private final Values<K, V> values;
+
+ EntrySet(final Values<K, V> values) {
+ this.values = requireNonNull(values);
+ }
+
+ @Override
+ public int size() {
+ return values.size();
+ }
+
+ @Override
+ public Iterator<Entry<K, V>> iterator() {
+ return Iterators.transform(values.iterator(), value -> Map.entry(value.key(), value));
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:parameterName")
+ public boolean contains(final Object o) {
+ // Key/Value are related, asking whether we have a particular Entry is asking whether values contain that
+ // the entry's value
+ return values.contains(((Entry<?, ?>)o).getValue());
+ }
+ }
+
+ private static final class KeySet<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends AbstractSet<K> implements Immutable {
+ private final Values<K, V> values;
+
+ KeySet(final Values<K, V> values) {
+ this.values = requireNonNull(values);
+ }
+
+ @Override
+ public int size() {
+ return values.size();
+ }
+
+ @Override
+ public Iterator<K> iterator() {
+ return Iterators.transform(values.iterator(), value -> value.key());
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:parameterName")
+ public boolean contains(final Object o) {
+ return values.map.containsKey(o);
+ }
+ }
+
+ /*
+ * Lazily-populated translation of DOM values to binding values. This class is not completely lazy, as we allocate
+ * the array to hold all values upfront and populate it with MapEntry nodes. That allows us to perform lock-free
+ * access, as we just end up CASing MapEntryNodes with their Binding replacements.
+ */
+ private static final class Values<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends AbstractSet<V> implements Immutable {
+ private final LazyBindingMap<K, V> map;
+ private final Object[] objects;
+
+ Values(final LazyBindingMap<K, V> map) {
+ this.map = requireNonNull(map);
+ objects = map.mapNode().getValue().toArray();
+ }
+
+ @Override
+ public Iterator<V> iterator() {
+ return new AbstractIterator<>() {
+ private int nextOffset;
+
+ @Override
+ protected V computeNext() {
+ return nextOffset < objects.length ? objectAt(nextOffset++) : endOfData();
+ }
+ };
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:parameterName")
+ public boolean contains(final Object o) {
+ return map.containsValue(o);
+ }
+
+ @Override
+ public int size() {
+ return map.size();
+ }
+
+ @NonNull V objectAt(final int offset) {
+ final Object obj = OBJ_AA.getAcquire(objects, offset);
+ return obj instanceof MapEntryNode ? loadObjectAt(offset, (MapEntryNode) obj) : (V) obj;
+ }
+
+ private @NonNull V loadObjectAt(final int offset, final MapEntryNode obj) {
+ final V ret = map.createValue(obj);
+ final Object witness;
+ return (witness = OBJ_AA.compareAndExchangeRelease(objects, offset, obj, ret)) == obj ? ret : (V) witness;
+ }
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.mdsal.binding.dom.codec.impl;
+
+import static java.util.Objects.requireNonNull;
+import static org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingList.OBJ_AA;
+
+import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.Iterators;
+import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.VarHandle;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Optional;
+import java.util.concurrent.ConcurrentHashMap;
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.opendaylight.yangtools.concepts.Immutable;
+import org.opendaylight.yangtools.yang.binding.DataObject;
+import org.opendaylight.yangtools.yang.binding.Identifiable;
+import org.opendaylight.yangtools.yang.binding.Identifier;
+import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
+
+/**
+ * {@link LazyBindingMap.State} optimized for lookup access, mainly via {@link Map#values()}. Note that this
+ * implementation, while being effectively immutable, does not guarantee stable iteration order.
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+final class LazyBindingMapLookupState<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends LazyBindingMap.State<K, V> {
+ private static final VarHandle VALUES;
+
+ static {
+ try {
+ VALUES = MethodHandles.lookup().findVarHandle(LazyBindingMapLookupState.class, "values", Values.class);
+ } catch (NoSuchFieldException | IllegalAccessException e) {
+ throw new ExceptionInInitializerError(e);
+ }
+ }
+
+ // Primary storage of transformed nodes
+ private final ConcurrentHashMap<K, V> objects = new ConcurrentHashMap<>();
+ private final LazyBindingMap<K, V> map;
+
+ // Used via the varhandle above
+ @SuppressWarnings("unused")
+ private volatile Values<K, V> values;
+
+ LazyBindingMapLookupState(final LazyBindingMap<K, V> map) {
+ this.map = requireNonNull(map);
+ }
+
+ @Override
+ boolean containsKey(final Object key) {
+ // If we have the value, that is always accurate. Otherwise we have to attempt to load from DOM data and see
+ // what the result is.
+ return objects.containsKey(key) || loadKey(key) != null;
+ }
+
+ @Override
+ V get(final Object key) {
+ final V existing;
+ // Perform a lookup first, otherwise try to load the key from DOM data
+ return (existing = objects.get(key)) != null ? existing : loadKey(key);
+ }
+
+ @Override
+ KeySet<K, V> keySet() {
+ return new KeySet<>(values());
+ }
+
+ @Override
+ Values<K, V> values() {
+ final Values<K, V> ret;
+ return (ret = (Values<K, V>) VALUES.getAcquire(this)) != null ? ret : loadValues();
+ }
+
+ @Override
+ EntrySet<K, V> entrySet() {
+ return new EntrySet<>(values());
+ }
+
+ private @Nullable V loadKey(final @NonNull Object key) {
+ final Optional<V> opt = map.lookupValue(key);
+ if (opt.isEmpty()) {
+ return null;
+ }
+
+ // Here is a conundrum: which key do we use?
+ //
+ // We have the lookup key readily available, which means faster insert at the expense of having duplicates once
+ // the looked-up object is accessed. On the other hand we could use ret.key(), which forces population of key
+ // properties and the key itself.
+ //
+ // Opt for the provided key, as it is likely the user will end up looking at other properties of the returned
+ // object.
+ //
+ // This leaves the option for lookupValue() to use the key to initialize object's cache fields, so that we end
+ // up reflecting the same key instance as well as reuse key's components as object values. The case for that
+ // needs to be justified, though, as it ends up doing more work upfront unrelated to what the caller is about
+ // to do.
+ return putIfAbsent((K) key, opt.orElseThrow());
+ }
+
+ private @NonNull V putIfAbsent(final @NonNull K key, final @NonNull V value) {
+ final V existing = objects.putIfAbsent(key, value);
+ return existing == null ? value : existing;
+ }
+
+ @SuppressWarnings("unchecked")
+ private @NonNull Values<K, V> loadValues() {
+ final Values<K, V> ret = new Values<>(this);
+ final Object witness;
+ return (witness = VALUES.compareAndExchangeRelease(this, null, ret)) == null ? ret : (Values<K, V>) witness;
+ }
+
+ private static final class EntrySet<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends AbstractSet<Entry<K, V>> implements Immutable {
+ private final Values<K, V> values;
+
+ EntrySet(final Values<K, V> values) {
+ this.values = requireNonNull(values);
+ }
+
+ @Override
+ public Iterator<Entry<K, V>> iterator() {
+ return values.entryIterator();
+ }
+
+ @Override
+ public int size() {
+ return values.size();
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:parameterName")
+ public boolean contains(final Object o) {
+ // Key/Value are related, asking whether we have a particular Entry is asking whether values contain that
+ // the entry's value
+ return values.contains(((Entry<?, ?>)o).getValue());
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:equalsHashCode")
+ public boolean equals(final Object obj) {
+ // Fast check due to us not wasting a field for this value
+ return obj instanceof EntrySet && values == ((EntrySet<?, ?>) obj).values || super.equals(obj);
+ }
+ }
+
+ private static final class KeySet<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends AbstractSet<K> implements Immutable {
+ private final Values<K, V> values;
+
+ KeySet(final Values<K, V> values) {
+ this.values = requireNonNull(values);
+ }
+
+ @Override
+ public Iterator<K> iterator() {
+ return values.keyIterator();
+ }
+
+ @Override
+ public int size() {
+ return values.size();
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:parameterName")
+ public boolean contains(final Object o) {
+ return values.map().containsKey(o);
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:equalsHashCode")
+ public boolean equals(final Object obj) {
+ // Fast check due to us not wasting a field for this value
+ return obj instanceof KeySet && values == ((KeySet<?, ?>) obj).values || super.equals(obj);
+ }
+ }
+
+ private static final class Values<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends AbstractSet<V> implements Immutable {
+ private final LazyBindingMapLookupState<K, V> state;
+
+ // Temporary storage for translated objects. We first initialize this to DOM values, so that we know what
+ // objects we need to visit. As we iterate through them, we pick the source from here, then run them through
+ // decode, then reconcile with the lookup map and finally store them back here.
+ //
+ // Once at least one iterator has gone through the entire entire array, we throw it away, as at that point
+ // the primary storage is guaranteed to have all the same objects. We then free this array and switch to using
+ // views on top of primary storage instead.
+ //
+ // This has the side-effect of changing iteration order once one of the iterators has made a complete pass.
+ // While it may be counter-intuitive, we opt for the added memory efficiency and squirm just right to say
+ // this is okay for Immutable contract :)
+ @SuppressFBWarnings(value = "VO_VOLATILE_REFERENCE_TO_ARRAY",
+ justification = "The ref should really be volatile. This class does not access elements directly.")
+ private volatile Object[] objects;
+
+ Values(final LazyBindingMapLookupState<K, V> state) {
+ this.state = requireNonNull(state);
+ objects = map().mapNode().getValue().toArray();
+ }
+
+ @Override
+ public Iterator<V> iterator() {
+ final Object[] local = objects;
+ // When we have null objects it means we have everyone in state.objects
+ return local == null ? Iterators.unmodifiableIterator(state.objects.values().iterator())
+ : new ValuesIter<>(this, local);
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:parameterName")
+ public boolean contains(final Object o) {
+ return map().containsValue(o);
+ }
+
+ @Override
+ public int size() {
+ return map().size();
+ }
+
+ Iterator<Entry<K, V>> entryIterator() {
+ final Object[] local = objects;
+ // When we have null objects it means we have everyone in state.objects
+ return local == null ? Iterators.unmodifiableIterator(state.objects.entrySet().iterator())
+ : Iterators.transform(new ValuesIter<>(this, local), value -> Map.entry(value.key(), value));
+ }
+
+ Iterator<K> keyIterator() {
+ final Object[] local = objects;
+ // When we have null objects it means we have everyone in state.objects
+ return local == null ? Iterators.unmodifiableIterator(state.objects.keySet().iterator())
+ : Iterators.transform(new ValuesIter<>(this, local), value -> value.key());
+ }
+
+ LazyBindingMap<K, V> map() {
+ return state.map;
+ }
+
+ void fullyIterated() {
+ // We have iterated over all objects. Clear them to indicate further access should go through state.objects
+ objects = null;
+ }
+ }
+
+ private static final class ValuesIter<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
+ extends AbstractIterator<V> {
+ private final Values<K, V> values;
+ private final Object[] objects;
+ private int nextOffset;
+
+ ValuesIter(final Values<K, V> values, final Object[] objects) {
+ this.values = requireNonNull(values);
+ this.objects = requireNonNull(objects);
+ }
+
+ @Override
+ protected V computeNext() {
+ if (nextOffset < objects.length) {
+ return objectAt(nextOffset++);
+ }
+ values.fullyIterated();
+ return endOfData();
+ }
+
+ private @NonNull V objectAt(final int offset) {
+ final Object obj = OBJ_AA.getAcquire(objects, offset);
+ return obj instanceof MapEntryNode ? loadObjectAt(offset, (MapEntryNode) obj) : (V) obj;
+ }
+
+ private @NonNull V loadObjectAt(final int offset, final MapEntryNode obj) {
+ final LazyBindingMapLookupState<K, V> local = values.state;
+ final V created = local.map.createValue(obj);
+ final V ret = local.putIfAbsent(created.key(), created);
+ final Object witness;
+ return (witness = OBJ_AA.compareAndExchangeRelease(objects, offset, obj, ret)) == obj ? ret : (V) witness;
+ }
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.mdsal.binding.dom.codec.impl;
+
+import static org.hamcrest.CoreMatchers.instanceOf;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertThrows;
+import static org.junit.Assert.assertTrue;
+import static org.mockito.Mockito.mock;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.Top;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.TopBuilder;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.two.level.list.TopLevelList;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.two.level.list.TopLevelListBuilder;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.two.level.list.TopLevelListKey;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.two.level.list.top.level.list.NestedListBuilder;
+import org.opendaylight.yangtools.yang.binding.DataObject;
+import org.opendaylight.yangtools.yang.binding.Identifiable;
+import org.opendaylight.yangtools.yang.binding.InstanceIdentifier;
+
+public class LazyBindingMapTest extends AbstractBindingCodecTest {
+ private static Top TOP;
+
+ @BeforeClass
+ public static void prepareTop() {
+ final Map<TopLevelListKey, TopLevelList> map = new HashMap<>();
+ for (int i = 0; i < 2 * LazyBindingMap.LAZY_CUTOFF; i++) {
+ final TopLevelList item = new TopLevelListBuilder().setName(String.valueOf(i)).build();
+ map.put(item.key(), item);
+ }
+
+ TOP = new TopBuilder().setTopLevelList(map).build();
+ }
+
+ @Test
+ public void testSimpleEquals() {
+ final Top actual = prepareData();
+ assertThat(actual.getTopLevelList(), instanceOf(LazyBindingMap.class));
+ // AbstractMap.equals() goes through its entrySet and performs lookup for each key, hence it is excercising
+ // primarily LookupState
+ assertEquals(TOP, actual);
+ }
+
+ @Test
+ public void testEqualEntrySet() {
+ final Top actual = prepareData();
+ // Check equality based on entry set. This primarily exercises IterState
+ assertEquals(TOP.getTopLevelList().entrySet(), actual.getTopLevelList().entrySet());
+ }
+
+ @Test
+ public void testEqualKeySet() {
+ final Top actual = prepareData();
+ // Check equality based on key set. This primarily exercises IterState
+ assertEquals(TOP.getTopLevelList().keySet(), actual.getTopLevelList().keySet());
+ }
+
+ @Test
+ public void testIterKeySetLookup() {
+ final Top actual = prepareData();
+ // Forces IterState but then switches to key lookups
+ assertTrue(actual.getTopLevelList().keySet().containsAll(TOP.getTopLevelList().keySet()));
+ }
+
+ @Test
+ public void testIterEntrySetLookup() {
+ final Top actual = prepareData();
+ // Forces IterState but then switches to value lookups
+ assertTrue(actual.getTopLevelList().entrySet().containsAll(TOP.getTopLevelList().entrySet()));
+ }
+
+ @Test
+ public void testIterValueIteration() {
+ assertSameIteratorObjects(prepareData().getTopLevelList().values());
+ }
+
+ @Test
+ public void testLookupValueIteration() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ // Force lookup state instantiation
+ assertFalse(list.containsKey(new TopLevelListKey("blah")));
+
+ assertSameIteratorObjects(list.values());
+ }
+
+ @Test
+ public void testIterKeysetIteration() {
+ assertSameIteratorObjects(prepareData().getTopLevelList().keySet());
+ }
+
+ @Test
+ public void testLookupKeysetIteration() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ // Force lookup state instantiation
+ assertFalse(list.containsKey(new TopLevelListKey("blah")));
+
+ assertSameIteratorObjects(list.keySet());
+ }
+
+ private static void assertSameIteratorObjects(final Collection<?> collection) {
+ final Iterator<?> iter1 = collection.iterator();
+ final Iterator<?> iter2 = collection.iterator();
+
+ while (iter1.hasNext()) {
+ // Both iterators should return same values
+ assertSame(iter1.next(), iter2.next());
+ }
+ assertFalse(iter2.hasNext());
+ }
+
+ @Test
+ public void testIterSameViews() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ assertSame(list.values(), list.values());
+ assertSame(list.keySet(), list.keySet());
+ assertSame(list.entrySet(), list.entrySet());
+ }
+
+ @Test
+ public void testLookupSameViews() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ // Force lookup state instantiation
+ assertFalse(list.containsKey(new TopLevelListKey("blah")));
+
+ // Careful now ... first compare should end up changing the iteration of keyset/entryset
+ final Set<TopLevelListKey> keySet1 = list.keySet();
+ final Set<TopLevelListKey> keySet2 = list.keySet();
+ final Set<Entry<TopLevelListKey, TopLevelList>> entrySet1 = list.entrySet();
+ final Set<Entry<TopLevelListKey, TopLevelList>> entrySet2 = list.entrySet();
+
+ // .. right here ...
+ assertSame(list.values(), list.values());
+ // ... so this should end up iterating slightly differently
+ assertEquals(new HashSet<>(list.values()), new HashSet<>(list.values()));
+
+ // ... and as we do not reuse keyset/entryset, we need to run full compare
+ assertEquals(keySet1, keySet2);
+ assertEquals(keySet1, new HashSet<>(keySet2));
+ assertEquals(entrySet1, entrySet2);
+ assertEquals(entrySet1, new HashSet<>(entrySet2));
+ }
+
+ @Test
+ public void testIterSameSize() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ // Force lookup state instantiation
+ assertFalse(list.containsKey(new TopLevelListKey("blah")));
+
+ assertEquals(list.size(), list.entrySet().size());
+ assertEquals(list.size(), list.keySet().size());
+ assertEquals(list.size(), list.values().size());
+ }
+
+ @Test
+ public void testLookupSameSize() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ assertEquals(list.size(), list.entrySet().size());
+ assertEquals(list.size(), list.keySet().size());
+ assertEquals(list.size(), list.values().size());
+ }
+
+ @Test
+ public void testImmutableThrows() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ // Various asserts for completeness' sake
+ assertThrows(UnsupportedOperationException.class, () -> list.clear());
+ assertThrows(UnsupportedOperationException.class, () -> list.remove(null));
+ assertThrows(UnsupportedOperationException.class, () -> list.putAll(null));
+ }
+
+ @Test
+ public void testLookupContainsValueThrows() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ assertThrows(NullPointerException.class, () -> list.containsValue(null));
+ assertThrows(ClassCastException.class, () -> list.containsValue(mock(DataObject.class)));
+ }
+
+ @Test
+ public void testLookupContainsKeyThrows() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ assertThrows(NullPointerException.class, () -> list.containsKey(null));
+ assertThrows(ClassCastException.class, () -> list.containsKey(mock(Identifiable.class)));
+ }
+
+ @Test
+ public void testLookupKey() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ for (TopLevelListKey key : TOP.getTopLevelList().keySet()) {
+ assertTrue(list.containsKey(key));
+ }
+
+ assertFalse(list.containsKey(new TopLevelListKey("blah")));
+ }
+
+ @Test
+ public void testLookupValue() {
+ final Map<TopLevelListKey, TopLevelList> list = prepareData().getTopLevelList();
+ for (TopLevelList val : TOP.getTopLevelList().values()) {
+ assertTrue(list.containsValue(val));
+ }
+
+ assertFalse(list.containsValue(new TopLevelListBuilder().setName("blah").build()));
+
+ // We checked this key, but this is a different object
+ assertFalse(list.containsValue(new TopLevelListBuilder(TOP.getTopLevelList().values().iterator().next())
+ .setNestedList(List.of(new NestedListBuilder().setName("foo").build()))
+ .build()));
+ }
+
+ private Top prepareData() {
+ return thereAndBackAgain(InstanceIdentifier.create(Top.class), TOP);
+ }
+}