source: vis_dev/vis-2.3/src/ntk/ntkNode.c @ 74

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

  FileName    [ntkNode.c]

  PackageName [ntk]

  Synopsis    [Routines to access the node data structure.]

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

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

#include "ntkInt.h"
#include "baig.h"

static char rcsid[] UNUSED = "$Id: ntkNode.c,v 1.15 2009/04/11 01:56:10 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/
#define UNASSIGNED_OUTPUT_INDEX -1
#define LATCH_DATA    0 
#define LATCH_INITIAL 1



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

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

static void NetworkAddCombOutput(Ntk_Network_t *network, Ntk_Node_t *node);

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


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

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

  Synopsis    [Returns the name of a node.]

  Description [Returns the (actual) name of a node.  User must not free this
  string.  Every node must have a non-NULL name. It is an error to call this
  function on a NULL node.]

  SideEffects []

  SeeAlso     [Ntk_NodeCreateInNetwork]

******************************************************************************/
char *
Ntk_NodeReadName(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->name);
}


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

  Synopsis    [Returns the network of a node.]

  Description [Returns the network to which node belongs.  User must not free
  this network.  Every node must have a non-NULL network.  It is an error to
  call this function on a NULL node.]

  SideEffects []

  SeeAlso     [Ntk_NodeCreateInNetwork]

******************************************************************************/
Ntk_Network_t *
Ntk_NodeReadNetwork(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->network);
}


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

  Synopsis    [Returns the variable of a node.]

  Description [Returns the multi-valued variable at the output of a node.
  User must not free this variable.  Every node must have a non-NULL variable.
  The returned variable actually belongs to the hierarchy manager from which
  the node's network was derived.  However, in the context of the network, the
  only information contained in the variable that should be used, is the
  information relating to the number (and name, if symbolic) of values. It is
  an error to call this function on a NULL node.]

  SideEffects []

  SeeAlso     [Ntk_NodeCreateInNetwork Var_VariableReadNumValues
  Var_VariableReadIndexFromSymbolicValue
  Var_VariableReadSymbolicValueFromIndex Var_VariableTestIsSymbolic
  Var_VariableTestIsEnumerative]

******************************************************************************/
Var_Variable_t *
Ntk_NodeReadVariable(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->variable);
}


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

  Synopsis    [Returns the table of a node.]

  Description [Returns the table which defines the function of this node.  User
  must not free this table.  Every combinational node and every pseudo input
  has a table.  It is an error to call this function on a NULL node or a node
  that isn't combinational or a pseudo input.]

  SideEffects []

  SeeAlso [Ntk_NodeDeclareAsCombinational Ntk_NodeDeclareAsPseudoInput
  Ntk_NodeSetTable]

******************************************************************************/
Tbl_Table_t *
Ntk_NodeReadTable(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  assert((node->type == NtkCombinational_c) || (node->type == NtkPseudoInput_c));
  return (node->table);
}

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

  Synopsis    [Returns the AndInv Id  of a node.]

  Description [Returns the AndInv Id of the node in the AndInv graph.]

  SideEffects []

  SeeAlso     []

******************************************************************************/
mAigEdge_t
Ntk_NodeReadMAigId(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->mAigId);
}


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

  Synopsis    [Sets the AndInv Id  of a node.]

  Description [Setss the AndInv Id of the node to a given vlaue.]

  SideEffects []

  SeeAlso     []

******************************************************************************/
void
Ntk_NodeSetMAigId(
  Ntk_Node_t * node,
  mAigEdge_t mAigId)
{
  assert(node != NIL(Ntk_Node_t));
  node->mAigId = mAigId;
}

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

  Synopsis    [Sets the table of the node to supplied table.]

  Description [Sets the table of the node to supplied table. THIS FUNCTION
  SHOULD BE USED WITH UTMOST CAUTION. It is assumed that the reference count of
  the supplied table is appropriately incremented. If a table already exists in
  the node it is NOT deleted. It is the users responsibility to free memory
  associated with the old table. Every combinational node and every pseudo
  input has a table. It is an error to call this function on a NULL node or a
  node that isn't combinational or a pseudo input. No checks are done to ensure
  that the supplied table infact has an output column for the specified node or
  the variables corresponding to the input columns are indeed those of the
  fanin nodes.]

  SideEffects [The old table pointed to by the node is NOT deleted.]

  SeeAlso [Ntk_NodeDeclareAsCombinational Ntk_NodeDeclareAsPseudoInput
  Ntk_NodeReadTable]

