SparseArrayData.java revision 1844:9c7526916609
1239275Sgonzo/* 2239275Sgonzo * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved. 3239275Sgonzo * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4239275Sgonzo * 5239275Sgonzo * This code is free software; you can redistribute it and/or modify it 6239275Sgonzo * under the terms of the GNU General Public License version 2 only, as 7239275Sgonzo * published by the Free Software Foundation. Oracle designates this 8239275Sgonzo * particular file as subject to the "Classpath" exception as provided 9239275Sgonzo * by Oracle in the LICENSE file that accompanied this code. 10239275Sgonzo * 11239275Sgonzo * This code is distributed in the hope that it will be useful, but WITHOUT 12239275Sgonzo * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13239275Sgonzo * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14239275Sgonzo * version 2 for more details (a copy is included in the LICENSE file that 15239275Sgonzo * accompanied this code). 16239275Sgonzo * 17239275Sgonzo * You should have received a copy of the GNU General Public License version 18239275Sgonzo * 2 along with this work; if not, write to the Free Software Foundation, 19239275Sgonzo * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20239275Sgonzo * 21239275Sgonzo * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22239275Sgonzo * or visit www.oracle.com if you need additional information or have any 23239275Sgonzo * questions. 24239275Sgonzo */ 25239275Sgonzo 26239275Sgonzopackage jdk.nashorn.internal.runtime.arrays; 27239275Sgonzo 28239275Sgonzoimport java.util.Arrays; 29239275Sgonzoimport java.util.Map; 30239275Sgonzoimport java.util.TreeMap; 31239275Sgonzoimport jdk.nashorn.internal.codegen.types.Type; 32239275Sgonzoimport jdk.nashorn.internal.runtime.JSType; 33239275Sgonzoimport jdk.nashorn.internal.runtime.ScriptRuntime; 34239275Sgonzo 35239275Sgonzo/** 36239275Sgonzo * Handle arrays where the index is very large. 37239275Sgonzo */ 38239275Sgonzoclass SparseArrayData extends ArrayData { 39239275Sgonzo /** Maximum size for dense arrays */ 40239275Sgonzo static final int MAX_DENSE_LENGTH = 1024 * 1024; 41239275Sgonzo 42239275Sgonzo /** Underlying array. */ 43239275Sgonzo private ArrayData underlying; 44239275Sgonzo 45239275Sgonzo /** Maximum length to be stored in the array. */ 46239275Sgonzo private final long maxDenseLength; 47239275Sgonzo 48239275Sgonzo /** Sparse elements. */ 49239275Sgonzo private TreeMap<Long, Object> sparseMap; 50239275Sgonzo 51239275Sgonzo SparseArrayData(final ArrayData underlying, final long length) { 52239275Sgonzo this(underlying, length, new TreeMap<>()); 53239275Sgonzo } 54239275Sgonzo 55239275Sgonzo private SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) { 56239275Sgonzo super(length); 57239275Sgonzo assert underlying.length() <= length; 58239275Sgonzo this.underlying = underlying; 59239275Sgonzo this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length()); 60239275Sgonzo this.sparseMap = sparseMap; 61239275Sgonzo } 62239275Sgonzo 63239275Sgonzo @Override 64239275Sgonzo public ArrayData copy() { 65239275Sgonzo return new SparseArrayData(underlying.copy(), length(), new TreeMap<>(sparseMap)); 66239275Sgonzo } 67239275Sgonzo 68239275Sgonzo @Override 69239275Sgonzo public Object[] asObjectArray() { 70239275Sgonzo final int len = (int)Math.min(length(), Integer.MAX_VALUE); 71239275Sgonzo final int underlyingLength = (int)Math.min(len, underlying.length()); 72239275Sgonzo final Object[] objArray = new Object[len]; 73239275Sgonzo 74239275Sgonzo for (int i = 0; i < underlyingLength; i++) { 75239275Sgonzo objArray[i] = underlying.getObject(i); 76239275Sgonzo } 77239275Sgonzo 78239275Sgonzo Arrays.fill(objArray, underlyingLength, len, ScriptRuntime.UNDEFINED); 79239275Sgonzo 80239275Sgonzo for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 81239275Sgonzo final long key = entry.getKey(); 82239275Sgonzo if (key < Integer.MAX_VALUE) { 83239275Sgonzo objArray[(int)key] = entry.getValue(); 84239275Sgonzo } else { 85239275Sgonzo break; // ascending key order 86239275Sgonzo } 87239275Sgonzo } 88239275Sgonzo 89239275Sgonzo return objArray; 90239275Sgonzo } 91239275Sgonzo 92239275Sgonzo @Override 93239275Sgonzo public ArrayData shiftLeft(final int by) { 94239275Sgonzo underlying = underlying.shiftLeft(by); 95239275Sgonzo 96239275Sgonzo final TreeMap<Long, Object> newSparseMap = new TreeMap<>(); 97239275Sgonzo 98239275Sgonzo for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 99239275Sgonzo final long newIndex = entry.getKey() - by; 100239275Sgonzo if (newIndex >= 0) { 101239275Sgonzo if (newIndex < maxDenseLength) { 102239275Sgonzo final long oldLength = underlying.length(); 103239275Sgonzo underlying = underlying.ensure(newIndex) 104239275Sgonzo .set((int) newIndex, entry.getValue(), false) 105239275Sgonzo .safeDelete(oldLength, newIndex - 1, false); 106239275Sgonzo } else { 107239275Sgonzo newSparseMap.put(newIndex, entry.getValue()); 108239275Sgonzo } 109239275Sgonzo } 110239275Sgonzo } 111239275Sgonzo 112239275Sgonzo sparseMap = newSparseMap; 113239275Sgonzo setLength(Math.max(length() - by, 0)); 114239275Sgonzo 115239275Sgonzo return sparseMap.isEmpty() ? underlying : this; 116239275Sgonzo } 117239275Sgonzo 118239275Sgonzo @Override 119239275Sgonzo public ArrayData shiftRight(final int by) { 120239275Sgonzo final TreeMap<Long, Object> newSparseMap = new TreeMap<>(); 121239275Sgonzo // Move elements from underlying to sparse map if necessary 122239275Sgonzo final long len = underlying.length(); 123239275Sgonzo if (len + by > maxDenseLength) { 124239275Sgonzo // Length of underlying array after shrinking, before right-shifting 125239275Sgonzo final long tempLength = Math.max(0, maxDenseLength - by); 126239275Sgonzo for (long i = tempLength; i < len; i++) { 127239275Sgonzo if (underlying.has((int) i)) { 128239275Sgonzo newSparseMap.put(i + by, underlying.getObject((int) i)); 129239275Sgonzo } 130239275Sgonzo } 131239275Sgonzo underlying = underlying.shrink((int) tempLength); 132239275Sgonzo underlying.setLength(tempLength); 133239275Sgonzo } 134239275Sgonzo 135239275Sgonzo underlying = underlying.shiftRight(by); 136239275Sgonzo 137239275Sgonzo for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 138239275Sgonzo final long newIndex = entry.getKey() + by; 139239275Sgonzo newSparseMap.put(newIndex, entry.getValue()); 140239275Sgonzo } 141239275Sgonzo 142239275Sgonzo sparseMap = newSparseMap; 143239275Sgonzo setLength(length() + by); 144239275Sgonzo 145239275Sgonzo return this; 146239275Sgonzo } 147239275Sgonzo 148239275Sgonzo @Override 149239275Sgonzo public ArrayData ensure(final long safeIndex) { 150239275Sgonzo if (safeIndex >= length()) { 151239275Sgonzo setLength(safeIndex + 1); 152239275Sgonzo } 153239275Sgonzo return this; 154239275Sgonzo } 155239275Sgonzo 156239275Sgonzo @Override 157239275Sgonzo public ArrayData shrink(final long newLength) { 158239275Sgonzo if (newLength < underlying.length()) { 159239275Sgonzo underlying = underlying.shrink(newLength); 160239275Sgonzo underlying.setLength(newLength); 161239275Sgonzo sparseMap.clear(); 162239275Sgonzo setLength(newLength); 163239275Sgonzo } 164239275Sgonzo 165239275Sgonzo sparseMap.subMap(newLength, Long.MAX_VALUE).clear(); 166239275Sgonzo setLength(newLength); 167239275Sgonzo return this; 168239275Sgonzo } 169239275Sgonzo 170239275Sgonzo @Override 171239275Sgonzo public ArrayData set(final int index, final Object value, final boolean strict) { 172239275Sgonzo if (index >= 0 && index < maxDenseLength) { 173239275Sgonzo final long oldLength = underlying.length(); 174239275Sgonzo underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict); 175239275Sgonzo setLength(Math.max(underlying.length(), length())); 176239275Sgonzo } else { 177239275Sgonzo final Long longIndex = indexToKey(index); 178239275Sgonzo sparseMap.put(longIndex, value); 179239275Sgonzo setLength(Math.max(longIndex + 1, length())); 180239275Sgonzo } 181239275Sgonzo 182239275Sgonzo return this; 183239275Sgonzo } 184239275Sgonzo 185239275Sgonzo @Override 186239275Sgonzo public ArrayData set(final int index, final int value, final boolean strict) { 187239275Sgonzo if (index >= 0 && index < maxDenseLength) { 188239275Sgonzo final long oldLength = underlying.length(); 189239275Sgonzo underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict); 190239275Sgonzo setLength(Math.max(underlying.length(), length())); 191239275Sgonzo } else { 192239275Sgonzo final Long longIndex = indexToKey(index); 193239275Sgonzo sparseMap.put(longIndex, value); 194239275Sgonzo setLength(Math.max(longIndex + 1, length())); 195239275Sgonzo } 196239275Sgonzo return this; 197239275Sgonzo } 198239275Sgonzo 199239275Sgonzo @Override 200239275Sgonzo public ArrayData set(final int index, final double value, final boolean strict) { 201239275Sgonzo if (index >= 0 && index < maxDenseLength) { 202239275Sgonzo final long oldLength = underlying.length(); 203239275Sgonzo underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict); 204239275Sgonzo setLength(Math.max(underlying.length(), length())); 205239275Sgonzo } else { 206239275Sgonzo final Long longIndex = indexToKey(index); 207239275Sgonzo sparseMap.put(longIndex, value); 208239275Sgonzo setLength(Math.max(longIndex + 1, length())); 209239275Sgonzo } 210239275Sgonzo return this; 211239275Sgonzo } 212239275Sgonzo 213239275Sgonzo @Override 214239275Sgonzo public ArrayData setEmpty(final int index) { 215239275Sgonzo underlying.setEmpty(index); 216239275Sgonzo return this; 217239275Sgonzo } 218239275Sgonzo 219239275Sgonzo @Override 220239275Sgonzo public ArrayData setEmpty(final long lo, final long hi) { 221239275Sgonzo underlying.setEmpty(lo, hi); 222239275Sgonzo return this; 223239275Sgonzo } 224239275Sgonzo 225239275Sgonzo @Override 226239275Sgonzo public Type getOptimisticType() { 227239275Sgonzo return underlying.getOptimisticType(); 228239275Sgonzo } 229239275Sgonzo 230239275Sgonzo @Override 231239275Sgonzo public int getInt(final int index) { 232239275Sgonzo if (index >= 0 && index < maxDenseLength) { 233239275Sgonzo return underlying.getInt(index); 234239275Sgonzo } 235239275Sgonzo 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} 376