src/rt/oocsort.c

/* 
   ==================================================================
   N-way hybrid out-of-core merge sort
   Sorts N blocks internally using quicksort, followed by N-way
   merge using priority queue.
   
   Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
   (c) Fraunhofer Institute for Solar Energy Systems,
       Lucerne University of Applied Sciences & Arts   
   ==================================================================
   
   $Id $
*/


#include "oocsort.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/* Priority queue node */
typedef struct {
   OOC_Sort_Key pri;   /* Record's priority (sort key) */
   unsigned blk;           /* Block containing record */
} OOC_Sort_PQNode;

typedef struct {
   OOC_Sort_PQNode *node;
   unsigned len, tail;
} OOC_Sort_PQueue;

/* Block descriptor */
typedef struct {
   FILE *file;                /* Temporary file */
   char *buf, *head, *tail;   /* Associated I/O buffa, 
                                 head/tail pointers */
} OOC_Sort_Block;


/* Record priority evaluation function */
static OOC_Sort_Key (*pri)(const void *);


static int OOC_Sort_Compare (const void *rec1, const void *rec2)
/* Comparison function for internal sorting */
{
   const OOC_Sort_Key pri1 = pri(rec1), pri2 = pri(rec2);
   
   if (!rec1 || !rec2)
      return 0;
   
   if (pri1 < pri2)
      return -1;
   else if (pri1 > pri2)
      return 1;
   else 
      return 0;
}


static char *OOC_Sort_Read (OOC_Sort_Block *blk, unsigned recSize)
/* Read next record from specified block; return pointer to buffa entry
   or NULL on error */
{
   char *rec = NULL;
         
   if (blk -> head >= blk -> tail) {
      /* Input buffa empty; read next block (potentially truncated if last),
       * where tail marks end of buffa */ 
      const unsigned long bufSize = blk -> tail - blk -> buf;
    
      if (feof(blk -> file))
         return NULL;

      blk -> head = blk -> buf;
      blk -> tail = blk -> buf + fread(blk -> buf, 1, bufSize, blk -> file);
                    
      if (blk -> tail == blk -> head)
         return NULL;
   }
   
   rec = blk -> head;
   blk -> head += recSize;
   
   return rec;
}


static char *OOC_Sort_Peek (OOC_Sort_Block *blk, unsigned recSize)
/* Return next record from specified block WITHOUT removing from buffa */
{
   char *rec = NULL;
   
   if (rec = OOC_Sort_Read(blk, recSize)) {
      /* Restore buffa head */
      blk -> head -= recSize;
   }
   
   return rec;
}


static char *OOC_Sort_Write (OOC_Sort_Block *blk, unsigned recSize,
                             const char *rec)
/* Output record to specified block and return pointer to buffa entry
   or NULL on error */
{
   char *res = NULL;
   
   if (blk -> head >= blk -> tail) {
      /* Flush output buffa (tail marks end of buffa) */
      const unsigned long bufSize = blk -> tail - blk -> buf;

      blk -> head = blk -> buf;
      if (fwrite(blk -> buf, 1, bufSize, blk -> file) != bufSize)
         return NULL;
   }
   
   if (!rec)
      return NULL;
      
   memcpy(blk -> head, rec, recSize);
   res = blk -> head;
   blk -> head += recSize;
   
   return res;
}


#ifdef DEBUG
   static int OOC_Sort_PQCheck (OOC_Sort_PQueue *pq, unsigned root)
   /* Priority queue sanity check */
   {
      unsigned kid;
      
      if (root < pq -> tail) {
         if ((kid = (root << 1) + 1) < pq -> tail)
            if (pq -> node [kid].pri < pq -> node [root].pri)
               return -1;
            else return OOC_Sort_PQCheck(pq, kid);
            
         if ((kid = kid + 1) < pq -> tail)
            if (pq -> node [kid].pri < pq -> node [root].pri)
               return -1;
            else return OOC_Sort_PQCheck(pq, kid);
         
      }
      
      return 0;
   }
#endif


static int OOC_Sort_Push (OOC_Sort_PQueue *pq, OOC_Sort_Key pri,
                          unsigned blk)
