1 /**CFile****************************************************************
2
3 FileName [hopTable.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Minimalistic 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: hopTable.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "hop.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 // hashing the node
Hop_Hash(Hop_Obj_t * pObj,int TableSize)31 static unsigned long Hop_Hash( Hop_Obj_t * pObj, int TableSize )
32 {
33 unsigned long Key = Hop_ObjIsExor(pObj) * 1699;
34 Key ^= Hop_ObjFanin0(pObj)->Id * 7937;
35 Key ^= Hop_ObjFanin1(pObj)->Id * 2971;
36 Key ^= Hop_ObjFaninC0(pObj) * 911;
37 Key ^= Hop_ObjFaninC1(pObj) * 353;
38 return Key % TableSize;
39 }
40
41 // returns the place where this node is stored (or should be stored)
Hop_TableFind(Hop_Man_t * p,Hop_Obj_t * pObj)42 static Hop_Obj_t ** Hop_TableFind( Hop_Man_t * p, Hop_Obj_t * pObj )
43 {
44 Hop_Obj_t ** ppEntry;
45 assert( Hop_ObjChild0(pObj) && Hop_ObjChild1(pObj) );
46 assert( Hop_ObjFanin0(pObj)->Id < Hop_ObjFanin1(pObj)->Id );
47 for ( ppEntry = p->pTable + Hop_Hash(pObj, p->nTableSize); *ppEntry; ppEntry = &(*ppEntry)->pNext )
48 if ( *ppEntry == pObj )
49 return ppEntry;
50 assert( *ppEntry == NULL );
51 return ppEntry;
52 }
53
54 static void Hop_TableResize( Hop_Man_t * p );
55
56 ////////////////////////////////////////////////////////////////////////
57 /// FUNCTION DEFINITIONS ///
58 ////////////////////////////////////////////////////////////////////////
59
60 /**Function*************************************************************
61
62 Synopsis [Checks if a node with the given attributes is in the hash table.]
63
64 Description []
65
66 SideEffects []
67
68 SeeAlso []
69
70 ***********************************************************************/
Hop_TableLookup(Hop_Man_t * p,Hop_Obj_t * pGhost)71 Hop_Obj_t * Hop_TableLookup( Hop_Man_t * p, Hop_Obj_t * pGhost )
72 {
73 Hop_Obj_t * pEntry;
74 assert( !Hop_IsComplement(pGhost) );
75 assert( Hop_ObjChild0(pGhost) && Hop_ObjChild1(pGhost) );
76 assert( Hop_ObjFanin0(pGhost)->Id < Hop_ObjFanin1(pGhost)->Id );
77 if ( p->fRefCount && (!Hop_ObjRefs(Hop_ObjFanin0(pGhost)) || !Hop_ObjRefs(Hop_ObjFanin1(pGhost))) )
78 return NULL;
79 for ( pEntry = p->pTable[Hop_Hash(pGhost, p->nTableSize)]; pEntry; pEntry = pEntry->pNext )
80 {
81 if ( Hop_ObjChild0(pEntry) == Hop_ObjChild0(pGhost) &&
82 Hop_ObjChild1(pEntry) == Hop_ObjChild1(pGhost) &&
83 Hop_ObjType(pEntry) == Hop_ObjType(pGhost) )
84 return pEntry;
85 }
86 return NULL;
87 }
88
89 /**Function*************************************************************
90
91 Synopsis [Adds the new node to the hash table.]
92
93 Description []
94
95 SideEffects []
96
97 SeeAlso []
98
99 ***********************************************************************/
Hop_TableInsert(Hop_Man_t * p,Hop_Obj_t * pObj)100 void Hop_TableInsert( Hop_Man_t * p, Hop_Obj_t * pObj )
101 {
102 Hop_Obj_t ** ppPlace;
103 assert( !Hop_IsComplement(pObj) );
104 assert( Hop_TableLookup(p, pObj) == NULL );
105 if ( (pObj->Id & 0xFF) == 0 && 2 * p->nTableSize < Hop_ManNodeNum(p) )
106 Hop_TableResize( p );
107 ppPlace = Hop_TableFind( p, pObj );
108 assert( *ppPlace == NULL );
109 *ppPlace = pObj;
110 }
111
112 /**Function*************************************************************
113
114 Synopsis [Deletes the node from the hash table.]
115
116 Description []
117
118 SideEffects []
119
120 SeeAlso []
121
122 ***********************************************************************/
Hop_TableDelete(Hop_Man_t * p,Hop_Obj_t * pObj)123 void Hop_TableDelete( Hop_Man_t * p, Hop_Obj_t * pObj )
124 {
125 Hop_Obj_t ** ppPlace;
126 assert( !Hop_IsComplement(pObj) );
127 ppPlace = Hop_TableFind( p, pObj );
128 assert( *ppPlace == pObj ); // node should be in the table
129 // remove the node
130 *ppPlace = pObj->pNext;
131 pObj->pNext = NULL;
132 }
133
134 /**Function*************************************************************
135
136 Synopsis [Count the number of nodes in the table.]
137
138 Description []
139
140 SideEffects []
141
142 SeeAlso []
143
144 ***********************************************************************/
Hop_TableCountEntries(Hop_Man_t * p)145 int Hop_TableCountEntries( Hop_Man_t * p )
146 {
147 Hop_Obj_t * pEntry;
148 int i, Counter = 0;
149 for ( i = 0; i < p->nTableSize; i++ )
150 for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext )
151 Counter++;
152 return Counter;
153 }
154
155 /**Function*************************************************************
156
157 Synopsis [Resizes the table.]
158
159 Description [Typically this procedure should not be called.]
160
161 SideEffects []
162
163 SeeAlso []
164
165 ***********************************************************************/
Hop_TableResize(Hop_Man_t * p)166 void Hop_TableResize( Hop_Man_t * p )
167 {
168 Hop_Obj_t * pEntry, * pNext;
169 Hop_Obj_t ** pTableOld, ** ppPlace;
170 int nTableSizeOld, Counter, nEntries, i;
171 abctime clk;
172 clk = Abc_Clock();
173 // save the old table
174 pTableOld = p->pTable;
175 nTableSizeOld = p->nTableSize;
176 // get the new table
177 p->nTableSize = Abc_PrimeCudd( 2 * Hop_ManNodeNum(p) );
178 p->pTable = ABC_ALLOC( Hop_Obj_t *, p->nTableSize );
179 memset( p->pTable, 0, sizeof(Hop_Obj_t *) * p->nTableSize );
180 // rehash the entries from the old table
181 Counter = 0;
182 for ( i = 0; i < nTableSizeOld; i++ )
183 for ( pEntry = pTableOld[i], pNext = pEntry? pEntry->pNext : NULL; pEntry; pEntry = pNext, pNext = pEntry? pEntry->pNext : NULL )
184 {
185 // get the place where this entry goes in the table
186 ppPlace = Hop_TableFind( p, pEntry );
187 assert( *ppPlace == NULL ); // should not be there
188 // add the entry to the list
189 *ppPlace = pEntry;
190 pEntry->pNext = NULL;
191 Counter++;
192 }
193 nEntries = Hop_ManNodeNum(p);
194 assert( Counter == nEntries );
195 // printf( "Increasing the structural table size from %6d to %6d. ", nTableSizeOld, p->nTableSize );
196 // ABC_PRT( "Time", Abc_Clock() - clk );
197 // replace the table and the parameters
198 ABC_FREE( pTableOld );
199 }
200
201 /**Function********************************************************************
202
203 Synopsis [Profiles the hash table.]
204
205 Description []
206
207 SideEffects []
208
209 SeeAlso []
210
211 ******************************************************************************/
Hop_TableProfile(Hop_Man_t * p)212 void Hop_TableProfile( Hop_Man_t * p )
213 {
214 Hop_Obj_t * pEntry;
215 int i, Counter;
216 for ( i = 0; i < p->nTableSize; i++ )
217 {
218 Counter = 0;
219 for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext )
220 Counter++;
221 if ( Counter )
222 printf( "%d ", Counter );
223 }
224 }
225
226 ////////////////////////////////////////////////////////////////////////
227 /// END OF FILE ///
228 ////////////////////////////////////////////////////////////////////////
229
230
231 ABC_NAMESPACE_IMPL_END
232
233