BigListElement.C

Go to the documentation of this file.

// BigListElement.C
//
// 2/11/98 WAH:  Broke away from Scheduler package; minor patching up.
// 3/23/98 WAH:  Added RemovePredecessor and RemoveSuccessor methods.
// 4/2/98 WAH:   Removed all sorts of destructor calls; fixed Ancestor-
//               ClusterInfo and CopiedResultInfo inits in copy constructor
//               and assignment (== instead of =); activated assignment
//               operator - added copying of DagNode info, changed
//               return value, reworked Predecessors/Successors copying,
//               added test for self-assignment.

#include <iostream.h>
#include <fstream.h>
#include "SmallListElement.H"
#include "BigListElement.H"

/* Debugging support, courtesy of Sumedh */
// #define _BIGLISTELEMENT_DEBUG_
#ifdef _BIGLISTELEMENT_DEBUG_
#define derr(s)         cerr << s
#else
#define derr(s)
#endif

#define AddEntry(E,D,O,I,L,P);  { (E).SetDependencyType((D));   \
                                  (E).SetOp((O));               \
                                  (E).SetDagEntry((I));         \
                                  (L)->push_back((E));          \
                                  (P) = (L)->back(); }

#define AddEntryBeginning(E,D,O,I,L,P); { (E).SetDependencyType((D));   \
                                  (E).SetOp((O));               \
                                  (E).SetDagEntry((I));         \
                                  (L)->insert((L)->begin(),(E));                \
                                  (P) = (L)->back(); }


/* AddPredecessorBeginning: Add an Op as a data predecessor with an edge of type
   Dependency */
int BigListElement::AddPredecessorBeginning( enum edgeTypes Dependency, legoOp *Op,
                                    BigListElement *Iter )
{
   SmallListElement Element;
   SmallListElement Ptr;

   AddEntryBeginning( Element, Dependency, Op, Iter, Predecessors, Ptr );
#if defined (_BIGLISTELEMENT_DEBUG_)
   derr ("** Cur Id " << GetOp()->GetOpId() << ", Predecessor "
        << Ptr.GetOp()->GetOpId() << "\n");
#endif
   return Predecessors->size();
}


/* AddPredecessor: Add an Op as a data predecessor with an edge of type
   Dependency */
int BigListElement::AddPredecessor( enum edgeTypes Dependency, legoOp *Op,
                                    BigListElement *Iter )
{
   SmallListElement Element;
   SmallListElement Ptr;

   AddEntry( Element, Dependency, Op, Iter, Predecessors, Ptr );
#if defined (_BIGLISTELEMENT_DEBUG_)
   derr ("** Cur Id " << GetOp()->GetOpId() << ", Predecessor "
        << Ptr.GetOp()->GetOpId() << "\n");
#endif
   return Predecessors->size();
}


/* AddSuccessor: Add an Op as a data successor with an edge of type
   Dependency */
int BigListElement::AddSuccessor( enum edgeTypes Dependency, legoOp *Op,
                                  BigListElement *Iter )
{
   SmallListElement Element;
   SmallListElement Ptr;

   AddEntry( Element, Dependency, Op, Iter, Successors, Ptr );
#if defined (_BIGLISTELEMENT_DEBUG_)
   derr ("** Cur Id " << GetOp()->GetOpId() << ", Successor "
        << Ptr.GetOp()->GetOpId() << "\n");
#endif
   return Successors->size();
}


/* RemovePredecessor: Remove an Op as a data predecessor with an edge of type
   Dependency */
/* DANGER!!! Predecessors and Successors are implemented as STL vectors.
   These two remove functions must use vector::erase, which MAY INVALIDATE
   ITERATORS INTO THE VECTORS! You'll have to handle that yourself, or
   reimplement using lists or some other STL class. */
