< prev index next >
src/jdk/nashorn/internal/runtime/arrays/SparseArrayData.java
Print this page
@@ -34,10 +34,11 @@
/**
* Handle arrays where the index is very large.
*/
class SparseArrayData extends ArrayData {
+ /** Maximum size for dense arrays */
static final int MAX_DENSE_LENGTH = 1024 * 1024;
/** Underlying array. */
private ArrayData underlying;
@@ -49,11 +50,11 @@
SparseArrayData(final ArrayData underlying, final long length) {
this(underlying, length, new TreeMap<Long, Object>());
}
- SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
+ private SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
super(length);
assert underlying.length() <= length;
this.underlying = underlying;
this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length());
this.sparseMap = sparseMap;
@@ -87,42 +88,53 @@
return objArray;
}
@Override
- public void shiftLeft(final int by) {
- underlying.shiftLeft(by);
+ public ArrayData shiftLeft(final int by) {
+ underlying = underlying.shiftLeft(by);
final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
final long newIndex = entry.getKey().longValue() - by;
+ if (newIndex >= 0) {
if (newIndex < maxDenseLength) {
- underlying = underlying.set((int) newIndex, entry.getValue(), false);
- } else if (newIndex >= 0) {
+ final long oldLength = underlying.length();
+ underlying = underlying.ensure(newIndex)
+ .set((int) newIndex, entry.getValue(), false)
+ .safeDelete(oldLength, newIndex - 1, false);
+ } else {
newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
}
}
+ }
sparseMap = newSparseMap;
setLength(Math.max(length() - by, 0));
+
+ return sparseMap.isEmpty() ? underlying : this;
}
@Override
public ArrayData shiftRight(final int by) {
final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
+ // Move elements from underlying to sparse map if necessary
final long len = underlying.length();
if (len + by > maxDenseLength) {
- for (long i = maxDenseLength - by; i < len; i++) {
+ // Length of underlying array after shrinking, before right-shifting
+ final long tempLength = Math.max(0, maxDenseLength - by);
+ for (long i = tempLength; i < len; i++) {
if (underlying.has((int) i)) {
newSparseMap.put(Long.valueOf(i + by), underlying.getObject((int) i));
}
}
- underlying = underlying.shrink((int) (maxDenseLength - by));
+ underlying = underlying.shrink((int) tempLength);
+ underlying.setLength(tempLength);
}
- underlying.shiftRight(by);
+ underlying = underlying.shiftRight(by);
for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
final long newIndex = entry.getKey().longValue() + by;
newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
}
@@ -133,18 +145,10 @@
return this;
}
@Override
public ArrayData ensure(final long safeIndex) {
- // Usually #ensure only needs to be called if safeIndex is greater or equal current length.
- // SparseArrayData is an exception as an index smaller than our current length may still
- // exceed the underlying ArrayData's capacity. Because of this, SparseArrayData invokes
- // its ensure method internally in various places where other ArrayData subclasses don't,
- // making it safe for outside uses to only call ensure(safeIndex) if safeIndex >= length.
- if (safeIndex < maxDenseLength && underlying.length() <= safeIndex) {
- underlying = underlying.ensure(safeIndex);
- }
if (safeIndex >= length()) {
setLength(safeIndex + 1);
}
return this;
}
@@ -165,12 +169,11 @@
@Override
public ArrayData set(final int index, final Object value, final boolean strict) {
if (index >= 0 && index < maxDenseLength) {
final long oldLength = underlying.length();
- ensure(index);
- underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
+ underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);
setLength(Math.max(underlying.length(), length()));
} else {
final Long longIndex = indexToKey(index);
sparseMap.put(longIndex, value);
setLength(Math.max(longIndex + 1, length()));
@@ -181,12 +184,11 @@
@Override
public ArrayData set(final int index, final int value, final boolean strict) {
if (index >= 0 && index < maxDenseLength) {
final long oldLength = underlying.length();
- ensure(index);
- underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
+ underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);
setLength(Math.max(underlying.length(), length()));
} else {
final Long longIndex = indexToKey(index);
sparseMap.put(longIndex, value);
setLength(Math.max(longIndex + 1, length()));
@@ -196,12 +198,11 @@
@Override
public ArrayData set(final int index, final double value, final boolean strict) {
if (index >= 0 && index < maxDenseLength) {
final long oldLength = underlying.length();
- ensure(index);
- underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
+ underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);
setLength(Math.max(underlying.length(), length()));
} else {
final Long longIndex = indexToKey(index);
sparseMap.put(longIndex, value);
setLength(Math.max(longIndex + 1, length()));
< prev index next >