source: vis_dev/vis-2.3/src/ord/ordNodes.c @ 57

/**CFile***********************************************************************

  FileName    [ordNodes.c]

  PackageName [ord]

  Synopsis    [Routines to order the nodes in the TFI of the roots of a network.]

  Description [Routines to order the nodes in the TFI of the roots of a
  network. To add a new method, create a new value for the Ord_NodeMethod
  enumerated type, and add a call to the new procedure from
  OrdNetworkOrderTFIOfRoots.]

  Author      [Tom Shiple and Fabio Somenzi]

  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
  All rights reserved.

  Permission is hereby granted, without written agreement and without license
  or royalty fees, to use, copy, modify, and distribute this software and its
  documentation for any purpose, provided that the above copyright notice and
  the following two paragraphs appear in all copies of this software.

  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

******************************************************************************/

#include "ordInt.h"

static char rcsid[] UNUSED = "$Id: ordNodes.c,v 1.12 2005/04/16 06:15:25 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/
/**Struct**********************************************************************

  Synopsis    [State needed for performing variable ordering.]

  SeeAlso     [NetworkInitializeOrderingState OrderingStateFree]

******************************************************************************/
typedef struct OrderingStateStruct {
  st_table *nodeToOrderList;    /* Ntk_Node_t * to lsList; top. order of tfi
                                   nodes */
  st_table *from;               /* Ntk_Node_t * to Ntk_Node_t */
  lsGen last;                   /* insertion point */
  Ntk_Node_t *root;             /* current output */
} OrderingState_t;

