deco.h File Reference

Go to the source code of this file.

Data Structures
struct	Dec_Edge_t_
struct	Dec_Node_t_
struct	Dec_Graph_t_
struct	Dec_Man_t_

Macros
#define	Dec_GraphForEachLeaf(pGraph, pLeaf, i)   for ( i = 0; (i < (pGraph)->nLeaves) && (((pLeaf) = Dec_GraphNode(pGraph, i)), 1); i++ )
	ITERATORS ///. More...
#define	Dec_GraphForEachNode(pGraph, pAnd, i)   for ( i = (pGraph)->nLeaves; (i < (pGraph)->nSize) && (((pAnd) = Dec_GraphNode(pGraph, i)), 1); i++ )

Typedefs
typedef typedefABC_NAMESPACE_HEADER_START struct Dec_Edge_t_	Dec_Edge_t
	INCLUDES ///. More...
typedef struct Dec_Node_t_	Dec_Node_t
typedef struct Dec_Graph_t_	Dec_Graph_t
typedef struct Dec_Man_t_	Dec_Man_t

Functions
static Dec_Edge_t	Dec_EdgeCreate (int Node, int fCompl)
	FUNCTION DECLARATIONS ///. More...
static unsigned	Dec_EdgeToInt (Dec_Edge_t eEdge)
static Dec_Edge_t	Dec_IntToEdge (unsigned Edge)
static unsigned	Dec_EdgeToInt_ (Dec_Edge_t m)
static Dec_Edge_t	Dec_IntToEdge_ (unsigned m)
static Dec_Graph_t *	Dec_GraphCreate (int nLeaves)
static Dec_Graph_t *	Dec_GraphCreateConst0 ()
static Dec_Graph_t *	Dec_GraphCreateConst1 ()
static Dec_Graph_t *	Dec_GraphCreateLeaf (int iLeaf, int nLeaves, int fCompl)
static void	Dec_GraphFree (Dec_Graph_t *pGraph)
static int	Dec_GraphIsConst (Dec_Graph_t *pGraph)
static int	Dec_GraphIsConst0 (Dec_Graph_t *pGraph)
static int	Dec_GraphIsConst1 (Dec_Graph_t *pGraph)
static int	Dec_GraphIsComplement (Dec_Graph_t *pGraph)
static void	Dec_GraphComplement (Dec_Graph_t *pGraph)
static int	Dec_GraphLeaveNum (Dec_Graph_t *pGraph)
static int	Dec_GraphNodeNum (Dec_Graph_t *pGraph)
static Dec_Node_t *	Dec_GraphNode (Dec_Graph_t *pGraph, int i)
static Dec_Node_t *	Dec_GraphNodeLast (Dec_Graph_t *pGraph)
static int	Dec_GraphNodeInt (Dec_Graph_t *pGraph, Dec_Node_t *pNode)
static int	Dec_GraphIsVar (Dec_Graph_t *pGraph)
static int	Dec_GraphNodeIsVar (Dec_Graph_t *pGraph, Dec_Node_t *pNode)
static Dec_Node_t *	Dec_GraphVar (Dec_Graph_t *pGraph)
static int	Dec_GraphVarInt (Dec_Graph_t *pGraph)
static void	Dec_GraphSetRoot (Dec_Graph_t *pGraph, Dec_Edge_t eRoot)
static Dec_Node_t *	Dec_GraphAppendNode (Dec_Graph_t *pGraph)
static Dec_Edge_t	Dec_GraphAddNodeAnd (Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1)
static Dec_Edge_t	Dec_GraphAddNodeOr (Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1)
static Dec_Edge_t	Dec_GraphAddNodeXor (Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1, int Type)
static Dec_Edge_t	Dec_GraphAddNodeMux (Dec_Graph_t *pGraph, Dec_Edge_t eEdgeC, Dec_Edge_t eEdgeT, Dec_Edge_t eEdgeE, int Type)

Macro Definition Documentation

#define Dec_GraphForEachLeaf	(		pGraph,
			pLeaf,
			i
	)		for ( i = 0; (i < (pGraph)->nLeaves) && (((pLeaf) = Dec_GraphNode(pGraph, i)), 1); i++ )

ITERATORS ///.

Definition at line 98 of file deco.h.

