1 /*
2 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
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<>());
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() - by;
99 if (newIndex < maxDenseLength) {
100 underlying = underlying.set((int) newIndex, entry.getValue(), false);
101 } else if (newIndex >= 0) {
102 newSparseMap.put(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(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() + by;
127 newSparseMap.put(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(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 long 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 set(final int index, final double value, final boolean strict) {
214 if (index >= 0 && index < maxDenseLength) {
215 final long oldLength = underlying.length();
216 ensure(index);
217 underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
218 setLength(Math.max(underlying.length(), length()));
219 } else {
220 final Long longIndex = indexToKey(index);
221 sparseMap.put(longIndex, value);
222 setLength(Math.max(longIndex + 1, length()));
223 }
224 return this;
225 }
226
227 @Override
228 public ArrayData setEmpty(final int index) {
229 underlying.setEmpty(index);
230 return this;
231 }
232
233 @Override
234 public ArrayData setEmpty(final long lo, final long hi) {
235 underlying.setEmpty(lo, hi);
236 return this;
237 }
238
239 @Override
240 public Type getOptimisticType() {
241 return underlying.getOptimisticType();
242 }
243
244 @Override
245 public int getInt(final int index) {
246 if (index >= 0 && index < maxDenseLength) {
247 return underlying.getInt(index);
248 }
249 return JSType.toInt32(sparseMap.get(indexToKey(index)));
250 }
251
252 @Override
253 public int getIntOptimistic(final int index, final int programPoint) {
254 if (index >= 0 && index < maxDenseLength) {
255 return underlying.getIntOptimistic(index, programPoint);
256 }
257 return JSType.toInt32Optimistic(sparseMap.get(indexToKey(index)), programPoint);
258 }
259
260 @Override
261 public long getLong(final int index) {
262 if (index >= 0 && index < maxDenseLength) {
263 return underlying.getLong(index);
264 }
265 return JSType.toLong(sparseMap.get(indexToKey(index)));
266 }
267
268 @Override
269 public long getLongOptimistic(final int index, final int programPoint) {
270 if (index >= 0 && index < maxDenseLength) {
271 return underlying.getLongOptimistic(index, programPoint);
272 }
273 return JSType.toLongOptimistic(sparseMap.get(indexToKey(index)), programPoint);
274 }
275
276 @Override
277 public double getDouble(final int index) {
278 if (index >= 0 && index < maxDenseLength) {
279 return underlying.getDouble(index);
280 }
281 return JSType.toNumber(sparseMap.get(indexToKey(index)));
282 }
283
284 @Override
285 public double getDoubleOptimistic(final int index, final int programPoint) {
286 if (index >= 0 && index < maxDenseLength) {
287 return underlying.getDouble(index);
288 }
289 return JSType.toNumberOptimistic(sparseMap.get(indexToKey(index)), programPoint);
290 }
291
292 @Override
293 public Object getObject(final int index) {
294 if (index >= 0 && index < maxDenseLength) {
295 return underlying.getObject(index);
296 }
297
298 final Long key = indexToKey(index);
299 if (sparseMap.containsKey(key)) {
300 return sparseMap.get(key);
301 }
302
303 return ScriptRuntime.UNDEFINED;
304 }
305
306 @Override
307 public boolean has(final int index) {
308 if (index >= 0 && index < maxDenseLength) {
309 return index < underlying.length() && underlying.has(index);
310 }
311
312 return sparseMap.containsKey(indexToKey(index));
313 }
314
315 @Override
316 public ArrayData delete(final int index) {
317 if (index >= 0 && index < maxDenseLength) {
318 if (index < underlying.length()) {
319 underlying = underlying.delete(index);
320 }
321 } else {
322 sparseMap.remove(indexToKey(index));
323 }
324
325 return this;
326 }
327
328 @Override
329 public ArrayData delete(final long fromIndex, final long toIndex) {
330 if (fromIndex < maxDenseLength && fromIndex < underlying.length()) {
331 underlying = underlying.delete(fromIndex, Math.min(toIndex, underlying.length() - 1));
332 }
333 if (toIndex >= maxDenseLength) {
334 sparseMap.subMap(fromIndex, true, toIndex, true).clear();
335 }
336 return this;
337 }
338
339 private static Long indexToKey(final int index) {
340 return ArrayIndex.toLongIndex(index);
341 }
342
343 @Override
344 public ArrayData convert(final Class<?> type) {
345 underlying = underlying.convert(type);
346 return this;
347 }
348
349 @Override
350 public Object pop() {
351 final long len = length();
352 final long underlyingLen = underlying.length();
353 if (len == 0) {
354 return ScriptRuntime.UNDEFINED;
355 }
356 if (len == underlyingLen) {
357 final Object result = underlying.pop();
358 setLength(underlying.length());
359 return result;
360 }
361 setLength(len - 1);
362 final Long key = len - 1;
363 return sparseMap.containsKey(key) ? sparseMap.remove(key) : ScriptRuntime.UNDEFINED;
364 }
365
366 @Override
367 public ArrayData slice(final long from, final long to) {
368 assert to <= length();
369 final long start = from < 0 ? (from + length()) : from;
370 final long newLength = to - start;
371
372 final long underlyingLength = underlying.length();
373
374 if (start >= 0 && to <= maxDenseLength) {
375 if (newLength <= underlyingLength) {
376 return underlying.slice(from, to);
377 }
378 return underlying.slice(from, to).ensure(newLength - 1).delete(underlyingLength, newLength);
379 }
380
381 ArrayData sliced = EMPTY_ARRAY;
382 sliced = sliced.ensure(newLength - 1);
383 for (long i = start; i < to; i = nextIndex(i)) {
384 if (has((int)i)) {
385 sliced = sliced.set((int)(i - start), getObject((int)i), false);
386 }
387 }
388 assert sliced.length() == newLength;
389 return sliced;
390 }
391
392 @Override
393 public long nextIndex(final long index) {
394 if (index < underlying.length() - 1) {
395 return underlying.nextIndex(index);
396 }
397
398 final Long nextKey = sparseMap.higherKey(index);
399 if (nextKey != null) {
400 return nextKey;
401 }
402
403 return length();
404 }
405 }