abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Data Structures | Typedefs | Functions
vecQue.h File Reference
#include <stdio.h>

Go to the source code of this file.

Data Structures

struct  Vec_Que_t_
 

Typedefs

typedef
typedefABC_NAMESPACE_HEADER_START
struct Vec_Que_t_ 		Vec_Que_t
 INCLUDES ///. More...
 

Functions

static float Vec_QuePrio (Vec_Que_t *p, int v)
 
static Vec_Que_t * Vec_QueAlloc (int nCap)
 MACRO DEFINITIONS ///. More...
 
static void Vec_QueFree (Vec_Que_t *p)
 
static void Vec_QueFreeP (Vec_Que_t **p)
 
static void Vec_QueSetPriority (Vec_Que_t *p, float **pCosts)
 
static void Vec_QueGrow (Vec_Que_t *p, int nCapMin)
 
static void Vec_QueClear (Vec_Que_t *p)
 
static int Vec_QueSize (Vec_Que_t *p)
 
static int Vec_QueTop (Vec_Que_t *p)
 
static float Vec_QueTopPriority (Vec_Que_t *p)
 
static int Vec_QueMoveUp (Vec_Que_t *p, int v)
 
static void Vec_QueMoveDown (Vec_Que_t *p, int v)
 
static void Vec_QueUpdate (Vec_Que_t *p, int v)
 
static int Vec_QueIsMember (Vec_Que_t *p, int v)
 
static void Vec_QuePush (Vec_Que_t *p, int v)
 
static int Vec_QuePop (Vec_Que_t *p)
 
static void Vec_QuePrint (Vec_Que_t *p)
 
static void Vec_QueCheck (Vec_Que_t *p)
 
static void Vec_QueTest (Vec_Flt_t *vCosts)
 

Typedef Documentation

typedef typedefABC_NAMESPACE_HEADER_START struct Vec_Que_t_ Vec_Que_t

INCLUDES ///.

CFile****************************************************************

FileName [vecQue.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Resizable arrays.]

Synopsis [Priority queue.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:
vecQue.h,v 1.00 2005/06/20 00:00:00 alanmi Exp

]PARAMETERS ///BASIC TYPES ///

Definition at line 40 of file vecQue.h.

Function Documentation

static Vec_Que_t* Vec_QueAlloc ( int  nCap)
inlinestatic

MACRO DEFINITIONS ///.

FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 71 of file vecQue.h.

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 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Que_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Que_t_ Vec_Que_t
INCLUDES ///.
Definition: vecQue.h:40
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
ABC_FALLOC
#define ABC_FALLOC(type, num)
Definition: abc_global.h:231
static void Vec_QueCheck ( Vec_Que_t *  p)
inlinestatic

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 289 of file vecQue.h.

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 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_QuePrio
static float Vec_QuePrio(Vec_Que_t *p, int v)
Definition: vecQue.h:50
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_QueClear ( Vec_Que_t *  p)
inlinestatic

Definition at line 110 of file vecQue.h.

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 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_QueFree ( Vec_Que_t *  p)
inlinestatic

Definition at line 83 of file vecQue.h.

