When a pairing backed by the array is removed, the order of pairings
would not follow the insertion order. This patch introduces an explicit
removal marker object and when the marker is present we defer to
newKeys map.
Change-Id: Ib27313e0df44754f5219d64126e0ec2a472a503f
Signed-off-by: Robert Varga <rovarga@cisco.com>
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
-import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
Ordered(final Map<K, Integer> offsets, final V[] objects) {
super(offsets, objects, new LinkedHashMap<K, V>());
}
Ordered(final Map<K, Integer> offsets, final V[] objects) {
super(offsets, objects, new LinkedHashMap<K, V>());
}
+
+ @Override
+ Object removedObject() {
+ return REMOVED;
+ }
+
+ @Override
+ UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] objects) {
+ return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), objects);
+ }
+
+ @Override
+ UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsets, final V[] objects) {
+ return new ImmutableOffsetMap.Ordered<>(offsets, objects);
+ }
}
private static final Object[] EMPTY_ARRAY = new Object[0];
}
private static final Object[] EMPTY_ARRAY = new Object[0];
+ private static final Object REMOVED = new Object();
private final Map<K, Integer> offsets;
private HashMap<K, V> newKeys;
private final Map<K, Integer> offsets;
private HashMap<K, V> newKeys;
+ private Object[] objects;
private int removed = 0;
private transient volatile int modCount;
private boolean needClone = true;
private int removed = 0;
private transient volatile int modCount;
private boolean needClone = true;
return new MutableOffsetMap.Ordered<>();
}
return new MutableOffsetMap.Ordered<>();
}
+ abstract Object removedObject();
+ abstract UnmodifiableMapPhase<K, V> modifiedMap(List<K> keys, V[] objects);
+ abstract UnmodifiableMapPhase<K, V> unmodifiedMap(Map<K, Integer> offsets, V[] objects);
+
@Override
public final int size() {
return offsets.size() + newKeys.size() - removed;
@Override
public final int size() {
return offsets.size() + newKeys.size() - removed;
@Override
public final boolean containsKey(final Object key) {
final Integer offset = offsets.get(key);
@Override
public final boolean containsKey(final Object key) {
final Integer offset = offsets.get(key);
- return offset == null ? newKeys.containsKey(key) : objects[offset] != null;
+ if (offset != null) {
+ final Object obj = objects[offset];
+ if (!REMOVED.equals(obj)) {
+ return obj != null;
+ }
+ }
+
+ return newKeys.containsKey(key);
}
@Override
public final V get(final Object key) {
final Integer offset = offsets.get(key);
}
@Override
public final V get(final Object key) {
final Integer offset = offsets.get(key);
- return offset == null ? newKeys.get(key) : objects[offset];
+ if (offset != null) {
+ final Object obj = objects[offset];
+
+ /*
+ * This is a bit tricky: Ordered will put REMOVED to removed objects to retain strict insertion order.
+ * Unordered will add null, indicating that the slot may be reused in future. Hence if we see a REMOVED
+ * marker, we need to fall back to checking with new keys.
+ */
+ if (!REMOVED.equals(obj)) {
+ @SuppressWarnings("unchecked")
+ final V ret = (V)obj;
+ return ret;
+ }
+ }
+
+ return newKeys.get(key);
}
private void cloneArray() {
}
private void cloneArray() {
- public V put(final K key, final V value) {
+ public final V put(final K key, final V value) {
Preconditions.checkNotNull(value);
final Integer offset = offsets.get(Preconditions.checkNotNull(key));
Preconditions.checkNotNull(value);
final Integer offset = offsets.get(Preconditions.checkNotNull(key));
- if (offset == null) {
- final V ret = newKeys.put(key, value);
- if (ret == null) {
- modCount++;
+ if (offset != null) {
+ final Object obj = objects[offset];
+
+ /*
+ * Put which can potentially replace something in objects. Replacing an object does not cause iterators
+ * to be invalidated and does follow insertion order (since it is not a fresh insert). If the object has
+ * been removed, we fall back to newKeys.
+ */
+ if (!REMOVED.equals(obj)) {
+ @SuppressWarnings("unchecked")
+ final V ret = (V)obj;
+
+ cloneArray();
+ objects[offset] = value;
+ if (ret == null) {
+ modCount++;
+ removed--;
+ }
+
+ return ret;
- cloneArray();
- final V ret = objects[offset];
- objects[offset] = value;
+ final V ret = newKeys.put(key, value);
if (ret == null) {
modCount++;
if (ret == null) {
modCount++;
- public V remove(final Object key) {
+ public final V remove(final Object key) {
final Integer offset = offsets.get(key);
final Integer offset = offsets.get(key);
- if (offset == null) {
- final V ret = newKeys.remove(key);
- if (ret != null) {
- modCount++;
+ if (offset != null) {
+ final Object obj = objects[offset];
+
+ /*
+ * A previous remove() may have indicated that the objects slot cannot be reused. In that case we need
+ * to fall back to checking with newKeys.
+ */
+ if (!REMOVED.equals(obj)) {
+ cloneArray();
+
+ @SuppressWarnings("unchecked")
+ final V ret = (V)obj;
+ objects[offset] = removedObject();
+ if (ret != null) {
+ modCount++;
+ removed++;
+ }
+ return ret;
- cloneArray();
- final V ret = objects[offset];
- objects[offset] = null;
+ final V ret = newKeys.remove(key);
if (ret != null) {
modCount++;
if (ret != null) {
modCount++;
}
return ret;
}
@Override
}
return ret;
}
@Override
+ public final void clear() {
if (size() != 0) {
newKeys.clear();
cloneArray();
if (size() != 0) {
newKeys.clear();
cloneArray();
- Arrays.fill(objects, null);
+ Arrays.fill(objects, removedObject());
removed = objects.length;
modCount++;
}
removed = objects.length;
modCount++;
}
@Override
public Map<K, V> toUnmodifiableMap() {
@Override
public Map<K, V> toUnmodifiableMap() {
- if (newKeys.isEmpty() && removed == 0) {
+ if (removed == 0 && newKeys.isEmpty()) {
// Make sure next modification clones the array, as we leak it to the map we return.
needClone = true;
// Make sure next modification clones the array, as we leak it to the map we return.
needClone = true;
+
+ // We have ended up with no removed objects, hence this cast is safe
+ @SuppressWarnings("unchecked")
+ final V[] values = (V[])objects;
+
/*
* TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
* perform any modifications, just return the original instance. The trade-off is increased complexity
* and an additional field in this class.
*/
/*
* TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
* perform any modifications, just return the original instance. The trade-off is increased complexity
* and an additional field in this class.
*/
- return new ImmutableOffsetMap.Ordered<>(offsets, objects);
+ return unmodifiedMap(offsets, values);
return ImmutableMap.of();
}
if (s == 1) {
return ImmutableMap.of();
}
if (s == 1) {
- return ImmutableMap.copyOf(this);
+ return SharedSingletonMap.copyOf(this);
}
// Construct the set of keys
}
// Construct the set of keys
- final Collection<K> keyset = new ArrayList<>(s);
+ final List<K> keyset = new ArrayList<>(s);
if (removed != 0) {
if (removed != offsets.size()) {
for (Entry<K, Integer> e : offsets.entrySet()) {
if (removed != 0) {
if (removed != offsets.size()) {
for (Entry<K, Integer> e : offsets.entrySet()) {
- if (objects[e.getValue()] != null) {
+ final Object o = objects[e.getValue()];
+ if (o != null && !REMOVED.equals(o)) {
keyset.add(e.getKey());
}
}
keyset.add(e.getKey());
}
}
if (removed != 0) {
if (removed != offsets.size()) {
for (Entry<K, Integer> e : offsets.entrySet()) {
if (removed != 0) {
if (removed != offsets.size()) {
for (Entry<K, Integer> e : offsets.entrySet()) {
- final V o = objects[e.getValue()];
- if (o != null) {
- values[i++] = o;
+ final Object o = objects[e.getValue()];
+ if (o != null && !REMOVED.equals(o)) {
+ @SuppressWarnings("unchecked")
+ final V v = (V) o;
+ values[i++] = v;
- return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keyset), values);
+ return modifiedMap(keyset, values);
}
@SuppressWarnings("unchecked")
}
@SuppressWarnings("unchecked")
// Ensure all objects are present
for (Entry<K, Integer> e : offsets.entrySet()) {
// Ensure all objects are present
for (Entry<K, Integer> e : offsets.entrySet()) {
- final V v = objects[e.getValue()];
- if (v != null && !v.equals(other.get(e.getKey()))) {
+ final Object obj = objects[e.getValue()];
+ if (obj != null && !REMOVED.equals(obj) && !obj.equals(other.get(e.getKey()))) {
private void updateNextKey() {
while (oldIterator.hasNext()) {
final Entry<K, Integer> e = oldIterator.next();
private void updateNextKey() {
while (oldIterator.hasNext()) {
final Entry<K, Integer> e = oldIterator.next();
- if (objects[e.getValue()] != null) {
+ final Object obj = objects[e.getValue()];
+ if (obj != null && !REMOVED.equals(obj)) {
nextKey = e.getKey();
return;
}
nextKey = e.getKey();
return;
}
final Integer offset = offsets.get(currentKey);
if (offset != null) {
cloneArray();
final Integer offset = offsets.get(currentKey);
if (offset != null) {
cloneArray();
- objects[offset] = null;
+ objects[offset] = removedObject();
removed++;
} else {
newIterator.remove();
removed++;
} else {
newIterator.remove();
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import com.google.common.collect.ImmutableMap;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Iterables;
import com.google.common.collect.Iterators;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import com.google.common.collect.Iterators;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
mutable.put("k1", "v1");
final ImmutableOffsetMap<String, String> result = (ImmutableOffsetMap<String, String>) mutable.toUnmodifiableMap();
mutable.put("k1", "v1");
final ImmutableOffsetMap<String, String> result = (ImmutableOffsetMap<String, String>) mutable.toUnmodifiableMap();
- assertEquals(source, result);
+ assertTrue(source.equals(result));
+ assertTrue(result.equals(source));
- // 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()));
+ // Iterator order must not be preserved
+ assertFalse(Iterators.elementsEqual(source.entrySet().iterator(), result.entrySet().iterator()));
final Map<String, String> result = mutable.toUnmodifiableMap();
// Should devolve to a singleton
final Map<String, String> result = mutable.toUnmodifiableMap();
// Should devolve to a singleton
- assertTrue(result instanceof ImmutableMap);
+ assertTrue(result instanceof SharedSingletonMap);
assertEquals(ImmutableMap.of("k2", "v2"), result);
}
assertEquals(ImmutableMap.of("k2", "v2"), result);
}
mutable.put("k3", "v3");
mutable.put("k1", "v1");
mutable.put("k3", "v3");
mutable.put("k1", "v1");
- assertEquals(ImmutableMap.of("k3", "v3"), mutable.newKeys());
+ assertEquals(ImmutableMap.of("k1", "v1", "k3", "v3"), mutable.newKeys());
final Map<String, String> result = mutable.toUnmodifiableMap();
assertTrue(result instanceof ImmutableOffsetMap);
assertEquals(threeEntryMap, result);
assertEquals(result, threeEntryMap);
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()));
+ assertFalse(Iterators.elementsEqual(threeEntryMap.entrySet().iterator(), result.entrySet().iterator()));
assertFalse(source.needClone());
assertTrue(result.needClone());
assertFalse(source.needClone());
assertTrue(result.needClone());
- // Creates a immutable view, which shares the array
+ // Forced copy, no cloning needed, but maps are equal
final ImmutableOffsetMap<String, String> immutable = (ImmutableOffsetMap<String, String>) source.toUnmodifiableMap();
final ImmutableOffsetMap<String, String> immutable = (ImmutableOffsetMap<String, String>) source.toUnmodifiableMap();
- assertTrue(source.needClone());
- assertSame(source.array(), immutable.objects());
+ assertFalse(source.needClone());
+ assertTrue(source.equals(immutable));
+ assertTrue(immutable.equals(source));
+ assertTrue(Iterables.elementsEqual(source.entrySet(), immutable.entrySet()));