SparseArrayData.java revision 1350:3cb11f4d617e
138774Snsouch/* 238774Snsouch * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved. 338774Snsouch * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 438774Snsouch * 538774Snsouch * This code is free software; you can redistribute it and/or modify it 638774Snsouch * under the terms of the GNU General Public License version 2 only, as 738774Snsouch * published by the Free Software Foundation. Oracle designates this 838774Snsouch * particular file as subject to the "Classpath" exception as provided 938774Snsouch * by Oracle in the LICENSE file that accompanied this code. 1038774Snsouch * 1138774Snsouch * This code is distributed in the hope that it will be useful, but WITHOUT 1238774Snsouch * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1338774Snsouch * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1438774Snsouch * version 2 for more details (a copy is included in the LICENSE file that 1538774Snsouch * accompanied this code). 1638774Snsouch * 1738774Snsouch * You should have received a copy of the GNU General Public License version 1838774Snsouch * 2 along with this work; if not, write to the Free Software Foundation, 1938774Snsouch * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2038774Snsouch * 2138774Snsouch * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2238774Snsouch * or visit www.oracle.com if you need additional information or have any 2338774Snsouch * questions. 2438774Snsouch */ 2538774Snsouch 26119418Sobrienpackage jdk.nashorn.internal.runtime.arrays; 27119418Sobrien 28119418Sobrienimport java.util.Arrays; 29119418Sobrienimport java.util.Map; 3038774Snsouchimport java.util.TreeMap; 3138774Snsouchimport jdk.nashorn.internal.codegen.types.Type; 32181304Sjhbimport jdk.nashorn.internal.runtime.JSType; 33167855Simpimport jdk.nashorn.internal.runtime.ScriptRuntime; 3438774Snsouch 35181304Sjhb/** 3638774Snsouch * Handle arrays where the index is very large. 3738774Snsouch */ 3838774Snsouchclass SparseArrayData extends ArrayData { 3938774Snsouch static final int MAX_DENSE_LENGTH = 8 * 1024 * 1024; 4038774Snsouch 4138774Snsouch /** Underlying array. */ 4238774Snsouch private ArrayData underlying; 4338774Snsouch 4438774Snsouch /** Maximum length to be stored in the array. */ 4538774Snsouch private final long maxDenseLength; 4638774Snsouch 4738774Snsouch /** Sparse elements. */ 4838774Snsouch private TreeMap<Long, Object> sparseMap; 4938774Snsouch 5038774Snsouch SparseArrayData(final ArrayData underlying, final long length) { 5138774Snsouch this(underlying, length, new TreeMap<Long, Object>()); 5238774Snsouch } 5338774Snsouch 5438774Snsouch SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) { 5538774Snsouch super(length); 5638774Snsouch assert underlying.length() <= length; 5740782Snsouch this.underlying = underlying; 5840782Snsouch this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length()); 5940782Snsouch this.sparseMap = sparseMap; 6040782Snsouch } 6140782Snsouch 62181304Sjhb @Override 6340782Snsouch public ArrayData copy() { 64181304Sjhb return new SparseArrayData(underlying.copy(), length(), new TreeMap<>(sparseMap)); 65181304Sjhb } 6640782Snsouch 6740782Snsouch @Override 68181304Sjhb public Object[] asObjectArray() { 69181304Sjhb final int len = (int)Math.min(length(), Integer.MAX_VALUE); 7040782Snsouch final int underlyingLength = (int)Math.min(len, underlying.length()); 7140782Snsouch final Object[] objArray = new Object[len]; 7240782Snsouch 7340782Snsouch for (int i = 0; i < underlyingLength; i++) { 7440782Snsouch objArray[i] = underlying.getObject(i); 7540782Snsouch } 7640782Snsouch 7740782Snsouch Arrays.fill(objArray, underlyingLength, len, ScriptRuntime.UNDEFINED); 7840782Snsouch 7940782Snsouch for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 8038774Snsouch final long key = entry.getKey(); 8138774Snsouch if (key < Integer.MAX_VALUE) { 8238774Snsouch objArray[(int)key] = entry.getValue(); 8338774Snsouch } else { 8438774Snsouch break; // ascending key order 8538774Snsouch } 8638774Snsouch } 8738774Snsouch 8838774Snsouch return objArray; 8938774Snsouch } 9038774Snsouch 91181304Sjhb @Override 9238774Snsouch public void shiftLeft(final int by) { 9340782Snsouch underlying.shiftLeft(by); 94181304Sjhb 9552776Snsouch final TreeMap<Long, Object> newSparseMap = new TreeMap<>(); 9652776Snsouch 9752776Snsouch for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 9852776Snsouch final long newIndex = entry.getKey() - by; 9952776Snsouch if (newIndex < maxDenseLength) { 10052776Snsouch underlying = underlying.set((int) newIndex, entry.getValue(), false); 10140782Snsouch } else if (newIndex >= 0) { 10238774Snsouch newSparseMap.put(newIndex, entry.getValue()); 10343976Snsouch } 10438774Snsouch } 10540782Snsouch 10638774Snsouch sparseMap = newSparseMap; 10738774Snsouch setLength(Math.max(length() - by, 0)); 10838774Snsouch } 109181304Sjhb 11038774Snsouch @Override 11138774Snsouch public ArrayData shiftRight(final int by) { 11243976Snsouch final TreeMap<Long, Object> newSparseMap = new TreeMap<>(); 11343976Snsouch final long len = underlying.length(); 11443976Snsouch if (len + by > maxDenseLength) { 11543976Snsouch for (long i = maxDenseLength - by; i < len; i++) { 11643976Snsouch if (underlying.has((int) i)) { 11738774Snsouch newSparseMap.put(i + by, underlying.getObject((int) i)); 118181304Sjhb } 11938774Snsouch } 12038774Snsouch underlying = underlying.shrink((int) (maxDenseLength - by)); 12138774Snsouch } 12238774Snsouch 12338774Snsouch underlying.shiftRight(by); 12438774Snsouch 12538774Snsouch for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) { 12638774Snsouch final long newIndex = entry.getKey() + by; 12738774Snsouch newSparseMap.put(newIndex, entry.getValue()); 12838774Snsouch } 12938774Snsouch 13038774Snsouch sparseMap = newSparseMap; 13138774Snsouch setLength(length() + by); 132181304Sjhb 13338774Snsouch return this; 13440782Snsouch } 13540782Snsouch 13640782Snsouch @Override 13740782Snsouch public ArrayData ensure(final long safeIndex) { 13840782Snsouch // Usually #ensure only needs to be called if safeIndex is greater or equal current length. 13940782Snsouch // SparseArrayData is an exception as an index smaller than our current length may still 140181304Sjhb // exceed the underlying ArrayData's capacity. Because of this, SparseArrayData invokes 141181304Sjhb // its ensure method internally in various places where other ArrayData subclasses don't, 14238774Snsouch // making it safe for outside uses to only call ensure(safeIndex) if safeIndex >= length. 143181304Sjhb if (safeIndex < maxDenseLength && underlying.length() <= safeIndex) { 14438774Snsouch underlying = underlying.ensure(safeIndex); 14538774Snsouch } 14638774Snsouch if (safeIndex >= length()) { 147181304Sjhb setLength(safeIndex + 1); 14838774Snsouch } 14938774Snsouch return this; 15038774Snsouch } 151181304Sjhb 15238774Snsouch @Override 15338774Snsouch public ArrayData shrink(final long newLength) { 15438774Snsouch if (newLength < underlying.length()) { 15538774Snsouch underlying = underlying.shrink(newLength); 15638774Snsouch underlying.setLength(newLength); 15742442Snsouch sparseMap.clear(); 15842442Snsouch setLength(newLength); 15942442Snsouch } 16042442Snsouch 16142442Snsouch sparseMap.subMap(newLength, Long.MAX_VALUE).clear(); 16242442Snsouch setLength(newLength); 16342442Snsouch return this; 16442442Snsouch } 16542442Snsouch 16642442Snsouch @Override 16742442Snsouch public ArrayData set(final int index, final Object value, final boolean strict) { 16842442Snsouch if (index >= 0 && index < maxDenseLength) { 16942442Snsouch ensure(index); 17042442Snsouch underlying = underlying.set(index, value, strict); 17142442Snsouch setLength(Math.max(underlying.length(), length())); 17242442Snsouch } else { 17342442Snsouch final Long longIndex = indexToKey(index); 17442442Snsouch sparseMap.put(longIndex, value); 17542442Snsouch setLength(Math.max(longIndex + 1, length())); 17642442Snsouch } 17742442Snsouch 17842442Snsouch return this; 17942442Snsouch } 18042442Snsouch 18142442Snsouch @Override 18242442Snsouch public ArrayData set(final int index, final int value, final boolean strict) { 18342442Snsouch if (index >= 0 && index < maxDenseLength) { 18442442Snsouch ensure(index); 18542442Snsouch underlying = underlying.set(index, value, strict); 18642442Snsouch setLength(Math.max(underlying.length(), length())); 18742442Snsouch } else { 18842442Snsouch final Long longIndex = indexToKey(index); 18942442Snsouch sparseMap.put(longIndex, value); 19042442Snsouch setLength(Math.max(longIndex + 1, length())); 19142442Snsouch } 19243347Sroger return this; 19343347Sroger } 19443347Sroger 19543347Sroger @Override 19643347Sroger public ArrayData set(final int index, final long value, final boolean strict) { 19743347Sroger if (index >= 0 && index < maxDenseLength) { 19843347Sroger ensure(index); 19943347Sroger underlying = underlying.set(index, value, strict); 20043347Sroger setLength(Math.max(underlying.length(), length())); 20143347Sroger } else { 20243347Sroger final Long longIndex = indexToKey(index); 20343347Sroger sparseMap.put(longIndex, value); 20443347Sroger setLength(Math.max(longIndex + 1, length())); 20543714Sroger } 20643347Sroger return this; 20743347Sroger } 20843347Sroger 20943347Sroger @Override 21043347Sroger public ArrayData set(final int index, final double value, final boolean strict) { 21143347Sroger if (index >= 0 && index < maxDenseLength) { 21243347Sroger ensure(index); 21343347Sroger underlying = underlying.set(index, value, strict); 21442442Snsouch setLength(Math.max(underlying.length(), length())); 21542442Snsouch } else { 21642442Snsouch final Long longIndex = indexToKey(index); 21742442Snsouch sparseMap.put(longIndex, value); 21842442Snsouch setLength(Math.max(longIndex + 1, length())); 21942442Snsouch } 22042442Snsouch return this; 22142442Snsouch } 22242442Snsouch 22342442Snsouch @Override 22442442Snsouch public ArrayData setEmpty(final int index) { 22542442Snsouch underlying.setEmpty(index); 22642442Snsouch return this; 22742442Snsouch } 22842442Snsouch 22942442Snsouch @Override 23042442Snsouch public ArrayData setEmpty(final long lo, final long hi) { 23142442Snsouch underlying.setEmpty(lo, hi); 23242442Snsouch return this; 23342442Snsouch } 23442442Snsouch 23542442Snsouch @Override 23642442Snsouch public Type getOptimisticType() { 23742442Snsouch return underlying.getOptimisticType(); 23842442Snsouch } 23942442Snsouch 24042442Snsouch @Override 24142442Snsouch public int getInt(final int index) { 242164901Simp if (index >= 0 && index < maxDenseLength) { 24342442Snsouch return underlying.getInt(index); 24442442Snsouch } 24542442Snsouch return JSType.toInt32(sparseMap.get(indexToKey(index))); 246228257Sadrian } 247228257Sadrian 24842442Snsouch @Override 24942442Snsouch public int getIntOptimistic(final int index, final int programPoint) { 25042442Snsouch if (index >= 0 && index < maxDenseLength) { 25142442Snsouch return underlying.getIntOptimistic(index, programPoint); 25242442Snsouch } 25342442Snsouch return JSType.toInt32Optimistic(sparseMap.get(indexToKey(index)), programPoint); 25442442Snsouch } 25542442Snsouch 25642442Snsouch @Override 25742442Snsouch public long getLong(final int index) { 25842442Snsouch if (index >= 0 && index < maxDenseLength) { 25942442Snsouch return underlying.getLong(index); 26042442Snsouch } 26142442Snsouch return JSType.toLong(sparseMap.get(indexToKey(index))); 26242442Snsouch } 26342442Snsouch 264228257Sadrian @Override 265228257Sadrian public long getLongOptimistic(final int index, final int programPoint) { 26642442Snsouch if (index >= 0 && index < maxDenseLength) { 26742442Snsouch return underlying.getLongOptimistic(index, programPoint); 26842442Snsouch } 26942442Snsouch return JSType.toLongOptimistic(sparseMap.get(indexToKey(index)), programPoint); 27042442Snsouch } 27142442Snsouch 27243347Sroger @Override 27343347Sroger public double getDouble(final int index) { 27443347Sroger if (index >= 0 && index < maxDenseLength) { 27543347Sroger return underlying.getDouble(index); 27643347Sroger } 27743347Sroger return JSType.toNumber(sparseMap.get(indexToKey(index))); 27843347Sroger } 27943347Sroger 28043347Sroger @Override 28143347Sroger public double getDoubleOptimistic(final int index, final int programPoint) { 28243347Sroger if (index >= 0 && index < maxDenseLength) { 28343347Sroger return underlying.getDouble(index); 28443347Sroger } 28543347Sroger return JSType.toNumberOptimistic(sparseMap.get(indexToKey(index)), programPoint); 28643347Sroger } 28743347Sroger 28843347Sroger @Override 28943347Sroger public Object getObject(final int index) { 29043347Sroger if (index >= 0 && index < maxDenseLength) { 29143347Sroger return underlying.getObject(index); 29243347Sroger } 29343347Sroger 29443347Sroger final Long key = indexToKey(index); 29543347Sroger if (sparseMap.containsKey(key)) { 29643347Sroger return sparseMap.get(key); 29743347Sroger } 29843347Sroger 29938774Snsouch return ScriptRuntime.UNDEFINED; 30038774Snsouch } 30138774Snsouch 30238774Snsouch @Override 30338774Snsouch public boolean has(final int index) { 30438774Snsouch if (index >= 0 && index < maxDenseLength) { 30538774Snsouch return index < underlying.length() && underlying.has(index); 30638774Snsouch } 30738774Snsouch 30838774Snsouch return sparseMap.containsKey(indexToKey(index)); 30940782Snsouch } 31038774Snsouch 31138774Snsouch @Override 31240782Snsouch public ArrayData delete(final int index) { 31338774Snsouch if (index >= 0 && index < maxDenseLength) { 31438774Snsouch if (index < underlying.length()) { 31538774Snsouch underlying = underlying.delete(index); 31638774Snsouch } 31738774Snsouch } else { 31838774Snsouch sparseMap.remove(indexToKey(index)); 31938774Snsouch } 32038774Snsouch 32138774Snsouch return this; 32238774Snsouch } 32338774Snsouch 32438774Snsouch @Override 32538774Snsouch public ArrayData delete(final long fromIndex, final long toIndex) { 32638774Snsouch if (fromIndex < maxDenseLength && fromIndex < underlying.length()) { 32738774Snsouch underlying = underlying.delete(fromIndex, Math.min(toIndex, underlying.length() - 1)); 32838774Snsouch } 32938774Snsouch if (toIndex >= maxDenseLength) { 33040782Snsouch sparseMap.subMap(fromIndex, true, toIndex, true).clear(); 33138774Snsouch } 33238774Snsouch return this; 33340782Snsouch } 33438774Snsouch 33540782Snsouch private static Long indexToKey(final int index) { 33638774Snsouch return ArrayIndex.toLongIndex(index); 33738774Snsouch } 33838774Snsouch 339160372Simp @Override 340160372Simp public ArrayData convert(final Class<?> type) { 341181304Sjhb underlying = underlying.convert(type); 342160372Simp return this; 343160372Simp } 344160372Simp 345160372Simp @Override 346160372Simp public Object pop() { 347160372Simp final long len = length(); 348160372Simp final long underlyingLen = underlying.length(); 349160372Simp if (len == 0) { 350160372Simp return ScriptRuntime.UNDEFINED; 351160372Simp } 352160372Simp if (len == underlyingLen) { 353160372Simp final Object result = underlying.pop(); 354160372Simp setLength(underlying.length()); 355160372Simp return result; 356160372Simp } 357160372Simp setLength(len - 1); 358160372Simp final Long key = len - 1; 359160372Simp return sparseMap.containsKey(key) ? sparseMap.remove(key) : ScriptRuntime.UNDEFINED; 360160372Simp } 361160372Simp 362160372Simp @Override 363160372Simp public ArrayData slice(final long from, final long to) { 364167855Simp assert to <= length(); 365160372Simp final long start = from < 0 ? (from + length()) : from; 366214999Snwhitehorn final long newLength = to - start; 367167855Simp 368160372Simp final long underlyingLength = underlying.length(); 369182034Simp 370182034Simp if (start >= 0 && to <= maxDenseLength) { 371182034Simp if (newLength <= underlyingLength) { 372182034Simp return underlying.slice(from, to); 373181304Sjhb } 374182034Simp return underlying.slice(from, to).ensure(newLength - 1).delete(underlyingLength, newLength); 375167855Simp } 376214999Snwhitehorn 377167855Simp ArrayData sliced = EMPTY_ARRAY; 378160372Simp sliced = sliced.ensure(newLength - 1); 379214999Snwhitehorn for (long i = start; i < to; i = nextIndex(i)) { 380160372Simp if (has((int)i)) { 381214999Snwhitehorn sliced = sliced.set((int)(i - start), getObject((int)i), false); 382160372Simp } 383214999Snwhitehorn } 384214999Snwhitehorn assert sliced.length() == newLength; 385214999Snwhitehorn return sliced; 386214999Snwhitehorn } 387214999Snwhitehorn 388214999Snwhitehorn @Override 389214999Snwhitehorn public long nextIndex(final long index) { 390214999Snwhitehorn if (index < underlying.length() - 1) { 391214999Snwhitehorn return underlying.nextIndex(index); 392214999Snwhitehorn } 393214999Snwhitehorn 394214999Snwhitehorn final Long nextKey = sparseMap.higherKey(index); 395214999Snwhitehorn if (nextKey != null) { 396214999Snwhitehorn return nextKey; 397214999Snwhitehorn } 398214999Snwhitehorn 399214999Snwhitehorn return length(); 400214999Snwhitehorn } 401214999Snwhitehorn} 402214999Snwhitehorn