src/aig/deco/deco.h File Reference

This graph shows which files directly or indirectly include this file:

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_

Defines

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

Typedefs

typedef struct Dec_Edge_t_ Dec_Edge_t
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)
static unsigned Dec_EdgeToInt (Dec_Edge_t eEdge)
static Dec_Edge_t Dec_IntToEdge (unsigned Edge)
static unsigned Dec_EdgeToInt_ (Dec_Edge_t eEdge)
static Dec_Edge_t Dec_IntToEdge_ (unsigned Edge)
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)

Define Documentation

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

ITERATORS ///

Definition at line 95 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 98 of file deco.h.

Typedef Documentation

typedef struct Dec_Edge_t_ Dec_Edge_t

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

] INCLUDES /// PARAMETERS /// BASIC TYPES ///

Definition at line 40 of file deco.h.

typedef struct Dec_Graph_t_ Dec_Graph_t

Definition at line 65 of file deco.h.

typedef struct Dec_Man_t_ Dec_Man_t

Definition at line 76 of file deco.h.

typedef struct Dec_Node_t_ Dec_Node_t

Definition at line 47 of file deco.h.

Function Documentation

static Dec_Edge_t Dec_EdgeCreate ( int  Node,
int  fCompl 
) [inline, static]

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 120 of file deco.h.

00121 {
00122     Dec_Edge_t eEdge = { fCompl, Node }; 
00123     return eEdge; 
00124 }

static unsigned Dec_EdgeToInt ( Dec_Edge_t  eEdge  )  [inline, static]

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

Synopsis [Converts the edge into unsigned integer.]

Description []

SideEffects []

SeeAlso []

Definition at line 137 of file deco.h.

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

static unsigned Dec_EdgeToInt_ ( Dec_Edge_t  eEdge  )  [inline, static]

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

Synopsis [Converts the edge into unsigned integer.]

Description []

SideEffects []

SeeAlso []

Definition at line 169 of file deco.h.

00170 {
00171     return *(unsigned *)&eEdge;
00172 }

static Dec_Edge_t Dec_GraphAddNodeAnd ( Dec_Graph_t *  pGraph,
Dec_Edge_t  eEdge0,
Dec_Edge_t  eEdge1 
) [inline, static]

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

Synopsis [Creates an AND node.]

Description []

SideEffects []

SeeAlso []

Definition at line 571 of file deco.h.

00572 {
00573     Dec_Node_t * pNode;
00574     // get the new node
00575     pNode = Dec_GraphAppendNode( pGraph );
00576     // set the inputs and other info
00577     pNode->eEdge0 = eEdge0;
00578     pNode->eEdge1 = eEdge1;
00579     pNode->fCompl0 = eEdge0.fCompl;
00580     pNode->fCompl1 = eEdge1.fCompl;
00581     return Dec_EdgeCreate( pGraph->nSize - 1, 0 );
00582 }

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

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 664 of file deco.h.

00665 {
00666     Dec_Edge_t eNode0, eNode1, eNode;
00667     if ( Type == 0 )
00668     {
00669         // derive the first AND
00670         eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
00671         // derive the second AND
00672         eEdgeC.fCompl ^= 1;
00673         eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
00674         // derive the final OR
00675         eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00676     }
00677     else
00678     {
00679         // complement the arguments
00680         eEdgeT.fCompl ^= 1;
00681         eEdgeE.fCompl ^= 1;
00682         // derive the first AND
00683         eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
00684         // derive the second AND
00685         eEdgeC.fCompl ^= 1;
00686         eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
00687         // derive the final OR
00688         eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00689         eNode.fCompl ^= 1;
00690     }
00691     return eNode;
00692 }

static Dec_Edge_t Dec_GraphAddNodeOr ( Dec_Graph_t *  pGraph,
Dec_Edge_t  eEdge0,
Dec_Edge_t  eEdge1 
) [inline, static]

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

