@Override
public MutableOffsetMap<K, V> toModifiableMap() {
- return MutableOffsetMap.copyOf(this);
+ return MutableOffsetMap.orderedCopyOf(this);
}
@Override
- Map<K, Integer> resolveKeys(final List<K> keys) {
- return OffsetMapCache.orderedOffsets(keys);
+ void setFields(final List<K> keys, final V[] values) throws IOException {
+ setField(this, OFFSETS_FIELD, OffsetMapCache.orderedOffsets(keys));
+ setField(this, ARRAY_FIELD, values);
+ }
+ }
+
+ static final class Unordered<K, V> extends ImmutableOffsetMap<K, V> {
+ private static final long serialVersionUID = 1L;
+
+ Unordered(final Map<K, Integer> offsets, final V[] objects) {
+ super(offsets, objects);
+ }
+
+ @Override
+ public MutableOffsetMap<K, V> toModifiableMap() {
+ return MutableOffsetMap.unorderedCopyOf(this);
+ }
+
+ @Override
+ void setFields(final List<K> keys, final V[] values) throws IOException {
+ final Map<K, Integer> offsets = OffsetMapCache.unorderedOffsets(keys);
+
+ setField(this, OFFSETS_FIELD, offsets);
+ setField(this, ARRAY_FIELD, OffsetMapCache.adjustedArray(offsets, keys, values));
}
}
private static final long serialVersionUID = 1L;
- private final Map<K, Integer> offsets;
- private final V[] objects;
- private int hashCode;
+ private transient final Map<K, Integer> offsets;
+ private transient final V[] objects;
+ private transient int hashCode;
/**
* Construct a new instance backed by specified key-to-offset map and array of objects.
@Override
public abstract MutableOffsetMap<K, V> toModifiableMap();
- abstract Map<K, Integer> resolveKeys(List<K> keys);
+ abstract void setFields(List<K> keys, V[] values) throws IOException;
/**
* Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
*
* @param m Input map, may not be null.
* @return An isolated, immutable copy of the input map
+ * @deprecated Use {@link #orderedCopyOf(Map)} or {@link #unorderedCopyOf(Map)} instead.
*/
+ @Deprecated
@Nonnull public static <K, V> Map<K, V> copyOf(@Nonnull final Map<K, V> m) {
+ return orderedCopyOf(m);
+ }
+
+ /**
+ * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
+ * as this method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient.
+ * This method also recognizes {@link ImmutableOffsetMap} on input, and returns it back without doing anything else.
+ * It also recognizes {@link MutableOffsetMap} (as returned by {@link #toModifiableMap()}) and makes an efficient
+ * copy of its contents. All other maps are converted to an {@link ImmutableOffsetMap} with the same iteration
+ * order as input.
+ *
+ * @param m Input map, may not be null.
+ * @return An isolated, immutable copy of the input map
+ */
+ @Nonnull public static <K, V> Map<K, V> orderedCopyOf(@Nonnull final Map<K, V> m) {
// Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
if (m instanceof ImmutableOffsetMap || m instanceof SharedSingletonMap) {
return m;
if (size == 1) {
// Efficient single-entry implementation
final Entry<K, V> e = m.entrySet().iterator().next();
- return SharedSingletonMap.of(e.getKey(), e.getValue());
+ return SharedSingletonMap.orderedOf(e.getKey(), e.getValue());
}
final Map<K, Integer> offsets = OffsetMapCache.orderedOffsets(m.keySet());
return new Ordered<>(offsets, array);
}
+ /**
+ * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
+ * as this method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient.
+ * This method also recognizes {@link ImmutableOffsetMap} on input, and returns it back without doing anything else.
+ * It also recognizes {@link MutableOffsetMap} (as returned by {@link #toModifiableMap()}) and makes an efficient
+ * copy of its contents. All other maps are converted to an {@link ImmutableOffsetMap}. Iterator order is not
+ * guaranteed to be retained.
+ *
+ * @param m Input map, may not be null.
+ * @return An isolated, immutable copy of the input map
+ */
+ @Nonnull public static <K, V> Map<K, V> unorderedCopyOf(@Nonnull final Map<K, V> m) {
+ // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
+ if (m instanceof ImmutableOffsetMap || m instanceof SharedSingletonMap) {
+ return m;
+ }
+
+ // Familiar and efficient to copy
+ if (m instanceof MutableOffsetMap) {
+ return ((MutableOffsetMap<K, V>) m).toUnmodifiableMap();
+ }
+
+ final int size = m.size();
+ if (size == 0) {
+ // Shares a single object
+ return ImmutableMap.of();
+ }
+ if (size == 1) {
+ // Efficient single-entry implementation
+ final Entry<K, V> e = m.entrySet().iterator().next();
+ return SharedSingletonMap.unorderedOf(e.getKey(), e.getValue());
+ }
+
+ final Map<K, Integer> offsets = OffsetMapCache.unorderedOffsets(m.keySet());
+ @SuppressWarnings("unchecked")
+ final V[] array = (V[]) new Object[offsets.size()];
+ for (Entry<K, V> e : m.entrySet()) {
+ array[offsets.get(e.getKey())] = e.getValue();
+ }
+
+ return new Unordered<>(offsets, array);
+ }
+
@Override
public final int size() {
return offsets.size();
return f;
}
- private void setField(final Field field, final Object value) throws IOException {
+ private static void setField(final ImmutableOffsetMap<?, ?> map, final Field field, final Object value) throws IOException {
try {
- field.set(this, value);
+ field.set(map, value);
} catch (IllegalArgumentException | IllegalAccessException e) {
throw new IOException("Failed to set field " + field, e);
}
values[i] = (V)in.readObject();
}
- setField(OFFSETS_FIELD, resolveKeys(keys));
- setField(ARRAY_FIELD, values);
+ setFields(keys, values);
}
}
UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsets, final V[] objects) {
return new ImmutableOffsetMap.Ordered<>(offsets, objects);
}
+
+ @Override
+ SharedSingletonMap<K, V> singletonMap() {
+ return SharedSingletonMap.orderedCopyOf(this);
+ }
+ }
+
+ static final class Unordered<K, V> extends MutableOffsetMap<K, V> {
+ Unordered() {
+ super(new HashMap<K, V>());
+ }
+
+ Unordered(final Map<K, V> source) {
+ super(OffsetMapCache.unorderedOffsets(source.keySet()), source, new HashMap<K, V>());
+ }
+
+ Unordered(final Map<K, Integer> offsets, final V[] objects) {
+ super(offsets, objects, new HashMap<K, V>());
+ }
+
+ @Override
+ Object removedObject() {
+ return null;
+ }
+
+ @Override
+ UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] objects) {
+ final Map<K, Integer> offsets = OffsetMapCache.unorderedOffsets(keys);
+ return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, objects));
+ }
+
+ @Override
+ UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsets, final V[] objects) {
+ return new ImmutableOffsetMap.Unordered<>(offsets, objects);
+ }
+
+ @Override
+ SharedSingletonMap<K, V> singletonMap() {
+ return SharedSingletonMap.unorderedCopyOf(this);
+ }
}
private static final Object[] EMPTY_ARRAY = new Object[0];
this.needClone = false;
}
+ /**
+ * @deprecated Use {@link #orderedCopyOf(Map)} or {@link #unorderedCopyOf(Map)} instead.
+ */
+ @Deprecated
public static <K, V> MutableOffsetMap<K, V> copyOf(final Map<K, V> m) {
- if (m instanceof MutableOffsetMap) {
- return ((MutableOffsetMap<K, V>) m).clone();
+ return orderedCopyOf(m);
+ }
+
+ public static <K, V> MutableOffsetMap<K, V> orderedCopyOf(final Map<K, V> m) {
+ if (m instanceof Ordered) {
+ return ((Ordered<K, V>) m).clone();
}
if (m instanceof ImmutableOffsetMap) {
final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) m;
- return new MutableOffsetMap.Ordered<>(om.offsets(), om.objects());
+ return new Ordered<>(om.offsets(), om.objects());
}
- return new MutableOffsetMap.Ordered<>(m);
+ return new Ordered<>(m);
}
+ public static <K, V> MutableOffsetMap<K, V> unorderedCopyOf(final Map<K, V> m) {
+ if (m instanceof Unordered) {
+ return ((Unordered<K, V>) m).clone();
+ }
+ if (m instanceof ImmutableOffsetMap) {
+ final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) m;
+ return new Unordered<>(om.offsets(), om.objects());
+ }
+
+ return new Unordered<>(m);
+ }
+
+ /**
+ * @deprecated Use {@link #ordered()} or {@link #unordered()} instead.
+ */
+ @Deprecated
public static <K, V> MutableOffsetMap<K, V> of() {
+ return ordered();
+ }
+
+ public static <K, V> MutableOffsetMap<K, V> ordered() {
return new MutableOffsetMap.Ordered<>();
}
+ public static <K, V> MutableOffsetMap<K, V> unordered() {
+ return new MutableOffsetMap.Unordered<>();
+ }
+
abstract Object removedObject();
abstract UnmodifiableMapPhase<K, V> modifiedMap(List<K> keys, V[] objects);
abstract UnmodifiableMapPhase<K, V> unmodifiedMap(Map<K, Integer> offsets, V[] objects);
+ abstract SharedSingletonMap<K, V> singletonMap();
@Override
public final int size() {
return ImmutableMap.of();
}
if (s == 1) {
- return SharedSingletonMap.copyOf(this);
+ return singletonMap();
}
// Construct the set of keys
package org.opendaylight.yangtools.util;
import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Verify;
import com.google.common.cache.CacheBuilder;
import com.google.common.cache.CacheLoader;
import com.google.common.cache.LoadingCache;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableMap.Builder;
import com.google.common.collect.ImmutableSet;
+import java.lang.reflect.Array;
import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
import java.util.Map;
final class OffsetMapCache {
return offsets(ImmutableSet.copyOf(args));
}
+
+ private static <K, V> V[] adjustArray(final Map<K, Integer> offsets, final List<K> keys, final V[] array) {
+ @SuppressWarnings("unchecked")
+ final V[] ret = (V[]) Array.newInstance(array.getClass().getComponentType(), array.length);
+
+ int i = 0;
+ for (final K k : keys) {
+ final Integer o = Verify.verifyNotNull(offsets.get(k), "Key %s not present in offsets %s", k, offsets);
+ ret[o] = array[i++];
+ }
+
+ return ret;
+ }
+
+ static <K, V> V[] adjustedArray(final Map<K, Integer> offsets, final List<K> keys, final V[] array) {
+ Verify.verify(offsets.size() == keys.size(), "Offsets %s do not match keys %s", offsets, keys);
+
+ // This relies on the fact that offsets has an ascending iterator
+ final Iterator<K> oi = offsets.keySet().iterator();
+ final Iterator<K> ki = keys.iterator();
+
+ while (oi.hasNext()) {
+ final K o = oi.next();
+ final K k = ki.next();
+ if (!k.equals(o)) {
+ return adjustArray(offsets, keys, array);
+ }
+ }
+
+ return array;
+ }
}
@Override
public ModifiableMapPhase<K, V> toModifiableMap() {
- return MutableOffsetMap.copyOf(this);
+ return MutableOffsetMap.orderedCopyOf(this);
+ }
+ }
+
+ private static final class Unordered<K, V> extends SharedSingletonMap<K, V> {
+ private static final long serialVersionUID = 1L;
+
+ Unordered(final K key, final V value) {
+ super(key, value);
+ }
+
+ @Override
+ public ModifiableMapPhase<K, V> toModifiableMap() {
+ return MutableOffsetMap.unorderedCopyOf(this);
}
}
this.value = Preconditions.checkNotNull(value);
}
+ /**
+ * @deprecated Use {@link #orderedOf(Object, Object)} or {@link #unorderedOf(Object, Object)} instead.
+ */
+ @Deprecated
public static <K, V> SharedSingletonMap<K, V> of(final K key, final V value) {
return new Ordered<>(key, value);
}
+ public static <K, V> SharedSingletonMap<K, V> orderedOf(final K key, final V value) {
+ return new Ordered<>(key, value);
+ }
+
+ public static <K, V> SharedSingletonMap<K, V> unorderedOf(final K key, final V value) {
+ return new Unordered<>(key, value);
+ }
+
+ /**
+ * @deprecated Use {@link #orderedCopyOf(Map)} or {@link #unorderedCopyOf(Map)} instead.
+ */
+ @Deprecated
public static <K, V> SharedSingletonMap<K, V> copyOf(final Map<K, V> m) {
+ return orderedCopyOf(m);
+ }
+
+ public static <K, V> SharedSingletonMap<K, V> orderedCopyOf(final Map<K, V> m) {
Preconditions.checkArgument(m.size() == 1);
final Entry<K, V> e = m.entrySet().iterator().next();
return new Ordered<>(e.getKey(), e.getValue());
}
+ public static <K, V> SharedSingletonMap<K, V> unorderedCopyOf(final Map<K, V> m) {
+ Preconditions.checkArgument(m.size() == 1);
+
+ final Entry<K, V> e = m.entrySet().iterator().next();
+ return new Unordered<>(e.getKey(), e.getValue());
+ }
+
@Override
public final SingletonSet<Entry<K, V>> entrySet() {
return SingletonSet.<Entry<K, V>>of(new SimpleImmutableEntry<>(keySet.getElement(), value));
private final Map<String, String> threeEntryMap = ImmutableMap.of("k1", "v1", "k2", "v2", "k3", "v3");
private ImmutableOffsetMap<String, String> createMap() {
- return (ImmutableOffsetMap<String, String>) ImmutableOffsetMap.copyOf(twoEntryMap);
+ return (ImmutableOffsetMap<String, String>) ImmutableOffsetMap.orderedCopyOf(twoEntryMap);
+ }
+
+ private ImmutableOffsetMap<String, String> unorderedMap() {
+ return (ImmutableOffsetMap<String, String>) ImmutableOffsetMap.unorderedCopyOf(twoEntryMap);
}
@Before
@Test
public void testCopyEmptyMap() {
final Map<String, String> source = Collections.emptyMap();
- final Map<String, String> result = ImmutableOffsetMap.copyOf(source);
+ final Map<String, String> result = ImmutableOffsetMap.orderedCopyOf(source);
assertEquals(source, result);
assertTrue(result instanceof ImmutableMap);
@Test
public void testCopySingletonMap() {
final Map<String, String> source = Collections.singletonMap("a", "b");
- final Map<String, String> result = ImmutableOffsetMap.copyOf(source);
+ final Map<String, String> result = ImmutableOffsetMap.orderedCopyOf(source);
assertEquals(source, result);
assertTrue(result instanceof SharedSingletonMap);
assertTrue(Iterators.elementsEqual(twoEntryMap.entrySet().iterator(), map.entrySet().iterator()));
// Should result in the same object
- assertSame(map, ImmutableOffsetMap.copyOf(map));
+ assertSame(map, ImmutableOffsetMap.orderedCopyOf(map));
final Map<String, String> mutable = map.toModifiableMap();
- final Map<String, String> copy = ImmutableOffsetMap.copyOf(mutable);
+ final Map<String, String> copy = ImmutableOffsetMap.orderedCopyOf(mutable);
assertEquals(mutable, copy);
assertEquals(map, copy);
assertFalse(Iterators.elementsEqual(source.entrySet().iterator(), result.entrySet().iterator()));
}
+ @Test
+ public void testReusedOffsetsUnordered() {
+ final ImmutableOffsetMap<String, String> source = unorderedMap();
+ final MutableOffsetMap<String, String> mutable = source.toModifiableMap();
+
+ mutable.remove("k1");
+ mutable.put("k1", "v1");
+
+ final ImmutableOffsetMap<String, String> result = (ImmutableOffsetMap<String, String>) mutable.toUnmodifiableMap();
+ assertEquals(source, result);
+
+ // Only offsets should be shared
+ assertSame(source.offsets(), result.offsets());
+ assertNotSame(source.objects(), result.objects());
+
+ // Iterator order needs to be preserved
+ assertTrue(Iterators.elementsEqual(source.entrySet().iterator(), result.entrySet().iterator()));
+ }
+
@Test
public void testEmptyMutable() throws CloneNotSupportedException {
- final MutableOffsetMap<String, String> map = MutableOffsetMap.of();
+ final MutableOffsetMap<String, String> map = MutableOffsetMap.ordered();
assertTrue(map.isEmpty());
final Map<String, String> other = map.clone();
assertFalse(Iterators.elementsEqual(threeEntryMap.entrySet().iterator(), result.entrySet().iterator()));
}
+ @Test
+ public void testExpansionWithoutOrder() {
+ final MutableOffsetMap<String, String> mutable = unorderedMap().toModifiableMap();
+
+ mutable.remove("k1");
+ mutable.put("k3", "v3");
+ mutable.put("k1", "v1");
+
+ assertEquals(ImmutableMap.of("k3", "v3"), mutable.newKeys());
+
+ final Map<String, String> result = mutable.toUnmodifiableMap();
+
+ assertTrue(result instanceof ImmutableOffsetMap);
+ assertEquals(threeEntryMap, result);
+ assertEquals(result, threeEntryMap);
+ assertTrue(Iterators.elementsEqual(threeEntryMap.entrySet().iterator(), result.entrySet().iterator()));
+ }
+
@Test
public void testReplacedValue() {
final ImmutableOffsetMap<String, String> source = createMap();
assertTrue(Iterables.elementsEqual(source.entrySet(), immutable.entrySet()));
}
+ @Test
+ public void testCloneableFlippingUnordered() throws CloneNotSupportedException {
+ final MutableOffsetMap<String, String> source = unorderedMap().toModifiableMap();
+
+ // Must clone before mutation
+ assertTrue(source.needClone());
+
+ // Non-existent entry, should not clone
+ source.remove("non-existent");
+ assertTrue(source.needClone());
+
+ // Changes the array, should clone
+ source.remove("k1");
+ assertFalse(source.needClone());
+
+ // Create a clone of the map, which shares the array
+ final MutableOffsetMap<String, String> result = source.clone();
+ assertFalse(source.needClone());
+ assertTrue(result.needClone());
+ assertSame(source.array(), result.array());
+
+ // Changes the array, should clone
+ source.put("k1", "v2");
+ assertFalse(source.needClone());
+ assertTrue(result.needClone());
+
+ // Creates a immutable view, which shares the array
+ final ImmutableOffsetMap<String, String> immutable = (ImmutableOffsetMap<String, String>) source.toUnmodifiableMap();
+ assertTrue(source.needClone());
+ assertSame(source.array(), immutable.objects());
+ }
+
@Test
public void testMutableEntrySet() {
final MutableOffsetMap<String, String> map = createMap().toModifiableMap();
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
+import com.google.common.collect.ImmutableMap;
import java.util.Collections;
import java.util.Map;
import java.util.Set;
public class SharedSingletonMapTest {
private static UnmodifiableMapPhase<String, String> create() {
- return SharedSingletonMap.of("k1", "v1");
+ return SharedSingletonMap.orderedOf("k1", "v1");
}
@Test
assertFalse(m.equals(Collections.singletonMap("k1", null)));
assertFalse(m.equals(Collections.singletonMap(null, "v1")));
assertFalse(m.equals(Collections.singletonMap("k1", "v2")));
+ assertFalse(m.equals(ImmutableMap.of("k1", "v1", "k2", "v2")));
final Set<String> set = m.keySet();
assertTrue(set instanceof SingletonSet);
assertTrue(set.contains("k1"));
}
+ @Test
+ public void testOrderedCopyOf() {
+ final Map<String, String> t = Collections.singletonMap("k1", "v1");
+ final Map<String, String> m = SharedSingletonMap.orderedCopyOf(t);
+ assertTrue(t.equals(m));
+ assertTrue(m.equals(t));
+ }
+
+ @Test
+ public void testUnorderedCopyOf() {
+ final Map<String, String> t = Collections.singletonMap("k1", "v1");
+ final Map<String, String> m = SharedSingletonMap.unorderedCopyOf(t);
+ assertTrue(t.equals(m));
+ assertTrue(m.equals(t));
+ }
+
+ @Test(expected=IllegalArgumentException.class)
+ public void testEmptyOrderedCopyOf() {
+ SharedSingletonMap.orderedCopyOf(ImmutableMap.of());
+ }
+
+ @Test(expected=IllegalArgumentException.class)
+ public void testEmptyUnorderedCopyOf() {
+ SharedSingletonMap.unorderedCopyOf(ImmutableMap.of());
+ }
+
@Test(expected=UnsupportedOperationException.class)
public void testClear() {
create().clear();
public NodeIdentifierWithPredicates(final QName node, final Map<QName, Object> keyValues) {
super(node);
// Retains ImmutableMap for empty maps. For larger sizes uses a shared key set.
- this.keyValues = ImmutableOffsetMap.copyOf(keyValues);
+ this.keyValues = ImmutableOffsetMap.unorderedCopyOf(keyValues);
}
public NodeIdentifierWithPredicates(final QName node, final QName key, final Object value) {
- this(node, SharedSingletonMap.of(key, value));
+ super(node);
+ this.keyValues = SharedSingletonMap.unorderedOf(key, value);
}
public Map<QName, Object> getKeyValues() {
import org.opendaylight.yangtools.yang.data.api.schema.DataContainerChild;
import org.opendaylight.yangtools.yang.data.api.schema.DataContainerNode;
-public abstract class AbstractImmutableDataContainerNode<K extends PathArgument> extends AbstractImmutableNormalizedNode<K, Collection<DataContainerChild<? extends PathArgument, ?>>> implements Immutable, DataContainerNode<K> {
+public abstract class AbstractImmutableDataContainerNode<K extends PathArgument>
+ extends AbstractImmutableNormalizedNode<K, Collection<DataContainerChild<? extends PathArgument, ?>>>
+ implements Immutable, DataContainerNode<K> {
private final Map<PathArgument, DataContainerChild<? extends PathArgument, ?>> children;
public AbstractImmutableDataContainerNode(
final Map<PathArgument, DataContainerChild<? extends PathArgument, ?>> children, final K nodeIdentifier) {
super(nodeIdentifier);
- this.children = ImmutableOffsetMap.copyOf(children);
+ this.children = ImmutableOffsetMap.unorderedCopyOf(children);
}
@Override
Code Review / yangtools.git / commitdiff