Listing 9: PolySort implementation

/*
 *  psort.c
 */

#define NO_SORT_LOG     //#define to disable logging
#include "psort.h"
//#include "sortlog.h"  /* on code disk only */

PolySort::PolySort( InternalSort & insort,
                    int nfiles, size_t blen ) :
    _next_call(0), _width(insort.Width())
{   Ins = &insort;
    _old_handler = set_new_handler(0);
    if( nfiles < 3 )  nfiles = 3;   //minimum size
    Src  = new MergeFile( _width, blen );
    Targ = new MergeFile( _width, blen );
    Ps   = new PreSort( *Src, insort );
    Mp   = new MergeList( nfiles - 1, _width, blen );
    set_new_handler(_old_handler);
}

PolySort::~PolySort()   {   delete Mp;
                            delete Src;
                            delete Targ;
                            delete Ps;     }

int PolySort::_distribute_runs()
{   int level = 0;
    MergeFile *p, *tail = Mp->PeekTail();
    if( _next_call++ )  //Clear for next sort run ...
        for( Mp->Restart(); Mp->Test(); Mp->Next() )
            Mp->Current()->ResetIOMode(MergeFile::out);

    while( !Src->EndOfFile() )
    {  /* Compute ideal #runs to reach next level.. */
        int ideal = (level == 0 ? 1 : tail->Actual());
        size_t max_runs = 0;
        Mp->Restart();
        p = Mp->Current();
        p->Null( p->Actual() ); /*save old value */
        p->Actual( ideal );

        while (1)
        {   int actual = p->Null();  /* get old value*/
            p->Null( p->Actual() - actual);
            max_runs += p->Null();
            Mp->Next();
            if( Mp->Test() == 0 ) break;
            p = Mp->Current(); /* next buffer */
            p->Null( p->Actual() ); /*save old value */
            p->Actual( actual + ideal ); /* new ideal*/
        }

        /* Distribute runs for current level .... */
        while( max_runs && !Src->EndOfFile() )
        {   int cont;
            size_t items;
            for( Mp->Restart(); Mp->Test(); Mp->Next())
            {   p = Mp->Current();
                if( Src->EndOfFile() )
                    break;
                while( p->Null() )
                {   items = Ps->GenerateRun( p, cont);
                    if( items == 0 )
                        break;
                    d_SetItemsIn(d_ItemsIn() + items);
                    d_SetRunsIn(d_RunsIn() + 1);
                    if( 0 == level || cont > 0 )
                    {   p->Null(p->Null() - 1);
                        d_SetRunsOut(d_RunsOut() + 1);
                        --max_runs;
                        break;
                    }   //else continue same run...
                }
            }
        }
        level++;
    }

    d_RunDistributionSummary( level, Mp, Targ );
    return level;
}

void PolySort::_merge_runs(int level )
{   /* Flush & rewind work files and begin merge....*/
    for( Mp->Restart(); Mp->Test(); Mp->Next() )
        Mp->Current()->ResetIOMode(MergeFile::in);

    do  /* For each merge level...... */
    {   MergeFile *p, *head = Mp->PeekHead();
        int min_runs = head->Actual(); //has <st #runs
        Targ->ResetIOMode(MergeFile::out);   //zero out
        d_DisplayRunsAtBegLevel( level, Mp, Targ );

        do  //Merge min_runs from each file to Targ
        {   //Exclude all files with null runs ...
            d_SetXferCount(0);
            for(Mp->Restart(); Mp->Test(); Mp->Next() )
            {   p = Mp->Current();
                if( p->Null() )
                {   p->Null( p->Null() - 1 );
                    p->Actual( p->Actual() - 1 );
                }
                else  //Put file on active list....
                    Mp->PutActive(p);
            } //if all files have null runs, do a
            if( Mp->ActiveCount() == 0 )  //dummy merge
                Targ->Null(Targ->Null() + 1);
            else do   //Merge 1 run from each active
            {   PCDATA pmin, ptmp; //file to Targ...
                MergeFile *fmin;
                Mp->RestartActive();
                fmin = Mp->CurrentActive();
                pmin = fmin->Nextg();
                Mp->NextActive();
                while(Mp->TestActive()) //find <st item
                {   p = Mp->CurrentActive();
                    ptmp = p->Nextg();
                    if( Ins->Compare
                        ( &ptmp, &pmin ) < 0 )
                    {   fmin = p;
                        pmin = ptmp;
                    }
                    Mp->NextActive();
                }
                /* Transfer 1 data item .... */
                Targ->Put( fmin->Get() );
                d_SetXferCount( d_XferCount()+1 );
                d_SetXferTotal( d_XferTotal()+1 );
                /* Detect end of run ...... */
                ptmp = Targ->Lastp();
                pmin = fmin->Nextg();
                if( fmin->EndOfFile() ||
                    Ins->Compare( &ptmp, &pmin) > 0 )
                {   fmin->Actual(fmin->Actual()-1);
                    Mp->DetachActive(fmin);
                }
            } while( Mp->ActiveCount() );
            //.... end of a mini-pass
            Targ->Actual(Targ->Actual() + 1);
            d_DisplayRunsAtEndPass( Mp, Targ );
        } while( --min_runs );  //...end of 1 merge pass
        /* Rotate files for next level ...... */
        if( level > 1 )
        {   Targ->ResetIOMode( MergeFile::in );
            Mp->PutTail(Targ);  //now has >st #runs
            Mp->GetHead(Targ);  //head empty, = next Targ
        }
    } while( --level );
}

void PolySort::Sort( ffstream *input_stream,
                     const char *output_file )
{   d_ResetLog();
    Src->AttachStream( input_stream );
    _merge_runs( _distribute_runs() );
    d_DisplayXferTotals();
    d_VerifySort( output_file, Ins, Mp, Targ );
    Targ->RenameOutput( output_file );
}
//End of File