src/ord/ordRoots.c

Go to the documentation of this file.

#include "ordInt.h"

static char rcsid[] UNUSED = "$Id: ordRoots.c,v 1.7 2002/08/27 08:43:16 fabio Exp $";

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


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


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


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


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


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


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

lsList
Ord_NetworkOrderRoots(
  Ntk_Network_t *network,
  Ord_RootMethod rootMethod,
  lsList partialOrder,
  boolean verbose)
{
  lsList rootOrderList;
  
  switch (rootMethod) {
    case Ord_RootsByDepth_c:
      rootOrderList = OrdNetworkOrderRootsByDepth(network, verbose); 
      break;
    case Ord_RootsByPerm_c:
      rootOrderList = OrdNetworkOrderRootsByPerm(network, verbose);
      break;
    case Ord_RootsByDefault_c:
      /*
       * RootByPerm method is cubic in the number of latches, so use it by
       * default only if the number of latches is not too large (30 is somewhat
       * arbitrary).
       */
      if (Ntk_NetworkReadNumLatches(network) < 30) {
        rootOrderList = OrdNetworkOrderRootsByPerm(network, verbose);
      }
      else {
        rootOrderList = OrdNetworkOrderRootsByDepth(network, verbose);
      }
      break;
    default:
      fail("unrecognized root order method");
  }

  /*
   * If a partial order is supplied, merge (left, arbitrarily) the computed
   * order into the supplied order, to get a total ordering on all of the
   * roots.
   */
  if (partialOrder != (lsList) NULL) {
    lsList partialOrderCopy = lsCopy(partialOrder,
                                     (lsGeneric (*) (lsGeneric)) NULL);

    Ord_ListMergeList(partialOrderCopy, rootOrderList, Ord_ListMergeLeft_c);
    (void) lsDestroy(rootOrderList, (void (*) (lsGeneric)) NULL);
    return partialOrderCopy;
  }
  else {
    return rootOrderList;
  }
}

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

lsList
OrdNetworkOrderRootsByDepth(
  Ntk_Network_t *network,
  boolean verbose)
{
  lsGen       gen;
  Ntk_Node_t *node;
  st_table   *processedTable = st_init_table(st_ptrcmp, st_ptrhash);
  lsList dataInputs = lsCreate();
  lsList otherCombOuts = lsCreate();
  lsList combOutputs = Ntk_NetworkReadCombOutputs(network);

  /*
   * A node can drive more than one latch data input, latch initial input,
   * or primary output. Use a hash table to ensure that no node appears twice
   * across the two lists.
   */
  Ntk_NetworkForEachCombOutput(network, gen, node) {
    if (Ntk_NodeTestIsLatchDataInput(node)) {
      OrdNodeAddToList(dataInputs, processedTable, node);
    }
    else {
      OrdNodeAddToList(otherCombOuts, processedTable, node);
    }
  }
  st_free_table(processedTable);

  /* Compute depth of all combinational outputs. */
  OrdNetworkComputeNodeDepths(network, combOutputs);

  /* Sort each list independently. */
  lsSort(dataInputs, OrdNodesFromListCompareDepth);
  lsSort(otherCombOuts, OrdNodesFromListCompareDepth);

  Ord_ListAppendList(dataInputs, otherCombOuts);
  (void) lsDestroy(otherCombOuts, (void (*) (lsGeneric)) NULL);
  
  return dataInputs;
}

void
OrdNodeAddToList(
  lsList nodeList,
  st_table *nodeTable,
  Ntk_Node_t *node)
{
  if (!st_is_member(nodeTable, (char *) node)) {
    st_insert(nodeTable, (char *) node, NIL(char));
    (void) lsNewEnd(nodeList, (lsGeneric) node, LS_NH);
  }
}



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