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 */
013package org.jikesrvm.compilers.opt.util;
014
015import java.util.Enumeration;
016
017
018/**
019 * Depth First Spanning Tree, builds topological sort of a graph consisting of SortedGraphNode.
020 */
021public 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   * @return the last sorted node
054   */
055  public static SortedGraphNode buildTopological(TopSortInterface graph, boolean forward) {
056
057    SortedGraphNode start = graph.startNode(forward);
058    TopSort sorter = new TopSort();
059    sorter.sortMarker = SortedGraphNode.getNewSortMarker(start);
060    sorter.forward = forward;
061    sorter.DFS(start, graph.numberOfNodes());
062    return sorter.lastNumberedNode;
063  }
064
065  /**
066   * Depth-first numbering in a non-recursive manner
067   * @param node the root node
068   * @param numNodes the number of nodes in this graph
069   */
070  private void DFS(SortedGraphNode node, int numNodes) {
071
072    // push node on to the emulated activation stack
073    push(node);
074    @SuppressWarnings("unchecked") // the java generic array problem
075        Enumeration<? extends SortedGraphNode>[] nodeEnum = new Enumeration[numNodes];
076
077    recurse:
078    while (!empty()) {
079
080      node = peek();
081
082      // check if we were already processing this node, if so we would have
083      // saved the state of the enumeration in the loop below
084      Enumeration<? extends SortedGraphNode> _enum = nodeEnum[node.getNumber()];
085      if (_enum == null) {
086        // mark node as visited
087        node.setSortMarker(sortMarker);
088        if (forward) {
089          _enum = node.getOutNodes();
090        } else {
091          _enum = node.getInNodes();
092        }
093      }
094
095      while (_enum.hasMoreElements()) {
096        SortedGraphNode target = _enum.nextElement();
097
098        // have we visited target?
099        if (target.getSortMarker() != sortMarker) {
100          // simulate a recursive call
101          // but first save the enumeration state for resumption later
102          nodeEnum[node.getNumber()] = _enum;
103          push(target);
104          continue recurse;
105        }
106      }
107
108      // give node the next smallest number
109      node.setSortNumber(sortNumber--, forward);
110      // link it to the previous smallest node, even if that node is null
111      node.setSortedNext(lastNumberedNode, forward);
112      // update the smallest node
113      lastNumberedNode = node;
114
115      // "Pop" from the emulated activiation stack
116      pop();
117    }
118  }
119}
120
121
122