Listing 8 An external sort program

/* esort: Sort large files by merging subfiles */

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINES 1000
#define MAXSUBFILES 15

struct subfile
{
   FILE *f;
   char line[BUFSIZ];
};

int comp(const void *, const void *);
void make_subfile(char *[], sizet,
  struct subfile *, size_t);

main()
{
   int i, merge_flag = 0;
   size_t nlines, nfiles = 0, min_idx;
   static char s[BUFSIZ], *lines[MAXLINES];
   static struct subfile subfiles[MAXSUBFILES];

   /* Read file - form subfiles if needed */
   for (nlines = 0; fgets(s,BUFSIZ,stdin); ++nlines)
   {
      if (nlines == MAXLINES ||
        (lines[nlines] = malloc(strlen(s)+1)) == NULL)
      {
          /* Sort lines to a temporary merge file */
          merge_flag = 1;
          make_subfile(lines,nlines,subfiles,nfiles++);
          line[nlines = O] = malloc(strlen(s)+1);
          assert(lines[O] != NULL);
       }
       strcpy(lines[nlines],s);
   }

   if (merge_flag)
   {
       /* Form last merge file from remaining lines */
       make_subfile(lines,nlines,subfiles,nfiles++};
       /* Prepare to read temporary files */
       for (i = 0; i < nfiles; ++i)
       {
          FILE *f = subfiles[i].f;
          rewind(f);
          fgets(subfiles[i].line,BUFSIZ,f);
       }

       /* Do the merge */
       while (nfiles)
       {
          struct subfile *sfp;

          /* Find next output line */
          for (min_idx = 0, i = 1; i < nfiles; ++i)
             if (strcmp(subfiles[i].line,
                      subfiles[min_idx].line) < 0)
                min_idx = i;
          sfp = &subfiles[min_idx];

          /* Output the line */
          fputs(sfp->line,stdout);
          fflush(stdout);
          assert(!ferror(stdout));

          /* Get the next line from this file */
          if (fgets(sfp->line,BUFSIZ,sfp->f) == NULL)
             subfiles[min_idx] = subfiles[--nfiles];
       }
   }
   else
   {
       /* Sort singleton file */
       qsort(lines,nlines,sizeof lines[0],comp);
       for (i = 0; i < nlines; ++i)
       {
          fputs (lines[i],stdout);
          fflush(stdout);
          assert(!ferror(stdout));
       }
   }

   return 0;
}

int comp(const void *p1, const void *p2)
{
   return strcmp(* (char **) pl, * (char **) p2);
}

void make_subfile(char *lines[],size_t nl, struct subfile subf[],size_t nf}
{
   int i;
   FILE *f = tmpfile();
   assert(f);

   /* Write sorted subfile to temporary file */
   qsort(lines,nl,sizeof lines[O],comp);
   for (i = 0; i < nl; ++i)
   {
       fputs(lines[i],f);
       fflush(f);
       assert(!ferror(f));
       free (lines[i]);
   }
   subf[nf].f = f;
}

/* End of File */