From a762c695d7c0d953d644c0c77a2948d378d0d624 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 5 May 2013 01:54:11 -0700 Subject: New fast extract. --- src/misc/vec/vecInt.h | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++- src/misc/vec/vecQue.h | 11 +++--- src/misc/vec/vecWec.h | 95 ++++++++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 198 insertions(+), 7 deletions(-) (limited to 'src/misc/vec') diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h index 03427a0b..2fe15792 100644 --- a/src/misc/vec/vecInt.h +++ b/src/misc/vec/vecInt.h @@ -885,6 +885,20 @@ static inline int Vec_IntRemove( Vec_Int_t * p, int Entry ) p->nSize--; return 1; } +static inline int Vec_IntRemove1( Vec_Int_t * p, int Entry ) +{ + int i; + for ( i = 1; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + break; + if ( i >= p->nSize ) + return 0; + assert( i < p->nSize ); + for ( i++; i < p->nSize; i++ ) + p->pArray[i-1] = p->pArray[i]; + p->nSize--; + return 1; +} /**Function************************************************************* @@ -1298,6 +1312,18 @@ static inline int Vec_IntTwoCountCommon( Vec_Int_t * vArr1, Vec_Int_t * vArr2 ) } return Counter; } + +/**Function************************************************************* + + Synopsis [Collects common entries.] + + Description [Assumes that the vectors are sorted in the increasing order.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ static inline int Vec_IntTwoFindCommon( Vec_Int_t * vArr1, Vec_Int_t * vArr2, Vec_Int_t * vArr ) { int * pBeg1 = vArr1->pArray; @@ -1317,6 +1343,77 @@ static inline int Vec_IntTwoFindCommon( Vec_Int_t * vArr1, Vec_Int_t * vArr2, Ve return Vec_IntSize(vArr); } +/**Function************************************************************* + + Synopsis [Collects and removes common entries] + + Description [Assumes that the vectors are sorted in the increasing order.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_IntTwoRemoveCommon( Vec_Int_t * vArr1, Vec_Int_t * vArr2, Vec_Int_t * vArr ) +{ + int * pBeg1 = vArr1->pArray; + int * pBeg2 = vArr2->pArray; + int * pEnd1 = vArr1->pArray + vArr1->nSize; + int * pEnd2 = vArr2->pArray + vArr2->nSize; + int * pBeg1New = vArr1->pArray; + int * pBeg2New = vArr2->pArray; + Vec_IntClear( vArr ); + while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 ) + { + if ( *pBeg1 == *pBeg2 ) + Vec_IntPush( vArr, *pBeg1 ), pBeg1++, pBeg2++; + else if ( *pBeg1 < *pBeg2 ) + *pBeg1New++ = *pBeg1++; + else + *pBeg2New++ = *pBeg2++; + } + while ( pBeg1 < pEnd1 ) + *pBeg1New++ = *pBeg1++; + while ( pBeg2 < pEnd2 ) + *pBeg2New++ = *pBeg2++; + Vec_IntShrink( vArr1, pBeg1New - vArr1->pArray ); + Vec_IntShrink( vArr2, pBeg2New - vArr2->pArray ); + return Vec_IntSize(vArr); +} + +/**Function************************************************************* + + Synopsis [Removes entries of the second one from the first one.] + + Description [Assumes that the vectors are sorted in the increasing order.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_IntTwoRemove( Vec_Int_t * vArr1, Vec_Int_t * vArr2 ) +{ + int * pBeg1 = vArr1->pArray; + int * pBeg2 = vArr2->pArray; + int * pEnd1 = vArr1->pArray + vArr1->nSize; + int * pEnd2 = vArr2->pArray + vArr2->nSize; + int * pBeg1New = vArr1->pArray; + while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 ) + { + if ( *pBeg1 == *pBeg2 ) + pBeg1++, pBeg2++; + else if ( *pBeg1 < *pBeg2 ) + *pBeg1New++ = *pBeg1++; + else + pBeg2++; + } + while ( pBeg1 < pEnd1 ) + *pBeg1New++ = *pBeg1++; + Vec_IntShrink( vArr1, pBeg1New - vArr1->pArray ); + return Vec_IntSize(vArr1); +} + /**Function************************************************************* Synopsis [Returns the result of merging the two vectors.] @@ -1358,7 +1455,7 @@ static inline Vec_Int_t * Vec_IntTwoMerge( Vec_Int_t * vArr1, Vec_Int_t * vArr2 /**Function************************************************************* - Synopsis [Returns the result of merging the two vectors.] + Synopsis [Returns the result of splitting of the two vectors.] Description [Assumes that the vectors are sorted in the increasing order.] diff --git a/src/misc/vec/vecQue.h b/src/misc/vec/vecQue.h index 83be97a8..445c6fb3 100644 --- a/src/misc/vec/vecQue.h +++ b/src/misc/vec/vecQue.h @@ -94,7 +94,7 @@ static inline void Vec_QueFreeP( Vec_Que_t ** p ) } static inline void Vec_QueSetCosts( Vec_Que_t * p, float * pCosts ) { - assert( p->pCostsFlt == NULL ); +// assert( p->pCostsFlt == NULL ); p->pCostsFlt = pCosts; } static inline void Vec_QueGrow( Vec_Que_t * p, int nCapMin ) @@ -215,12 +215,15 @@ static inline void Vec_QueUpdate( Vec_Que_t * p, int v ) ***********************************************************************/ static inline int Vec_QueIsMember( Vec_Que_t * p, int v ) { - return (int)( p->pOrder[v] >= 0 ); + assert( v >= 0 ); + return (int)( v < p->nCap && p->pOrder[v] >= 0 ); } static inline void Vec_QuePush( Vec_Que_t * p, int v ) { - if ( p->nSize == p->nCap ) - Vec_QueGrow( p, 2 * p->nCap ); + if ( p->nSize >= p->nCap ) + Vec_QueGrow( p, Abc_MaxInt(p->nSize+1, 2*p->nCap) ); + if ( v >= p->nCap ) + Vec_QueGrow( p, Abc_MaxInt(v+1, 2*p->nCap) ); assert( p->nSize < p->nCap ); assert( p->pOrder[v] == -1 ); assert( p->pHeap[p->nSize] == -1 ); diff --git a/src/misc/vec/vecWec.h b/src/misc/vec/vecWec.h index 34d5d956..8a924f90 100644 --- a/src/misc/vec/vecWec.h +++ b/src/misc/vec/vecWec.h @@ -54,6 +54,8 @@ struct Vec_Wec_t_ // iterators through levels #define Vec_WecForEachLevel( vGlob, vVec, i ) \ for ( i = 0; (i < Vec_WecSize(vGlob)) && (((vVec) = Vec_WecEntry(vGlob, i)), 1); i++ ) +#define Vec_WecForEachLevelVec( vLevels, vGlob, vVec, i ) \ + for ( i = 0; (i < Vec_IntSize(vLevels)) && (((vVec) = Vec_WecEntry(vGlob, Vec_IntEntry(vLevels, i))), 1); i++ ) #define Vec_WecForEachLevelStart( vGlob, vVec, i, LevelStart ) \ for ( i = LevelStart; (i < Vec_WecSize(vGlob)) && (((vVec) = Vec_WecEntry(vGlob, i)), 1); i++ ) #define Vec_WecForEachLevelStop( vGlob, vVec, i, LevelStop ) \ @@ -147,6 +149,27 @@ static inline int Vec_WecEntryEntry( Vec_Wec_t * p, int i, int k ) return Vec_IntEntry( Vec_WecEntry(p, i), k ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Int_t * Vec_WecArray( Vec_Wec_t * p ) +{ + return p->pArray; +} +static inline int Vec_WecLevelId( Vec_Wec_t * p, Vec_Int_t * vLevel ) +{ + assert( p->pArray <= vLevel && vLevel < p->pArray + p->nSize ); + return vLevel - p->pArray; +} + /**Function************************************************************* Synopsis [] @@ -239,14 +262,21 @@ static inline void Vec_WecPush( Vec_Wec_t * p, int Level, int Entry ) { if ( p->nSize < Level + 1 ) { - Vec_WecGrow( p, Level + 1 ); + Vec_WecGrow( p, Abc_MaxInt(2*p->nCap, Level + 1) ); p->nSize = Level + 1; } Vec_IntPush( Vec_WecEntry(p, Level), Entry ); } static inline Vec_Int_t * Vec_WecPushLevel( Vec_Wec_t * p ) { - Vec_WecGrow( p, ++p->nSize ); + if ( p->nSize == p->nCap ) + { + if ( p->nCap < 16 ) + Vec_WecGrow( p, 16 ); + else + Vec_WecGrow( p, 2 * p->nCap ); + } + ++p->nSize; return Vec_WecEntryLast( p ); } @@ -557,6 +587,67 @@ static inline Vec_Ptr_t * Vec_WecConvertToVecPtr( Vec_Wec_t * p ) return vCopy; } + +/**Function************************************************************* + + Synopsis [Temporary vector marking.] + + Description [The vector should be static when the marking is used.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_WecIntHasMark( Vec_Int_t * vVec ) { return (vVec->nCap >> 30) & 1; } +static inline void Vec_WecIntSetMark( Vec_Int_t * vVec ) { vVec->nCap |= (1<<30); } +static inline void Vec_WecIntXorMark( Vec_Int_t * vVec ) { vVec->nCap ^= (1<<30); } +static inline void Vec_WecMarkLevels( Vec_Wec_t * vCubes, Vec_Int_t * vLevels ) +{ + Vec_Int_t * vCube; + int i; + Vec_WecForEachLevelVec( vLevels, vCubes, vCube, i ) + { + assert( !Vec_WecIntHasMark( vCube ) ); + Vec_WecIntXorMark( vCube ); + } +} +static inline void Vec_WecUnmarkLevels( Vec_Wec_t * vCubes, Vec_Int_t * vLevels ) +{ + Vec_Int_t * vCube; + int i; + Vec_WecForEachLevelVec( vLevels, vCubes, vCube, i ) + { + assert( Vec_WecIntHasMark( vCube ) ); + Vec_WecIntXorMark( vCube ); + } +} + +/**Function************************************************************* + + Synopsis [Removes 0-size vectors.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WecRemoveEmpty( Vec_Wec_t * vCubes ) +{ + Vec_Int_t * vCube; + int i, k = 0; + Vec_WecForEachLevel( vCubes, vCube, i ) + if ( Vec_IntSize(vCube) > 0 ) + vCubes->pArray[k++] = *vCube; + else + ABC_FREE( vCube->pArray ); + Vec_WecShrink( vCubes, k ); +// Vec_WecSortByFirstInt( vCubes, 0 ); +} + + ABC_NAMESPACE_HEADER_END #endif -- cgit v1.2.3