SparseArrayData.java revision 1179:2b9af466a49d
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 int MAX_DENSE_LENGTH = 8 * 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 ensure(index); 170 underlying = underlying.set(index, value, strict); 171 setLength(Math.max(underlying.length(), length())); 172 } else { 173 final Long longIndex = indexToKey(index); 174 sparseMap.put(longIndex, value); 175 setLength(Math.max(longIndex + 1, length())); 176 } 177 178 return this; 179 } 180 181 @Override 182 public ArrayData set(final int index, final int value, final boolean strict) { 183 if (index >= 0 && index < maxDenseLength) { 184 ensure(index); 185 underlying = underlying.set(index, value, strict); 186 setLength(Math.max(underlying.length(), length())); 187 } else { 188 final Long longIndex = indexToKey(index); 189 sparseMap.put(longIndex, value); 190 setLength(Math.max(longIndex + 1, length())); 191 } 192 return this; 193 } 194 195 @Override 196 public ArrayData set(final int index, final long value, final boolean strict) { 197 if (index >= 0 && index < maxDenseLength) { 198 ensure(index); 199 underlying = underlying.set(index, value, strict); 200 setLength(Math.max(underlying.length(), length())); 201 } else { 202 final Long longIndex = indexToKey(index); 203 sparseMap.put(longIndex, value); 204 setLength(Math.max(longIndex + 1, length())); 205 } 206 return this; 207 } 208 209 @Override 210 public ArrayData set(final int index, final double value, final boolean strict) { 211 if (index >= 0 && index < maxDenseLength) { 212 ensure(index); 213 underlying = underlying.set(index, value, strict); 214 setLength(Math.max(underlying.length(), length())); 215 } else { 216 final Long longIndex = indexToKey(index); 217 sparseMap.put(longIndex, value); 218 setLength(Math.max(longIndex + 1, length())); 219 } 220 return this; 221 } 222 223 @Override 224 public ArrayData setEmpty(final int index) { 225 underlying.setEmpty(index); 226 return this; 227 } 228 229 @Override 230 public ArrayData setEmpty(final long lo, final long hi) { 231 underlying.setEmpty(lo, hi); 232 return this; 233 } 234 235 @Override 236 public Type getOptimisticType() { 237 return underlying.getOptimisticType(); 238 } 239 240 @Override 241 public int getInt(final int index) { 242 if (index >= 0 && index < maxDenseLength) { 243 return underlying.getInt(index); 244 } 245 return JSType.toInt32(sparseMap.get(indexToKey(index))); 246 } 247 248 @Override 249 public int getIntOptimistic(final int index, final int programPoint) { 250 if (index >= 0 && index < maxDenseLength) { 251 return underlying.getIntOptimistic(index, programPoint); 252 } 253 return JSType.toInt32Optimistic(sparseMap.get(indexToKey(index)), programPoint); 254 } 255 256 @Override 257 public long getLong(final int index) { 258 if (index >= 0 && index < maxDenseLength) { 259 return underlying.getLong(index); 260 } 261 return JSType.toLong(sparseMap.get(indexToKey(index))); 262 } 263 264 @Override 265 public long getLongOptimistic(final int index, final int programPoint) { 266 if (index >= 0 && index < maxDenseLength) { 267 return underlying.getLongOptimistic(index, programPoint); 268 } 269 return JSType.toLongOptimistic(sparseMap.get(indexToKey(index)), programPoint); 270 } 271 272 @Override 273 public double getDouble(final int index) { 274 if (index >= 0 && index < maxDenseLength) { 275 return underlying.getDouble(index); 276 } 277 return JSType.toNumber(sparseMap.get(indexToKey(index))); 278 } 279 280 @Override 281 public double getDoubleOptimistic(final int index, final int programPoint) { 282 if (index >= 0 && index < maxDenseLength) { 283 return underlying.getDouble(index); 284 } 285 return JSType.toNumberOptimistic(sparseMap.get(indexToKey(index)), programPoint); 286 } 287 288 @Override 289 public Object getObject(final int index) { 290 if (index >= 0 && index < maxDenseLength) { 291 return underlying.getObject(index); 292 } 293 294 final Long key = indexToKey(index); 295 if (sparseMap.containsKey(key)) { 296 return sparseMap.get(key); 297 } 298 299 return ScriptRuntime.UNDEFINED; 300 } 301 302 @Override 303 public boolean has(final int index) { 304 if (index >= 0 && index < maxDenseLength) { 305 return index < underlying.length() && underlying.has(index); 306 } 307 308 return sparseMap.containsKey(indexToKey(index)); 309 } 310 311 @Override 312 public ArrayData delete(final int index) { 313 if (index >= 0 && index < maxDenseLength) { 314 if (index < underlying.length()) { 315 underlying = underlying.delete(index); 316 } 317 } else { 318 sparseMap.remove(indexToKey(index)); 319 } 320 321 return this; 322 } 323 324 @Override 325 public ArrayData delete(final long fromIndex, final long toIndex) { 326 if (fromIndex < maxDenseLength && fromIndex < underlying.length()) { 327 underlying = underlying.delete(fromIndex, Math.min(toIndex, underlying.length() - 1)); 328 } 329 if (toIndex >= maxDenseLength) { 330 sparseMap.subMap(fromIndex, true, toIndex, true).clear(); 331 } 332 return this; 333 } 334 335 private static Long indexToKey(final int index) { 336 return Long.valueOf(ArrayIndex.toLongIndex(index)); 337 } 338 339 @Override 340 public ArrayData convert(final Class<?> type) { 341 underlying = underlying.convert(type); 342 return this; 343 } 344 345 @Override 346 public Object pop() { 347 final long len = length(); 348 final long underlyingLen = underlying.length(); 349 if (len == 0) { 350 return ScriptRuntime.UNDEFINED; 351 } 352 if (len == underlyingLen) { 353 final Object result = underlying.pop(); 354 setLength(underlying.length()); 355 return result; 356 } 357 setLength(len - 1); 358 final Long key = Long.valueOf(len - 1); 359 return sparseMap.containsKey(key) ? sparseMap.remove(key) : ScriptRuntime.UNDEFINED; 360 } 361 362 @Override 363 public ArrayData slice(final long from, final long to) { 364 assert to <= length(); 365 final long start = from < 0 ? (from + length()) : from; 366 final long newLength = to - start; 367 368 final long underlyingLength = underlying.length(); 369 370 if (start >= 0 && to <= maxDenseLength) { 371 if (newLength <= underlyingLength) { 372 return underlying.slice(from, to); 373 } 374 return underlying.slice(from, to).ensure(newLength - 1).delete(underlyingLength, newLength); 375 } 376 377 ArrayData sliced = EMPTY_ARRAY; 378 sliced = sliced.ensure(newLength - 1); 379 for (long i = start; i < to; i = nextIndex(i)) { 380 if (has((int)i)) { 381 sliced = sliced.set((int)(i - start), getObject((int)i), false); 382 } 383 } 384 assert sliced.length() == newLength; 385 return sliced; 386 } 387 388 @Override 389 public long nextIndex(final long index) { 390 if (index < underlying.length() - 1) { 391 return underlying.nextIndex(index); 392 } 393 394 final Long nextKey = sparseMap.higherKey(index); 395 if (nextKey != null) { 396 return nextKey; 397 } 398 399 return length(); 400 } 401} 402