Back to index

radiance  4R0+20100331
sort.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: sort.c,v 1.8 2003/11/15 02:13:37 schorsch Exp $";
00003 #endif
00004 /*
00005  *   Sorting routines for meta-files
00006  */
00007 
00008 #include  "platform.h"  /* [_]snprintf() */
00009 #include  "rtprocess.h" /* getpid() */
00010 #include  "rterror.h"
00011 #include  "meta.h"
00012 
00013 
00014 #define  PBSIZE  1000              /* max size of sort block */
00015                             /* maxalloc must be >= this */
00016 
00017 #define  NFILES  4          /* number of sort files */
00018 
00019 
00020 static void treemerge(int height, int nt, int nf, PLIST *pl,
00021               int (*pcmp)(), FILE *ofp);
00022 static void sendsort( PLIST  *pl, int  (*pcmp)());
00023 static void order(PRIMITIVE  *pa[], int  n, PLIST  *pl);
00024 static char * tfname( int  lvl, int num);
00025 
00026 /*
00027  *   This sort routine does a combination quicksort and
00028  *   n-ary mergesort
00029  */
00030 
00031 
00032 void
00033 sort(         /* sort primitives according to pcmp */
00034 FILE  *infp,
00035 int  (*pcmp)()              /* compares pointers to pointers to primitives! */
00036 )
00037 {
00038  PRIMITIVE  *prims[PBSIZE];        /* pointers to primitives */
00039  PLIST  primlist;                  /* our primitives list */
00040  int  nprims;
00041  short  done;
00042 
00043  do  {
00044 
00045     for (nprims = 0; nprims < PBSIZE; nprims++)  {      /* read to global */
00046 
00047        if ((prims[nprims] = palloc()) == NULL)
00048           error(SYSTEM, "memory exhausted in sort");
00049 
00050        readp(prims[nprims], infp);
00051 
00052        if (isglob(prims[nprims]->com))
00053          break;
00054        }
00055 
00056        qsort(prims, nprims, sizeof(*prims), pcmp);      /* sort pointer array */
00057 
00058        if (nprims < PBSIZE)               /* tack on global if one */
00059            nprims++;
00060 
00061        order(prims, nprims, &primlist);   /* make array into list */
00062 
00063        sendsort(&primlist, pcmp);         /* send to merge sorter */
00064 
00065        done = primlist.pbot->com == PEOF;
00066 
00067        plfree(&primlist);                 /* free up array */
00068 
00069     }  while (!done);
00070 
00071  }
00072 
00073 
00074 
00075 
00076 
00077 /*
00078  *  The following routine merges up to NFILES sorted primitive files
00079  *     with 0 or 1 primitive lists.  Each set of primitives can end with
00080  *     0 or 1 global commands.
00081  */
00082 
00083 void
00084 pmergesort(   /* merge sorted files with list */
00085 
00086 FILE  *fi[],         /* array of input files */
00087 int  nf,             /* number of input files */
00088 PLIST  *pl,          /* sorted list */
00089 int  (*pcmp)(),             /* comparison function, takes primitive handles */
00090 FILE  *ofp           /* output file */
00091 )
00092 {
00093     PRIMITIVE  *plp;        /* position in list */
00094     PRIMITIVE  *pp[NFILES]; /* input primitives */
00095     int  minf = 0;
00096     PRIMITIVE  *minp;
00097     register int i;
00098 
00099     if (pl == NULL)
00100        plp = NULL;                 /* initialize list */
00101     else
00102        plp = pl->ptop;
00103 
00104     for (i = 0; i < nf; i++) {            /* initialize input files */
00105        if ((pp[i] = palloc()) == NULL)
00106            error(SYSTEM, "memory exhausted in pmergesort");
00107        readp(pp[i], fi[i]);
00108     }
00109 
00110     for ( ; ; ) {
00111 
00112        if (plp != NULL && isprim(plp->com))
00113            minp = plp;
00114        else
00115            minp = NULL;
00116 
00117        for (i = 0; i < nf; i++)
00118            if (isprim(pp[i]->com) &&
00119                      (minp == NULL || (*pcmp)(&pp[i], &minp) < 0))
00120               minp = pp[minf=i];
00121 
00122        if (minp == NULL)
00123            break;
00124 
00125        writep(minp, ofp);
00126 
00127        if (minp == plp)
00128            plp = plp->pnext;
00129        else {
00130            fargs(pp[minf]);
00131            readp(pp[minf], fi[minf]);
00132        }
00133     }
00134 
00135     if (plp != NULL && plp->com != PEOF)
00136        writep(plp, ofp);
00137 
00138     for (i = 0; i < nf; i++) {
00139        if (pp[i]->com != PEOF)
00140            writep(pp[i], ofp);
00141        pfree(pp[i]);
00142     }
00143 
00144 }
00145 
00146 
00147 
00148 static void
00149 treemerge(    /* merge into one file */
00150 
00151 int  height, int nt, int nf,
00152 PLIST  *pl,
00153 int  (*pcmp)(),
00154 FILE  *ofp
00155 )
00156 {
00157     FILE  *fi[NFILES], *fp;
00158     int  i;
00159     
00160     if (nf <= NFILES) {
00161 
00162        for (i = 0; i < nf; i++)
00163            fi[i] = efopen(tfname(height, i + nt*NFILES), "r");
00164        
00165        if ((fp = ofp) == NULL)
00166            fp = efopen(tfname(height + 1, nt), "w");
00167        
00168        pmergesort(fi, nf, pl, pcmp, fp);
00169        
00170        for (i = 0; i < nf; i++) {
00171            fclose(fi[i]);
00172            unlink(tfname(height, i + nt*NFILES));
00173        }
00174        if (ofp == NULL) {
00175            writeof(fp);
00176            fclose(fp);
00177        }
00178        
00179     } else {
00180     
00181         for (i = 0; i < (nf-1)/NFILES; i++)
00182             treemerge(height, i, NFILES, NULL, pcmp, NULL);
00183             
00184        treemerge(height, (nf-1)/NFILES, (nf-1)%NFILES + 1, pl, pcmp, NULL);
00185 
00186        treemerge(height + 1, 0, (nf-1)/NFILES + 1, NULL, pcmp, ofp);
00187             
00188     }
00189 
00190 }
00191 
00192 
00193 
00194 
00195 static void
00196 sendsort(            /* send a sorted list */
00197 
00198 PLIST  *pl,
00199 int  (*pcmp)()
00200 )
00201 {
00202     static int  nf = 0,
00203               intree = FALSE;
00204 
00205     if (isglob(pl->pbot->com)) {
00206 
00207                                    /* send sorted output to stdout */
00208        if (intree && nf <= NFILES)
00209 
00210            treemerge(0, 0, nf, pl, pcmp, stdout);
00211 
00212        else if (nf%NFILES == 0)
00213 
00214            if (intree) {
00215               treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
00216               treemerge(1, 0, nf/NFILES, NULL, pcmp, stdout);
00217            } else
00218               treemerge(1, 0, nf/NFILES, pl, pcmp, stdout);
00219 
00220        else {
00221 
00222            treemerge(0, nf/NFILES, nf%NFILES, pl, pcmp, NULL);
00223            treemerge(1, 0, nf/NFILES + 1, NULL, pcmp, stdout);
00224 
00225        }
00226 
00227        nf = 0;                            /* all done */
00228        intree = FALSE;                    /* reset for next time */
00229        
00230     } else if (intree && nf%NFILES == 0) {
00231 
00232                                    /* merge NFILES with list */
00233        treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
00234        intree = FALSE;
00235 
00236     } else {
00237 
00238                                    /* output straight to temp file */
00239        treemerge(-1, nf++, 0, pl, pcmp, NULL);
00240        intree = TRUE;
00241 
00242     }
00243 
00244 
00245 
00246 }
00247 
00248 
00249 
00250 static void
00251 order( /* order the first n array primitives into list */
00252 
00253 PRIMITIVE  *pa[],
00254 int  n,
00255 PLIST  *pl
00256 )
00257 {
00258  register int  i;
00259 
00260  for (i = 1; i < n; i++)
00261     pa[i-1]->pnext = pa[i];
00262 
00263  pa[n-1]->pnext = NULL;
00264  pl->ptop = pa[0];
00265  pl->pbot = pa[n-1];
00266 
00267  }
00268 
00269 
00270 
00271 
00272 static char *
00273 tfname(              /* create temporary file name */
00274 
00275 int  lvl, int num
00276 )
00277 {
00278        static char  pathbuf[PATH_MAX];
00279     static char  fnbuf[PATH_MAX];
00280        static size_t psiz;
00281 
00282        if (pathbuf[0] == '\0') { /* first time */
00283               temp_directory(pathbuf, sizeof(pathbuf));
00284               psiz = strlen(pathbuf);
00285        }
00286        snprintf(fnbuf, sizeof(pathbuf)-psiz,
00287                      "%s/S%d%c%d", pathbuf, getpid(), lvl+'A', num);
00288     /*sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);*/
00289 
00290     return(fnbuf);
00291 }