******************************************************************************/
void
Ntk_NodeSetTable(
  Ntk_Node_t * node,
  Tbl_Table_t *table)
{

  assert(node != NIL(Ntk_Node_t));
  assert((node->type == NtkCombinational_c) || (node->type == NtkPseudoInput_c));

  node->table = table;
}

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

  Synopsis    [Returns the output index of a node.]

  Description [Returns the output column of the node's table that defines the
  node's function.  It is an error to call this function on a NULL node or a
  node of type other than combinational or pseudo input.]

  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsCombinational Ntk_NodeDeclareAsPrimaryInput
  Ntk_NodeReadTable] 

******************************************************************************/
int
Ntk_NodeReadOutputIndex(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  assert((node->type == NtkCombinational_c) || (node->type == NtkPseudoInput_c));
  return (node->outputIndex);
}


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

  Synopsis    [Returns the MDD id of a node.]

  Description [Returns the MDD id of a node.  Whether or not a node has an MDD
  id depends on which nodes were assigned an id in Ord_NetworkOrderVariables.
  Returns NTK_UNASSIGNED_MDD_ID if node does not have an assigned MDD id.  It
  is an error to call this function on a NULL node.]

  SideEffects []

  SeeAlso     [Ord_NetworkOrderVariables Ntk_NodeSetMddId]

******************************************************************************/
int
Ntk_NodeReadMddId(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->mddId);
}


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

  Synopsis    [Sets the MDD id of a node.]

  Description [Sets the MDD id of a node. Any node can have its MDD id set. No
  check is made to see if node already has an MDD id.  Use the constant
  NTK_UNASSIGNED_MDD_ID to indicate that the id is not set.  If mddId is not
  NTK_UNASSIGNED_MDD_ID, then this mddId/node pair will be added to the
  network's mddId to node table, and any previous pair involving this node
  will be removed from the table.  Note that this function does *not* register
  this mddId with the MDD manager; this must be done by calling
  mdd_create_variables. It is an error to call this function on a NULL node.]

  SideEffects []

  SeeAlso     [Ntk_NodeReadMddId Ord_NetworkOrderVariables
  Ntk_NetworkFindNodeByMddId] 

******************************************************************************/
void
Ntk_NodeSetMddId(
  Ntk_Node_t * node,
  int  id)
{
  Ntk_Network_t *network = node->network;
  char *entry;
  
  assert(node != NIL(Ntk_Node_t));

  /* If the node already has an assigned id, then clean it from the table. */
  if (node->mddId != NTK_UNASSIGNED_MDD_ID) {
    entry = (char *) (long) node->mddId;
    (void) st_delete(network->mddIdToNode, &entry, NIL(char *));
  }

  /* Set the new id, and add it to the table (if it's not unassigned). */
  node->mddId = id;
  if (id != NTK_UNASSIGNED_MDD_ID) {
    st_insert(network->mddIdToNode, (char *) (long) id, (char *) node);
  }
}


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

  Synopsis    [Returns the undef field of a node.]

  Description [Returns the undef field of a node.  There is no restriction on how
  this field is used.  However, you should use extreme caution to make sure
  that you are not using this field to store more that one thing at a given
  time (if you can't be sure, then use a hash table).  It is an error to call
  this function on a NULL node.]

  SideEffects []

  SeeAlso     [Ntk_NodeSetUndef]

******************************************************************************/
void *
Ntk_NodeReadUndef(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->undef);
}


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

  Synopsis    [Sets the undef field of a node.]

  Description [Sets the undef field of a node.  There is no restriction on
  how this field is used.  It is an error to call this function on a NULL
  node.]

  SideEffects []

  SeeAlso     [Ntk_NodeReadUndef]

******************************************************************************/
void
Ntk_NodeSetUndef(
  Ntk_Node_t * node,
  void * value)
{
  assert(node != NIL(Ntk_Node_t));
  node->undef = value;
}


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

  Synopsis    [Returns 1 if node is a primary input, else returns 0.]

  Description [Returns 1 if node is a primary input, else returns 0.  A node
  is a primary input only if it has been so declared using
  Ntk_NodeDeclareAsPrimaryInput. It is an error to call this function on a
  NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPrimaryInput Ntk_NodeTestIsInput]
  
******************************************************************************/
boolean
Ntk_NodeTestIsPrimaryInput(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->type == NtkPrimaryInput_c);
}


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

  Synopsis    [Returns 1 if node is a pseudo input, else returns 0.]

  Description [Returns 1 if node is a pseudo input, else returns 0.  A node is
  a pseudo input only if it has been so declared using
  Ntk_NodeDeclareAsPseudoInput. A pseudo input has no fanins, but has a table
  defining its function. It is an error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPseudoInput Ntk_NodeTestIsInput]
  
