DeletedRangeArrayFilter.java revision 1040:cc3000241e57 
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.lang.reflect.Array;
29import jdk.nashorn.internal.runtime.ScriptRuntime;
30
31/**
32 * This filter handles the deletion of array elements.
33 */
34final 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 intHi = (int)Math.min(hi, Integer.MAX_VALUE);
71            for (int i = (int)lo; i <= intHi; 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 intHi = (int)Math.min(hi, Integer.MAX_VALUE);
86            for (int i = (int)lo; i <= intHi; 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 long 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 ArrayData set(final int index, final double value, final boolean strict) {
185        final long longIndex = ArrayIndex.toLongIndex(index);
186        if (longIndex < lo || longIndex > hi) {
187            return super.set(index, value, strict);
188        } else if (longIndex > lo && longIndex < hi) {
189            return getDeletedArrayFilter().set(index, value, strict);
190        }
191        if (longIndex == lo) {
192            lo++;
193        } else {
194            assert longIndex == hi;
195            hi--;
196        }
197
198        return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
199    }
200
201    @Override
202    public boolean has(final int index) {
203        return super.has(index) && !isDeleted(index);
204    }
205
206    private ArrayData getDeletedArrayFilter() {
207        final ArrayData deleteFilter = new DeletedArrayFilter(getUnderlying());
208        deleteFilter.delete(lo, hi);
209        return deleteFilter;
210    }
211
212    @Override
213    public ArrayData delete(final int index) {
214        final long longIndex = ArrayIndex.toLongIndex(index);
215        underlying.setEmpty(index);
216
217        if (longIndex + 1 == lo) {
218            lo = longIndex;
219        } else if (longIndex - 1 == hi) {
220            hi = longIndex;
221        } else if (longIndex < lo || hi < longIndex) {
222           return getDeletedArrayFilter().delete(index);
223        }
224
225        return this;
226    }
227
228    @Override
229    public ArrayData delete(final long fromIndex, final long toIndex) {
230        if (fromIndex > hi + 1  || toIndex < lo - 1) {
231            return getDeletedArrayFilter().delete(fromIndex, toIndex);
232        }
233        lo = Math.min(fromIndex, lo);
234        hi = Math.max(toIndex, hi);
235        underlying.setEmpty(lo, hi);
236        return this;
237    }
238
239    @Override
240    public Object pop() {
241        final int index = (int)length - 1;
242        if (super.has(index)) {
243            final boolean isDeleted = isDeleted(index);
244            final Object value      = super.pop();
245
246            lo = Math.min(index + 1, lo);
247            hi = Math.min(index, hi);
248            return isDeleted ? ScriptRuntime.UNDEFINED : value;
249        }
250
251        return super.pop();
252    }
253
254    @Override
255    public ArrayData slice(final long from, final long to) {
256        return new DeletedRangeArrayFilter(underlying.slice(from, to), Math.max(0, lo - from), Math.max(0, hi - from));
257    }
258}
259