19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package jdk.nashorn.internal.runtime.arrays; 27 28 import java.util.Arrays; 29 import java.util.Map; 30 import java.util.TreeMap; 31 import jdk.nashorn.internal.codegen.types.Type; 32 import jdk.nashorn.internal.runtime.JSType; 33 import jdk.nashorn.internal.runtime.ScriptRuntime; 34 35 /** 36 * Handle arrays where the index is very large. 37 */ 38 class SparseArrayData extends ArrayData { 39 static final int MAX_DENSE_LENGTH = 1024 * 1024; 40 41 /** Underlying array. */ 42 private ArrayData underlying; 43 44 /** Maximum length to be stored in the array. */ 45 private final long maxDenseLength; 46 47 /** Sparse elements. */ 48 private TreeMap<Long, Object> sparseMap; 49 50 SparseArrayData(final ArrayData underlying, final long length) { 51 this(underlying, length, new TreeMap<Long, Object>()); 52 } 53 54 SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) { 55 super(length); 56 assert underlying.length() <= length; 57 this.underlying = underlying; 58 this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length()); 59 this.sparseMap = sparseMap; 60 } 61 62 @Override 63 public ArrayData copy() { 64 return new SparseArrayData(underlying.copy(), length(), new TreeMap<>(sparseMap)); 65 } 66 67 @Override 68 public Object[] asObjectArray() { 69 final int len = (int)Math.min(length(), Integer.MAX_VALUE); 70 final int underlyingLength = (int)Math.min(len, underlying.length()); 71 final Object[] objArray = new Object[len]; 72 73 for (int i = 0; i < underlyingLength; i++) { 74 objArray[i] = underlying.getObject(i); 75 } 76 77 Arrays.fill(objArray, underlyingLength, len, ScriptRuntime.UNDEFINED); 78 79 for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 80 final long key = entry.getKey(); 81 if (key < Integer.MAX_VALUE) { 82 objArray[(int)key] = entry.getValue(); 83 } else { 84 break; // ascending key order 85 } 86 } 87 88 return objArray; 89 } 90 91 @Override 92 public void shiftLeft(final int by) { 93 underlying.shiftLeft(by); 94 95 final TreeMap<Long, Object> newSparseMap = new TreeMap<>(); 96 97 for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 98 final long newIndex = entry.getKey().longValue() - by; 99 if (newIndex < maxDenseLength) { 100 underlying = underlying.set((int) newIndex, entry.getValue(), false); 101 } else if (newIndex >= 0) { 102 newSparseMap.put(Long.valueOf(newIndex), entry.getValue()); 103 } 104 } 105 106 sparseMap = newSparseMap; 107 setLength(Math.max(length() - by, 0)); 108 } 109 110 @Override 111 public ArrayData shiftRight(final int by) { 112 final TreeMap<Long, Object> newSparseMap = new TreeMap<>(); 113 final long len = underlying.length(); 114 if (len + by > maxDenseLength) { 115 for (long i = maxDenseLength - by; i < len; i++) { 116 if (underlying.has((int) i)) { 117 newSparseMap.put(Long.valueOf(i + by), underlying.getObject((int) i)); 118 } 119 } 120 underlying = underlying.shrink((int) (maxDenseLength - by)); 121 } 122 123 underlying.shiftRight(by); 124 125 for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 126 final long newIndex = entry.getKey().longValue() + by; 127 newSparseMap.put(Long.valueOf(newIndex), entry.getValue()); 128 } 129 130 sparseMap = newSparseMap; 131 setLength(length() + by); 132 133 return this; 134 } 135 136 @Override 137 public ArrayData ensure(final long safeIndex) { 138 // Usually #ensure only needs to be called if safeIndex is greater or equal current length. 139 // SparseArrayData is an exception as an index smaller than our current length may still 140 // exceed the underlying ArrayData's capacity. Because of this, SparseArrayData invokes 141 // its ensure method internally in various places where other ArrayData subclasses don't, 142 // making it safe for outside uses to only call ensure(safeIndex) if safeIndex >= length. 143 if (safeIndex < maxDenseLength && underlying.length() <= safeIndex) { 144 underlying = underlying.ensure(safeIndex); 145 } 146 if (safeIndex >= length()) { 147 setLength(safeIndex + 1); 148 } 149 return this; 150 } 151 152 @Override 153 public ArrayData shrink(final long newLength) { 154 if (newLength < underlying.length()) { 155 underlying = underlying.shrink(newLength); 156 underlying.setLength(newLength); 157 sparseMap.clear(); 158 setLength(newLength); 159 } 160 161 sparseMap.subMap(Long.valueOf(newLength), Long.MAX_VALUE).clear(); 162 setLength(newLength); 163 return this; 164 } 165 166 @Override 167 public ArrayData set(final int index, final Object value, final boolean strict) { 168 if (index >= 0 && index < maxDenseLength) { 169 final long oldLength = underlying.length(); 170 ensure(index); 171 underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict); 172 setLength(Math.max(underlying.length(), length())); 173 } else { 174 final Long longIndex = indexToKey(index); 175 sparseMap.put(longIndex, value); 176 setLength(Math.max(longIndex + 1, length())); 177 } 178 179 return this; 180 } 181 182 @Override 183 public ArrayData set(final int index, final int value, final boolean strict) { 184 if (index >= 0 && index < maxDenseLength) { 185 final long oldLength = underlying.length(); 186 ensure(index); 187 underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict); 188 setLength(Math.max(underlying.length(), length())); 189 } else { 190 final Long longIndex = indexToKey(index); 191 sparseMap.put(longIndex, value); 192 setLength(Math.max(longIndex + 1, length())); 193 } 194 return this; 195 } 196 197 @Override 198 public ArrayData set(final int index, final double value, final boolean strict) { 199 if (index >= 0 && index < maxDenseLength) { 200 final long oldLength = underlying.length(); 201 ensure(index); 202 underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict); 203 setLength(Math.max(underlying.length(), length())); 204 } else { 205 final Long longIndex = indexToKey(index); 206 sparseMap.put(longIndex, value); 207 setLength(Math.max(longIndex + 1, length())); 208 } 209 return this; 210 } 211 212 @Override 213 public ArrayData setEmpty(final int index) { 214 underlying.setEmpty(index); 215 return this; 216 } 217 218 @Override 219 public ArrayData setEmpty(final long lo, final long hi) { 220 underlying.setEmpty(lo, hi); 221 return this; 222 } | 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package jdk.nashorn.internal.runtime.arrays; 27 28 import java.util.Arrays; 29 import java.util.Map; 30 import java.util.TreeMap; 31 import jdk.nashorn.internal.codegen.types.Type; 32 import jdk.nashorn.internal.runtime.JSType; 33 import jdk.nashorn.internal.runtime.ScriptRuntime; 34 35 /** 36 * Handle arrays where the index is very large. 37 */ 38 class SparseArrayData extends ArrayData { 39 /** Maximum size for dense arrays */ 40 static final int MAX_DENSE_LENGTH = 1024 * 1024; 41 42 /** Underlying array. */ 43 private ArrayData underlying; 44 45 /** Maximum length to be stored in the array. */ 46 private final long maxDenseLength; 47 48 /** Sparse elements. */ 49 private TreeMap<Long, Object> sparseMap; 50 51 SparseArrayData(final ArrayData underlying, final long length) { 52 this(underlying, length, new TreeMap<Long, Object>()); 53 } 54 55 private SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) { 56 super(length); 57 assert underlying.length() <= length; 58 this.underlying = underlying; 59 this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length()); 60 this.sparseMap = sparseMap; 61 } 62 63 @Override 64 public ArrayData copy() { 65 return new SparseArrayData(underlying.copy(), length(), new TreeMap<>(sparseMap)); 66 } 67 68 @Override 69 public Object[] asObjectArray() { 70 final int len = (int)Math.min(length(), Integer.MAX_VALUE); 71 final int underlyingLength = (int)Math.min(len, underlying.length()); 72 final Object[] objArray = new Object[len]; 73 74 for (int i = 0; i < underlyingLength; i++) { 75 objArray[i] = underlying.getObject(i); 76 } 77 78 Arrays.fill(objArray, underlyingLength, len, ScriptRuntime.UNDEFINED); 79 80 for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 81 final long key = entry.getKey(); 82 if (key < Integer.MAX_VALUE) { 83 objArray[(int)key] = entry.getValue(); 84 } else { 85 break; // ascending key order 86 } 87 } 88 89 return objArray; 90 } 91 92 @Override 93 public ArrayData shiftLeft(final int by) { 94 underlying = underlying.shiftLeft(by); 95 96 final TreeMap<Long, Object> newSparseMap = new TreeMap<>(); 97 98 for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 99 final long newIndex = entry.getKey().longValue() - by; 100 if (newIndex >= 0) { 101 if (newIndex < maxDenseLength) { 102 final long oldLength = underlying.length(); 103 underlying = underlying.ensure(newIndex) 104 .set((int) newIndex, entry.getValue(), false) 105 .safeDelete(oldLength, newIndex - 1, false); 106 } else { 107 newSparseMap.put(Long.valueOf(newIndex), entry.getValue()); 108 } 109 } 110 } 111 112 sparseMap = newSparseMap; 113 setLength(Math.max(length() - by, 0)); 114 115 return sparseMap.isEmpty() ? underlying : this; 116 } 117 118 @Override 119 public ArrayData shiftRight(final int by) { 120 final TreeMap<Long, Object> newSparseMap = new TreeMap<>(); 121 // Move elements from underlying to sparse map if necessary 122 final long len = underlying.length(); 123 if (len + by > maxDenseLength) { 124 // Length of underlying array after shrinking, before right-shifting 125 final long tempLength = Math.max(0, maxDenseLength - by); 126 for (long i = tempLength; i < len; i++) { 127 if (underlying.has((int) i)) { 128 newSparseMap.put(Long.valueOf(i + by), underlying.getObject((int) i)); 129 } 130 } 131 underlying = underlying.shrink((int) tempLength); 132 underlying.setLength(tempLength); 133 } 134 135 underlying = underlying.shiftRight(by); 136 137 for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 138 final long newIndex = entry.getKey().longValue() + by; 139 newSparseMap.put(Long.valueOf(newIndex), entry.getValue()); 140 } 141 142 sparseMap = newSparseMap; 143 setLength(length() + by); 144 145 return this; 146 } 147 148 @Override 149 public ArrayData ensure(final long safeIndex) { 150 if (safeIndex >= length()) { 151 setLength(safeIndex + 1); 152 } 153 return this; 154 } 155 156 @Override 157 public ArrayData shrink(final long newLength) { 158 if (newLength < underlying.length()) { 159 underlying = underlying.shrink(newLength); 160 underlying.setLength(newLength); 161 sparseMap.clear(); 162 setLength(newLength); 163 } 164 165 sparseMap.subMap(Long.valueOf(newLength), Long.MAX_VALUE).clear(); 166 setLength(newLength); 167 return this; 168 } 169 170 @Override 171 public ArrayData set(final int index, final Object value, final boolean strict) { 172 if (index >= 0 && index < maxDenseLength) { 173 final long oldLength = underlying.length(); 174 underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict); 175 setLength(Math.max(underlying.length(), length())); 176 } else { 177 final Long longIndex = indexToKey(index); 178 sparseMap.put(longIndex, value); 179 setLength(Math.max(longIndex + 1, length())); 180 } 181 182 return this; 183 } 184 185 @Override 186 public ArrayData set(final int index, final int value, final boolean strict) { 187 if (index >= 0 && index < maxDenseLength) { 188 final long oldLength = underlying.length(); 189 underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict); 190 setLength(Math.max(underlying.length(), length())); 191 } else { 192 final Long longIndex = indexToKey(index); 193 sparseMap.put(longIndex, value); 194 setLength(Math.max(longIndex + 1, length())); 195 } 196 return this; 197 } 198 199 @Override 200 public ArrayData set(final int index, final double value, final boolean strict) { 201 if (index >= 0 && index < maxDenseLength) { 202 final long oldLength = underlying.length(); 203 underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict); 204 setLength(Math.max(underlying.length(), length())); 205 } else { 206 final Long longIndex = indexToKey(index); 207 sparseMap.put(longIndex, value); 208 setLength(Math.max(longIndex + 1, length())); 209 } 210 return this; 211 } 212 213 @Override 214 public ArrayData setEmpty(final int index) { 215 underlying.setEmpty(index); 216 return this; 217 } 218 219 @Override 220 public ArrayData setEmpty(final long lo, final long hi) { 221 underlying.setEmpty(lo, hi); 222 return this; 223 } |