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

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

/* quickstart main routine. */
typedef struct {
	int *v;
	int s;
	int e;
} QS_IF ;
typedef __code (*RET)(void*);

#include"quicksort_cbc.h"

/* for check. */
void *mustbefreed;

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

__code quicksort_start(void *arg, stack sp)
{
	QS_IF *recvif = arg;
	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;
	QS_IF *outif;

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

	/* recvif is used by second quicksort_start.  */
	recvif->s = e+1;
	goto quicksort_start(outif, sp);
}
/* recursive call routine end. */

#define STACK_SIZE 10240

typedef struct {
	__code (*ret)(void*);
	void *ret_arg;
	stack *sp;
} QS_FINISH;
__code
quicksort(int *v, int s, int e,  RET ret, void *arg )
{
	framep fp;
	stack sp0, sp;
	sp0 = malloc(STACK_SIZE);
		mustbefreed = sp0;
	sp = sp0 + STACK_SIZE;
	QS_FINISH *finish_if;
	QS_IF *outif;
	
	/* interface for quicksort_finish.  */
	finish_if = (sp -= sizeof(QS_FINISH));
	finish_if->ret = ret;
	finish_if->ret_arg = arg;
	finish_if->sp = sp0;

	/* interface for quicksort_start.  */
	outif = (sp -= sizeof(QS_IF));
	outif->v = v;
	outif->s = s;
	outif->e = e;
	/* frame for quicksort_finish.  */
	fp = (sp -= sizeof(frame));
	fp->code = quicksort_finish;
	fp->interface = finish_if;
	fp->size = sizeof(frame)+sizeof(QS_IF);

	goto quicksort_start(outif, sp);
}
__code
quicksort_finish(void *arg, stack sp)
{
	QS_FINISH interface = *(QS_FINISH*)arg;
	assert(interface.sp==mustbefreed);
	free(interface.sp);
	goto interface.ret(interface.ret_arg);
}



#if 0
void
quicksort_c(int *v, int s0, int e0, stack sp)
{
	int p;
	int s=s0, e=e0;
	if (e<=s) return;

	//p = (v[s]+v[(s+e)/2]+v[e])/3;
	p = mid_point(v[s],v[e],v[(s+e)/2]);

	while (1) {
		 while (v[s]<p) s++;
		 while (p<v[e]) e--;

		 if (!(s<e)) break;
		 SWAP(&v[s], &v[e]);
		 s++; e--;
	}
	assert(e+1==s || s==e);

	quicksort(v, s0, e);
	quicksort(v, e+1, e0);
	return;
}



/*  --------------------
 *     | args |fp| 
 *  --------------------
 *  +            ↑     -
 *               sp
 */ 
/* code segmentへgotoしたときのstack spの状態
 *
 * sp が直接さすのは frame 構造体
 * frame.size:
 * frame.code: そのcode segmentが終了した時にgotoすべきcode segment.
 * frame.interface: frame.codeへgotoするときのinterface.
 *                  このポインタが指すメモリ領域は stack
 *                  中にあっても良いしなくても良い。
 *                  ただしframe.codeを登録した側で解放すべき。
 * sp+sizeof(frame)が指すのは実行中のcode segmentのinterface(引数)
 * これは実行中のcode segmentがメモリ管理する
 * 通常はこのcode segmentが終了する際に sp+=frame.size とすればよい
 */
__code caller0(void *arg, stack sp)
{
	/* interface for caller_finish0.  */
	double *finish_arg = (sp -= sizeof(double));

	/* arg for quicksort_start.  */
	outif = (sp -= sizeof(*outif));
	framep fp = (sp -= sizeof(frame));
	fp->code = caller_finish;
	fp->interface = NULL;
	fp->size = sizeof(*outif)+sizeof(frame);

	goto quicksort_start(outif, sp);
}
__code caller_finish0(void *arg, stack sp)
{
}

__code __returner0(void *arg , stack sp)
{
	framep fp = sp;
	sp += fp->size;
	goto fp->code(fp->interface, sp);
}

#endif