int BigListElement::RemovePredecessor( enum edgeTypes Dependency, legoOp *Op,
                                       BigListElement *Iter )
{
   SmallListElement *Element;
   //   SmallListElement Ptr;
   int PredId = Op->GetOpId();

   //   AddEntry( Element, Dependency, Op, Iter, Predecessors, Ptr );
   vector < SmallListElement >::iterator Front, Back;

   for ( Front = Predecessors->begin(), Back = Predecessors->end();
         Front != Back; Front++ )
     {
       Element = &(*Front);
       if ( Element->GetOp() == Op &&
            Element->GetDagEntry() == Iter &&
            Element->GetDependencyType() == Dependency )
         {
           //      delete &(*Front);
           Predecessors->erase (Front);
#if defined (_BIGLISTELEMENT_DEBUG_)
           derr ("** Cur Id " << GetOp()->GetOpId() << ", ~Predecessor "
                << PredId << "\n");
#endif
           break;
         } // end if
     } // end for

   return Predecessors->size();
}


/* RemoveSuccessor: Remove an Op as a data successor with an edge of type
   Dependency */
int BigListElement::RemoveSuccessor( enum edgeTypes Dependency, legoOp *Op,
                                       BigListElement *Iter )
{
   SmallListElement *Element;
   //   SmallListElement Ptr;
   int SuccId = Op->GetOpId();

   //   AddEntry( Element, Dependency, Op, Iter, Successors, Ptr );
   vector < SmallListElement >::iterator Front, Back;

   for ( Front = Successors->begin(), Back = Successors->end();
         Front != Back; Front++ )
     {
       Element = &(*Front);
       if ( Element->GetOp() == Op &&
            Element->GetDagEntry() == Iter &&
            Element->GetDependencyType() == Dependency )
         {
           //      delete &(*Front);
           Successors->erase (Front);
#if defined (_BIGLISTELEMENT_DEBUG_)
           derr ("** Cur Id " << GetOp()->GetOpId() << ", ~Successor "
                << SuccId << "\n");
#endif
           break;
         } // end if
     } // end for
        
   return Successors->size();
}


/* RemovePredecessor: Remove an Op as a data predecessor with an edge of type
   Dependency */
/* DANGER!!! Predecessors and Successors are implemented as STL vectors.
   These two remove functions must use vector::erase, which MAY INVALIDATE
   ITERATORS INTO THE VECTORS! You'll have to handle that yourself, or
   reimplement using lists or some other STL class. */
vector < SmallListElement >::iterator 
BigListElement::RemovePredecessor( enum edgeTypes Dependency, legoOp *Op )
{
   SmallListElement *Element;
   //   SmallListElement Ptr;
   int PredId = Op->GetOpId();

   vector < SmallListElement >::iterator Front, Back, returniter;

   for ( Front = Predecessors->begin(), Back = Predecessors->end();
         Front != Back; Front++ )
     {
       Element = &(*Front);
       if ( Element->GetOp() == Op &&
            Element->GetDependencyType() == Dependency )
         {
           //      delete &(*Front);
           returniter = Predecessors->erase (Front);
           derr ("\nRemoved !!!   Size now = " << Predecessors->size());
#if defined (_BIGLISTELEMENT_DEBUG_)
           derr ("** Cur Id " << GetOp()->GetOpId() << ", ~Predecessor "
                << PredId << "\n");
#endif
           return returniter;
         } // end if
       else {
         returniter = Predecessors->end(); 
       }
     } // end for

   derr ("\nNot Removed ???   Size now = " << Predecessors->size());
   return returniter;
}


/* RemoveSuccessor: Remove an Op as a data successor with an edge of type
   Dependency */
vector < SmallListElement >::iterator 
BigListElement::RemoveSuccessor( enum edgeTypes Dependency, legoOp *Op )
{
   SmallListElement *Element;
   //   SmallListElement Ptr;
   int SuccId = Op->GetOpId();

   vector < SmallListElement >::iterator Front, Back, returniter;

   for ( Front = Successors->begin(), Back = Successors->end();
         Front != Back; Front++ )
     {
       Element = &(*Front);
       if ( Element->GetOp() == Op &&
            Element->GetDependencyType() == Dependency )
         {
           //      delete &(*Front);
           returniter = Successors->erase (Front);
           derr ("\nRemoved !!!   Size now = " << Successors->size());
#if defined (_BIGLISTELEMENT_DEBUG_)
           derr ("** Cur Id " << GetOp()->GetOpId() << ", ~Successor "
                << SuccId << "\n");
#endif
           return returniter;
         } // end if
       else {
         returniter = Successors->end(); 
       }
     } // end for
        
   derr ("\nNot Removed ???   Size now = " << Successors->size());
   return returniter;
}


