annotate CbC-examples/quicksort/quicksort_cbc.cbc @ 39:9117c3b65bc3

modify quicksort examples.
author kent@zeus.cr.ie.u-ryukyu.ac.jp
date Mon, 25 Jan 2010 16:14:42 +0900
parents 2476ed92181e
children 3367c5a7ec79
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;
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
9 __code (*ret)(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 ;
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
18 typedef __code (*RET)(void*);
22
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
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
25 __code returner(stack sp)
22
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;
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
29 goto fp->ret(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
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
32 __code quicksort_start(void *arg, stack sp)
22
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. */
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
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 }
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
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 }
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
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 }
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
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;
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
91 //s++;
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
92 //e--;
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
93 goto quicksort_divider(recvif, s+1, e-1, p, sp);
22
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 goto quicksort_treecall(recvif, s, e, sp);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 }
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 /* divide routin end. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99
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 /* recursive call routine. */
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
102 __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
103 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 framep fp;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
105 QS_IF *outif;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
106
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 /* 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
108 outif = (sp-=sizeof(QS_IF));
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 outif->v = recvif->v;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 outif->s = recvif->s;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 outif->e = e;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 fp = (sp-=sizeof(frame));
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
113 fp->ret = quicksort_start;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 fp->interface = recvif;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
115 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
116
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 /* recvif is used by second quicksort_start. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 recvif->s = e+1;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 goto quicksort_start(outif, sp);
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 /* recursive call routine end. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122
23
775dfe898662 add quicksort version 2.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
123 #define STACK_SIZE 10240
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
124
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
125 typedef struct {
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
126 __code (*ret)(void*);
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 void *ret_arg;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 stack *sp;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
129 } QS_FINISH;
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
130 __code
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 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
132 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 framep fp;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
134 stack sp0, sp;
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
135 sp0 = mustbefreed = malloc(STACK_SIZE);
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
136 sp = sp0 + STACK_SIZE;
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
137 QS_FINISH *finish_if;
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
138 QS_IF *outif;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
139
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 /* interface for quicksort_finish. */
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
141 finish_if = (sp -= sizeof(QS_FINISH));
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 finish_if->ret = ret;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 finish_if->ret_arg = arg;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
144 finish_if->sp = sp0;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
145
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 /* interface for quicksort_start. */
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
147 outif = (sp -= sizeof(QS_IF));
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 outif->v = v;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 outif->s = s;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 outif->e = e;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 /* frame for quicksort_finish. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 fp = (sp -= sizeof(frame));
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
153 fp->ret = quicksort_finish;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 fp->interface = finish_if;
24
f37d7058d1ce bit modifing.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
155 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
156
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 goto quicksort_start(outif, sp);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 }
25
2476ed92181e modified machine description of i386 for support indirect sibcall attributed fastcall.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
159 __code
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 quicksort_finish(void *arg, stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 {
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
162 QS_FINISH interface;
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
163 interface = *(QS_FINISH*)arg;
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
164 //assert((void*)interface.sp==(void*)mustbefreed);
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
165 free(interface.sp);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 goto interface.ret(interface.ret_arg);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 }
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 #if 0
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 void
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 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
174 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
175 int p;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 int s=s0, e=e0;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 if (e<=s) return;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
178
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 //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
180 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
181
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 while (1) {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
183 while (v[s]<p) s++;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 while (p<v[e]) 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 if (!(s<e)) break;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 SWAP(&v[s], &v[e]);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 s++; e--;
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 assert(e+1==s || s==e);
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 quicksort(v, s0, e);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 quicksort(v, e+1, e0);
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 return;
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
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 * | args |fp|
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 * --------------------
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 * sp
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 */
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
205 /* ret segmentへgotoしたときのstack spの状態
22
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 * sp が直接さすのは frame 構造体
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 * frame.size:
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
209 * frame.ret: そのret segmentが終了した時にgotoすべきret segment.
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
210 * frame.interface: frame.retへgotoするときのinterface.
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
211 * このポインタが指すメモリ領域は stack
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 * 中にあっても良いしなくても良い。
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
213 * ただしframe.retを登録した側で解放すべき。
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
214 * sp+sizeof(frame)が指すのは実行中のret segmentのinterface(引数)
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
215 * これは実行中のret segmentがメモリ管理する
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
216 * 通常はこのret segmentが終了する際に sp+=frame.size とすればよい
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
218 __code caller0(void *arg, stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
219 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
220 /* interface for caller_finish0. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 double *finish_arg = (sp -= sizeof(double));
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
222
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
223 /* arg for quicksort_start. */
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
224 outif = (sp -= sizeof(*outif));
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 framep fp = (sp -= sizeof(frame));
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
226 fp->ret = caller_finish;
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
227 fp->interface = NULL;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 fp->size = sizeof(*outif)+sizeof(frame);
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 goto quicksort_start(outif, 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 __code caller_finish0(void *arg, stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
233 {
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 __code __returner0(void *arg , stack sp)
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
237 {
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
238 framep fp = sp;
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
239 sp += fp->size;
39
9117c3b65bc3 modify quicksort examples.
kent@zeus.cr.ie.u-ryukyu.ac.jp
parents: 25
diff changeset
240 goto fp->ret(fp->interface, sp);
22
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 }
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 #endif
0eb6cac880f0 add cbc example of quicksort.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
244
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