src/meta/sort.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 *   Sorting routines for meta-files
 */


#define  PBSIZE  1000           /* max size of sort block */
                                /* maxalloc must be >= this */


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


#include  "meta.h"


/*
 *   This sort routine does a combination quicksort and
 *   n-ary mergesort
 */


sort(infp, pcmp)                /* sort primitives according to pcmp */

FILE  *infp;
int  (*pcmp)();         /* compares pointers to pointers to primitives! */

{
 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);

 }


/*
 *  The following routine merges up to NFILES sorted primitive files
 *     with 0 or 1 primitive lists.  Each set of primitives can end with
 *     0 or 1 global commands.
 */

mergesort(fi, nf, pl, pcmp, ofp)        /* merge sorted files with list */

FILE  *fi[];            /* array of input files */
int  nf;                /* number of input files */
PLIST  *pl;             /* sorted list */
int  (*pcmp)();         /* comparison function, takes primitive handles */
FILE  *ofp;             /* output file */

{
    PRIMITIVE  *plp;            /* position in list */
    PRIMITIVE  *pp[NFILES];     /* input primitives */
    int  minf;
    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 mergesort");
        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]);
    }

}


static
treemerge(height, nt, nf, pl, pcmp, ofp)        /* merge into one file */

int  height, nt, nf;
PLIST  *pl;
int  (*pcmp)();
FILE  *ofp;

{
    char  *tfname();
    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");
        
        mergesort(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);
            
    }

}


static
sendsort(pl, pcmp)              /* send a sorted list */

PLIST  *pl;
int  (*pcmp)();

{
    static int  nf = 0,
                intree = FALSE;
    FILE  *fp;

    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;

    }


}


static
order(pa, n, pl)        /* order the first n array primitives into list */

PRIMITIVE  *pa[];
int  n;
PLIST  *pl;

{
 register int  i;

 for (i = 1; i < n; i++)
    pa[i-1]->pnext = pa[i];

 pa[n-1]->pnext = NULL;
 pl->ptop = pa[0];
 pl->pbot = pa[n-1];

 }


static char *
tfname(lvl, num)                /* create temporary file name */

int  lvl, num;

