1 /**CFile****************************************************************
2
3 FileName [vecQue.h]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Resizable arrays.]
8
9 Synopsis [Priority queue.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: vecQue.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #ifndef ABC__misc__vec__Queue_h
22 #define ABC__misc__vec__Queue_h
23
24 ////////////////////////////////////////////////////////////////////////
25 /// INCLUDES ///
26 ////////////////////////////////////////////////////////////////////////
27
28 #include <stdio.h>
29
30 ABC_NAMESPACE_HEADER_START
31
32 ////////////////////////////////////////////////////////////////////////
33 /// PARAMETERS ///
34 ////////////////////////////////////////////////////////////////////////
35
36 ////////////////////////////////////////////////////////////////////////
37 /// BASIC TYPES ///
38 ////////////////////////////////////////////////////////////////////////
39
40 typedef struct Vec_Que_t_ Vec_Que_t;
41 struct Vec_Que_t_
42 {
43 int nCap;
44 int nSize;
45 int * pHeap;
46 int * pOrder;
47 float ** pCostsFlt; // owned by the caller
48 };
49
Vec_QuePrio(Vec_Que_t * p,int v)50 static inline float Vec_QuePrio( Vec_Que_t * p, int v ) { return *p->pCostsFlt ? (*p->pCostsFlt)[v] : v; }
51
52 ////////////////////////////////////////////////////////////////////////
53 /// MACRO DEFINITIONS ///
54 ////////////////////////////////////////////////////////////////////////
55
56 ////////////////////////////////////////////////////////////////////////
57 /// FUNCTION DEFINITIONS ///
58 ////////////////////////////////////////////////////////////////////////
59
60 /**Function*************************************************************
61
62 Synopsis []
63
64 Description []
65
66 SideEffects []
67
68 SeeAlso []
69
70 ***********************************************************************/
Vec_QueAlloc(int nCap)71 static inline Vec_Que_t * Vec_QueAlloc( int nCap )
72 {
73 Vec_Que_t * p;
74 p = ABC_CALLOC( Vec_Que_t, 1 );
75 if ( nCap < 16 )
76 nCap = 16;
77 p->nSize = 1;
78 p->nCap = nCap + 1;
79 p->pHeap = ABC_FALLOC( int, p->nCap );
80 p->pOrder = ABC_FALLOC( int, p->nCap );
81 return p;
82 }
Vec_QueFree(Vec_Que_t * p)83 static inline void Vec_QueFree( Vec_Que_t * p )
84 {
85 ABC_FREE( p->pOrder );
86 ABC_FREE( p->pHeap );
87 ABC_FREE( p );
88 }
Vec_QueFreeP(Vec_Que_t ** p)89 static inline void Vec_QueFreeP( Vec_Que_t ** p )
90 {
91 if ( *p )
92 Vec_QueFree( *p );
93 *p = NULL;
94 }
Vec_QueSetPriority(Vec_Que_t * p,float ** pCosts)95 static inline void Vec_QueSetPriority( Vec_Que_t * p, float ** pCosts )
96 {
97 assert( p->pCostsFlt == NULL );
98 p->pCostsFlt = pCosts;
99 }
Vec_QueGrow(Vec_Que_t * p,int nCapMin)100 static inline void Vec_QueGrow( Vec_Que_t * p, int nCapMin )
101 {
102 if ( p->nCap >= nCapMin )
103 return;
104 p->pHeap = ABC_REALLOC( int, p->pHeap, nCapMin );
105 p->pOrder = ABC_REALLOC( int, p->pOrder, nCapMin );
106 memset( p->pHeap + p->nCap, 0xff, (size_t)(nCapMin - p->nCap) * sizeof(int) );
107 memset( p->pOrder + p->nCap, 0xff, (size_t)(nCapMin - p->nCap) * sizeof(int) );
108 p->nCap = nCapMin;
109 }
Vec_QueClear(Vec_Que_t * p)110 static inline void Vec_QueClear( Vec_Que_t * p )
111 {
112 int i;
113 assert( p->pHeap[0] == -1 );
114 for ( i = 1; i < p->nSize; i++ )
115 {
116 assert( p->pHeap[i] >= 0 && p->pOrder[p->pHeap[i]] == i );
117 p->pOrder[p->pHeap[i]] = -1;
118 p->pHeap[i] = -1;
119 }
120 p->nSize = 1;
121 }
122
123 /**Function*************************************************************
124
125 Synopsis []
126
127 Description []
128
129 SideEffects []
130
131 SeeAlso []
132
133 ***********************************************************************/
Vec_QueSize(Vec_Que_t * p)134 static inline int Vec_QueSize( Vec_Que_t * p )
135 {
136 assert( p->nSize > 0 );
137 return p->nSize - 1;
138 }
Vec_QueTop(Vec_Que_t * p)139 static inline int Vec_QueTop( Vec_Que_t * p )
140 {
141 return Vec_QueSize(p) > 0 ? p->pHeap[1] : -1;
142 }
Vec_QueTopPriority(Vec_Que_t * p)143 static inline float Vec_QueTopPriority( Vec_Que_t * p )
144 {
145 return Vec_QueSize(p) > 0 ? Vec_QuePrio(p, p->pHeap[1]) : -ABC_INFINITY;
146 }
147
148 /**Function*************************************************************
149
150 Synopsis []
151
152 Description []
153
154 SideEffects []
155
156 SeeAlso []
157
158 ***********************************************************************/
Vec_QueMoveUp(Vec_Que_t * p,int v)159 static inline int Vec_QueMoveUp( Vec_Que_t * p, int v )
160 {
161 float Cost = Vec_QuePrio(p, v);
162 int i = p->pOrder[v];
163 int parent = i >> 1;
164 int fMoved = 0;
165 assert( p->pOrder[v] != -1 );
166 assert( p->pHeap[i] == v );
167 while ( i > 1 && Cost > Vec_QuePrio(p, p->pHeap[parent]) )
168 {
169 p->pHeap[i] = p->pHeap[parent];
170 p->pOrder[p->pHeap[i]] = i;
171 i = parent;
172 parent = i >> 1;
173 fMoved = 1;
174 }
175 p->pHeap[i] = v;
176 p->pOrder[v] = i;
177 return fMoved;
178 }
Vec_QueMoveDown(Vec_Que_t * p,int v)179 static inline void Vec_QueMoveDown( Vec_Que_t * p, int v )
180 {
181 float Cost = Vec_QuePrio(p, v);
182 int i = p->pOrder[v];
183 int child = i << 1;
184 while ( child < p->nSize )
185 {
186 if ( child + 1 < p->nSize && Vec_QuePrio(p, p->pHeap[child]) < Vec_QuePrio(p, p->pHeap[child+1]) )
187 child++;
188 assert( child < p->nSize );
189 if ( Cost >= Vec_QuePrio(p, p->pHeap[child]))
190 break;
191 p->pHeap[i] = p->pHeap[child];
192 p->pOrder[p->pHeap[i]] = i;
193 i = child;
194 child = child << 1;
195 }
196 p->pHeap[i] = v;
197 p->pOrder[v] = i;
198 }
Vec_QueUpdate(Vec_Que_t * p,int v)199 static inline void Vec_QueUpdate( Vec_Que_t * p, int v )
200 {
201 if ( !Vec_QueMoveUp( p, v ) )
202 Vec_QueMoveDown( p, v );
203 }
204
205 /**Function*************************************************************
206
207 Synopsis []
208
209 Description []
210
211 SideEffects []
212
213 SeeAlso []
214
215 ***********************************************************************/
Vec_QueIsMember(Vec_Que_t * p,int v)216 static inline int Vec_QueIsMember( Vec_Que_t * p, int v )
217 {
218 assert( v >= 0 );
219 return (int)( v < p->nCap && p->pOrder[v] >= 0 );
220 }
Vec_QuePush(Vec_Que_t * p,int v)221 static inline void Vec_QuePush( Vec_Que_t * p, int v )
222 {
223 if ( p->nSize >= p->nCap )
224 Vec_QueGrow( p, Abc_MaxInt(p->nSize+1, 2*p->nCap) );
225 if ( v >= p->nCap )
226 Vec_QueGrow( p, Abc_MaxInt(v+1, 2*p->nCap) );
227 assert( p->nSize < p->nCap );
228 assert( p->pOrder[v] == -1 );
229 assert( p->pHeap[p->nSize] == -1 );
230 p->pOrder[v] = p->nSize;
231 p->pHeap[p->nSize++] = v;
232 Vec_QueMoveUp( p, v );
233 }
Vec_QuePop(Vec_Que_t * p)234 static inline int Vec_QuePop( Vec_Que_t * p )
235 {
236 int v, Res;
237 assert( p->nSize > 1 );
238 Res = p->pHeap[1]; p->pOrder[Res] = -1;
239 if ( --p->nSize == 1 )
240 {
241 p->pHeap[1] = -1;
242 return Res;
243 }
244 v = p->pHeap[p->nSize]; p->pHeap[p->nSize] = -1;
245 p->pHeap[1] = v; p->pOrder[v] = 1;
246 Vec_QueMoveDown( p, v );
247 return Res;
248 }
249
250 /**Function*************************************************************
251
252 Synopsis []
253
254 Description []
255
256 SideEffects []
257
258 SeeAlso []
259
260 ***********************************************************************/
Vec_QuePrint(Vec_Que_t * p)261 static inline void Vec_QuePrint( Vec_Que_t * p )
262 {
263 int i, k, m;
264 for ( i = k = 1; i < p->nSize; i += k, k *= 2 )
265 {
266 for ( m = 0; m < k; m++ )
267 if ( i+m < p->nSize )
268 printf( "%-5d", p->pHeap[i+m] );
269 printf( "\n" );
270 for ( m = 0; m < k; m++ )
271 if ( i+m < p->nSize )
272 printf( "%-5.0f", Vec_QuePrio(p, p->pHeap[i+m]) );
273 printf( "\n" );
274 printf( "\n" );
275 }
276 }
277
278 /**Function*************************************************************
279
280 Synopsis []
281
282 Description []
283
284 SideEffects []
285
286 SeeAlso []
287
288 ***********************************************************************/
Vec_QueCheck(Vec_Que_t * p)289 static inline void Vec_QueCheck( Vec_Que_t * p )
290 {
291 int i, child;
292 assert( p->nSize > 0 );
293 assert( p->nSize <= p->nCap );
294 // check mapping
295 for ( i = 0; i < p->nSize-1; i++ )
296 assert( p->pOrder[i] > 0 );
297 for ( ; i < p->nCap; i++ )
298 assert( p->pOrder[i] == -1 );
299 // check heap
300 assert( p->pHeap[0] == -1 );
301 for ( i = 0; i < p->nSize-1; i++ )
302 assert( p->pHeap[p->pOrder[i]] == i );
303 for ( i++; i < p->nCap; i++ )
304 assert( p->pHeap[i] == -1 );
305 // check heap property
306 for ( i = 1; i < p->nSize; i++ )
307 {
308 child = i << 1;
309 if ( child < p->nSize )
310 assert( Vec_QuePrio(p, p->pHeap[i]) >= Vec_QuePrio(p, p->pHeap[child]) );
311 child++;
312 if ( child < p->nSize )
313 assert( Vec_QuePrio(p, p->pHeap[i]) >= Vec_QuePrio(p, p->pHeap[child]) );
314 }
315 }
316
317 /**Function*************************************************************
318
319 Synopsis []
320
321 Description []
322
323 SideEffects []
324
325 SeeAlso []
326
327 ***********************************************************************/
Vec_QueTest(Vec_Flt_t * vCosts)328 static inline void Vec_QueTest( Vec_Flt_t * vCosts )
329 {
330 Vec_Int_t * vTop;
331 Vec_Que_t * p;
332 int i, Entry;
333
334 // start the queue
335 p = Vec_QueAlloc( Vec_FltSize(vCosts) );
336 Vec_QueSetPriority( p, Vec_FltArrayP(vCosts) );
337 for ( i = 0; i < Vec_FltSize(vCosts); i++ )
338 Vec_QuePush( p, i );
339 // Vec_QuePrint( p );
340 Vec_QueCheck( p );
341
342 // find the topmost 10%
343 vTop = Vec_IntAlloc( Vec_FltSize(vCosts) / 10 );
344 while ( Vec_IntSize(vTop) < Vec_FltSize(vCosts) / 10 )
345 Vec_IntPush( vTop, Vec_QuePop(p) );
346 // Vec_IntPrint( vTop );
347 // Vec_QueCheck( p ); // queque is not ready at this point!!!
348
349 // put them back
350 Vec_IntForEachEntry( vTop, Entry, i )
351 Vec_QuePush( p, Entry );
352 Vec_IntFree( vTop );
353 Vec_QueCheck( p );
354
355 Vec_QueFree( p );
356 }
357
358 /*
359 {
360 extern void Vec_QueTest( Vec_Flt_t * p );
361 Vec_QueTest( p->vTimesOut );
362 }
363 */
364
365 ////////////////////////////////////////////////////////////////////////
366 /// END OF FILE ///
367 ////////////////////////////////////////////////////////////////////////
368
369
370
371 ABC_NAMESPACE_HEADER_END
372
373 #endif
374
375