Mercurial > hg > CbC > CbC_gcc
diff CbC-examples/quicksort/quicksort_cbc2.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 | |
children | 9117c3b65bc3 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/CbC-examples/quicksort/quicksort_cbc2.cbc Wed Oct 14 12:12:51 2009 +0900 @@ -0,0 +1,159 @@ +#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 code; +} 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->code(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->code = 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->code = 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); +} +