001    /*
002     *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003     *
004     *  This file is licensed to You under the Eclipse Public License (EPL);
005     *  You may not use this file except in compliance with the License. You
006     *  may obtain a copy of the License at
007     *
008     *      http://www.opensource.org/licenses/eclipse-1.0.php
009     *
010     *  See the COPYRIGHT.txt file distributed with this work for information
011     *  regarding copyright ownership.
012     */
013    package org.jikesrvm.compilers.opt.util;
014    
015    import java.util.Enumeration;
016    
017    
018    /**
019     * Depth First Spanning Tree, builds topological sort of a graph consisting of SortedGraphNode.
020     */
021    public final class TopSort extends Stack<SortedGraphNode> {
022    
023      /**
024       * the "visited" marker to use
025       */
026      private int sortMarker;
027    
028      /**
029       * the next "number" to give out
030       */
031      private int sortNumber;
032    
033      /**
034       * the last node to get a number
035       */
036      private SortedGraphNode lastNumberedNode;
037    
038      /**
039       * are we processing the graph in forward order?
040       */
041      private boolean forward;
042    
043      /**
044       * Prevent instantiation
045       */
046      private TopSort() { }
047    
048      /**
049       * @param graph the graph
050       * @param forward should we treat edges as forward?
051       *  This is the second version of the implementation
052       *   (see CVS file for older one)
053       */
054      public static SortedGraphNode buildTopological(TopSortInterface graph, boolean forward) {
055    
056        SortedGraphNode start = graph.startNode(forward);
057        TopSort sorter = new TopSort();
058        sorter.sortMarker = SortedGraphNode.getNewSortMarker(start);
059        sorter.forward = forward;
060        sorter.DFS(start, graph.numberOfNodes());
061        return sorter.lastNumberedNode;
062      }
063    
064      /**
065       * Depth-first numbering in a non-recursive manner
066       * @param node the root node
067       * @param numNodes the number of nodes in this graph
068       */
069      private void DFS(SortedGraphNode node, int numNodes) {
070    
071        // push node on to the emulated activation stack
072        push(node);
073        @SuppressWarnings("unchecked") // the java generic array problem
074            Enumeration<? extends SortedGraphNode>[] nodeEnum = new Enumeration[numNodes];
075    
076        recurse:
077        while (!empty()) {
078    
079          node = peek();
080    
081          // check if we were already processing this node, if so we would have
082          // saved the state of the enumeration in the loop below
083          Enumeration<? extends SortedGraphNode> _enum = nodeEnum[node.getNumber()];
084          if (_enum == null) {
085            // mark node as visited
086            node.setSortMarker(sortMarker);
087            if (forward) {
088              _enum = node.getOutNodes();
089            } else {
090              _enum = node.getInNodes();
091            }
092          }
093    
094          while (_enum.hasMoreElements()) {
095            SortedGraphNode target = _enum.nextElement();
096    
097            // have we visited target?
098            if (target.getSortMarker() != sortMarker) {
099              // simulate a recursive call
100              // but first save the enumeration state for resumption later
101              nodeEnum[node.getNumber()] = _enum;
102              push(target);
103              continue recurse;
104            }
105          }
106    
107          // give node the next smallest number
108          node.setSortNumber(sortNumber--, forward);
109          // link it to the previous smallest node, even if that node is null
110          node.setSortedNext(lastNumberedNode, forward);
111          // update the smallest node
112          lastNumberedNode = node;
113    
114          // "Pop" from the emulated activiation stack
115          pop();
116        }
117      }
118    }
119    
120    
121