From 6130e39b18b5f53902e4eab14f6d5cdde5219563 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 1 Nov 2010 01:35:04 -0700 Subject: initial commit of public abc --- src/misc/vec/vec.h | 18 +- src/misc/vec/vecAtt.h | 12 +- src/misc/vec/vecFlt.h | 40 +- src/misc/vec/vecInt.h | 176 +++++++- src/misc/vec/vecPtr.h | 144 ++++++- src/misc/vec/vecStr.h | 111 +++-- src/misc/vec/vecVec.h | 55 ++- src/misc/vec/vecWrd.h | 1071 +++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 1511 insertions(+), 116 deletions(-) create mode 100644 src/misc/vec/vecWrd.h (limited to 'src/misc/vec') diff --git a/src/misc/vec/vec.h b/src/misc/vec/vec.h index d6ed53b9..fadf6405 100644 --- a/src/misc/vec/vec.h +++ b/src/misc/vec/vec.h @@ -21,17 +21,20 @@ #ifndef __VEC_H__ #define __VEC_H__ + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// #include "abc_global.h" + #include "vecInt.h" #include "vecFlt.h" #include "vecStr.h" #include "vecPtr.h" #include "vecVec.h" #include "vecAtt.h" +#include "vecWrd.h" //////////////////////////////////////////////////////////////////////// /// MACRO DEFINITIONS /// @@ -41,9 +44,10 @@ /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// -#ifdef __cplusplus -extern "C" { -#endif + + +ABC_NAMESPACE_HEADER_START + //////////////////////////////////////////////////////////////////////// /// BASIC TYPES /// @@ -53,9 +57,11 @@ extern "C" { /// FUNCTION DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -#ifdef __cplusplus -} -#endif + + +ABC_NAMESPACE_HEADER_END + + #endif diff --git a/src/misc/vec/vecAtt.h b/src/misc/vec/vecAtt.h index 74379bf6..60b2d17a 100644 --- a/src/misc/vec/vecAtt.h +++ b/src/misc/vec/vecAtt.h @@ -21,12 +21,16 @@ #ifndef __VEC_ATT_H__ #define __VEC_ATT_H__ + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// #include +ABC_NAMESPACE_HEADER_START + + //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// @@ -65,9 +69,9 @@ struct Vec_Att_t_ void ** pArrayPtr; // the pointer attribute array // attribute specific info void * pMan; // the manager for this attribute - void (*pFuncFreeMan) (void *); // the procedure to ABC_FREE the manager + void (*pFuncFreeMan) (void *); // the procedure to free the manager void*(*pFuncStartObj)(void *); // the procedure to start one attribute - void (*pFuncFreeObj) (void *, void *); // the procedure to ABC_FREE one attribute + void (*pFuncFreeObj) (void *, void *); // the procedure to free one attribute }; //////////////////////////////////////////////////////////////////////// @@ -282,6 +286,10 @@ static inline void ** Vec_AttArray( Vec_Att_t * p ) return p->pArrayPtr; } + + +ABC_NAMESPACE_HEADER_END + #endif //////////////////////////////////////////////////////////////////////// diff --git a/src/misc/vec/vecFlt.h b/src/misc/vec/vecFlt.h index 8f0ea42d..8273b033 100644 --- a/src/misc/vec/vecFlt.h +++ b/src/misc/vec/vecFlt.h @@ -21,12 +21,16 @@ #ifndef __VEC_FLT_H__ #define __VEC_FLT_H__ + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// #include +ABC_NAMESPACE_HEADER_START + + //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// @@ -209,6 +213,25 @@ static inline void Vec_FltFree( Vec_Flt_t * p ) ABC_FREE( p ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_FltFreeP( Vec_Flt_t ** p ) +{ + if ( *p == NULL ) + return; + ABC_FREE( (*p)->pArray ); + ABC_FREE( (*p) ); +} + /**Function************************************************************* Synopsis [] @@ -378,16 +401,17 @@ static inline void Vec_FltFill( Vec_Flt_t * p, int nSize, float Entry ) SeeAlso [] ***********************************************************************/ -static inline void Vec_FltFillExtra( Vec_Flt_t * p, int nSize, float Entry ) +static inline void Vec_FltFillExtra( Vec_Flt_t * p, int nSize, float Fill ) { int i; - if ( p->nSize >= nSize ) + if ( nSize <= p->nSize ) return; - if ( nSize < 2 * p->nSize ) - nSize = 2 * p->nSize; - Vec_FltGrow( p, nSize ); + if ( nSize > 2 * p->nCap ) + Vec_FltGrow( p, nSize ); + else if ( nSize > p->nCap ) + Vec_FltGrow( p, 2 * p->nCap ); for ( i = p->nSize; i < nSize; i++ ) - p->pArray[i] = Entry; + p->pArray[i] = Fill; p->nSize = nSize; } @@ -628,5 +652,9 @@ static inline void Vec_FltSort( Vec_Flt_t * p, int fReverse ) /// END OF FILE /// //////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_HEADER_END + #endif diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h index 966f5ac9..6fcce5c6 100644 --- a/src/misc/vec/vecInt.h +++ b/src/misc/vec/vecInt.h @@ -21,12 +21,16 @@ #ifndef __VEC_INT_H__ #define __VEC_INT_H__ + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// #include +ABC_NAMESPACE_HEADER_START + + //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// @@ -105,6 +109,26 @@ static inline Vec_Int_t * Vec_IntStart( int nSize ) return p; } +/**Function************************************************************* + + Synopsis [Allocates a vector with the given size and cleans it.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Int_t * Vec_IntStartFull( int nSize ) +{ + Vec_Int_t * p; + p = Vec_IntAlloc( nSize ); + p->nSize = nSize; + memset( p->pArray, 0xff, sizeof(int) * nSize ); + return p; +} + /**Function************************************************************* Synopsis [Allocates a vector with the given size and cleans it.] @@ -233,6 +257,25 @@ static inline void Vec_IntFree( Vec_Int_t * p ) ABC_FREE( p ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_IntFreeP( Vec_Int_t ** p ) +{ + if ( *p == NULL ) + return; + ABC_FREE( (*p)->pArray ); + ABC_FREE( (*p) ); +} + /**Function************************************************************* Synopsis [] @@ -347,10 +390,10 @@ static inline void Vec_IntWriteEntry( Vec_Int_t * p, int i, int Entry ) SeeAlso [] ***********************************************************************/ -static inline void Vec_IntAddToEntry( Vec_Int_t * p, int i, int Addition ) +static inline int Vec_IntAddToEntry( Vec_Int_t * p, int i, int Addition ) { assert( i >= 0 && i < p->nSize ); - p->pArray[i] += Addition; + return p->pArray[i] += Addition; } /**Function************************************************************* @@ -424,11 +467,12 @@ static inline void Vec_IntFill( Vec_Int_t * p, int nSize, int Fill ) static inline void Vec_IntFillExtra( Vec_Int_t * p, int nSize, int Fill ) { int i; - if ( p->nSize >= nSize ) + if ( nSize <= p->nSize ) return; - if ( nSize < 2 * p->nSize ) - nSize = 2 * p->nSize; - Vec_IntGrow( p, nSize ); + if ( nSize > 2 * p->nCap ) + Vec_IntGrow( p, nSize ); + else if ( nSize > p->nCap ) + Vec_IntGrow( p, 2 * p->nCap ); for ( i = p->nSize; i < nSize; i++ ) p->pArray[i] = Fill; p->nSize = nSize; @@ -451,6 +495,23 @@ static inline int Vec_IntGetEntry( Vec_Int_t * p, int i ) return Vec_IntEntry( p, i ); } +/**Function************************************************************* + + Synopsis [Returns the entry even if the place not exist.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int * Vec_IntGetEntryP( Vec_Int_t * p, int i ) +{ + Vec_IntFillExtra( p, i + 1, 0 ); + return Vec_IntEntryP( p, i ); +} + /**Function************************************************************* Synopsis [Inserts the entry even if the place does not exist.] @@ -711,6 +772,27 @@ static inline int Vec_IntRemove( Vec_Int_t * p, int Entry ) return 1; } +/**Function************************************************************* + + Synopsis [Interts entry at the index iHere. Shifts other entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_IntInsert( Vec_Int_t * p, int iHere, int Entry ) +{ + int i; + assert( iHere >= 0 && iHere < p->nSize ); + Vec_IntPush( p, 0 ); + for ( i = p->nSize - 1; i > iHere; i-- ) + p->pArray[i] = p->pArray[i-1]; + p->pArray[i] = Entry; +} + /**Function************************************************************* Synopsis [Find entry.] @@ -790,16 +872,64 @@ static inline void Vec_IntReverseOrder( Vec_Int_t * p ) SeeAlso [] ***********************************************************************/ -static inline Vec_Int_t * Vec_IntInvert( Vec_Int_t * p ) +static inline Vec_Int_t * Vec_IntInvert( Vec_Int_t * p, int Fill ) { - Vec_Int_t * vRes; int Entry, i; - vRes = Vec_IntStart( Vec_IntFindMax(p) + 1 ); + Vec_Int_t * vRes = Vec_IntAlloc( 0 ); + Vec_IntFill( vRes, Vec_IntFindMax(p) + 1, Fill ); Vec_IntForEachEntry( p, Entry, i ) - Vec_IntWriteEntry( vRes, Entry, i ); + if ( Entry != Fill ) + Vec_IntWriteEntry( vRes, Entry, i ); return vRes; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_IntSum( Vec_Int_t * p ) +{ + int i, Counter = 0; + for ( i = 0; i < p->nSize; i++ ) + Counter += p->pArray[i]; + return Counter; +} + +/**Function************************************************************* + + Synopsis [Counts the number of common entries.] + + Description [Assumes that the entries are non-negative integers that + are not very large, so inversion of the array can be performed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_IntCountCommon( Vec_Int_t * p1, Vec_Int_t * p2 ) +{ + Vec_Int_t * vTemp; + int Entry, i, Counter = 0; + if ( Vec_IntSize(p1) < Vec_IntSize(p2) ) + vTemp = p1, p1 = p2, p2 = vTemp; + assert( Vec_IntSize(p1) >= Vec_IntSize(p2) ); + vTemp = Vec_IntInvert( p2, -1 ); + Vec_IntFillExtra( vTemp, Vec_IntFindMax(p1) + 1, -1 ); + Vec_IntForEachEntry( p1, Entry, i ) + if ( Vec_IntEntry(vTemp, Entry) >= 0 ) + Counter++; + Vec_IntFree( vTemp ); + return Counter; +} + /**Function************************************************************* Synopsis [Comparison procedure for two integers.] @@ -863,6 +993,28 @@ static inline void Vec_IntSort( Vec_Int_t * p, int fReverse ) (int (*)(const void *, const void *)) Vec_IntSortCompare1 ); } +/**Function************************************************************* + + Synopsis [Leaves only unique entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static void Vec_IntUniqify( Vec_Int_t * p ) +{ + int i, k; + if ( p->nSize < 2 ) + return; + Vec_IntSort( p, 0 ); + for ( i = k = 1; i < p->nSize; i++ ) + if ( p->pArray[i] != p->pArray[i-1] ) + p->pArray[k++] = p->pArray[i]; + p->nSize = k; +} /**Function************************************************************* @@ -970,6 +1122,10 @@ static inline Vec_Int_t * Vec_IntTwoMerge( Vec_Int_t * vArr1, Vec_Int_t * vArr2 return vArr; } + + +ABC_NAMESPACE_HEADER_END + #endif //////////////////////////////////////////////////////////////////////// diff --git a/src/misc/vec/vecPtr.h b/src/misc/vec/vecPtr.h index 7b153d90..9915f2d6 100644 --- a/src/misc/vec/vecPtr.h +++ b/src/misc/vec/vecPtr.h @@ -21,12 +21,16 @@ #ifndef __VEC_PTR_H__ #define __VEC_PTR_H__ + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// #include +ABC_NAMESPACE_HEADER_START + + //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// @@ -48,16 +52,16 @@ struct Vec_Ptr_t_ //////////////////////////////////////////////////////////////////////// // iterators through entries -#define Vec_PtrForEachEntry( vVec, pEntry, i ) \ - for ( i = 0; (i < Vec_PtrSize(vVec)) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i++ ) -#define Vec_PtrForEachEntryStart( vVec, pEntry, i, Start ) \ - for ( i = Start; (i < Vec_PtrSize(vVec)) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i++ ) -#define Vec_PtrForEachEntryStop( vVec, pEntry, i, Stop ) \ - for ( i = 0; (i < Stop) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i++ ) -#define Vec_PtrForEachEntryStartStop( vVec, pEntry, i, Start, Stop ) \ - for ( i = Start; (i < Stop) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i++ ) -#define Vec_PtrForEachEntryReverse( vVec, pEntry, i ) \ - for ( i = Vec_PtrSize(vVec) - 1; (i >= 0) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i-- ) +#define Vec_PtrForEachEntry( Type, vVec, pEntry, i ) \ + for ( i = 0; (i < Vec_PtrSize(vVec)) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i++ ) +#define Vec_PtrForEachEntryStart( Type, vVec, pEntry, i, Start ) \ + for ( i = Start; (i < Vec_PtrSize(vVec)) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i++ ) +#define Vec_PtrForEachEntryStop( Type, vVec, pEntry, i, Stop ) \ + for ( i = 0; (i < Stop) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i++ ) +#define Vec_PtrForEachEntryStartStop( Type, vVec, pEntry, i, Start, Stop ) \ + for ( i = Start; (i < Stop) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i++ ) +#define Vec_PtrForEachEntryReverse( Type, vVec, pEntry, i ) \ + for ( i = Vec_PtrSize(vVec) - 1; (i >= 0) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i-- ) //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// @@ -212,6 +216,25 @@ static inline void Vec_PtrFree( Vec_Ptr_t * p ) ABC_FREE( p ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_PtrFreeP( Vec_Ptr_t ** p ) +{ + if ( *p == NULL ) + return; + ABC_FREE( (*p)->pArray ); + ABC_FREE( (*p) ); +} + /**Function************************************************************* Synopsis [] @@ -382,17 +405,17 @@ static inline void Vec_PtrFill( Vec_Ptr_t * p, int nSize, void * Entry ) SeeAlso [] ***********************************************************************/ -static inline void Vec_PtrFillExtra( Vec_Ptr_t * p, int nSize, void * Entry ) +static inline void Vec_PtrFillExtra( Vec_Ptr_t * p, int nSize, void * Fill ) { int i; - if ( p->nSize >= nSize ) + if ( nSize <= p->nSize ) return; - assert( p->nSize < nSize ); - if ( nSize < 2 * p->nSize ) - nSize = 2 * p->nSize; - Vec_PtrGrow( p, nSize ); + if ( nSize > 2 * p->nCap ) + Vec_PtrGrow( p, nSize ); + else if ( nSize > p->nCap ) + Vec_PtrGrow( p, 2 * p->nCap ); for ( i = p->nSize; i < nSize; i++ ) - p->pArray[i] = Entry; + p->pArray[i] = Fill; p->nSize = nSize; } @@ -479,7 +502,7 @@ static inline void Vec_PtrFreeFree( Vec_Ptr_t * p ) void * pTemp; int i; if ( p == NULL ) return; - Vec_PtrForEachEntry( p, pTemp, i ) + Vec_PtrForEachEntry( void *, p, pTemp, i ) ABC_FREE( pTemp ); Vec_PtrFree( p ); } @@ -526,6 +549,33 @@ static inline void Vec_PtrPush( Vec_Ptr_t * p, void * Entry ) p->pArray[p->nSize++] = Entry; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_PtrPushFirst( Vec_Ptr_t * p, void * Entry ) +{ + int i; + if ( p->nSize == p->nCap ) + { + if ( p->nCap < 16 ) + Vec_PtrGrow( p, 16 ); + else + Vec_PtrGrow( p, 2 * p->nCap ); + } + p->nSize++; + for ( i = p->nSize - 1; i >= 1; i-- ) + p->pArray[i] = p->pArray[i-1]; + p->pArray[0] = Entry; +} + /**Function************************************************************* Synopsis [] @@ -615,6 +665,27 @@ static inline void Vec_PtrRemove( Vec_Ptr_t * p, void * Entry ) p->nSize--; } +/**Function************************************************************* + + Synopsis [Interts entry at the index iHere. Shifts other entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_PtrInsert( Vec_Ptr_t * p, int iHere, void * Entry ) +{ + int i; + assert( iHere >= 0 && iHere < p->nSize ); + Vec_PtrPush( p, 0 ); + for ( i = p->nSize - 1; i > iHere; i-- ) + p->pArray[i] = p->pArray[i-1]; + p->pArray[i] = Entry; +} + /**Function************************************************************* Synopsis [Moves the first nItems to the end.] @@ -657,6 +728,26 @@ static inline void Vec_PtrReverseOrder( Vec_Ptr_t * p ) } } +/**Function************************************************************* + + Synopsis [Comparison procedure for two integers.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int Vec_PtrSortComparePtr( void ** pp1, void ** pp2 ) +{ + if ( *pp1 < *pp2 ) + return -1; + if ( *pp1 > *pp2 ) + return 1; + return 0; +} + /**Function************************************************************* Synopsis [Sorting the entries by their integer value.] @@ -668,12 +759,17 @@ static inline void Vec_PtrReverseOrder( Vec_Ptr_t * p ) SeeAlso [] ***********************************************************************/ +static void Vec_PtrSort( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) ___unused; static void Vec_PtrSort( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) { if ( p->nSize < 2 ) return; - qsort( (void *)p->pArray, p->nSize, sizeof(void *), - (int (*)(const void *, const void *)) Vec_PtrSortCompare ); + if ( Vec_PtrSortCompare == NULL ) + qsort( (void *)p->pArray, p->nSize, sizeof(void *), + (int (*)(const void *, const void *)) Vec_PtrSortComparePtr ); + else + qsort( (void *)p->pArray, p->nSize, sizeof(void *), + (int (*)(const void *, const void *)) Vec_PtrSortCompare ); } /**Function************************************************************* @@ -687,13 +783,13 @@ static void Vec_PtrSort( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) SeeAlso [] ***********************************************************************/ +static void Vec_PtrUniqify( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) ___unused; static void Vec_PtrUniqify( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) { int i, k; if ( p->nSize < 2 ) return; - qsort( (void *)p->pArray, p->nSize, sizeof(void *), - (int (*)(const void *, const void *)) Vec_PtrSortCompare ); + Vec_PtrSort( p, Vec_PtrSortCompare ); for ( i = k = 1; i < p->nSize; i++ ) if ( p->pArray[i] != p->pArray[i-1] ) p->pArray[k++] = p->pArray[i]; @@ -880,6 +976,10 @@ static inline Vec_Ptr_t * Vec_PtrAllocTruthTables( int nVars ) return p; } + + +ABC_NAMESPACE_HEADER_END + #endif diff --git a/src/misc/vec/vecStr.h b/src/misc/vec/vecStr.h index bd10154c..c92760f2 100644 --- a/src/misc/vec/vecStr.h +++ b/src/misc/vec/vecStr.h @@ -21,12 +21,16 @@ #ifndef __VEC_STR_H__ #define __VEC_STR_H__ + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// #include +ABC_NAMESPACE_HEADER_START + + //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// @@ -203,6 +207,25 @@ static inline void Vec_StrFree( Vec_Str_t * p ) ABC_FREE( p ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_StrFreeP( Vec_Str_t ** p ) +{ + if ( *p == NULL ) + return; + ABC_FREE( (*p)->pArray ); + ABC_FREE( (*p) ); +} + /**Function************************************************************* Synopsis [] @@ -359,11 +382,12 @@ static inline void Vec_StrFill( Vec_Str_t * p, int nSize, char Fill ) static inline void Vec_StrFillExtra( Vec_Str_t * p, int nSize, char Fill ) { int i; - if ( p->nSize >= nSize ) + if ( nSize <= p->nSize ) return; - if ( nSize < 2 * p->nSize ) - nSize = 2 * p->nSize; - Vec_StrGrow( p, nSize ); + if ( nSize > 2 * p->nCap ) + Vec_StrGrow( p, nSize ); + else if ( nSize > p->nCap ) + Vec_StrGrow( p, 2 * p->nCap ); for ( i = p->nSize; i < nSize; i++ ) p->pArray[i] = Fill; p->nSize = nSize; @@ -459,26 +483,22 @@ static inline void Vec_StrPush( Vec_Str_t * p, char Entry ) p->pArray[p->nSize++] = Entry; } -/**Function******************************************************************** - - Synopsis [Finds the smallest integer larger of equal than the logarithm.] +/**Function************************************************************* - Description [Returns [Log10(Num)].] + Synopsis [Returns the last entry and removes it from the list.] + Description [] + SideEffects [] SeeAlso [] -******************************************************************************/ -static inline int Vec_StrBase10Log( unsigned Num ) +***********************************************************************/ +static inline char Vec_StrPop( Vec_Str_t * p ) { - int Res; - assert( Num >= 0 ); - if ( Num == 0 ) return 0; - if ( Num == 1 ) return 1; - for ( Res = 0, Num--; Num; Num /= 10, Res++ ); - return Res; -} /* end of Extra_Base2Log */ + assert( p->nSize > 0 ); + return p->pArray[--p->nSize]; +} /**Function************************************************************* @@ -493,26 +513,22 @@ static inline int Vec_StrBase10Log( unsigned Num ) ***********************************************************************/ static inline void Vec_StrPrintNum( Vec_Str_t * p, int Num ) { - int i, nDigits; - if ( Num < 0 ) - { - Vec_StrPush( p, '-' ); - Num = -Num; - } - if ( Num < 10 ) + int i; + char Digits[16]; + if ( Num == 0 ) { - Vec_StrPush( p, (char)('0' + Num) ); + Vec_StrPush( p, '0' ); return; } - nDigits = Vec_StrBase10Log( Num ); - Vec_StrGrow( p, p->nSize + nDigits ); - for ( i = nDigits - 1; i >= 0; i-- ) + if ( Num < 0 ) { - Vec_StrWriteEntry( p, p->nSize + i, (char)('0' + Num % 10) ); - Num /= 10; + Vec_StrPush( p, '-' ); + Num = -Num; } - assert( Num == 0 ); - p->nSize += nDigits; + for ( i = 0; Num; Num /= 10, i++ ) + Digits[i] = (char)('0' + Num % 10); + for ( i--; i >= 0; i-- ) + Vec_StrPush( p, Digits[i] ); } /**Function************************************************************* @@ -526,7 +542,7 @@ static inline void Vec_StrPrintNum( Vec_Str_t * p, int Num ) SeeAlso [] ***********************************************************************/ -static inline void Vec_StrPrintStr( Vec_Str_t * p, char * pStr ) +static inline void Vec_StrPrintStr( Vec_Str_t * p, const char * pStr ) { int i, Length = strlen(pStr); for ( i = 0; i < Length; i++ ) @@ -544,30 +560,9 @@ static inline void Vec_StrPrintStr( Vec_Str_t * p, char * pStr ) SeeAlso [] ***********************************************************************/ -static inline void Vec_StrAppend( Vec_Str_t * p, char * pString ) +static inline void Vec_StrAppend( Vec_Str_t * p, const char * pString ) { - int i, nLength = strlen(pString); - Vec_StrGrow( p, p->nSize + nLength ); - for ( i = 0; i < nLength; i++ ) - p->pArray[p->nSize + i] = pString[i]; - p->nSize += nLength; -} - -/**Function************************************************************* - - Synopsis [Returns the last entry and removes it from the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline char Vec_StrPop( Vec_Str_t * p ) -{ - assert( p->nSize > 0 ); - return p->pArray[--p->nSize]; + Vec_StrPrintStr( p, pString ); } /**Function************************************************************* @@ -655,6 +650,10 @@ static inline void Vec_StrSort( Vec_Str_t * p, int fReverse ) (int (*)(const void *, const void *)) Vec_StrSortCompare1 ); } + + +ABC_NAMESPACE_HEADER_END + #endif //////////////////////////////////////////////////////////////////////// diff --git a/src/misc/vec/vecVec.h b/src/misc/vec/vecVec.h index a77cdf76..8915329b 100644 --- a/src/misc/vec/vecVec.h +++ b/src/misc/vec/vecVec.h @@ -21,12 +21,16 @@ #ifndef __VEC_VEC_H__ #define __VEC_VEC_H__ + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// #include +ABC_NAMESPACE_HEADER_START + + //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// @@ -60,26 +64,26 @@ struct Vec_Vec_t_ for ( i = LevelStart; (i >= LevelStop) && (((vVec) = (Vec_Ptr_t*)Vec_VecEntry(vGlob, i)), 1); i-- ) // iteratores through entries -#define Vec_VecForEachEntry( vGlob, pEntry, i, k ) \ +#define Vec_VecForEachEntry( Type, vGlob, pEntry, i, k ) \ for ( i = 0; i < Vec_VecSize(vGlob); i++ ) \ - Vec_PtrForEachEntry( Vec_VecEntry(vGlob, i), pEntry, k ) -#define Vec_VecForEachEntryLevel( vGlob, pEntry, i, Level ) \ - Vec_PtrForEachEntry( Vec_VecEntry(vGlob, Level), pEntry, i ) -#define Vec_VecForEachEntryStart( vGlob, pEntry, i, k, LevelStart ) \ + Vec_PtrForEachEntry( Type, (Vec_Ptr_t *)Vec_VecEntry(vGlob, i), pEntry, k ) +#define Vec_VecForEachEntryLevel( Type, vGlob, pEntry, i, Level ) \ + Vec_PtrForEachEntry( Type, (Vec_Ptr_t *)Vec_VecEntry(vGlob, Level), pEntry, i ) +#define Vec_VecForEachEntryStart( Type, vGlob, pEntry, i, k, LevelStart ) \ for ( i = LevelStart; i < Vec_VecSize(vGlob); i++ ) \ - Vec_PtrForEachEntry( Vec_VecEntry(vGlob, i), pEntry, k ) -#define Vec_VecForEachEntryStartStop( vGlob, pEntry, i, k, LevelStart, LevelStop ) \ + Vec_PtrForEachEntry( Type, (Vec_Ptr_t *)Vec_VecEntry(vGlob, i), pEntry, k ) +#define Vec_VecForEachEntryStartStop( Type, vGlob, pEntry, i, k, LevelStart, LevelStop ) \ for ( i = LevelStart; i <= LevelStop; i++ ) \ - Vec_PtrForEachEntry( Vec_VecEntry(vGlob, i), pEntry, k ) -#define Vec_VecForEachEntryReverse( vGlob, pEntry, i, k ) \ + Vec_PtrForEachEntry( Type, (Vec_Ptr_t *)Vec_VecEntry(vGlob, i), pEntry, k ) +#define Vec_VecForEachEntryReverse( Type, vGlob, pEntry, i, k ) \ for ( i = 0; i < Vec_VecSize(vGlob); i++ ) \ - Vec_PtrForEachEntryReverse( Vec_VecEntry(vGlob, i), pEntry, k ) -#define Vec_VecForEachEntryReverseReverse( vGlob, pEntry, i, k ) \ + Vec_PtrForEachEntryReverse( Type, (Vec_Ptr_t *)Vec_VecEntry(vGlob, i), pEntry, k ) +#define Vec_VecForEachEntryReverseReverse( Type, vGlob, pEntry, i, k ) \ for ( i = Vec_VecSize(vGlob) - 1; i >= 0; i-- ) \ - Vec_PtrForEachEntryReverse( Vec_VecEntry(vGlob, i), pEntry, k ) -#define Vec_VecForEachEntryReverseStart( vGlob, pEntry, i, k, LevelStart ) \ + Vec_PtrForEachEntryReverse( Type, (Vec_Ptr_t *)Vec_VecEntry(vGlob, i), pEntry, k ) +#define Vec_VecForEachEntryReverseStart( Type, vGlob, pEntry, i, k, LevelStart ) \ for ( i = LevelStart; i >= 0; i-- ) \ - Vec_PtrForEachEntry( Vec_VecEntry(vGlob, i), pEntry, k ) + Vec_PtrForEachEntry( Type, (Vec_Ptr_t *)Vec_VecEntry(vGlob, i), pEntry, k ) //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// @@ -205,6 +209,25 @@ static inline void Vec_VecFree( Vec_Vec_t * p ) Vec_PtrFree( (Vec_Ptr_t *)p ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_VecFreeP( Vec_Vec_t ** p ) +{ + if ( *p == NULL ) + return; + Vec_VecFree( *p ); + *p = NULL; +} + /**Function************************************************************* Synopsis [Frees the vector.] @@ -390,6 +413,10 @@ static inline void Vec_VecSort( Vec_Vec_t * p, int fReverse ) (int (*)(const void *, const void *)) Vec_VecSortCompare1 ); } + + +ABC_NAMESPACE_HEADER_END + #endif //////////////////////////////////////////////////////////////////////// diff --git a/src/misc/vec/vecWrd.h b/src/misc/vec/vecWrd.h new file mode 100644 index 00000000..94449262 --- /dev/null +++ b/src/misc/vec/vecWrd.h @@ -0,0 +1,1071 @@ +/**CFile**************************************************************** + + FileName [vecWrd.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Resizable arrays.] + + Synopsis [Resizable arrays of long unsigned integers.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: vecWrd.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef __VEC_WRD_H__ +#define __VEC_WRD_H__ + + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include + +ABC_NAMESPACE_HEADER_START + + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Vec_Wrd_t_ Vec_Wrd_t; +struct Vec_Wrd_t_ +{ + int nCap; + int nSize; + word * pArray; +}; + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +#define Vec_WrdForEachEntry( vVec, Entry, i ) \ + for ( i = 0; (i < Vec_WrdSize(vVec)) && (((Entry) = Vec_WrdEntry(vVec, i)), 1); i++ ) +#define Vec_WrdForEachEntryStart( vVec, Entry, i, Start ) \ + for ( i = Start; (i < Vec_WrdSize(vVec)) && (((Entry) = Vec_WrdEntry(vVec, i)), 1); i++ ) +#define Vec_WrdForEachEntryStop( vVec, Entry, i, Stop ) \ + for ( i = 0; (i < Stop) && (((Entry) = Vec_WrdEntry(vVec, i)), 1); i++ ) +#define Vec_WrdForEachEntryStartStop( vVec, Entry, i, Start, Stop ) \ + for ( i = Start; (i < Stop) && (((Entry) = Vec_WrdEntry(vVec, i)), 1); i++ ) +#define Vec_WrdForEachEntryReverse( vVec, pEntry, i ) \ + for ( i = Vec_WrdSize(vVec) - 1; (i >= 0) && (((pEntry) = Vec_WrdEntry(vVec, i)), 1); i-- ) + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Allocates a vector with the given capacity.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdAlloc( int nCap ) +{ + Vec_Wrd_t * p; + p = ABC_ALLOC( Vec_Wrd_t, 1 ); + if ( nCap > 0 && nCap < 16 ) + nCap = 16; + p->nSize = 0; + p->nCap = nCap; + p->pArray = p->nCap? ABC_ALLOC( word, p->nCap ) : NULL; + return p; +} + +/**Function************************************************************* + + Synopsis [Allocates a vector with the given size and cleans it.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdStart( int nSize ) +{ + Vec_Wrd_t * p; + p = Vec_WrdAlloc( nSize ); + p->nSize = nSize; + memset( p->pArray, 0, sizeof(word) * nSize ); + return p; +} + +/**Function************************************************************* + + Synopsis [Allocates a vector with the given size and cleans it.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdStartFull( int nSize ) +{ + Vec_Wrd_t * p; + p = Vec_WrdAlloc( nSize ); + p->nSize = nSize; + memset( p->pArray, 0xff, sizeof(word) * nSize ); + return p; +} + +/**Function************************************************************* + + Synopsis [Allocates a vector with the given size and cleans it.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdStartNatural( int nSize ) +{ + Vec_Wrd_t * p; + int i; + p = Vec_WrdAlloc( nSize ); + p->nSize = nSize; + for ( i = 0; i < nSize; i++ ) + p->pArray[i] = i; + return p; +} + +/**Function************************************************************* + + Synopsis [Creates the vector from an integer array of the given size.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdAllocArray( word * pArray, int nSize ) +{ + Vec_Wrd_t * p; + p = ABC_ALLOC( Vec_Wrd_t, 1 ); + p->nSize = nSize; + p->nCap = nSize; + p->pArray = pArray; + return p; +} + +/**Function************************************************************* + + Synopsis [Creates the vector from an integer array of the given size.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdAllocArrayCopy( word * pArray, int nSize ) +{ + Vec_Wrd_t * p; + p = ABC_ALLOC( Vec_Wrd_t, 1 ); + p->nSize = nSize; + p->nCap = nSize; + p->pArray = ABC_ALLOC( word, nSize ); + memcpy( p->pArray, pArray, sizeof(word) * nSize ); + return p; +} + +/**Function************************************************************* + + Synopsis [Duplicates the integer array.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdDup( Vec_Wrd_t * pVec ) +{ + Vec_Wrd_t * p; + p = ABC_ALLOC( Vec_Wrd_t, 1 ); + p->nSize = pVec->nSize; + p->nCap = pVec->nSize; + p->pArray = p->nCap? ABC_ALLOC( word, p->nCap ) : NULL; + memcpy( p->pArray, pVec->pArray, sizeof(word) * pVec->nSize ); + return p; +} + +/**Function************************************************************* + + Synopsis [Transfers the array into another vector.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdDupArray( Vec_Wrd_t * pVec ) +{ + Vec_Wrd_t * p; + p = ABC_ALLOC( Vec_Wrd_t, 1 ); + p->nSize = pVec->nSize; + p->nCap = pVec->nCap; + p->pArray = pVec->pArray; + pVec->nSize = 0; + pVec->nCap = 0; + pVec->pArray = NULL; + return p; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdFree( Vec_Wrd_t * p ) +{ + ABC_FREE( p->pArray ); + ABC_FREE( p ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdFreeP( Vec_Wrd_t ** p ) +{ + if ( *p == NULL ) + return; + ABC_FREE( (*p)->pArray ); + ABC_FREE( (*p) ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word * Vec_WrdReleaseArray( Vec_Wrd_t * p ) +{ + word * pArray = p->pArray; + p->nCap = 0; + p->nSize = 0; + p->pArray = NULL; + return pArray; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word * Vec_WrdArray( Vec_Wrd_t * p ) +{ + return p->pArray; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_WrdSize( Vec_Wrd_t * p ) +{ + return p->nSize; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Vec_WrdEntry( Vec_Wrd_t * p, int i ) +{ + assert( i >= 0 && i < p->nSize ); + return p->pArray[i]; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word * Vec_WrdEntryP( Vec_Wrd_t * p, int i ) +{ + assert( i >= 0 && i < p->nSize ); + return p->pArray + i; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdWriteEntry( Vec_Wrd_t * p, int i, word Entry ) +{ + assert( i >= 0 && i < p->nSize ); + p->pArray[i] = Entry; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Vec_WrdAddToEntry( Vec_Wrd_t * p, int i, int Addition ) +{ + assert( i >= 0 && i < p->nSize ); + return p->pArray[i] += Addition; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Vec_WrdEntryLast( Vec_Wrd_t * p ) +{ + assert( p->nSize > 0 ); + return p->pArray[p->nSize-1]; +} + +/**Function************************************************************* + + Synopsis [Resizes the vector to the given capacity.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdGrow( Vec_Wrd_t * p, int nCapMin ) +{ + if ( p->nCap >= nCapMin ) + return; + p->pArray = ABC_REALLOC( word, p->pArray, nCapMin ); + assert( p->pArray ); + p->nCap = nCapMin; +} + +/**Function************************************************************* + + Synopsis [Fills the vector with given number of entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdFill( Vec_Wrd_t * p, int nSize, int Fill ) +{ + int i; + Vec_WrdGrow( p, nSize ); + for ( i = 0; i < nSize; i++ ) + p->pArray[i] = Fill; + p->nSize = nSize; +} + +/**Function************************************************************* + + Synopsis [Fills the vector with given number of entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdFillExtra( Vec_Wrd_t * p, int nSize, int Fill ) +{ + int i; + if ( nSize <= p->nSize ) + return; + if ( nSize > 2 * p->nCap ) + Vec_WrdGrow( p, nSize ); + else if ( nSize > p->nCap ) + Vec_WrdGrow( p, 2 * p->nCap ); + for ( i = p->nSize; i < nSize; i++ ) + p->pArray[i] = Fill; + p->nSize = nSize; +} + +/**Function************************************************************* + + Synopsis [Returns the entry even if the place not exist.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Vec_WrdGetEntry( Vec_Wrd_t * p, int i ) +{ + Vec_WrdFillExtra( p, i + 1, 0 ); + return Vec_WrdEntry( p, i ); +} + +/**Function************************************************************* + + Synopsis [Returns the entry even if the place not exist.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word * Vec_WrdGetEntryP( Vec_Wrd_t * p, int i ) +{ + Vec_WrdFillExtra( p, i + 1, 0 ); + return Vec_WrdEntryP( p, i ); +} + +/**Function************************************************************* + + Synopsis [Inserts the entry even if the place does not exist.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdSetEntry( Vec_Wrd_t * p, int i, word Entry ) +{ + Vec_WrdFillExtra( p, i + 1, 0 ); + Vec_WrdWriteEntry( p, i, Entry ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdShrink( Vec_Wrd_t * p, int nSizeNew ) +{ + assert( p->nSize >= nSizeNew ); + p->nSize = nSizeNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdClear( Vec_Wrd_t * p ) +{ + p->nSize = 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdPush( Vec_Wrd_t * p, word Entry ) +{ + if ( p->nSize == p->nCap ) + { + if ( p->nCap < 16 ) + Vec_WrdGrow( p, 16 ); + else + Vec_WrdGrow( p, 2 * p->nCap ); + } + p->pArray[p->nSize++] = Entry; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdPushFirst( Vec_Wrd_t * p, word Entry ) +{ + int i; + if ( p->nSize == p->nCap ) + { + if ( p->nCap < 16 ) + Vec_WrdGrow( p, 16 ); + else + Vec_WrdGrow( p, 2 * p->nCap ); + } + p->nSize++; + for ( i = p->nSize - 1; i >= 1; i-- ) + p->pArray[i] = p->pArray[i-1]; + p->pArray[0] = Entry; +} + +/**Function************************************************************* + + Synopsis [Inserts the entry while preserving the increasing order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdPushOrder( Vec_Wrd_t * p, word Entry ) +{ + int i; + if ( p->nSize == p->nCap ) + { + if ( p->nCap < 16 ) + Vec_WrdGrow( p, 16 ); + else + Vec_WrdGrow( p, 2 * p->nCap ); + } + p->nSize++; + for ( i = p->nSize-2; i >= 0; i-- ) + if ( p->pArray[i] > Entry ) + p->pArray[i+1] = p->pArray[i]; + else + break; + p->pArray[i+1] = Entry; +} + +/**Function************************************************************* + + Synopsis [Inserts the entry while preserving the increasing order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_WrdPushUniqueOrder( Vec_Wrd_t * p, word Entry ) +{ + int i; + for ( i = 0; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + return 1; + Vec_WrdPushOrder( p, Entry ); + return 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_WrdPushUnique( Vec_Wrd_t * p, word Entry ) +{ + int i; + for ( i = 0; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + return 1; + Vec_WrdPush( p, Entry ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Returns the pointer to the next nWords entries in the vector.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word * Vec_WrdFetch( Vec_Wrd_t * p, int nWords ) +{ + if ( nWords == 0 ) + return NULL; + assert( nWords > 0 ); + p->nSize += nWords; + if ( p->nSize > p->nCap ) + { +// Vec_WrdGrow( p, 2 * p->nSize ); + return NULL; + } + return p->pArray + p->nSize - nWords; +} + +/**Function************************************************************* + + Synopsis [Returns the last entry and removes it from the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Vec_WrdPop( Vec_Wrd_t * p ) +{ + assert( p->nSize > 0 ); + return p->pArray[--p->nSize]; +} + +/**Function************************************************************* + + Synopsis [Find entry.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_WrdFind( Vec_Wrd_t * p, word Entry ) +{ + int i; + for ( i = 0; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + return i; + return -1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_WrdRemove( Vec_Wrd_t * p, word Entry ) +{ + int i; + for ( i = 0; 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************************************************************* + + Synopsis [Interts entry at the index iHere. Shifts other entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdInsert( Vec_Wrd_t * p, int iHere, word Entry ) +{ + int i; + assert( iHere >= 0 && iHere < p->nSize ); + Vec_WrdPush( p, 0 ); + for ( i = p->nSize - 1; i > iHere; i-- ) + p->pArray[i] = p->pArray[i-1]; + p->pArray[i] = Entry; +} + +/**Function************************************************************* + + Synopsis [Find entry.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Vec_WrdFindMax( Vec_Wrd_t * p ) +{ + word Best; + int i; + if ( p->nSize == 0 ) + return 0; + Best = p->pArray[0]; + for ( i = 1; i < p->nSize; i++ ) + if ( Best < p->pArray[i] ) + Best = p->pArray[i]; + return Best; +} + +/**Function************************************************************* + + Synopsis [Find entry.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Vec_WrdFindMin( Vec_Wrd_t * p ) +{ + word Best; + int i; + if ( p->nSize == 0 ) + return 0; + Best = p->pArray[0]; + for ( i = 1; i < p->nSize; i++ ) + if ( Best > p->pArray[i] ) + Best = p->pArray[i]; + return Best; +} + +/**Function************************************************************* + + Synopsis [Reverses the order of entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdReverseOrder( Vec_Wrd_t * p ) +{ + word Temp; + int i; + for ( i = 0; i < p->nSize/2; i++ ) + { + Temp = p->pArray[i]; + p->pArray[i] = p->pArray[p->nSize-1-i]; + p->pArray[p->nSize-1-i] = Temp; + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Wrd_t * Vec_WrdInvert( Vec_Wrd_t * p, word Fill ) +{ + int i; + word Entry; + Vec_Wrd_t * vRes = Vec_WrdAlloc( 0 ); + Vec_WrdFill( vRes, Vec_WrdFindMax(p) + 1, Fill ); + Vec_WrdForEachEntry( p, Entry, i ) + if ( Entry != Fill ) + Vec_WrdWriteEntry( vRes, Entry, i ); + return vRes; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Vec_WrdSum( Vec_Wrd_t * p ) +{ + word Counter = 0; + int i; + for ( i = 0; i < p->nSize; i++ ) + Counter += p->pArray[i]; + return Counter; +} + +/**Function************************************************************* + + Synopsis [Counts the number of common entries.] + + Description [Assumes that the entries are non-negative integers that + are not very large, so inversion of the array can be performed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_WrdCountCommon( Vec_Wrd_t * p1, Vec_Wrd_t * p2 ) +{ + Vec_Wrd_t * vTemp; + word Entry; + int i, Counter = 0; + if ( Vec_WrdSize(p1) < Vec_WrdSize(p2) ) + vTemp = p1, p1 = p2, p2 = vTemp; + assert( Vec_WrdSize(p1) >= Vec_WrdSize(p2) ); + vTemp = Vec_WrdInvert( p2, -1 ); + Vec_WrdFillExtra( vTemp, Vec_WrdFindMax(p1) + 1, -1 ); + Vec_WrdForEachEntry( p1, Entry, i ) + if ( Vec_WrdEntry(vTemp, Entry) >= 0 ) + Counter++; + Vec_WrdFree( vTemp ); + return Counter; +} + +/**Function************************************************************* + + Synopsis [Comparison procedure for two integers.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int Vec_WrdSortCompare1( word * pp1, word * pp2 ) +{ + // for some reason commenting out lines (as shown) led to crashing of the release version + if ( *pp1 < *pp2 ) + return -1; + if ( *pp1 > *pp2 ) // + return 1; + return 0; // +} + +/**Function************************************************************* + + Synopsis [Comparison procedure for two integers.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int Vec_WrdSortCompare2( word * pp1, word * pp2 ) +{ + // for some reason commenting out lines (as shown) led to crashing of the release version + if ( *pp1 > *pp2 ) + return -1; + if ( *pp1 < *pp2 ) // + return 1; + return 0; // +} + +/**Function************************************************************* + + Synopsis [Sorting the entries by their integer value.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdSort( Vec_Wrd_t * p, int fReverse ) +{ + if ( fReverse ) + qsort( (void *)p->pArray, p->nSize, sizeof(word), + (int (*)(const void *, const void *)) Vec_WrdSortCompare2 ); + else + qsort( (void *)p->pArray, p->nSize, sizeof(word), + (int (*)(const void *, const void *)) Vec_WrdSortCompare1 ); +} + +/**Function************************************************************* + + Synopsis [Leaves only unique entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static void Vec_WrdUniqify( Vec_Wrd_t * p ) +{ + int i, k; + if ( p->nSize < 2 ) + return; + Vec_WrdSort( p, 0 ); + for ( i = k = 1; i < p->nSize; i++ ) + if ( p->pArray[i] != p->pArray[i-1] ) + p->pArray[k++] = p->pArray[i]; + p->nSize = k; +} + +/**Function************************************************************* + + Synopsis [Comparison procedure for two integers.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int Vec_WrdSortCompareUnsigned( word * pp1, word * pp2 ) +{ + if ( *pp1 < *pp2 ) + return -1; + if ( *pp1 > *pp2 ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Sorting the entries by their integer value.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_WrdSortUnsigned( Vec_Wrd_t * p ) +{ + qsort( (void *)p->pArray, p->nSize, sizeof(word), + (int (*)(const void *, const void *)) Vec_WrdSortCompareUnsigned ); +} + + + +ABC_NAMESPACE_HEADER_END + +#endif + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + -- cgit v1.2.3