Synopsis [Creates an OR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 595 of file deco.h.

00596 {
00597     Dec_Node_t * pNode;
00598     // get the new node
00599     pNode = Dec_GraphAppendNode( pGraph );
00600     // set the inputs and other info
00601     pNode->eEdge0 = eEdge0;
00602     pNode->eEdge1 = eEdge1;
00603     pNode->fCompl0 = eEdge0.fCompl;
00604     pNode->fCompl1 = eEdge1.fCompl;
00605     // make adjustments for the OR gate
00606     pNode->fNodeOr = 1;
00607     pNode->eEdge0.fCompl = !pNode->eEdge0.fCompl;
00608     pNode->eEdge1.fCompl = !pNode->eEdge1.fCompl;
00609     return Dec_EdgeCreate( pGraph->nSize - 1, 1 );
00610 }

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

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 623 of file deco.h.

00624 {
00625     Dec_Edge_t eNode0, eNode1, eNode;
00626     if ( Type == 0 )
00627     {
00628         // derive the first AND
00629         eEdge0.fCompl ^= 1;
00630         eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00631         eEdge0.fCompl ^= 1;
00632         // derive the second AND
00633         eEdge1.fCompl ^= 1;
00634         eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00635         // derive the final OR
00636         eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00637     }
00638     else
00639     {
00640         // derive the first AND
00641         eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00642         // derive the second AND
00643         eEdge0.fCompl ^= 1;
00644         eEdge1.fCompl ^= 1;
00645         eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00646         // derive the final OR
00647         eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00648         eNode.fCompl ^= 1;
00649     }
00650     return eNode;
00651 }

static Dec_Node_t* Dec_GraphAppendNode ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Appends a new node to the graph.]

Description [This procedure is meant for internal use.]

SideEffects []

SeeAlso []

Definition at line 547 of file deco.h.

00548 {
00549     Dec_Node_t * pNode;
00550     if ( pGraph->nSize == pGraph->nCap )
00551     {
00552         pGraph->pNodes = REALLOC( Dec_Node_t, pGraph->pNodes, 2 * pGraph->nCap ); 
00553         pGraph->nCap   = 2 * pGraph->nCap;
00554     }
00555     pNode = pGraph->pNodes + pGraph->nSize++;
00556     memset( pNode, 0, sizeof(Dec_Node_t) );
00557     return pNode;
00558 }

static void Dec_GraphComplement ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Checks if the graph is complemented.]

Description []

SideEffects []

SeeAlso []

Definition at line 368 of file deco.h.

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

static Dec_Graph_t* Dec_GraphCreate ( int  nLeaves  )  [inline, static]

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 201 of file deco.h.

00202 {
00203     Dec_Graph_t * pGraph;
00204     pGraph = ALLOC( Dec_Graph_t, 1 );
00205     memset( pGraph, 0, sizeof(Dec_Graph_t) );
00206     pGraph->nLeaves = nLeaves;
00207     pGraph->nSize = nLeaves;
00208     pGraph->nCap = 2 * nLeaves + 50;
00209     pGraph->pNodes = ALLOC( Dec_Node_t, pGraph->nCap );
00210     memset( pGraph->pNodes, 0, sizeof(Dec_Node_t) * pGraph->nSize );
00211     return pGraph;
00212 }

static Dec_Graph_t* Dec_GraphCreateConst0 (  )  [inline, static]

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