/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static lsList NetworkOrderTFIOfRootsByMerging(Ntk_Network_t *network, lsList roots, Ord_ListMergeMethod method, st_table *nodeToHandle, int verbose);
static lsList NodeOrderRecursivelyByMerging(Ntk_Node_t * node, OrderingState_t * orderingState, Ord_ListMergeMethod method, int verbose);
static lsList NetworkOrderTFIOfRootsByAppending(Ntk_Network_t *network, lsList roots, st_table *nodeToHandle, int verbose);
static void NodeOrderRecursivelyByAppending(Ntk_Node_t * node, lsList orderList, st_table *nodeToHandle, int verbose);
static lsList NetworkOrderTFIOfRootsByInterleaving(Ntk_Network_t *network, lsList roots, st_table *nodeToHandle, int verbose);
static void NodeOrderRecursivelyByInterleaving(Ntk_Node_t * node, lsList orderList, st_table *nodeToHandle, OrderingState_t *orderingState, int verbose);
static OrderingState_t * NetworkInitializeOrderingState(Ntk_Network_t * network);
static void OrderingStateSetLast(Ntk_Node_t * node, st_table * nodeToHandle, OrderingState_t * orderingState);
static void OrderingStateFree(OrderingState_t * orderingState);
static lsList NodeReadOrderList(Ntk_Node_t * node, OrderingState_t * orderingState);
static void NodeSetOrderList(Ntk_Node_t * node, lsList orderList, OrderingState_t * orderingState);
static Ntk_Node_t * NodeReadFrom(Ntk_Node_t * node, OrderingState_t * orderingState);
static void NodeSetFrom(Ntk_Node_t * node, OrderingState_t * orderingState);

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis    [Orders the nodes of a network in TFI of roots.]

  Description [Orders the nodes of a network that are in the transitive fanin
  of the list of roots, including the roots themselves.  The roots are visited
  in the order given in the root list.  Combinational inputs (primary inputs,
  pseudo inputs, and latches) and constants terminate the recursion.  If you
  want a latch next state function to be a root, then the corresponding data
  input should be in the root list, not the latch itself. Note that next state
  variables are not included in the ordering; these should be added as a
  post-processing step.<p>

  The different node ordering methods are documented in the static_order
  command. If nodeMethod is Ord_NodesByDefault_c, then one of the ordering
  methods is called by default.<p>

  nodeToHandle should be an empty table created using st_init_table(st_ptrcmp,
  st_ptrhash).  For every node in the returned list, there is an entry in
  nodeToHandle mapping the node to the node's handle in the returned list.]

  SideEffects [nodeToHandle table is modified]

  SeeAlso     [Ord_NetworkOrderRoots]

******************************************************************************/
lsList
OrdNetworkOrderTFIOfRoots(
  Ntk_Network_t *network,
  lsList  roots /* of Ntk_Node_t  */,
  Ord_NodeMethod nodeOrderMethod,
  st_table *nodeToHandle /* modified */,
  int verbose)
{
  switch (nodeOrderMethod) {
    case Ord_NodesByDefault_c:
    case Ord_NodesByInterleaving_c:
      return NetworkOrderTFIOfRootsByInterleaving(network, roots,
                                                  nodeToHandle, verbose);
    case Ord_NodesByMergingLeft_c:
      return NetworkOrderTFIOfRootsByMerging(network, roots,
                                             Ord_ListMergeLeft_c,
                                             nodeToHandle, verbose);
    case Ord_NodesByMergingRight_c:
      return NetworkOrderTFIOfRootsByMerging(network, roots,
                                             Ord_ListMergeRight_c,
                                             nodeToHandle, verbose);
    case Ord_NodesByAppending_c:
      return NetworkOrderTFIOfRootsByAppending(network, roots,
                                               nodeToHandle, verbose);
    default:
      fail("unrecognized node ordering method");
      return (lsList) 0;
  }
}


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis    [Orders the nodes of a network by the merging method.]

  Description [Orders the nodes of a network by the merging method.  The
  parameters are the same as in OrdNetworkOrderTFIOfRoots.<p>
  
  This function implements an algorithm alluded to in Section 3.2 of Fujii et
  al., "Interleaving Based Variable Ordering Methods for OBDDs", ICCAD 1993,
  p. 38.  The ordering returned is a topological ordering.  The algorithm
  works as follows.  For every node, a topological ordering on the tfi nodes
  is created and stored at the node.  This is done recursively.  For leaves of
  the recursion, a trivial list of length 1 is created.  For the general case,
  the order lists at the fanins are merged together, and then the node itself
  is appended to the end of the list.  The merging is done from the highest
  priority fanin to the lowest priority, where a "merge right" or "merge
  right" is performed, depending on the value of method. Nodes with greater
  depth have higher priority.<p>

  TODO: This function is consuming more memory than is
  necessary. Specifically, a node list is computed and stored at each network
  node.  Currently, this list is not freed until the very end of the node
  ordering computation.  Instead, a reference count could be precomputed for
  each node, and when this falls to zero, the list can be immediately freed.]

  SideEffects [nodeToHandle table is modified]

  SeeAlso     [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByMerging
  OrdNetworkComputeNodeDepths]

******************************************************************************/
static lsList
NetworkOrderTFIOfRootsByMerging(
  Ntk_Network_t *network,
  lsList  roots /* list of Ntk_Node_t  */,
  Ord_ListMergeMethod method,
  st_table *nodeToHandle /* modified */,
  int verbose)
{
  lsGen            gen;
  Ntk_Node_t      *root;
  OrderingState_t *orderingState;
  lsList           orderList = lsCreate(); /* return list */

  
  /*
   * Compute and store the depth of each node in the network.  (The depth of a
   * node is stored in the undef field of the node).
   */
  OrdNetworkComputeNodeDepths(network, roots);

  /*
   * Initialize the necessary state needed for recursing through the network.
   */
  orderingState = NetworkInitializeOrderingState(network);

  /*
   * For each root, recursively order all nodes in its transitive fanin, and
   * merge this ordering into the nodes already ordered.
   */
  lsForEachItem(roots, gen, root) {
    lsList rootOrderList = NodeOrderRecursivelyByMerging(root, orderingState,
                                                         method, verbose);
    Ord_ListMergeListUsingTable(orderList, rootOrderList, nodeToHandle, method);

    if (verbose > 2) {
      /* This can generate a lot of output. */
      (void) fprintf(vis_stdout, "\nOrder list after merging node %s\n",
                     Ntk_NodeReadName(root));
      OrdNodeListWrite(vis_stdout, orderList);
    }
  }
  
  /*
   * Clean up and return the ordering list.
   */
  OrderingStateFree(orderingState);
  return orderList;
}

  
/**Function********************************************************************

  Synopsis    [Orders the fanins of a node, and then orders the node itself.]

  Description [Orders the fanins of a node, and then orders the node
  itself. The fanins of a node are visited in order of decreasing depth, and
  their orderings are merged.  The node appears in the order just after its
  fanins, yielding a topological order.  If node has already been visited,
  then simply return the order previously found.]

  SideEffects []

  SeeAlso     [OrdNetworkComputeNodeDepths NetworkOrderTFIOfRootsByMerging]

******************************************************************************/
static lsList
NodeOrderRecursivelyByMerging(
  Ntk_Node_t * node,
  OrderingState_t * orderingState,
  Ord_ListMergeMethod method,
  int verbose)
{
  lsList orderList;
  
  
  /*
   * If node has already been visited (i.e. its orderList is non-NULL), then
   * just return the orderList already computed.
   */
  orderList = NodeReadOrderList(node, orderingState);
  if (orderList != (lsList) NULL) {
    return orderList;
  }

  /*
   * Node has not yet been visited.  Create the orderList for node.
   */
  if (Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node)) {
    /*
     * Combinational inputs and constants terminate the recursion. If node is
     * one of these, then just create an empty list, to which we will add the
     * node.
     */
    orderList = lsCreate();
  }
  else if (Ntk_NodeReadNumFanins(node) == 1) {
    /*
     * If there is just one fanin, then just make a copy of the the fanin's
     * orderList. This case is distinguished from the general case for
     * efficiency. 
     */
    lsList faninOrderList = NodeOrderRecursivelyByMerging(Ntk_NodeReadFaninNode(node, 0),
                                                          orderingState,
                                                          method, verbose);
    orderList = lsCopy(faninOrderList, (lsGeneric (*) (lsGeneric)) NULL);
  }
  else {
    int       i;
    array_t  *sortedFanins;
    st_table *nodeToHandle;

    /*
     * Sort the fanins of node in decreasing order of depth.  See
     * OrdNetworkComputeNodeDepths.
     */
    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);

    /*
     * Start with an empty list for the orderList of the node.  Also, start
     * with an empty nodeToHandle table.  This table is only used locally, and
     * will be deleted below.
     */
    orderList = lsCreate();
    nodeToHandle  = st_init_table(st_ptrcmp, st_ptrhash);
    
    /*
     * Recursively visit the fanins in order of decreasing depth. The
     * nodeToHandle table keeps track of the nodes currently in orderList.
     */
    for (i = 0; i < array_n(sortedFanins); i++) {
      Ntk_Node_t *fanin          = array_fetch(Ntk_Node_t *, sortedFanins, i);
      lsList      faninOrderList = NodeOrderRecursivelyByMerging(fanin,
                                                                 orderingState,
                                                                 method, verbose);
      /*
       * Merge faninOrderList into the list of nodes already ordered.
       */
      Ord_ListMergeListUsingTable(orderList, faninOrderList, nodeToHandle, method);
    }
    array_free(sortedFanins);
    st_free_table(nodeToHandle);
  }

  /*
   * Regardless of the branch taken above, add node to the end of the
   * orderList, and set the node's orderList.
   */
  (void) lsNewEnd(orderList, (lsGeneric) node, LS_NH);
  NodeSetOrderList(node, orderList, orderingState);

  if (verbose > 2) {
    /* This can generate a lot of output. */
    (void) fprintf(vis_stdout, "\nOrder list for node %s\n", Ntk_NodeReadName(node));
    OrdNodeListWrite(vis_stdout, orderList);
  }
  
  return orderList;
}