******************************************************************************/
boolean
Ntk_NodeTestIsPseudoInput(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->type == NtkPseudoInput_c);
}


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

  Synopsis    [Returns 1 if node is a primary or pseudo input, else returns 0.]

  Description [Returns 1 if node is a primary or pseudo input, else returns 0.
  It is an error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPrimaryInput Ntk_NodeDeclareAsPseudoInput
  Ntk_NodeTestIsPrimaryInput Ntk_NodeTestIsPseudoInput]
  
******************************************************************************/
boolean
Ntk_NodeTestIsInput(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return ((node->type == NtkPrimaryInput_c) || (node->type == NtkPseudoInput_c));
  
}


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

  Synopsis    [Returns 1 if node is undefined, else returns 0.]

  Description [Returns 1 if node is undefined, else returns 0. A node is
  undefined if it has been created but not declared as anything. It is an
  error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeCreateInNetwork Ntk_NodeDeclareAsCombinational]

******************************************************************************/
boolean
Ntk_NodeTestIsUndefined(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->type == NtkUnassigned_c);
}


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

  Synopsis    [Returns 1 if node is a latch, else returns 0.]

  Description [Returns 1 if node is a latch, else returns 0.  A node is a
  latch only if it has been so declared using Ntk_NodeDeclareAsLatch. It is an
  error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsLatch]

******************************************************************************/
boolean
Ntk_NodeTestIsLatch(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->type == NtkLatch_c);
}


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

  Synopsis    [Returns 1 if node is a next state node, else returns 0.]

  Description [Returns 1 if node is a next state node, else returns 0.  A next
  state node is a shadow node whose origin node is a latch.  It is an
  error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsShadow]

******************************************************************************/
boolean
Ntk_NodeTestIsNextStateNode(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  if (Ntk_NodeTestIsShadow(node)) {
    Ntk_Node_t *origin = Ntk_ShadowReadOrigin(node);
    if (Ntk_NodeTestIsLatch(origin)) {
      return (TRUE);
    }
  }
  
  return (FALSE);
}


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

  Synopsis    [Returns 1 if node is a shadow node, else returns 0.]

  Description [Returns 1 if node is a shadow node, else returns 0.  A shadow
  node is used to associate extra information with a node, in particular
  another MDD id. It is an error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsShadow Ntk_ShadowReadOrigin Ntk_NodeReadShadow]

******************************************************************************/
boolean
Ntk_NodeTestIsShadow(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->type == NtkShadow_c);
}


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

  Synopsis    [Returns 1 if node is a combinational input, else returns 0.]

  Description [Returns 1 if node is a combinational input, else returns 0.  A
  node is a combinational input if it is a primary input, a pseudo input, or a
  latch. It is an error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPrimaryInput Ntk_NodeDeclareAsLatch
  Ntk_NodeDeclareAsPseudoInput]

******************************************************************************/
boolean
Ntk_NodeTestIsCombInput(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return ((node->type == NtkLatch_c)
          || (node->type == NtkPrimaryInput_c)
          || (node->type == NtkPseudoInput_c));
}


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

  Synopsis    [Returns 1 if node is a combinational output, else returns 0.]

  Description [Returns 1 if node is a combinational output, else returns 0.  A
  node is a combinational output if it is a primary output, a data input to a
  latch, or an initial input to a latch. This is a constant time operation.
  It is an error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPrimaryOutput Ntk_NodeDeclareAsLatch]
  
******************************************************************************/
boolean
Ntk_NodeTestIsCombOutput(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (Ntk_NodeTestIsPrimaryOutput(node)
          || Ntk_NodeTestIsLatchDataInput(node)
          || Ntk_NodeTestIsLatchInitialInput(node));
}


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

  Synopsis    [Returns 1 if node is combinational, else returns 0.]

  Description [Returns 1 if node is combinational, else returns 0.  A node is
  combinational only if it has been so declared using
  Ntk_NodeDeclareAsCombinational.  Combinational nodes have tables.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsCombinational]

******************************************************************************/
boolean
Ntk_NodeTestIsCombinational(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->type == NtkCombinational_c);
}


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

  Synopsis    [Returns 1 if node is a primary output, else returns 0.]

  Description [Returns 1 if node is a primary output, else returns 0.  Any
  node can be a primary output, except those of type shadow.  A node is a
  primary output only if it has been so declared using
  Ntk_NodeDeclareAsPrimaryOutput.  It is an error to call this function on a
  NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPrimaryOutput]
  
******************************************************************************/
boolean
Ntk_NodeTestIsPrimaryOutput(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->outputFlag);
}


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

  Synopsis    [Returns 1 if node is a data input to a latch, else returns 0.]

  Description [Returns 1 if node is a data input to a latch, else returns 0.
  Nodes of all types can be data inputs to latches.  A node is declared as a
  data input to a latch by virtue of a call to Ntk_NodeDeclareAsLatch. It is
  an error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsLatch]

