View Javadoc

1   // PriorityQueueSolver.java, created Thu Apr 25 16:32:26 2002 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Dataflow;
5   
6   import java.util.Collection;
7   import java.util.HashMap;
8   import java.util.Iterator;
9   import java.util.List;
10  import java.util.Map;
11  import jwutil.collections.BinHeapPriorityQueue;
12  import jwutil.collections.MapFactory;
13  import jwutil.collections.MaxPriorityQueue;
14  import jwutil.graphs.Graph;
15  import jwutil.graphs.Traversals;
16  
17  /***
18   * PriorityQueueSolver
19   * 
20   * @author John Whaley
21   * @version $Id: PriorityQueueSolver.java 1931 2004-09-22 22:17:47Z joewhaley $
22   */
23  public class PriorityQueueSolver extends WorklistSolver {
24  
25      /*** Map from nodes to their (integer) priorities. */
26      protected Map nodesToPriorities;
27      /*** Priority-queue implementation of the worklist. */
28      protected MaxPriorityQueue worklist;
29  
30      public PriorityQueueSolver(MapFactory f) {
31          super(f);
32      }
33      public PriorityQueueSolver() {
34          super();
35      }
36  
37      /* (non-Javadoc)
38       * @see joeq.Compiler.Dataflow.Solver#initialize(Compiler.Dataflow.Problem, Util.Graphs.Graph)
39       */
40      public void initialize(Problem p, Graph graph) {
41          this.initialize(p, graph, Traversals.reversePostOrder(graph.getNavigator(), graph.getRoots()));
42      }
43      
44      /*** Initializes this solver with the given dataflow problem, graph, and
45       * traversal order.
46       * 
47       * @see joeq.Compiler.Dataflow.Solver#initialize(joeq.Compiler.Dataflow.Problem, jwutil.graphs.Graph)
48       */
49      public void initialize(Problem p, Graph graph, List traversalOrder) {
50          super.initialize(p, graph);
51          initializeTraversalOrder(traversalOrder);
52      }
53      
54      protected void initializeTraversalOrder(List order) {
55          int n = order.size();
56          this.nodesToPriorities = new HashMap();
57          Iterator i = order.iterator();
58          while (i.hasNext()) {
59              Object o = i.next();
60              nodesToPriorities.put(o, new Integer(n));
61              --n;
62          }
63          if (TRACE) System.out.println("Priorities: "+nodesToPriorities);
64      }
65  
66      /* (non-Javadoc)
67       * @see joeq.Compiler.Dataflow.Solver#allLocations()
68       */
69      public Iterator allLocations() {
70          return nodesToPriorities.keySet().iterator();
71      }
72  
73      /* (non-Javadoc)
74       * @see joeq.Compiler.Dataflow.WorklistSolver#initializeWorklist()
75       */
76      protected void initializeWorklist() {
77          worklist = new BinHeapPriorityQueue(nodesToPriorities.size());
78          for (Iterator i = nodesToPriorities.entrySet().iterator(); i.hasNext(); ) {
79              Map.Entry e = (Map.Entry) i.next();
80              Object o = e.getKey();
81              if (boundaries.contains(o)) continue;
82              int v = ((Integer) e.getValue()).intValue();
83              worklist.insert(o, v);
84          }
85      }
86  
87      /* (non-Javadoc)
88       * @see joeq.Compiler.Dataflow.WorklistSolver#hasNext()
89       */
90      protected boolean hasNext() {
91          return !worklist.isEmpty();
92      }
93  
94      /* (non-Javadoc)
95       * @see joeq.Compiler.Dataflow.WorklistSolver#pull()
96       */
97      protected Object pull() {
98          return worklist.deleteMax();
99      }
100 
101     /* (non-Javadoc)
102      * @see joeq.Compiler.Dataflow.WorklistSolver#pushAll(java.util.Collection)
103      */
104     protected void pushAll(Collection c) {
105         for (Iterator i = c.iterator(); i.hasNext(); ) {
106             Object o = i.next();
107             int v = ((Integer) nodesToPriorities.get(o)).intValue();
108             worklist.insert(o, v);
109         }
110     }
111     
112 }