2 * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved.
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
8 package org.opendaylight.mdsal.binding.dom.codec.impl;
10 import static java.util.Objects.requireNonNull;
11 import static org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingList.OBJ_AA;
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;
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.Identifiable;
29 import org.opendaylight.yangtools.yang.binding.Identifier;
30 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
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.
37 * @param <V> value type
39 final class LazyBindingMapLookupState<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
40 extends LazyBindingMap.State<K, V> {
41 private static final VarHandle VALUES;
45 VALUES = MethodHandles.lookup().findVarHandle(LazyBindingMapLookupState.class, "values", Values.class);
46 } catch (NoSuchFieldException | IllegalAccessException e) {
47 throw new ExceptionInInitializerError(e);
51 // Primary storage of transformed nodes
52 private final ConcurrentHashMap<K, V> objects = new ConcurrentHashMap<>();
53 private final LazyBindingMap<K, V> map;
55 // Used via the varhandle above
56 @SuppressWarnings("unused")
57 private volatile Values<K, V> values;
59 LazyBindingMapLookupState(final LazyBindingMap<K, V> map) {
60 this.map = requireNonNull(map);
64 boolean containsKey(final Object key) {
65 // If we have the value, that is always accurate. Otherwise we have to attempt to load from DOM data and see
66 // what the result is.
67 return objects.containsKey(key) || loadKey(key) != null;
71 V get(final Object key) {
73 // Perform a lookup first, otherwise try to load the key from DOM data
74 return (existing = objects.get(key)) != null ? existing : loadKey(key);
78 KeySet<K, V> keySet() {
79 return new KeySet<>(values());
83 Values<K, V> values() {
84 final Values<K, V> ret;
85 return (ret = (Values<K, V>) VALUES.getAcquire(this)) != null ? ret : loadValues();
89 EntrySet<K, V> entrySet() {
90 return new EntrySet<>(values());
93 private @Nullable V loadKey(final @NonNull Object key) {
94 final Optional<V> opt = map.lookupValue(key);
99 // Here is a conundrum: which key do we use?
101 // We have the lookup key readily available, which means faster insert at the expense of having duplicates once
102 // the looked-up object is accessed. On the other hand we could use ret.key(), which forces population of key
103 // properties and the key itself.
105 // Opt for the provided key, as it is likely the user will end up looking at other properties of the returned
108 // This leaves the option for lookupValue() to use the key to initialize object's cache fields, so that we end
109 // up reflecting the same key instance as well as reuse key's components as object values. The case for that
110 // needs to be justified, though, as it ends up doing more work upfront unrelated to what the caller is about
112 return putIfAbsent((K) key, opt.orElseThrow());
115 private @NonNull V putIfAbsent(final @NonNull K key, final @NonNull V value) {
116 final V existing = objects.putIfAbsent(key, value);
117 return existing == null ? value : existing;
120 @SuppressWarnings("unchecked")
121 private @NonNull Values<K, V> loadValues() {
122 final Values<K, V> ret = new Values<>(this);
123 final Object witness;
124 return (witness = VALUES.compareAndExchangeRelease(this, null, ret)) == null ? ret : (Values<K, V>) witness;
127 private static final class EntrySet<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
128 extends AbstractSet<Entry<K, V>> implements Immutable {
129 private final Values<K, V> values;
131 EntrySet(final Values<K, V> values) {
132 this.values = requireNonNull(values);
136 public Iterator<Entry<K, V>> iterator() {
137 return values.entryIterator();
142 return values.size();
146 @SuppressWarnings("checkstyle:parameterName")
147 public boolean contains(final Object o) {
148 // Key/Value are related, asking whether we have a particular Entry is asking whether values contain that
150 return values.contains(((Entry<?, ?>)o).getValue());
154 @SuppressWarnings("checkstyle:equalsHashCode")
155 public boolean equals(final Object obj) {
156 // Fast check due to us not wasting a field for this value
157 return obj instanceof EntrySet && values == ((EntrySet<?, ?>) obj).values || super.equals(obj);
161 private static final class KeySet<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
162 extends AbstractSet<K> implements Immutable {
163 private final Values<K, V> values;
165 KeySet(final Values<K, V> values) {
166 this.values = requireNonNull(values);
170 public Iterator<K> iterator() {
171 return values.keyIterator();
176 return values.size();
180 @SuppressWarnings("checkstyle:parameterName")
181 public boolean contains(final Object o) {
182 return values.map().containsKey(o);
186 @SuppressWarnings("checkstyle:equalsHashCode")
187 public boolean equals(final Object obj) {
188 // Fast check due to us not wasting a field for this value
189 return obj instanceof KeySet && values == ((KeySet<?, ?>) obj).values || super.equals(obj);
193 private static final class Values<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
194 extends AbstractSet<V> implements Immutable {
195 private final LazyBindingMapLookupState<K, V> state;
197 // Temporary storage for translated objects. We first initialize this to DOM values, so that we know what
198 // objects we need to visit. As we iterate through them, we pick the source from here, then run them through
199 // decode, then reconcile with the lookup map and finally store them back here.
201 // Once at least one iterator has gone through the entire entire array, we throw it away, as at that point
202 // the primary storage is guaranteed to have all the same objects. We then free this array and switch to using
203 // views on top of primary storage instead.
205 // This has the side-effect of changing iteration order once one of the iterators has made a complete pass.
206 // While it may be counter-intuitive, we opt for the added memory efficiency and squirm just right to say
207 // this is okay for Immutable contract :)
208 @SuppressFBWarnings(value = "VO_VOLATILE_REFERENCE_TO_ARRAY",
209 justification = "The ref should really be volatile. This class does not access elements directly.")
210 private volatile Object[] objects;
212 Values(final LazyBindingMapLookupState<K, V> state) {
213 this.state = requireNonNull(state);
214 objects = map().mapNode().body().toArray();
218 public Iterator<V> iterator() {
219 final Object[] local = objects;
220 // When we have null objects it means we have everyone in state.objects
221 return local == null ? Iterators.unmodifiableIterator(state.objects.values().iterator())
222 : new ValuesIter<>(this, local);
226 @SuppressWarnings("checkstyle:parameterName")
227 public boolean contains(final Object o) {
228 return map().containsValue(o);
236 Iterator<Entry<K, V>> entryIterator() {
237 final Object[] local = objects;
238 // When we have null objects it means we have everyone in state.objects
239 return local == null ? Iterators.unmodifiableIterator(state.objects.entrySet().iterator())
240 : Iterators.transform(new ValuesIter<>(this, local), value -> Map.entry(value.key(), value));
243 Iterator<K> keyIterator() {
244 final Object[] local = objects;
245 // When we have null objects it means we have everyone in state.objects
246 return local == null ? Iterators.unmodifiableIterator(state.objects.keySet().iterator())
247 : Iterators.transform(new ValuesIter<>(this, local), value -> value.key());
250 LazyBindingMap<K, V> map() {
254 void fullyIterated() {
255 // We have iterated over all objects. Clear them to indicate further access should go through state.objects
260 private static final class ValuesIter<K extends Identifier<V>, V extends DataObject & Identifiable<K>>
261 extends AbstractIterator<V> {
262 private final Values<K, V> values;
263 private final Object[] objects;
264 private int nextOffset;
266 ValuesIter(final Values<K, V> values, final Object[] objects) {
267 this.values = requireNonNull(values);
268 this.objects = requireNonNull(objects);
272 protected V computeNext() {
273 if (nextOffset < objects.length) {
274 return objectAt(nextOffset++);
276 values.fullyIterated();
280 private @NonNull V objectAt(final int offset) {
281 final Object obj = OBJ_AA.getAcquire(objects, offset);
282 return obj instanceof MapEntryNode ? loadObjectAt(offset, (MapEntryNode) obj) : (V) obj;
285 private @NonNull V loadObjectAt(final int offset, final MapEntryNode obj) {
286 final LazyBindingMapLookupState<K, V> local = values.state;
287 final V created = local.map.createValue(obj);
288 final V ret = local.putIfAbsent(created.key(), created);
289 final Object witness;
290 return (witness = OBJ_AA.compareAndExchangeRelease(objects, offset, obj, ret)) == obj ? ret : (V) witness;