#include "lsort.h"
#include <stdlib.h>
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;
if (compar(p, q, call_data) < 0) {
m = r = p;
p = getnext(p);
}
else {
m = r = q;
q = getnext(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);
}
}
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) {
q = p;
for (r = getnext(q); r && (r = getnext(r)) != NULL; r = getnext(r))
q = getnext(q);
r = getnext(q);
setnext(q, NULL);
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;
}