/**Function********************************************************************

  Synopsis    [Orders the nodes of a network by the appending method.]

  Description [Orders the nodes of a network by the appending method.  The
  parameters are the same as in OrdNetworkOrderTFIOfRoots.<p>
  
  This function implements the algorithm of Malik, et al. "Logic Verification
  using Binary Decision Diagrams in a Logic Synthesis Environment," ICCAD,
  1988.  The ordering returned is a topological ordering.  The algorithm works
  as follows.  For every root, a topological ordering on the tfi nodes not
  yet ordered is generated by DFS. The ordered obtained starting from a root
  is appended to the order already found.]

  SideEffects [nodeToHandle table is modified]

  SeeAlso     [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByAppending]

******************************************************************************/
static lsList
NetworkOrderTFIOfRootsByAppending(
  Ntk_Network_t *network,
  lsList  roots /* list of Ntk_Node_t  */,
  st_table *nodeToHandle /* modified */,
  int verbose)
{
  lsGen       gen;
  Ntk_Node_t *root;
  lsList      orderList = lsCreate(); /* return list */

  
  /*
   * Compute and store the depth of each node in the network.  (The depth of a
   * node is stored in the undef field of the node).
   */
  OrdNetworkComputeNodeDepths(network, roots);

  if (verbose > 1) {
    Ntk_Node_t *node;
    (void) fprintf(vis_stdout, "\nDepths of network nodes:\n");
    Ntk_NetworkForEachNode(network, gen, node) {
      (void) fprintf(vis_stdout, "%s: depth = %ld\n", Ntk_NodeReadName(node),
                     OrdNodeReadDepth(node));
    }
  }

  /*
   * For each root, recursively order all nodes in its transitive fanin.
   */
  lsForEachItem(roots, gen, root) {
    NodeOrderRecursivelyByAppending(root, orderList, nodeToHandle, verbose);
  }
  
  return orderList;
}


