Mercurial > repos > bitlab > bitlab
comparison gecko/src/quicksort.c @ 1:35af401890c0 draft
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 } |