abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
aigTable.c File Reference
#include "aig.h"

Go to the source code of this file.

Functions

static
ABC_NAMESPACE_IMPL_START
unsigned long 		Aig_Hash (Aig_Obj_t *pObj, int TableSize)
 DECLARATIONS ///. More...
 
static Aig_Obj_t ** Aig_TableFind (Aig_Man_t *p, Aig_Obj_t *pObj)
 
void Aig_TableResize (Aig_Man_t *p)
 FUNCTION DEFINITIONS ///. More...
 
Aig_Obj_t * Aig_TableLookup (Aig_Man_t *p, Aig_Obj_t *pGhost)
 
Aig_Obj_t * Aig_TableLookupTwo (Aig_Man_t *p, Aig_Obj_t *pFanin0, Aig_Obj_t *pFanin1)
 
void Aig_TableInsert (Aig_Man_t *p, Aig_Obj_t *pObj)
 
void Aig_TableDelete (Aig_Man_t *p, Aig_Obj_t *pObj)
 
int Aig_TableCountEntries (Aig_Man_t *p)
 
void Aig_TableProfile (Aig_Man_t *p)
 
void Aig_TableClear (Aig_Man_t *p)
 

Function Documentation

static ABC_NAMESPACE_IMPL_START unsigned long Aig_Hash ( Aig_Obj_t *  pObj,
int  TableSize 
)
static

DECLARATIONS ///.

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

FileName [aigTable.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Structural hashing table.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id:
aigTable.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

]

Definition at line 31 of file aigTable.c.

32 {
33  unsigned long Key = Aig_ObjIsExor(pObj) * 1699;
34  Key ^= Aig_ObjFanin0(pObj)->Id * 7937;
35  Key ^= Aig_ObjFanin1(pObj)->Id * 2971;
36  Key ^= Aig_ObjFaninC0(pObj) * 911;
37  Key ^= Aig_ObjFaninC1(pObj) * 353;
38  return Key % TableSize;
39 }
Aig_ObjFanin0
static Aig_Obj_t * Aig_ObjFanin0(Aig_Obj_t *pObj)
Definition: aig.h:308
Aig_ObjFanin1
static Aig_Obj_t * Aig_ObjFanin1(Aig_Obj_t *pObj)
Definition: aig.h:309
Aig_ObjFaninC0
static int Aig_ObjFaninC0(Aig_Obj_t *pObj)
Definition: aig.h:306
Aig_ObjIsExor
static int Aig_ObjIsExor(Aig_Obj_t *pObj)
Definition: aig.h:279
Aig_ObjFaninC1
static int Aig_ObjFaninC1(Aig_Obj_t *pObj)
Definition: aig.h:307
Aig_Obj_t_::Id
int Id
Definition: aig.h:85
void Aig_TableClear ( Aig_Man_t *  p)

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

