VIS
Enumerations | Functions | Variables

src/ntk/ntkGraph.c File Reference

#include "ntkInt.h"
Include dependency graph for ntkGraph.c:

Go to the source code of this file.

Enumerations

enum  DfsColor { dfsWhite_c, dfsGrey_c, dfsBlack_c }

Functions

static void RegionFindNodesRecursively (Ntk_Node_t *node, st_table *leaves, st_table *result)
static boolean NodeTestCannotReachCycle (Ntk_Node_t *node)
static boolean NodeTestCoveredByLeaves (Ntk_Node_t *node, st_table *leaves, st_table *visited)
static DfsColor NodeReadColor (Ntk_Node_t *node)
static void NodeSetColor (Ntk_Node_t *node, DfsColor color)
static void NodeSetTfoLatchList (Ntk_Node_t *node, lsList tfoLatchList)
static lsList NodeReadTfoLatchList (Ntk_Node_t *node)
static void NodeFreeTfoLatchList (Ntk_Node_t *node)
static void ListAppendList (lsList list1, lsList list2)
static lsList NodeComputeTfoLatchList (Ntk_Node_t *node)
static void NodeRecursivelyComputeTransitiveFaninNodes (Ntk_Node_t *node, st_table *resultTable, boolean stopAtLatches)
static void NodeComputeTopologicalOrderRecursively (Ntk_Node_t *node, st_table *leafNodesTable, lsList topologicalNodeList)
static void NodeComputeTransitiveFaninNodes (Ntk_Node_t *node, st_table *resultTable, boolean stopAtLatches)
array_t * Ntk_NodeComputeTransitiveFanoutNodes (array_t *nodeArray, int depth)
array_t * Ntk_NodeComputeTransitiveFanInputNodes (array_t *nodeArray, int depth)
array_t * Ntk_NodeComputeTransitiveFaninNodes (Ntk_Network_t *network, array_t *nodeArray, boolean stopAtLatches, boolean combInputsOnly)
array_t * Ntk_NodeComputeCombinationalSupport (Ntk_Network_t *network, array_t *nodeArray, boolean stopAtLatches)
st_table * Ntk_RegionFindNodes (array_t *roots, st_table *leaves)
st_table * Ntk_NetworkComputeLatchDependencies (Ntk_Network_t *network)
boolean Ntk_NetworkTestIsAcyclic (Ntk_Network_t *network)
boolean Ntk_NetworkTestLeavesCoverSupportOfRoots (Ntk_Network_t *network, array_t *roots, st_table *leaves)
lsList Ntk_NetworkComputeTopologicalOrder (Ntk_Network_t *network, array_t *rootNodesArray, st_table *leafNodesTable)

Variables

static char rcsid[] UNUSED = "$Id: ntkGraph.c,v 1.11 2005/04/16 04:24:15 fabio Exp $"

Enumeration Type Documentation

enum DfsColor

Enum************************************************************************

Synopsis [Used to keep track of the state of a node during depth first search.required]

Enumerator:
dfsWhite_c 
dfsGrey_c 
dfsBlack_c 

Definition at line 46 of file ntkGraph.c.

             {
  dfsWhite_c,   /* unvisited node */
  dfsGrey_c,    /* node on "stack" */
  dfsBlack_c    /* node completely visited */
} DfsColor;

Function Documentation

static void ListAppendList ( lsList  list1,
lsList  list2 
) [static]

Function********************************************************************

Synopsis [Appends list2 to list1.]

Description [Adds the elements of list2 to the end of list1. The elements of list2 are not copied. If an element of list2 already exists in list1, then it is not added to the end of list1. List2 is not changed by this operation.]

SideEffects [List1 is modified.]

SeeAlso []

Definition at line 765 of file ntkGraph.c.

{
  lsGen      gen;
  lsGeneric  data;
  st_table  *table1 = st_init_table(st_ptrcmp, st_ptrhash);
  
  /*
   * Load a hash table mapping each item in list1 to NULL.
   */
  gen = lsStart(list1);
  while (lsNext(gen, &data, LS_NH) == LS_OK) {
    st_insert(table1, (char *) data, (char *) NULL);
  }
  (void) lsFinish(gen);

  /*
   * For each item in list2, if it's not already present in list1, then add it
   * to the end of list1.
   */
  lsForEachItem(list2, gen, data) {
    if (st_is_member(table1, (char *) data) == 0) {
      lsNewEnd(list1, data, LS_NH);
    }
  }
  st_free_table(table1);
}

