1 cananian 1.1.2.4 // ReversePostOrderIterator.java, created Tue Jul 27 17:33:06 1999 by duncan
2 cananian 1.1.2.6 // Copyright (C) 1998 John Whaley <jwhaley@alum.mit.edu>
3 cananian 1.1.2.3 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 duncan 1.1.2.1 package harpoon.Analysis.DataFlow;
5 duncan 1.1.2.1
6 duncan 1.1.2.1 /**
7 duncan 1.1.2.1 * ReversePostOrderIterator
8 duncan 1.1.2.1 *
9 cananian 1.1.2.6 * @author John Whaley <jwhaley@alum.mit.edu>
10 cananian 1.4 * @version $Id: ReversePostOrderIterator.java,v 1.4 2002/04/10 02:59:11 cananian Exp $
11 duncan 1.1.2.1 */
12 duncan 1.1.2.1
13 pnkfelix 1.1.2.5 import harpoon.Analysis.BasicBlock;
14 duncan 1.1.2.1 import harpoon.Util.EnumerationIterator;
15 duncan 1.1.2.1 import harpoon.Util.Util;
16 duncan 1.1.2.1
17 duncan 1.1.2.1 import java.util.HashSet;
18 duncan 1.1.2.1 import java.util.Iterator;
19 duncan 1.1.2.1 import java.util.Set;
20 duncan 1.1.2.1 import java.util.Stack;
21 duncan 1.1.2.1
22 duncan 1.1.2.1 public class ReversePostOrderIterator implements Iterator {
23 duncan 1.1.2.1
24 duncan 1.1.2.1 public static boolean DEBUG = false;
25 duncan 1.1.2.1 public static void db(String s) { System.out.println(s); }
26 duncan 1.1.2.1
27 duncan 1.1.2.1 Stack order;
28 duncan 1.1.2.2
29 duncan 1.1.2.2 public ReversePostOrderIterator(BasicBlock start) {
30 duncan 1.1.2.1 Stack iter_stack = new Stack();
31 duncan 1.1.2.1 Stack bb_stack = new Stack();
32 duncan 1.1.2.1 order = new Stack();
33 duncan 1.1.2.1 Set done = new HashSet();
34 duncan 1.1.2.1 done.add(start); bb_stack.push(start);
35 duncan 1.1.2.1 iter_stack.push(new EnumerationIterator(start.next()));
36 duncan 1.1.2.1 while (!bb_stack.isEmpty()) {
37 cananian 1.3.2.1 assert bb_stack.size() == iter_stack.size();
38 duncan 1.1.2.1 for (Iterator i = (Iterator)iter_stack.pop(); i.hasNext();) {
39 duncan 1.1.2.1 BasicBlock bb2 = (BasicBlock)i.next();
40 duncan 1.1.2.1 if (!done.contains(bb2)) {
41 duncan 1.1.2.1 if (DEBUG) db("visiting "+bb2+" for the first time");
42 duncan 1.1.2.1 done.add(bb2);
43 duncan 1.1.2.1 bb_stack.push(bb2);
44 duncan 1.1.2.1 iter_stack.push(i);
45 duncan 1.1.2.1 i = new EnumerationIterator(bb2.next());
46 duncan 1.1.2.1 }
47 duncan 1.1.2.1 }
48 duncan 1.1.2.1 Object o = bb_stack.pop();
49 duncan 1.1.2.1 if (DEBUG) db("leaving "+o);
50 duncan 1.1.2.1 order.push(o);
51 duncan 1.1.2.1 }
52 duncan 1.1.2.1 }
53 duncan 1.1.2.1
54 duncan 1.1.2.1 public boolean hasNext() {
55 duncan 1.1.2.1 return !order.empty();
56 duncan 1.1.2.1 }
57 duncan 1.1.2.1
58 duncan 1.1.2.1 public Object next() {
59 duncan 1.1.2.1 return order.pop();
60 duncan 1.1.2.1 }
61 duncan 1.1.2.1
62 duncan 1.1.2.1 public void remove() { throw new UnsupportedOperationException(); }
63 duncan 1.1.2.1
64 duncan 1.1.2.1 public ReversePostOrderIterator copy() {
65 duncan 1.1.2.1 ReversePostOrderIterator r = new ReversePostOrderIterator();
66 duncan 1.1.2.1 r.order = (Stack)order.clone();
67 duncan 1.1.2.1 return r;
68 duncan 1.1.2.1 }
69 duncan 1.1.2.1
70 duncan 1.1.2.1 private ReversePostOrderIterator() {}
71 duncan 1.1.2.1
72 duncan 1.1.2.1 }
73 duncan 1.1.2.1
74 duncan 1.1.2.1
75 duncan 1.1.2.1
76 cananian 1.2