11 bindings=new Vector();
12 binding=new Hashtable();
15 public String toString() {
17 for(int i=0;i<bindings.size();i++)
18 st+=bindings.get(i).toString()+"\n";
19 st+="---------------------\n";
20 for(int i=0;i<updates.size();i++)
21 st+=updates.get(i).toString()+"\n";
25 public void addBindings(Vector v) {
26 for (int i=0;i<v.size();i++) {
27 addBinding((Binding)v.get(i));
31 public boolean checkupdates() {
32 if (!checkconflicts()) /* Do we have conflicting concrete updates */
34 if (computeordering()) /* Ordering exists */
39 private boolean computeordering() {
40 /* Build dependency graph between updates */
41 HashSet graph=new HashSet();
42 Hashtable mapping=new Hashtable();
43 for(int i=0;i<updates.size();i++) {
44 Updates u=(Updates)updates.get(i);
45 GraphNode gn=new GraphNode(String.valueOf(i),u);
49 for(int i=0;i<updates.size();i++) {
50 Updates u1=(Updates)updates.get(i);
53 for(int j=0;j<updates.size();j++) {
54 Updates u2=(Updates)updates.get(j);
57 Descriptor d=u1.getDescriptor();
58 if (u2.getRightExpr().usesDescriptor(d)) {
59 /* Add edge for dependency */
60 GraphNode gn1=(GraphNode) mapping.get(u1);
61 GraphNode gn2=(GraphNode) mapping.get(u2);
62 GraphNode.Edge e=new GraphNode.Edge("dependency",gn2);
68 if (!GraphNode.DFS.depthFirstSearch(graph)) /* DFS & check for acyclicity */
71 TreeSet topologicalsort = new TreeSet(new Comparator() {
72 public boolean equals(Object obj) { return false; }
73 public int compare(Object o1, Object o2) {
74 GraphNode g1 = (GraphNode) o1;
75 GraphNode g2 = (GraphNode) o2;
76 return g2.getFinishingTime() - g1.getFinishingTime();
79 topologicalsort.addAll(graph);
80 Vector sortedvector=new Vector();
81 for(Iterator sort=topologicalsort.iterator();sort.hasNext();) {
82 GraphNode gn=(GraphNode)sort.next();
83 sortedvector.add(gn.getOwner());
85 updates=sortedvector; //replace updates with the sorted array
89 private boolean checkconflicts() {
90 Set toremove=new HashSet();
91 for(int i=0;i<updates.size();i++) {
92 Updates u1=(Updates)updates.get(i);
93 for(int j=0;j<updates.size();j++) {
94 Updates u2=(Updates)updates.get(j);
97 if (u1.isAbstract()||u2.isAbstract())
98 continue; /* Abstract updates are already accounted for by graph */
99 if (u1.getDescriptor()!=u2.getDescriptor())
100 continue; /* No interference - different descriptors */
102 if ((u1.getOpcode()==Opcode.GT||u1.getOpcode()==Opcode.GE)&&
103 (u2.getOpcode()==Opcode.GT||u2.getOpcode()==Opcode.GE))
104 continue; /* Can be satisfied simultaneously */
106 if ((u1.getOpcode()==Opcode.LT||u1.getOpcode()==Opcode.LE)&&
107 (u2.getOpcode()==Opcode.LT||u2.getOpcode()==Opcode.LE))
109 if ((u1.getOpcode()==u2.getOpcode())&&
110 u1.isExpr()&&u2.isExpr()&&
111 u1.getRightExpr().equals(null, u2.getRightExpr())) {
112 /*We'll remove the second occurence*/
120 /* Handle = or != NULL */
121 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
122 ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
123 (((u1.isExpr()&&u1.getRightExpr().isNull())&&(!u2.isExpr()||u2.getRightExpr().isNonNull()))
124 ||((!u1.isExpr()||u1.getRightExpr().isNonNull())&&(u2.isExpr()&&u2.getRightExpr().isNull())))) {
125 if (u1.getOpcode()==Opcode.NE)
132 /* Handle = and != to different constants */
133 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
134 ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
135 (u1.isExpr()&&u1.getRightExpr() instanceof LiteralExpr)&&
136 (u2.isExpr()&&u2.getRightExpr() instanceof LiteralExpr)&&
137 !u1.getRightExpr().equals(u2.getRightExpr())) {
138 if (u1.getOpcode()==Opcode.NE)
145 /* Compatible operations < & <= */
146 if (((u1.getOpcode()==Opcode.LT)||(u1.getOpcode()==Opcode.LE))&&
147 ((u2.getOpcode()==Opcode.LT)||(u2.getOpcode()==Opcode.LE)))
150 /* Compatible operations > & >= */
151 if (((u1.getOpcode()==Opcode.GT)||(u1.getOpcode()==Opcode.GE))&&
152 ((u2.getOpcode()==Opcode.GT)||(u2.getOpcode()==Opcode.GE)))
157 /* Equality & Comparisons */
160 return false; /* They interfere */
163 updates.removeAll(toremove);
167 public void addBinding(Binding b) {
169 binding.put(b.getVar(),b);
172 public Binding getBinding(VarDescriptor vd) {
173 if (binding.containsKey(vd))
174 return (Binding)binding.get(vd);
179 public void addUpdate(Updates u) {
183 public int numUpdates() {
184 return updates.size();
186 public Updates getUpdate(int i) {
187 return (Updates)updates.get(i);