Mercurial > hg > Papers > 2010 > kent-master

comparison quicksort_for_ppc/mc/quicksort_cbc.cbc @ 1:aa09c34b90d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add quicksort_for_pcc add sources, figures.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Mon, 01 Feb 2010 20:37:36 +0900
parents
children
comparison
equal deleted inserted replaced
0:e9ecd5b5f29a 1:aa09c34b90d3
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;
9 __code (*ret)(void*, stack) ;
10 } frame, *framep;
11
12 /* quickstart main routine. */
13 typedef struct {
14 int *v;
15 int s;
16 int e;
17 } QS_IF ;
18 typedef __code (*RET)(void*);
19
20 #include"quicksort_cbc.h"
21
22 /* for check. */
23 void *mustbefreed;
24
25 __code returner(stack sp)
26 {
27 framep fp = (framep)sp;
28 sp += fp->size;
29 goto fp->ret(fp->interface, sp);
30 }
31
32 __code quicksort_start(void *arg, stack sp)
33 {
34 QS_IF *recvif = arg;
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. */
64 __code quicksort_divider(QS_IF *recvif, int s, int e, int p, stack sp)
65 {
66 goto quicksort_divider_s(recvif, s, e, p, sp);
67 }
68 __code quicksort_divider_s(QS_IF *recvif, int s, int e, int p, stack sp)
69 {
70 if (recvif->v[s]<p) {
71 goto quicksort_divider_s(recvif, s+1, e, p, sp);
72 } else
73 goto quicksort_divider_e(recvif, s, e, p, sp);
74 }
75 __code quicksort_divider_e(QS_IF *recvif, int s, int e, int p, stack sp)
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 }
83 __code quicksort_swapper(QS_IF *recvif, int s, int e, int p, stack sp)
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;
90 goto quicksort_divider(recvif, s+1, e-1, p, sp);
91 } else {
92 goto quicksort_treecall(recvif, s, e, sp);
93 }
94 }
95 /* divide routin end. */
96
97
98 /* recursive call routine. */
99 __code quicksort_treecall(QS_IF *recvif, int s, int e, stack sp)
100 {
101 framep fp;
102 QS_IF *outif;
103
104 /* interface for first quicksort_start this segment directly jump to. */
105 outif = (sp-=sizeof(QS_IF));
106 outif->v = recvif->v;
107 outif->s = recvif->s;
108 outif->e = e;
109 fp = (sp-=sizeof(frame));
110 fp->ret = quicksort_start;
111 fp->interface = recvif;
112 fp->size = sizeof(frame)+sizeof(QS_IF);
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
120 #define STACK_SIZE 10240
121
122 typedef struct {
123 __code (*ret)(void*);
124 void *ret_arg;
125 stack *sp;
126 } QS_FINISH;
127 __code
128 quicksort(int *v, int s, int e, RET ret, void *arg )
129 {
130 framep fp;
131 stack sp0, sp;
132 sp0 = mustbefreed = malloc(STACK_SIZE);
133 sp = sp0 + STACK_SIZE;
134 QS_FINISH *finish_if;
135 QS_IF *outif;
136
137 /* interface for quicksort_finish. */
138 finish_if = (sp -= sizeof(QS_FINISH));
139 finish_if->ret = ret;
140 finish_if->ret_arg = arg;
141 finish_if->sp = sp0;
142
143 /* interface for quicksort_start. */
144 outif = (sp -= sizeof(QS_IF));
145 outif->v = v;
146 outif->s = s;
147 outif->e = e;
148 /* frame for quicksort_finish. */
149 fp = (sp -= sizeof(frame));
150 fp->ret = quicksort_finish;
151 fp->interface = finish_if;
152 fp->size = sizeof(frame)+sizeof(QS_IF);
153
154 goto quicksort_start(outif, sp);
155 }
156 __code
157 quicksort_finish(void *arg, stack sp)
158 {
159 QS_FINISH interface;
160 interface = *(QS_FINISH*)arg;
161 //assert((void*)interface.sp==(void*)mustbefreed);
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 */
202 /* ret segmentへgotoしたときのstack spの状態
203 *
204 * sp が直接さすのは frame 構造体
205 * frame.size:
206 * frame.ret: そのret segmentが終了した時にgotoすべきret segment.
207 * frame.interface: frame.retへgotoするときのinterface.
208 * このポインタが指すメモリ領域は stack
209 * 中にあっても良いしなくても良い。
210 * ただしframe.retを登録した側で解放すべき。
211 * sp+sizeof(frame)が指すのは実行中のret segmentのinterface(引数)
212 * これは実行中のret segmentがメモリ管理する
213 * 通常はこのret segmentが終了する際に sp+=frame.size とすればよい
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));
223 fp->ret = caller_finish;
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;
237 goto fp->ret(fp->interface, sp);
238 }
239
240 #endif
241
242
243
244