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 /** Maximum size for dense arrays */
40 static final int MAX_DENSE_LENGTH = 128 * 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<>());
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 = 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() - 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(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(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() + by;
139 newSparseMap.put(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(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 }
224
225 @Override
226 public Type getOptimisticType() {
227 return underlying.getOptimisticType();
228 }
229
230 @Override
231 public int getInt(final int index) {
232 if (index >= 0 && index < maxDenseLength) {
233 return underlying.getInt(index);
234 }
235 return JSType.toInt32(sparseMap.get(indexToKey(index)));
236 }
237
238 @Override
239 public int getIntOptimistic(final int index, final int programPoint) {
240 if (index >= 0 && index < maxDenseLength) {
241 return underlying.getIntOptimistic(index, programPoint);
242 }
243 return JSType.toInt32Optimistic(sparseMap.get(indexToKey(index)), programPoint);
244 }
245
246 @Override
247 public double getDouble(final int index) {
248 if (index >= 0 && index < maxDenseLength) {
249 return underlying.getDouble(index);
250 }
251 return JSType.toNumber(sparseMap.get(indexToKey(index)));
252 }
253
254 @Override
255 public double getDoubleOptimistic(final int index, final int programPoint) {
256 if (index >= 0 && index < maxDenseLength) {
257 return underlying.getDouble(index);
258 }
259 return JSType.toNumberOptimistic(sparseMap.get(indexToKey(index)), programPoint);
260 }
261
262 @Override
263 public Object getObject(final int index) {
264 if (index >= 0 && index < maxDenseLength) {
265 return underlying.getObject(index);
266 }
267
268 final Long key = indexToKey(index);
269 if (sparseMap.containsKey(key)) {
270 return sparseMap.get(key);
271 }
272
273 return ScriptRuntime.UNDEFINED;
274 }
275
276 @Override
277 public boolean has(final int index) {
278 if (index >= 0 && index < maxDenseLength) {
279 return index < underlying.length() && underlying.has(index);
280 }
281
282 return sparseMap.containsKey(indexToKey(index));
283 }
284
285 @Override
286 public ArrayData delete(final int index) {
287 if (index >= 0 && index < maxDenseLength) {
288 if (index < underlying.length()) {
289 underlying = underlying.delete(index);
290 }
291 } else {
292 sparseMap.remove(indexToKey(index));
293 }
294
295 return this;
296 }
297
298 @Override
299 public ArrayData delete(final long fromIndex, final long toIndex) {
300 if (fromIndex < maxDenseLength && fromIndex < underlying.length()) {
301 underlying = underlying.delete(fromIndex, Math.min(toIndex, underlying.length() - 1));
302 }
303 if (toIndex >= maxDenseLength) {
304 sparseMap.subMap(fromIndex, true, toIndex, true).clear();
305 }
306 return this;
307 }
308
309 private static Long indexToKey(final int index) {
310 return ArrayIndex.toLongIndex(index);
311 }
312
313 @Override
314 public ArrayData convert(final Class<?> type) {
315 underlying = underlying.convert(type);
316 return this;
317 }
318
319 @Override
320 public Object pop() {
321 final long len = length();
322 final long underlyingLen = underlying.length();
323 if (len == 0) {
324 return ScriptRuntime.UNDEFINED;
325 }
326 if (len == underlyingLen) {
327 final Object result = underlying.pop();
328 setLength(underlying.length());
329 return result;
330 }
331 setLength(len - 1);
332 final Long key = len - 1;
333 return sparseMap.containsKey(key) ? sparseMap.remove(key) : ScriptRuntime.UNDEFINED;
334 }
335
336 @Override
337 public ArrayData slice(final long from, final long to) {
338 assert to <= length();
339 final long start = from < 0 ? (from + length()) : from;
340 final long newLength = to - start;
341
342 final long underlyingLength = underlying.length();
343
344 if (start >= 0 && to <= maxDenseLength) {
345 if (newLength <= underlyingLength) {
346 return underlying.slice(from, to);
347 }
348 return underlying.slice(from, to).ensure(newLength - 1).delete(underlyingLength, newLength);
349 }
350
351 ArrayData sliced = EMPTY_ARRAY;
352 sliced = sliced.ensure(newLength - 1);
353 for (long i = start; i < to; i = nextIndex(i)) {
354 if (has((int)i)) {
355 sliced = sliced.set((int)(i - start), getObject((int)i), false);
356 }
357 }
358 assert sliced.length() == newLength;
359 return sliced;
360 }
361
362 @Override
363 public long nextIndex(final long index) {
364 if (index < underlying.length() - 1) {
365 return underlying.nextIndex(index);
366 }
367
368 final Long nextKey = sparseMap.higherKey(index);
369 if (nextKey != null) {
370 return nextKey;
371 }
372
373 return length();
374 }
375 }