/* lsort.c -- linked list (merge) sort
 *
 * public domain code by Ray Gardner.
 *
 * Modified by Ken Murchison to use getnext(), setnext() and call_data
 * parameters.
 */

/* $Id: lsort.c,v 1.2 2002/05/25 19:57:47 leg Exp $ */

#include "lsort.h"
#include <stdlib.h>

/* merge two sorted lists */
static void *lmerge(void *p, void *q,
		    void *(*getnext)(void *),
		    void (*setnext)(void *, void *), 
		    int (*compar)(void *, void *, void *),
		    void *call_data)
{
    void *r, *m;

    /* the lowest item in p/q starts the new list */
    if (compar(p, q, call_data) < 0) {
      m = r = p;
      p = getnext(p);
    }
    else {
      m = r = q;
      q = getnext(q);
    }

    /* merge the rest of p/q */
    while (p && q) {
	if (compar(p, q, call_data) < 0) {
	    setnext(r, p);
	    r = p;
	    p = getnext(p);
	}
	else {
	    setnext(r, q);
	    r = q;
	    q = getnext(q);
	}
    }

    /* tack remainder of p/q onto the end */
    setnext(r, p ? p : q);

    return m;
}

void *lsort(void *p,
	    void *(*getnext)(void *),
	    void (*setnext)(void *, void *), 
	    int (*compar)(void *, void *, void *),
	    void *call_data)
{
    void *q, *r;

    if (p) {
	/* split list in half */
	q = p;
	for (r = getnext(q); r && (r = getnext(r)) != NULL; r = getnext(r))
	    q = getnext(q);
	r = getnext(q);
	setnext(q, NULL);

	/* sort each half recursively and merge the results */
	if (r)
	    p = lmerge(lsort(p, getnext, setnext, compar, call_data),
		       lsort(r, getnext, setnext, compar, call_data),
		       getnext, setnext, compar, call_data);
    }
    return p;
}