/* CompareIds: returns 1 NodeOne has a smaller OpId, 0 otherwise */
static int CompareIds( SmallListElement NodeOne, SmallListElement NodeTwo )
{
   int Opid1, Opid2, rc;

#if 0
   Opid1 = NodeOne.GetOp()->GetOpId();
   Opid2 = NodeTwo.GetOp()->GetOpId();
#if 0
   cerr << ">> CompareOpIds(1): Op 1-"
        << NodeOne.GetDagEntry()->GetOp()->GetOpId() << ", Op 2-"
        << NodeTwo.GetDagEntry()->GetOp()->GetOpId() << "\n";
   cerr << ">> CompareOpIds(2): Op 1-"
        << NodeOne.GetOp()->GetOpId() << ", Op 2-"
        << NodeTwo.GetOp()->GetOpId() << "\n";
#endif
#else
   Opid1 = NodeOne.GetDagEntry()->GetOp()->GetOpId();
   Opid2 = NodeTwo.GetDagEntry()->GetOp()->GetOpId();
#endif
   derr( ">> CompareOpIds: Op 1-" << Opid1 << ", Op 2-" << Opid2 << "\n" );
   rc = Opid1 > Opid2;

   return rc;
}

/* CompareWeights: returns 1 NodeOne has a smaller profile weight,
   0 otherwise */
static int CompareWeights( SmallListElement NodeOne, SmallListElement NodeTwo )
{
   return NodeOne.GetDagEntry()->GetWeight() >
          NodeTwo.GetDagEntry()->GetWeight();
}


/* CompareHeights: returns 1 NodeOne has a lesser height, 0 otherwise */
static int CompareHeights( SmallListElement NodeOne, SmallListElement NodeTwo )
{
   return NodeOne.GetDagEntry()->GetHeight() >
          NodeTwo.GetDagEntry()->GetHeight();
}


/* CompareDepths: returns 1 NodeOne has a lesser depth, 0 otherwise */
static int CompareDepths( SmallListElement NodeOne, SmallListElement NodeTwo )
{
   return NodeOne.GetDagEntry()->GetDepth() >
          NodeTwo.GetDagEntry()->GetDepth();
}


/* CompareValues: returns 1 NodeOne has a lesser Value field, 0 otherwise */
static int CompareValues( SmallListElement NodeOne, SmallListElement NodeTwo )
{
   return NodeOne.GetDagEntry()->Value > NodeTwo.GetDagEntry()->Value;
}


// BubbleSort:
void BigListElement::BubbleSort( vector < SmallListElement > *Vector,
                                 int (*Compare)( SmallListElement,
                                                 SmallListElement ) )
{
   int i, size;
   SmallListElement *Element, Element1;
   vector < SmallListElement >::iterator Front, Back, SubFront, SubBack, Max;


   derr( ">> BigListElement::BubbleSort\n" );

   // Until all nodes are examined, continue
   for ( size = Vector->size(), i = 0, Front = Vector->begin(),
         Back = Vector->end(); Front != Back; Front++, i++ ) {

      // Set the current list element as the maximum element
      Max = Front;

      // Compare all elements from this one down to the end
      // Keep an iterator to the largest one found
      for ( SubFront = Front; SubFront != Back; SubFront++ ) {
         if ( Compare( (*SubFront), (*Max) ) == 1 )
            Max = SubFront;
      }
      derr( "   ** New Max: Op " << (*Max).GetOp()->GetOpId() << "\n" );

      // Place the new max element into the n-th place in the list. If
      // the max element is the same as before the list was examined,
      // there is no need for the copy.
      if ( Max != Front ) {
         derr( "   Swapping Ops " << (*Max).GetDagEntry()->GetOp()->GetOpId()
               << " and " << (*Front).GetDagEntry()->GetOp()->GetOpId()
               << "\n" );
         // Element = new SmallListElement( *Max );
         //         Element1.SmallListElement( *Max );
         Element1 = *Max;  // wah 3/24/98
#if 0
         // (*Max).~SmallListElement();
         (*Max).SmallListElement( (*Vector)[ i ] );
         // (*Vector)[ i ].~SmallListElement();
         // (*Vector)[ i ].SmallListElement( *Element );
         (*Vector)[ i ].SmallListElement( Element1 );
#else
         *Max = (*Vector)[ i ];
         (*Vector)[ i ] = Element1;
#endif
      }
   }
   derr( "<< BigListElement::BubbleSort\n" );
}


