]> git.llucax.com Git - z.facultad/75.06/emufs.git/blob - emufs/external_sort/s_ext.c
Subo cosas de external sort con las que estoy trabajando. Todavia no hay nada utiliza...
[z.facultad/75.06/emufs.git] / emufs / external_sort / s_ext.c
1 /* external sort */
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 /****************************
8  * implementation dependent *
9  ****************************/
10
11 /* template for workfiles (8.3 format) */
12 #define FNAME "_sort%03d.dat"
13 #define LNAME 13
14
15 /* comparison operators */
16 #define compLT(x,y) (x < y)
17 #define compGT(x,y) (x > y)
18
19 /* define the record to be sorted here */
20 #define LRECL 100
21 typedef int keyType;
22 typedef struct recTypeTag {
23     keyType key;                                /* sort key for record */
24     #if LRECL
25         char data[LRECL-sizeof(keyType)];       /* other fields */
26     #endif
27 } recType;
28
29 /******************************
30  * implementation independent *
31  ******************************/
32
33 typedef enum {false, true} bool;
34
35 typedef struct tmpFileTag {
36     FILE *fp;                   /* file pointer */
37     char name[LNAME];           /* filename */
38     recType rec;                /* last record read */
39     int dummy;                  /* number of dummy runs */
40     bool eof;                   /* end-of-file flag */
41     bool eor;                   /* end-of-run flag */
42     bool valid;                 /* true if rec is valid */
43     int fib;                    /* ideal fibonacci number */
44 } tmpFileType;
45
46 static tmpFileType **file;      /* array of file info for tmp files */
47 static int nTmpFiles;           /* number of tmp files */
48 static char *ifName;            /* input filename */
49 static char *ofName;            /* output filename */
50
51 static int level;               /* level of runs */
52 static int nNodes;              /* number of nodes for selection tree */
53
54 void deleteTmpFiles(void) {
55     int i;
56
57     /* delete merge files and free resources */
58     if (file) {
59         for (i = 0; i < nTmpFiles; i++) {
60             if (file[i]) {
61                 if (file[i]->fp) fclose(file[i]->fp);
62                 if (*file[i]->name) remove(file[i]->name);
63                 free (file[i]);
64             }
65         }
66         free (file);
67     }
68 }
69
70 void termTmpFiles(int rc) {
71
72     /* cleanup files */
73     remove(ofName);
74     if (rc == 0) {
75         int fileT;
76
77         /* file[T] contains results */
78         fileT = nTmpFiles - 1;
79         fclose(file[fileT]->fp); file[fileT]->fp = NULL;
80         if (rename(file[fileT]->name, ofName)) {
81             perror("io1");
82             deleteTmpFiles();
83             exit(1);
84         }
85         *file[fileT]->name = 0;
86     }
87     deleteTmpFiles();
88 }
89
90 void cleanExit(int rc) {
91
92     /* cleanup tmp files and exit */
93     termTmpFiles(rc);
94     exit(rc);
95 }
96
97 void *safeMalloc(size_t size) {
98     void *p;
99
100     /* safely allocate memory and initialize to zero */
101     if ((p = calloc(1, size)) == NULL) {
102         printf("error: malloc failed, size = %d\n", size);
103         cleanExit(1);
104     }
105     return p;
106 }
107
108 void initTmpFiles(void) {
109     int i;
110     tmpFileType *fileInfo;
111
112     /* initialize merge files */
113     if (nTmpFiles < 3) nTmpFiles = 3;
114     file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
115     fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
116     for (i = 0; i < nTmpFiles; i++) {
117         file[i] = fileInfo + i;
118         sprintf(file[i]->name, FNAME, i);
119         if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
120             perror("io2");
121             cleanExit(1);
122         }
123     }
124 }
125
126 recType *readRec(void) {
127
128     typedef struct iNodeTag {   /* internal node */
129         struct iNodeTag *parent;/* parent of internal node */
130         struct eNodeTag *loser; /* external loser */
131     } iNodeType;
132
133     typedef struct eNodeTag {   /* external node */
134         struct iNodeTag *parent;/* parent of external node */
135         recType rec;            /* input record */
136         int run;                /* run number */
137         bool valid;             /* input record is valid */
138     } eNodeType;
139
140     typedef struct nodeTag {
141         iNodeType i;            /* internal node */
142         eNodeType e;            /* external node */
143     } nodeType;
144
145     static nodeType *node;      /* array of selection tree nodes */
146     static eNodeType *win;      /* new winner */
147     static FILE *ifp;           /* input file */
148     static bool eof;            /* true if end-of-file, input */
149     static int maxRun;          /* maximum run number */
150     static int curRun;          /* current run number */
151     iNodeType *p;               /* pointer to internal nodes */
152     static bool lastKeyValid;   /* true if lastKey is valid */
153     static keyType lastKey;     /* last key written */
154
155     /* read next record using replacement selection */
156
157     /* check for first call */
158     if (node == NULL) {
159         int i;
160
161         if (nNodes < 2) nNodes = 2;
162         node = safeMalloc(nNodes * sizeof(nodeType));
163         for (i = 0; i < nNodes; i++) {
164             node[i].i.loser = &node[i].e;
165             node[i].i.parent = &node[i/2].i;
166             node[i].e.parent = &node[(nNodes + i)/2].i;
167             node[i].e.run = 0;
168             node[i].e.valid = false;
169         }
170         win = &node[0].e;
171         lastKeyValid = false;
172
173         if ((ifp = fopen(ifName, "rb")) == NULL) {
174             printf("error: file %s, unable to open\n", ifName);
175             cleanExit(1);
176         }
177     }
178
179     while (1) {
180
181         /* replace previous winner with new record */
182         if (!eof) {
183             if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
184                 if ((!lastKeyValid || compLT(win->rec.key, lastKey))
185                 && (++win->run > maxRun))
186                     maxRun = win->run;
187                 win->valid = true;
188             } else if (feof(ifp)) {
189                 fclose(ifp);
190                 eof = true;
191                 win->valid = false;
192                 win->run = maxRun + 1;
193             } else {
194                 perror("io4");
195                 cleanExit(1);
196             } 
197         } else {
198             win->valid = false;
199             win->run = maxRun + 1;
200         }
201
202         /* adjust loser and winner pointers */
203         p = win->parent;
204         do {
205             bool swap;
206             swap = false;
207             if (p->loser->run < win->run) {
208                 swap = true;
209             } else if (p->loser->run == win->run) {
210                 if (p->loser->valid && win->valid) {
211                     if (compLT(p->loser->rec.key, win->rec.key))
212                         swap = true;
213                 } else {
214                     swap = true;
215                 }
216             }
217             if (swap) {
218                 /* p should be winner */
219                 eNodeType *t;
220
221                 t = p->loser;
222                 p->loser = win;
223                 win = t;
224             }
225             p = p->parent;
226         } while (p != &node[0].i);
227
228         /* end of run? */
229         if (win->run != curRun) {
230             /* win->run = curRun + 1 */
231             if (win->run > maxRun) {
232                 /* end of output */
233                 free(node);
234                 return NULL;
235             }
236             curRun = win->run;
237         }
238
239         /* output top of tree */
240         if (win->run) {
241             lastKey = win->rec.key;
242             lastKeyValid = true;
243             return &win->rec;
244         }
245     }
246 }
247
248 void makeRuns(void) {
249     recType *win;       /* winner */
250     int fileT;          /* last file */
251     int fileP;          /* next to last file */
252     int j;              /* selects file[j] */
253
254
255     /* Make initial runs using replacement selection.
256      * Runs are written using a Fibonacci distintbution.
257      */
258
259     /* initialize file structures */
260     fileT = nTmpFiles - 1;
261     fileP = fileT - 1;
262     for (j = 0; j < fileT; j++) {
263         file[j]->fib = 1;
264         file[j]->dummy = 1;
265     }
266     file[fileT]->fib = 0;
267     file[fileT]->dummy = 0;
268
269     level = 1;
270     j = 0;
271
272
273     win = readRec();
274     while (win) {
275         bool anyrun;
276
277         anyrun = false;
278         for (j = 0; win && j <= fileP; j++) {
279             bool run;
280
281             run = false;
282             if (file[j]->valid) {
283                 if (!compLT(win->key, file[j]->rec.key)) {
284                     /* append to an existing run */
285                     run = true;
286                 } else if (file[j]->dummy) {
287                     /* start a new run */
288                     file[j]->dummy--;
289                     run = true;
290                 }
291             } else {
292                 /* first run in file */
293                 file[j]->dummy--;
294                 run = true;
295             }
296
297             if (run) {
298                 anyrun = true;
299
300                 /* flush run */
301                 while(1) {
302                     if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
303                         perror("io3");
304                         cleanExit(1);
305                     }
306                     file[j]->rec.key = win->key;
307                     file[j]->valid = true;
308                     if ((win = readRec()) == NULL) break;
309                     if (compLT(win->key, file[j]->rec.key)) break;
310                 }
311             }
312         }
313
314         /* if no room for runs, up a level */
315         if (!anyrun) {
316             int t;
317             level++;
318             t = file[0]->fib;
319             for (j = 0; j <= fileP; j++) {
320                 file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
321                 file[j]->fib = t + file[j+1]->fib; 
322             }
323         }
324     }
325 }
326
327 void rewindFile(int j) {
328     /* rewind file[j] and read in first record */
329     file[j]->eor = false;
330     file[j]->eof = false;
331     rewind(file[j]->fp);
332     if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
333         if (feof(file[j]->fp)) {
334             file[j]->eor = true;
335             file[j]->eof = true;
336         } else {
337             perror("io5");
338             cleanExit(1);
339         }
340     }
341 }
342
343 void mergeSort(void) {
344     int fileT;
345     int fileP;
346     int j;
347     tmpFileType *tfile;
348
349     /* polyphase merge sort */
350
351     fileT = nTmpFiles - 1;
352     fileP = fileT - 1;
353
354     /* prime the files */
355     for (j = 0; j < fileT; j++) {
356         rewindFile(j);
357     }
358
359     /* each pass through loop merges one run */
360     while (level) {
361         while(1) {
362             bool allDummies;
363             bool anyRuns;
364
365             /* scan for runs */
366             allDummies = true;
367             anyRuns = false;
368             for (j = 0; j <= fileP; j++) {
369                 if (!file[j]->dummy) {
370                     allDummies = false;
371                     if (!file[j]->eof) anyRuns = true;
372                 }
373             }
374
375             if (anyRuns) {
376                 int k;
377                 keyType lastKey;
378
379                 /* merge 1 run file[0]..file[P] --> file[T] */
380
381                 while(1) {
382                     /* each pass thru loop writes 1 record to file[fileT] */
383
384                     /* find smallest key */
385                     k = -1;
386                     for (j = 0; j <= fileP; j++) {
387                         if (file[j]->eor) continue;
388                         if (file[j]->dummy) continue;
389                         if (k < 0 || 
390                         (k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
391                             k = j;
392                     }
393                     if (k < 0) break;
394
395                     /* write record[k] to file[fileT] */
396                     if (fwrite(&file[k]->rec, sizeof(recType), 1, 
397                             file[fileT]->fp) != 1) {
398                         perror("io6");
399                         cleanExit(1);
400                     }
401
402                     /* replace record[k] */
403                     lastKey = file[k]->rec.key;
404                     if (fread(&file[k]->rec, sizeof(recType), 1,
405                             file[k]->fp) == 1) {
406                         /* check for end of run on file[s] */
407                         if (compLT(file[k]->rec.key, lastKey))
408                             file[k]->eor = true;
409                     } else if (feof(file[k]->fp)) {
410                         file[k]->eof = true;
411                         file[k]->eor = true;
412                     } else {
413                         perror("io7");
414                         cleanExit(1);
415                     }
416                 }
417
418                 /* fixup dummies */
419                 for (j = 0; j <= fileP; j++) {
420                     if (file[j]->dummy) file[j]->dummy--;
421                     if (!file[j]->eof) file[j]->eor = false;
422                 }
423
424             } else if (allDummies) {
425                 for (j = 0; j <= fileP; j++)
426                     file[j]->dummy--;
427                 file[fileT]->dummy++;
428             }
429
430             /* end of run */
431             if (file[fileP]->eof && !file[fileP]->dummy) {
432                 /* completed a fibonocci-level */
433                 level--;
434                 if (!level) {
435                     /* we're done, file[fileT] contains data */
436                     return;
437                 }
438
439                 /* fileP is exhausted, reopen as new */
440                 fclose(file[fileP]->fp);
441                 if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
442                         == NULL) {
443                     perror("io8");
444                     cleanExit(1);
445                 }
446                 file[fileP]->eof = false;
447                 file[fileP]->eor = false;
448
449                 rewindFile(fileT);
450
451                 /* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
452                 tfile = file[fileT];
453                 memmove(file + 1, file, fileT * sizeof(tmpFileType*));
454                 file[0] = tfile;
455
456                 /* start new runs */
457                 for (j = 0; j <= fileP; j++)
458                     if (!file[j]->eof) file[j]->eor = false;
459             }
460         }
461
462     }
463 }
464
465
466 void extSort(void) {
467     initTmpFiles();
468     makeRuns();
469     mergeSort();
470     termTmpFiles(0);
471 }
472
473 int main(int argc, char *argv[]) {
474
475     /* command-line:
476      *
477      *   ext ifName ofName nTmpFiles nNodes
478      *
479      *   ext in.dat out.dat 5 2000
480      *       reads in.dat, sorts using 5 files and 2000 nodes, output to out.dat
481      */
482     if (argc != 5) {
483         printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
484         cleanExit(1);
485     }
486
487     ifName = argv[1];
488     ofName = argv[2];
489     nTmpFiles = atoi(argv[3]);
490     nNodes = atoi(argv[4]);
491
492     printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
493         nTmpFiles, nNodes, sizeof(recType));
494
495     extSort();
496
497     return 0;
498 }