src/meta/sort.c

#ifndef lint
static const char       RCSid[] = "$Id: sort.c,v 1.7 2003/10/21 19:19:28 schorsch Exp $";
#endif
/*
 *   Sorting routines for meta-files
 */

#include  "platform.h"  /* [_]snprintf() */
#include  "rtprocess.h" /* getpid() */
#include  "rterror.h"
#include  "meta.h"


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

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


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

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


void
sort(           /* 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.
 */

void
pmergesort(     /* 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 = 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]);
    }

}


static void
treemerge(      /* merge into one file */

int  height, int nt, int nf,
PLIST  *pl,
int  (*pcmp)(),
FILE  *ofp
)
{
    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);
            
    }

}


static void
sendsort(               /* send a sorted list */

PLIST  *pl,
int  (*pcmp)()
)
{
    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;

    }


}


static void
order(  /* 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(         /* create temporary file name */

int  lvl, int num
)
{
        static char  pathbuf[PATH_MAX];
    static char  fnbuf[PATH_MAX];
        static size_t psiz;

        if (pathbuf[0] == '\0') { /* first time */
                temp_directory(pathbuf, sizeof(pathbuf));
                psiz = strlen(pathbuf);
        }
        snprintf(fnbuf, sizeof(pathbuf)-psiz,
                        "%s/S%d%c%d", pathbuf, getpid(), lvl+'A', num);
    /*sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);*/

    return(fnbuf);
}
Revision:	1.8
Committed:	Sat Nov 15 02:13:37 2003 UTC (21 years, 1 month ago) by schorsch
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, rad5R2, rad4R2P2, rad5R0, rad5R1, rad3R7P2, rad3R7P1, rad4R2, rad4R1, rad4R0, rad3R6, rad3R6P1, rad3R8, rad3R9, rad4R2P1, rad5R3, HEAD
Changes since 1.7:	+2 -3 lines
Log Message:	Continued ANSIfication, and reduced other compile warnings.
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	schorsch	1.8	static const char RCSid[] = "$Id: sort.c,v 1.7 2003/10/21 19:19:28 schorsch Exp $";
3	greg	1.1	#endif
4			/*
5			* Sorting routines for meta-files
6			*/
7
8	schorsch	1.7	#include "platform.h" /* [_]snprintf() */
9	schorsch	1.6	#include "rtprocess.h" /* getpid() */
10			#include "rterror.h"
11	schorsch	1.2	#include "meta.h"
12	schorsch	1.3
13	greg	1.1
14			#define PBSIZE 1000 /* max size of sort block */
15			/* maxalloc must be >= this */
16
17			#define NFILES 4 /* number of sort files */
18
19
20	schorsch	1.2	static void treemerge(int height, int nt, int nf, PLIST *pl,
21			int (pcmp)(), FILE ofp);
22			static void sendsort( PLIST pl, int (pcmp)());
23			static void order(PRIMITIVE pa[], int n, PLIST pl);
24			static char * tfname( int lvl, int num);
25	greg	1.1
26			/*
27			* This sort routine does a combination quicksort and
28			* n-ary mergesort
29			*/
30
31
32	schorsch	1.2	void
33			sort( /* sort primitives according to pcmp */
34			FILE *infp,
35			int (pcmp)() / compares pointers to pointers to primitives! */
36			)
37	greg	1.1	{
38			PRIMITIVE prims[PBSIZE]; / pointers to primitives */
39			PLIST primlist; /* our primitives list */
40			int nprims;
41			short done;
42
43			do {
44
45			for (nprims = 0; nprims < PBSIZE; nprims++) { /* read to global */
46
47			if ((prims[nprims] = palloc()) == NULL)
48			error(SYSTEM, "memory exhausted in sort");
49
50			readp(prims[nprims], infp);
51
52			if (isglob(prims[nprims]->com))
53			break;
54			}
55
56			qsort(prims, nprims, sizeof(prims), pcmp); / sort pointer array */
57
58			if (nprims < PBSIZE) /* tack on global if one */
59			nprims++;
60
61			order(prims, nprims, &primlist); /* make array into list */
62
63			sendsort(&primlist, pcmp); /* send to merge sorter */
64
65			done = primlist.pbot->com == PEOF;
66
67			plfree(&primlist); /* free up array */
68
69			} while (!done);
70
71			}
72
73
74
75
76
77			/*
78			* The following routine merges up to NFILES sorted primitive files
79			* with 0 or 1 primitive lists. Each set of primitives can end with
80			* 0 or 1 global commands.
81			*/
82
83	schorsch	1.2	void
84	greg	1.5	pmergesort( /* merge sorted files with list */
85	greg	1.1
86	schorsch	1.2	FILE fi[], / array of input files */
87			int nf, /* number of input files */
88			PLIST pl, / sorted list */
89			int (pcmp)(), / comparison function, takes primitive handles */
90			FILE ofp / output file */
91			)
92	greg	1.1	{
93			PRIMITIVE plp; / position in list */
94			PRIMITIVE pp[NFILES]; / input primitives */
95	schorsch	1.8	int minf = 0;
96	greg	1.1	PRIMITIVE *minp;
97			register int i;
98
99			if (pl == NULL)
100			plp = NULL; /* initialize list */
101			else
102			plp = pl->ptop;
103
104			for (i = 0; i < nf; i++) { /* initialize input files */
105			if ((pp[i] = palloc()) == NULL)
106	greg	1.5	error(SYSTEM, "memory exhausted in pmergesort");
107	greg	1.1	readp(pp[i], fi[i]);
108			}
109
110			for ( ; ; ) {
111
112			if (plp != NULL && isprim(plp->com))
113			minp = plp;
114			else
115			minp = NULL;
116
117			for (i = 0; i < nf; i++)
118			if (isprim(pp[i]->com) &&
119			(minp == NULL \|\| (*pcmp)(&pp[i], &minp) < 0))
120			minp = pp[minf=i];
121
122			if (minp == NULL)
123			break;
124
125			writep(minp, ofp);
126
127			if (minp == plp)
128			plp = plp->pnext;
129			else {
130			fargs(pp[minf]);
131			readp(pp[minf], fi[minf]);
132			}
133			}
134
135			if (plp != NULL && plp->com != PEOF)
136			writep(plp, ofp);
137
138			for (i = 0; i < nf; i++) {
139			if (pp[i]->com != PEOF)
140			writep(pp[i], ofp);
141			pfree(pp[i]);
142			}
143
144			}
145
146
147
148	schorsch	1.2	static void
149			treemerge( /* merge into one file */
150	greg	1.1
151	schorsch	1.2	int height, int nt, int nf,
152			PLIST *pl,
153			int (*pcmp)(),
154			FILE *ofp
155			)
156	greg	1.1	{
157			FILE fi[NFILES], fp;
158			int i;
159
160			if (nf <= NFILES) {
161
162			for (i = 0; i < nf; i++)
163			fi[i] = efopen(tfname(height, i + nt*NFILES), "r");
164
165			if ((fp = ofp) == NULL)
166			fp = efopen(tfname(height + 1, nt), "w");
167
168	greg	1.5	pmergesort(fi, nf, pl, pcmp, fp);
169	greg	1.1
170			for (i = 0; i < nf; i++) {
171			fclose(fi[i]);
172			unlink(tfname(height, i + nt*NFILES));
173			}
174			if (ofp == NULL) {
175			writeof(fp);
176			fclose(fp);
177			}
178
179			} else {
180
181			for (i = 0; i < (nf-1)/NFILES; i++)
182			treemerge(height, i, NFILES, NULL, pcmp, NULL);
183
184			treemerge(height, (nf-1)/NFILES, (nf-1)%NFILES + 1, pl, pcmp, NULL);
185
186			treemerge(height + 1, 0, (nf-1)/NFILES + 1, NULL, pcmp, ofp);
187
188			}
189
190			}
191
192
193
194
195	schorsch	1.2	static void
196			sendsort( /* send a sorted list */
197	greg	1.1
198	schorsch	1.2	PLIST *pl,
199			int (*pcmp)()
200			)
201	greg	1.1	{
202			static int nf = 0,
203			intree = FALSE;
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	schorsch	1.2	static void
251			order( /* order the first n array primitives into list */
252	greg	1.1
253	schorsch	1.2	PRIMITIVE *pa[],
254			int n,
255			PLIST *pl
256			)
257	greg	1.1	{
258			register int i;
259
260			for (i = 1; i < n; i++)
261			pa[i-1]->pnext = pa[i];
262
263			pa[n-1]->pnext = NULL;
264			pl->ptop = pa[0];
265			pl->pbot = pa[n-1];
266
267			}
268
269
270
271
272			static char *
273	schorsch	1.2	tfname( /* create temporary file name */
274	greg	1.1
275	schorsch	1.2	int lvl, int num
276			)
277	greg	1.1	{
278	schorsch	1.2	static char pathbuf[PATH_MAX];
279	schorsch	1.3	static char fnbuf[PATH_MAX];
280			static size_t psiz;
281	greg	1.1
282	schorsch	1.3	if (pathbuf[0] == '\0') { /* first time */
283			temp_directory(pathbuf, sizeof(pathbuf));
284			psiz = strlen(pathbuf);
285			}
286	schorsch	1.4	snprintf(fnbuf, sizeof(pathbuf)-psiz,
287	schorsch	1.3	"%s/S%d%c%d", pathbuf, getpid(), lvl+'A', num);
288	schorsch	1.2	/sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);/
289	greg	1.1
290	schorsch	1.3	return(fnbuf);
291	greg	1.1	}