summaryrefslogtreecommitdiffstats
path: root/src/misc/vec/vecQue.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/misc/vec/vecQue.h')
-rw-r--r--src/misc/vec/vecQue.h360
1 files changed, 360 insertions, 0 deletions
diff --git a/src/misc/vec/vecQue.h b/src/misc/vec/vecQue.h
new file mode 100644
index 00000000..d31abb27
--- /dev/null
+++ b/src/misc/vec/vecQue.h
@@ -0,0 +1,360 @@
+/**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 $]
+
+***********************************************************************/
+
+#ifndef ABC__misc__vec__Queue_h
+#define ABC__misc__vec__Queue_h
+
+////////////////////////////////////////////////////////////////////////
+/// INCLUDES ///
+////////////////////////////////////////////////////////////////////////
+
+#include <stdio.h>
+
+ABC_NAMESPACE_HEADER_START
+
+////////////////////////////////////////////////////////////////////////
+/// PARAMETERS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// BASIC TYPES ///
+////////////////////////////////////////////////////////////////////////
+
+typedef struct Vec_Que_t_ Vec_Que_t;
+struct Vec_Que_t_
+{
+ int nCap;
+ int nSize;
+ int * pHeap;
+ int * pOrder;
+ float * pCostsFlt; // owned by the caller
+};
+
+static inline float Vec_QueCost( Vec_Que_t * p, int v ) { return p->pCostsFlt ? p->pCostsFlt[v] : v; }
+
+////////////////////////////////////////////////////////////////////////
+/// MACRO DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline Vec_Que_t * Vec_QueAlloc( int nCap )
+{
+ Vec_Que_t * p;
+ p = ABC_CALLOC( Vec_Que_t, 1 );
+ if ( nCap < 16 )
+ nCap = 16;
+ p->nSize = 1;
+ p->nCap = nCap + 1;
+ p->pHeap = ABC_FALLOC( int, p->nCap );
+ p->pOrder = ABC_FALLOC( int, p->nCap );
+ return p;
+}
+static inline void Vec_QueFree( Vec_Que_t * p )
+{
+ ABC_FREE( p->pOrder );
+ ABC_FREE( p->pHeap );
+ ABC_FREE( p );
+}
+static inline void Vec_QueFreeP( Vec_Que_t ** p )
+{
+ if ( *p )
+ Vec_QueFree( *p );
+ *p = NULL;
+}
+static inline void Vec_QueSetCosts( Vec_Que_t * p, float * pCosts )
+{
+ assert( p->pCostsFlt == NULL );
+ p->pCostsFlt = pCosts;
+}
+static inline void Vec_QueGrow( Vec_Que_t * p, int nCapMin )
+{
+ if ( p->nCap >= nCapMin )
+ return;
+ p->pHeap = ABC_REALLOC( int, p->pHeap, nCapMin );
+ p->pOrder = ABC_REALLOC( int, p->pOrder, nCapMin );
+ memset( p->pHeap + p->nCap, 0xff, (nCapMin - p->nCap) * sizeof(int) );
+ memset( p->pOrder + p->nCap, 0xff, (nCapMin - p->nCap) * sizeof(int) );
+ p->nCap = nCapMin;
+}
+static inline void Vec_QueClear( Vec_Que_t * p )
+{
+ int i;
+ assert( p->pHeap[0] == -1 );
+ for ( i = 1; i < p->nSize; i++ )
+ {
+ assert( p->pHeap[i] >= 0 && p->pOrder[p->pHeap[i]] == i );
+ p->pOrder[p->pHeap[i]] = -1;
+ p->pHeap[i] = -1;
+ }
+ p->nSize = 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int Vec_QueSize( Vec_Que_t * p )
+{
+ assert( p->nSize > 0 );
+ return p->nSize - 1;
+}
+static inline int Vec_QueTop( Vec_Que_t * p )
+{
+ return Vec_QueSize(p) > 0 ? p->pHeap[1] : -1;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int Vec_QueMoveUp( Vec_Que_t * p, int v )
+{
+ float Cost = Vec_QueCost(p, v);
+ int i = p->pOrder[v];
+ int parent = i >> 1;
+ int fMoved = 0;
+ assert( p->pOrder[v] != -1 );
+ assert( p->pHeap[i] == v );
+ while ( i > 1 && Cost > Vec_QueCost(p, p->pHeap[parent]) )
+ {
+ p->pHeap[i] = p->pHeap[parent];
+ p->pOrder[p->pHeap[i]] = i;
+ i = parent;
+ parent = i >> 1;
+ fMoved = 1;
+ }
+ p->pHeap[i] = v;
+ p->pOrder[v] = i;
+ return fMoved;
+}
+static inline void Vec_QueMoveDown( Vec_Que_t * p, int v )
+{
+ float Cost = Vec_QueCost(p, v);
+ int i = p->pOrder[v];
+ int child = i << 1;
+ while ( child < p->nSize )
+ {
+ if ( child + 1 < p->nSize && Vec_QueCost(p, p->pHeap[child]) < Vec_QueCost(p, p->pHeap[child+1]) )
+ child++;
+ assert( child < p->nSize );
+ if ( Cost >= Vec_QueCost(p, p->pHeap[child]))
+ break;
+ p->pHeap[i] = p->pHeap[child];
+ p->pOrder[p->pHeap[i]] = i;
+ i = child;
+ child = child << 1;
+ }
+ p->pHeap[i] = v;
+ p->pOrder[v] = i;
+}
+static inline void Vec_QueUpdate( Vec_Que_t * p, int v )
+{
+ if ( !Vec_QueMoveUp( p, v ) )
+ Vec_QueMoveDown( p, v );
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Vec_QuePush( Vec_Que_t * p, int v )
+{
+ if ( p->nSize == p->nCap )
+ Vec_QueGrow( p, 2 * p->nCap );
+ assert( p->nSize < p->nCap );
+ assert( p->pOrder[v] == -1 );
+ assert( p->pHeap[p->nSize] == -1 );
+ p->pOrder[v] = p->nSize;
+ p->pHeap[p->nSize++] = v;
+ Vec_QueMoveUp( p, v );
+}
+static inline int Vec_QuePop( Vec_Que_t * p )
+{
+ int v, Res;
+ assert( p->nSize > 1 );
+ Res = p->pHeap[1]; p->pOrder[Res] = -1;
+ if ( --p->nSize == 1 )
+ return Res;
+ v = p->pHeap[p->nSize]; p->pHeap[p->nSize] = -1;
+ p->pHeap[1] = v; p->pOrder[v] = 1;
+ Vec_QueMoveDown( p, v );
+ return Res;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Vec_QuePrint( Vec_Que_t * p )
+{
+ int i, k, m;
+ for ( i = k = 1; i < p->nSize; i += k, k *= 2 )
+ {
+ for ( m = 0; m < k; m++ )
+ if ( i+m < p->nSize )
+ printf( "%-5d", p->pHeap[i+m] );
+ printf( "\n" );
+ for ( m = 0; m < k; m++ )
+ if ( i+m < p->nSize )
+ printf( "%-5.0f", Vec_QueCost(p, p->pHeap[i+m]) );
+ printf( "\n" );
+ printf( "\n" );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Vec_QueCheck( Vec_Que_t * p )
+{
+ int i, child;
+ assert( p->nSize > 0 );
+ assert( p->nSize <= p->nCap );
+ // check mapping
+ for ( i = 0; i < p->nSize-1; i++ )
+ assert( p->pOrder[i] > 0 );
+ for ( ; i < p->nCap; i++ )
+ assert( p->pOrder[i] == -1 );
+ // check heap
+ assert( p->pHeap[0] == -1 );
+ for ( i = 0; i < p->nSize-1; i++ )
+ assert( p->pHeap[p->pOrder[i]] == i );
+ for ( i++; i < p->nCap; i++ )
+ assert( p->pHeap[i] == -1 );
+ // check heap property
+ for ( i = 1; i < p->nSize; i++ )
+ {
+ child = i << 1;
+ if ( child < p->nSize )
+ assert( Vec_QueCost(p, p->pHeap[i]) >= Vec_QueCost(p, p->pHeap[child]) );
+ child++;
+ if ( child < p->nSize )
+ assert( Vec_QueCost(p, p->pHeap[i]) >= Vec_QueCost(p, p->pHeap[child]) );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Vec_QueTest( Vec_Flt_t * vCosts )
+{
+ Vec_Int_t * vTop;
+ Vec_Que_t * p;
+ int i, Entry;
+
+ // start the queue
+ p = Vec_QueAlloc( Vec_FltSize(vCosts) );
+ Vec_QueSetCosts( p, Vec_FltArray(vCosts) );
+ for ( i = 0; i < Vec_FltSize(vCosts); i++ )
+ Vec_QuePush( p, i );
+// Vec_QuePrint( p );
+ Vec_QueCheck( p );
+
+ // find the topmost 10%
+ vTop = Vec_IntAlloc( Vec_FltSize(vCosts) / 10 );
+ while ( Vec_IntSize(vTop) < Vec_FltSize(vCosts) / 10 )
+ Vec_IntPush( vTop, Vec_QuePop(p) );
+// Vec_IntPrint( vTop );
+// Vec_QueCheck( p ); // queque is not ready at this point!!!
+
+ // put them back
+ Vec_IntForEachEntry( vTop, Entry, i )
+ Vec_QuePush( p, Entry );
+ Vec_IntFree( vTop );
+ Vec_QueCheck( p );
+
+ Vec_QueFree( p );
+}
+
+/*
+ {
+ extern void Vec_QueTest( Vec_Flt_t * p );
+ Vec_QueTest( p->vTimesOut );
+ }
+*/
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+
+ABC_NAMESPACE_HEADER_END
+
+#endif
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-10 14:43:38 +0000