Version abc71001

1 files changed, 495 insertions, 0 deletions

diff --git a/src/sat/msat/msatVec.c b/src/sat/msat/msatVec.c
new file mode 100644
index 00000000..75f53047
--- /dev/null
+++ b/src/sat/msat/msatVec.c
@@ -0,0 +1,495 @@
+/**CFile****************************************************************
+
+  FileName    [msatVec.c]
+
+  PackageName [A C version of SAT solver MINISAT, originally developed 
+  in C++ by Niklas Een and Niklas Sorensson, Chalmers University of 
+  Technology, Sweden: http://www.cs.chalmers.se/~een/Satzoo.]
+
+  Synopsis    [Integer vector borrowed from Extra.]
+
+  Author      [Alan Mishchenko <alanmi@eecs.berkeley.edu>]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - January 1, 2004.]
+
+  Revision    [$Id: msatVec.c,v 1.0 2004/01/01 1:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "msatInt.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+static int Msat_IntVecSortCompare1( int * pp1, int * pp2 );
+static int Msat_IntVecSortCompare2( int * pp1, int * pp2 );
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Allocates a vector with the given capacity.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Msat_IntVec_t * Msat_IntVecAlloc( int nCap )
+{
+    Msat_IntVec_t * p;
+    p = ALLOC( Msat_IntVec_t, 1 );
+    if ( nCap > 0 && nCap < 16 )
+        nCap = 16;
+    p->nSize  = 0;
+    p->nCap   = nCap;
+    p->pArray = p->nCap? ALLOC( int, p->nCap ) : NULL;
+    return p;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Creates the vector from an integer array of the given size.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Msat_IntVec_t * Msat_IntVecAllocArray( int * pArray, int nSize )
+{
+    Msat_IntVec_t * p;
+    p = ALLOC( Msat_IntVec_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     []
+
+***********************************************************************/
+Msat_IntVec_t * Msat_IntVecAllocArrayCopy( int * pArray, int nSize )
+{
+    Msat_IntVec_t * p;
+    p = ALLOC( Msat_IntVec_t, 1 );
+    p->nSize  = nSize;
+    p->nCap   = nSize;
+    p->pArray = ALLOC( int, nSize );
+    memcpy( p->pArray, pArray, sizeof(int) * nSize );
+    return p;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Duplicates the integer array.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Msat_IntVec_t * Msat_IntVecDup( Msat_IntVec_t * pVec )
+{
+    Msat_IntVec_t * p;
+    p = ALLOC( Msat_IntVec_t, 1 );
+    p->nSize  = pVec->nSize;
+    p->nCap   = pVec->nCap;
+    p->pArray = p->nCap? ALLOC( int, p->nCap ) : NULL;
+    memcpy( p->pArray, pVec->pArray, sizeof(int) * pVec->nSize );
+    return p;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Transfers the array into another vector.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Msat_IntVec_t * Msat_IntVecDupArray( Msat_IntVec_t * pVec )
+{
+    Msat_IntVec_t * p;
+    p = ALLOC( Msat_IntVec_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     []
+
+***********************************************************************/
+void Msat_IntVecFree( Msat_IntVec_t * p )
+{
+    FREE( p->pArray );
+    FREE( p );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Fills the vector with given number of entries.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Msat_IntVecFill( Msat_IntVec_t * p, int nSize, int Entry )
+{
+    int i;
+    Msat_IntVecGrow( p, nSize );
+    p->nSize = nSize;
+    for ( i = 0; i < p->nSize; i++ )
+        p->pArray[i] = Entry;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int * Msat_IntVecReleaseArray( Msat_IntVec_t * p )
+{
+    int * pArray = p->pArray;
+    p->nCap = 0;
+    p->nSize = 0;
+    p->pArray = NULL;
+    return pArray;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int * Msat_IntVecReadArray( Msat_IntVec_t * p )
+{
+    return p->pArray;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Msat_IntVecReadSize( Msat_IntVec_t * p )
+{
+    return p->nSize;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Msat_IntVecReadEntry( Msat_IntVec_t * p, int i )
+{
+    assert( i >= 0 && i < p->nSize );
+    return p->pArray[i];
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Msat_IntVecWriteEntry( Msat_IntVec_t * p, int i, int Entry )
+{
+    assert( i >= 0 && i < p->nSize );
+    p->pArray[i] = Entry;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Msat_IntVecReadEntryLast( Msat_IntVec_t * p )
+{
+    return p->pArray[p->nSize-1];
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Resizes the vector to the given capacity.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Msat_IntVecGrow( Msat_IntVec_t * p, int nCapMin )
+{
+    if ( p->nCap >= nCapMin )
+        return;
+    p->pArray = REALLOC( int, p->pArray, nCapMin ); 
+    p->nCap   = nCapMin;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Msat_IntVecShrink( Msat_IntVec_t * p, int nSizeNew )
+{
+    assert( p->nSize >= nSizeNew );
+    p->nSize = nSizeNew;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Msat_IntVecClear( Msat_IntVec_t * p )
+{
+    p->nSize = 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Msat_IntVecPush( Msat_IntVec_t * p, int Entry )
+{
+    if ( p->nSize == p->nCap )
+    {
+        if ( p->nCap < 16 )
+            Msat_IntVecGrow( p, 16 );
+        else
+            Msat_IntVecGrow( p, 2 * p->nCap );
+    }
+    p->pArray[p->nSize++] = Entry;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Add the element while ensuring uniqueness.]
+
+  Description [Returns 1 if the element was found, and 0 if it was new. ]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Msat_IntVecPushUnique( Msat_IntVec_t * p, int Entry )
+{
+    int i;
+    for ( i = 0; i < p->nSize; i++ )
+        if ( p->pArray[i] == Entry )
+            return 1;
+    Msat_IntVecPush( p, Entry );
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Inserts the element while sorting in the increasing order.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Msat_IntVecPushUniqueOrder( Msat_IntVec_t * p, int Entry, int fIncrease )
+{
+    int Entry1, Entry2;
+    int i;
+    Msat_IntVecPushUnique( p, Entry );
+    // find the p of the node
+    for ( i = p->nSize-1; i > 0; i-- )
+    {
+        Entry1 = p->pArray[i  ];
+        Entry2 = p->pArray[i-1];
+        if ( fIncrease && Entry1 >= Entry2 || 
+            !fIncrease && Entry1 <= Entry2 )
+            break;
+        p->pArray[i  ] = Entry2;
+        p->pArray[i-1] = Entry1;
+    }
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Returns the last entry and removes it from the list.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Msat_IntVecPop( Msat_IntVec_t * p )
+{
+    assert( p->nSize > 0 );
+    return p->pArray[--p->nSize];
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Sorting the entries by their integer value.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Msat_IntVecSort( Msat_IntVec_t * p, int fReverse )
+{
+    if ( fReverse ) 
+        qsort( (void *)p->pArray, p->nSize, sizeof(int), 
+                (int (*)(const void *, const void *)) Msat_IntVecSortCompare2 );
+    else
+        qsort( (void *)p->pArray, p->nSize, sizeof(int), 
+                (int (*)(const void *, const void *)) Msat_IntVecSortCompare1 );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Comparison procedure for two clauses.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Msat_IntVecSortCompare1( int * pp1, int * 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 clauses.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Msat_IntVecSortCompare2( int * pp1, int * 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; //
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+