001: /* SortedBlocks.java */
002:
003: package org.quilt.cl;
004:
005: import java.util.*;
006: import org.quilt.graph.*;
007:
008: /**
009: * Manages an index into the bytecode vertices in a method's control flow
010: * graph. The vertices (blocks) are indexed by their position in the
011: * original code. The blocks may be from different graphs in a set of
012: * nested graphs.
013: *
014: * @author < a href="jdd@dixons.org">Jim Dixon</a>
015: */
016: public class SortedBlocks {
017:
018: private ControlFlowGraph graph; // control flow graph for a method
019: private SortedMap blox; // index of vertices by position
020:
021: /** Creates an empty map. */
022: public SortedBlocks() {
023: blox = new TreeMap();
024: }
025:
026: /**
027: * Add a vertex at its bytecode position. * It is an
028: * error if there is already a vertex at this position.
029: *
030: * XXX SHOULD THROW EXCEPTION IN SUCH A CASE.
031: *
032: * @param v CodeVertex to be inserted
033: * @return True if the operation succeeds, false if something is
034: * already present at that position.
035: */
036: public boolean add(final CodeVertex v) {
037: int pos = -1;
038: if (v == null) {
039: throw new IllegalArgumentException(
040: "attempt to add null vertex");
041: }
042: pos = v.getPosition();
043: if (pos < 0) {
044: throw new IllegalArgumentException(
045: "vertex has invalid position");
046: }
047: Integer p = new Integer(pos);
048: if (blox.containsKey(p)) {
049: return false; // operation failed
050: } else {
051: blox.put(p, v);
052: return true;
053: }
054: }
055:
056: /**
057: * Find or create a code vertex starting at a given position.
058: *
059: * @param pos Byte offset in the original bytecode.
060: * @param e If the vertex must be created, Edge into which it
061: * gets inserted. Otherwise, edge target becomes
062: * the existing vertex.
063: */
064: public CodeVertex find(final int pos, ControlFlowGraph currGraph,
065: Edge e) {
066: Integer p = new Integer(pos);
067: if (blox.containsKey(p)) {
068: CodeVertex v = (CodeVertex) blox.get(p);
069: ControlFlowGraph vGraph = (ControlFlowGraph) v.getGraph();
070: Entry x;
071: if (vGraph == currGraph) {
072: e.setTarget(v); // point the edge at this vertex
073: } else if ((x = currGraph.closestEntry(vGraph)) != null) {
074: // if v is in a lower level graph, connect the edge
075: // to the netwise closest Entry
076: e.setTarget(x);
077: } else {
078: // if v is in any graph which is not this graph or a
079: // child, we get there through the current graph's Exit
080: e.setTarget(currGraph.getExit());
081: }
082: return v;
083: } else {
084: return add(pos, e);
085: }
086: }
087:
088: /**
089: * Add a vertex at bytecode offset pos along edge e. No other
090: * vertex with that bytecode offset may exist.
091: *
092: * @param pos Bytecode offset.
093: * @param e Edge along which the Vertex will be created
094: * @return Reference to the Vertex created.
095: */
096: public CodeVertex add(final int pos, final Edge e) {
097: // // DEBUG
098: // System.out.println(
099: // "- - - - - - - - - - - - - - - - - - - - - - - - - \n"
100: // + "SortedBlocks.add: pos " + pos + " along edge " + e);
101: // // END
102: Integer p = new Integer(pos);
103: Vertex source_ = e.getSource();
104: CodeVertex v;
105: if (source_ instanceof Exit) {
106: v = ((ControlFlowGraph) e.getTarget().getGraph())
107: .insertCodeVertex(e);
108: } else {
109: v = ((ControlFlowGraph) source_.getGraph())
110: .insertCodeVertex(e);
111: }
112: v.setPos(pos);
113: // v.getConnector().setData ( new ConnData() );
114: blox.put(p, v);
115: // // DEBUG
116: // System.out.println(
117: // " after insertion edge becomes " + e
118: // + "\n- - - - - - - - - - - - - - - - - - - - - - - - - ");
119: // // END
120: return v;
121: }
122:
123: /** Does a vertex exist with this bytecode offset? */
124: public boolean exists(final int pos) {
125: Integer p = new Integer(pos);
126: return blox.containsKey(p);
127: }
128:
129: /**
130: * Find the code vertex starting at a given bytecode offset.
131: * The vertex must exist. XXX Should throw an exception if
132: * it doesn't.
133: *
134: * @param pos Bytecode offset of first instruction in the block.
135: * @return The matching vertex.
136: */
137: public CodeVertex get(final int pos) {
138: Integer p = new Integer(pos);
139: if (!blox.containsKey(p)) {
140: throw new GraphBuildException(
141: "INTERNAL ERROR - no vertex at " + pos);
142: }
143: return (CodeVertex) blox.get(p);
144: }
145:
146: /**
147: * How many code vertices are currently in the index?
148: *
149: * @return The number of vertices in the index.
150: */
151: public int size() {
152: return blox.size();
153: }
154:
155: /**
156: * Standard toString(), XXX needs some work.
157: *
158: * @return Roughly formatted table of vertices.
159: */
160: public String toString() {
161: // the vertices are keyed by position
162: Iterator vertices = blox.keySet().iterator();
163: String s = "vertex position / instructions\n";
164: while (vertices.hasNext()) {
165: Integer position = (Integer) vertices.next();
166: CodeVertex v = (CodeVertex) blox.get(position);
167: s += " " + v.getIndex() + " " + position + "\n" + v // possibly problems here ...
168: ;
169: }
170: return s;
171: }
172: }
|