Back to index

radiance  4R0+20100331
Defines | Functions | Variables
sort.c File Reference
#include "platform.h"
#include "rtprocess.h"
#include "rterror.h"
#include "meta.h"

Go to the source code of this file.

Defines

#define PBSIZE   1000 /* max size of sort block */
#define NFILES   4 /* number of sort files */

Functions

static void treemerge (int height, int nt, int nf, PLIST *pl, int(*pcmp)(), FILE *ofp)
static void sendsort (PLIST *pl, int(*pcmp)())
static void order (PRIMITIVE *pa[], int n, PLIST *pl)
static char * tfname (int lvl, int num)
void sort (FILE *infp, int(*pcmp)())
void pmergesort (FILE *fi[], int nf, PLIST *pl, int(*pcmp)(), FILE *ofp)

Variables

static const char RCSid [] = "$Id: sort.c,v 1.8 2003/11/15 02:13:37 schorsch Exp $"

Define Documentation

#define NFILES   4 /* number of sort files */

Definition at line 17 of file sort.c.

#define PBSIZE   1000 /* max size of sort block */

Definition at line 14 of file sort.c.


Function Documentation

static void order ( PRIMITIVE *  pa[],
int  n,
PLIST *  pl 
) [static]
void pmergesort ( FILE *  fi[],
int  nf,
PLIST *  pl,
int(*)()  pcmp,
FILE *  ofp 
)

Definition at line 84 of file sort.c.

{
    PRIMITIVE  *plp;        /* position in list */
    PRIMITIVE  *pp[NFILES]; /* input primitives */
    int  minf = 0;
    PRIMITIVE  *minp;
    register int i;

    if (pl == NULL)
       plp = NULL;                 /* initialize list */
    else
       plp = pl->ptop;

    for (i = 0; i < nf; i++) {            /* initialize input files */
       if ((pp[i] = palloc()) == NULL)
           error(SYSTEM, "memory exhausted in pmergesort");
       readp(pp[i], fi[i]);
    }

    for ( ; ; ) {

       if (plp != NULL && isprim(plp->com))
           minp = plp;
       else
           minp = NULL;

       for (i = 0; i < nf; i++)
           if (isprim(pp[i]->com) &&
                     (minp == NULL || (*pcmp)(&pp[i], &minp) < 0))
              minp = pp[minf=i];

       if (minp == NULL)
           break;

       writep(minp, ofp);

       if (minp == plp)
           plp = plp->pnext;
       else {
           fargs(pp[minf]);
           readp(pp[minf], fi[minf]);
       }
    }

    if (plp != NULL && plp->com != PEOF)
       writep(plp, ofp);

    for (i = 0; i < nf; i++) {
       if (pp[i]->com != PEOF)
           writep(pp[i], ofp);
       pfree(pp[i]);
    }

}

Here is the call graph for this function:

Here is the caller graph for this function:

static void sendsort ( PLIST *  pl,
int(*)()  pcmp 
) [static]

Definition at line 196 of file sort.c.

{
    static int  nf = 0,
              intree = FALSE;

    if (isglob(pl->pbot->com)) {

                                   /* send sorted output to stdout */
       if (intree && nf <= NFILES)

           treemerge(0, 0, nf, pl, pcmp, stdout);

       else if (nf%NFILES == 0)

           if (intree) {
              treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
              treemerge(1, 0, nf/NFILES, NULL, pcmp, stdout);
           } else
              treemerge(1, 0, nf/NFILES, pl, pcmp, stdout);

       else {

           treemerge(0, nf/NFILES, nf%NFILES, pl, pcmp, NULL);
           treemerge(1, 0, nf/NFILES + 1, NULL, pcmp, stdout);

       }

       nf = 0;                            /* all done */
       intree = FALSE;                    /* reset for next time */
       
    } else if (intree && nf%NFILES == 0) {

                                   /* merge NFILES with list */
       treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
       intree = FALSE;

    } else {

                                   /* output straight to temp file */
       treemerge(-1, nf++, 0, pl, pcmp, NULL);
       intree = TRUE;

    }



}

Here is the call graph for this function:

Here is the caller graph for this function:

void sort ( FILE *  infp,
int(*)()  pcmp 
)

Definition at line 33 of file sort.c.

{
 PRIMITIVE  *prims[PBSIZE];        /* pointers to primitives */
 PLIST  primlist;                  /* our primitives list */
 int  nprims;
 short  done;

 do  {

    for (nprims = 0; nprims < PBSIZE; nprims++)  {      /* read to global */

       if ((prims[nprims] = palloc()) == NULL)
          error(SYSTEM, "memory exhausted in sort");

       readp(prims[nprims], infp);

       if (isglob(prims[nprims]->com))
         break;
       }

       qsort(prims, nprims, sizeof(*prims), pcmp);      /* sort pointer array */

       if (nprims < PBSIZE)               /* tack on global if one */
           nprims++;

       order(prims, nprims, &primlist);   /* make array into list */

       sendsort(&primlist, pcmp);         /* send to merge sorter */

       done = primlist.pbot->com == PEOF;

       plfree(&primlist);                 /* free up array */

    }  while (!done);

 }

Here is the call graph for this function:

Here is the caller graph for this function:

static char* tfname ( int  lvl,
int  num 
) [static]
static void treemerge ( int  height,
int  nt,
int  nf,
PLIST *  pl,
int(*)()  pcmp,
FILE *  ofp 
) [static]

Definition at line 149 of file sort.c.

{
    FILE  *fi[NFILES], *fp;
    int  i;
    
    if (nf <= NFILES) {

       for (i = 0; i < nf; i++)
           fi[i] = efopen(tfname(height, i + nt*NFILES), "r");
       
       if ((fp = ofp) == NULL)
           fp = efopen(tfname(height + 1, nt), "w");
       
       pmergesort(fi, nf, pl, pcmp, fp);
       
       for (i = 0; i < nf; i++) {
           fclose(fi[i]);
           unlink(tfname(height, i + nt*NFILES));
       }
       if (ofp == NULL) {
           writeof(fp);
           fclose(fp);
       }
       
    } else {
    
        for (i = 0; i < (nf-1)/NFILES; i++)
            treemerge(height, i, NFILES, NULL, pcmp, NULL);
            
       treemerge(height, (nf-1)/NFILES, (nf-1)%NFILES + 1, pl, pcmp, NULL);

       treemerge(height + 1, 0, (nf-1)/NFILES + 1, NULL, pcmp, ofp);
            
    }

}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

const char RCSid[] = "$Id: sort.c,v 1.8 2003/11/15 02:13:37 schorsch Exp $" [static]

Definition at line 2 of file sort.c.