/* SortList */
void BigListElement::SortList( vector <SmallListElement> *List,
                      int (*Compare)( SmallListElement, SmallListElement ) )
{
   sort( (*List).begin(), (*List).end(), Compare );
   // BubbleSort( List, Compare );
}


/* SortSuccessorsByOpId */
void BigListElement::SortSuccessorsByOpId()
{
   SortList( Successors, CompareIds );
}


/* SortSuccessorsByHeight */
void BigListElement::SortSuccessorsByHeight()
{
   SortList( Successors, CompareHeights );
}


/* SortSuccessorsByWeight */
void BigListElement::SortSuccessorsByWeight()
{
   SortList( Successors, CompareWeights );
}


/* SortSuccessorsByDepth */
void BigListElement::SortSuccessorsByDepth()
{
   SortList( Successors, CompareDepths );
}


/* SortSuccessorsByValue */
void BigListElement::SortSuccessorsByValue()
{
   SortList( Successors, CompareValues );
}


/* SortPredecessorsByOpId */
void BigListElement::SortPredecessorsByOpId()
{
   SortList( Predecessors, CompareIds );
}


/* SortPredecessorsByHeight */
void BigListElement::SortPredecessorsByHeight()
{
   SortList( Predecessors, CompareHeights );
}


/* SortPredecessorsByWeight */
void BigListElement::SortPredecessorsByWeight()
{
   SortList( Predecessors, CompareWeights );
}


/* SortPredecessorsByDepth */
void BigListElement::SortPredecessorsByDepth()
{
   SortList( Predecessors, CompareDepths );
}


/* SortPredecessorsByValue */
void BigListElement::SortPredecessorsByValue()
{
   SortList( Predecessors, CompareValues );
}


// FreeSmallVector: deallocate all memory stored with elements in a vector
//    of SmallListElements
void FreeSmallVector( vector < SmallListElement >::iterator Front,
                      vector < SmallListElement >::iterator Back )
{
   return;
}


// Allocate_AncestorClusterInfo - allocate an array of size n (> 0)
void BigListElement::Allocate_AncestorClusterInfo( int n )
{     
   if ( n > 0 && a_array_size == 0 ) {  // allocate 'positive' space
                                        // and don't allow reallocations
      AncestorClusterInfo = new int [ n ];
      a_array_size = n;
   }
}


// InitAncestorClusterInfo - sets all entries to -1
void BigListElement::InitAncestorClusterInfo()
{
   int i;

   if ( a_array_size > 0 )
      for ( i = 0; i < a_array_size; i++ ) AncestorClusterInfo[ i ] = -1;
}


// Allocate_CopiedResultInfo
void BigListElement::Allocate_CopiedResultInfo( int n )
{
   if ( n > 0 && c_array_size ==  0 ) { // allocate 'positive' space
                                        // and don't allow reallocations
      int i;

      CopiedResultInfo = new int [ n ];
      c_array_size = n;
      for ( i = 0; i < c_array_size; i++ ) CopiedResultInfo[ i ] = 0;
   }
}


// PrintElement: as it says
void BigListElement::PrintElement()
{
   cerr.width(4);
   cerr << "Opid " << GetOp()->GetOpId() << "\tHeight: " << GetHeight()
        << "\tDepth: " << GetDepth() << "\n\tWeight: "
        << GetWeight() << "\tValue: " << Value << "\tClusterid: " << ClusterId
        << "\n";
   cerr << "\tPOINTS TO: ";
   if ( NumSuccessors() == 0 ) cerr << "*** Exit Node ***\n";
   else {
      cerr << "(" << NumSuccessors() << ")";
      PrintList( Successors );
   }
   cerr << "\tDEPENDS ON: ";
   if ( NumPredecessors() == 0 ) cerr << "*** Entry Node ***\n";
   else {
      cerr << "(" << NumPredecessors() << ")";
      PrintList( Predecessors );
   }
}

