#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef struct {
	int *v;
	int s;
	int e;
} QS_IF;

typedef void *stack;
typedef __code (*RET)(QS_IF, stack);
typedef struct {
	int size;
	QS_IF interface;
	RET ret;
} frame, *framep;

typedef __code (*RETTYPE)(void*);
typedef struct {
	RETTYPE ret;
	void *ret_arg;
	stack *sp;
} QS_FINISH;
#define STACK_SIZE 10240

#include"quicksort_cbc2.h"

__code returner(stack sp)
{
	framep fp = (framep)sp;
	sp += fp->size;
	goto fp->ret(fp->interface, sp);
}

__code quicksort_start(QS_IF recvif, stack sp)
{
	int a,b,c,p;
	a = recvif.v[recvif.s];
	b = recvif.v[recvif.e];
	c = recvif.v[(recvif.s+recvif.e)/2];

	//printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e);
	if (recvif.e <= recvif.s) goto returner(sp);

	if (a < b) {
		if (b < c)
			p = b;
		else if (a < c)
			p = c;
		else 
			p = a;
	} else {
		if (a < c)
			p = a;
		else if (b < c)
			p = c;
		else 
			p = b;
	}

	goto quicksort_divider (recvif, recvif.s, recvif.e, p, sp);
}
/* main routine end. */

/* divide routine. */
__code quicksort_divider(QS_IF recvif, int s, int e, int p, stack sp)
{
	goto quicksort_divider_s(recvif, s, e, p, sp);
}
__code quicksort_divider_s(QS_IF recvif, int s, int e, int p, stack sp)
{
	if (recvif.v[s]<p) {
		s++;
		goto quicksort_divider_s(recvif, s, e, p, sp);
	} else
		goto quicksort_divider_e(recvif, s, e, p, sp);
}
__code quicksort_divider_e(QS_IF recvif, int s, int e, int p, stack sp)
{
	if (p<recvif.v[e]) {
		e--;
		goto quicksort_divider_e(recvif, s, e, p, sp);
	} else
		goto quicksort_swapper(recvif, s, e, p, sp);
}
__code quicksort_swapper(QS_IF recvif, int s, int e, int p, stack sp)
{
	if (s<e) {
		int tmp;
		tmp = recvif.v[s];
		recvif.v[s] = recvif.v[e];
		recvif.v[e] = tmp;
		s++;
		e--;
		goto quicksort_divider(recvif, s, e, p, sp);
	} else {
		//assert(e+1==s || s==e);
		goto quicksort_treecall(recvif, s, e, sp);
	}
}
/* divide routin end. */


/* recursive call routine. */
__code quicksort_treecall(QS_IF recvif, int s, int e, stack sp)
{
	framep fp;

	/* interface for first quicksort_start this segment directly jump to.  */
	fp = (sp-=sizeof(frame));
	fp->ret = quicksort_start;
	fp->size = sizeof(frame);
	fp->interface.v = recvif.v;
	fp->interface.s = e+1;
	fp->interface.e = recvif.e;

	/* recvif is used by second quicksort_start.  */
	recvif.e = e;
	goto quicksort_start(recvif, sp);
}
/* recursive call routine end. */

__code
quicksort(int *v, int s, int e,  RETTYPE ret, void *arg )
{
	framep fp;
	stack sp0, sp;
	sp0 = malloc(STACK_SIZE);
	printf("allocate a stack %p\n", sp0);
	sp = sp0 + STACK_SIZE;
	QS_FINISH *finish_if;
	
	/* interface for quicksort_finish.  */
	finish_if = (sp -= sizeof(*finish_if));
	finish_if->ret = ret;
	finish_if->ret_arg = arg;
	finish_if->sp = sp0;

	/* interface for quicksort_start.  */
	/* frame for quicksort_finish.  */
	fp = (sp -= sizeof(frame));
	fp->ret = quicksort_finish;
	fp->size = sizeof(frame);
	fp->interface.v = v;
	fp->interface.s = s;
	fp->interface.e = e;

	goto quicksort_start(fp->interface, sp);
}
__code
quicksort_finish(QS_IF recvif, stack sp)
{
	QS_FINISH *interface = (QS_FINISH*)sp;
	free(interface->sp);
	printf("free the stack %p\n", interface->sp);
	goto interface->ret(interface->ret_arg);
}