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