|
1
|
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 }
|