#define Dec_GraphForEachNode	(		pGraph,
			pAnd,
			i
	)		for ( i = (pGraph)->nLeaves; (i < (pGraph)->nSize) && (((pAnd) = Dec_GraphNode(pGraph, i)), 1); i++ )

Definition at line 101 of file deco.h.

Typedef Documentation

typedef typedefABC_NAMESPACE_HEADER_START struct Dec_Edge_t_ Dec_Edge_t

INCLUDES ///.

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

FileName [deco.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [A simple decomposition tree/node data structure and its APIs.]

Synopsis [External declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

deco.h,v 1.00 2005/06/20 00:00:00 alanmi Exp

]PARAMETERS ///BASIC TYPES ///

Definition at line 42 of file deco.h.

typedef struct Dec_Graph_t_ Dec_Graph_t

Definition at line 68 of file deco.h.

typedef struct Dec_Man_t_ Dec_Man_t

Definition at line 79 of file deco.h.

typedef struct Dec_Node_t_ Dec_Node_t

Definition at line 49 of file deco.h.

Function Documentation

static Dec_Edge_t Dec_EdgeCreate ( int  Node, int  fCompl  )

inlinestatic

FUNCTION DECLARATIONS ///.

FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Creates an edge pointing to the node in the given polarity.]

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file deco.h.

{
    Dec_Edge_t eEdge = { fCompl, Node }; 
    return eEdge; 
}

static unsigned Dec_EdgeToInt ( Dec_Edge_t  eEdge )

inlinestatic

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

Synopsis [Converts the edge into unsigned integer.]

Description []

SideEffects []

SeeAlso []

Definition at line 140 of file deco.h.

{
    return (eEdge.Node << 1) | eEdge.fCompl; 
}

static unsigned Dec_EdgeToInt_ ( Dec_Edge_t  m )

inlinestatic

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

Synopsis [Converts the edge into unsigned integer.]

Description []

SideEffects []

SeeAlso []

Definition at line 172 of file deco.h.

{ union { Dec_Edge_t x; unsigned y; } v; v.x = m; return v.y;  }

static Dec_Edge_t Dec_GraphAddNodeAnd ( Dec_Graph_t *  pGraph, Dec_Edge_t  eEdge0, Dec_Edge_t  eEdge1  )

inlinestatic

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

Synopsis [Creates an AND node.]

Description []

SideEffects []

SeeAlso []

Definition at line 580 of file deco.h.

{
    Dec_Node_t * pNode;
    // get the new node
    pNode = Dec_GraphAppendNode( pGraph );
    // set the inputs and other info
    pNode->eEdge0 = eEdge0;
    pNode->eEdge1 = eEdge1;
    pNode->fCompl0 = eEdge0.fCompl;
    pNode->fCompl1 = eEdge1.fCompl;
    return Dec_EdgeCreate( pGraph->nSize - 1, 0 );
}

static Dec_Edge_t Dec_GraphAddNodeMux ( Dec_Graph_t *  pGraph, Dec_Edge_t  eEdgeC, Dec_Edge_t  eEdgeT, Dec_Edge_t  eEdgeE, int  Type  )

inlinestatic

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 673 of file deco.h.

{
    Dec_Edge_t eNode0, eNode1, eNode;
    if ( Type == 0 )
    {
        // derive the first AND
        eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
        // derive the second AND
        eEdgeC.fCompl ^= 1;
        eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
        // derive the final OR
        eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
    }
    else
    {
        // complement the arguments
        eEdgeT.fCompl ^= 1;
        eEdgeE.fCompl ^= 1;
        // derive the first AND
        eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
        // derive the second AND
        eEdgeC.fCompl ^= 1;
        eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
        // derive the final OR
        eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
        eNode.fCompl ^= 1;
    }
    return eNode;
}

static Dec_Edge_t Dec_GraphAddNodeOr ( Dec_Graph_t *  pGraph, Dec_Edge_t  eEdge0, Dec_Edge_t  eEdge1  )

inlinestatic

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

