annotate CbC-examples/quicksort/quicksort_cbc.cbc @ 22:0eb6cac880f0

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