******************************************************************************/
boolean
Ntk_NodeTestIsLatchDataInput(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->latchDataInput);
}


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

  Synopsis    [Returns 1 if node is an initial input to a latch, else returns 0.]

  Description [Returns 1 if node is an initial input to a latch, else returns
  0.  Nodes of all types can be initial inputs to latches. The initial input
  to a latch gives the initial value of the latch. A node is declared as a
  initial input to a latch by virtue of a call to Ntk_NodeDeclareAsLatch. It
  is an error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsLatch]

******************************************************************************/
boolean
Ntk_NodeTestIsLatchInitialInput(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->latchInitialInput);
}


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

  Synopsis    [Returns 1 if node is a constant, else returns 0.]

  Description [Returns 1 if node is a constant, else returns 0.  A constant is
  a combinational node that has no inputs, and whose output can take exactly
  one of its values.  It is an error to call this function on a NULL node.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsCombinational]

******************************************************************************/
boolean
Ntk_NodeTestIsConstant(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->constant);
}


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

  Synopsis    [Returns the shadow of a node.]

  Description [Returns the shadow of a node if one exists, else returns NULL.
  A shadow node can serve as a placeholder for an extra MDD variable, such as
  a next state variable.  It is an error to call this function on a node that
  is a shadow.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsShadow Ntk_ShadowReadOrigin Ntk_NodeTestIsShadow]

******************************************************************************/
Ntk_Node_t *
Ntk_NodeReadShadow(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  assert(node->type != NtkShadow_c);
  return (node->shadowInfo.shadow);
}


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

  Synopsis    [Returns the origin node of a shadow node.]

  Description [Returns the origin node of a shadow node.  The origin of a
  shadow node is that node that is "casting" the shadow.  A shadow is used as
  a placeholder for a node, in particular a place to store an additional MDD
  variable.  It is an error to call this function on a node that is not a
  shadow.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsShadow Ntk_NodeReadShadow Ntk_NodeTestIsShadow]

******************************************************************************/
Ntk_Node_t *
Ntk_ShadowReadOrigin(
  Ntk_Node_t * shadow)
{
  assert(shadow != NIL(Ntk_Node_t));
  assert(shadow->type == NtkShadow_c);
  return (shadow->shadowInfo.origin);
}


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

  Synopsis    [Returns the of data input of a latch.]

  Description [Returns the data input of a latch.  The data input determines the
  value of the latch output at the next clock. It is an error to call this
  function on a node that is not a latch.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsLatch]

******************************************************************************/
Ntk_Node_t *
Ntk_LatchReadDataInput(
  Ntk_Node_t * node)
{
  Ntk_Node_t *data;
  
  assert(node != NIL(Ntk_Node_t));
  assert(node->type == NtkLatch_c);
  data = array_fetch(Ntk_Node_t *, node->fanins, LATCH_DATA);
  
  return (data);
}


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

  Synopsis    [Returns the initial input of a latch.]

  Description [Returns the initial input of a latch.  The initial value
  of the latch is determined by the value of the initial input. It is
  an error to call this function on a node that is not a latch.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsLatch]

******************************************************************************/
Ntk_Node_t *
Ntk_LatchReadInitialInput(
  Ntk_Node_t * node)
{
  Ntk_Node_t *initial;
  
  assert(node != NIL(Ntk_Node_t));
  assert(node->type == NtkLatch_c);
  initial = array_fetch(Ntk_Node_t *, node->fanins, LATCH_INITIAL);
  
  return (initial);
}


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

  Synopsis    [Returns the number of fanins of a node.]

  SideEffects []

  SeeAlso     [Ntk_NodeReadNumFanouts]

******************************************************************************/
int
Ntk_NodeReadNumFanins(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (array_n(node->fanins));
}


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

  Synopsis    [Returns the number of fanouts of a node.]

  SideEffects []

  SeeAlso     [Ntk_NodeReadNumFanins]

******************************************************************************/
int
Ntk_NodeReadNumFanouts(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (array_n(node->fanouts));
}


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

  Synopsis    [Returns the fanin of node corresponding to faninIndex.]

  Description [Returns the fanin of node corresponding to faninIndex.  Fanins are
  numbered starting from 0.]

  SideEffects []

  SeeAlso     [Ntk_NodeReadFaninIndex]

