/*
 *  LIST_SORT.C
 *
 *	list_sort(list, compare_routine) -> sorted_list
 *
 *	Assumes a list of structures, with a pointer to "next" as the first
 *	field.	It reorders the list into ascending order, and returns the
 *	new first node's address.  It is order N log(N).
 *
 *	The compare routine should return positive if the items are in order,
 *	and non-positive if they are not.  If the compare routine returns zero
 *	in case of equality, the sort will be stable.
 */

/*	This routine depends upon compiler-dependant struct layout, but this
 *	assumption is likely to be fairly commonly valid.
 */

#define _LIST_SORT_C

#include <stdio.h>
#include "version.h"

IDENT(".01");

typedef struct node_struct {
    struct node_struct *next;
} node_type;

typedef int (*cf_type)(node_type *, node_type *);

Local node_type *list_sort(node_type *, cf_type);

node_type *
list_sort(node_type *list, cf_type cmp)
{
    struct node_struct *new[2]; /* back of new stuff */
    struct node_struct *old[2]; /* front of old stuff */
    int n;		    /* current new list */
    int o;		    /* current old list */
    long m, hm; 	    /* m is merge length, hm is half of that */
    long count[2];	    /* counts entries drawn from "old" lists */
    node_type front[2];     /* artificial front-of-list */

    /*
     *	The basic notion of this sort is to make sorted sublists longer and
     *	longer by merging.  On the Nth pass through the list, sorted
     *	sublists of length 2^(N-1) are produced.  Eventually, the entire
     *	list is sorted, in log2(N)+1 passes through the list.  There is
     *	extra bookkeeping overhead, but minimal extra storage space needed.
     *	Counts and clever pointer management substitute for extra "glue"
     *	nodes.
     *
     *	while more than one list
     *		while not at end of composite lists
     *			for each merge_length(m) block
     *				merge lists onto current output list
     *			toggle current output list
     */

    front[0].next = 0;
    front[1].next = list;

    for (hm = 0, m = 1; front[1].next != 0; hm = m, m <<= 1) {
	/* log2(N)+1 times through (since m doubles every time) */

	new[0] = &front[0];	old[0] = front[0].next;
	new[1] = &front[1];	old[1] = front[1].next;
	n = 0;
	count[0] = count[1] = 0;

	for (;;) {
	    /*
	     * N times through (each time through consumes
	     * one item from one or the other of the old lists)
	     */

	    if (old[0] == 0) {
		/*
		 * First composite input list exhausted...
		 * copy second list onto output, quitting
		 * if second list is at end.
		 */

		new[n] = new[n]->next = old[1];
		if ((old[1] = old[1]->next) == 0)
		    break;
		if (++count[1] >= hm)
		    n = 1 - n, count[0] = count[1] = 0;
	    } else if (old[1] == 0) {
		/*
		 * Second composite input list exhausted...
		 * copy first list onto output, quitting
		 * if first list is at end.
		 */

		new[n] = new[n]->next = old[0];
		if ((old[0] = old[0]->next) == 0)
		    break;
		if (++count[0] >= hm)
		    n = 1 - n, count[0] = count[1] = 0;
	    } else if (count[0] >= hm) {
		/*
		 * First logical input list exhausted...
		 * copy second list onto output, swapping
		 * output list if second input list ends.
		 */

		new[n] = new[n]->next = old[1];
		old[1] = old[1]->next;
		if (++count[1] >= hm)
		    n = 1 - n, count[0] = count[1] = 0;
	    } else if (count[1] >= hm) {
		/*
		 * Second logical input list exhausted...
		 * copy first list onto output, swapping
		 * output list if first input list ends.
		 */

		new[n] = new[n]->next = old[0];
		old[0] = old[0]->next;
		if (++count[0] >= hm)
		    n = 1 - n, count[0] = count[1] = 0;
	    } else {
		/*
		 * Compare the two items at the heads of
		 * the input lists, and put the smaller
		 * on the current output list.
		 */

		o = (*cmp)(old[0], old[1]) > 0;
		new[n] = new[n]->next = old[o];
		old[o] = old[o]->next;
		++count[o];
	    }
	}
	new[0]->next = new[1]->next = 0;
    }
    return front[0].next;
}