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 void shiftLeft(final int by) {
105 super.shiftLeft(by);
106 lo = Math.max(0, lo - by);
107 hi = Math.max(-1, hi - by);
108 }
109
110 @Override
111 public ArrayData shiftRight(final int by) {
112 super.shiftRight(by);
113 final long len = length();
114 lo = Math.min(len, lo + by);
115 hi = Math.min(len - 1, hi + by);
116
117 return isEmpty() ? getUnderlying() : this;
118 }
119
120 @Override
121 public ArrayData shrink(final long newLength) {
122 super.shrink(newLength);
123 lo = Math.min(newLength, lo);
124 hi = Math.min(newLength - 1, hi);
125
126 return isEmpty() ? getUnderlying() : this;
127 }
128
129 @Override
130 public ArrayData set(final int index, final Object value, final boolean strict) {
131 final long longIndex = ArrayIndex.toLongIndex(index);
132 if (longIndex < lo || longIndex > hi) {
133 return super.set(index, value, strict);
134 } else if (longIndex > lo && longIndex < hi) {
135 return getDeletedArrayFilter().set(index, value, strict);
136 }
137 if (longIndex == lo) {
138 lo++;
139 } else {
140 assert longIndex == hi;
141 hi--;
142 }
143
144 return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
145 }
146
147 @Override
148 public ArrayData set(final int index, final int value, final boolean strict) {
149 final long longIndex = ArrayIndex.toLongIndex(index);
150 if (longIndex < lo || longIndex > hi) {
151 return super.set(index, value, strict);
152 } else if (longIndex > lo && longIndex < hi) {
153 return getDeletedArrayFilter().set(index, value, strict);
154 }
155 if (longIndex == lo) {
156 lo++;
157 } else {
158 assert longIndex == hi;
159 hi--;
160 }
161
162 return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
163 }
164
165 @Override
166 public ArrayData set(final int index, final double value, final boolean strict) {
167 final long longIndex = ArrayIndex.toLongIndex(index);
168 if (longIndex < lo || longIndex > hi) {
169 return super.set(index, value, strict);
170 } else if (longIndex > lo && longIndex < hi) {
171 return getDeletedArrayFilter().set(index, value, strict);
172 }
173 if (longIndex == lo) {
174 lo++;
175 } else {
176 assert longIndex == hi;
177 hi--;
178 }
179
180 return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
181 }
182
183 @Override
184 public boolean has(final int index) {
185 return super.has(index) && !isDeleted(index);
186 }
187
188 private ArrayData getDeletedArrayFilter() {
189 final ArrayData deleteFilter = new DeletedArrayFilter(getUnderlying());
190 deleteFilter.delete(lo, hi);
191 return deleteFilter;
192 }
193
194 @Override
195 public ArrayData delete(final int index) {
196 final long longIndex = ArrayIndex.toLongIndex(index);
197 underlying.setEmpty(index);
198
199 if (longIndex + 1 == lo) {
200 lo = longIndex;
201 } else if (longIndex - 1 == hi) {
202 hi = longIndex;
203 } else if (longIndex < lo || hi < longIndex) {
204 return getDeletedArrayFilter().delete(index);
205 }
206
207 return this;
208 }
209
210 @Override
211 public ArrayData delete(final long fromIndex, final long toIndex) {
212 if (fromIndex > hi + 1 || toIndex < lo - 1) {
213 return getDeletedArrayFilter().delete(fromIndex, toIndex);
214 }
215 lo = Math.min(fromIndex, lo);
216 hi = Math.max(toIndex, hi);
217 underlying.setEmpty(lo, hi);
218 return this;
219 }
220
221 @Override
222 public Object pop() {
223 final int index = (int)length() - 1;
224 if (super.has(index)) {
225 final boolean isDeleted = isDeleted(index);
226 final Object value = super.pop();
227
228 lo = Math.min(index + 1, lo);
229 hi = Math.min(index, hi);
230 return isDeleted ? ScriptRuntime.UNDEFINED : value;
231 }
232
233 return super.pop();
234 }
235
236 @Override
237 public ArrayData slice(final long from, final long to) {
238 return new DeletedRangeArrayFilter(underlying.slice(from, to), Math.max(0, lo - from), Math.max(0, hi - from));
239 }
240 }
--- EOF ---