******************************************************************************/
Ntk_Node_t *
Ntk_NodeReadFaninNode(
  Ntk_Node_t * node,
  int  faninIndex)
{
  Ntk_Node_t *faninNode;
  
  assert(node != NIL(Ntk_Node_t));
  assert((faninIndex >= 0) && (faninIndex < Ntk_NodeReadNumFanins(node)));
  faninNode = array_fetch(Ntk_Node_t *, node->fanins, faninIndex);
  return (faninNode);
}

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

  Synopsis    [Returns the fanin index of node corresponding to faninNode.]

  Description [Returns the fanin index of node corresponding to faninNode. If
  faninNode is not a fanin of node, then returns NTK_UNDEFINED_FANIN_INDEX.]

  SideEffects []

  SeeAlso     [Ntk_NodeReadFaninNode]

******************************************************************************/
int
Ntk_NodeReadFaninIndex(
  Ntk_Node_t * node,
  Ntk_Node_t * faninNode)
{
  int         i;
  Ntk_Node_t *tempNode;
  
  assert(node != NIL(Ntk_Node_t));
  Ntk_NodeForEachFanin(node, i, tempNode) {
    if (tempNode == faninNode) {
      return (i);
    }
  }

  return (NTK_UNDEFINED_FANIN_INDEX);
}


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

  Synopsis    [Returns the array of fanins of a node.]

  Description [Returns the array of fanins of a node.  The user must not free or
  modify this array in any way.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeReadNumFanins]

******************************************************************************/
array_t *
Ntk_NodeReadFanins(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->fanins);
}


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

  Synopsis    [Returns the array of fanouts of a node.]

  Description [Returns the array of fanouts of a node.  The user must not free or
  modify this array in any way.]
  
  SideEffects []

  SeeAlso     [Ntk_NodeReadNumFanouts]

******************************************************************************/
array_t *
Ntk_NodeReadFanouts(
  Ntk_Node_t * node)
{
  assert(node != NIL(Ntk_Node_t));
  return (node->fanouts);
}


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

  Synopsis    [Sets the array of fanins of a node.]

  Description [Sets the array of fanins of a node. This function must be used
  with UTMOST caution. Use this only when you know EXACTLY what you are doing.]
  
  SideEffects [Old fanin array is deleted.]

  SeeAlso     [Ntk_NodeReadNumFanins Ntk_NodeReadFanins]

******************************************************************************/
void
Ntk_NodeSetFanins(
  Ntk_Node_t * node,
  array_t *faninArray)
{
  assert(node != NIL(Ntk_Node_t));
  if (node->fanins)
    array_free(node->fanins);
  
  node->fanins = faninArray;

  return;
}


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

  Synopsis    [Sets the array of fanouts of a node.]

  Description [Sets the array of fanouts of a node. This function must be used
  with UTMOST caution. Use this only when you know EXACTLY what you are doing.]
  
  SideEffects [Old fanout array is deleted.]

  SeeAlso     [Ntk_NodeReadNumFanouts Ntk_NodeReadFanouts]