/**Function********************************************************************

  Synopsis    [Orders the fanins of a node, and then orders the node itself.]

  Description [Orders the fanins of a node, and then orders the node
  itself. The fanins of a node are visited in order of decreasing depth.  The
  node appears in the order just after its fanins, yielding a topological
  order.  If node has already been visited, then simply return the order
  previously found.]

  Comment [The nodeToHandle table serves as the visited table for the DFS.]
  
  SideEffects [nodeToHandle table is modified]

  SeeAlso     [NetworkOrderTFIOfRootsByAppending OrdNetworkComputeNodeDepths]

******************************************************************************/
static void
NodeOrderRecursivelyByAppending(
  Ntk_Node_t * node,
  lsList orderList,
  st_table *nodeToHandle,
  int verbose)
{
  lsHandle handle;
  
  /*
   * If node has already been visited (i.e. its in the nodeToHandle table), then
   * just return.
   */
  if (st_is_member(nodeToHandle, (char *) node)) {
    return;
  }
  
  /*
   * Node has not yet been visited.  Recurse on the inputs, and then add node
   * to the end of the current ordering.
   */
  if (!(Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node))) {
    /*
     * Combinational inputs and constants terminate the recursion. If node is
     * not one of these, then recurse on the inputs.
     */
    int       i;
    array_t  *sortedFanins;

    /*
     * Sort the fanins of node in decreasing order of depth.  See
     * OrdNetworkComputeNodeDepths.
     */
    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);

    /*
     * Recursively visit the fanins in order of decreasing depth. The
     * nodeToHandle table keeps track of the nodes currently in orderList.
     */
    for (i = 0; i < array_n(sortedFanins); i++) {
      Ntk_Node_t *fanin = array_fetch(Ntk_Node_t *, sortedFanins, i);

      NodeOrderRecursivelyByAppending(fanin, orderList, nodeToHandle, verbose);
    }
    array_free(sortedFanins);
  }

  /*
   * Regardless of the branch taken above, add node to the end of the
   * orderList and to the nodeToHandle table.
   */
  (void) lsNewEnd(orderList, (lsGeneric) node, &handle);
  st_insert(nodeToHandle, (char *) node, (char *) handle);
}

  
/**Function********************************************************************

  Synopsis    [Orders the nodes of a network by the interleaving method.]

  Description [Orders the nodes of a network by the interleaving method.  The
  parameters are the same as in OrdNetworkOrderTFIOfRoots.<p>
  
  This function implements Algorithm 2 of Fujii, et al. "Inteleaving Based
  Variable Ordering Methods for Ordered Binary Decision Diagrams," ICCAD,
  1993.  The ordering returned is a topological ordering.  The algorithm is a
  modified DFS that keeps track of an insertion point so that variables in the
  tfi of the second and successive outputs be properly interleaved with the
  variables already ordered.]

  SideEffects [nodeToHandle table is modified]

  SeeAlso     [OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByInterleaving]

******************************************************************************/
static lsList
NetworkOrderTFIOfRootsByInterleaving(
  Ntk_Network_t *network,
  lsList roots /* list of Ntk_Node_t  */,
  st_table *nodeToHandle /* modified */,
  int verbose)
{
  lsGen       gen;
  Ntk_Node_t *root;
  lsList      orderList = lsCreate(); /* return list */
  OrderingState_t *orderingState;

  /*
   * Compute and store the depth of each node in the network.  (The depth of a
   * node is stored in the undef field of the node.)
   */
  OrdNetworkComputeNodeDepths(network, roots);

  /*
   * Initialize the state needed for recurring through the network.
   */
  orderingState = NetworkInitializeOrderingState(network);

  if (verbose > 1) {
    Ntk_Node_t *node;
    (void) fprintf(vis_stdout, "\nDepths of network nodes:\n");
    Ntk_NetworkForEachNode(network, gen, node) {
      (void) fprintf(vis_stdout, "%s: depth = %ld\n", Ntk_NodeReadName(node),
                     OrdNodeReadDepth(node));
    }
  }

  /*
   * For each root, recursively order all nodes in its transitive fanin.
   */
  lsForEachItem(roots, gen, root) {
    orderingState->root = root;
    orderingState->last = lsStart(orderList);
    NodeOrderRecursivelyByInterleaving(root, orderList, nodeToHandle,
                                       orderingState, verbose);
    lsFinish(orderingState->last);

    if (verbose > 2) {
      /* This can generate a lot of output. */
      (void) fprintf(vis_stdout, "\nOrder list after merging node %s\n",
                     Ntk_NodeReadName(root));
      OrdNodeListWrite(vis_stdout, orderList);
    }
  }

  /*
   * Clean up and return the ordering list.
   */
  OrderingStateFree(orderingState);
  return orderList;
}

  
/**Function********************************************************************

  Synopsis    [Orders the fanins of a node, and then orders the node itself.]

  Description [Orders the fanins of a node, and then orders the node
  itself. The fanins of a node are visited in order of decreasing depth.  The
  node appears in the order just after its fanins, yielding a topological
  order.  If node has already been visited, then simply update the info on
  the output from which it was last reached, and change the insertion point.]

  Comment [The nodeToHandle table serves as the visited table for the DFS.]
  
  SideEffects [nodeToHandle table is modified]

  SeeAlso     [NetworkOrderTFIOfRootsByAppending OrdNetworkComputeNodeDepths]

******************************************************************************/
static void
NodeOrderRecursivelyByInterleaving(
  Ntk_Node_t * node,
  lsList orderList,
  st_table *nodeToHandle,
  OrderingState_t *orderingState,
  int verbose)
{
  lsHandle handle;
  
  /*
   * If node has already been visited (i.e., it is in the nodeToHandle table),
   * then update the info on the output from which it was last reached,
   * and change the insertion point to this node.
   */
  if (st_is_member(nodeToHandle, (char *) node)) {
    if (NodeReadFrom(node, orderingState) != orderingState->root) {
      OrderingStateSetLast(node, nodeToHandle, orderingState);
      NodeSetFrom(node, orderingState);
    }
    return;
  }

  /*
   * Node has not yet been visited.  Recur on the inputs, and then add node
   * to the end of the current ordering.
   */
  if (!(Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node))) {
    /*
     * Combinational inputs and constants terminate the recursion. If node is
     * not one of these, then recur on the inputs.
     */
    int       i;
    array_t  *sortedFanins;

    /*
     * Sort the fanins of node in decreasing order of depth.  See
     * OrdNetworkComputeNodeDepths.
     */
    sortedFanins = array_dup(Ntk_NodeReadFanins(node)); 
    array_sort(sortedFanins, OrdNodesFromArrayCompareDepth);

    /*
     * Recursively visit the fanins in order of decreasing depth. The
     * nodeToHandle table keeps track of the nodes currently in orderList.
     */
    for (i = 0; i < array_n(sortedFanins); i++) {
      Ntk_Node_t *fanin = array_fetch(Ntk_Node_t *, sortedFanins, i);

      NodeOrderRecursivelyByInterleaving(fanin, orderList, nodeToHandle,
                                         orderingState,verbose);
    }
    array_free(sortedFanins);
  }

  /*
   * Regardless of the branch taken above, add node to orderList at the
   * insertion point and to the nodeToHandle table. Make node the new
   * insertion point.
   */
  NodeSetFrom(node, orderingState);
  (void) lsInBefore(orderingState->last, (lsGeneric) node, &handle);
  st_insert(nodeToHandle, (char *) node, (char *) handle);
  OrderingStateSetLast(node, nodeToHandle, orderingState);
}


