Version abc71001

1 files changed, 445 insertions, 0 deletions

diff --git a/src/opt/fxu/fxuHeapD.c b/src/opt/fxu/fxuHeapD.c
new file mode 100644
index 00000000..c81ad818
--- /dev/null
+++ b/src/opt/fxu/fxuHeapD.c
@@ -0,0 +1,445 @@
+/**CFile****************************************************************
+
+  FileName    [fxuHeapD.c]
+
+  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]
+
+  Synopsis    [The priority queue for double cube divisors.]
+
+  Author      [MVSIS Group]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - February 1, 2003.]
+
+  Revision    [$Id: fxuHeapD.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "fxuInt.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+#define FXU_HEAP_DOUBLE_WEIGHT(pDiv)           ((pDiv)->Weight)
+#define FXU_HEAP_DOUBLE_CURRENT(p, pDiv)       ((p)->pTree[(pDiv)->HNum])
+#define FXU_HEAP_DOUBLE_PARENT_EXISTS(p, pDiv) ((pDiv)->HNum > 1)
+#define FXU_HEAP_DOUBLE_CHILD1_EXISTS(p, pDiv) (((pDiv)->HNum << 1) <= p->nItems)
+#define FXU_HEAP_DOUBLE_CHILD2_EXISTS(p, pDiv) ((((pDiv)->HNum << 1)+1) <= p->nItems)
+#define FXU_HEAP_DOUBLE_PARENT(p, pDiv)        ((p)->pTree[(pDiv)->HNum >> 1])
+#define FXU_HEAP_DOUBLE_CHILD1(p, pDiv)        ((p)->pTree[(pDiv)->HNum << 1])
+#define FXU_HEAP_DOUBLE_CHILD2(p, pDiv)        ((p)->pTree[((pDiv)->HNum << 1)+1])
+#define FXU_HEAP_DOUBLE_ASSERT(p, pDiv)        assert( (pDiv)->HNum >= 1 && (pDiv)->HNum <= p->nItemsAlloc )
+
+static void Fxu_HeapDoubleResize( Fxu_HeapDouble * p );                  
+static void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 );  
+static void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv );  
+static void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv );  
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Fxu_HeapDouble * Fxu_HeapDoubleStart()
+{
+    Fxu_HeapDouble * p;
+    p = ALLOC( Fxu_HeapDouble, 1 );
+    memset( p, 0, sizeof(Fxu_HeapDouble) );
+    p->nItems      = 0;
+    p->nItemsAlloc = 10000;
+    p->pTree       = ALLOC( Fxu_Double *, p->nItemsAlloc + 1 );
+    p->pTree[0]    = NULL;
+    return p;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleResize( Fxu_HeapDouble * p )
+{
+    p->nItemsAlloc *= 2;
+    p->pTree = REALLOC( Fxu_Double *, p->pTree, p->nItemsAlloc + 1 );
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleStop( Fxu_HeapDouble * p )
+{
+    free( p->pTree );
+    free( p );
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoublePrint( FILE * pFile, Fxu_HeapDouble * p )
+{
+    Fxu_Double * pDiv;
+    int Counter = 1;
+    int Degree  = 1;
+
+    Fxu_HeapDoubleCheck( p );
+    fprintf( pFile, "The contents of the heap:\n" );
+    fprintf( pFile, "Level %d:  ", Degree );
+    Fxu_HeapDoubleForEachItem( p, pDiv )
+    {
+        assert( Counter == p->pTree[Counter]->HNum );
+        fprintf( pFile, "%2d=%3d  ", Counter, FXU_HEAP_DOUBLE_WEIGHT(p->pTree[Counter]) );
+        if ( ++Counter == (1 << Degree) )
+        {
+            fprintf( pFile, "\n" );
+            Degree++;
+            fprintf( pFile, "Level %d:  ", Degree );
+        }
+    }
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "End of the heap printout.\n" );
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleCheck( Fxu_HeapDouble * p )
+{
+    Fxu_Double * pDiv;
+    Fxu_HeapDoubleForEachItem( p, pDiv )
+    {
+        assert( pDiv->HNum == p->i );
+        Fxu_HeapDoubleCheckOne( p, pDiv );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleCheckOne( Fxu_HeapDouble * p, Fxu_Double * pDiv )
+{
+    int Weight1, Weight2;
+    if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) )
+    {
+        Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv);
+        Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) );
+        assert( Weight1 >= Weight2 );
+    }
+    if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) )
+    {
+        Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv);
+        Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) );
+        assert( Weight1 >= Weight2 );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleInsert( Fxu_HeapDouble * p, Fxu_Double * pDiv )
+{
+    if ( p->nItems == p->nItemsAlloc )
+        Fxu_HeapDoubleResize( p );
+    // put the last entry to the last place and move up
+    p->pTree[++p->nItems] = pDiv;
+    pDiv->HNum = p->nItems;
+    // move the last entry up if necessary
+    Fxu_HeapDoubleMoveUp( p, pDiv );
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleUpdate( Fxu_HeapDouble * p, Fxu_Double * pDiv )
+{
+//printf( "Updating divisor %d.\n", pDiv->Num );
+
+    FXU_HEAP_DOUBLE_ASSERT(p,pDiv);
+    if ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,pDiv) && 
+         FXU_HEAP_DOUBLE_WEIGHT(pDiv) > FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_PARENT(p,pDiv) ) )
+        Fxu_HeapDoubleMoveUp( p, pDiv );
+    else if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) && 
+        FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) ) )
+        Fxu_HeapDoubleMoveDn( p, pDiv );
+    else if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) && 
+        FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) ) )
+        Fxu_HeapDoubleMoveDn( p, pDiv );
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleDelete( Fxu_HeapDouble * p, Fxu_Double * pDiv )
+{
+    FXU_HEAP_DOUBLE_ASSERT(p,pDiv);
+    // put the last entry to the deleted place
+    // decrement the number of entries
+    p->pTree[pDiv->HNum] = p->pTree[p->nItems--];
+    p->pTree[pDiv->HNum]->HNum = pDiv->HNum;
+    // move the top entry down if necessary
+    Fxu_HeapDoubleUpdate( p, p->pTree[pDiv->HNum] );
+    pDiv->HNum = 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Fxu_Double * Fxu_HeapDoubleReadMax( Fxu_HeapDouble * p )
+{
+    if ( p->nItems == 0 )
+        return NULL;
+    return p->pTree[1];     
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Fxu_Double * Fxu_HeapDoubleGetMax( Fxu_HeapDouble * p )
+{
+    Fxu_Double * pDiv;
+    if ( p->nItems == 0 )
+        return NULL;
+    // prepare the return value
+    pDiv = p->pTree[1];
+    pDiv->HNum = 0;
+    // put the last entry on top
+    // decrement the number of entries
+    p->pTree[1] = p->pTree[p->nItems--];
+    p->pTree[1]->HNum = 1;
+    // move the top entry down if necessary
+    Fxu_HeapDoubleMoveDn( p, p->pTree[1] );
+    return pDiv;     
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int  Fxu_HeapDoubleReadMaxWeight( Fxu_HeapDouble * p )
+{
+    if ( p->nItems == 0 )
+        return -1;
+    else
+        return FXU_HEAP_DOUBLE_WEIGHT(p->pTree[1]);
+}
+
+
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 )
+{
+    Fxu_Double * pDiv;
+    int Temp;
+    pDiv   = *pDiv1;
+    *pDiv1 = *pDiv2;
+    *pDiv2 = pDiv;
+    Temp          = (*pDiv1)->HNum;
+    (*pDiv1)->HNum = (*pDiv2)->HNum;
+    (*pDiv2)->HNum = Temp;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv )
+{
+    Fxu_Double ** ppDiv, ** ppPar;
+    ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv);
+    while ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,*ppDiv) )
+    {
+        ppPar = &FXU_HEAP_DOUBLE_PARENT(p,*ppDiv);
+        if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) > FXU_HEAP_DOUBLE_WEIGHT(*ppPar) )
+        {
+            Fxu_HeapDoubleSwap( ppDiv, ppPar );
+            ppDiv = ppPar;
+        }
+        else
+            break;
+    }
+}
+ 
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv )
+{
+    Fxu_Double ** ppChild1, ** ppChild2, ** ppDiv;
+    ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv);
+    while ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,*ppDiv) )
+    { // if Child1 does not exist, Child2 also does not exists
+
+        // get the children
+        ppChild1 = &FXU_HEAP_DOUBLE_CHILD1(p,*ppDiv);
+        if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,*ppDiv) )
+        {
+            ppChild2 = &FXU_HEAP_DOUBLE_CHILD2(p,*ppDiv);
+
+            // consider two cases
+            if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) &&
+                 FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) )
+            { // Div is larger than both, skip
+                break;
+            }
+            else
+            { // Div is smaller than one of them, then swap it with larger 
+                if ( FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) )
+                {
+                    Fxu_HeapDoubleSwap( ppDiv, ppChild1 );
+                    // update the pointer
+                    ppDiv = ppChild1;
+                }
+                else
+                {
+                    Fxu_HeapDoubleSwap( ppDiv, ppChild2 );
+                    // update the pointer
+                    ppDiv = ppChild2;
+                }
+            }
+        }
+        else // Child2 does not exist
+        {
+            // consider two cases
+            if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) )
+            { // Div is larger than Child1, skip
+                break;
+            }
+            else
+            { // Div is smaller than Child1, then swap them
+                Fxu_HeapDoubleSwap( ppDiv, ppChild1 );
+                // update the pointer
+                ppDiv = ppChild1;
+            }
+        }
+    }
+}
+
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+