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
020     * March 14, 1998
021     * Builds topological sort of a graph consisting of SortedGraphNode.
022     */
023    public final class TopSort extends Stack<SortedGraphNode> {
024    
025      /**
026       * the "visited" marker to use
027       */
028      private int sortMarker;
029    
030      /**
031       * the next "number" to give out
032       */
033      private int sortNumber;
034    
035      /**
036       * the last node to get a number
037       */
038      private SortedGraphNode lastNumberedNode;
039    
040      /**
041       * are we processing the graph in forward order?
042       */
043      private boolean forward;
044    
045      /**
046       * Prevent instantiation
047       */
048      private TopSort() { }
049    
050      /**
051       * @param graph the graph
052       * @param forward should we treat edges as forward?
053       *  This is the second version of the implementation
054       *   (see CVS file for older one)
055       */
056      public static SortedGraphNode buildTopological(TopSortInterface graph, boolean forward) {
057    
058        SortedGraphNode start = graph.startNode(forward);
059        TopSort sorter = new TopSort();
060        sorter.sortMarker = SortedGraphNode.getNewSortMarker(start);
061        sorter.forward = forward;
062        sorter.DFS(start, graph.numberOfNodes());
063        return sorter.lastNumberedNode;
064      }
065    
066      /**
067       * Depth-first numbering in a non-recursive manner
068       * @param node the root node
069       * @param numNodes the number of nodes in this graph
070       */
071      private void DFS(SortedGraphNode node, int numNodes) {
072    
073        // push node on to the emulated activation stack
074        push(node);
075        @SuppressWarnings("unchecked") // the java generic array problem
076            Enumeration<? extends SortedGraphNode>[] nodeEnum = new Enumeration[numNodes];
077    
078        recurse:
079        while (!empty()) {
080    
081          node = peek();
082    
083          // check if we were already processing this node, if so we would have
084          // saved the state of the enumeration in the loop below
085          Enumeration<? extends SortedGraphNode> _enum = nodeEnum[node.getNumber()];
086          if (_enum == null) {
087            // mark node as visited
088            node.setSortMarker(sortMarker);
089            if (forward) {
090              _enum = node.getOutNodes();
091            } else {
092              _enum = node.getInNodes();
093            }
094          }
095    
096          while (_enum.hasMoreElements()) {
097            SortedGraphNode target = _enum.nextElement();
098    
099            // have we visited target?
100            if (target.getSortMarker() != sortMarker) {
101              // simulate a recursive call
102              // but first save the enumeration state for resumption later
103              nodeEnum[node.getNumber()] = _enum;
104              push(target);
105              continue recurse;
106            }
107          }
108    
109          // give node the next smallest number
110          node.setSortNumber(sortNumber--, forward);
111          // link it to the previous smallest node, even if that node is null
112          node.setSortedNext(lastNumberedNode, forward);
113          // update the smallest node
114          lastNumberedNode = node;
115    
116          // "Pop" from the emulated activiation stack
117          pop();
118        }
119      }
120    }
121    
122    
123