/**Function********************************************************************

  Synopsis    [Initializes structure needed to maintain state of ordering
  routine.]

  Description [Allocates and initializes data structure needed to maintain the
  state of the variable ordering routine.]

  SideEffects []

  Comment [The node depths are not stored in a hash table of orderingState,
  because, for OrdNodesFromArrayCompareDepth, we need to be able to access the
  depth of a node given *just* the node.]
  
  SeeAlso     [OrderingStateFree]

******************************************************************************/
static OrderingState_t *
NetworkInitializeOrderingState(
  Ntk_Network_t * network)
{
  OrderingState_t *orderingState = ALLOC(OrderingState_t, 1);

  /* nodeToOrderList is used by the merging method. */
  orderingState->nodeToOrderList = st_init_table(st_ptrcmp, st_ptrhash);

  /* from, last, and root used by the interleaving method. */
  orderingState->from = st_init_table(st_ptrcmp, st_ptrhash);
  orderingState->last = NULL;
  orderingState->root = NULL;

  return orderingState;
}


/**Function********************************************************************

  Synopsis    [Updates the insertion point in orderingState.]

  Description [Updates the insertion point in orderingState. Assumes that
  node is already in nodeToHandle.]

  SideEffects []

  SeeAlso     [NetworkInitializeOrderingState]

******************************************************************************/
static void
OrderingStateSetLast(
  Ntk_Node_t * node,
  st_table * nodeToHandle,
  OrderingState_t * orderingState)
{
  lsHandle handle;
  lsGen gen;
  lsGeneric data;

  /* Dispose of the current generator. */
  lsFinish(orderingState->last);

  /* Get a handle for the current node. */
  st_lookup(nodeToHandle, node, &handle);

  /*
   * Create a new generator positioned after node and register it
   * in orderingState.
   */
  gen = lsGenHandle(handle,&data,LS_AFTER);
  orderingState->last = gen;
}

