/* * * 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 * * And now adapted for Amiga style double linked lists. * and then again for bpo_ lists * ** ** 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/bpo_sort_i.c,v $ * $Author: mpoole $ * $Date: 2002/10/07 09:37:37 $ * $Revision: 1.2 $ * * $Log: bpo_sort_i.c,v $ * Revision 1.2 2002/10/07 09:37:37 mpoole * Initial checkin of mplib1-3.1.0 * * Revision 1.1 2002/10/07 09:36:54 mpoole * Initial checkin of mplib1-3.1.0 * * ******************************************************************************* */ #ident "$Header: /home/cvs/cvsroot/onelan/onelan/src/mplib1/libsrc/bpo_sort_i.c,v 1.2 2002/10/07 09:37:37 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) (datapp->lno_Item) #define GNNODE(n,off) ((bpo_Node_t *)GRPTR(n,off)) /* ------------------------------------------------------------------ includes ------------------------------------------------------------------ */ #include #include #include #include #include #include #include #include #include #ifdef NO_TRACE #include #endif #include #include #include /* ------------------------------------------------------------------ variables ------------------------------------------------------------------ */ static int (*compare)( const void *, const void *); static char *base_p; /* ------------------------------------------------------------------ code starts here ------------------------------------------------------------------ */ static bpo_Node_t * binmerge( register bpo_Node_t * datap_a, register bpo_Node_t * datap_b ) { register bpo_Node_t * tail; bpo_Node_t * start; /* Initialisation */ if( (*compare)( GRPTR(datap_a,datap_a->lno_Item), GRPTR(datap_b,datap_b->lno_Item) ) > 0 ) { start= datap_b; goto b_wins; } start= datap_a; a_wins: do { tail= datap_a; if( !(datap_a= GRPTR(datap_a,datap_a->lno_Succ)) ) { tail->lno_Succ= datap_b->lno_me; return(start); } } while( (*compare)( GRPTR(datap_a,datap_a->lno_Item), GRPTR(datap_b,datap_b->lno_Item) ) <= 0 ); tail->lno_Succ= datap_b->lno_me; b_wins: do { tail= datap_b; if( !(datap_b= GRPTR(datap_b,datap_b->lno_Succ)) ) { tail->lno_Succ= datap_a->lno_me; return(start); } } while( (*compare)( GRPTR(datap_a,datap_a->lno_Item), GRPTR(datap_b,datap_b->lno_Item) ) >= 0 ); tail->lno_Succ= datap_a->lno_me; goto a_wins; /*NOTREACHED*/ } static void tweak_header( bpo_Node_t *tail, bpo_Node_t *first ) { /* first is passed as dummy in case modification via tail changes its value */ bpo_Node_t * temp; temp = GNNODE( &tail, tail->lno_Pred ); temp->lno_Succ = (off_t)0; return; } int bpo_sort_i( bpo_List_t *sort_list, int (*compar)(const void *, const void *) ) { int k; bpo_Node_t * temp; bpo_Node_t * this_one; bpo_Node_t * next_one; bpo_Node_t * runhook[MAXHOOKS]; off_t toff; toff = Get_SODB_Offset( sort_list ); base_p = ((char *)(sort_list)) - toff; this_one = GNNODE(&sort_list->lno_Head, sort_list->lno_Head.lno_Succ); if ( this_one->lno_Succ ) { /* Initialisation */ compare = compar; for( k= 0; k < MAXHOOKS; k++ ) runhook[k]= NULL; tweak_header( &sort_list->lno_Tail, this_one ); while( this_one ) { temp= this_one; next_one= GNNODE(this_one, this_one->lno_Succ); if( next_one ) { /* Run Linker */ if( (*compare)( GRPTR(this_one, this_one->lno_Item), GRPTR(next_one, next_one->lno_Item) ) <= 0 ) { /* Non-descending-order run */ TRACE( ("linker: run up\n%p", GETKEY(this_one) ) ); do /* no need to relink default */ { TRACE( (" %d", GETKEY(next_one)) ); this_one= next_one; next_one= GNNODE(this_one, this_one->lno_Succ); } while( next_one && (*compare)( GRPTR(this_one, this_one->lno_Item), GRPTR(next_one, next_one->lno_Item) ) <= 0 ); this_one->lno_Succ= 0; /* terminate run up */ TRACE( ("\n") ); } else { /* Descending-order run */ TRACE( ("linker: run down\n%d", GETKEY(this_one) ) ); this_one->lno_Succ= 0; /* terminate run down */ do /* relink backwards */ { TRACE( (" %d", GETKEY(next_one)) ); temp= next_one; next_one= GNNODE(next_one, next_one->lno_Succ); temp->lno_Succ= GOFF(base_p,this_one); this_one= temp; } while( next_one && (*compare)( GRPTR(this_one, this_one->lno_Item), GRPTR(next_one, next_one->lno_Item) ) >= 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) ); temp= runhook[k]; while( ++k < MAXHOOKS ) if( runhook[k] ) { TRACE( ("merging with list on hook %d\n", k) ); temp= binmerge( runhook[k], temp ); } else TRACE( ("hook %d free\t", k) ); /* At this point, the first bpo_Node_t is pointed to by start, attach this to the Head of the list, and then walk the list correcting the back pointers */ TRACE( ("\nAdjust List\n") ); sort_list->lno_Head.lno_Succ = temp->lno_me; this_one = temp; temp = &sort_list->lno_Head; while(this_one) { TRACE( ("Adjust pred of %p\n", this_one) ); this_one->lno_Pred = temp->lno_me; temp = this_one; this_one = GNNODE(this_one,this_one->lno_Succ); }; temp->lno_Succ = sort_list->lno_Tail.lno_me; sort_list->lno_Tail.lno_Pred = temp->lno_me; TRACE( ("finished\n") ); } return( 0 ); } /* -- End of File -- */