Synopsis [Creates an OR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 604 of file deco.h.

{
    Dec_Node_t * pNode;
    // get the new node
    pNode = Dec_GraphAppendNode( pGraph );
    // set the inputs and other info
    pNode->eEdge0 = eEdge0;
    pNode->eEdge1 = eEdge1;
    pNode->fCompl0 = eEdge0.fCompl;
    pNode->fCompl1 = eEdge1.fCompl;
    // make adjustments for the OR gate
    pNode->fNodeOr = 1;
    pNode->eEdge0.fCompl = !pNode->eEdge0.fCompl;
    pNode->eEdge1.fCompl = !pNode->eEdge1.fCompl;
    return Dec_EdgeCreate( pGraph->nSize - 1, 1 );
}

static Dec_Edge_t Dec_GraphAddNodeXor ( Dec_Graph_t *  pGraph, Dec_Edge_t  eEdge0, Dec_Edge_t  eEdge1, int  Type  )

inlinestatic

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 632 of file deco.h.

{
    Dec_Edge_t eNode0, eNode1, eNode;
    if ( Type == 0 )
    {
        // derive the first AND
        eEdge0.fCompl ^= 1;
        eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
        eEdge0.fCompl ^= 1;
        // derive the second AND
        eEdge1.fCompl ^= 1;
        eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
        // derive the final OR
        eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
    }
    else
    {
        // derive the first AND
        eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
        // derive the second AND
        eEdge0.fCompl ^= 1;
        eEdge1.fCompl ^= 1;
        eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
        // derive the final OR
        eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
        eNode.fCompl ^= 1;
    }
    return eNode;
}

static Dec_Node_t* Dec_GraphAppendNode ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Appends a new node to the graph.]

Description [This procedure is meant for internal use.]

SideEffects []

SeeAlso []

Definition at line 556 of file deco.h.

{
    Dec_Node_t * pNode;
    if ( pGraph->nSize == pGraph->nCap )
    {
        pGraph->pNodes = ABC_REALLOC( Dec_Node_t, pGraph->pNodes, 2 * pGraph->nCap ); 
        pGraph->nCap   = 2 * pGraph->nCap;
    }
    pNode = pGraph->pNodes + pGraph->nSize++;
    memset( pNode, 0, sizeof(Dec_Node_t) );
    return pNode;
}

static void Dec_GraphComplement ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Checks if the graph is complemented.]

Description []

SideEffects []

SeeAlso []

Definition at line 377 of file deco.h.

{
    pGraph->eRoot.fCompl ^= 1;
}

static Dec_Graph_t* Dec_GraphCreate ( int  nLeaves )

inlinestatic

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

Synopsis [Creates a graph with the given number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 210 of file deco.h.

{
    Dec_Graph_t * pGraph;
    pGraph = ABC_ALLOC( Dec_Graph_t, 1 );
    memset( pGraph, 0, sizeof(Dec_Graph_t) );
    pGraph->nLeaves = nLeaves;
    pGraph->nSize = nLeaves;
    pGraph->nCap = 2 * nLeaves + 50;
    pGraph->pNodes = ABC_ALLOC( Dec_Node_t, pGraph->nCap );
    memset( pGraph->pNodes, 0, sizeof(Dec_Node_t) * pGraph->nSize );
    return pGraph;
}

static Dec_Graph_t* Dec_GraphCreateConst0 ( )

inlinestatic

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

Synopsis [Creates constant 0 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 234 of file deco.h.

{
    Dec_Graph_t * pGraph;
    pGraph = ABC_ALLOC( Dec_Graph_t, 1 );
    memset( pGraph, 0, sizeof(Dec_Graph_t) );
    pGraph->fConst = 1;
    pGraph->eRoot.fCompl = 1;
    return pGraph;
}

static Dec_Graph_t* Dec_GraphCreateConst1 ( )

inlinestatic

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

Synopsis [Creates constant 1 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 255 of file deco.h.

{
    Dec_Graph_t * pGraph;
    pGraph = ABC_ALLOC( Dec_Graph_t, 1 );
    memset( pGraph, 0, sizeof(Dec_Graph_t) );
    pGraph->fConst = 1;
    return pGraph;
}

static Dec_Graph_t* Dec_GraphCreateLeaf ( int  iLeaf, int  nLeaves, int  fCompl  )

inlinestatic

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

Synopsis [Creates the literal graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 275 of file deco.h.

{
    Dec_Graph_t * pGraph;
    assert( 0 <= iLeaf && iLeaf < nLeaves );
    pGraph = Dec_GraphCreate( nLeaves );
    pGraph->eRoot.Node   = iLeaf;
    pGraph->eRoot.fCompl = fCompl;
    return pGraph;
}

static void Dec_GraphFree ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Creates a graph with the given number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 296 of file deco.h.

{
    ABC_FREE( pGraph->pNodes );
    ABC_FREE( pGraph );
}

static int Dec_GraphIsComplement ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns 1 if the graph is complemented.]

Description []

SideEffects []

SeeAlso []

Definition at line 361 of file deco.h.

{
    return pGraph->eRoot.fCompl;
}

static int Dec_GraphIsConst ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns 1 if the graph is a constant.]

Description []

SideEffects []

SeeAlso []

Definition at line 313 of file deco.h.

{
    return pGraph->fConst;
}

static int Dec_GraphIsConst0 ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns 1 if the graph is constant 0.]

Description []

SideEffects []

SeeAlso []

Definition at line 329 of file deco.h.

{
    return pGraph->fConst && pGraph->eRoot.fCompl;
}

static int Dec_GraphIsConst1 ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns 1 if the graph is constant 1.]

