/* * * 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. * ** ** 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/dl_sort_i.c,v $ * $Author: mpoole $ * $Date: 2002/10/07 09:37:39 $ * $Revision: 1.2 $ * * $Log: dl_sort_i.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:56 mpoole * Initial checkin of mplib1-3.1.0 * * ******************************************************************************* */ #ident "$Header: /home/cvs/cvsroot/onelan/onelan/src/mplib1/libsrc/dl_sort_i.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) (datapp->ln_Item) /* ------------------------------------------------------------------ includes ------------------------------------------------------------------ */ #include #ifdef NO_TRACE #include #endif #include #include /* ------------------------------------------------------------------ variables ------------------------------------------------------------------ */ static int (*compare)( const void *, const void *); /* ------------------------------------------------------------------ code starts here ------------------------------------------------------------------ */ static dl_Node_t * binmerge( register dl_Node_t * datap_a, register dl_Node_t * datap_b ) { register dl_Node_t * tail; dl_Node_t * start; /* Initialisation */ if( (*compare)( datap_a->ln_Item, datap_b->ln_Item ) > 0 ) { start= datap_b; goto b_wins; } start= datap_a; a_wins: do { tail= datap_a; if( !(datap_a= datap_a->ln_Succ) ) { tail->ln_Succ= datap_b; return(start); } } while( (*compare)( datap_a->ln_Item, datap_b->ln_Item ) <= 0 ); tail->ln_Succ= datap_b; b_wins: do { tail= datap_b; if( !(datap_b= datap_b->ln_Succ) ) { tail->ln_Succ= datap_a; return(start); } } while( (*compare)( datap_a->ln_Item, datap_b->ln_Item ) >= 0 ); tail->ln_Succ= datap_a; goto a_wins; /*NOTREACHED*/ } int dl_sort_i( dl_List_t *sort_list, int (*compar)(const void *, const void *) ) { int k; dl_Node_t * temp; dl_Node_t * this_one; dl_Node_t * next_one; dl_Node_t * runhook[MAXHOOKS]; if (sort_list->ln_Head.ln_Succ->ln_Succ) { /* Initialisation */ compare = compar; for( k= 0; k < MAXHOOKS; k++ ) runhook[k]= NULL; /* And now knock out the last forward pointer so we can use a simple test to finish */ sort_list->ln_Tail.ln_Pred->ln_Succ=NULL; this_one= sort_list->ln_Head.ln_Succ; while( this_one ) { temp= this_one; next_one= this_one->ln_Succ; if( next_one ) { /* Run Linker */ if( (*compare)( this_one->ln_Item, next_one->ln_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= this_one->ln_Succ; } while( next_one && (*compare)( this_one->ln_Item, next_one->ln_Item ) <= 0 ); this_one->ln_Succ= 0; /* terminate run up */ TRACE( ("\n") ); } else { /* Descending-order run */ TRACE( ("linker: run down\n%d", GETKEY(this_one) ) ); this_one->ln_Succ= 0; /* terminate run down */ do /* relink backwards */ { TRACE( (" %d", GETKEY(next_one)) ); temp= next_one; next_one= next_one->ln_Succ; temp->ln_Succ= this_one; this_one= temp; } while( next_one && (*compare)( this_one->ln_Item, next_one->ln_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 Node 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->ln_Head.ln_Succ = temp; this_one = temp; temp = &sort_list->ln_Head; while(this_one) { TRACE( ("Adjust pred of %p\n", this_one) ); this_one->ln_Pred = temp; temp = this_one; this_one = this_one->ln_Succ; }; temp->ln_Succ = &sort_list->ln_Tail; sort_list->ln_Tail.ln_Pred = temp; TRACE( ("finished\n") ); } return( 0 ); } /* -- End of File -- */