001: /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
002: *
003: * ***** BEGIN LICENSE BLOCK *****
004: * Version: MPL 1.1/GPL 2.0
005: *
006: * The contents of this file are subject to the Mozilla Public License Version
007: * 1.1 (the "License"); you may not use this file except in compliance with
008: * the License. You may obtain a copy of the License at
009: * http://www.mozilla.org/MPL/
010: *
011: * Software distributed under the License is distributed on an "AS IS" basis,
012: * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
013: * for the specific language governing rights and limitations under the
014: * License.
015: *
016: * The Original Code is Rhino code, released
017: * May 6, 1999.
018: *
019: * The Initial Developer of the Original Code is
020: * Netscape Communications Corporation.
021: * Portions created by the Initial Developer are Copyright (C) 1997-2000
022: * the Initial Developer. All Rights Reserved.
023: *
024: * Contributor(s):
025: * Igor Bukanov
026: *
027: * Alternatively, the contents of this file may be used under the terms of
028: * the GNU General Public License Version 2 or later (the "GPL"), in which
029: * case the provisions of the GPL are applicable instead of those above. If
030: * you wish to allow use of your version of this file only under the terms of
031: * the GPL and not to allow others to use your version of this file under the
032: * MPL, indicate your decision by deleting the provisions above and replacing
033: * them with the notice and other provisions required by the GPL. If you do
034: * not delete the provisions above, a recipient may use your version of this
035: * file under either the MPL or the GPL.
036: *
037: * ***** END LICENSE BLOCK ***** */
038:
039: package org.mozilla.javascript;
040:
041: import java.io.Serializable;
042: import java.io.IOException;
043: import java.io.ObjectInputStream;
044: import java.io.ObjectOutputStream;
045:
046: /**
047: Implementation of resizable array with focus on minimizing memory usage by storing few initial array elements in object fields. Can also be used as a stack.
048: */
049:
050: public class ObjArray implements Serializable {
051: static final long serialVersionUID = 4174889037736658296L;
052:
053: public ObjArray() {
054: }
055:
056: public final boolean isSealed() {
057: return sealed;
058: }
059:
060: public final void seal() {
061: sealed = true;
062: }
063:
064: public final boolean isEmpty() {
065: return size == 0;
066: }
067:
068: public final int size() {
069: return size;
070: }
071:
072: public final void setSize(int newSize) {
073: if (newSize < 0)
074: throw new IllegalArgumentException();
075: if (sealed)
076: throw onSeledMutation();
077: int N = size;
078: if (newSize < N) {
079: for (int i = newSize; i != N; ++i) {
080: setImpl(i, null);
081: }
082: } else if (newSize > N) {
083: if (newSize > FIELDS_STORE_SIZE) {
084: ensureCapacity(newSize);
085: }
086: }
087: size = newSize;
088: }
089:
090: public final Object get(int index) {
091: if (!(0 <= index && index < size))
092: throw onInvalidIndex(index, size);
093: return getImpl(index);
094: }
095:
096: public final void set(int index, Object value) {
097: if (!(0 <= index && index < size))
098: throw onInvalidIndex(index, size);
099: if (sealed)
100: throw onSeledMutation();
101: setImpl(index, value);
102: }
103:
104: private Object getImpl(int index) {
105: switch (index) {
106: case 0:
107: return f0;
108: case 1:
109: return f1;
110: case 2:
111: return f2;
112: case 3:
113: return f3;
114: case 4:
115: return f4;
116: }
117: return data[index - FIELDS_STORE_SIZE];
118: }
119:
120: private void setImpl(int index, Object value) {
121: switch (index) {
122: case 0:
123: f0 = value;
124: break;
125: case 1:
126: f1 = value;
127: break;
128: case 2:
129: f2 = value;
130: break;
131: case 3:
132: f3 = value;
133: break;
134: case 4:
135: f4 = value;
136: break;
137: default:
138: data[index - FIELDS_STORE_SIZE] = value;
139: }
140:
141: }
142:
143: public int indexOf(Object obj) {
144: int N = size;
145: for (int i = 0; i != N; ++i) {
146: Object current = getImpl(i);
147: if (current == obj
148: || (current != null && current.equals(obj))) {
149: return i;
150: }
151: }
152: return -1;
153: }
154:
155: public int lastIndexOf(Object obj) {
156: for (int i = size; i != 0;) {
157: --i;
158: Object current = getImpl(i);
159: if (current == obj
160: || (current != null && current.equals(obj))) {
161: return i;
162: }
163: }
164: return -1;
165: }
166:
167: public final Object peek() {
168: int N = size;
169: if (N == 0)
170: throw onEmptyStackTopRead();
171: return getImpl(N - 1);
172: }
173:
174: public final Object pop() {
175: if (sealed)
176: throw onSeledMutation();
177: int N = size;
178: --N;
179: Object top;
180: switch (N) {
181: case -1:
182: throw onEmptyStackTopRead();
183: case 0:
184: top = f0;
185: f0 = null;
186: break;
187: case 1:
188: top = f1;
189: f1 = null;
190: break;
191: case 2:
192: top = f2;
193: f2 = null;
194: break;
195: case 3:
196: top = f3;
197: f3 = null;
198: break;
199: case 4:
200: top = f4;
201: f4 = null;
202: break;
203: default:
204: top = data[N - FIELDS_STORE_SIZE];
205: data[N - FIELDS_STORE_SIZE] = null;
206: }
207: size = N;
208: return top;
209: }
210:
211: public final void push(Object value) {
212: add(value);
213: }
214:
215: public final void add(Object value) {
216: if (sealed)
217: throw onSeledMutation();
218: int N = size;
219: if (N >= FIELDS_STORE_SIZE) {
220: ensureCapacity(N + 1);
221: }
222: size = N + 1;
223: setImpl(N, value);
224: }
225:
226: public final void add(int index, Object value) {
227: int N = size;
228: if (!(0 <= index && index <= N))
229: throw onInvalidIndex(index, N + 1);
230: if (sealed)
231: throw onSeledMutation();
232: Object tmp;
233: switch (index) {
234: case 0:
235: if (N == 0) {
236: f0 = value;
237: break;
238: }
239: tmp = f0;
240: f0 = value;
241: value = tmp;
242: case 1:
243: if (N == 1) {
244: f1 = value;
245: break;
246: }
247: tmp = f1;
248: f1 = value;
249: value = tmp;
250: case 2:
251: if (N == 2) {
252: f2 = value;
253: break;
254: }
255: tmp = f2;
256: f2 = value;
257: value = tmp;
258: case 3:
259: if (N == 3) {
260: f3 = value;
261: break;
262: }
263: tmp = f3;
264: f3 = value;
265: value = tmp;
266: case 4:
267: if (N == 4) {
268: f4 = value;
269: break;
270: }
271: tmp = f4;
272: f4 = value;
273: value = tmp;
274:
275: index = FIELDS_STORE_SIZE;
276: default:
277: ensureCapacity(N + 1);
278: if (index != N) {
279: System.arraycopy(data, index - FIELDS_STORE_SIZE, data,
280: index - FIELDS_STORE_SIZE + 1, N - index);
281: }
282: data[index - FIELDS_STORE_SIZE] = value;
283: }
284: size = N + 1;
285: }
286:
287: public final void remove(int index) {
288: int N = size;
289: if (!(0 <= index && index < N))
290: throw onInvalidIndex(index, N);
291: if (sealed)
292: throw onSeledMutation();
293: --N;
294: switch (index) {
295: case 0:
296: if (N == 0) {
297: f0 = null;
298: break;
299: }
300: f0 = f1;
301: case 1:
302: if (N == 1) {
303: f1 = null;
304: break;
305: }
306: f1 = f2;
307: case 2:
308: if (N == 2) {
309: f2 = null;
310: break;
311: }
312: f2 = f3;
313: case 3:
314: if (N == 3) {
315: f3 = null;
316: break;
317: }
318: f3 = f4;
319: case 4:
320: if (N == 4) {
321: f4 = null;
322: break;
323: }
324: f4 = data[0];
325:
326: index = FIELDS_STORE_SIZE;
327: default:
328: if (index != N) {
329: System.arraycopy(data, index - FIELDS_STORE_SIZE + 1,
330: data, index - FIELDS_STORE_SIZE, N - index);
331: }
332: data[N - FIELDS_STORE_SIZE] = null;
333: }
334: size = N;
335: }
336:
337: public final void clear() {
338: if (sealed)
339: throw onSeledMutation();
340: int N = size;
341: for (int i = 0; i != N; ++i) {
342: setImpl(i, null);
343: }
344: size = 0;
345: }
346:
347: public final Object[] toArray() {
348: Object[] array = new Object[size];
349: toArray(array, 0);
350: return array;
351: }
352:
353: public final void toArray(Object[] array) {
354: toArray(array, 0);
355: }
356:
357: public final void toArray(Object[] array, int offset) {
358: int N = size;
359: switch (N) {
360: default:
361: System.arraycopy(data, 0, array,
362: offset + FIELDS_STORE_SIZE, N - FIELDS_STORE_SIZE);
363: case 5:
364: array[offset + 4] = f4;
365: case 4:
366: array[offset + 3] = f3;
367: case 3:
368: array[offset + 2] = f2;
369: case 2:
370: array[offset + 1] = f1;
371: case 1:
372: array[offset + 0] = f0;
373: case 0:
374: break;
375: }
376: }
377:
378: private void ensureCapacity(int minimalCapacity) {
379: int required = minimalCapacity - FIELDS_STORE_SIZE;
380: if (required <= 0)
381: throw new IllegalArgumentException();
382: if (data == null) {
383: int alloc = FIELDS_STORE_SIZE * 2;
384: if (alloc < required) {
385: alloc = required;
386: }
387: data = new Object[alloc];
388: } else {
389: int alloc = data.length;
390: if (alloc < required) {
391: if (alloc <= FIELDS_STORE_SIZE) {
392: alloc = FIELDS_STORE_SIZE * 2;
393: } else {
394: alloc *= 2;
395: }
396: if (alloc < required) {
397: alloc = required;
398: }
399: Object[] tmp = new Object[alloc];
400: if (size > FIELDS_STORE_SIZE) {
401: System.arraycopy(data, 0, tmp, 0, size
402: - FIELDS_STORE_SIZE);
403: }
404: data = tmp;
405: }
406: }
407: }
408:
409: private static RuntimeException onInvalidIndex(int index,
410: int upperBound) {
411: // \u2209 is "NOT ELEMENT OF"
412: String msg = index + " \u2209 [0, " + upperBound + ')';
413: throw new IndexOutOfBoundsException(msg);
414: }
415:
416: private static RuntimeException onEmptyStackTopRead() {
417: throw new RuntimeException("Empty stack");
418: }
419:
420: private static RuntimeException onSeledMutation() {
421: throw new IllegalStateException(
422: "Attempt to modify sealed array");
423: }
424:
425: private void writeObject(ObjectOutputStream os) throws IOException {
426: os.defaultWriteObject();
427: int N = size;
428: for (int i = 0; i != N; ++i) {
429: Object obj = getImpl(i);
430: os.writeObject(obj);
431: }
432: }
433:
434: private void readObject(ObjectInputStream is) throws IOException,
435: ClassNotFoundException {
436: is.defaultReadObject(); // It reads size
437: int N = size;
438: if (N > FIELDS_STORE_SIZE) {
439: data = new Object[N - FIELDS_STORE_SIZE];
440: }
441: for (int i = 0; i != N; ++i) {
442: Object obj = is.readObject();
443: setImpl(i, obj);
444: }
445: }
446:
447: // Number of data elements
448: private int size;
449:
450: private boolean sealed;
451:
452: private static final int FIELDS_STORE_SIZE = 5;
453: private transient Object f0, f1, f2, f3, f4;
454: private transient Object[] data;
455: }
|