******************************************************************************/
void
Ntk_NodeSetFanouts(
  Ntk_Node_t * node,
  array_t *fanoutArray)
{
  assert(node != NIL(Ntk_Node_t));
  if (node->fanouts)
    array_free(node->fanouts);
  
  node->fanouts = fanoutArray;

  return;
}


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

  Synopsis    [Returns a string giving a node's type.]

  Description [Returns a string giving a node's type.  The return string can
  be one of the following: "latch", "shadow", "primary-input", "pseudo-input",
  "combinational", or "unassigned".  It is the user's responsibility to free
  this string.]

  SideEffects []

  SeeAlso     [Ntk_NodePrint]

******************************************************************************/
char *
Ntk_NodeObtainTypeAsString(
  Ntk_Node_t * node)
{
  char *typeString;

  assert(node != NIL(Ntk_Node_t));
  switch(node->type) {
      case NtkLatch_c:
        typeString = util_strsav("latch");
        break;
      case NtkShadow_c:
        typeString = util_strsav("shadow");
        break;
      case NtkPrimaryInput_c:
        typeString = util_strsav("primary-input");
        break;
      case NtkPseudoInput_c:
        typeString = util_strsav("pseudo-input");
        break;
      case NtkCombinational_c:
        typeString = util_strsav("combinational");
        break;
      case NtkUnassigned_c:
        typeString = util_strsav("unassigned");
        break;
      default:
        fail("Unexpected type");
  }
  return (typeString);
}


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

  Synopsis    [Prints information about a node.]

  Description [Prints the node's name, MDD id, type, and attributes. In
  addition, if printIo is TRUE, prints the name of each fanin node and each
  fanout node. And if printTableStats is TRUE, print table statistics for
  those nodes having a table.]

  SideEffects []

  SeeAlso     [Ntk_NetworkPrint]

******************************************************************************/
void
Ntk_NodePrint(
  FILE * fp,
  Ntk_Node_t * node,
  boolean printIo,
  boolean printTableStats)
{
  int         i;
  Ntk_Node_t *fanin;
  Ntk_Node_t *fanout;
  char       *typeString = Ntk_NodeObtainTypeAsString(node);
  

  /*
   * Print the node's name, MDD id, type, and attributes.
   */
  (void) fprintf(fp, "%s: mdd=%d, %s;%s%s%s%s%s%s\n",
                 Ntk_NodeReadName(node),
                 Ntk_NodeReadMddId(node),
                 typeString,
                 (Ntk_NodeTestIsPrimaryOutput(node) ? " output" : ""),
                 (Ntk_NodeTestIsConstant(node) ? " constant" : ""),
                 (Ntk_NodeTestIsLatchDataInput(node) ? " data-input" : ""),
                 (Ntk_NodeTestIsLatchInitialInput(node) ? " initial-input" : ""),
                 (Ntk_NodeTestIsCombInput(node) ? " comb-input" : ""),
                 (Ntk_NodeTestIsCombOutput(node) ? " comb-output" : "")
                 );

  FREE(typeString);
  
  if (printIo) {
    /*
     * Print the name of each fanin.
     */
    (void) fprintf(fp, "Fanins:  ");
    Ntk_NodeForEachFanin(node, i, fanin) {
      if (i != 0) (void) fprintf(fp, ",");
      (void) fprintf(fp, " %s", Ntk_NodeReadName(fanin));
    }
    (void) fprintf(fp, "\n");

    /*
     * Print the name of each fanout.
     */
    (void) fprintf(fp, "Fanouts: ");
    Ntk_NodeForEachFanout(node, i, fanout) {
      if (i != 0) (void) fprintf(fp, ",");
      (void) fprintf(fp, " %s", Ntk_NodeReadName(fanout));
    }
    (void) fprintf(fp, "\n");
  }

  if (printTableStats) {
    if (Ntk_NodeTestIsCombinational(node) || Ntk_NodeTestIsPseudoInput(node)) {
      Tbl_TablePrintStats(Ntk_NodeReadTable(node), fp);
    }
  }
}


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

  Synopsis    [Creates a node in a network with a name and a variable.]

  Description [Creates a node in a network.  The name, network, and variable
  fields are initialized with the supplied values (a copy of name is made
  first, a copy of the variable is not made).  The fanins and fanouts fields
  are initialized with empty arrays.  All other fields are initialized to NULL
  or UNASSIGNED values.  A non-NULL name, non-NULL network, and non-NULL
  variable are required. This is the only way to allocate a node; in other
  words, a node can only exist with a name and a variable, within the context
  of a network.]

  SideEffects [The node is added to the network's information.]

  SeeAlso     [Ntk_NodeFree]

******************************************************************************/
Ntk_Node_t *
Ntk_NodeCreateInNetwork(
  Ntk_Network_t * network,
  char * name,
  Var_Variable_t *variable)
{
  Ntk_Node_t *node = ALLOC(Ntk_Node_t, 1);

  assert(network != NIL(Ntk_Network_t));
  assert(name != NIL(char));
  assert(variable != NIL(Var_Variable_t));
  
  node->name                  = util_strsav(name);
  node->network               = network;
  node->variable              = variable;
  node->type                  = NtkUnassigned_c;
  node->fanins                = array_alloc(Ntk_Node_t *, 0);
  node->fanouts               = array_alloc(Ntk_Node_t *, 0);
  node->table                 = NIL(Tbl_Table_t);
  node->outputIndex           = UNASSIGNED_OUTPUT_INDEX;
  node->mddId                 = NTK_UNASSIGNED_MDD_ID;
  node->mAigId                = -1;
  node->shadowInfo.shadow     = NIL(Ntk_Node_t);
  node->outputFlag            = 0;
  node->constant              = 0;
  node->latchDataInput        = 0;
  node->latchInitialInput     = 0;
  node->undef                 = NIL(void);

  /*
   * Update the state of the network. Note: it's important to use node->name
   * here, rather than just name, because we don't own name.
   */
  st_insert(network->actualNameToNode, (char *) node->name, (char *) node);
  lsNewEnd(network->nodes, (lsGeneric) node, LS_NH);

  return (node);
}


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

  Synopsis    [Declares a node as combinational and sets the table.]

  Description [Declares a node as combinational using the column of table
  corresponding to outputIndex as the function of the node.  This function
  does not make a copy of the table; instead, it just sets a pointer to it.
  However, it's assumed that the table will own the table, and the table is
  freed when the node is freed.  Connections are made to the nodes
  corresponding to the inputs in the table.  The node for the ith table input
  is found by calling Ntk_NetworkFindNodeByName with the ith entry of
  inputNames.  The order of the fanins of node returned by
  Ntk_NodeForEachFanin are guaranteed to be the same as the order of the
  corresponding input columns in the table.]

  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPrimaryInput Ntk_NodeDeclareAsPrimaryOutput]

******************************************************************************/
void
Ntk_NodeDeclareAsCombinational(
  Ntk_Node_t * node,
  Tbl_Table_t * table,
  array_t * inputNames /* array of char */,
  int  outputIndex)
{
  int            i;
  Ntk_Network_t *network = node->network;

  assert(node->type == NtkUnassigned_c);
  
  node->type        = NtkCombinational_c;
  node->table       = table;
  node->outputIndex = outputIndex;

  /*
   * If it can be determined that the corresponding output column of table can
   * take assume just a single value, then set the constant flag. 
   */
  if (Tbl_TableTestIsConstant(table, outputIndex)) {
    node->constant = 1;
  }
  
  /*
   * Create a connection to each input of table. 
   */
  for (i = 0; i < array_n(inputNames); i++) {
    char        *faninName = array_fetch(char *, inputNames, i);
    Ntk_Node_t  *fanin     = Ntk_NetworkFindNodeByName(network, faninName);

    assert(fanin != NIL(Ntk_Node_t));

    /*
     * Make the connections between node and fanin.  Note: it is critical
     * that the fanins of node are added to node->fanins in the same order
     * they appear in the table.
     */
    array_insert_last(Ntk_Node_t *, fanin->fanouts, node);
    array_insert_last(Ntk_Node_t *, node->fanins, fanin);
  }
}


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

  Synopsis    [Declares a node as a latch.]

  Description [Declares a node as a latch.  Makes connections to the data and
  initial input nodes.  The data node is taken as that one found by calling
  Ntk_NetworkFindNodeByName with the name "dataName"; likewise for the initial
  node.  Adds the node to the end of the latch list of the node's network, and
  the combinational input list.  This function does not automatically create
  a shadow node for the latch (i.e. a node to store information about the next
  state variable of the latch); to do this, use Ntk_NodeCreateInNetwork and
  Ntk_NodeDeclareAsShadow.]

  SideEffects []

  SeeAlso     [Ntk_LatchReadDataInput Ntk_LatchReadInitialInput]

******************************************************************************/
void
Ntk_NodeDeclareAsLatch(
  Ntk_Node_t * latch,
  char * dataName,
  char * initName)
{
  Ntk_Node_t    *dataNode;
  Ntk_Node_t    *initNode;
  Ntk_Network_t *network = latch->network;
  
  assert(latch->type == NtkUnassigned_c);
  latch->type = NtkLatch_c;

  /*
   * Get the nodes corresponding to dataName and initName.
   */
  dataNode = Ntk_NetworkFindNodeByName(network, dataName);
  initNode = Ntk_NetworkFindNodeByName(network, initName);
  assert(dataNode != NIL(Ntk_Node_t));
  assert(initNode != NIL(Ntk_Node_t));

  /*
   * Make the necessary connections. Note the predefined locations of the data
   * and initial inputs in the fanin array of latch.
   */
  array_insert(Ntk_Node_t *, latch->fanins, LATCH_DATA, dataNode);
  array_insert(Ntk_Node_t *, latch->fanins, LATCH_INITIAL, initNode);

  array_insert_last(Ntk_Node_t *, dataNode->fanouts, latch);
  array_insert_last(Ntk_Node_t *, initNode->fanouts, latch);

  /*
   * Set the special flags in the data and init nodes, and add them to the
   * list of combinational outputs.
   */
  dataNode->latchDataInput = 1;
  NetworkAddCombOutput(network, dataNode);

  initNode->latchInitialInput = 1;
  NetworkAddCombOutput(network, initNode);

  /*
   * Add the latch to the appropriate lists in network.
   */
  lsNewEnd(network->latches,    (lsGeneric) latch, LS_NH);
  lsNewEnd(network->combInputs, (lsGeneric) latch, LS_NH);
}


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

  Synopsis    [Declares a node as a primary input.]

  Description [Declares a node as a primary input.  Adds node to the relevant
  node lists maintained by the node's network.]

  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPrimaryOutput]

******************************************************************************/
void
Ntk_NodeDeclareAsPrimaryInput(
  Ntk_Node_t * node)
{
  assert(node->type == NtkUnassigned_c);
  node->type = NtkPrimaryInput_c;

  lsNewEnd(node->network->primaryInputs, (lsGeneric) node, LS_NH);
  lsNewEnd(node->network->inputs,        (lsGeneric) node, LS_NH);
  lsNewEnd(node->network->combInputs,    (lsGeneric) node, LS_NH);
}


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

  Synopsis    [Declares a node as a pseudo input.]

  Description [Declares a node as a pseudo input.  The function of a pseudo
  input is given by the column of table corresponding to outputIndex.  This
  function does not make a copy of the table; instead, it just sets a pointer
  to it.  However, it's assumed that the table will own the table, and the
  table is freed when the node is freed.  Adds node to the relevant node lists
  maintained by the node's network.]

  SideEffects []

  SeeAlso     [Ntk_NodeDeclareAsPrimaryInput]

******************************************************************************/
void
Ntk_NodeDeclareAsPseudoInput(
  Ntk_Node_t * node,
  Tbl_Table_t * table,
  int  outputIndex)
{
  assert(node->type == NtkUnassigned_c);

  node->type        = NtkPseudoInput_c;
  node->table       = table;
  node->outputIndex = outputIndex;
  
  if (Tbl_TableTestIsConstant(table, outputIndex)) {
    node->constant = 1;
  }
  
  lsNewEnd(node->network->pseudoInputs, (lsGeneric) node, LS_NH);
  lsNewEnd(node->network->inputs,       (lsGeneric) node, LS_NH);
  lsNewEnd(node->network->combInputs,   (lsGeneric) node, LS_NH);
}


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

  Synopsis    [Declares a node as a primary output.]

  Description [Declares a node as a primary output.  Node can be of any type,
  except type shadow.]

  SideEffects []

  SeeAlso     [Ntk_TestIsPrimaryOutput]

******************************************************************************/
void
Ntk_NodeDeclareAsPrimaryOutput(
  Ntk_Node_t * node)
{
  assert(node->type != NtkShadow_c);
  node->outputFlag = 1;
  lsNewEnd(node->network->primaryOutputs, (lsGeneric) node, LS_NH);
  NetworkAddCombOutput(node->network, node);
}


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

  Synopsis    [Declares a node as a shadow node.]

  Description [Declares a node as a shadow node. A shadow node is used to
  associate extra information with a node, in particular another MDD id.  Any
  "origin" node can have a shadow node, except a node which itself is of type
  shadow. This function makes the bidirectional link between the shadow and
  origin nodes.]

  SideEffects []

  SeeAlso     [Ntk_NodeTestIsShadow Ntk_ShadowReadOrigin Ntk_NodeReadShadow]

******************************************************************************/
void
Ntk_NodeDeclareAsShadow(
  Ntk_Node_t * shadow,
  Ntk_Node_t * origin)
{
  assert(shadow->type == NtkUnassigned_c);
  assert(origin->type != NtkShadow_c);
  
  shadow->type = NtkShadow_c;

  shadow->shadowInfo.origin = origin;
  origin->shadowInfo.shadow = shadow;
}


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

  Synopsis    [Frees all the memory local to the node.]

  Description [Frees all the memory local to the node, including the node
  itself. Does not free the nodes in the fanin and fanout of node, nor does it
  free the network of node.  Also, this function does not update the lists
  maintained by the network to reflect that this node no longer exists, nor
  does it update the fanin and fanout lists of neighboring nodes.]

  SideEffects []

  SeeAlso     [Ntk_NodeCreateInNetwork]

******************************************************************************/
void
Ntk_NodeFree(
  Ntk_Node_t * node)
{
  FREE(node->name);
  array_free(node->fanins);
  array_free(node->fanouts);
  Tbl_TableFree(node->table);
  
  /*
   * Unassign a few key fields for safety's sake.
   */
  node->name              = NIL(char);
  node->network           = NIL(Ntk_Network_t);
  node->variable          = NIL(Var_Variable_t);
  node->type              = NtkUnassigned_c;
  node->fanins            = NIL(array_t);
  node->fanouts           = NIL(array_t);
  node->table             = NIL(Tbl_Table_t);
  node->mddId             = NTK_UNASSIGNED_MDD_ID;

  FREE(node);
}


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


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

  Synopsis    [Adds a node to the network's list of combinational outputs.]

  Description [Adds a node to the network's list of combinational outputs. If
  the list already contains the node, then nothing is done.  List membership
  is maintained via a hash table.]

  SideEffects []

  SeeAlso     [Ntk_NetworkForEachCombOutput]

******************************************************************************/
static void
NetworkAddCombOutput(
  Ntk_Network_t *network,
  Ntk_Node_t    *node)
{
  if (!st_is_member(network->combOutputsTable, (char *) node)) {
    st_insert(network->combOutputsTable, (char *) node, (char *) 0);
    lsNewEnd(network->combOutputs, (lsGeneric) node, LS_NH);
  }
}