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