Mercurial > hg > CbC > CbC_gcc
annotate CbC-examples/quicksort/quicksort_cbc.cbc @ 39:9117c3b65bc3
modify quicksort examples.
author | kent@zeus.cr.ie.u-ryukyu.ac.jp |
---|---|
date | Mon, 25 Jan 2010 16:14:42 +0900 |
parents | 2476ed92181e |
children | 3367c5a7ec79 |
rev | line source |
---|---|
22 | 1 #include<stdio.h> |
2 #include<stdlib.h> | |
3 #include<assert.h> | |
4 | |
5 typedef void *stack; | |
6 typedef struct { | |
7 int size; | |
8 void *interface; | |
39 | 9 __code (*ret)(void*, stack) ; |
22 | 10 } frame, *framep; |
11 | |
12 /* quickstart main routine. */ | |
24 | 13 typedef struct { |
22 | 14 int *v; |
15 int s; | |
16 int e; | |
24 | 17 } QS_IF ; |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
18 typedef __code (*RET)(void*); |
22 | 19 |
20 #include"quicksort_cbc.h" | |
21 | |
24 | 22 /* for check. */ |
23 void *mustbefreed; | |
24 | |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
25 __code returner(stack sp) |
22 | 26 { |
27 framep fp = (framep)sp; | |
28 sp += fp->size; | |
39 | 29 goto fp->ret(fp->interface, sp); |
22 | 30 } |
31 | |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
32 __code quicksort_start(void *arg, stack sp) |
22 | 33 { |
24 | 34 QS_IF *recvif = arg; |
22 | 35 int a,b,c,p; |
36 a = recvif->v[recvif->s]; | |
37 b = recvif->v[recvif->e]; | |
38 c = recvif->v[(recvif->s+recvif->e)/2]; | |
39 | |
40 //printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e); | |
41 if (recvif->e <= recvif->s) goto returner(sp); | |
42 | |
43 if (a < b) { | |
44 if (b < c) | |
45 p = b; | |
46 else if (a < c) | |
47 p = c; | |
48 else | |
49 p = a; | |
50 } else { | |
51 if (a < c) | |
52 p = a; | |
53 else if (b < c) | |
54 p = c; | |
55 else | |
56 p = b; | |
57 } | |
58 | |
59 goto quicksort_divider (recvif, recvif->s, recvif->e, p, sp); | |
60 } | |
61 /* main routine end. */ | |
62 | |
63 /* divide routine. */ | |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
64 __code quicksort_divider(QS_IF *recvif, int s, int e, int p, stack sp) |
22 | 65 { |
66 goto quicksort_divider_s(recvif, s, e, p, sp); | |
67 } | |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
68 __code quicksort_divider_s(QS_IF *recvif, int s, int e, int p, stack sp) |
22 | 69 { |
70 if (recvif->v[s]<p) { | |
71 s++; | |
72 goto quicksort_divider_s(recvif, s, e, p, sp); | |
73 } else | |
74 goto quicksort_divider_e(recvif, s, e, p, sp); | |
75 } | |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
76 __code quicksort_divider_e(QS_IF *recvif, int s, int e, int p, stack sp) |
22 | 77 { |
78 if (p<recvif->v[e]) { | |
79 e--; | |
80 goto quicksort_divider_e(recvif, s, e, p, sp); | |
81 } else | |
82 goto quicksort_swapper(recvif, s, e, p, sp); | |
83 } | |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
84 __code quicksort_swapper(QS_IF *recvif, int s, int e, int p, stack sp) |
22 | 85 { |
86 if (s<e) { | |
87 int tmp; | |
88 tmp = recvif->v[s]; | |
89 recvif->v[s] = recvif->v[e]; | |
90 recvif->v[e] = tmp; | |
39 | 91 //s++; |
92 //e--; | |
93 goto quicksort_divider(recvif, s+1, e-1, p, sp); | |
22 | 94 } else { |
95 goto quicksort_treecall(recvif, s, e, sp); | |
96 } | |
97 } | |
98 /* divide routin end. */ | |
99 | |
100 | |
101 /* recursive call routine. */ | |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
102 __code quicksort_treecall(QS_IF *recvif, int s, int e, stack sp) |
22 | 103 { |
104 framep fp; | |
24 | 105 QS_IF *outif; |
22 | 106 |
107 /* interface for first quicksort_start this segment directly jump to. */ | |
24 | 108 outif = (sp-=sizeof(QS_IF)); |
22 | 109 outif->v = recvif->v; |
110 outif->s = recvif->s; | |
111 outif->e = e; | |
112 fp = (sp-=sizeof(frame)); | |
39 | 113 fp->ret = quicksort_start; |
22 | 114 fp->interface = recvif; |
24 | 115 fp->size = sizeof(frame)+sizeof(QS_IF); |
22 | 116 |
117 /* recvif is used by second quicksort_start. */ | |
118 recvif->s = e+1; | |
119 goto quicksort_start(outif, sp); | |
120 } | |
121 /* recursive call routine end. */ | |
122 | |
23 | 123 #define STACK_SIZE 10240 |
22 | 124 |
24 | 125 typedef struct { |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
126 __code (*ret)(void*); |
22 | 127 void *ret_arg; |
128 stack *sp; | |
24 | 129 } QS_FINISH; |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
130 __code |
22 | 131 quicksort(int *v, int s, int e, RET ret, void *arg ) |
132 { | |
133 framep fp; | |
24 | 134 stack sp0, sp; |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
135 sp0 = mustbefreed = malloc(STACK_SIZE); |
24 | 136 sp = sp0 + STACK_SIZE; |
137 QS_FINISH *finish_if; | |
138 QS_IF *outif; | |
22 | 139 |
140 /* interface for quicksort_finish. */ | |
24 | 141 finish_if = (sp -= sizeof(QS_FINISH)); |
22 | 142 finish_if->ret = ret; |
143 finish_if->ret_arg = arg; | |
24 | 144 finish_if->sp = sp0; |
22 | 145 |
146 /* interface for quicksort_start. */ | |
24 | 147 outif = (sp -= sizeof(QS_IF)); |
22 | 148 outif->v = v; |
149 outif->s = s; | |
150 outif->e = e; | |
151 /* frame for quicksort_finish. */ | |
152 fp = (sp -= sizeof(frame)); | |
39 | 153 fp->ret = quicksort_finish; |
22 | 154 fp->interface = finish_if; |
24 | 155 fp->size = sizeof(frame)+sizeof(QS_IF); |
22 | 156 |
157 goto quicksort_start(outif, sp); | |
158 } | |
25
2476ed92181e
modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
24
diff
changeset
|
159 __code |
22 | 160 quicksort_finish(void *arg, stack sp) |
161 { | |
39 | 162 QS_FINISH interface; |
163 interface = *(QS_FINISH*)arg; | |
164 //assert((void*)interface.sp==(void*)mustbefreed); | |
22 | 165 free(interface.sp); |
166 goto interface.ret(interface.ret_arg); | |
167 } | |
168 | |
169 | |
170 | |
171 #if 0 | |
172 void | |
173 quicksort_c(int *v, int s0, int e0, stack sp) | |
174 { | |
175 int p; | |
176 int s=s0, e=e0; | |
177 if (e<=s) return; | |
178 | |
179 //p = (v[s]+v[(s+e)/2]+v[e])/3; | |
180 p = mid_point(v[s],v[e],v[(s+e)/2]); | |
181 | |
182 while (1) { | |
183 while (v[s]<p) s++; | |
184 while (p<v[e]) e--; | |
185 | |
186 if (!(s<e)) break; | |
187 SWAP(&v[s], &v[e]); | |
188 s++; e--; | |
189 } | |
190 assert(e+1==s || s==e); | |
191 | |
192 quicksort(v, s0, e); | |
193 quicksort(v, e+1, e0); | |
194 return; | |
195 } | |
196 | |
197 | |
198 | |
199 /* -------------------- | |
200 * | args |fp| | |
201 * -------------------- | |
202 * + ↑ - | |
203 * sp | |
204 */ | |
39 | 205 /* ret segmentへgotoしたときのstack spの状態 |
22 | 206 * |
207 * sp が直接さすのは frame 構造体 | |
208 * frame.size: | |
39 | 209 * frame.ret: そのret segmentが終了した時にgotoすべきret segment. |
210 * frame.interface: frame.retへgotoするときのinterface. | |
22 | 211 * このポインタが指すメモリ領域は stack |
212 * 中にあっても良いしなくても良い。 | |
39 | 213 * ただしframe.retを登録した側で解放すべき。 |
214 * sp+sizeof(frame)が指すのは実行中のret segmentのinterface(引数) | |
215 * これは実行中のret segmentがメモリ管理する | |
216 * 通常はこのret segmentが終了する際に sp+=frame.size とすればよい | |
22 | 217 */ |
218 __code caller0(void *arg, stack sp) | |
219 { | |
220 /* interface for caller_finish0. */ | |
221 double *finish_arg = (sp -= sizeof(double)); | |
222 | |
223 /* arg for quicksort_start. */ | |
224 outif = (sp -= sizeof(*outif)); | |
225 framep fp = (sp -= sizeof(frame)); | |
39 | 226 fp->ret = caller_finish; |
22 | 227 fp->interface = NULL; |
228 fp->size = sizeof(*outif)+sizeof(frame); | |
229 | |
230 goto quicksort_start(outif, sp); | |
231 } | |
232 __code caller_finish0(void *arg, stack sp) | |
233 { | |
234 } | |
235 | |
236 __code __returner0(void *arg , stack sp) | |
237 { | |
238 framep fp = sp; | |
239 sp += fp->size; | |
39 | 240 goto fp->ret(fp->interface, sp); |
22 | 241 } |
242 | |
243 #endif | |
244 | |
245 | |
246 | |
247 |