/* Insert specified block index into priority queue; return block index 
 * or -1 if queue is full */
{
   OOC_Sort_PQNode *pqn = pq -> node;
   unsigned kid, root;
   
   if (pq -> tail >= pq -> len)
      /* Queue full */
      return -1;
   
   /* Append node at tail and re-sort */
   kid = pq -> tail++;
   
   while (kid) {
      root = kid - 1 >> 1;
      
      /* Compare with parent node and swap if necessary, else terminate */
      if (pri < pqn [root].pri) {
         pqn [kid].pri = pqn [root].pri;
         pqn [kid].blk = pqn [root].blk;
         kid = root;
      }
      else break;
   }
      
   pqn [kid].pri = pri;
   pqn [kid].blk = blk;   

#ifdef DEBUG
   if (OOC_Sort_PQCheck(pq, 0) < 0) {
      fprintf(stderr, "OOC_Sort: priority queue inconsistency\n");
      return -1;
   }
#endif
   
   return blk;
}


static int OOC_Sort_Pop (OOC_Sort_PQueue *pq)
/* Remove head of priority queue and return its block index 
 * or -1 if queue is empty */
{
   OOC_Sort_PQNode *pqn = pq -> node;
   OOC_Sort_Key pri;
   unsigned kid, kid2, root = 0, blk, res;
   
   if (!pq -> tail)
      /* Queue empty */
      return -1;
   
   res = pqn -> blk;
   pri = pqn [--pq -> tail].pri;
   blk = pqn [pq -> tail].blk;

   /* Replace head with tail node and re-sort */
   while ((kid = (root << 1) + 1) < pq -> tail) {
      /* Compare with with smaller kid and swap if necessary, else
       * terminate */
      if ((kid2 = (kid + 1)) < pq -> tail && pqn [kid2].pri < pqn [kid].pri)
         kid = kid2;
            
      if (pri > pqn [kid].pri) {
         pqn [root].pri = pqn [kid].pri;
         pqn [root].blk = pqn [kid].blk;
      }
      else break;
         
      root = kid;
   }
   
   pqn [root].pri = pri;
   pqn [root].blk = blk;

#ifdef DEBUG
   if (OOC_Sort_PQCheck(pq, 0) < 0) {
      fprintf(stderr, "OOC_Sort: priority queue inconsistency\n");
      return -1;
   }
#endif
   
   return res;
}
 
#if 0 
int OOC_Sort (const char *inFile, const char *outFile,
              unsigned long blkSize, unsigned recSize,
              OOC_Sort_Key (*priority)(const void *))
