Mercurial > hg > CbC > CbC_gcc
view CbC-examples/quicksort/quicksort_cbc.cbc @ 24:f37d7058d1ce
bit modifing.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 15 Oct 2009 18:47:39 +0900 |
parents | 775dfe898662 |
children | 2476ed92181e |
line wrap: on
line source
#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