Mercurial > hg > CbC > CbC_gcc

comparison CbC-examples/quicksort/quicksort_cbc2.cbc @ 23:775dfe898662

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
22:0eb6cac880f0 23:775dfe898662
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<assert.h>
4
5 typedef struct {
6 int *v;
7 int s;
8 int e;
9 } QS_IF;
10
11 typedef void *stack;
12 typedef __code (*RET)(QS_IF, stack);
13 typedef struct {
14 int size;
15 QS_IF interface;
16 RET code;
17 } frame, *framep;
18
19 typedef __code (*RETTYPE)(void*);
20 typedef struct {
21 RETTYPE ret;
22 void *ret_arg;
23 stack *sp;
24 } QS_FINISH;
25 #define STACK_SIZE 10240
26
27 #include"quicksort_cbc2.h"
28
29 __code returner(stack sp)
30 {
31 framep fp = (framep)sp;
32 sp += fp->size;
33 goto fp->code(fp->interface, sp);
34 }
35
36 __code quicksort_start(QS_IF recvif, stack sp)
37 {
38 int a,b,c,p;
39 a = recvif.v[recvif.s];
40 b = recvif.v[recvif.e];
41 c = recvif.v[(recvif.s+recvif.e)/2];
42
43 //printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e);
44 if (recvif.e <= recvif.s) goto returner(sp);
45
46 if (a < b) {
47 if (b < c)
48 p = b;
49 else if (a < c)
50 p = c;
51 else
52 p = a;
53 } else {
54 if (a < c)
55 p = a;
56 else if (b < c)
57 p = c;
58 else
59 p = b;
60 }
61
62 goto quicksort_divider (recvif, recvif.s, recvif.e, p, sp);
63 }
64 /* main routine end. */
65
66 /* divide routine. */
67 __code quicksort_divider(QS_IF recvif, int s, int e, int p, stack sp)
68 {
69 goto quicksort_divider_s(recvif, s, e, p, sp);
70 }
71 __code quicksort_divider_s(QS_IF recvif, int s, int e, int p, stack sp)
72 {
73 if (recvif.v[s]<p) {
74 s++;
75 goto quicksort_divider_s(recvif, s, e, p, sp);
76 } else
77 goto quicksort_divider_e(recvif, s, e, p, sp);
78 }
79 __code quicksort_divider_e(QS_IF recvif, int s, int e, int p, stack sp)
80 {
81 if (p<recvif.v[e]) {
82 e--;
83 goto quicksort_divider_e(recvif, s, e, p, sp);
84 } else
85 goto quicksort_swapper(recvif, s, e, p, sp);
86 }
87 __code quicksort_swapper(QS_IF recvif, int s, int e, int p, stack sp)
88 {
89 if (s<e) {
90 int tmp;
91 tmp = recvif.v[s];
92 recvif.v[s] = recvif.v[e];
93 recvif.v[e] = tmp;
94 s++;
95 e--;
96 goto quicksort_divider(recvif, s, e, p, sp);
97 } else {
98 assert(e+1==s || s==e);
99 goto quicksort_treecall(recvif, s, e, sp);
100 }
101 }
102 /* divide routin end. */
103
104
105 /* recursive call routine. */
106 __code quicksort_treecall(QS_IF recvif, int s, int e, stack sp)
107 {
108 framep fp;
109
110 /* interface for first quicksort_start this segment directly jump to. */
111 fp = (sp-=sizeof(frame));
112 fp->code = quicksort_start;
113 fp->size = sizeof(frame);
114 fp->interface.v = recvif.v;
115 fp->interface.s = e+1;
116 fp->interface.e = recvif.e;
117
118 /* recvif is used by second quicksort_start. */
119 recvif.e = e;
120 goto quicksort_start(recvif, sp);
121 }
122 /* recursive call routine end. */
123
124 __code
125 quicksort(int *v, int s, int e, RETTYPE ret, void *arg )
126 {
127 framep fp;
128 stack sp0, sp;
129 sp0 = malloc(STACK_SIZE);
130 printf("allocate a stack %p\n", sp0);
131 sp = sp0 + STACK_SIZE;
132 QS_FINISH *finish_if;
133
134 /* interface for quicksort_finish. */
135 finish_if = (sp -= sizeof(*finish_if));
136 finish_if->ret = ret;
137 finish_if->ret_arg = arg;
138 finish_if->sp = sp0;
139
140 /* interface for quicksort_start. */
141 /* frame for quicksort_finish. */
142 fp = (sp -= sizeof(frame));
143 fp->code = quicksort_finish;
144 fp->size = sizeof(frame);
145 fp->interface.v = v;
146 fp->interface.s = s;
147 fp->interface.e = e;
148
149 goto quicksort_start(fp->interface, sp);
150 }
151 __code
152 quicksort_finish(QS_IF recvif, stack sp)
153 {
154 QS_FINISH *interface = (QS_FINISH*)sp;
155 free(interface->sp);
156 printf("free the stack %p\n", interface->sp);
157 goto interface->ret(interface->ret_arg);
158 }
159