Synopsis [Creates constant 0 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 225 of file deco.h.

00226 {
00227     Dec_Graph_t * pGraph;
00228     pGraph = ALLOC( Dec_Graph_t, 1 );
00229     memset( pGraph, 0, sizeof(Dec_Graph_t) );
00230     pGraph->fConst = 1;
00231     pGraph->eRoot.fCompl = 1;
00232     return pGraph;
00233 }

static Dec_Graph_t* Dec_GraphCreateConst1 (  )  [inline, static]

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

Synopsis [Creates constant 1 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 246 of file deco.h.

00247 {
00248     Dec_Graph_t * pGraph;
00249     pGraph = ALLOC( Dec_Graph_t, 1 );
00250     memset( pGraph, 0, sizeof(Dec_Graph_t) );
00251     pGraph->fConst = 1;
00252     return pGraph;
00253 }

static Dec_Graph_t* Dec_GraphCreateLeaf ( int  iLeaf,
int  nLeaves,
int  fCompl 
) [inline, static]

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

Synopsis [Creates the literal graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 266 of file deco.h.

00267 {
00268     Dec_Graph_t * pGraph;
00269     assert( 0 <= iLeaf && iLeaf < nLeaves );
00270     pGraph = Dec_GraphCreate( nLeaves );
00271     pGraph->eRoot.Node   = iLeaf;
00272     pGraph->eRoot.fCompl = fCompl;
00273     return pGraph;
00274 }

static void Dec_GraphFree ( Dec_Graph_t *  pGraph  )  [inline, static]

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 287 of file deco.h.

00288 {
00289     FREE( pGraph->pNodes );
00290     free( pGraph );
00291 }

static int Dec_GraphIsComplement ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns 1 if the graph is complemented.]

Description []

SideEffects []

SeeAlso []

Definition at line 352 of file deco.h.

00353 {
00354     return pGraph->eRoot.fCompl;
00355 }

static int Dec_GraphIsConst ( Dec_Graph_t *  pGraph  )  [inline, static]

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 304 of file deco.h.

00305 {
00306     return pGraph->fConst;
00307 }

static int Dec_GraphIsConst0 ( Dec_Graph_t *  pGraph  )  [inline, static]

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 320 of file deco.h.

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

static int Dec_GraphIsConst1 ( Dec_Graph_t *  pGraph  )  [inline, static]

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 336 of file deco.h.

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

static int Dec_GraphIsVar ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Check if the graph represents elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 465 of file deco.h.

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

static int Dec_GraphLeaveNum ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 385 of file deco.h.

00386 {
00387     return pGraph->nLeaves;
00388 }

static Dec_Node_t* Dec_GraphNode ( Dec_Graph_t *  pGraph,
int  i 
) [inline, static]

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

Synopsis [Returns the pointer to the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 417 of file deco.h.

00418 {
00419     return pGraph->pNodes + i;
00420 }

static int Dec_GraphNodeInt ( Dec_Graph_t *  pGraph,
Dec_Node_t *  pNode 
) [inline, static]

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

Synopsis [Returns the number of the given node.]

Description []

SideEffects []

SeeAlso []

Definition at line 449 of file deco.h.

00450 {
00451     return pNode - pGraph->pNodes;
00452 }

static int Dec_GraphNodeIsVar ( Dec_Graph_t *  pGraph,
Dec_Node_t *  pNode 
) [inline, static]

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

Synopsis [Check if the graph represents elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 481 of file deco.h.

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

static Dec_Node_t* Dec_GraphNodeLast ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the pointer to the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 433 of file deco.h.

00434 {
00435     return pGraph->pNodes + pGraph->nSize - 1;
00436 }

static int Dec_GraphNodeNum ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the number of internal nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 401 of file deco.h.

00402 {
00403     return pGraph->nSize - pGraph->nLeaves;
00404 }

static void Dec_GraphSetRoot ( Dec_Graph_t *  pGraph,
Dec_Edge_t  eRoot 
) [inline, static]

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

Synopsis [Sets the root of the graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 531 of file deco.h.

00532 {
00533     pGraph->eRoot = eRoot;
00534 }

static Dec_Node_t* Dec_GraphVar ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the elementary variable elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 497 of file deco.h.

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

static int Dec_GraphVarInt ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the number of the elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 514 of file deco.h.

00515 {
00516     assert( Dec_GraphIsVar( pGraph ) );
00517     return Dec_GraphNodeInt( pGraph, Dec_GraphVar(pGraph) );
00518 }

static Dec_Edge_t Dec_IntToEdge ( unsigned  Edge  )  [inline, static]

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

Synopsis [Converts unsigned integer into the edge.]

Description []

SideEffects []

SeeAlso []

Definition at line 153 of file deco.h.

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

static Dec_Edge_t Dec_IntToEdge_ ( unsigned  Edge  )  [inline, static]

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

Synopsis [Converts unsigned integer into the edge.]

Description []

SideEffects []

SeeAlso []

Definition at line 185 of file deco.h.

00186 {
00187     return *(Dec_Edge_t *)&Edge;
00188 }

Generated on Tue Jan 5 12:18:18 2010 for abc70930 by  doxygen 1.6.1