Description []

SideEffects []

SeeAlso []

Definition at line 345 of file deco.h.

{
    return pGraph->fConst && !pGraph->eRoot.fCompl;
}

static int Dec_GraphIsVar ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Check if the graph represents elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 474 of file deco.h.

{
    return pGraph->eRoot.Node < (unsigned)pGraph->nLeaves;
}

static int Dec_GraphLeaveNum ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns the number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 394 of file deco.h.

{
    return pGraph->nLeaves;
}

static Dec_Node_t* Dec_GraphNode ( Dec_Graph_t *  pGraph, int  i  )

inlinestatic

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

Synopsis [Returns the pointer to the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 426 of file deco.h.

{
    return pGraph->pNodes + i;
}

static int Dec_GraphNodeInt ( Dec_Graph_t *  pGraph, Dec_Node_t *  pNode  )

inlinestatic

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

Synopsis [Returns the number of the given node.]

Description []

SideEffects []

SeeAlso []

Definition at line 458 of file deco.h.

{
    return pNode - pGraph->pNodes;
}

static int Dec_GraphNodeIsVar ( Dec_Graph_t *  pGraph, Dec_Node_t *  pNode  )

inlinestatic

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

Synopsis [Check if the graph represents elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 490 of file deco.h.

{
    return Dec_GraphNodeInt(pGraph,pNode) < pGraph->nLeaves;
}

static Dec_Node_t* Dec_GraphNodeLast ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns the pointer to the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 442 of file deco.h.

{
    return pGraph->pNodes + pGraph->nSize - 1;
}

static int Dec_GraphNodeNum ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns the number of internal nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 410 of file deco.h.

{
    return pGraph->nSize - pGraph->nLeaves;
}

static void Dec_GraphSetRoot ( Dec_Graph_t *  pGraph, Dec_Edge_t  eRoot  )

inlinestatic

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

Synopsis [Sets the root of the graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 540 of file deco.h.

{
    pGraph->eRoot = eRoot;
}

static Dec_Node_t* Dec_GraphVar ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns the elementary variable elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 506 of file deco.h.

{
    assert( Dec_GraphIsVar( pGraph ) );
    return Dec_GraphNode( pGraph, pGraph->eRoot.Node );
}

static int Dec_GraphVarInt ( Dec_Graph_t *  pGraph )

inlinestatic

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

Synopsis [Returns the number of the elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 523 of file deco.h.

{
    assert( Dec_GraphIsVar( pGraph ) );
    return Dec_GraphNodeInt( pGraph, Dec_GraphVar(pGraph) );
}

static Dec_Edge_t Dec_IntToEdge ( unsigned  Edge )

inlinestatic

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

Synopsis [Converts unsigned integer into the edge.]

Description []

SideEffects []

SeeAlso []

Definition at line 156 of file deco.h.

{
    return Dec_EdgeCreate( Edge >> 1, Edge & 1 ); 
}

static Dec_Edge_t Dec_IntToEdge_ ( unsigned  m )

inlinestatic

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

Synopsis [Converts unsigned integer into the edge.]

Description []

SideEffects []

SeeAlso []

Definition at line 191 of file deco.h.

{ union { Dec_Edge_t x; unsigned y; } v; v.y = m; return v.x;  }