1 /**CFile****************************************************************
2
3 FileName [ivyTable.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [And-Inverter Graph package.]
8
9 Synopsis [Structural hashing table.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - May 11, 2006. ]
16
17 Revision [$Id: ivyTable.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "ivy.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 // hashing the node
Ivy_Hash(Ivy_Obj_t * pObj,int TableSize)31 static unsigned Ivy_Hash( Ivy_Obj_t * pObj, int TableSize )
32 {
33 unsigned Key = Ivy_ObjIsExor(pObj) * 1699;
34 Key ^= Ivy_ObjFaninId0(pObj) * 7937;
35 Key ^= Ivy_ObjFaninId1(pObj) * 2971;
36 Key ^= Ivy_ObjFaninC0(pObj) * 911;
37 Key ^= Ivy_ObjFaninC1(pObj) * 353;
38 Key ^= Ivy_ObjInit(pObj) * 911;
39 return Key % TableSize;
40 }
41
42 // returns the place where this node is stored (or should be stored)
Ivy_TableFind(Ivy_Man_t * p,Ivy_Obj_t * pObj)43 static int * Ivy_TableFind( Ivy_Man_t * p, Ivy_Obj_t * pObj )
44 {
45 int i;
46 assert( Ivy_ObjIsHash(pObj) );
47 for ( i = Ivy_Hash(pObj, p->nTableSize); p->pTable[i]; i = (i+1) % p->nTableSize )
48 if ( p->pTable[i] == pObj->Id )
49 break;
50 return p->pTable + i;
51 }
52
53 static void Ivy_TableResize( Ivy_Man_t * p );
54 static unsigned int Cudd_PrimeAig( unsigned int p );
55
56 ////////////////////////////////////////////////////////////////////////
57 /// FUNCTION DEFINITIONS ///
58 ////////////////////////////////////////////////////////////////////////
59
60 /**Function*************************************************************
61
62 Synopsis [Checks if node with the given attributes is in the hash table.]
63
64 Description []
65
66 SideEffects []
67
68 SeeAlso []
69
70 ***********************************************************************/
Ivy_TableLookup(Ivy_Man_t * p,Ivy_Obj_t * pObj)71 Ivy_Obj_t * Ivy_TableLookup( Ivy_Man_t * p, Ivy_Obj_t * pObj )
72 {
73 Ivy_Obj_t * pEntry;
74 int i;
75 assert( !Ivy_IsComplement(pObj) );
76 if ( !Ivy_ObjIsHash(pObj) )
77 return NULL;
78 assert( Ivy_ObjIsLatch(pObj) || Ivy_ObjFaninId0(pObj) > 0 );
79 assert( Ivy_ObjFaninId1(pObj) == 0 || Ivy_ObjFaninId0(pObj) < Ivy_ObjFaninId1(pObj) );
80 if ( Ivy_ObjFanin0(pObj)->nRefs == 0 || (Ivy_ObjChild1(pObj) && Ivy_ObjFanin1(pObj)->nRefs == 0) )
81 return NULL;
82 for ( i = Ivy_Hash(pObj, p->nTableSize); p->pTable[i]; i = (i+1) % p->nTableSize )
83 {
84 pEntry = Ivy_ManObj( p, p->pTable[i] );
85 if ( Ivy_ObjChild0(pEntry) == Ivy_ObjChild0(pObj) &&
86 Ivy_ObjChild1(pEntry) == Ivy_ObjChild1(pObj) &&
87 Ivy_ObjInit(pEntry) == Ivy_ObjInit(pObj) &&
88 Ivy_ObjType(pEntry) == Ivy_ObjType(pObj) )
89 return pEntry;
90 }
91 return NULL;
92 }
93
94 /**Function*************************************************************
95
96 Synopsis [Adds the node to the hash table.]
97
98 Description []
99
100 SideEffects []
101
102 SeeAlso []
103
104 ***********************************************************************/
Ivy_TableInsert(Ivy_Man_t * p,Ivy_Obj_t * pObj)105 void Ivy_TableInsert( Ivy_Man_t * p, Ivy_Obj_t * pObj )
106 {
107 int * pPlace;
108 assert( !Ivy_IsComplement(pObj) );
109 if ( !Ivy_ObjIsHash(pObj) )
110 return;
111 if ( (pObj->Id & 63) == 0 )
112 {
113 if ( p->nTableSize < 2 * Ivy_ManHashObjNum(p) )
114 Ivy_TableResize( p );
115 }
116 pPlace = Ivy_TableFind( p, pObj );
117 assert( *pPlace == 0 );
118 *pPlace = pObj->Id;
119 }
120
121 /**Function*************************************************************
122
123 Synopsis [Deletes the node from the hash table.]
124
125 Description []
126
127 SideEffects []
128
129 SeeAlso []
130
131 ***********************************************************************/
Ivy_TableDelete(Ivy_Man_t * p,Ivy_Obj_t * pObj)132 void Ivy_TableDelete( Ivy_Man_t * p, Ivy_Obj_t * pObj )
133 {
134 Ivy_Obj_t * pEntry;
135 int i, * pPlace;
136 assert( !Ivy_IsComplement(pObj) );
137 if ( !Ivy_ObjIsHash(pObj) )
138 return;
139 pPlace = Ivy_TableFind( p, pObj );
140 assert( *pPlace == pObj->Id ); // node should be in the table
141 *pPlace = 0;
142 // rehash the adjacent entries
143 i = pPlace - p->pTable;
144 for ( i = (i+1) % p->nTableSize; p->pTable[i]; i = (i+1) % p->nTableSize )
145 {
146 pEntry = Ivy_ManObj( p, p->pTable[i] );
147 p->pTable[i] = 0;
148 Ivy_TableInsert( p, pEntry );
149 }
150 }
151
152 /**Function*************************************************************
153
154 Synopsis [Updates the table to point to the new node.]
155
156 Description [If the old node (pObj) is in the table, updates the table
157 to point to an object with different ID (ObjIdNew). The table should
158 not contain an object with ObjIdNew (this is currently not checked).]
159
160 SideEffects []
161
162 SeeAlso []
163
164 ***********************************************************************/
Ivy_TableUpdate(Ivy_Man_t * p,Ivy_Obj_t * pObj,int ObjIdNew)165 void Ivy_TableUpdate( Ivy_Man_t * p, Ivy_Obj_t * pObj, int ObjIdNew )
166 {
167 int * pPlace;
168 assert( !Ivy_IsComplement(pObj) );
169 if ( !Ivy_ObjIsHash(pObj) )
170 return;
171 pPlace = Ivy_TableFind( p, pObj );
172 assert( *pPlace == pObj->Id ); // node should be in the table
173 *pPlace = ObjIdNew;
174 }
175
176 /**Function*************************************************************
177
178 Synopsis [Count the number of nodes in the table.]
179
180 Description []
181
182 SideEffects []
183
184 SeeAlso []
185
186 ***********************************************************************/
Ivy_TableCountEntries(Ivy_Man_t * p)187 int Ivy_TableCountEntries( Ivy_Man_t * p )
188 {
189 int i, Counter = 0;
190 for ( i = 0; i < p->nTableSize; i++ )
191 Counter += (p->pTable[i] != 0);
192 return Counter;
193 }
194
195 /**Function*************************************************************
196
197 Synopsis [Resizes the table.]
198
199 Description [Typically this procedure should not be called.]
200
201 SideEffects []
202
203 SeeAlso []
204
205 ***********************************************************************/
Ivy_TableResize(Ivy_Man_t * p)206 void Ivy_TableResize( Ivy_Man_t * p )
207 {
208 int * pTableOld, * pPlace;
209 int nTableSizeOld, Counter, nEntries, e;
210 abctime clk;
211 clk = Abc_Clock();
212 // save the old table
213 pTableOld = p->pTable;
214 nTableSizeOld = p->nTableSize;
215 // get the new table
216 p->nTableSize = Abc_PrimeCudd( 5 * Ivy_ManHashObjNum(p) );
217 p->pTable = ABC_ALLOC( int, p->nTableSize );
218 memset( p->pTable, 0, sizeof(int) * p->nTableSize );
219 // rehash the entries from the old table
220 Counter = 0;
221 for ( e = 0; e < nTableSizeOld; e++ )
222 {
223 if ( pTableOld[e] == 0 )
224 continue;
225 Counter++;
226 // get the place where this entry goes in the table table
227 pPlace = Ivy_TableFind( p, Ivy_ManObj(p, pTableOld[e]) );
228 assert( *pPlace == 0 ); // should not be in the table
229 *pPlace = pTableOld[e];
230 }
231 nEntries = Ivy_ManHashObjNum(p);
232 // assert( Counter == nEntries );
233 // printf( "Increasing the structural table size from %6d to %6d. ", nTableSizeOld, p->nTableSize );
234 // ABC_PRT( "Time", Abc_Clock() - clk );
235 // replace the table and the parameters
236 ABC_FREE( pTableOld );
237 }
238
239 /**Function********************************************************************
240
241 Synopsis [Profiles the hash table.]
242
243 Description []
244
245 SideEffects []
246
247 SeeAlso []
248
249 ******************************************************************************/
Ivy_TableProfile(Ivy_Man_t * p)250 void Ivy_TableProfile( Ivy_Man_t * p )
251 {
252 int i, Counter = 0;
253 for ( i = 0; i < p->nTableSize; i++ )
254 {
255 if ( p->pTable[i] )
256 Counter++;
257 else if ( Counter )
258 {
259 printf( "%d ", Counter );
260 Counter = 0;
261 }
262 }
263 }
264
265
266 ////////////////////////////////////////////////////////////////////////
267 /// END OF FILE ///
268 ////////////////////////////////////////////////////////////////////////
269
270
271 ABC_NAMESPACE_IMPL_END
272
273