//HZ: 8/24/00
// PrintElement: as it say (to a stream)
void BigListElement::PrintElement(ofstream & os1)
{
   os1.width(4);
   os1 << "Opid " << GetOp()->GetOpId() << "\tHeight: " << GetHeight()
        << "\tDepth: " << GetDepth() << "\n\tWeight: "
        << GetWeight() << "\tValue: " << Value << "\tClusterid: " << ClusterId
        << "\n";
   os1 << "\tPOINTS TO: ";
   if ( NumSuccessors() == 0 ) os1 << "*** Exit Node ***\n";
   else {
      os1 << "(" << NumSuccessors() << ")";
      PrintList( Successors, os1 );
   }
   os1 << "\tDEPENDS ON: ";
   if ( NumPredecessors() == 0 ) os1 << "*** Entry Node ***\n";
   else {
      os1 << "(" << NumPredecessors() << ")";
      PrintList( Predecessors, os1 );
   }
}

/* Constructor */
BigListElement::BigListElement()
{
   ClusterId = -1;
   Value = 0;
   a_array_size = 0;
   c_array_size = 0;
   Predecessors = new vector < SmallListElement >;
   Successors = new vector < SmallListElement >;
}


/* Destructor */
BigListElement::~BigListElement()
{
   int size, i;

   DestructSmallVector( Predecessors );
   delete Predecessors;
   DestructSmallVector( Successors );
   delete Successors;
   if ( a_array_size > 0 ) delete[] AncestorClusterInfo;
   if ( c_array_size > 0 ) delete[] CopiedResultInfo;
}


/* Copy constructor */
BigListElement::BigListElement( const BigListElement &src ) :
   DagNode( (DagNode) src )
{
   vector < SmallListElement >::iterator Front, Back;
   vector < SmallListElement > *Vptr;
   SmallListElement *ElementPtr, Tmp;
   int size, i;


   derr( ">> BigListElement::copy constructor\n" );

   ClusterId = src.ClusterId;
   Value = src.Value;
   a_array_size = src.a_array_size;
   c_array_size = src.c_array_size;

   // Copy the current AncestorClusterInfo array
   if ( src.a_array_size > 0 ) {
      AncestorClusterInfo = new int [ a_array_size ];
      for ( i = 0; i < a_array_size; i++ )
         AncestorClusterInfo[ i ] = src.AncestorClusterInfo[ i ];
   }
   else AncestorClusterInfo = NULL;

   // Copy the current CopiedResultInfo array
   if ( src.c_array_size > 0 ) {
      CopiedResultInfo = new int [ c_array_size ];
      for ( i = 0; i < c_array_size; i++ )
         CopiedResultInfo[ i ] = src.CopiedResultInfo[ i ];
   }
   else CopiedResultInfo = NULL;

   // wah 3/24/98 Reworked Predecessors/Successors construction
   // Should the current Predecessors be destroyed? Or do we assume that
   // it doesn't exist?
   // DestructSmallVector( Predecessors );
   //   Predecessors = new vector < SmallListElement >;
   Vptr = src.Predecessors;
   Front = Vptr->begin();
   Back = Vptr->end();

   derr( "   Original predecessors\n" );
   // PrintList( Vptr );
   // Use the copy constructors of the STL data structures
   derr( "   Copying predecessors..." );
   //   Predecessors->vector( Front, Back );
   Predecessors = new vector < SmallListElement > ( Front, Back );
   derr( "Copied predecessors\n" );
   // PrintList( Predecessors );

   // Should the current Successors be destroyed? Or do we assume that
   // it doesn't exist?
   // DestructSmallVector( Successors );
   //   Successors = new vector < SmallListElement >;
   Vptr = src.Successors;
   Front = Vptr->begin();
   Back = Vptr->end();

   derr( "   Original successors\n" );
   // PrintList( Vptr );
   // Use the copy constructors of the STL data structures
   derr( "   Copying successors..." );
   //   Successors->vector( Front, Back );
   Successors = new vector < SmallListElement > ( Front, Back );
   derr( "Copied successors\n" );
   derr( "<< BigListElement::copy constructor\n" );
}

