view CbC-examples/quicksort/quicksort_cbc.cbc @ 23:775dfe898662

add quicksort version 2.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Wed, 14 Oct 2009 12:12:51 +0900
parents 0eb6cac880f0
children f37d7058d1ce
line wrap: on
line source

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

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

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

#include"quicksort_cbc.h"

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

__code quicksort_start(void *arg, stack sp)
{
	struct 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(struct qs_if *recvif, int s, int e, int p, stack sp)
{
	goto quicksort_divider_s(recvif, s, e, p, sp);
}
__code quicksort_divider_s(struct 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(struct 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(struct 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(struct qs_if *recvif, int s, int e, stack sp)
{
	framep fp;
	struct qs_if *outif;

	/* interface for first quicksort_start this segment directly jump to.  */
	outif = (sp-=sizeof(struct 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(struct 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
int v[100];
struct qs_if *outif;

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

	/* interface for quicksort_start.  */
	outif = (sp -= sizeof(*outif));
	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(outif);

	goto quicksort_start(outif, sp);
}
__code
quicksort_finish(void *arg, stack sp)
{
	struct qs interface = *(struct qs*)arg;
	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