/*@z45.c:External Sort:SortFile()@********************************************/
/* */
/* THE LOUT DOCUMENT FORMATTING SYSTEM (VERSION 3.17) */
/* COPYRIGHT (C) 1991, 1999 Jeffrey H. Kingston */
/* */
/* Jeffrey H. Kingston (jeff@cs.usyd.edu.au) */
/* Basser Department of Computer Science */
/* The University of Sydney 2006 */
/* AUSTRALIA */
/* */
/* This program is free software; you can redistribute it and/or modify */
/* it under the terms of the GNU General Public License as published by */
/* the Free Software Foundation; either Version 2, or (at your option) */
/* any later version. */
/* */
/* This program is distributed in the hope that it will be useful, */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
/* GNU General Public License for more details. */
/* */
/* You should have received a copy of the GNU General Public License */
/* along with this program; if not, write to the Free Software */
/* Foundation, Inc., 59 Temple Place, Suite 330, Boston MA 02111-1307 USA */
/* */
/* FILE: z45.c */
/* MODULE: External Sort */
/* EXTERNS: SortFile() */
/* */
/* This simple sort utility assumes that the source file can all be read */
/* into memory. If not, you get an "out of memory" error message. */
/* */
/*****************************************************************************/
#include "externs.h"
#define BUFF_SIZE 4096 /* size of one memory buffer */
#define LINES_GUESS 2000 /* initial guess of number of lines */
/*****************************************************************************/
/* */
/* LINE *ReadLines(FILE *fp, FULL_CHAR *fname, FULL_CHAR *first_line, *len) */
/* */
/* Read all of the lines of fp into memory and return a null-terminated */
/* array of pointers to these lines, and set *len to the number of lines. */
/* Make sure the lines themselves are null-terminated, also. */
/* */
/* fname is the name of the file being sorted, and is used for error */
/* messages only. */
/* */
/* if first_line is non-null then it is a pointer to a string which is */
/* to become as the first line of the result. This string needs copying. */
/* */
/*****************************************************************************/
LINE *ReadLines(FILE *fp, FULL_CHAR *fname, FULL_CHAR *first_line, int *len)
{
char *buff; /* the current input line buffer */
char *buff_top; /* first spot off end of buffer */
char *bp; /* first free spot in buff */
LINE *lines; /* the array of pointers to lines */
int lines_length; /* the length of the lines array */
LINE *lines_top; /* first spot off end of lines */
LINE *lp; /* first free spot in lines */
char *p, *q;
int ch;
debug1(DEX, D, "ReadLines(-, %s, -)", fname);
/* initialize buff to be empty with size BUFF_SIZE */
buff = malloc(BUFF_SIZE * sizeof(char));
if( buff == NULL )
Error(45, 1, "run out of memory when reading index file %s",
FATAL, no_fpos, fname);
buff_top = buff + BUFF_SIZE;
bp = buff;
/* initialize the lines buffer to be the first line */
lines_length = LINES_GUESS;
lines = malloc(lines_length * sizeof(LINE *));
lines_top = &lines[lines_length];
lp = lines;
/* add first_line to lines buffer if required */
if( first_line != (FULL_CHAR *) null )
{
*lp = malloc((StringLength(first_line) + 1) * sizeof(char));
StringCopy( (char *) *lp, first_line);
lp++;
}
*lp++ = bp;
while( (ch = getc(fp)) != EOF )
{
debug4(DEX, DD, "lines: [%d %d(%d) %d]",
(int) lines, (int) (lp-1), (int) *(lp-1), (int) lines_top -1);
debug3(DEX, DD, " buff: [%d bp %d %d]",
(int) buff, (int) bp, (int) buff_top - 1);
assert( (int) buff >= (int) lines_top ||
(int) buff_top <= (int) lines,
"ReadLines: lines and buff overlap!" );
/* get new buffer and copy current line across if out of buff space */
if( bp == buff_top )
{
debug0(DEX, D, " getting new buff");
buff = malloc(BUFF_SIZE * sizeof(char));
if( buff == NULL )
Error(45, 2, "run out of memory when reading index file %s",
FATAL, no_fpos, fname);
buff_top = buff + BUFF_SIZE;
for( p = buff, q = *(lp-1); q != bp; *p++ = *q++ );
bp = p; *bp = '\0';
debug1(DEX, D, " copied into new buff: %s", buff);
*(lp-1) = buff;
if( bp == buff_top )
Error(45, 3, "line too long when reading index file %s",
FATAL, no_fpos, fname);
}
/* if newline char, end this line and start the next */
if( ch == '\n' )
{
*bp++ = '\0';
debug1(DEX, D, " finished line: %s", *(lp-1));
/* if no room in lines for next line, double its size */
if( lp == lines_top )
{
debug1(DEX, D, " realloc(lines, %d)", 2 * lines_length);
lines = realloc(lines, 2 * lines_length * sizeof(LINE *));
if( lines == NULL )
Error(45, 4, "run out of memory when reading index file %s",
FATAL, no_fpos, fname);
lp = &lines[lines_length];
lines_length = 2 * lines_length;
lines_top = &lines[lines_length];
}
*lp++ = bp;
}
else /* ordinary char with space available, so just add it */
{
*bp++ = ch;
}
}
*len = (lp - lines - 1);
debug1(DEX, D, "ReadLines returning (len = %d)", *len);
return lines;
} /* end ReadLines */
/*****************************************************************************/
/* */
/* WriteLines(FILE *fp, LINE *lines, int len) */
/* */
/* Write array of lines "lines", of length len, to file fp. */
/* */
/*****************************************************************************/
void WriteLines(FILE *fp, LINE *lines, int len)
{ int i;
for( i = 0; i < len; i++ )
{ fputs(lines[i], fp);
fputs("\n", fp);
}
}
/*****************************************************************************/
/* */
/* Line comparison functions (for qsort) */
/* */
/* By Jeff Kingston and Valery Ushakov (uwe). */
/* */
/*****************************************************************************/
static int pstrcmp(const void *a, const void *b) /* !UseCollate */
{
return strcmp (*(char **)a, *(char **)b);
}
static int pstrcollcmp(const void *a, const void *b) /* UseCollate */
{
return strcollcmp (*(char **)a, *(char**)b);
}
/*****************************************************************************/
/* */
/* void SortLines(LINE *lines, int lines_len) */
/* */
/* Sort the given lines. */
/* */
/*****************************************************************************/
void SortLines(LINE *lines, int lines_len)
{
qsort(lines, lines_len, sizeof(LINE), (UseCollate ? pstrcollcmp : pstrcmp));
}
/*****************************************************************************/
/* */
/* void SortFile(char *infile, char *outfile) */
/* */
/* Sort file infile, placing the result on file outfile. */
/* */
/*****************************************************************************/
void SortFile(FULL_CHAR *infile, FULL_CHAR *outfile)
{
LINE *lines;
int lines_len;
FILE *in_fp, *out_fp;
debug2(DEX, D, "SortFile(%s, %s)", infile, outfile);
/* open input file */
in_fp = fopen( (char *) infile, READ_BINARY);
if( in_fp == (FILE *) NULL )
Error(45, 5, "cannot open index file %s for reading",
FATAL, no_fpos, outfile);
/* open output file */
out_fp = fopen( (char *) outfile, WRITE_BINARY);
if( out_fp == (FILE *) NULL )
Error(45, 6, "cannot open index file %s for writing",
FATAL, no_fpos, outfile);
/* read lines, sort them, and write them out again sorted */
lines = ReadLines(in_fp, infile, (FULL_CHAR *) NULL, &lines_len);
SortLines(lines, lines_len);
fclose(in_fp);
WriteLines(out_fp, lines, lines_len);
fclose(out_fp);
}