#if 1
/* = operator */
BigListElement & BigListElement::operator=(const BigListElement &src )
{
   vector < SmallListElement >::iterator Front, Back;
   vector < SmallListElement > *Vptr;
   SmallListElement *ElementPtr, Tmp;
   int size, i;


   if (&src == this) return *this;
   derr( ">> BigListElement: = operator\n" );

   // Copy DagNode members!
   height = src.height;
   depth = src.depth;
   cycle = src.cycle;
   ProfileWeight = src.ProfileWeight;
   Op = src.Op;

   ClusterId = src.ClusterId;
   Value = src.Value;
   a_array_size = src.a_array_size;
   c_array_size = src.c_array_size;

   // Copy the current AncestorClusterInfo array
   if ( src.a_array_size > 0 ) {
      AncestorClusterInfo = new int [ a_array_size ];
      for ( i = 0; i < a_array_size; i++ )
         AncestorClusterInfo[ i ] = src.AncestorClusterInfo[ i ];
   }
   else AncestorClusterInfo = NULL;

   // Copy the current CopiedResultInfo array
   if ( src.c_array_size > 0 ) {
      CopiedResultInfo = new int [ c_array_size ];
      for ( i = 0; i < c_array_size; i++ )
         CopiedResultInfo[ i ] = src.CopiedResultInfo[ i ];
   }
   else CopiedResultInfo = NULL;

   DestructSmallVector( Predecessors );
   delete Predecessors;
   Vptr = src.Predecessors;
   Front = Vptr->begin();
   Back = Vptr->end();
   // Use the copy constructors of the STL data structures
   //   derr( "   Copying predecessors..." );
   Predecessors = new vector < SmallListElement > ( Front, Back );

   //   derr( "   Original predecessors\n" );
   // PrintList( Vptr );
   //   derr( "Copied predecessors\n" );
   // PrintList( Predecessors );

   DestructSmallVector( Successors );
   delete Successors;
   Vptr = src.Successors;
   Front = Vptr->begin();
   Back = Vptr->end();
   // Use the copy constructors of the STL data structures
   //   derr( "   Copying successors..." );
   Successors = new vector < SmallListElement > ( Front, Back );

   //   derr( "   Original successors\n" );
   // PrintList( Vptr );
   //   derr( "Copied successors\n" );
   // PrintList( Successors );

   derr( "<< BigListElement: = operator\n" );
   return *this;
}
#endif


/***************************** Utility functions *********************/

/******************* BEGIN ****************/

// DestructBigVector:  destructs a vector of of BigListElements
void DestructBigVector( vector < BigListElement > *Vector )
{
   (*Vector).erase( (*Vector).begin(), (*Vector).end() );

   return;
}


// DestructBigList:  destructs a list of of BigListElements
void DestructBigList( list < BigListElement > *List )
{
   (*List).erase( (*List).begin(), (*List).end() );

   return;
}


// CopyBigVector: copy elements from Src to Target
int CopyBigVector( vector < BigListElement > *Src,
                   vector < BigListElement > *Target )
{
   vector < BigListElement >::iterator Front, Back;
   BigListElement *Element;

   (*Target).reserve( (*Src).size() );
   for ( Front = (*Src).begin(), Back = (*Src).end(); Front != Back; Front++ ) {
      Element = new BigListElement( *Front );
      (*Target).push_back( *Element );
   }
   return( (*Target).size() );
}


//FindOpInBigList
int FindOpInList( vector < BigListElement > *V, int OpId )
{
   int i, size; 
   BigListElement Element;


   if ( (size=(*V).size()) == 0 ) return -1;
   for ( i = 0; i < size; i++ )
      if ( (*V)[ i ].GetOp()->GetOpId() == OpId )
         return i;

   return -1;
}


// FindNode: find Op w/'OpId' in the vector V.
vector < BigListElement >::iterator FindNode( int OpId,
                                              vector < BigListElement > *V )
{
   vector < BigListElement >::iterator Front, Back;


   for ( Front = V->begin(), Back = V->end(); Front != Back; Front++ )
      if ( (*Front).GetOp()->GetOpId() == OpId ) return Front;

   return V->end();
}

/******************** END *****************/

---