#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <alloca.h>
char *sort_name = "Splaysort";
char *sort_version = "$Revision: 1.2 $";
#define DATAPTR
#ifdef DATAPTR
#define DATA(p) ((p)->data)
#else
#define DATA(p) (A+size*(p-T))
#endif
#define FASTCOPY
#ifdef FASTCOPY
#define COPYCODE(TYPE, parmi, parmj, n) { \
long i = (n) / sizeof (TYPE); \
register TYPE *pi = (TYPE *) (parmi); \
register TYPE *pj = (TYPE *) (parmj); \
do { \
*pi++ = *pj++; \
} while (--i > 0); \
}
void
copyfunc(char *d, char *s, int size, int copytype)
{
if(copytype <= 1)
COPYCODE(long, d, s, size)
else
COPYCODE(char, d, s, size)
return;
}
#define COPY(d,s,size) \
if (copytype == 0) { \
*(long *)(d) = *(long *)(s); \
} else \
copyfunc(d, s, size, copytype)
#else
#define COPY(d,s,size) memcpy(d,s,size)
#endif
typedef struct node_rec node;
struct node_rec {
node *left, *rght;
#ifdef DATAPTR
char *data;
#endif
};
void
sort(void *A, size_t n, size_t size, int (*cmp)(const void *, const void *))
{
register node *next, *curr, *prnt;
char *item;
node *l, *r, *ch;
node root, *T, *new, *end, *move;
#ifndef DATAPTR
char *p;
#endif
#ifdef FASTCOPY
int copytype=((char *)A - (char *)0) % sizeof(long) ||
size % sizeof(long) ? 2 : size == sizeof(long) ? 0 : 1;
#endif
if(n < 2)
return;
if((T = new = (node *) malloc(sizeof(*T)*n)) == NULL) {
fprintf(stderr, "Couldn't allocate space for structure\n");
}
curr = new++;
item = A;
curr->left = curr->rght = NULL;
#ifdef DATAPTR
curr->data = item;
#endif
item += size;
end = T+n;
for( ; new<end; ) {
l = r = &root;
while(curr != NULL) {
if(cmp(item, DATA(curr)) < 0) {
if((ch = curr->left) == NULL) {
r = r->left = curr;
break;
}
else if(cmp(item, DATA(ch)) < 0) {
curr->left = ch->rght;
ch->rght = curr;
r = r->left = ch;
curr = ch->left;
}
else {
r = r->left = curr;
l = l->rght = ch;
curr = ch->rght;
}
}
else {
if((ch = curr->rght) == NULL) {
l = l->rght = curr;
break;
}
else if (cmp(item, DATA(ch)) < 0) {
l = l->rght = curr;
r = r->left = ch;
curr = ch->left;
}
else {
curr->rght = ch->left;
ch->left = curr;
l = l->rght = ch;
curr = ch->rght;
}
}
}
r->left = l->rght = NULL;
new->rght = root.left;
new->left = root.rght;
#ifdef DATAPTR
new->data = item;
#endif
curr = new++;
item += size;
}
prnt = NULL;
move = T;
while (1) {
if ((next = curr->left) != NULL) {
curr->left = prnt;
prnt = curr;
curr = next;
}
else {
next = curr->rght;
curr->rght = move++;
if (next != NULL) {
if((curr = next->left) != NULL) {
next->left = prnt;
prnt = next;
continue;
}
else {
curr = next;
continue;
}
}
if (prnt != NULL) {
curr = prnt;
prnt = prnt->left;
curr->left = NULL;
continue;
}
break;
}
}
#ifndef DATAPTR
for(next = T, p = A; next < end; p += size, next++)
next->rght->left = (node *)p;
item = (char *)malloc(size);
for (next=T; next<end; next++) {
char *datacurr, *dataleftcurr, *final;
if (next->left == NULL)
continue;
curr = next;
final = datacurr = DATA(curr);
COPY(item, datacurr, size);
while ((char *)(curr->left) != final) {
dataleftcurr = (char *)(curr->left);
COPY(datacurr, dataleftcurr, size);
prnt = curr;
curr = T + (((char *)(curr->left)-A)/size);
prnt->left = NULL;
datacurr = dataleftcurr;
}
COPY(datacurr, item, size);
curr->left = NULL;
}
#else
for(next = T; next < end; next++)
next->rght->left = next;
item = (char *)malloc(size);
for (next=T; next<end; next++) {
char *datacurr, *dataleftcurr, *final;
if (DATA(next) == (char *) NULL || next->left == next)
continue;
final = datacurr = DATA(next);
curr = next->left;
COPY(item, datacurr, size);
while ((dataleftcurr = DATA(curr)) != final) {
COPY(datacurr, dataleftcurr, size);
prnt = curr;
curr = curr->left;
DATA(prnt) = (char *) NULL;
datacurr = dataleftcurr;
}
COPY(datacurr, item, size);
DATA(curr) = (char *) NULL;
}
#endif
free(item);
free(T);
}