{
    static char  fnbuf[32];

    sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);

    return(fnbuf);
}
Revision:	1.1
Committed:	Sat Feb 22 02:07:26 2003 UTC (22 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R5
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2			static const char RCSid[] = "$Id$";
3			#endif
4			/*
5			* Sorting routines for meta-files
6			*/
7
8
9			#define PBSIZE 1000 /* max size of sort block */
10			/* maxalloc must be >= this */
11
12
13			#define NFILES 4 /* number of sort files */
14
15
16
17			#include "meta.h"
18
19
20
21
22
23
24
25			/*
26			* This sort routine does a combination quicksort and
27			* n-ary mergesort
28			*/
29
30
31			sort(infp, pcmp) /* sort primitives according to pcmp */
32
33			FILE *infp;
34			int (pcmp)(); / compares pointers to pointers to primitives! */
35
36			{
37			PRIMITIVE prims[PBSIZE]; / pointers to primitives */
38			PLIST primlist; /* our primitives list */
39			int nprims;
40			short done;
41
42			do {
43
44			for (nprims = 0; nprims < PBSIZE; nprims++) { /* read to global */
45
46			if ((prims[nprims] = palloc()) == NULL)
47			error(SYSTEM, "memory exhausted in sort");
48
49			readp(prims[nprims], infp);
50
51			if (isglob(prims[nprims]->com))
52			break;
53			}
54
55			qsort(prims, nprims, sizeof(prims), pcmp); / sort pointer array */
56
57			if (nprims < PBSIZE) /* tack on global if one */
58			nprims++;
59
60			order(prims, nprims, &primlist); /* make array into list */
61
62			sendsort(&primlist, pcmp); /* send to merge sorter */
63
64			done = primlist.pbot->com == PEOF;
65
66			plfree(&primlist); /* free up array */
67
68			} while (!done);
69
70			}
71
72
73
74
75
76			/*
77			* The following routine merges up to NFILES sorted primitive files
78			* with 0 or 1 primitive lists. Each set of primitives can end with
79			* 0 or 1 global commands.
80			*/
81
82			mergesort(fi, nf, pl, pcmp, ofp) /* merge sorted files with list */
83
84			FILE fi[]; / array of input files */
85			int nf; /* number of input files */
86			PLIST pl; / sorted list */
87			int (pcmp)(); / comparison function, takes primitive handles */
88			FILE ofp; / output file */
89
90			{
91			PRIMITIVE plp; / position in list */
92			PRIMITIVE pp[NFILES]; / input primitives */
93			int minf;
94			PRIMITIVE *minp;
95			register int i;
96
97			if (pl == NULL)
98			plp = NULL; /* initialize list */
99			else
100			plp = pl->ptop;
101
102			for (i = 0; i < nf; i++) { /* initialize input files */
103			if ((pp[i] = palloc()) == NULL)
104			error(SYSTEM, "memory exhausted in mergesort");
105			readp(pp[i], fi[i]);
106			}
107
108			for ( ; ; ) {
109
110			if (plp != NULL && isprim(plp->com))
111			minp = plp;
112			else
113			minp = NULL;
114
115			for (i = 0; i < nf; i++)
116			if (isprim(pp[i]->com) &&
117			(minp == NULL \|\| (*pcmp)(&pp[i], &minp) < 0))
118			minp = pp[minf=i];
119
120			if (minp == NULL)
121			break;
122
123			writep(minp, ofp);
124
125			if (minp == plp)
126			plp = plp->pnext;
127			else {
128			fargs(pp[minf]);
129			readp(pp[minf], fi[minf]);
130			}
131			}
132
133			if (plp != NULL && plp->com != PEOF)
134			writep(plp, ofp);
135
136			for (i = 0; i < nf; i++) {
137			if (pp[i]->com != PEOF)
138			writep(pp[i], ofp);
139			pfree(pp[i]);
140			}
141
142			}
143
144
145
146			static
147			treemerge(height, nt, nf, pl, pcmp, ofp) /* merge into one file */
148
149			int height, nt, nf;
150			PLIST *pl;
151			int (*pcmp)();
152			FILE *ofp;
153
154			{
155			char *tfname();
156			FILE fi[NFILES], fp;
157			int i;
158
159			if (nf <= NFILES) {
160
161			for (i = 0; i < nf; i++)
162			fi[i] = efopen(tfname(height, i + nt*NFILES), "r");
163
164			if ((fp = ofp) == NULL)
165			fp = efopen(tfname(height + 1, nt), "w");
166
167			mergesort(fi, nf, pl, pcmp, fp);
168
169			for (i = 0; i < nf; i++) {
170			fclose(fi[i]);
171			unlink(tfname(height, i + nt*NFILES));
172			}
173			if (ofp == NULL) {
174			writeof(fp);
175			fclose(fp);
176			}
177
178			} else {
179
180			for (i = 0; i < (nf-1)/NFILES; i++)
181			treemerge(height, i, NFILES, NULL, pcmp, NULL);
182
183			treemerge(height, (nf-1)/NFILES, (nf-1)%NFILES + 1, pl, pcmp, NULL);
184
185			treemerge(height + 1, 0, (nf-1)/NFILES + 1, NULL, pcmp, ofp);
186
187			}
188
189			}
190
191
192
193
194			static
195			sendsort(pl, pcmp) /* send a sorted list */
196
197			PLIST *pl;
198			int (*pcmp)();
199
200			{
201			static int nf = 0,
202			intree = FALSE;
203			FILE *fp;
204
205			if (isglob(pl->pbot->com)) {
206
207			/* send sorted output to stdout */
208			if (intree && nf <= NFILES)
209
210			treemerge(0, 0, nf, pl, pcmp, stdout);
211
212			else if (nf%NFILES == 0)
213
214			if (intree) {
215			treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
216			treemerge(1, 0, nf/NFILES, NULL, pcmp, stdout);
217			} else
218			treemerge(1, 0, nf/NFILES, pl, pcmp, stdout);
219
220			else {
221
222			treemerge(0, nf/NFILES, nf%NFILES, pl, pcmp, NULL);
223			treemerge(1, 0, nf/NFILES + 1, NULL, pcmp, stdout);
224
225			}
226
227			nf = 0; /* all done */
228			intree = FALSE; /* reset for next time */
229
230			} else if (intree && nf%NFILES == 0) {
231
232			/* merge NFILES with list */
233			treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
234			intree = FALSE;
235
236			} else {
237
238			/* output straight to temp file */
239			treemerge(-1, nf++, 0, pl, pcmp, NULL);
240			intree = TRUE;
241
242			}
243
244
245
246			}
247
248
249
250
251			static
252			order(pa, n, pl) /* order the first n array primitives into list */
253
254			PRIMITIVE *pa[];
255			int n;
256			PLIST *pl;
257
258			{
259			register int i;
260
261			for (i = 1; i < n; i++)
262			pa[i-1]->pnext = pa[i];
263
264			pa[n-1]->pnext = NULL;
265			pl->ptop = pa[0];
266			pl->pbot = pa[n-1];
267
268			}
269
270
271
272
273			static char *
274			tfname(lvl, num) /* create temporary file name */
275
276			int lvl, num;
277
278			{
279			static char fnbuf[32];
280
281			sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);
282
283			return(fnbuf);
284			}