SparseArrayData.java revision 1036:f0b5e3900a10
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 26package jdk.nashorn.internal.runtime.arrays; 27 28import java.util.Arrays; 29import java.util.Map; 30import java.util.TreeMap; 31import jdk.nashorn.internal.codegen.types.Type; 32import jdk.nashorn.internal.runtime.JSType; 33import jdk.nashorn.internal.runtime.ScriptRuntime; 34 35/** 36 * Handle arrays where the index is very large. 37 */ 38class SparseArrayData extends ArrayData { 39 static final long MAX_DENSE_LENGTH = 16 * 512 * 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 length = (int) Math.min(length(), Integer.MAX_VALUE); 70 final int underlyingLength = (int) Math.min(length, underlying.length()); 71 final Object[] objArray = new Object[length]; 72 73 for (int i = 0; i < underlyingLength; i++) { 74 objArray[i] = underlying.getObject(i); 75 } 76 77 Arrays.fill(objArray, underlyingLength, length, 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 if (underlying.length() + by > maxDenseLength) { 114 for (long i = maxDenseLength - by; i < underlying.length(); i++) { 115 if (underlying.has((int) i)) { 116 newSparseMap.put(Long.valueOf(i + by), underlying.getObject((int) i)); 117 } 118 } 119 underlying = underlying.shrink((int) (maxDenseLength - by)); 120 } 121 122 underlying.shiftRight(by); 123 124 for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 125 final long newIndex = entry.getKey().longValue() + by; 126 newSparseMap.put(Long.valueOf(newIndex), entry.getValue()); 127 } 128 129 sparseMap = newSparseMap; 130 setLength(length() + by); 131 132 return this; 133 } 134 135 @Override 136 public ArrayData ensure(final long safeIndex) { 137 if (safeIndex < maxDenseLength && underlying.length() <= safeIndex) { 138 underlying = underlying.ensure(safeIndex); 139 } 140 setLength(Math.max(safeIndex + 1, length())); 141 return this; 142 } 143 144 @Override 145 public ArrayData shrink(final long newLength) { 146 if (newLength < underlying.length()) { 147 underlying = underlying.shrink(newLength); 148 underlying.setLength(newLength); 149 sparseMap.clear(); 150 setLength(newLength); 151 } 152 153 sparseMap.subMap(Long.valueOf(newLength), Long.MAX_VALUE).clear(); 154 setLength(newLength); 155 return this; 156 } 157 158 @Override 159 public ArrayData set(final int index, final Object value, final boolean strict) { 160 if (index >= 0 && index < maxDenseLength) { 161 ensure(index); 162 underlying = underlying.set(index, value, strict); 163 setLength(Math.max(underlying.length(), length())); 164 } else { 165 final Long longIndex = indexToKey(index); 166 sparseMap.put(longIndex, value); 167 setLength(Math.max(longIndex + 1, length())); 168 } 169 170 return this; 171 } 172 173 @Override 174 public ArrayData set(final int index, final int value, final boolean strict) { 175 if (index >= 0 && index < maxDenseLength) { 176 ensure(index); 177 underlying = underlying.set(index, value, strict); 178 setLength(Math.max(underlying.length(), length())); 179 } else { 180 final Long longIndex = indexToKey(index); 181 sparseMap.put(longIndex, value); 182 setLength(Math.max(longIndex + 1, length())); 183 } 184 return this; 185 } 186 187 @Override 188 public ArrayData set(final int index, final long value, final boolean strict) { 189 if (index >= 0 && index < maxDenseLength) { 190 ensure(index); 191 underlying = underlying.set(index, value, strict); 192 setLength(Math.max(underlying.length(), length())); 193 } else { 194 final Long longIndex = indexToKey(index); 195 sparseMap.put(longIndex, value); 196 setLength(Math.max(longIndex + 1, length())); 197 } 198 return this; 199 } 200 201 @Override 202 public ArrayData set(final int index, final double value, final boolean strict) { 203 if (index >= 0 && index < maxDenseLength) { 204 ensure(index); 205 underlying = underlying.set(index, value, strict); 206 setLength(Math.max(underlying.length(), length())); 207 } else { 208 final Long longIndex = indexToKey(index); 209 sparseMap.put(longIndex, value); 210 setLength(Math.max(longIndex + 1, length())); 211 } 212 return this; 213 } 214 215 @Override 216 public ArrayData setEmpty(final int index) { 217 underlying.setEmpty(index); 218 return this; 219 } 220 221 @Override 222 public ArrayData setEmpty(final long lo, final long hi) { 223 underlying.setEmpty(lo, hi); 224 return this; 225 } 226 227 @Override 228 public Type getOptimisticType() { 229 return underlying.getOptimisticType(); 230 } 231 232 @Override 233 public int getInt(final int index) { 234 if (index >= 0 && index < maxDenseLength) { 235 return underlying.getInt(index); 236 } 237 return JSType.toInt32(sparseMap.get(indexToKey(index))); 238 } 239 240 @Override 241 public int getIntOptimistic(final int index, final int programPoint) { 242 if (index >= 0 && index < maxDenseLength) { 243 return underlying.getIntOptimistic(index, programPoint); 244 } 245 return JSType.toInt32Optimistic(sparseMap.get(indexToKey(index)), programPoint); 246 } 247 248 @Override 249 public long getLong(final int index) { 250 if (index >= 0 && index < maxDenseLength) { 251 return underlying.getLong(index); 252 } 253 return JSType.toLong(sparseMap.get(indexToKey(index))); 254 } 255 256 @Override 257 public long getLongOptimistic(final int index, final int programPoint) { 258 if (index >= 0 && index < maxDenseLength) { 259 return underlying.getLongOptimistic(index, programPoint); 260 } 261 return JSType.toLongOptimistic(sparseMap.get(indexToKey(index)), programPoint); 262 } 263 264 @Override 265 public double getDouble(final int index) { 266 if (index >= 0 && index < maxDenseLength) { 267 return underlying.getDouble(index); 268 } 269 return JSType.toNumber(sparseMap.get(indexToKey(index))); 270 } 271 272 @Override 273 public double getDoubleOptimistic(final int index, final int programPoint) { 274 if (index >= 0 && index < maxDenseLength) { 275 return underlying.getDouble(index); 276 } 277 return JSType.toNumberOptimistic(sparseMap.get(indexToKey(index)), programPoint); 278 } 279 280 @Override 281 public Object getObject(final int index) { 282 if (index >= 0 && index < maxDenseLength) { 283 return underlying.getObject(index); 284 } 285 286 final Long key = indexToKey(index); 287 if (sparseMap.containsKey(key)) { 288 return sparseMap.get(key); 289 } 290 291 return ScriptRuntime.UNDEFINED; 292 } 293 294 @Override 295 public boolean has(final int index) { 296 if (index >= 0 && index < maxDenseLength) { 297 return index < underlying.length() && underlying.has(index); 298 } 299 300 return sparseMap.containsKey(indexToKey(index)); 301 } 302 303 @Override 304 public ArrayData delete(final int index) { 305 if (index >= 0 && index < maxDenseLength) { 306 if (index < underlying.length()) { 307 underlying = underlying.delete(index); 308 } 309 } else { 310 sparseMap.remove(indexToKey(index)); 311 } 312 313 return this; 314 } 315 316 @Override 317 public ArrayData delete(final long fromIndex, final long toIndex) { 318 if (fromIndex < maxDenseLength && fromIndex < underlying.length()) { 319 underlying = underlying.delete(fromIndex, Math.min(toIndex, underlying.length() - 1)); 320 } 321 if (toIndex >= maxDenseLength) { 322 sparseMap.subMap(fromIndex, true, toIndex, true).clear(); 323 } 324 return this; 325 } 326 327 private static Long indexToKey(final int index) { 328 return Long.valueOf(ArrayIndex.toLongIndex(index)); 329 } 330 331 @Override 332 public ArrayData convert(final Class<?> type) { 333 underlying = underlying.convert(type); 334 return this; 335 } 336 337 @Override 338 public Object pop() { 339 if (length() == 0) { 340 return ScriptRuntime.UNDEFINED; 341 } 342 if (length() == underlying.length()) { 343 final Object result = underlying.pop(); 344 setLength(underlying.length()); 345 return result; 346 } 347 setLength(length() - 1); 348 final Long key = Long.valueOf(length()); 349 return sparseMap.containsKey(key) ? sparseMap.remove(key) : ScriptRuntime.UNDEFINED; 350 } 351 352 @Override 353 public ArrayData slice(final long from, final long to) { 354 assert to <= length(); 355 final long start = from < 0 ? (from + length()) : from; 356 final long newLength = to - start; 357 358 if (start >= 0 && to <= maxDenseLength) { 359 if (newLength <= underlying.length()) { 360 return underlying.slice(from, to); 361 } 362 return underlying.slice(from, to).ensure(newLength - 1).delete(underlying.length(), newLength); 363 } 364 365 ArrayData sliced = EMPTY_ARRAY; 366 sliced = sliced.ensure(newLength - 1); 367 for (long i = start; i < to; i = nextIndex(i)) { 368 if (has((int)i)) { 369 sliced = sliced.set((int)(i - start), getObject((int)i), false); 370 } 371 } 372 assert sliced.length() == newLength; 373 return sliced; 374 } 375 376 @Override 377 public long nextIndex(final long index) { 378 if (index < underlying.length() - 1) { 379 return underlying.nextIndex(index); 380 } 381 382 final Long nextKey = sparseMap.higherKey(index); 383 if (nextKey != null) { 384 return nextKey; 385 } 386 return length(); 387 } 388} 389