annotate CbC-examples/quicksort/quicksort_cbc.cbc @ 24:f37d7058d1ce

bit modifing.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Thu, 15 Oct 2009 18:47:39 +0900
parents 775dfe898662
children 2476ed92181e
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;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
9 __code (*code)(void*, stack);
22
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. */
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
13 typedef struct {
22
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;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
17 } QS_IF ;
22
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
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
22 /* for check. */
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
23 void *mustbefreed;
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
24
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 __code returner(stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 framep fp = (framep)sp;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 sp += fp->size;
23
775dfe898662 add quicksort version 2.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
29 goto fp->code(fp->interface, sp);
22
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
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 __code quicksort_start(void *arg, stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 {
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
34 QS_IF *recvif = arg;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 int a,b,c,p;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 a = recvif->v[recvif->s];
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 b = recvif->v[recvif->e];
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 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
39
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 //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
41 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
42
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 if (a < b) {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 if (b < c)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 p = b;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 else if (a < c)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 p = c;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 else
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 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 if (a < c)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 p = a;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 else if (b < c)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 p = c;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 else
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 p = b;
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
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 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
60 }
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 /* main routine end. */
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 /* divide routine. */
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
64 __code quicksort_divider(QS_IF *recvif, int s, int e, int p, stack sp)
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 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
67 }
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
68 __code quicksort_divider_s(QS_IF *recvif, int s, int e, int p, stack sp)
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 if (recvif->v[s]<p) {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 s++;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 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
73 } else
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 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
75 }
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
76 __code quicksort_divider_e(QS_IF *recvif, int s, int e, int p, stack sp)
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 if (p<recvif->v[e]) {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 e--;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 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
81 } else
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 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
83 }
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
84 __code quicksort_swapper(QS_IF *recvif, int s, int e, int p, stack sp)
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 if (s<e) {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 int tmp;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 tmp = recvif->v[s];
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 recvif->v[s] = recvif->v[e];
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 recvif->v[e] = tmp;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 s++;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 e--;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 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
94 } else {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 assert(e+1==s || s==e);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 goto quicksort_treecall(recvif, s, e, sp);
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 /* divide routin end. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
100
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 /* recursive call routine. */
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
103 __code quicksort_treecall(QS_IF *recvif, int s, int e, stack sp)
22
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 framep fp;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
106 QS_IF *outif;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 /* interface for first quicksort_start this segment directly jump to. */
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
109 outif = (sp-=sizeof(QS_IF));
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 outif->v = recvif->v;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 outif->s = recvif->s;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 outif->e = e;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 fp = (sp-=sizeof(frame));
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 fp->code = quicksort_start;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 fp->interface = recvif;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
116 fp->size = sizeof(frame)+sizeof(QS_IF);
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 /* recvif is used by second quicksort_start. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 recvif->s = e+1;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 goto quicksort_start(outif, sp);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 }
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 /* recursive call routine end. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123
23
775dfe898662 add quicksort version 2.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
124 #define STACK_SIZE 10240
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
125
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
126 typedef struct {
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 __code (*ret)(void*);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 void *ret_arg;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 stack *sp;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
130 } QS_FINISH;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 __code
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 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
133 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 framep fp;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
135 stack sp0, sp;
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
136 sp0 = malloc(STACK_SIZE);
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
137 mustbefreed = sp0;
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
138 sp = sp0 + STACK_SIZE;
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
139 QS_FINISH *finish_if;
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
140 QS_IF *outif;
22
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_finish. */
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
143 finish_if = (sp -= sizeof(QS_FINISH));
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 finish_if->ret = ret;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 finish_if->ret_arg = arg;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
146 finish_if->sp = sp0;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
147
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 /* interface for quicksort_start. */
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
149 outif = (sp -= sizeof(QS_IF));
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 outif->v = v;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 outif->s = s;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 outif->e = e;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 /* frame for quicksort_finish. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 fp = (sp -= sizeof(frame));
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 fp->code = quicksort_finish;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
156 fp->interface = finish_if;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
157 fp->size = sizeof(frame)+sizeof(QS_IF);
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
158
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 goto quicksort_start(outif, sp);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 }
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 __code
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 quicksort_finish(void *arg, stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 {
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
164 QS_FINISH interface = *(QS_FINISH*)arg;
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
165 assert(interface.sp==mustbefreed);
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 free(interface.sp);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 goto interface.ret(interface.ret_arg);
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
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
170
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
171
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 #if 0
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 void
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
174 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
175 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 int p;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 int s=s0, e=e0;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
178 if (e<=s) return;
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 //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
181 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
182
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
183 while (1) {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 while (v[s]<p) s++;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
185 while (p<v[e]) e--;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
186
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 if (!(s<e)) break;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 SWAP(&v[s], &v[e]);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 s++; e--;
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 assert(e+1==s || s==e);
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 quicksort(v, s0, e);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 quicksort(v, e+1, e0);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 return;
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
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
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 * | args |fp|
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 * --------------------
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 * + ↑ -
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 * sp
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 /* code segmentへgotoしたときのstack spの状態
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
207 *
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 * sp が直接さすのは frame 構造体
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 * frame.size:
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 * frame.code: そのcode segmentが終了した時にgotoすべきcode segment.
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
211 * frame.interface: frame.codeへgotoするときのinterface.
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 * このポインタが指すメモリ領域は stack
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 * ただしframe.codeを登録した側で解放すべき。
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
215 * sp+sizeof(frame)が指すのは実行中のcode segmentのinterface(引数)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 * これは実行中のcode segmentがメモリ管理する
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 * 通常はこのcode segmentが終了する際に sp+=frame.size とすればよい
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
218 */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
219 __code caller0(void *arg, stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
220 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 /* interface for caller_finish0. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 double *finish_arg = (sp -= sizeof(double));
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 /* arg for quicksort_start. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 outif = (sp -= sizeof(*outif));
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
226 framep fp = (sp -= sizeof(frame));
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
227 fp->code = caller_finish;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 fp->interface = NULL;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
229 fp->size = sizeof(*outif)+sizeof(frame);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
230
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
231 goto quicksort_start(outif, sp);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 }
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
233 __code caller_finish0(void *arg, stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
234 {
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 __code __returner0(void *arg , stack sp)
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 framep fp = sp;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
240 sp += fp->size;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 goto fp->code(fp->interface, sp);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
242 }
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
243
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
244 #endif
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
245
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
246
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
247
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
248