84 {
85  ABC_FREE( p->pOrder );
86  ABC_FREE( p->pHeap );
87  ABC_FREE( p );
88 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
static void Vec_QueFreeP ( Vec_Que_t **  p)
inlinestatic

Definition at line 89 of file vecQue.h.

90 {
91  if ( *p )
92  Vec_QueFree( *p );
93  *p = NULL;
94 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_QueFree
static void Vec_QueFree(Vec_Que_t *p)
Definition: vecQue.h:83
static void Vec_QueGrow ( Vec_Que_t *  p,
int  nCapMin 
)
inlinestatic

Definition at line 100 of file vecQue.h.

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 }
memset
char * memset()
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
static int Vec_QueIsMember ( Vec_Que_t *  p,
int  v 
)
inlinestatic

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 216 of file vecQue.h.

217 {
218  assert( v >= 0 );
219  return (int)( v < p->nCap && p->pOrder[v] >= 0 );
220 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_QueMoveDown ( Vec_Que_t *  p,
int  v 
)
inlinestatic

Definition at line 179 of file vecQue.h.

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 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_QuePrio
static float Vec_QuePrio(Vec_Que_t *p, int v)
Definition: vecQue.h:50
assert
#define assert(ex)
Definition: util_old.h:213
static int Vec_QueMoveUp ( Vec_Que_t *  p,
int  v 
)
inlinestatic

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 159 of file vecQue.h.

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 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_QuePrio
static float Vec_QuePrio(Vec_Que_t *p, int v)
Definition: vecQue.h:50
assert
#define assert(ex)
Definition: util_old.h:213
static int Vec_QuePop ( Vec_Que_t *  p)
inlinestatic

Definition at line 234 of file vecQue.h.

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 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_QueMoveDown
static void Vec_QueMoveDown(Vec_Que_t *p, int v)
Definition: vecQue.h:179
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_QuePrint ( Vec_Que_t *  p)
inlinestatic

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 261 of file vecQue.h.

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 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_QuePrio
static float Vec_QuePrio(Vec_Que_t *p, int v)
Definition: vecQue.h:50
static float Vec_QuePrio ( Vec_Que_t *  p,
int  v 
)
inlinestatic

Definition at line 50 of file vecQue.h.

50 { return *p->pCostsFlt ? (*p->pCostsFlt)[v] : v; }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static void Vec_QuePush ( Vec_Que_t *  p,
int  v 
)
inlinestatic

Definition at line 221 of file vecQue.h.

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_QueGrow
static void Vec_QueGrow(Vec_Que_t *p, int nCapMin)
Definition: vecQue.h:100
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
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_QueSetPriority ( Vec_Que_t *  p,
float **  pCosts 
)
inlinestatic

Definition at line 95 of file vecQue.h.

96 {
97  assert( p->pCostsFlt == NULL );
98  p->pCostsFlt = pCosts;
99 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
assert
#define assert(ex)
Definition: util_old.h:213
static int Vec_QueSize ( Vec_Que_t *  p)
inlinestatic

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 134 of file vecQue.h.

135 {
136  assert( p->nSize > 0 );
137  return p->nSize - 1;
138 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_QueTest ( Vec_Flt_t *  vCosts)
inlinestatic

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 328 of file vecQue.h.

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 }
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
Vec_Que_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Que_t_ Vec_Que_t
INCLUDES ///.
Definition: vecQue.h:40
Vec_QuePop
static int Vec_QuePop(Vec_Que_t *p)
Definition: vecQue.h:234
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
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
Vec_QueFree
static void Vec_QueFree(Vec_Que_t *p)
Definition: vecQue.h:83
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
static int Vec_QueTop ( Vec_Que_t *  p)
inlinestatic

Definition at line 139 of file vecQue.h.

140 {
141  return Vec_QueSize(p) > 0 ? p->pHeap[1] : -1;
142 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_QueSize
static int Vec_QueSize(Vec_Que_t *p)
Definition: vecQue.h:134
static float Vec_QueTopPriority ( Vec_Que_t *  p)
inlinestatic

Definition at line 143 of file vecQue.h.

144 {
145  return Vec_QueSize(p) > 0 ? Vec_QuePrio(p, p->pHeap[1]) : -ABC_INFINITY;
146 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_QueSize
static int Vec_QueSize(Vec_Que_t *p)
Definition: vecQue.h:134
Vec_QuePrio
static float Vec_QuePrio(Vec_Que_t *p, int v)
Definition: vecQue.h:50
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
static void Vec_QueUpdate ( Vec_Que_t *  p,
int  v 
)
inlinestatic

Definition at line 199 of file vecQue.h.

200 {
201  if ( !Vec_QueMoveUp( p, v ) )
202  Vec_QueMoveDown( p, v );
203 }
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_QueMoveDown
static void Vec_QueMoveDown(Vec_Que_t *p, int v)
Definition: vecQue.h:179