Here is the caller graph for this function:

static lsList NodeComputeTfoLatchList ( Ntk_Node_t *  node) [static]

Function********************************************************************

Synopsis [Computes the set of latches in the TFO of a node.]

Description [Computes the set of latches in the TFO of a node. If there are no latches in the TFO, then an empty list is returned. In the special case where the node is itself a latch, then a list containing just the node is returned; this is one of the terminal cases of the recursion. The other terminal case is a node with no immediate fanouts.]

SideEffects []

Definition at line 809 of file ntkGraph.c.

{
  lsList tfoLatchList = NodeReadTfoLatchList(node);

  /*
   * If node already has a non-NULL tfoLatchList, then just return it (this
   * can happen if the node was already visited via one of its other
   * fanins). Otherwise, create an empty list and fill it appropriately.
   */
  if (tfoLatchList != (lsList) NULL) {
    return (tfoLatchList);
  }
  else {
    tfoLatchList = lsCreate();

    if (Ntk_NodeTestIsLatch(node)) {
      /*
       * Special case; terminal condition.
       */
      lsNewEnd(tfoLatchList, (lsGeneric) node, LS_NH);
    }
    else {
      int         i;
      Ntk_Node_t *fanout;
      
      /*
       * Get the latches in the TFO of each fanout of node, and accumulate into
       * a list.
       */
      Ntk_NodeForEachFanout(node, i, fanout) {
        lsList fanoutTfoLatchList = NodeComputeTfoLatchList(fanout);

        ListAppendList(tfoLatchList, fanoutTfoLatchList);
      }
    }

    /*
     * Store the list with the node, then return the list.
     */
    NodeSetTfoLatchList(node, tfoLatchList);
    return (tfoLatchList);    
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void NodeComputeTopologicalOrderRecursively ( Ntk_Node_t *  node,
st_table *  leafNodesTable,
lsList  topologicalNodeList 
) [static]

Function********************************************************************

Synopsis [Recursively performs the depth-first traversal of the network starting at the given node.]

Description [Recursively performs the depth-first traversal of the network starting at the given node.]

SideEffects []

SeeAlso []

Definition at line 912 of file ntkGraph.c.

{
  int i;
  Ntk_Node_t *fanin;
  
  if (NodeReadColor(node) == dfsBlack_c){
    /* Has already been put in the list. */
    return;
  }
  if (NodeReadColor(node) == dfsGrey_c){
    /* Indicates that this node is currently being processed (possibly a
       combinational loop). */
    return;
  }
  if (st_is_member(leafNodesTable, (char *)node)== 0){
    NodeSetColor(node, dfsGrey_c);
    Ntk_NodeForEachFanin(node, i, fanin){
      NodeComputeTopologicalOrderRecursively(fanin, leafNodesTable,
                                             topologicalNodeList);
    }
  }
  NodeSetColor(node, dfsBlack_c);
  lsNewEnd(topologicalNodeList, (lsGeneric)node, LS_NH);
  return;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void NodeComputeTransitiveFaninNodes ( Ntk_Node_t *  node,
st_table *  resultTable,
boolean  stopAtLatches 
) [static]

Function********************************************************************

Synopsis [Computes the set of nodes in the TFI of the node.]

Description [Computes the set of nodes in the TFI of the node. If stopAtLatches is TRUE, the search terminates at combinational inputs which are latches; otherwise it continues, and the search terminates only at primary inputs and pseudo inputs.]

SideEffects []

Definition at line 953 of file ntkGraph.c.

{
  int i;
  Ntk_Node_t * fanin;
  
  /* test if we have already started processing this node */
  if (st_is_member(resultTable, node))
    return;

  st_insert(resultTable, node, (char *)(long)2);

  if (Ntk_NodeTestIsInput(node) || (stopAtLatches && Ntk_NodeTestIsLatch(node)))
    return;

  Ntk_NodeForEachFanin(node, i, fanin) {
    NodeComputeTransitiveFaninNodes(fanin, resultTable, stopAtLatches);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void NodeFreeTfoLatchList ( Ntk_Node_t *  node) [static]

Function********************************************************************

Synopsis [Frees the tfoLatchList of a node.]

Description [If the node has a non-NULL tfoLatchList, then frees the list and sets the tfoLatchList of node to NULL; else, does nothing.]

SideEffects []

SeeAlso [NodeReadTfoLatchList NodeSetTfoLatchList ]

Definition at line 739 of file ntkGraph.c.

{
  lsList tfoLatchList = NodeReadTfoLatchList(node);

  if (tfoLatchList != (lsList) NULL) {
    (void) lsDestroy(tfoLatchList, (void (*) (lsGeneric)) NULL);
    Ntk_NodeSetUndef(node, (void *) NULL);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static DfsColor NodeReadColor ( Ntk_Node_t *  node) [static]

Function********************************************************************

Synopsis [Gets the color of a node.]

SideEffects []

SeeAlso [NodeSetColor]

Definition at line 666 of file ntkGraph.c.

{
  return ((DfsColor) (long) Ntk_NodeReadUndef(node));
}

Here is the call graph for this function:

Here is the caller graph for this function:

static lsList NodeReadTfoLatchList ( Ntk_Node_t *  node) [static]

Function********************************************************************

Synopsis [Gets the TfoLatchList of a node.]

SideEffects []

SeeAlso [NodeSetTfoLatchList NodeFreeTfoLatchList]

Definition at line 719 of file ntkGraph.c.

{
  return ((lsList) Ntk_NodeReadUndef(node));
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void NodeRecursivelyComputeTransitiveFaninNodes ( Ntk_Node_t *  node,
st_table *  resultTable,
boolean  stopAtLatches 
) [static]

Function********************************************************************

Synopsis [Computes the set of combinational inputs in the TFI of the node.]

Description [Computes the set of combinational inputs in the TFI of the node. If stopAtLatches is TRUE, the search terminates at combinational inputs which are latches; otherwise it continues, and the search terminates only at primary inputs and pseudo inputs.]

SideEffects []

Definition at line 869 of file ntkGraph.c.

{
  int i;
  Ntk_Node_t * fanin;

  /* test if we have already started processing this node */
  if ( NodeReadColor( node ) == dfsBlack_c ) {
        return;
  }
  NodeSetColor( node, dfsBlack_c );

  if ( Ntk_NodeTestIsCombInput( node ) ) {
        st_insert( resultTable, (char *) node, (char *) 0 );
  }

  if ( Ntk_NodeTestIsInput(node) || ((stopAtLatches == TRUE)&&(Ntk_NodeTestIsLatch(node))) ) {
        return;
  }

  Ntk_NodeForEachFanin( node, i, fanin ) {
        NodeRecursivelyComputeTransitiveFaninNodes( fanin, resultTable, stopAtLatches );
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void NodeSetColor ( Ntk_Node_t *  node,
DfsColor  color 
) [static]

Function********************************************************************

Synopsis [Sets the color of a node.]

SideEffects []

SeeAlso [NodeReadColor]

Definition at line 683 of file ntkGraph.c.

{
  Ntk_NodeSetUndef(node, (void *) (long) color);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void NodeSetTfoLatchList ( Ntk_Node_t *  node,
lsList  tfoLatchList 
) [static]

Function********************************************************************

Synopsis [Sets the tfoLatchList of a node.]

SideEffects []

SeeAlso [NodeReadTfoLatchList NodeFreeTfoLatchList]

Definition at line 701 of file ntkGraph.c.

{
  Ntk_NodeSetUndef(node, (void *) tfoLatchList);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean NodeTestCannotReachCycle ( Ntk_Node_t *  node) [static]

Function********************************************************************

Synopsis [Returns 1 if node cannot reach a cycle, else returns 0.]

Description [Visits a node, and recursively all of its children, to determine if the node can reach a combinational cycle. If it cannot, the function return 1, else it returns 0. If a cycle is found, then a message is written to error_string.]

SideEffects []

Definition at line 526 of file ntkGraph.c.

{
  Ntk_Node_t *fanout;
  int i;

  /*
   * Set the color of node to grey to indicate that it is on the "stack".
   */
  NodeSetColor(node, dfsGrey_c);

  Ntk_NodeForEachFanout(node, i, fanout) {
    /*
     * Traverse fanout if it is *not* a latch; latches break combinational cycles.
     */
    if (Ntk_NodeTestIsLatch(fanout) == 0) {
      DfsColor fanoutColor = NodeReadColor(fanout);

      /* 
       * If fanout is white, it has not been visited yet, so visit it, and 
       * break the search if it can reach a cycle.  Else if fanout is grey, it 
       * means that fanout is also on the stack, so a cycle has been found; 
       * thus break.  Else, the fanout is black, and there is nothing to do.
       */
      if (fanoutColor == dfsWhite_c) {
        if (NodeTestCannotReachCycle(fanout) == 0) {
          return (0);
        }
      }
      else if (fanoutColor == dfsGrey_c) {
        error_append("(");
        error_append(Ntk_NodeReadName(node));
        error_append(", ");
        error_append(Ntk_NodeReadName(fanout));
        error_append(")");
        return (0);
      } 
    }
  }

  /*
   * Set the color of node to black to indicate that it has been visited.
   */
  NodeSetColor(node, dfsBlack_c);
  
  /*
   * No cycles found from node.
   */
  return (1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean NodeTestCoveredByLeaves ( Ntk_Node_t *  node,
st_table *  leaves,
st_table *  visited 
) [static]

Function********************************************************************

Synopsis [Returns FALSE if the support of node contains a combinational input that is not a leaf, otherwise returns TRUE.]

Description [The function does a DFS starting from node, never going beyond a leaf or a node already visited. If it reaches a combinational input that is not a leaf it returns FALSE. If this doesn't happen for all the fanins of the node, then TRUE is returned.]

SideEffects []

SeeAlso [Ntk_NetworkTestLeavesCoverSupportOfRoots]

Definition at line 594 of file ntkGraph.c.

{
  int         i;
  Ntk_Node_t *fanin;

  /*
   * If node has already been visited, just return.  Else, mark it as
   * visited. Note that it is important to mark it as visited BEFORE recursing,
   * in case combinational cycles are present.
   */
  if (st_is_member(visited, (char *) node)) {
    return TRUE;
  }
  else {
    st_insert(visited, (char *) node, NIL(char));
  }

  if (st_is_member(leaves, (char *) node)) {
    /*
     * Positive termination of recursion: if node is a leaf, then everything
     * is fine.
     */ 
    return TRUE;
  }
  else {
    /* Node is not a leaf. */
    if (Ntk_NodeTestIsCombInput(node)) {
      /*
       * Negative termination of recursion: a combinational input was reached
       * without seeing a leaf.
       */ 
      error_append("Node ");
      error_append(Ntk_NodeReadName(node));
      error_append(" found in the support of node ");
      return FALSE;
    }
    else {
      /*
       * Node is not a leaf nor a combinational input.  Recurse over fanins.
       * Return FALSE if any fanins fail the test.
       */
      Ntk_NodeForEachFanin(node, i, fanin) {
        boolean status = NodeTestCoveredByLeaves(fanin, leaves, visited);
        if (!status) {
          return FALSE;
        }
      }
      /*
       * If the loop terminates without the function returning, then each
       * fanin has already been visited and no dfsWhite_c-labelled comb input
       * can be reached from the fanins. Therefore, return TRUE.
       */
      return TRUE;
    }
  }
  
}

Here is the call graph for this function:

Here is the caller graph for this function:

st_table* Ntk_NetworkComputeLatchDependencies ( Ntk_Network_t *  network)

Function********************************************************************

Synopsis [Computes the set of latches that each latch transitively fanouts to.]

Description [For each latch, builds a list containing those latches which can be transitively reached from the fanout of the latch. If a latch doesn't have any latches in its TFO, then an empty list will be built. The dependencies are returned as a hash table mapping each latch (Ntk_Node_t *) to a list (lsList). It is the user's responsibility to free the returned hash table and the lists stored as values in the table. NOTE: this function name is a misnomer because it does not compute the latches on which a given latch depends, but instead computes the latches to which a given latch fanouts.]

SideEffects []

Definition at line 254 of file ntkGraph.c.

{
  lsGen       gen;
  Ntk_Node_t *node;
  Ntk_Node_t *latch;
  st_table   *latchDependencies = st_init_table(st_ptrcmp, st_ptrhash);

  /*
   * Initialize the TFO latch list of each node to NULL.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetTfoLatchList(node, (lsList) NULL);
  }

  /*
   * For each latch, compute the set of latches in its TFO (including possibly
   * itself).  Accumulate this set of latches into a list, and when the list
   * is complete, store the latch and list as the key and value in the hash
   * table.
   */
  Ntk_NetworkForEachLatch(network, gen, latch) {
    int         i;
    Ntk_Node_t *fanout;
    lsList      tfoLatchList = lsCreate();  /* allocate a fresh list */

    /*
     * Get the latches in the TFO of each fanout of latch, and accumulate into
     * a list. Note that we can't call NodeComputeTfoLatchList on latch
     * itself, because latches serve as the terminal case of the recursion.
     */
    Ntk_NodeForEachFanout(latch, i, fanout) {
      lsList fanoutTfoLatchList = NodeComputeTfoLatchList(fanout);

      ListAppendList(tfoLatchList, fanoutTfoLatchList);
    }

    st_insert(latchDependencies, (char *) latch, (char *) tfoLatchList);
    
  }

  /*
   * Free the tfoLatchList stored at the nodes.  Only nodes in the transitive
   * fanout of latches will have a non-NULL list, but we just call free
   * tfoLatchList function on each node.  Note that the lists being returned
   * in the hash table are distinct from those stored at nodes.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeFreeTfoLatchList(node);
  }

  return (latchDependencies);
}

Here is the call graph for this function:

Here is the caller graph for this function:

lsList Ntk_NetworkComputeTopologicalOrder ( Ntk_Network_t *  network,
array_t *  rootNodesArray,
st_table *  leafNodesTable 
)

Function********************************************************************

Synopsis [Computes the topological order of nodes in the network for a given array of root nodes and the leaf nodes.]

Description [Depth first traversal is used from each node in the root node array. The search is terminated when a node in the leaf table is reached. It is necessary that all the root nodes eventually depend on the leaf nodes. The returned list contains the nodes in the topological order.]

SideEffects []

SeeAlso []

Definition at line 447 of file ntkGraph.c.

{
  int i;
  lsList topologicalNodeList = lsCreate();
  Ntk_Node_t *node;
  lsGen gen;
  
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetColor(node, dfsWhite_c);
  }

  for (i=0; i<array_n(rootNodesArray); i++){
    node = array_fetch(Ntk_Node_t *, rootNodesArray, i);
    NodeComputeTopologicalOrderRecursively(node, leafNodesTable,
                                           topologicalNodeList);
  }
  return topologicalNodeList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean Ntk_NetworkTestIsAcyclic ( Ntk_Network_t *  network)

Function********************************************************************

Synopsis [Returns 0 if a combinational cycle exists, else returns 1.]

Description [Returns 0 if a cycle exists in the network, else returns 1. Latches are considered to break cycles. If a cycle is found, then a message is written to error_string (see the error package) giving two nodes in the cycle. Use a code fragment like the following to retrieve the error message: 

    error_init();
    status = Ntk_NetworkTestIsAcyclic(network);
    if (status == 0) {
      (void) fprintf(fp, "%s", error_string());
    }

]

SideEffects []

Comment [This function implements the DFS routine outlined in Cormen, Leiserson, Rivest, "Introduction to Algorithms", p. 478. It has been specialized to just detect cycles.]

Definition at line 333 of file ntkGraph.c.

{
  lsGen       gen;
  Ntk_Node_t *node;
  boolean     status = 1; /* In case network has no vertices. */

  /* The meaning of the colors is:
   *   white: node has not been visited yet
   *   grey:  node is on the "stack"
   *   black: node, and all its descendents, have been visited
   */

  /*
   * Initialize the color of each node to white.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetColor(node, dfsWhite_c);
  }
  
  /*
   * Recursively visit each unvisited node.  The order in which we visit the
   * nodes is immaterial.  
   */  
  Ntk_NetworkForEachNode(network, gen, node) {
    if (NodeReadColor(node) == dfsWhite_c) {
      status = NodeTestCannotReachCycle(node);
      if (status == 0) {
        /* A cycle has been found. */
        break;
      }
    }
  }

  /*
   * Colors will be left in the undef field of the nodes, but we don't care.
   */
  return (status);
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean Ntk_NetworkTestLeavesCoverSupportOfRoots ( Ntk_Network_t *  network,
array_t *  roots,
st_table *  leaves 
)

Function********************************************************************

Synopsis [Returns TRUE if leaves cover the support of roots, otherwise returns FALSE.]

Description [The function takes as input a network, a hash table of nodes called leaves, and an array of nodes called roots. It returns TRUE if the nodes in leaves cover the support of the nodes in roots, otherwise it returns FALSE. In other words, if there exists a combinational input in the transitive fanin of a root, which can be reached from the root without passing through a leaf, then FALSE is returned. If FALSE is returned, then the message "Node b found in the support of node c" is written to error_string, where b is a combinational input not in leaves and c is a root. It is allowed that some roots are themselves leaves, and that some leaves are in the transitive fanin of other leaves. Combinational cycles within the region defined by roots and leaves have no effect on the result. If TRUE is returned, then the runtime of this procedure is proportional to the number of nodes in the region defined by roots and leaves; if FALSE is returned, then the worst case is proportional to the number of nodes in the network.]

Comment [The undef field is modified of some of the nodes in the network to which node belongs.]

SideEffects []

Definition at line 402 of file ntkGraph.c.

{
  int         i;
  Ntk_Node_t *root;
  st_table   *visited = st_init_table(st_ptrcmp, st_ptrhash);
  
  /* Perform DFS from the roots.  Return FALSE upon the first failure. */
  arrayForEachItem(Ntk_Node_t *, roots, i, root) {
    boolean status = NodeTestCoveredByLeaves(root, leaves, visited);
    
    if(!status) {
      error_append(Ntk_NodeReadName(root));
      error_append(".\n");
      st_free_table(visited);
      return FALSE; 
    }
  }
  st_free_table(visited);
  return TRUE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

array_t* Ntk_NodeComputeCombinationalSupport ( Ntk_Network_t *  network,
array_t *  nodeArray,
boolean  stopAtLatches 
)

Function********************************************************************

Synopsis [Returns array of combinational inputs in transitive fanin of nodeArray.]

Description [Returns array of nodes in transitive fanin of nodes in nodeArray. If stopAtLatches is TRUE, the search terminates at combinational inputs which are latches; otherwise it continues, and the search terminates only at primary inputs and pseudo inputs. It is an error if this function is called with an empty array.]

SideEffects [required]

SeeAlso [optional]

Definition at line 182 of file ntkGraph.c.

{
  lsGen gen;
  int i;
  Ntk_Node_t *node;
  st_generator *stGen;
  st_table *resultTable = st_init_table( st_ptrcmp, st_ptrhash );
  array_t *resultArray = array_alloc( Ntk_Node_t *, 0 );

  Ntk_NetworkForEachNode( network, gen, node ) {
        NodeSetColor( node, dfsWhite_c );
  }

  arrayForEachItem( Ntk_Node_t *, nodeArray, i, node ) {
        NodeRecursivelyComputeTransitiveFaninNodes( node, resultTable, stopAtLatches );
  }

  st_foreach_item( resultTable, stGen, &node, NULL ){
        array_insert_last( Ntk_Node_t *, resultArray, node );
  }
  st_free_table( resultTable );

  return resultArray;
}

Here is the call graph for this function:

Here is the caller graph for this function:

array_t* Ntk_NodeComputeTransitiveFaninNodes ( Ntk_Network_t *  network,
array_t *  nodeArray,
boolean  stopAtLatches,
boolean  combInputsOnly 
)

Function********************************************************************

Synopsis [Returns array of nodes in transitive fanin of nodeArray.]

Description [Returns array of nodes in transitive fanin of nodes in nodeArray. If stopAtLatches is TRUE, the search terminates at combinational inputs which are latches; otherwise it continues, and the search terminates only at primary inputs and pseudo inputs. It is an error if this function is called with an empty array.]

SideEffects [required]

SeeAlso [optional]

Definition at line 140 of file ntkGraph.c.

{
  int i;
  Ntk_Node_t *node;
  st_generator *stGen;
  st_table *resultTable = st_init_table( st_ptrcmp, st_ptrhash );
  array_t *resultArray = array_alloc( Ntk_Node_t *, 0 );

  arrayForEachItem( Ntk_Node_t *, nodeArray, i, node ) {
    NodeComputeTransitiveFaninNodes(node, resultTable, stopAtLatches );
  }
  
  st_foreach_item( resultTable, stGen, &node, NULL ){
    if ( !combInputsOnly || Ntk_NodeTestIsCombInput(node) ) 
      array_insert_last( Ntk_Node_t *, resultArray, node );
  }
  st_free_table( resultTable );
  
  return resultArray;
}

Here is the call graph for this function:

Here is the caller graph for this function:

array_t* Ntk_NodeComputeTransitiveFanInputNodes ( array_t *  nodeArray,
int  depth 
)

Function********************************************************************

Synopsis [Returns array of nodes in transitive fanin of node.]

Description [Returns array of nodes in transitive fanin of node. If depth is non-zero, then only includes nodes within depth of node. If depth is zero, then includes all nodes up to and including combinational inputs.]

SideEffects [required]

SeeAlso [optional]

Definition at line 116 of file ntkGraph.c.

{
  fail("not yet implemented");
  return(NIL(array_t));
}
array_t* Ntk_NodeComputeTransitiveFanoutNodes ( array_t *  nodeArray,
int  depth 
)

AutomaticEnd Function********************************************************************

Synopsis [Returns array of nodes in transitive fanout of node.]

Description [Returns array of nodes in transitive fanout of node. If depth is non-zero, then only includes nodes within depth of node. If depth is zero, then includes all nodes up to and including combinational outputs.]

SideEffects [required]

SeeAlso [optional]

Definition at line 94 of file ntkGraph.c.

{
  fail("not yet implemented");
  return(NIL(array_t));
}
st_table* Ntk_RegionFindNodes ( array_t *  roots,
st_table *  leaves 
)

Function********************************************************************

Synopsis [Return table of all nodes lying in fanin of roots, stopping whenever a leaf node is reached. The search also stops on nodes that pass the test Ntk_NodeTestIsConstant. Note that the leaves are also present in the returned table.]

SideEffects []

Definition at line 222 of file ntkGraph.c.

{
  int i;
  st_table *result = st_init_table(st_ptrcmp, st_ptrhash);
  for (i = 0; i < array_n(roots); i++) {
    Ntk_Node_t *root = array_fetch(Ntk_Node_t *, roots, i);
    RegionFindNodesRecursively(root, leaves, result);
  }
  return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void RegionFindNodesRecursively ( Ntk_Node_t *  node,
st_table *  leaves,
st_table *  result 
) [static]

AutomaticStart

Function********************************************************************

Synopsis [Recursively add all fanins of node to result, stopping at leaves and constants.]

SideEffects []

Definition at line 482 of file ntkGraph.c.

{
  int i;
  Ntk_Node_t *fanin;

  if (st_is_member(result, (char *) node)) {
    /* already visited this node */
    return;
  }
  else {
    /*
     * Add to table before recursing, to avoid infinite loops in presence of
     * combinational cycles.
     */
    st_insert(result, (char *) node, NIL(char));
  }
  
  
  if (!st_is_member(leaves, (char *) node) && !Ntk_NodeTestIsConstant(node)) {
    /* not a leaf; recurse */
    Ntk_NodeForEachFanin(node, i, fanin) {
      RegionFindNodesRecursively(fanin, leaves, result);
    }
  }

  return;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

char rcsid [] UNUSED = "$Id: ntkGraph.c,v 1.11 2005/04/16 04:24:15 fabio Exp $" [static]

CFile***********************************************************************

FileName [ntkGraph.c]

PackageName [ntk]

Synopsis [Routines related to the abstract graph of a network.]

Author [Adnan Aziz, Tom Shiple]

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.]

Definition at line 34 of file ntkGraph.c.