/**Function********************************************************************

  Synopsis    [Frees all memory associated with an ordering state.]

  SideEffects []

  SeeAlso     [NetworkInitializeOrderingState]

******************************************************************************/
static void
OrderingStateFree(
  OrderingState_t * orderingState)
{
  st_generator *stGen;
  lsList orderList;
  Ntk_Node_t *node;
  
  st_foreach_item(orderingState->nodeToOrderList, stGen, &node, &orderList) {
    (void) lsDestroy(orderList, (void (*) (lsGeneric)) NULL);
  }
  
  st_free_table(orderingState->nodeToOrderList);
  st_free_table(orderingState->from);
  
  FREE(orderingState);
}


/**Function********************************************************************

  Synopsis    [Gets the order list of a node.]

  Description [Gets the order list of a node.  This is a topological ordering
  of all the nodes in the transitive fanin of the node.  Returns NULL if node
  is not in the nodeToOrderList hash table of orderingState.]
  
  SideEffects []

  SeeAlso     [NodeSetOrderList]

******************************************************************************/
static lsList
NodeReadOrderList(
  Ntk_Node_t * node,
  OrderingState_t * orderingState)
{
  lsList orderList = (lsList) NULL;

  st_lookup(orderingState->nodeToOrderList, node, &orderList);
  
  return orderList;
}


/**Function********************************************************************

  Synopsis    [Sets the orderList of a node.]

  SideEffects []

  SeeAlso     [NodeReadOrderList]

******************************************************************************/
static void
NodeSetOrderList(
  Ntk_Node_t * node,
  lsList orderList,
  OrderingState_t * orderingState)
{
  st_insert(orderingState->nodeToOrderList, (char *) node, (char *) orderList);
}


/**Function********************************************************************

  Synopsis    [Gets the from root of a node.]

  Description [Gets the from node of a node.  This is the root from
  which the node was last reached during DFS. Returns NULL if node is
  not in the from hash table of orderingState.]
  
  SideEffects [none]

  SeeAlso     [NodeSetFrom]

******************************************************************************/
static Ntk_Node_t *
NodeReadFrom(
  Ntk_Node_t * node,
  OrderingState_t * orderingState)
{
  Ntk_Node_t * from = NULL;

  st_lookup(orderingState->from, node, &from);
  
  return from;
}


/**Function********************************************************************

  Synopsis    [Sets the from root of a node to the current root.]

  SideEffects [The from table of orderingState is modified.]

  SeeAlso     [NodeReadFrom]

******************************************************************************/
static void
NodeSetFrom(
  Ntk_Node_t * node,
  OrderingState_t * orderingState)
{
  st_insert(orderingState->from, (char *) node, (char *) orderingState->root);
}