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