Mercurial > hg > CbC > CbC_gcc
annotate CbC-examples/quicksort/quicksort_cbc.cbc @ 40:3367c5a7ec79
modify quicksort for benchmark.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 25 Jan 2010 16:51:28 +0900 |
parents | 9117c3b65bc3 |
children |
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) { | |
40
3367c5a7ec79
modify quicksort for benchmark.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
71 goto quicksort_divider_s(recvif, s+1, e, p, sp); |
22 | 72 } else |
73 goto quicksort_divider_e(recvif, s, e, p, sp); | |
74 } | |
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
|
75 __code quicksort_divider_e(QS_IF *recvif, int s, int e, int p, stack sp) |
22 | 76 { |
77 if (p<recvif->v[e]) { | |
78 e--; | |
79 goto quicksort_divider_e(recvif, s, e, p, sp); | |
80 } else | |
81 goto quicksort_swapper(recvif, s, e, p, sp); | |
82 } | |
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
|
83 __code quicksort_swapper(QS_IF *recvif, int s, int e, int p, stack sp) |
22 | 84 { |
85 if (s<e) { | |
86 int tmp; | |
87 tmp = recvif->v[s]; | |
88 recvif->v[s] = recvif->v[e]; | |
89 recvif->v[e] = tmp; | |
39 | 90 goto quicksort_divider(recvif, s+1, e-1, p, sp); |
22 | 91 } else { |
92 goto quicksort_treecall(recvif, s, e, sp); | |
93 } | |
94 } | |
95 /* divide routin end. */ | |
96 | |
97 | |
98 /* 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
|
99 __code quicksort_treecall(QS_IF *recvif, int s, int e, stack sp) |
22 | 100 { |
101 framep fp; | |
24 | 102 QS_IF *outif; |
22 | 103 |
104 /* interface for first quicksort_start this segment directly jump to. */ | |
24 | 105 outif = (sp-=sizeof(QS_IF)); |
22 | 106 outif->v = recvif->v; |
107 outif->s = recvif->s; | |
108 outif->e = e; | |
109 fp = (sp-=sizeof(frame)); | |
39 | 110 fp->ret = quicksort_start; |
22 | 111 fp->interface = recvif; |
24 | 112 fp->size = sizeof(frame)+sizeof(QS_IF); |
22 | 113 |
114 /* recvif is used by second quicksort_start. */ | |
115 recvif->s = e+1; | |
116 goto quicksort_start(outif, sp); | |
117 } | |
118 /* recursive call routine end. */ | |
119 | |
23 | 120 #define STACK_SIZE 10240 |
22 | 121 |
24 | 122 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
|
123 __code (*ret)(void*); |
22 | 124 void *ret_arg; |
125 stack *sp; | |
24 | 126 } 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
|
127 __code |
22 | 128 quicksort(int *v, int s, int e, RET ret, void *arg ) |
129 { | |
130 framep fp; | |
24 | 131 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
|
132 sp0 = mustbefreed = malloc(STACK_SIZE); |
24 | 133 sp = sp0 + STACK_SIZE; |
134 QS_FINISH *finish_if; | |
135 QS_IF *outif; | |
22 | 136 |
137 /* interface for quicksort_finish. */ | |
24 | 138 finish_if = (sp -= sizeof(QS_FINISH)); |
22 | 139 finish_if->ret = ret; |
140 finish_if->ret_arg = arg; | |
24 | 141 finish_if->sp = sp0; |
22 | 142 |
143 /* interface for quicksort_start. */ | |
24 | 144 outif = (sp -= sizeof(QS_IF)); |
22 | 145 outif->v = v; |
146 outif->s = s; | |
147 outif->e = e; | |
148 /* frame for quicksort_finish. */ | |
149 fp = (sp -= sizeof(frame)); | |
39 | 150 fp->ret = quicksort_finish; |
22 | 151 fp->interface = finish_if; |
24 | 152 fp->size = sizeof(frame)+sizeof(QS_IF); |
22 | 153 |
154 goto quicksort_start(outif, sp); | |
155 } | |
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
|
156 __code |
22 | 157 quicksort_finish(void *arg, stack sp) |
158 { | |
39 | 159 QS_FINISH interface; |
160 interface = *(QS_FINISH*)arg; | |
161 //assert((void*)interface.sp==(void*)mustbefreed); | |
22 | 162 free(interface.sp); |
163 goto interface.ret(interface.ret_arg); | |
164 } | |
165 | |
166 | |
167 | |
168 #if 0 | |
169 void | |
170 quicksort_c(int *v, int s0, int e0, stack sp) | |
171 { | |
172 int p; | |
173 int s=s0, e=e0; | |
174 if (e<=s) return; | |
175 | |
176 //p = (v[s]+v[(s+e)/2]+v[e])/3; | |
177 p = mid_point(v[s],v[e],v[(s+e)/2]); | |
178 | |
179 while (1) { | |
180 while (v[s]<p) s++; | |
181 while (p<v[e]) e--; | |
182 | |
183 if (!(s<e)) break; | |
184 SWAP(&v[s], &v[e]); | |
185 s++; e--; | |
186 } | |
187 assert(e+1==s || s==e); | |
188 | |
189 quicksort(v, s0, e); | |
190 quicksort(v, e+1, e0); | |
191 return; | |
192 } | |
193 | |
194 | |
195 | |
196 /* -------------------- | |
197 * | args |fp| | |
198 * -------------------- | |
199 * + ↑ - | |
200 * sp | |
201 */ | |
39 | 202 /* ret segmentへgotoしたときのstack spの状態 |
22 | 203 * |
204 * sp が直接さすのは frame 構造体 | |
205 * frame.size: | |
39 | 206 * frame.ret: そのret segmentが終了した時にgotoすべきret segment. |
207 * frame.interface: frame.retへgotoするときのinterface. | |
22 | 208 * このポインタが指すメモリ領域は stack |
209 * 中にあっても良いしなくても良い。 | |
39 | 210 * ただしframe.retを登録した側で解放すべき。 |
211 * sp+sizeof(frame)が指すのは実行中のret segmentのinterface(引数) | |
212 * これは実行中のret segmentがメモリ管理する | |
213 * 通常はこのret segmentが終了する際に sp+=frame.size とすればよい | |
22 | 214 */ |
215 __code caller0(void *arg, stack sp) | |
216 { | |
217 /* interface for caller_finish0. */ | |
218 double *finish_arg = (sp -= sizeof(double)); | |
219 | |
220 /* arg for quicksort_start. */ | |
221 outif = (sp -= sizeof(*outif)); | |
222 framep fp = (sp -= sizeof(frame)); | |
39 | 223 fp->ret = caller_finish; |
22 | 224 fp->interface = NULL; |
225 fp->size = sizeof(*outif)+sizeof(frame); | |
226 | |
227 goto quicksort_start(outif, sp); | |
228 } | |
229 __code caller_finish0(void *arg, stack sp) | |
230 { | |
231 } | |
232 | |
233 __code __returner0(void *arg , stack sp) | |
234 { | |
235 framep fp = sp; | |
236 sp += fp->size; | |
39 | 237 goto fp->ret(fp->interface, sp); |
22 | 238 } |
239 | |
240 #endif | |
241 | |
242 | |
243 | |
244 |