001: /***
002: * ASM: a very small and fast Java bytecode manipulation framework
003: * Copyright (c) 2000-2005 INRIA, France Telecom
004: * All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: * 1. Redistributions of source code must retain the above copyright
010: * notice, this list of conditions and the following disclaimer.
011: * 2. Redistributions in binary form must reproduce the above copyright
012: * notice, this list of conditions and the following disclaimer in the
013: * documentation and/or other materials provided with the distribution.
014: * 3. Neither the name of the copyright holders nor the names of its
015: * contributors may be used to endorse or promote products derived from
016: * this software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
022: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
023: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
024: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
025: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
026: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
027: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
028: * THE POSSIBILITY OF SUCH DAMAGE.
029: */package org.objectweb.asm.tree;
030:
031: import java.util.Iterator;
032:
033: import org.objectweb.asm.MethodVisitor;
034:
035: /**
036: * A doubly linked list of {@link AbstractInsnNode} objects. <i>This
037: * implementation is not thread safe</i>.
038: */
039: public class InsnList {
040:
041: /**
042: * Indicates if preconditions of methods of this class must be checked.
043: * <i>Checking preconditions causes the {@link #indexOf indexOf},
044: * {@link #set set}, {@link #insert(AbstractInsnNode, AbstractInsnNode)},
045: * {@link #insert(AbstractInsnNode, InsnList)}, {@link #remove remove} and
046: * {@link #clear} methods to execute in O(n) time instead of O(1)</i>.
047: */
048: public static boolean check;
049:
050: /**
051: * The number of instructions in this list.
052: */
053: private int size;
054:
055: /**
056: * The first instruction in this list. May be <tt>null</tt>.
057: */
058: private AbstractInsnNode first;
059:
060: /**
061: * The last instruction in this list. May be <tt>null</tt>.
062: */
063: private AbstractInsnNode last;
064:
065: /**
066: * A cache of the instructions of this list. This cache is used to improve
067: * the performance of the {@link #get} method.
068: */
069: private AbstractInsnNode[] cache;
070:
071: /**
072: * Returns the number of instructions in this list.
073: *
074: * @return the number of instructions in this list.
075: */
076: public int size() {
077: return size;
078: }
079:
080: /**
081: * Returns the first instruction in this list.
082: *
083: * @return the first instruction in this list, or <tt>null</tt> if the
084: * list is empty.
085: */
086: public AbstractInsnNode getFirst() {
087: return first;
088: }
089:
090: /**
091: * Returns the last instruction in this list.
092: *
093: * @return the last instruction in this list, or <tt>null</tt> if the list
094: * is empty.
095: */
096: public AbstractInsnNode getLast() {
097: return last;
098: }
099:
100: /**
101: * Returns the instruction whose index is given. This method builds a cache
102: * of the instructions in this list to avoid scanning the whole list each
103: * time it is called. Once the cache is built, this method run in constant
104: * time. This cache is invalidated by all the methods that modify the list.
105: *
106: * @param index the index of the instruction that must be returned.
107: * @return the instruction whose index is given.
108: * @throws IndexOutOfBoundsException if (index < 0 || index >= size()).
109: */
110: public AbstractInsnNode get(final int index) {
111: if (index < 0 || index >= size) {
112: throw new IndexOutOfBoundsException();
113: }
114: if (cache == null) {
115: cache = toArray();
116: }
117: return cache[index];
118: }
119:
120: /**
121: * Returns <tt>true</tt> if the given instruction belongs to this list.
122: * This method always scans the instructions of this list until it finds the
123: * given instruction or reaches the end of the list.
124: *
125: * @param insn an instruction.
126: * @return <tt>true</tt> if the given instruction belongs to this list.
127: */
128: public boolean contains(final AbstractInsnNode insn) {
129: AbstractInsnNode i = first;
130: while (i != null && i != insn) {
131: i = i.next;
132: }
133: return i != null;
134: }
135:
136: /**
137: * Returns the index of the given instruction in this list. This method
138: * builds a cache of the instruction indexes to avoid scanning the whole
139: * list each time it is called. Once the cache is built, this method run in
140: * constant time. The cache is invalidated by all the methods that modify
141: * the list.
142: *
143: * @param insn an instruction <i>of this list</i>.
144: * @return the index of the given instruction in this list. <i>The result of
145: * this method is undefined if the given instruction does not belong
146: * to this list</i>. Use {@link #contains contains} to test if an
147: * instruction belongs to an instruction list or not.
148: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt> and
149: * if insn does not belong to this list.
150: */
151: public int indexOf(final AbstractInsnNode insn) {
152: if (check && !contains(insn)) {
153: throw new IllegalArgumentException();
154: }
155: if (cache == null) {
156: cache = toArray();
157: }
158: return insn.index;
159: }
160:
161: /**
162: * Makes the given visitor visit all of the instructions in this list.
163: *
164: * @param mv the method visitor that must visit the instructions.
165: */
166: public void accept(final MethodVisitor mv) {
167: AbstractInsnNode insn = first;
168: while (insn != null) {
169: insn.accept(mv);
170: insn = insn.next;
171: }
172: }
173:
174: /**
175: * Returns an iterator over the instructions in this list.
176: *
177: * @return an iterator over the instructions in this list.
178: */
179: public Iterator iterator() {
180: return new Iterator() {
181:
182: AbstractInsnNode insn = first;
183:
184: public boolean hasNext() {
185: return insn != null;
186: }
187:
188: public Object next() {
189: Object result = insn;
190: insn = insn.next;
191: return result;
192: }
193:
194: public void remove() {
195: InsnList.this .remove(insn.prev);
196: }
197: };
198: }
199:
200: /**
201: * Returns an array containing all of the instructions in this list.
202: *
203: * @return an array containing all of the instructions in this list.
204: */
205: public AbstractInsnNode[] toArray() {
206: int i = 0;
207: AbstractInsnNode elem = first;
208: AbstractInsnNode[] insns = new AbstractInsnNode[size];
209: while (elem != null) {
210: insns[i] = elem;
211: elem.index = i++;
212: elem = elem.next;
213: }
214: return insns;
215: }
216:
217: /**
218: * Replaces an instruction of this list with another instruction.
219: *
220: * @param i an instruction <i>of this list</i>.
221: * @param insn another instruction, <i>which must not belong to any
222: * {@link InsnList}</i>.
223: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
224: * and if i does not belong to this list or if insn belongs to an
225: * instruction list.
226: */
227: public void set(final AbstractInsnNode i,
228: final AbstractInsnNode insn) {
229: if (check && !(contains(i) && insn.index == -1)) {
230: throw new IllegalArgumentException();
231: }
232: AbstractInsnNode next = i.next;
233: insn.next = next;
234: if (next != null) {
235: next.prev = insn;
236: } else {
237: last = insn;
238: }
239: AbstractInsnNode prev = i.prev;
240: insn.prev = prev;
241: if (prev != null) {
242: prev.next = insn;
243: } else {
244: first = insn;
245: }
246: if (cache != null) {
247: int index = i.index;
248: cache[index] = insn;
249: insn.index = index;
250: } else {
251: insn.index = 0; // insn now belongs to an InsnList
252: }
253: i.index = -1; // i no longer belongs to an InsnList
254: i.prev = null;
255: i.next = null;
256: }
257:
258: /**
259: * Adds the given instruction to the end of this list.
260: *
261: * @param insn an instruction, <i>which must not belong to any
262: * {@link InsnList}</i>.
263: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
264: * and if insn belongs to an instruction list.
265: */
266: public void add(final AbstractInsnNode insn) {
267: if (check && insn.index != -1) {
268: throw new IllegalArgumentException();
269: }
270: ++size;
271: if (last == null) {
272: first = insn;
273: last = insn;
274: } else {
275: last.next = insn;
276: insn.prev = last;
277: }
278: last = insn;
279: cache = null;
280: insn.index = 0; // insn now belongs to an InsnList
281: }
282:
283: /**
284: * Adds the given instructions to the end of this list.
285: *
286: * @param insns an instruction list, which is cleared during the process.
287: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
288: * and if insn == this.
289: */
290: public void add(final InsnList insns) {
291: if (check && insns == this ) {
292: throw new IllegalArgumentException();
293: }
294: if (insns.size == 0) {
295: return;
296: }
297: size += insns.size;
298: if (last == null) {
299: first = insns.first;
300: last = insns.last;
301: } else {
302: AbstractInsnNode elem = insns.first;
303: last.next = elem;
304: elem.prev = last;
305: last = insns.last;
306: }
307: cache = null;
308: insns.removeAll(false);
309: }
310:
311: /**
312: * Inserts the given instruction at the begining of this list.
313: *
314: * @param insn an instruction, <i>which must not belong to any
315: * {@link InsnList}</i>.
316: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
317: * and if insn belongs to an instruction list.
318: */
319: public void insert(final AbstractInsnNode insn) {
320: if (check && insn.index != -1) {
321: throw new IllegalArgumentException();
322: }
323: ++size;
324: if (first == null) {
325: first = insn;
326: last = insn;
327: } else {
328: first.prev = insn;
329: insn.next = first;
330: }
331: first = insn;
332: cache = null;
333: insn.index = 0; // insn now belongs to an InsnList
334: }
335:
336: /**
337: * Inserts the given instructions at the begining of this list.
338: *
339: * @param insns an instruction list, which is cleared during the process.
340: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
341: * and if insn == this.
342: */
343: public void insert(final InsnList insns) {
344: if (check && insns == this ) {
345: throw new IllegalArgumentException();
346: }
347: if (insns.size == 0) {
348: return;
349: }
350: size += insns.size;
351: if (first == null) {
352: first = insns.first;
353: last = insns.last;
354: } else {
355: AbstractInsnNode elem = insns.last;
356: first.prev = elem;
357: elem.next = first;
358: first = insns.first;
359: }
360: cache = null;
361: insns.removeAll(false);
362: }
363:
364: /**
365: * Inserts the given instruction after the specified instruction.
366: *
367: * @param i an instruction <i>of this list</i> after which insn must be
368: * inserted.
369: * @param insn the instruction to be inserted, <i>which must not belong to
370: * any {@link InsnList}</i>.
371: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
372: * and if i does not belong to this list or if insn belongs to an
373: * instruction list.
374: */
375: public void insert(final AbstractInsnNode i,
376: final AbstractInsnNode insn) {
377: if (check && !(contains(i) && insn.index == -1)) {
378: throw new IllegalArgumentException();
379: }
380: ++size;
381: AbstractInsnNode next = i.next;
382: if (next == null) {
383: last = insn;
384: } else {
385: next.prev = insn;
386: }
387: i.next = insn;
388: insn.next = next;
389: insn.prev = i;
390: cache = null;
391: insn.index = 0; // insn now belongs to an InsnList
392: }
393:
394: /**
395: * Inserts the given instructions after the specified instruction.
396: *
397: * @param i an instruction <i>of this list</i> after which the instructions
398: * must be inserted.
399: * @param insns the instruction list to be inserted, which is cleared during
400: * the process.
401: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
402: * and if i does not belong to this list or if insns == this.
403: */
404: public void insert(final AbstractInsnNode i, final InsnList insns) {
405: if (check && !(contains(i) && insns != this )) {
406: throw new IllegalArgumentException();
407: }
408: if (insns.size == 0) {
409: return;
410: }
411: size += insns.size;
412: AbstractInsnNode ifirst = insns.first;
413: AbstractInsnNode ilast = insns.last;
414: AbstractInsnNode next = i.next;
415: if (next == null) {
416: last = ilast;
417: } else {
418: next.prev = ilast;
419: }
420: i.next = ifirst;
421: ilast.next = next;
422: ifirst.prev = i;
423: cache = null;
424: insns.removeAll(false);
425: }
426:
427: /**
428: * Removes the given instruction from this list.
429: *
430: * @param insn the instruction <i>of this list</i> that must be removed.
431: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
432: * and if insn does not belong to this list.
433: */
434: public void remove(final AbstractInsnNode insn) {
435: if (check && !contains(insn)) {
436: throw new IllegalArgumentException();
437: }
438: --size;
439: AbstractInsnNode next = insn.next;
440: AbstractInsnNode prev = insn.prev;
441: if (next == null) {
442: if (prev == null) {
443: first = null;
444: last = null;
445: } else {
446: prev.next = null;
447: last = prev;
448: }
449: } else {
450: if (prev == null) {
451: first = next;
452: next.prev = null;
453: } else {
454: prev.next = next;
455: next.prev = prev;
456: }
457: }
458: cache = null;
459: insn.index = -1; // insn no longer belongs to an InsnList
460: insn.prev = null;
461: insn.next = null;
462: }
463:
464: /**
465: * Removes all of the instructions of this list.
466: *
467: * @param mark if the instructions must be marked as no longer belonging to
468: * any {@link InsnList}.
469: */
470: private void removeAll(final boolean mark) {
471: if (mark) {
472: AbstractInsnNode insn = first;
473: while (insn != null) {
474: AbstractInsnNode next = insn.next;
475: insn.index = -1; // insn no longer belongs to an InsnList
476: insn.prev = null;
477: insn.next = null;
478: insn = next;
479: }
480: }
481: size = 0;
482: first = null;
483: last = null;
484: cache = null;
485: }
486:
487: /**
488: * Removes all of the instructions of this list.
489: */
490: public void clear() {
491: removeAll(check);
492: }
493: }
|