abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fpgaVec.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [fpgaVec.c]
4 
5  PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6 
7  Synopsis [Technology mapping for variable-size-LUT FPGAs.]
8 
9  Author [MVSIS Group]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 2.0. Started - August 18, 2004.]
14 
15  Revision [$Id: fpgaVec.c,v 1.3 2005/01/23 06:59:42 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "fpgaInt.h"
20 
21 ABC_NAMESPACE_IMPL_START
22 
23 
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27 
28 static int Fpga_NodeVecCompareLevels( Fpga_Node_t ** pp1, Fpga_Node_t ** pp2 );
29 
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 /**Function*************************************************************
35 
36  Synopsis [Allocates a vector with the given capacity.]
37 
38  Description []
39 
40  SideEffects []
41 
42  SeeAlso []
43 
44 ***********************************************************************/
45 Fpga_NodeVec_t * Fpga_NodeVecAlloc( int nCap )
46 {
47  Fpga_NodeVec_t * p;
48  p = ABC_ALLOC( Fpga_NodeVec_t, 1 );
49  if ( nCap > 0 && nCap < 16 )
50  nCap = 16;
51  p->nSize = 0;
52  p->nCap = nCap;
53  p->pArray = p->nCap? ABC_ALLOC( Fpga_Node_t *, p->nCap ) : NULL;
54  return p;
55 }
56 
57 /**Function*************************************************************
58 
59  Synopsis []
60 
61  Description []
62 
63  SideEffects []
64 
65  SeeAlso []
66 
67 ***********************************************************************/
68 void Fpga_NodeVecFree( Fpga_NodeVec_t * p )
69 {
70  ABC_FREE( p->pArray );
71  ABC_FREE( p );
72 }
73 
74 /**Function*************************************************************
75 
76  Synopsis []
77 
78  Description []
79 
80  SideEffects []
81 
82  SeeAlso []
83 
84 ***********************************************************************/
85 Fpga_Node_t ** Fpga_NodeVecReadArray( Fpga_NodeVec_t * p )
86 {
87  return p->pArray;
88 }
89 
90 /**Function*************************************************************
91 
92  Synopsis []
93 
94  Description []
95 
96  SideEffects []
97 
98  SeeAlso []
99 
100 ***********************************************************************/
101 int Fpga_NodeVecReadSize( Fpga_NodeVec_t * p )
102 {
103  return p->nSize;
104 }
105 
106 /**Function*************************************************************
107 
108  Synopsis [Resizes the vector to the given capacity.]
109 
110  Description []
111 
112  SideEffects []
113 
114  SeeAlso []
115 
116 ***********************************************************************/
117 void Fpga_NodeVecGrow( Fpga_NodeVec_t * p, int nCapMin )
118 {
119  if ( p->nCap >= nCapMin )
120  return;
121  p->pArray = ABC_REALLOC( Fpga_Node_t *, p->pArray, nCapMin );
122  p->nCap = nCapMin;
123 }
124 
125 /**Function*************************************************************
126 
127  Synopsis []
128 
129  Description []
130 
131  SideEffects []
132 
133  SeeAlso []
134 
135 ***********************************************************************/
136 void Fpga_NodeVecShrink( Fpga_NodeVec_t * p, int nSizeNew )
137 {
138  assert( p->nSize >= nSizeNew );
139  p->nSize = nSizeNew;
140 }
141 
142 /**Function*************************************************************
143 
144  Synopsis []
145 
146  Description []
147 
148  SideEffects []
149 
150  SeeAlso []
151 
152 ***********************************************************************/
153 void Fpga_NodeVecClear( Fpga_NodeVec_t * p )
154 {
155  p->nSize = 0;
156 }
157 
158 /**Function*************************************************************
159 
160  Synopsis []
161 
162  Description []
163 
164  SideEffects []
165 
166  SeeAlso []
167 
168 ***********************************************************************/
169 void Fpga_NodeVecPush( Fpga_NodeVec_t * p, Fpga_Node_t * Entry )
170 {
171  if ( p->nSize == p->nCap )
172  {
173  if ( p->nCap < 16 )
174  Fpga_NodeVecGrow( p, 16 );
175  else
176  Fpga_NodeVecGrow( p, 2 * p->nCap );
177  }
178  p->pArray[p->nSize++] = Entry;
179 }
180 
181 /**Function*************************************************************
182 
183  Synopsis [Add the element while ensuring uniqueness.]
184 
185  Description [Returns 1 if the element was found, and 0 if it was new. ]
186 
187  SideEffects []
188 
189  SeeAlso []
190 
191 ***********************************************************************/
192 int Fpga_NodeVecPushUnique( Fpga_NodeVec_t * p, Fpga_Node_t * Entry )
193 {
194  int i;
195  for ( i = 0; i < p->nSize; i++ )
196  if ( p->pArray[i] == Entry )
197  return 1;
198  Fpga_NodeVecPush( p, Entry );
199  return 0;
200 }
201 
202 /**Function*************************************************************
203 
204  Synopsis []
205 
206  Description []
207 
208  SideEffects []
209 
210  SeeAlso []
211 
212 ***********************************************************************/
213 Fpga_Node_t * Fpga_NodeVecPop( Fpga_NodeVec_t * p )
214 {
215  return p->pArray[--p->nSize];
216 }
217 
218 /**Function*************************************************************
219 
220  Synopsis []
221 
222  Description []
223 
224  SideEffects []
225 
226  SeeAlso []
227 
228 ***********************************************************************/
229 void Fpga_NodeVecWriteEntry( Fpga_NodeVec_t * p, int i, Fpga_Node_t * Entry )
230 {
231  assert( i >= 0 && i < p->nSize );
232  p->pArray[i] = Entry;
233 }
234 
235 /**Function*************************************************************
236 
237  Synopsis []
238 
239  Description []
240 
241  SideEffects []
242 
243  SeeAlso []
244 
245 ***********************************************************************/
246 Fpga_Node_t * Fpga_NodeVecReadEntry( Fpga_NodeVec_t * p, int i )
247 {
248  assert( i >= 0 && i < p->nSize );
249  return p->pArray[i];
250 }
251 
252 /**Function*************************************************************
253 
254  Synopsis [Comparison procedure for two nodes.]
255 
256  Description []
257 
258  SideEffects []
259 
260  SeeAlso []
261 
262 ***********************************************************************/
263 int Fpga_NodeVecCompareLevels( Fpga_Node_t ** pp1, Fpga_Node_t ** pp2 )
264 {
265  int Level1 = Fpga_Regular(*pp1)->Level;
266  int Level2 = Fpga_Regular(*pp2)->Level;
267  if ( Level1 < Level2 )
268  return -1;
269  if ( Level1 > Level2 )
270  return 1;
271  if ( Fpga_Regular(*pp1)->Num < Fpga_Regular(*pp2)->Num )
272  return -1;
273  if ( Fpga_Regular(*pp1)->Num > Fpga_Regular(*pp2)->Num )
274  return 1;
275  return 0;
276 }
277 
278 /**Function*************************************************************
279 
280  Synopsis [Sorting the entries by their integer value.]
281 
282  Description []
283 
284  SideEffects []
285 
286  SeeAlso []
287 
288 ***********************************************************************/
289 void Fpga_NodeVecSortByLevel( Fpga_NodeVec_t * p )
290 {
291  qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *),
292  (int (*)(const void *, const void *)) Fpga_NodeVecCompareLevels );
293 }
294 
295 /**Function*************************************************************
296 
297  Synopsis [Compares the arrival times.]
298 
299  Description []
300 
301  SideEffects []
302 
303  SeeAlso []
304 
305 ***********************************************************************/
306 int Fpga_NodeVecCompareArrivals( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 )
307 {
308  if ( (*ppS1)->pCutBest->tArrival < (*ppS2)->pCutBest->tArrival )
309  return -1;
310  if ( (*ppS1)->pCutBest->tArrival > (*ppS2)->pCutBest->tArrival )
311  return 1;
312  return 0;
313 }
314 
315 /**Function*************************************************************
316 
317  Synopsis [Orders the nodes in the increasing order of the arrival times.]
318 
319  Description []
320 
321  SideEffects []
322 
323  SeeAlso []
324 
325 ***********************************************************************/
326 void Fpga_SortNodesByArrivalTimes( Fpga_NodeVec_t * p )
327 {
328  qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *),
329  (int (*)(const void *, const void *)) Fpga_NodeVecCompareArrivals );
330 // assert( Fpga_CompareNodesByLevel( p->pArray, p->pArray + p->nSize - 1 ) <= 0 );
331 }
332 
333 
334 /**Function*************************************************************
335 
336  Synopsis [Computes the union of nodes in two arrays.]
337 
338  Description []
339 
340  SideEffects []
341 
342  SeeAlso []
343 
344 ***********************************************************************/
345 void Fpga_NodeVecUnion( Fpga_NodeVec_t * p, Fpga_NodeVec_t * p1, Fpga_NodeVec_t * p2 )
346 {
347  int i;
348  Fpga_NodeVecClear( p );
349  for ( i = 0; i < p1->nSize; i++ )
350  Fpga_NodeVecPush( p, p1->pArray[i] );
351  for ( i = 0; i < p2->nSize; i++ )
352  Fpga_NodeVecPush( p, p2->pArray[i] );
353 }
354 
355 /**Function*************************************************************
356 
357  Synopsis [Inserts a new node in the order by arrival times.]
358 
359  Description []
360 
361  SideEffects []
362 
363  SeeAlso []
364 
365 ***********************************************************************/
366 void Fpga_NodeVecPushOrder( Fpga_NodeVec_t * vNodes, Fpga_Node_t * pNode, int fIncreasing )
367 {
368  Fpga_Node_t * pNode1, * pNode2;
369  int i;
370  Fpga_NodeVecPush( vNodes, pNode );
371  // find the place of the node
372  for ( i = vNodes->nSize-1; i > 0; i-- )
373  {
374  pNode1 = vNodes->pArray[i ];
375  pNode2 = vNodes->pArray[i-1];
376  if (( fIncreasing && pNode1->pCutBest->tArrival >= pNode2->pCutBest->tArrival) ||
377  (!fIncreasing && pNode1->pCutBest->tArrival <= pNode2->pCutBest->tArrival) )
378  break;
379  vNodes->pArray[i ] = pNode2;
380  vNodes->pArray[i-1] = pNode1;
381  }
382 }
383 
384 /**Function*************************************************************
385 
386  Synopsis [Inserts a new node in the order by arrival times.]
387 
388  Description []
389 
390  SideEffects []
391 
392  SeeAlso []
393 
394 ***********************************************************************/
395 void Fpga_NodeVecReverse( Fpga_NodeVec_t * vNodes )
396 {
397  Fpga_Node_t * pNode1, * pNode2;
398  int i;
399  for ( i = 0; i < vNodes->nSize/2; i++ )
400  {
401  pNode1 = vNodes->pArray[i];
402  pNode2 = vNodes->pArray[vNodes->nSize-1-i];
403  vNodes->pArray[i] = pNode2;
404  vNodes->pArray[vNodes->nSize-1-i] = pNode1;
405  }
406 }
407 
408 ////////////////////////////////////////////////////////////////////////
409 /// END OF FILE ///
410 ////////////////////////////////////////////////////////////////////////
411 
412 ABC_NAMESPACE_IMPL_END
413 
Fpga_NodeVecAlloc
Fpga_NodeVec_t * Fpga_NodeVecAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: fpgaVec.c:45
Fpga_NodeVecPush
void Fpga_NodeVecPush(Fpga_NodeVec_t *p, Fpga_Node_t *Entry)
Definition: fpgaVec.c:169
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Fpga_NodeVecCompareLevels
static ABC_NAMESPACE_IMPL_START int Fpga_NodeVecCompareLevels(Fpga_Node_t **pp1, Fpga_Node_t **pp2)
DECLARATIONS ///.
Definition: fpgaVec.c:263
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
Fpga_NodeVecCompareArrivals
int Fpga_NodeVecCompareArrivals(Fpga_Node_t **ppS1, Fpga_Node_t **ppS2)
Definition: fpgaVec.c:306
Fpga_NodeVecReadSize
int Fpga_NodeVecReadSize(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:101
Fpga_NodeVecReadEntry
Fpga_Node_t * Fpga_NodeVecReadEntry(Fpga_NodeVec_t *p, int i)
Definition: fpgaVec.c:246
Fpga_NodeVecWriteEntry
void Fpga_NodeVecWriteEntry(Fpga_NodeVec_t *p, int i, Fpga_Node_t *Entry)
Definition: fpgaVec.c:229
Fpga_NodeVecShrink
void Fpga_NodeVecShrink(Fpga_NodeVec_t *p, int nSizeNew)
Definition: fpgaVec.c:136
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Fpga_NodeVecUnion
void Fpga_NodeVecUnion(Fpga_NodeVec_t *p, Fpga_NodeVec_t *p1, Fpga_NodeVec_t *p2)
Definition: fpgaVec.c:345
Fpga_NodeVecGrow
void Fpga_NodeVecGrow(Fpga_NodeVec_t *p, int nCapMin)
Definition: fpgaVec.c:117
Fpga_CutStruct_t_::tArrival
float tArrival
Definition: fpgaInt.h:244
Fpga_NodeVecStruct_t_
Definition: fpgaInt.h:250
Fpga_NodeVecStruct_t_::nCap
int nCap
Definition: fpgaInt.h:254
Fpga_SortNodesByArrivalTimes
void Fpga_SortNodesByArrivalTimes(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:326
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
if
if(last==0)
Definition: sparse_int.h:34
Fpga_NodeVecFree
void Fpga_NodeVecFree(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:68
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Fpga_Regular
#define Fpga_Regular(p)
Definition: fpga.h:58
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Fpga_NodeVecSortByLevel
void Fpga_NodeVecSortByLevel(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:289
Fpga_NodeVecClear
void Fpga_NodeVecClear(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:153
Fpga_NodeVecPushOrder
void Fpga_NodeVecPushOrder(Fpga_NodeVec_t *vNodes, Fpga_Node_t *pNode, int fIncreasing)
Definition: fpgaVec.c:366
Fpga_NodeStruct_t_
Definition: fpgaInt.h:180
Fpga_NodeVecReverse
void Fpga_NodeVecReverse(Fpga_NodeVec_t *vNodes)
Definition: fpgaVec.c:395
assert
#define assert(ex)
Definition: util_old.h:213
Fpga_NodeVecReadArray
Fpga_Node_t ** Fpga_NodeVecReadArray(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:85
Fpga_NodeVecStruct_t_::pArray
Fpga_Node_t ** pArray
Definition: fpgaInt.h:252
Fpga_NodeStruct_t_::pCutBest
Fpga_Cut_t * pCutBest
Definition: fpgaInt.h:222
Fpga_NodeVecPushUnique
int Fpga_NodeVecPushUnique(Fpga_NodeVec_t *p, Fpga_Node_t *Entry)
Definition: fpgaVec.c:192
Fpga_NodeVecPop
Fpga_Node_t * Fpga_NodeVecPop(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:213
Fpga_NodeVecStruct_t_::nSize
int nSize
Definition: fpgaInt.h:253