Mercurial > hg > Papers > 2010 > kent-master
view paper/quicksort_for_ppc/mc/quicksort_cbc.cbc @ 10:3d9addf62d0b
organized repository.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 16 Feb 2010 14:35:36 +0900 |
parents | |
children |
line wrap: on
line source
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef void *stack; typedef struct { int size; void *interface; __code (*ret)(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->ret(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) { goto quicksort_divider_s(recvif, s+1, 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; goto quicksort_divider(recvif, s+1, e-1, p, sp); } else { 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->ret = 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 = mustbefreed = malloc(STACK_SIZE); 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->ret = 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; interface = *(QS_FINISH*)arg; //assert((void*)interface.sp==(void*)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 */ /* ret segmentへgotoしたときのstack spの状態 * * sp が直接さすのは frame 構造体 * frame.size: * frame.ret: そのret segmentが終了した時にgotoすべきret segment. * frame.interface: frame.retへgotoするときのinterface. * このポインタが指すメモリ領域は stack * 中にあっても良いしなくても良い。 * ただしframe.retを登録した側で解放すべき。 * sp+sizeof(frame)が指すのは実行中のret segmentのinterface(引数) * これは実行中のret segmentがメモリ管理する * 通常はこのret 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->ret = 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->ret(fp->interface, sp); } #endif