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
26 package jdk.nashorn.internal.runtime.arrays;
27
28 import java.lang.reflect.Array;
29 import jdk.nashorn.internal.runtime.ScriptRuntime;
30
31 /**
32 * This filter handles the deletion of array elements.
33 */
34 final class DeletedRangeArrayFilter extends ArrayFilter {
35 /** Range (inclusive) tracking deletions */
36 private long lo, hi;
37
38 DeletedRangeArrayFilter(final ArrayData underlying, final long lo, final long hi) {
39 super(maybeSparse(underlying, hi));
40 this.lo = lo;
41 this.hi = hi;
42 }
43
44 private static ArrayData maybeSparse(final ArrayData underlying, final long hi) {
45 if (hi < SparseArrayData.MAX_DENSE_LENGTH || underlying instanceof SparseArrayData) {
46 return underlying;
47 }
48 return new SparseArrayData(underlying, underlying.length());
49 }
50
51 private boolean isEmpty() {
52 return lo > hi;
53 }
54
55 private boolean isDeleted(final int index) {
56 final long longIndex = ArrayIndex.toLongIndex(index);
57 return lo <= longIndex && longIndex <= hi;
58 }
59
60 @Override
61 public ArrayData copy() {
62 return new DeletedRangeArrayFilter(underlying.copy(), lo, hi);
63 }
64
65 @Override
66 public Object[] asObjectArray() {
67 final Object[] value = super.asObjectArray();
68
69 if (lo < Integer.MAX_VALUE) {
70 final int end = (int)Math.min(hi + 1, Integer.MAX_VALUE);
71 for (int i = (int)lo; i < end; i++) {
72 value[i] = ScriptRuntime.UNDEFINED;
73 }
74 }
75
76 return value;
77 }
78
79 @Override
80 public Object asArrayOfType(final Class<?> componentType) {
81 final Object value = super.asArrayOfType(componentType);
82 final Object undefValue = convertUndefinedValue(componentType);
83
84 if (lo < Integer.MAX_VALUE) {
85 final int end = (int)Math.min(hi + 1, Integer.MAX_VALUE);
86 for (int i = (int)lo; i < end; i++) {
87 Array.set(value, i, undefValue);
88 }
89 }
90
91 return value;
92 }
93
94 @Override
95 public ArrayData ensure(final long safeIndex) {
96 if (safeIndex >= SparseArrayData.MAX_DENSE_LENGTH && safeIndex >= length()) {
97 return new SparseArrayData(this, safeIndex + 1);
98 }
99
100 return super.ensure(safeIndex);
101 }
102
103 @Override
104 public ArrayData shiftLeft(final int by) {
105 super.shiftLeft(by);
106 lo = Math.max(0, lo - by);
107 hi = Math.max(-1, hi - by);
108
109 return isEmpty() ? getUnderlying() : this;
110 }
111
112 @Override
113 public ArrayData shiftRight(final int by) {
114 super.shiftRight(by);
115 final long len = length();
116 lo = Math.min(len, lo + by);
117 hi = Math.min(len - 1, hi + by);
118
119 return isEmpty() ? getUnderlying() : this;
120 }
121
122 @Override
123 public ArrayData shrink(final long newLength) {
124 super.shrink(newLength);
125 lo = Math.min(newLength, lo);
126 hi = Math.min(newLength - 1, hi);
127
128 return isEmpty() ? getUnderlying() : this;
129 }
130
131 @Override
132 public ArrayData set(final int index, final Object value, final boolean strict) {
133 final long longIndex = ArrayIndex.toLongIndex(index);
134 if (longIndex < lo || longIndex > hi) {
135 return super.set(index, value, strict);
136 } else if (longIndex > lo && longIndex < hi) {
137 return getDeletedArrayFilter().set(index, value, strict);
138 }
139 if (longIndex == lo) {
140 lo++;
141 } else {
142 assert longIndex == hi;
143 hi--;
144 }
145
146 return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
147 }
148
149 @Override
150 public ArrayData set(final int index, final int value, final boolean strict) {
151 final long longIndex = ArrayIndex.toLongIndex(index);
152 if (longIndex < lo || longIndex > hi) {
153 return super.set(index, value, strict);
154 } else if (longIndex > lo && longIndex < hi) {
155 return getDeletedArrayFilter().set(index, value, strict);
156 }
157 if (longIndex == lo) {
158 lo++;
159 } else {
160 assert longIndex == hi;
161 hi--;
162 }
163
164 return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
165 }
166
167 @Override
168 public ArrayData set(final int index, final double value, final boolean strict) {
169 final long longIndex = ArrayIndex.toLongIndex(index);
170 if (longIndex < lo || longIndex > hi) {
171 return super.set(index, value, strict);
172 } else if (longIndex > lo && longIndex < hi) {
173 return getDeletedArrayFilter().set(index, value, strict);
174 }
175 if (longIndex == lo) {
176 lo++;
177 } else {
178 assert longIndex == hi;
179 hi--;
180 }
181
182 return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
183 }
184
185 @Override
186 public boolean has(final int index) {
187 return super.has(index) && !isDeleted(index);
188 }
189
190 private ArrayData getDeletedArrayFilter() {
191 final ArrayData deleteFilter = new DeletedArrayFilter(getUnderlying());
192 deleteFilter.delete(lo, hi);
193 return deleteFilter;
194 }
195
196 @Override
197 public ArrayData delete(final int index) {
198 final long longIndex = ArrayIndex.toLongIndex(index);
199 underlying.setEmpty(index);
200
201 if (longIndex + 1 == lo) {
202 lo = longIndex;
203 } else if (longIndex - 1 == hi) {
204 hi = longIndex;
205 } else if (longIndex < lo || hi < longIndex) {
206 return getDeletedArrayFilter().delete(index);
207 }
208
209 return this;
210 }
211
212 @Override
213 public ArrayData delete(final long fromIndex, final long toIndex) {
214 if (fromIndex > hi + 1 || toIndex < lo - 1) {
215 return getDeletedArrayFilter().delete(fromIndex, toIndex);
216 }
217 lo = Math.min(fromIndex, lo);
218 hi = Math.max(toIndex, hi);
219 underlying.setEmpty(lo, hi);
220 return this;
221 }
222
223 @Override
224 public Object pop() {
225 final int index = (int)length() - 1;
226 if (super.has(index)) {
227 final boolean isDeleted = isDeleted(index);
228 final Object value = super.pop();
229
230 lo = Math.min(index + 1, lo);
231 hi = Math.min(index, hi);
232 return isDeleted ? ScriptRuntime.UNDEFINED : value;
233 }
234
235 return super.pop();
236 }
237
238 @Override
239 public ArrayData slice(final long from, final long to) {
240 return new DeletedRangeArrayFilter(underlying.slice(from, to), Math.max(0, lo - from), Math.max(0, hi - from));
241 }
242 }