Mercurial > repos > bitlab > bitlab

comparison gecko/src/quicksort.c @ 1:35af401890c0 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author bitlab
date Thu, 13 Dec 2018 07:59:25 -0500
parents
children
comparison
equal deleted inserted replaced
0:ee6b15b409e5 1:35af401890c0
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <pthread.h>
5 #include <unistd.h>
6 #include <sys/time.h>
7 #include <stdint.h>
8 #include "structs.h"
9 #include "commonFunctions.h"
10 #include "quicksort.h"
11
12 #define BUF_SIZE 1024
13 #define SWAP(a,b,t) t=a; a=b; b=t;
14 #define STRING_SIZE 1024
15
16 typedef struct {
17 BaseType* a;
18 int l;
19 int r;
20 int nth;
21 } PQSortArgs;
22
23 typedef struct {
24 char fin1[STRING_SIZE];
25 char fin2[STRING_SIZE];
26 char fout[STRING_SIZE];
27 } PMergeArgs;
28
29 void assertNotNull(void* p, char* msg){
30 if(p==NULL){
31 terror(msg);
32 }
33 }
34
35 void assertIntEQ(int a, int b, char* msg){
36 if(a!=b){
37 terror(msg);
38 }
39 }
40
41 void assertIntGE(int a, int b, char* msg){
42 if(a<b){
43 terror(msg);
44 }
45 }
46
47 int bufMerge(BaseType* a1, int n1, BaseType* a2, int n2, BaseType* m){
48 int i1=0,i2=0;
49 int j=0;
50
51 while(i1<n1 && i2<n2){
52 if(GT(a1[i1],a2[i2])){
53 m[j]=a2[i2];
54 i2++;
55 j++;
56 }else{
57 m[j]=a1[i1];
58 i1++;
59 j++;
60 }
61 }
62
63 while(i1<n1){
64 m[j]=a1[i1];
65 i1++;
66 j++;
67 }
68
69 while(i2<n2){
70 m[j]=a2[i2];
71 i2++;
72 j++;
73 }
74
75 return j;
76 }
77
78 void *PMerge(void* a){
79 PMergeArgs* args = (PMergeArgs*)a;
80
81 FILE* fin1 = fopen(args->fin1,"rb");
82 assertNotNull(fin1,args->fin1);
83
84 FILE* fin2 = fopen(args->fin2,"rb");
85 assertNotNull(fin2,args->fin2);
86
87 FILE* fout = fopen(args->fout,"wb");
88 assertNotNull(fout,args->fout);
89
90 BaseType *a1 = (BaseType*)calloc(BUF_SIZE,sizeof(BaseType));
91 assertNotNull(a1,"calloc");
92
93 BaseType *a2 = (BaseType*)calloc(BUF_SIZE,sizeof(BaseType));
94 assertNotNull(a2,"calloc");
95
96 BaseType *m = (BaseType*)calloc(2*BUF_SIZE,sizeof(BaseType));
97 assertNotNull(m,"calloc");
98
99 int i,j,k;
100 int r1,r2,tmp;
101
102 r1=fread(a1,sizeof(BaseType),BUF_SIZE,fin1);
103 r2=fread(a2,sizeof(BaseType),BUF_SIZE,fin2);
104
105 i=j=k=0;
106 while(r1>0 && r2>0){
107 while(i<r1 && j<r2){
108 if(GT(a1[i],a2[j])){
109 m[k]=a2[j];
110 j++;
111 }else{
112 m[k]=a1[i];
113 i++;
114 }
115 k++;
116 if(k>=2*BUF_SIZE){
117 tmp=fwrite(m,sizeof(BaseType),k,fout);
118 assertIntEQ(tmp,k,"fwrite");
119 k=0;
120 }
121 }
122
123 if(i>=r1){
124 r1=fread(a1,sizeof(BaseType),BUF_SIZE,fin1);
125 i=0;
126 }
127
128 if(j>=r2){
129 r2=fread(a2,sizeof(BaseType),BUF_SIZE,fin2);
130 j=0;
131 }
132 }
133
134 if(k>0){
135 tmp=fwrite(m,sizeof(BaseType),k,fout);
136 assertIntEQ(tmp,k,"fwrite");
137 }
138
139 if(i<r1){
140 tmp=fwrite(a1+i,sizeof(BaseType),r1-i,fout);
141 assertIntEQ(tmp,r1-i,"fwrite");
142 }
143
144 if(j<r2){
145 tmp=fwrite(a2+j,sizeof(BaseType),r2-j,fout);
146 assertIntEQ(tmp,r2-j,"fwrite");
147 }
148
149 assertIntEQ(fclose(fin1),0,"fclose");
150 assertIntEQ(fclose(fin2),0,"fclose");
151 assertIntEQ(fclose(fout),0,"fclose");
152
153 assertIntEQ(unlink(args->fin1),0,args->fin1);
154 assertIntEQ(unlink(args->fin2),0,args->fin2);
155
156 pthread_exit(NULL);
157 }
158
159 int partition(BaseType* a, int l, int r) {
160 int i=l;
161 int j=r+1;
162 BaseType t;
163
164 // l sera el pivote
165 // y contendra la mediana de l, r y (l+r)/2
166 int mid = (l+r)/2;
167
168 if(GT(a[mid],a[r])) {
169 SWAP(a[mid],a[r],t);
170 }
171
172 if(GT(a[mid],a[l])) {
173 SWAP(a[mid],a[l],t);
174 }
175
176 if(GT(a[l],a[r])) {
177 SWAP(a[l],a[r],t);
178 }
179
180 while (1) {
181 do{
182 ++i;
183 }while( !GT(a[i],a[l]) && i <= r );
184
185 do{
186 --j;
187 }while( GT(a[j],a[l]) && j >= l);
188
189 if( i >= j ) break;
190
191 SWAP(a[i],a[j],t)
192 }
193
194 SWAP(a[l],a[j],t)
195
196 return j;
197 }
198
199 int QsortC(BaseType* a, int l,int r) {
200 int j;
201
202 if( l < r ) {
203 // divide and conquer
204 j = partition( a, l, r);
205 // j=(l+r)/2;
206 QsortC( a, l, j-1);
207 QsortC( a, j+1, r);
208 }
209 return 0;
210 }
211
212 void *PQSort(void* a){
213 PQSortArgs *args=(PQSortArgs*)a;
214 if(args->nth>1){
215 int tmp;
216 int j = partition(args->a,args->l,args->r);
217 int np=1;
218 if(args->r - args->l > 0)
219 np = (args->nth*(j-args->l))/(args->r-args->l);
220 if(np<1) np=1;
221 if(np>=args->nth) np=args->nth-1;
222 //printf("%d\t%d (%d)\t%d (%d)\n",args->r-args->l,j-args->l,np,args->r-j,args->nth-np);
223
224 pthread_t* th = (pthread_t*)calloc(2,sizeof(pthread_t));
225 assertNotNull(th,"calloc");
226
227 PQSortArgs* nargs = (PQSortArgs*)calloc(2,sizeof(PQSortArgs));
228 assertNotNull(args,"calloc");
229
230 nargs[0].a=args->a;
231 nargs[0].l=args->l;
232 nargs[0].r=j-1;
233 nargs[0].nth=np;
234 tmp=pthread_create(th,NULL,PQSort,(void*)(nargs));
235 assertIntEQ(tmp,0,"pthread_create");
236
237 nargs[1].a=args->a;
238 nargs[1].l=j+1;
239 nargs[1].r=args->r;
240 nargs[1].nth=args->nth-np;
241 tmp=pthread_create(th+1,NULL,PQSort,(void*)(nargs+1));
242 assertIntEQ(tmp,0,"pthread_create");
243
244 tmp=pthread_join(th[0],NULL);
245 assertIntEQ(tmp,0,"pthread_join");
246 tmp=pthread_join(th[1],NULL);
247 assertIntEQ(tmp,0,"pthread_join");
248
249 free(th);
250 free(nargs);
251 }else{
252 QsortC(args->a,args->l,args->r);
253 }
254 pthread_exit(NULL);
255 }
256
257 unsigned long timestart(){
258 struct timeval tv;
259
260 gettimeofday(&tv,NULL);
261
262 return (tv.tv_usec/1000) + (tv.tv_sec*1000);
263 }
264
265 unsigned long timestop(unsigned long start){
266 struct timeval tv;
267
268 gettimeofday(&tv,NULL);
269
270 return (tv.tv_usec/1000) + (tv.tv_sec*1000) - start;
271 }
272
273 int psort(int maxsize, int nproc, char* ifile, char* ofile){
274 int tmp;
275 int max=maxsize;
276 int np=nproc;
277 if(np<1) np=1;
278
279 printf("Allocating %lu bytes.\n",max*sizeof(BaseType));
280 BaseType* a = (BaseType*)calloc(max,sizeof(BaseType));
281 assertNotNull(a,"calloc");
282
283 FILE* fin=fopen(ifile,"rt");
284 assertNotNull(fin,ifile);
285
286 printf("Stage1: Quicksorts\n");
287 unsigned long t = timestart();
288 //Read + Quicksort + Write:
289 char fname[strlen(ofile)+10];
290 int nfile=0;
291
292 do {
293 //Read:
294 // printf("Reading...\n");
295 int n=fread(a,sizeof(BaseType),max,fin);
296 if(n==0) break;
297
298 //Quicksort:
299 // printf("Quicksort %d\n",n);
300 pthread_t th;
301 PQSortArgs args;
302
303 args.a=a;
304 args.l=0;
305 args.r=n-1;
306 args.nth=np;
307 tmp=pthread_create(&th,NULL,PQSort,(void*)(&args));
308 assertIntEQ(tmp,0,"pthread_create");
309
310 //Wait:
311 tmp=pthread_join(th,NULL);
312 assertIntEQ(tmp,0,"pthread_join");
313
314 //Write:
315 // printf("Writing...\n");
316 sprintf(fname,"%s.%06d",ofile,nfile);
317 FILE* fout=fopen(fname,"wb");
318 assertNotNull(fout,"fname");
319
320 tmp=fwrite(a,sizeof(BaseType),n,fout);
321 assertIntEQ(tmp,n,"fwrite");
322
323 tmp=fclose(fout);
324 assertIntEQ(tmp,0,"fclose");
325
326 nfile++;
327 }while(!feof(fin));
328
329 tmp=fclose(fin);
330 assertIntEQ(tmp,0,"fclose");
331
332 free(a);
333
334 tmp=unlink(ifile);
335 assertIntEQ(tmp,0,"unlink");
336
337 printf("Stage1: %lu\n\n",timestop(t));
338
339 //Merge:
340 printf("Stage2: Merge\n");
341 t = timestart();
342
343 int curf=0;
344 int i=0;
345 int j=0;
346 pthread_t th[np];
347 PMergeArgs args[np];
348
349 curf=0;
350 while(nfile-curf>1){
351 j=0;
352 while(curf<nfile-1 && j<np){
353 sprintf(args[j].fin1,"%s.%06d",ofile,curf);
354 sprintf(args[j].fin2,"%s.%06d",ofile,curf+1);
355 sprintf(args[j].fout,"%s.%06d",ofile,nfile+j);
356
357 // printf("Merge(%d, %d) -> %d\n",curf,curf+1,nfile+j);
358 tmp=pthread_create(th+j,NULL,PMerge,(void*)(args+j));
359 assertIntEQ(tmp,0,"pthread_create");
360 curf+=2;
361 j++;
362 }
363
364 for(i=0;i<j;i++){
365 tmp=pthread_join(th[i],NULL);
366 assertIntEQ(tmp,0,"pthread_join");
367 }
368
369 nfile+=j;
370 }
371
372 printf("Stage2: %lu\n\n",timestop(t));
373
374 //Bin2Text:
375 printf("Stage3: Write output file\n");
376 t = timestart();
377
378 sprintf(fname,"%s.%06d",ofile,curf);
379 if(nfile>0){
380 tmp=rename(fname,ofile);
381 assertIntEQ(tmp,0,"rename");
382 } else {
383 FILE *fout=fopen(ofile, "wb");
384 assertNotNull(fout,"fopen");
385 fclose(fout);
386 }
387
388 printf("Stage3: %lu\n",timestop(t));
389
390 return 0;
391
392 }