abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
vecQue.h
Go to the documentation of this file.
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 
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 ***********************************************************************/
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 }
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 }
89 static inline void Vec_QueFreeP( Vec_Que_t ** p )
90 {
91  if ( *p )
92  Vec_QueFree( *p );
93  *p = NULL;
94 }
95 static inline void Vec_QueSetPriority( Vec_Que_t * p, float ** pCosts )
96 {
97  assert( p->pCostsFlt == NULL );
98  p->pCostsFlt = pCosts;
99 }
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, (nCapMin - p->nCap) * sizeof(int) );
107  memset( p->pOrder + p->nCap, 0xff, (nCapMin - p->nCap) * sizeof(int) );
108  p->nCap = nCapMin;
109 }
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 ***********************************************************************/
134 static inline int Vec_QueSize( Vec_Que_t * p )
135 {
136  assert( p->nSize > 0 );
137  return p->nSize - 1;
138 }
139 static inline int Vec_QueTop( Vec_Que_t * p )
140 {
141  return Vec_QueSize(p) > 0 ? p->pHeap[1] : -1;
142 }
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 ***********************************************************************/
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 }
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 }
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 ***********************************************************************/
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 }
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 }
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 
memset
char * memset()
Vec_QueGrow
static void Vec_QueGrow(Vec_Que_t *p, int nCapMin)
Definition: vecQue.h:100
Vec_QuePrint
static void Vec_QuePrint(Vec_Que_t *p)
Definition: vecQue.h:261
Vec_QueMoveUp
static int Vec_QueMoveUp(Vec_Que_t *p, int v)
Definition: vecQue.h:159
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_QueCheck
static void Vec_QueCheck(Vec_Que_t *p)
Definition: vecQue.h:289
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
Vec_QueTopPriority
static float Vec_QueTopPriority(Vec_Que_t *p)
Definition: vecQue.h:143
Vec_QueMoveDown
static void Vec_QueMoveDown(Vec_Que_t *p, int v)
Definition: vecQue.h:179
Vec_Que_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Que_t_ Vec_Que_t
INCLUDES ///.
Definition: vecQue.h:40
Vec_QueTop
static int Vec_QueTop(Vec_Que_t *p)
Definition: vecQue.h:139
Vec_QuePop
static int Vec_QuePop(Vec_Que_t *p)
Definition: vecQue.h:234
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Vec_Que_t_::pHeap
int * pHeap
Definition: vecQue.h:45
Vec_Que_t_
Definition: vecQue.h:41
Vec_QueClear
static void Vec_QueClear(Vec_Que_t *p)
Definition: vecQue.h:110
Vec_QueSize
static int Vec_QueSize(Vec_Que_t *p)
Definition: vecQue.h:134
Vec_QueFreeP
static void Vec_QueFreeP(Vec_Que_t **p)
Definition: vecQue.h:89
Vec_Que_t_::pOrder
int * pOrder
Definition: vecQue.h:46
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Vec_Que_t_::pCostsFlt
float ** pCostsFlt
Definition: vecQue.h:47
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Vec_Que_t_::nCap
int nCap
Definition: vecQue.h:43
ABC_NAMESPACE_HEADER_START
#define ABC_NAMESPACE_HEADER_START
NAMESPACES ///.
Definition: abc_global.h:105
ABC_NAMESPACE_HEADER_END
#define ABC_NAMESPACE_HEADER_END
Definition: abc_global.h:106
Vec_Que_t_::nSize
int nSize
Definition: vecQue.h:44
Vec_QuePrio
static float Vec_QuePrio(Vec_Que_t *p, int v)
Definition: vecQue.h:50
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Vec_FltArrayP
static float ** Vec_FltArrayP(Vec_Flt_t *p)
Definition: vecFlt.h:278
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Vec_QueUpdate
static void Vec_QueUpdate(Vec_Que_t *p, int v)
Definition: vecQue.h:199
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
Vec_Flt_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Flt_t_ Vec_Flt_t
INCLUDES ///.
Definition: vecFlt.h:42
Vec_QueIsMember
static int Vec_QueIsMember(Vec_Que_t *p, int v)
Definition: vecQue.h:216
Vec_QueFree
static void Vec_QueFree(Vec_Que_t *p)
Definition: vecQue.h:83
Vec_QueTest
static void Vec_QueTest(Vec_Flt_t *vCosts)
Definition: vecQue.h:328
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
assert
#define assert(ex)
Definition: util_old.h:213
Vec_IntFree
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
Vec_FltSize
static int Vec_FltSize(Vec_Flt_t *p)
Definition: vecFlt.h:294
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Vec_QueAlloc
static Vec_Que_t * Vec_QueAlloc(int nCap)
MACRO DEFINITIONS ///.
Definition: vecQue.h:71
Vec_QuePush
static void Vec_QuePush(Vec_Que_t *p, int v)
Definition: vecQue.h:221
Vec_QueSetPriority
static void Vec_QueSetPriority(Vec_Que_t *p, float **pCosts)
Definition: vecQue.h:95
ABC_FALLOC
#define ABC_FALLOC(type, num)
Definition: abc_global.h:231