/*
*
*  Optimal list-merge sorting algorithm with exponential merge schedule.
*
*  From: Software Development International, Winter 1991.
*
*  This implementation by Jeremy Harris jgh@imptld.com
*
*  Adapted into toolkit by Martin Poole mpoole@cix.compulink.co.uk
*  
**
** WARNING !!  WARNING !! WARNING !! WARNING !! WARNING !! WARNING !!
**
** Any changes to be made to this file should first be checked with
** mplib1 source control for library integrity.
**
** mplib1 source control can be reached at  mplib1@quatermass.co.uk
** 
* $Source: /home/cvs/cvsroot/onelan/onelan/src/mplib1/libsrc/lmsort.c,v $
* $Author: mpoole $
* $Date: 2002/10/07 09:37:39 $
* $Revision: 1.2 $
*
* $Log: lmsort.c,v $
* Revision 1.2  2002/10/07 09:37:39  mpoole
* Initial checkin of mplib1-3.1.0
*
* Revision 1.1  2002/10/07 09:36:57  mpoole
* Initial checkin of mplib1-3.1.0
*
*
*******************************************************************************
*/

#ident "$Header: /home/cvs/cvsroot/onelan/onelan/src/mplib1/libsrc/lmsort.c,v 1.2 2002/10/07 09:37:39 mpoole Exp $"

/* ------------------------------------------------------------------
    defines
   ------------------------------------------------------------------ */

#ifdef TRACE
#undef TRACE
#define TRACE(x) printf x
#else
#define NO_TRACE
#define TRACE(x) /*empty*/
#endif

#define MAXHOOKS 24	/* permits merging up to 33,554,430 records */

#define KEYVAL(dataitem) dataitem
#define GETKEY(datapp) KEYVAL(*(datapp)->dp)

/* ------------------------------------------------------------------
    includes
   ------------------------------------------------------------------ */

#include <sys/types.h>
#ifdef NO_TRACE
#include <stdio.h>
#endif

#include <mplib1/mplib1_config.h>
#include <mplib1/lmsort.h>

/* ------------------------------------------------------------------
    variables
   ------------------------------------------------------------------ */

static int (*compare)( const void *, const void *);


/* ------------------------------------------------------------------
    code starts here
   ------------------------------------------------------------------ */


static struct lmsortp *
binmerge( register struct lmsortp * datap_a,
	  register struct lmsortp * datap_b )
{
    register struct lmsortp * tail;
    struct lmsortp * start;

    /* Initialisation */
    if( (*compare)( datap_a->dp, datap_b->dp ) > 0 )
    {
	start= datap_b;
	goto b_wins;
    }
    start= datap_a;

a_wins:	do
	{
	    tail= datap_a;
	    if( !(datap_a= datap_a->next) )
	    {
		tail->next= datap_b;
		return(start);
	    }
	} while( (*compare)( datap_a->dp, datap_b->dp ) <= 0 );
	tail->next= datap_b;

b_wins:	do
	{
	    tail= datap_b;
	    if( !(datap_b= datap_b->next) )
	    {
		tail->next= datap_a;
		return(start);
	    }
	} while( (*compare)( datap_a->dp, datap_b->dp ) >= 0 );
	tail->next= datap_a;
	goto a_wins;

    /*NOTREACHED*/
}





struct lmsortp *
lmsort( struct lmsortp * start, int (*compar)(const void *, const void *) )
{
    int k;
    struct lmsortp * temp;
    struct lmsortp * this_one;
    struct lmsortp * next_one;
    struct lmsortp * runhook[MAXHOOKS];

    /* Initialisation */
    compare = compar;
    for( k= 0; k < MAXHOOKS; k++ )
	runhook[k]= 0;

    this_one= start;
    while( this_one )
    {
	temp= this_one;
	next_one= this_one->next;
	if( next_one )
	{
	    /* Run Linker */

	    if( (*compare)( this_one->dp, next_one->dp ) <= 0 )
	    {
		/* Non-descending-order run */
		TRACE( ("linker: run up\n%d", GETKEY(this_one) ) );
		do				/* no need to relink default */
		{
		    TRACE( (" %d", GETKEY(next_one)) );
		    this_one= next_one;
		    next_one= this_one->next;
		} while( next_one  &&  (*compare)( this_one->dp, next_one->dp ) <= 0 );
		this_one->next= 0;		/* terminate run up */
		TRACE( ("\n") );
	    }
	    else
	    {
		/* Descending-order run */
		TRACE( ("linker: run down\n%d", GETKEY(this_one) ) );
		this_one->next= 0;		/* terminate run down */
		do				/* relink backwards */
		{
		    TRACE( (" %d", GETKEY(next_one)) );
		    temp= next_one;
		    next_one= next_one->next;
		    temp->next= this_one;
		    this_one= temp;
		} while( next_one  &&  (*compare)( this_one->dp, next_one->dp ) >= 0 );
		TRACE( ("\n") );
	    }
	}
	/* "temp" is now the head of a non-descending run */

	/* Merge Scheduler */
	TRACE( ("Merge Scheduler\n") );
	k= 0;
	do		/* Put the sublist on a hook */
	{
	    TRACE( ("hook %d", k) );
	    if( runhook[k] )
	    {
		/* Hook is occupied; merge and retry at hook k+1. */
		TRACE( (" was in use; merging\n") );
		temp= binmerge( runhook[k], temp );
		runhook[k]= 0;
	    }
	    else
	    {
		TRACE( (" was free\n") );
		runhook[k]= temp;
		temp= 0;		/* flag for loop exit */
	    }
	    k++;
	} while( temp );
	this_one= next_one;
    }


    /*
     * Run Collector.
     * At this point the eof has been found, so the runs in
     * runhook must be collected from the bottom up to keep it stable.
     */
    TRACE( ("Collector\n") );
    k= 0;
    while( !runhook[k] )
    {
	TRACE( ("hook %d free\t", k) );
	k++;
    }

    TRACE( ("list on hook %d\n", k) );
    start= runhook[k];
    while( ++k < MAXHOOKS )
	if( runhook[k] )
	{
	    TRACE( ("merging with list on hook %d\n", k) );
	    start= binmerge( runhook[k], start );
	}
	else
	    TRACE( ("hook %d free\t", k) );


    TRACE( ("finished\n") );
    return( start );
}


/* -- End of File -- */