Mercurial Mercurial > jdk-sandbox / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/SparseArrayData.java
changeset 26886 18c744ab4df2
parent 26768 751b0f427090
child 27098 2875b30458d3
equal deleted inserted replaced
26786:f0c5e4b732da 26886:18c744ab4df2 
    51         this(underlying, length, new TreeMap<Long, Object>());
 
    51         this(underlying, length, new TreeMap<Long, Object>());
 
    52     }
 
    52     }
 
    53 
    53 
    54     SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
 
    54     SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
 
    55         super(length);
 
    55         super(length);
 
    56         assert underlying.length() <= length;
 
    56         assert underlying.length <= length;
 
    57         this.underlying = underlying;
 
    57         this.underlying = underlying;
 
    58         this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length());
 
    58         this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length);
 
    59         this.sparseMap = sparseMap;
 
    59         this.sparseMap = sparseMap;
 
    60     }
 
    60     }
 
    61 
    61 
    62     @Override
 
    62     @Override
 
    63     public ArrayData copy() {
 
    63     public ArrayData copy() {
 
    64         return new SparseArrayData(underlying.copy(), length(), new TreeMap<>(sparseMap));
 
    64         return new SparseArrayData(underlying.copy(), length, new TreeMap<>(sparseMap));
 
    65     }
 
    65     }
 
    66 
    66 
    67     @Override
 
    67     @Override
 
    68     public Object[] asObjectArray() {
 
    68     public Object[] asObjectArray() {
 
    69         final int length = (int) Math.min(length(), Integer.MAX_VALUE);
 
    69         final int len = (int)Math.min(length, Integer.MAX_VALUE);
 
    70         final int underlyingLength = (int) Math.min(length, underlying.length());
 
    70         final int underlyingLength = (int)Math.min(len, underlying.length);
 
    71         final Object[] objArray = new Object[length];
 
    71         final Object[] objArray = new Object[len];
 
    72 
    72 
    73         for (int i = 0; i < underlyingLength; i++) {
 
    73         for (int i = 0; i < underlyingLength; i++) {
 
    74             objArray[i] = underlying.getObject(i);
 
    74             objArray[i] = underlying.getObject(i);
 
    75         }
 
    75         }
 
    76 
    76 
    77         Arrays.fill(objArray, underlyingLength, length, ScriptRuntime.UNDEFINED);
 
    77         Arrays.fill(objArray, underlyingLength, len, ScriptRuntime.UNDEFINED);
 
    78 
    78 
    79         for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
 
    79         for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
 
    80             final long key = entry.getKey();
 
    80             final long key = entry.getKey();
 
    81             if (key <= Integer.MAX_VALUE) {
 
    81             if (key <= Integer.MAX_VALUE) {
 
    82                 objArray[(int)key] = entry.getValue();
 
    82                 objArray[(int)key] = entry.getValue();
 
   102                 newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
 
   102                 newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
 
   103             }
 
   103             }
 
   104         }
 
   104         }
 
   105 
   105 
   106         sparseMap = newSparseMap;
 
   106         sparseMap = newSparseMap;
 
   107         setLength(Math.max(length() - by, 0));
 
   107         setLength(Math.max(length - by, 0));
 
   108     }
 
   108     }
 
   109 
   109 
   110     @Override
 
   110     @Override
 
   111     public ArrayData shiftRight(final int by) {
 
   111     public ArrayData shiftRight(final int by) {
 
   112         final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
 
   112         final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
 
   113         if (underlying.length() + by > maxDenseLength) {
 
   113         if (underlying.length + by > maxDenseLength) {
 
   114             for (long i = maxDenseLength - by; i < underlying.length(); i++) {
 
   114             for (long i = maxDenseLength - by; i < underlying.length; i++) {
 
   115                 if (underlying.has((int) i)) {
 
   115                 if (underlying.has((int) i)) {
 
   116                     newSparseMap.put(Long.valueOf(i + by), underlying.getObject((int) i));
 
   116                     newSparseMap.put(Long.valueOf(i + by), underlying.getObject((int) i));
 
   117                 }
 
   117                 }
 
   118             }
 
   118             }
 
   119             underlying = underlying.shrink((int) (maxDenseLength - by));
 
   119             underlying = underlying.shrink((int) (maxDenseLength - by));
 
   125             final long newIndex = entry.getKey().longValue() + by;
 
   125             final long newIndex = entry.getKey().longValue() + by;
 
   126             newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
 
   126             newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
 
   127         }
 
   127         }
 
   128 
   128 
   129         sparseMap = newSparseMap;
 
   129         sparseMap = newSparseMap;
 
   130         setLength(length() + by);
 
   130         setLength(length + by);
 
   131 
   131 
   132         return this;
 
   132         return this;
 
   133     }
 
   133     }
 
   134 
   134 
   135     @Override
 
   135     @Override
 
   136     public ArrayData ensure(final long safeIndex) {
 
   136     public ArrayData ensure(final long safeIndex) {
 
   137         if (safeIndex < maxDenseLength && underlying.length() <= safeIndex) {
 
   137         if (safeIndex < maxDenseLength && underlying.length <= safeIndex) {
 
   138             underlying = underlying.ensure(safeIndex);
 
   138             underlying = underlying.ensure(safeIndex);
 
   139         }
 
   139         }
 
   140         setLength(Math.max(safeIndex + 1, length()));
 
   140         setLength(Math.max(safeIndex + 1, length));
 
   141         return this;
 
   141         return this;
 
   142     }
 
   142     }
 
   143 
   143 
   144     @Override
 
   144     @Override
 
   145     public ArrayData shrink(final long newLength) {
 
   145     public ArrayData shrink(final long newLength) {
 
   146         if (newLength < underlying.length()) {
 
   146         if (newLength < underlying.length) {
 
   147             underlying = underlying.shrink(newLength);
 
   147             underlying = underlying.shrink(newLength);
 
   148             underlying.setLength(newLength);
 
   148             underlying.setLength(newLength);
 
   149             sparseMap.clear();
 
   149             sparseMap.clear();
 
   150             setLength(newLength);
 
   150             setLength(newLength);
 
   151         }
 
   151         }
 
   158     @Override
 
   158     @Override
 
   159     public ArrayData set(final int index, final Object value, final boolean strict) {
 
   159     public ArrayData set(final int index, final Object value, final boolean strict) {
 
   160         if (index >= 0 && index < maxDenseLength) {
 
   160         if (index >= 0 && index < maxDenseLength) {
 
   161             ensure(index);
 
   161             ensure(index);
 
   162             underlying = underlying.set(index, value, strict);
 
   162             underlying = underlying.set(index, value, strict);
 
   163             setLength(Math.max(underlying.length(), length()));
 
   163             setLength(Math.max(underlying.length, length));
 
   164         } else {
 
   164         } else {
 
   165             final Long longIndex = indexToKey(index);
 
   165             final Long longIndex = indexToKey(index);
 
   166             sparseMap.put(longIndex, value);
 
   166             sparseMap.put(longIndex, value);
 
   167             setLength(Math.max(longIndex + 1, length()));
 
   167             setLength(Math.max(longIndex + 1, length));
 
   168         }
 
   168         }
 
   169 
   169 
   170         return this;
 
   170         return this;
 
   171     }
 
   171     }
 
   172 
   172 
   173     @Override
 
   173     @Override
 
   174     public ArrayData set(final int index, final int value, final boolean strict) {
 
   174     public ArrayData set(final int index, final int value, final boolean strict) {
 
   175         if (index >= 0 && index < maxDenseLength) {
 
   175         if (index >= 0 && index < maxDenseLength) {
 
   176             ensure(index);
 
   176             ensure(index);
 
   177             underlying = underlying.set(index, value, strict);
 
   177             underlying = underlying.set(index, value, strict);
 
   178             setLength(Math.max(underlying.length(), length()));
 
   178             setLength(Math.max(underlying.length, length));
 
   179         } else {
 
   179         } else {
 
   180             final Long longIndex = indexToKey(index);
 
   180             final Long longIndex = indexToKey(index);
 
   181             sparseMap.put(longIndex, value);
 
   181             sparseMap.put(longIndex, value);
 
   182             setLength(Math.max(longIndex + 1, length()));
 
   182             setLength(Math.max(longIndex + 1, length));
 
   183         }
 
   183         }
 
   184         return this;
 
   184         return this;
 
   185     }
 
   185     }
 
   186 
   186 
   187     @Override
 
   187     @Override
 
   188     public ArrayData set(final int index, final long value, final boolean strict) {
 
   188     public ArrayData set(final int index, final long value, final boolean strict) {
 
   189         if (index >= 0 && index < maxDenseLength) {
 
   189         if (index >= 0 && index < maxDenseLength) {
 
   190             ensure(index);
 
   190             ensure(index);
 
   191             underlying = underlying.set(index, value, strict);
 
   191             underlying = underlying.set(index, value, strict);
 
   192             setLength(Math.max(underlying.length(), length()));
 
   192             setLength(Math.max(underlying.length, length));
 
   193         } else {
 
   193         } else {
 
   194             final Long longIndex = indexToKey(index);
 
   194             final Long longIndex = indexToKey(index);
 
   195             sparseMap.put(longIndex, value);
 
   195             sparseMap.put(longIndex, value);
 
   196             setLength(Math.max(longIndex + 1, length()));
 
   196             setLength(Math.max(longIndex + 1, length));
 
   197         }
 
   197         }
 
   198         return this;
 
   198         return this;
 
   199     }
 
   199     }
 
   200 
   200 
   201     @Override
 
   201     @Override
 
   202     public ArrayData set(final int index, final double value, final boolean strict) {
 
   202     public ArrayData set(final int index, final double value, final boolean strict) {
 
   203         if (index >= 0 && index < maxDenseLength) {
 
   203         if (index >= 0 && index < maxDenseLength) {
 
   204             ensure(index);
 
   204             ensure(index);
 
   205             underlying = underlying.set(index, value, strict);
 
   205             underlying = underlying.set(index, value, strict);
 
   206             setLength(Math.max(underlying.length(), length()));
 
   206             setLength(Math.max(underlying.length, length));
 
   207         } else {
 
   207         } else {
 
   208             final Long longIndex = indexToKey(index);
 
   208             final Long longIndex = indexToKey(index);
 
   209             sparseMap.put(longIndex, value);
 
   209             sparseMap.put(longIndex, value);
 
   210             setLength(Math.max(longIndex + 1, length()));
 
   210             setLength(Math.max(longIndex + 1, length));
 
   211         }
 
   211         }
 
   212         return this;
 
   212         return this;
 
   213     }
 
   213     }
 
   214 
   214 
   215     @Override
 
   215     @Override
 
   292     }
 
   292     }
 
   293 
   293 
   294     @Override
 
   294     @Override
 
   295     public boolean has(final int index) {
 
   295     public boolean has(final int index) {
 
   296         if (index >= 0 && index < maxDenseLength) {
 
   296         if (index >= 0 && index < maxDenseLength) {
 
   297             return index < underlying.length() && underlying.has(index);
 
   297             return index < underlying.length && underlying.has(index);
 
   298         }
 
   298         }
 
   299 
   299 
   300         return sparseMap.containsKey(indexToKey(index));
 
   300         return sparseMap.containsKey(indexToKey(index));
 
   301     }
 
   301     }
 
   302 
   302 
   303     @Override
 
   303     @Override
 
   304     public ArrayData delete(final int index) {
 
   304     public ArrayData delete(final int index) {
 
   305         if (index >= 0 && index < maxDenseLength) {
 
   305         if (index >= 0 && index < maxDenseLength) {
 
   306             if (index < underlying.length()) {
 
   306             if (index < underlying.length) {
 
   307                 underlying = underlying.delete(index);
 
   307                 underlying = underlying.delete(index);
 
   308             }
 
   308             }
 
   309         } else {
 
   309         } else {
 
   310             sparseMap.remove(indexToKey(index));
 
   310             sparseMap.remove(indexToKey(index));
 
   311         }
 
   311         }
 
   313         return this;
 
   313         return this;
 
   314     }
 
   314     }
 
   315 
   315 
   316     @Override
 
   316     @Override
 
   317     public ArrayData delete(final long fromIndex, final long toIndex) {
 
   317     public ArrayData delete(final long fromIndex, final long toIndex) {
 
   318         if (fromIndex < maxDenseLength && fromIndex < underlying.length()) {
 
   318         if (fromIndex < maxDenseLength && fromIndex < underlying.length) {
 
   319             underlying = underlying.delete(fromIndex, Math.min(toIndex, underlying.length() - 1));
 
   319             underlying = underlying.delete(fromIndex, Math.min(toIndex, underlying.length - 1));
 
   320         }
 
   320         }
 
   321         if (toIndex >= maxDenseLength) {
 
   321         if (toIndex >= maxDenseLength) {
 
   322             sparseMap.subMap(fromIndex, true, toIndex, true).clear();
 
   322             sparseMap.subMap(fromIndex, true, toIndex, true).clear();
 
   323         }
 
   323         }
 
   324         return this;
 
   324         return this;
 
   334         return this;
 
   334         return this;
 
   335     }
 
   335     }
 
   336 
   336 
   337     @Override
 
   337     @Override
 
   338     public Object pop() {
 
   338     public Object pop() {
 
   339         if (length() == 0) {
 
   339         if (length == 0) {
 
   340             return ScriptRuntime.UNDEFINED;
 
   340             return ScriptRuntime.UNDEFINED;
 
   341         }
 
   341         }
 
   342         if (length() == underlying.length()) {
 
   342         if (length == underlying.length) {
 
   343             final Object result = underlying.pop();
 
   343             final Object result = underlying.pop();
 
   344             setLength(underlying.length());
 
   344             setLength(underlying.length);
 
   345             return result;
 
   345             return result;
 
   346         }
 
   346         }
 
   347         setLength(length() - 1);
 
   347         setLength(length - 1);
 
   348         final Long key = Long.valueOf(length());
 
   348         final Long key = Long.valueOf(length);
 
   349         return sparseMap.containsKey(key) ? sparseMap.remove(key) : ScriptRuntime.UNDEFINED;
 
   349         return sparseMap.containsKey(key) ? sparseMap.remove(key) : ScriptRuntime.UNDEFINED;
 
   350     }
 
   350     }
 
   351 
   351 
   352     @Override
 
   352     @Override
 
   353     public ArrayData slice(final long from, final long to) {
 
   353     public ArrayData slice(final long from, final long to) {
 
   354         assert to <= length();
 
   354         assert to <= length;
 
   355         final long start = from < 0 ? (from + length()) : from;
 
   355         final long start = from < 0 ? (from + length) : from;
 
   356         final long newLength = to - start;
 
   356         final long newLength = to - start;
 
   357 
   357 
   358         if (start >= 0 && to <= maxDenseLength) {
 
   358         if (start >= 0 && to <= maxDenseLength) {
 
   359             if (newLength <= underlying.length()) {
 
   359             if (newLength <= underlying.length) {
 
   360                 return underlying.slice(from, to);
 
   360                 return underlying.slice(from, to);
 
   361             }
 
   361             }
 
   362             return underlying.slice(from, to).ensure(newLength - 1).delete(underlying.length(), newLength);
 
   362             return underlying.slice(from, to).ensure(newLength - 1).delete(underlying.length, newLength);
 
   363         }
 
   363         }
 
   364 
   364 
   365         ArrayData sliced = EMPTY_ARRAY;
 
   365         ArrayData sliced = EMPTY_ARRAY;
 
   366         sliced = sliced.ensure(newLength - 1);
 
   366         sliced = sliced.ensure(newLength - 1);
 
   367         for (long i = start; i < to; i = nextIndex(i)) {
 
   367         for (long i = start; i < to; i = nextIndex(i)) {
 
   368             if (has((int)i)) {
 
   368             if (has((int)i)) {
 
   369                 sliced = sliced.set((int)(i - start), getObject((int)i), false);
 
   369                 sliced = sliced.set((int)(i - start), getObject((int)i), false);
 
   370             }
 
   370             }
 
   371         }
 
   371         }
 
   372         assert sliced.length() == newLength;
 
   372         assert sliced.length == newLength;
 
   373         return sliced;
 
   373         return sliced;
 
   374     }
 
   374     }
 
   375 
   375 
   376     @Override
 
   376     @Override
 
   377     public long nextIndex(final long index) {
 
   377     public long nextIndex(final long index) {
 
   378         if (index < underlying.length() - 1) {
 
   378         if (index < underlying.length - 1) {
 
   379             return underlying.nextIndex(index);
 
   379             return underlying.nextIndex(index);
 
   380         }
 
   380         }
 
   381 
   381 
   382         final Long nextKey = sparseMap.higherKey(index);
 
   382         final Long nextKey = sparseMap.higherKey(index);
 
   383         if (nextKey != null) {
 
   383         if (nextKey != null) {
 
   384             return nextKey;
 
   384             return nextKey;
 
   385         }
 
   385         }
 
   386         return length();
 
   386         return length;
 
   387     }
 
   387     }
 
   388 }
 
   388 }
jdk-sandbox