Synopsis [Profiles the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 265 of file aigTable.c.

266 {
267  ABC_FREE( p->pTable );
268  p->nTableSize = 0;
269 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
int Aig_TableCountEntries ( Aig_Man_t *  p)

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

Synopsis [Count the number of nodes in the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 218 of file aigTable.c.

219 {
220  Aig_Obj_t * pEntry;
221  int i, Counter = 0;
222  for ( i = 0; i < p->nTableSize; i++ )
223  for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext )
224  Counter++;
225  return Counter;
226 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_Obj_t_
Definition: aig.h:69
Aig_Obj_t_::pNext
Aig_Obj_t * pNext
Definition: aig.h:72
Counter
static int Counter
Definition: extraBddMisc.c:1877
void Aig_TableDelete ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)

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

Synopsis [Deletes the node from the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 196 of file aigTable.c.

197 {
198  Aig_Obj_t ** ppPlace;
199  assert( !Aig_IsComplement(pObj) );
200  ppPlace = Aig_TableFind( p, pObj );
201  assert( *ppPlace == pObj ); // node should be in the table
202  // remove the node
203  *ppPlace = pObj->pNext;
204  pObj->pNext = NULL;
205 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_IsComplement
static int Aig_IsComplement(Aig_Obj_t *p)
Definition: aig.h:249
Aig_Obj_t_
Definition: aig.h:69
Aig_Obj_t_::pNext
Aig_Obj_t * pNext
Definition: aig.h:72
assert
#define assert(ex)
Definition: util_old.h:213
Aig_TableFind
static Aig_Obj_t ** Aig_TableFind(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aigTable.c:42
static Aig_Obj_t** Aig_TableFind ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)
static

Definition at line 42 of file aigTable.c.

43 {
44  Aig_Obj_t ** ppEntry;
45  assert( Aig_ObjChild0(pObj) && Aig_ObjChild1(pObj) );
46  assert( Aig_ObjFanin0(pObj)->Id < Aig_ObjFanin1(pObj)->Id );
47  for ( ppEntry = p->pTable + Aig_Hash(pObj, p->nTableSize); *ppEntry; ppEntry = &(*ppEntry)->pNext )
48  if ( *ppEntry == pObj )
49  return ppEntry;
50  assert( *ppEntry == NULL );
51  return ppEntry;
52 }
Aig_ObjChild0
static Aig_Obj_t * Aig_ObjChild0(Aig_Obj_t *pObj)
Definition: aig.h:310
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_ObjFanin0
static Aig_Obj_t * Aig_ObjFanin0(Aig_Obj_t *pObj)
Definition: aig.h:308
Aig_ObjFanin1
static Aig_Obj_t * Aig_ObjFanin1(Aig_Obj_t *pObj)
Definition: aig.h:309
Aig_Hash
static ABC_NAMESPACE_IMPL_START unsigned long Aig_Hash(Aig_Obj_t *pObj, int TableSize)
DECLARATIONS ///.
Definition: aigTable.c:31
Aig_ObjChild1
static Aig_Obj_t * Aig_ObjChild1(Aig_Obj_t *pObj)
Definition: aig.h:311
Aig_Obj_t_
Definition: aig.h:69
Aig_Obj_t_::pNext
Aig_Obj_t * pNext
Definition: aig.h:72
assert
#define assert(ex)
Definition: util_old.h:213
void Aig_TableInsert ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)

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

Synopsis [Adds the new node to the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 173 of file aigTable.c.

174 {
175  Aig_Obj_t ** ppPlace;
176  assert( !Aig_IsComplement(pObj) );
177  assert( Aig_TableLookup(p, pObj) == NULL );
178  if ( (pObj->Id & 0xFF) == 0 && 2 * p->nTableSize < Aig_ManNodeNum(p) )
179  Aig_TableResize( p );
180  ppPlace = Aig_TableFind( p, pObj );
181  assert( *ppPlace == NULL );
182  *ppPlace = pObj;
183 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_TableResize
void Aig_TableResize(Aig_Man_t *p)
FUNCTION DEFINITIONS ///.
Definition: aigTable.c:69
Aig_IsComplement
static int Aig_IsComplement(Aig_Obj_t *p)
Definition: aig.h:249
Aig_ManNodeNum
static int Aig_ManNodeNum(Aig_Man_t *p)
Definition: aig.h:256
Aig_Obj_t_
Definition: aig.h:69
Aig_TableLookup
Aig_Obj_t * Aig_TableLookup(Aig_Man_t *p, Aig_Obj_t *pGhost)
Definition: aigTable.c:116
assert
#define assert(ex)
Definition: util_old.h:213
Aig_Obj_t_::Id
int Id
Definition: aig.h:85
Aig_TableFind
static Aig_Obj_t ** Aig_TableFind(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aigTable.c:42
Aig_Obj_t* Aig_TableLookup ( Aig_Man_t *  p,
Aig_Obj_t *  pGhost 
)

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

Synopsis [Checks if node with the given attributes is in the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 116 of file aigTable.c.

117 {
118  Aig_Obj_t * pEntry;
119  assert( !Aig_IsComplement(pGhost) );
120  assert( Aig_ObjIsNode(pGhost) );
121  assert( Aig_ObjChild0(pGhost) && Aig_ObjChild1(pGhost) );
122  assert( Aig_ObjFanin0(pGhost)->Id < Aig_ObjFanin1(pGhost)->Id );
123  if ( p->pTable == NULL || !Aig_ObjRefs(Aig_ObjFanin0(pGhost)) || !Aig_ObjRefs(Aig_ObjFanin1(pGhost)) )
124  return NULL;
125  for ( pEntry = p->pTable[Aig_Hash(pGhost, p->nTableSize)]; pEntry; pEntry = pEntry->pNext )
126  {
127  if ( Aig_ObjChild0(pEntry) == Aig_ObjChild0(pGhost) &&
128  Aig_ObjChild1(pEntry) == Aig_ObjChild1(pGhost) &&
129  Aig_ObjType(pEntry) == Aig_ObjType(pGhost) )
130  return pEntry;
131  }
132  return NULL;
133 }
Aig_ObjType
static Aig_Type_t Aig_ObjType(Aig_Obj_t *pObj)
Definition: aig.h:272
Aig_ObjChild0
static Aig_Obj_t * Aig_ObjChild0(Aig_Obj_t *pObj)
Definition: aig.h:310
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_ObjFanin0
static Aig_Obj_t * Aig_ObjFanin0(Aig_Obj_t *pObj)
Definition: aig.h:308
Aig_IsComplement
static int Aig_IsComplement(Aig_Obj_t *p)
Definition: aig.h:249
Aig_ObjFanin1
static Aig_Obj_t * Aig_ObjFanin1(Aig_Obj_t *pObj)
Definition: aig.h:309
Aig_Hash
static ABC_NAMESPACE_IMPL_START unsigned long Aig_Hash(Aig_Obj_t *pObj, int TableSize)
DECLARATIONS ///.
Definition: aigTable.c:31
Aig_ObjIsNode
static int Aig_ObjIsNode(Aig_Obj_t *pObj)
Definition: aig.h:280
Aig_ObjChild1
static Aig_Obj_t * Aig_ObjChild1(Aig_Obj_t *pObj)
Definition: aig.h:311
Aig_Obj_t_
Definition: aig.h:69
Aig_Obj_t_::pNext
Aig_Obj_t * pNext
Definition: aig.h:72
assert
#define assert(ex)
Definition: util_old.h:213
Aig_ObjRefs
static int Aig_ObjRefs(Aig_Obj_t *pObj)
Definition: aig.h:300
Aig_Obj_t* Aig_TableLookupTwo ( Aig_Man_t *  p,
Aig_Obj_t *  pFanin0,
Aig_Obj_t *  pFanin1 
)

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

Synopsis [Checks if node with the given attributes is in the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 146 of file aigTable.c.

147 {
148  Aig_Obj_t * pGhost;
149  // consider simple cases
150  if ( pFanin0 == pFanin1 )
151  return pFanin0;
152  if ( pFanin0 == Aig_Not(pFanin1) )
153  return Aig_ManConst0(p);
154  if ( Aig_Regular(pFanin0) == Aig_ManConst1(p) )
155  return pFanin0 == Aig_ManConst1(p) ? pFanin1 : Aig_ManConst0(p);
156  if ( Aig_Regular(pFanin1) == Aig_ManConst1(p) )
157  return pFanin1 == Aig_ManConst1(p) ? pFanin0 : Aig_ManConst0(p);
158  pGhost = Aig_ObjCreateGhost( p, pFanin0, pFanin1, AIG_OBJ_AND );
159  return Aig_TableLookup( p, pGhost );
160 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_Regular
static Aig_Obj_t * Aig_Regular(Aig_Obj_t *p)
Definition: aig.h:246
Aig_ManConst0
static Aig_Obj_t * Aig_ManConst0(Aig_Man_t *p)
Definition: aig.h:263
Aig_Not
static Aig_Obj_t * Aig_Not(Aig_Obj_t *p)
Definition: aig.h:247
Aig_Obj_t_
Definition: aig.h:69
Aig_ObjCreateGhost
static Aig_Obj_t * Aig_ObjCreateGhost(Aig_Man_t *p, Aig_Obj_t *p0, Aig_Obj_t *p1, Aig_Type_t Type)
Definition: aig.h:346
Aig_ManConst1
static Aig_Obj_t * Aig_ManConst1(Aig_Man_t *p)
Definition: aig.h:264
Aig_TableLookup
Aig_Obj_t * Aig_TableLookup(Aig_Man_t *p, Aig_Obj_t *pGhost)
Definition: aigTable.c:116
void Aig_TableProfile ( Aig_Man_t *  p)

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

Synopsis [Profiles the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 239 of file aigTable.c.

240 {
241  Aig_Obj_t * pEntry;
242  int i, Counter;
243  printf( "Table size = %d. Entries = %d.\n", p->nTableSize, Aig_ManNodeNum(p) );
244  for ( i = 0; i < p->nTableSize; i++ )
245  {
246  Counter = 0;
247  for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext )
248  Counter++;
249  if ( Counter )
250  printf( "%d ", Counter );
251  }
252 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_ManNodeNum
static int Aig_ManNodeNum(Aig_Man_t *p)
Definition: aig.h:256
Aig_Obj_t_
Definition: aig.h:69
Aig_Obj_t_::pNext
Aig_Obj_t * pNext
Definition: aig.h:72
Counter
static int Counter
Definition: extraBddMisc.c:1877
void Aig_TableResize ( Aig_Man_t *  p)

FUNCTION DEFINITIONS ///.

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

Synopsis [Resizes the table.]

Description [Typically this procedure should not be called.]

SideEffects []

SeeAlso []

Definition at line 69 of file aigTable.c.

70 {
71  Aig_Obj_t * pEntry, * pNext;
72  Aig_Obj_t ** pTableOld, ** ppPlace;
73  int nTableSizeOld, Counter, i;
74  abctime clk;
75  assert( p->pTable != NULL );
76 clk = Abc_Clock();
77  // save the old table
78  pTableOld = p->pTable;
79  nTableSizeOld = p->nTableSize;
80  // get the new table
81  p->nTableSize = Abc_PrimeCudd( 2 * Aig_ManNodeNum(p) );
82  p->pTable = ABC_ALLOC( Aig_Obj_t *, p->nTableSize );
83  memset( p->pTable, 0, sizeof(Aig_Obj_t *) * p->nTableSize );
84  // rehash the entries from the old table
85  Counter = 0;
86  for ( i = 0; i < nTableSizeOld; i++ )
87  for ( pEntry = pTableOld[i], pNext = pEntry? pEntry->pNext : NULL;
88  pEntry; pEntry = pNext, pNext = pEntry? pEntry->pNext : NULL )
89  {
90  // get the place where this entry goes in the table
91  ppPlace = Aig_TableFind( p, pEntry );
92  assert( *ppPlace == NULL ); // should not be there
93  // add the entry to the list
94  *ppPlace = pEntry;
95  pEntry->pNext = NULL;
96  Counter++;
97  }
98  assert( Counter == Aig_ManNodeNum(p) );
99 // printf( "Increasing the structural table size from %6d to %6d. ", nTableSizeOld, p->nTableSize );
100 // ABC_PRT( "Time", Abc_Clock() - clk );
101  // replace the table and the parameters
102  ABC_FREE( pTableOld );
103 }
memset
char * memset()
Abc_PrimeCudd
static int Abc_PrimeCudd(unsigned int p)
Definition: abc_global.h:383
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Aig_ManNodeNum
static int Aig_ManNodeNum(Aig_Man_t *p)
Definition: aig.h:256
Aig_Obj_t_
Definition: aig.h:69
Aig_Obj_t_::pNext
Aig_Obj_t * pNext
Definition: aig.h:72
Counter
static int Counter
Definition: extraBddMisc.c:1877
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
assert
#define assert(ex)
Definition: util_old.h:213
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Aig_TableFind
static Aig_Obj_t ** Aig_TableFind(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aigTable.c:42