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