|
23
|
1 #include<stdio.h>
|
|
|
2 #include<stdlib.h>
|
|
|
3 #include<assert.h>
|
|
|
4
|
|
|
5 typedef struct {
|
|
|
6 int *v;
|
|
|
7 int s;
|
|
|
8 int e;
|
|
|
9 } QS_IF;
|
|
|
10
|
|
|
11 typedef void *stack;
|
|
|
12 typedef __code (*RET)(QS_IF, stack);
|
|
|
13 typedef struct {
|
|
|
14 int size;
|
|
|
15 QS_IF interface;
|
|
39
|
16 RET ret;
|
|
23
|
17 } frame, *framep;
|
|
|
18
|
|
|
19 typedef __code (*RETTYPE)(void*);
|
|
|
20 typedef struct {
|
|
|
21 RETTYPE ret;
|
|
|
22 void *ret_arg;
|
|
|
23 stack *sp;
|
|
|
24 } QS_FINISH;
|
|
|
25 #define STACK_SIZE 10240
|
|
|
26
|
|
|
27 #include"quicksort_cbc2.h"
|
|
|
28
|
|
|
29 __code returner(stack sp)
|
|
|
30 {
|
|
|
31 framep fp = (framep)sp;
|
|
|
32 sp += fp->size;
|
|
39
|
33 goto fp->ret(fp->interface, sp);
|
|
23
|
34 }
|
|
|
35
|
|
|
36 __code quicksort_start(QS_IF recvif, stack sp)
|
|
|
37 {
|
|
|
38 int a,b,c,p;
|
|
|
39 a = recvif.v[recvif.s];
|
|
|
40 b = recvif.v[recvif.e];
|
|
|
41 c = recvif.v[(recvif.s+recvif.e)/2];
|
|
|
42
|
|
|
43 //printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e);
|
|
|
44 if (recvif.e <= recvif.s) goto returner(sp);
|
|
|
45
|
|
|
46 if (a < b) {
|
|
|
47 if (b < c)
|
|
|
48 p = b;
|
|
|
49 else if (a < c)
|
|
|
50 p = c;
|
|
|
51 else
|
|
|
52 p = a;
|
|
|
53 } else {
|
|
|
54 if (a < c)
|
|
|
55 p = a;
|
|
|
56 else if (b < c)
|
|
|
57 p = c;
|
|
|
58 else
|
|
|
59 p = b;
|
|
|
60 }
|
|
|
61
|
|
|
62 goto quicksort_divider (recvif, recvif.s, recvif.e, p, sp);
|
|
|
63 }
|
|
|
64 /* main routine end. */
|
|
|
65
|
|
|
66 /* divide routine. */
|
|
|
67 __code quicksort_divider(QS_IF recvif, int s, int e, int p, stack sp)
|
|
|
68 {
|
|
|
69 goto quicksort_divider_s(recvif, s, e, p, sp);
|
|
|
70 }
|
|
|
71 __code quicksort_divider_s(QS_IF recvif, int s, int e, int p, stack sp)
|
|
|
72 {
|
|
|
73 if (recvif.v[s]<p) {
|
|
|
74 s++;
|
|
|
75 goto quicksort_divider_s(recvif, s, e, p, sp);
|
|
|
76 } else
|
|
|
77 goto quicksort_divider_e(recvif, s, e, p, sp);
|
|
|
78 }
|
|
|
79 __code quicksort_divider_e(QS_IF recvif, int s, int e, int p, stack sp)
|
|
|
80 {
|
|
|
81 if (p<recvif.v[e]) {
|
|
|
82 e--;
|
|
|
83 goto quicksort_divider_e(recvif, s, e, p, sp);
|
|
|
84 } else
|
|
|
85 goto quicksort_swapper(recvif, s, e, p, sp);
|
|
|
86 }
|
|
|
87 __code quicksort_swapper(QS_IF recvif, int s, int e, int p, stack sp)
|
|
|
88 {
|
|
|
89 if (s<e) {
|
|
|
90 int tmp;
|
|
|
91 tmp = recvif.v[s];
|
|
|
92 recvif.v[s] = recvif.v[e];
|
|
|
93 recvif.v[e] = tmp;
|
|
|
94 s++;
|
|
|
95 e--;
|
|
|
96 goto quicksort_divider(recvif, s, e, p, sp);
|
|
|
97 } else {
|
|
39
|
98 //assert(e+1==s || s==e);
|
|
23
|
99 goto quicksort_treecall(recvif, s, e, sp);
|
|
|
100 }
|
|
|
101 }
|
|
|
102 /* divide routin end. */
|
|
|
103
|
|
|
104
|
|
|
105 /* recursive call routine. */
|
|
|
106 __code quicksort_treecall(QS_IF recvif, int s, int e, stack sp)
|
|
|
107 {
|
|
|
108 framep fp;
|
|
|
109
|
|
|
110 /* interface for first quicksort_start this segment directly jump to. */
|
|
|
111 fp = (sp-=sizeof(frame));
|
|
39
|
112 fp->ret = quicksort_start;
|
|
23
|
113 fp->size = sizeof(frame);
|
|
|
114 fp->interface.v = recvif.v;
|
|
|
115 fp->interface.s = e+1;
|
|
|
116 fp->interface.e = recvif.e;
|
|
|
117
|
|
|
118 /* recvif is used by second quicksort_start. */
|
|
|
119 recvif.e = e;
|
|
|
120 goto quicksort_start(recvif, sp);
|
|
|
121 }
|
|
|
122 /* recursive call routine end. */
|
|
|
123
|
|
|
124 __code
|
|
|
125 quicksort(int *v, int s, int e, RETTYPE ret, void *arg )
|
|
|
126 {
|
|
|
127 framep fp;
|
|
|
128 stack sp0, sp;
|
|
|
129 sp0 = malloc(STACK_SIZE);
|
|
|
130 printf("allocate a stack %p\n", sp0);
|
|
|
131 sp = sp0 + STACK_SIZE;
|
|
|
132 QS_FINISH *finish_if;
|
|
|
133
|
|
|
134 /* interface for quicksort_finish. */
|
|
|
135 finish_if = (sp -= sizeof(*finish_if));
|
|
|
136 finish_if->ret = ret;
|
|
|
137 finish_if->ret_arg = arg;
|
|
|
138 finish_if->sp = sp0;
|
|
|
139
|
|
|
140 /* interface for quicksort_start. */
|
|
|
141 /* frame for quicksort_finish. */
|
|
|
142 fp = (sp -= sizeof(frame));
|
|
39
|
143 fp->ret = quicksort_finish;
|
|
23
|
144 fp->size = sizeof(frame);
|
|
|
145 fp->interface.v = v;
|
|
|
146 fp->interface.s = s;
|
|
|
147 fp->interface.e = e;
|
|
|
148
|
|
|
149 goto quicksort_start(fp->interface, sp);
|
|
|
150 }
|
|
|
151 __code
|
|
|
152 quicksort_finish(QS_IF recvif, stack sp)
|
|
|
153 {
|
|
|
154 QS_FINISH *interface = (QS_FINISH*)sp;
|
|
|
155 free(interface->sp);
|
|
|
156 printf("free the stack %p\n", interface->sp);
|
|
|
157 goto interface->ret(interface->ret_arg);
|
|
|
158 }
|
|
|
159
|