/* Sort records in inFile and output to outFile by (a) internally
 * quicksorting block of blkSize bytes at a time, then (b) merging them
 * via a priority queue. RecSize specifies the size in bytes of each data
 * record. The priority() callback evaluates a record's priority and must be
 * supplied by the caller. */
{
   FILE *in = NULL;
   OOC_Sort_PQueue pqueue;                         /* Priority queue */
   OOC_Sort_Block *iBlk = NULL, oBlk;              /* Block descriptors */ 
   char *rec, *sortBuf = NULL;                     /* Internal sort buffa */
   unsigned bufSize, numBlk;
   int b;
   
   /* Set record priority evaluation callback */                
   pri = priority;
   
   /* Round block and buffa size down to nearest multiple of record size */
   blkSize = (blkSize / recSize) * recSize;
   bufSize = (OOC_SORT_BUFSIZE / recSize) * recSize;

   if (!(in = fopen(inFile, "rb"))) {
      fprintf(stderr, "OOC_Sort: failure opening input file %s\n", inFile);
      return -1;
   }
   
   /* Get input file size and number of blocks (rounded up to nearest
    * multiple of block size) */
   fseek(in, 0, SEEK_END);
   numBlk = (ftell(in) + blkSize - 1) / blkSize;
   rewind(in);
#else

int OOC_Sort (const char *inFile, const char *outFile,
              unsigned numBlk, unsigned recSize,
              OOC_Sort_Key (*priority)(const void *))
/* Sort records in inFile and output to outFile by (a) internally
 * quicksorting numBlk blocks at a time, then (b) merging them via a priority
 * queue.  RecSize specifies the size in bytes of each data record.  The
 * priority() callback evaluates a record's priority (ordinal index) and
 * must be supplied by the caller.  */
{
   FILE *in = NULL;
   OOC_Sort_PQueue pqueue;                         /* Priority queue */
   OOC_Sort_Block *iBlk = NULL, oBlk;              /* Block descriptors */ 
   char *rec, *sortBuf = NULL;                     /* Internal sort buffa */
   unsigned long blkSize;
   unsigned bufSize;
   int b;
   
   /* Set record priority evaluation callback */                
   pri = priority;
   
   /* Round buffa size down to nearest multiple of record size */
   bufSize = (OOC_SORT_BUFSIZE / recSize) * recSize;

   if (!(in = fopen(inFile, "rb"))) {
      fprintf(stderr, "OOC_Sort: failure opening input file %s\n", inFile);
      return -1;
   }
   
   /* Get input file size and block size (in number of records) rounded up
    * to nearest multiple of number of blocks */
   fseek(in, 0, SEEK_END);
   blkSize = (ftell(in) / recSize + numBlk - 1) / numBlk;   
   rewind(in);
#endif

   /* Allocate buffa for internal sorting */
   if (!(sortBuf = malloc(blkSize))) {
      fprintf(stderr, "OOC_Sort: failure allocating internal sort buffer\n");
      return -1;
   }
   
   /* Allocate input blocks */
   if (!(iBlk = calloc(numBlk, sizeof(OOC_Sort_Block)))) {
      fprintf(stderr, "OOC_Sort: failure allocating input blocks\n");
      return -1;
   }
   
   /* ===================================================================
    * Pass 1: Internal quicksort of each input block in sortBuf
    * =================================================================== */

   for (b = 0; b < numBlk; b++) {
      unsigned long numRec;
      
      /* Open temporary file associated with block */
      if (!(iBlk [b].file = tmpfile())) {
         /* fprintf(stderr, "OOC_Sort: failure opening block file\n"); */
         perror("OOC_Sort: failure opening block file");
         return -1;
      }
      
      if (feof(in)) {
         fprintf(stderr, "OOC_Sort: unexpected end of input file %s\n",
                 inFile);
         return -1;
      }
      
      /* Read next block (potentially truncated if last) */
      if (!(numRec = fread(sortBuf, 1, blkSize, in) / recSize)) {
         fprintf(stderr, "OOC_Sort: error reading from input file %s\n",
                 inFile);
         return -1;
      }
         
      /* Quicksort block internally and write out to temp file */
      qsort(sortBuf, numRec, recSize, OOC_Sort_Compare);
      
      if (fwrite(sortBuf, recSize, numRec, iBlk [b].file) != numRec) {
         fprintf(stderr, "OOC_Sort: error writing to block file\n");
         return -1;
      }
      
      rewind(iBlk [b].file);
   }

   /* Close input file and free sort buffa */
   fclose(in);
   free(sortBuf);

   /* Allocate priority queue with numBlk nodes */   
   pqueue.tail = 0;
   pqueue.len = numBlk;
   if (!(pqueue.node = calloc(numBlk, sizeof(OOC_Sort_PQNode)))) {
      fprintf(stderr, "OOC_Sort: failure allocating priority queue\n");
      return -1;
   }
   
   /* Prepare for pass 2: allocate buffa for each input block and initialise
    * fill priority queue with single record from each block */
   for (b = 0; b < numBlk; b++) {
      if (!(iBlk [b].buf = malloc(bufSize))) {
         fprintf(stderr, "OOC_Sort: failure allocating input buffer\n");
         return -1;
      }
      
      /* Peek first record in block file without modifying buffa */
      iBlk [b].head = iBlk [b].tail = iBlk [b].buf + bufSize;
      if (!(rec = OOC_Sort_Peek(iBlk + b, recSize))) {
         fprintf(stderr, "OOC_Sort: error reading from block file\n");
         return -1;
      }
      
      /* Insert record into priority queue */
      if (OOC_Sort_Push(&pqueue, priority(rec), b) < 0) {
         fprintf(stderr, "OOC_Sort: failed priority queue insertion\n");
         return -1;
      }
   }
   
   /* Allocate output buffa and open output file */
   if (!(oBlk.file = fopen(outFile, "wb"))) {
      fprintf(stderr, "OOC_Sort: failure opening output file %s\n", outFile);
      return -1;
   }
   
   if (!(oBlk.head = oBlk.buf = malloc(bufSize))) {
      fprintf(stderr, "OOC_Sort: failure allocating output buffer\n");
      return -1;
   }
   
   /* tail marks end of output buffa */
   oBlk.tail = oBlk.buf + bufSize;
   
   /* ===================================================================
    * Pass 2: External merge of all blocks using priority queue
    * =================================================================== */
      
   do {
      /* Get next node in priority queue, read next record in corresponding
       * block, and send to output */
      b = OOC_Sort_Pop(&pqueue);
            
      if (b >= 0) {
         /* Priority queue non-empty */
         if (!(rec = OOC_Sort_Read(iBlk + b, recSize))) {
            /* Corresponding record should still be in the buffa, so EOF
             * should not happen */
            fprintf(stderr, "OOC_Sort: unexpected EOF in block file\n");
            return -1;
         }
         
         if (!OOC_Sort_Write(&oBlk, recSize, rec)) {
            fprintf(stderr, "OOC_Sort; error writing to output file %s\n",
                    outFile);
            return -1;
         }
         
         /* Peek next record from same block and insert in priority queue */
         if (rec = OOC_Sort_Peek(iBlk + b, recSize))
            /* Buffa not exhausted */
            if (OOC_Sort_Push(&pqueue, priority(rec), b) < 0) {
               fprintf(stderr, "OOC_Sort: failed priority queue insertion\n");
               return -1;
            }
      }
   } while (b >= 0);
   
   /* Priority queue now empty; flush output buffa & close file */
   oBlk.tail = oBlk.head;
   OOC_Sort_Write(&oBlk, 0, NULL);
   fclose(oBlk.file);
   
   for (b = 0; b < numBlk; b++) {
      fclose(iBlk [b].file);
      free(iBlk [b].buf);
   }

   free(iBlk);   
   free(pqueue.node);
   
   return 0;           
}   
Revision:	2.1
Committed:	Tue Feb 24 19:39:26 2015 UTC (10 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Log Message:	Initial check-in of photon map addition by Roland Schregle
#	User	Rev	Content
1	greg	2.1	/*
2			==================================================================
3			N-way hybrid out-of-core merge sort
4			Sorts N blocks internally using quicksort, followed by N-way
5			merge using priority queue.
6
7			Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
8			(c) Fraunhofer Institute for Solar Energy Systems,
9			Lucerne University of Applied Sciences & Arts
10			==================================================================
11
12			$Id $
13			*/
14
15
16			#include "oocsort.h"
17			#include <stdio.h>
18			#include <stdlib.h>
19			#include <string.h>
20
21
22			/* Priority queue node */
23			typedef struct {
24			OOC_Sort_Key pri; /* Record's priority (sort key) */
25			unsigned blk; /* Block containing record */
26			} OOC_Sort_PQNode;
27
28			typedef struct {
29			OOC_Sort_PQNode *node;
30			unsigned len, tail;
31			} OOC_Sort_PQueue;
32
33			/* Block descriptor */
34			typedef struct {
35			FILE file; / Temporary file */
36			char buf, head, tail; / Associated I/O buffa,
37			head/tail pointers */
38			} OOC_Sort_Block;
39
40
41			/* Record priority evaluation function */
42			static OOC_Sort_Key (pri)(const void );
43
44
45			static int OOC_Sort_Compare (const void rec1, const void rec2)
46			/* Comparison function for internal sorting */
47			{
48			const OOC_Sort_Key pri1 = pri(rec1), pri2 = pri(rec2);
49
50			if (!rec1 \|\| !rec2)
51			return 0;
52
53			if (pri1 < pri2)
54			return -1;
55			else if (pri1 > pri2)
56			return 1;
57			else
58			return 0;
59			}
60
61
62			static char OOC_Sort_Read (OOC_Sort_Block blk, unsigned recSize)
63			/* Read next record from specified block; return pointer to buffa entry
64			or NULL on error */
65			{
66			char *rec = NULL;
67
68			if (blk -> head >= blk -> tail) {
69			/* Input buffa empty; read next block (potentially truncated if last),
70			* where tail marks end of buffa */
71			const unsigned long bufSize = blk -> tail - blk -> buf;
72
73			if (feof(blk -> file))
74			return NULL;
75
76			blk -> head = blk -> buf;
77			blk -> tail = blk -> buf + fread(blk -> buf, 1, bufSize, blk -> file);
78
79			if (blk -> tail == blk -> head)
80			return NULL;
81			}
82
83			rec = blk -> head;
84			blk -> head += recSize;
85
86			return rec;
87			}
88
89
90			static char OOC_Sort_Peek (OOC_Sort_Block blk, unsigned recSize)
91			/* Return next record from specified block WITHOUT removing from buffa */
92			{
93			char *rec = NULL;
94
95			if (rec = OOC_Sort_Read(blk, recSize)) {
96			/* Restore buffa head */
97			blk -> head -= recSize;
98			}
99
100			return rec;
101			}
102
103
104			static char OOC_Sort_Write (OOC_Sort_Block blk, unsigned recSize,
105			const char *rec)
106			/* Output record to specified block and return pointer to buffa entry
107			or NULL on error */
108			{
109			char *res = NULL;
110
111			if (blk -> head >= blk -> tail) {
112			/* Flush output buffa (tail marks end of buffa) */
113			const unsigned long bufSize = blk -> tail - blk -> buf;
114
115			blk -> head = blk -> buf;
116			if (fwrite(blk -> buf, 1, bufSize, blk -> file) != bufSize)
117			return NULL;
118			}
119
120			if (!rec)
121			return NULL;
122
123			memcpy(blk -> head, rec, recSize);
124			res = blk -> head;
125			blk -> head += recSize;
126
127			return res;
128			}
129
130
131			#ifdef DEBUG
132			static int OOC_Sort_PQCheck (OOC_Sort_PQueue *pq, unsigned root)
133			/* Priority queue sanity check */
134			{
135			unsigned kid;
136
137			if (root < pq -> tail) {
138			if ((kid = (root << 1) + 1) < pq -> tail)
139			if (pq -> node [kid].pri < pq -> node [root].pri)
140			return -1;
141			else return OOC_Sort_PQCheck(pq, kid);
142
143			if ((kid = kid + 1) < pq -> tail)
144			if (pq -> node [kid].pri < pq -> node [root].pri)
145			return -1;
146			else return OOC_Sort_PQCheck(pq, kid);
147
148			}
149
150			return 0;
151			}
152			#endif
153
154
155			static int OOC_Sort_Push (OOC_Sort_PQueue *pq, OOC_Sort_Key pri,
156			unsigned blk)
157			/* Insert specified block index into priority queue; return block index
158			* or -1 if queue is full */
159			{
160			OOC_Sort_PQNode *pqn = pq -> node;
161			unsigned kid, root;
162
163			if (pq -> tail >= pq -> len)
164			/* Queue full */
165			return -1;
166
167			/* Append node at tail and re-sort */
168			kid = pq -> tail++;
169
170			while (kid) {
171			root = kid - 1 >> 1;
172
173			/* Compare with parent node and swap if necessary, else terminate */
174			if (pri < pqn [root].pri) {
175			pqn [kid].pri = pqn [root].pri;
176			pqn [kid].blk = pqn [root].blk;
177			kid = root;
178			}
179			else break;
180			}
181
182			pqn [kid].pri = pri;
183			pqn [kid].blk = blk;
184
185			#ifdef DEBUG
186			if (OOC_Sort_PQCheck(pq, 0) < 0) {
187			fprintf(stderr, "OOC_Sort: priority queue inconsistency\n");
188			return -1;
189			}
190			#endif
191
192			return blk;
193			}
194
195
196			static int OOC_Sort_Pop (OOC_Sort_PQueue *pq)
197			/* Remove head of priority queue and return its block index
198			* or -1 if queue is empty */
199			{
200			OOC_Sort_PQNode *pqn = pq -> node;
201			OOC_Sort_Key pri;
202			unsigned kid, kid2, root = 0, blk, res;
203
204			if (!pq -> tail)
205			/* Queue empty */
206			return -1;
207
208			res = pqn -> blk;
209			pri = pqn [--pq -> tail].pri;
210			blk = pqn [pq -> tail].blk;
211
212			/* Replace head with tail node and re-sort */
213			while ((kid = (root << 1) + 1) < pq -> tail) {
214			/* Compare with with smaller kid and swap if necessary, else
215			* terminate */
216			if ((kid2 = (kid + 1)) < pq -> tail && pqn [kid2].pri < pqn [kid].pri)
217			kid = kid2;
218
219			if (pri > pqn [kid].pri) {
220			pqn [root].pri = pqn [kid].pri;
221			pqn [root].blk = pqn [kid].blk;
222			}
223			else break;
224
225			root = kid;
226			}
227
228			pqn [root].pri = pri;
229			pqn [root].blk = blk;
230
231			#ifdef DEBUG
232			if (OOC_Sort_PQCheck(pq, 0) < 0) {
233			fprintf(stderr, "OOC_Sort: priority queue inconsistency\n");
234			return -1;
235			}
236			#endif
237
238			return res;
239			}
240
241			#if 0
242			int OOC_Sort (const char inFile, const char outFile,
243			unsigned long blkSize, unsigned recSize,
244			OOC_Sort_Key (priority)(const void ))
245			/* Sort records in inFile and output to outFile by (a) internally
246			* quicksorting block of blkSize bytes at a time, then (b) merging them
247			* via a priority queue. RecSize specifies the size in bytes of each data
248			* record. The priority() callback evaluates a record's priority and must be
249			* supplied by the caller. */
250			{
251			FILE *in = NULL;
252			OOC_Sort_PQueue pqueue; /* Priority queue */
253			OOC_Sort_Block iBlk = NULL, oBlk; / Block descriptors */
254			char rec, sortBuf = NULL; /* Internal sort buffa */
255			unsigned bufSize, numBlk;
256			int b;
257
258			/* Set record priority evaluation callback */
259			pri = priority;
260
261			/* Round block and buffa size down to nearest multiple of record size */
262			blkSize = (blkSize / recSize) * recSize;
263			bufSize = (OOC_SORT_BUFSIZE / recSize) * recSize;
264
265			if (!(in = fopen(inFile, "rb"))) {
266			fprintf(stderr, "OOC_Sort: failure opening input file %s\n", inFile);
267			return -1;
268			}
269
270			/* Get input file size and number of blocks (rounded up to nearest
271			* multiple of block size) */
272			fseek(in, 0, SEEK_END);
273			numBlk = (ftell(in) + blkSize - 1) / blkSize;
274			rewind(in);
275			#else
276
277			int OOC_Sort (const char inFile, const char outFile,
278			unsigned numBlk, unsigned recSize,
279			OOC_Sort_Key (priority)(const void ))
280			/* Sort records in inFile and output to outFile by (a) internally
281			* quicksorting numBlk blocks at a time, then (b) merging them via a priority
282			* queue. RecSize specifies the size in bytes of each data record. The
283			* priority() callback evaluates a record's priority (ordinal index) and
284			* must be supplied by the caller. */
285			{
286			FILE *in = NULL;
287			OOC_Sort_PQueue pqueue; /* Priority queue */
288			OOC_Sort_Block iBlk = NULL, oBlk; / Block descriptors */
289			char rec, sortBuf = NULL; /* Internal sort buffa */
290			unsigned long blkSize;
291			unsigned bufSize;
292			int b;
293
294			/* Set record priority evaluation callback */
295			pri = priority;
296
297			/* Round buffa size down to nearest multiple of record size */
298			bufSize = (OOC_SORT_BUFSIZE / recSize) * recSize;
299
300			if (!(in = fopen(inFile, "rb"))) {
301			fprintf(stderr, "OOC_Sort: failure opening input file %s\n", inFile);
302			return -1;
303			}
304
305			/* Get input file size and block size (in number of records) rounded up
306			* to nearest multiple of number of blocks */
307			fseek(in, 0, SEEK_END);
308			blkSize = (ftell(in) / recSize + numBlk - 1) / numBlk;
309			rewind(in);
310			#endif
311
312			/* Allocate buffa for internal sorting */
313			if (!(sortBuf = malloc(blkSize))) {
314			fprintf(stderr, "OOC_Sort: failure allocating internal sort buffer\n");
315			return -1;
316			}
317
318			/* Allocate input blocks */
319			if (!(iBlk = calloc(numBlk, sizeof(OOC_Sort_Block)))) {
320			fprintf(stderr, "OOC_Sort: failure allocating input blocks\n");
321			return -1;
322			}
323
324			/* ===================================================================
325			* Pass 1: Internal quicksort of each input block in sortBuf
326			* =================================================================== */
327
328			for (b = 0; b < numBlk; b++) {
329			unsigned long numRec;
330
331			/* Open temporary file associated with block */
332			if (!(iBlk [b].file = tmpfile())) {
333			/* fprintf(stderr, "OOC_Sort: failure opening block file\n"); */
334			perror("OOC_Sort: failure opening block file");
335			return -1;
336			}
337
338			if (feof(in)) {
339			fprintf(stderr, "OOC_Sort: unexpected end of input file %s\n",
340			inFile);
341			return -1;
342			}
343
344			/* Read next block (potentially truncated if last) */
345			if (!(numRec = fread(sortBuf, 1, blkSize, in) / recSize)) {
346			fprintf(stderr, "OOC_Sort: error reading from input file %s\n",
347			inFile);
348			return -1;
349			}
350
351			/* Quicksort block internally and write out to temp file */
352			qsort(sortBuf, numRec, recSize, OOC_Sort_Compare);
353
354			if (fwrite(sortBuf, recSize, numRec, iBlk [b].file) != numRec) {
355			fprintf(stderr, "OOC_Sort: error writing to block file\n");
356			return -1;
357			}
358
359			rewind(iBlk [b].file);
360			}
361
362			/* Close input file and free sort buffa */
363			fclose(in);
364			free(sortBuf);
365
366			/* Allocate priority queue with numBlk nodes */
367			pqueue.tail = 0;
368			pqueue.len = numBlk;
369			if (!(pqueue.node = calloc(numBlk, sizeof(OOC_Sort_PQNode)))) {
370			fprintf(stderr, "OOC_Sort: failure allocating priority queue\n");
371			return -1;
372			}
373
374			/* Prepare for pass 2: allocate buffa for each input block and initialise
375			* fill priority queue with single record from each block */
376			for (b = 0; b < numBlk; b++) {
377			if (!(iBlk [b].buf = malloc(bufSize))) {
378			fprintf(stderr, "OOC_Sort: failure allocating input buffer\n");
379			return -1;
380			}
381
382			/* Peek first record in block file without modifying buffa */
383			iBlk [b].head = iBlk [b].tail = iBlk [b].buf + bufSize;
384			if (!(rec = OOC_Sort_Peek(iBlk + b, recSize))) {
385			fprintf(stderr, "OOC_Sort: error reading from block file\n");
386			return -1;
387			}
388
389			/* Insert record into priority queue */
390			if (OOC_Sort_Push(&pqueue, priority(rec), b) < 0) {
391			fprintf(stderr, "OOC_Sort: failed priority queue insertion\n");
392			return -1;
393			}
394			}
395
396			/* Allocate output buffa and open output file */
397			if (!(oBlk.file = fopen(outFile, "wb"))) {
398			fprintf(stderr, "OOC_Sort: failure opening output file %s\n", outFile);
399			return -1;
400			}
401
402			if (!(oBlk.head = oBlk.buf = malloc(bufSize))) {
403			fprintf(stderr, "OOC_Sort: failure allocating output buffer\n");
404			return -1;
405			}
406
407			/* tail marks end of output buffa */
408			oBlk.tail = oBlk.buf + bufSize;
409
410			/* ===================================================================
411			* Pass 2: External merge of all blocks using priority queue
412			* =================================================================== */
413
414			do {
415			/* Get next node in priority queue, read next record in corresponding
416			* block, and send to output */
417			b = OOC_Sort_Pop(&pqueue);
418
419			if (b >= 0) {
420			/* Priority queue non-empty */
421			if (!(rec = OOC_Sort_Read(iBlk + b, recSize))) {
422			/* Corresponding record should still be in the buffa, so EOF
423			* should not happen */
424			fprintf(stderr, "OOC_Sort: unexpected EOF in block file\n");
425			return -1;
426			}
427
428			if (!OOC_Sort_Write(&oBlk, recSize, rec)) {
429			fprintf(stderr, "OOC_Sort; error writing to output file %s\n",
430			outFile);
431			return -1;
432			}
433
434			/* Peek next record from same block and insert in priority queue */
435			if (rec = OOC_Sort_Peek(iBlk + b, recSize))
436			/* Buffa not exhausted */
437			if (OOC_Sort_Push(&pqueue, priority(rec), b) < 0) {
438			fprintf(stderr, "OOC_Sort: failed priority queue insertion\n");
439			return -1;
440			}
441			}
442			} while (b >= 0);
443
444			/* Priority queue now empty; flush output buffa & close file */
445			oBlk.tail = oBlk.head;
446			OOC_Sort_Write(&oBlk, 0, NULL);
447			fclose(oBlk.file);
448
449			for (b = 0; b < numBlk; b++) {
450			fclose(iBlk [b].file);
451			free(iBlk [b].buf);
452			}
453
454			free(iBlk);
455			free(pqueue.node);
456
457			return 0;
458			}