/*@z45.c:External Sort:SortFile()@********************************************/ /* */ /* THE LOUT DOCUMENT FORMATTING SYSTEM (VERSION 3.36) */ /* COPYRIGHT (C) 1991, 2007 Jeffrey H. Kingston */ /* */ /* Jeffrey H. Kingston (jeff@it.usyd.edu.au) */ /* School of Information Technologies */ /* 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 3, 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 */ /*****************************************************************************/ /* */ /* int ReadOneLine(FILE *fp, char *buff, int buff_len) */ /* */ /* Read one line of fp, up to and including the following newline */ /* sequence, which may be a CH_LF/CH_CR pair as well as singleton. */ /* Place the contents of the line into *buff, including a concluding */ /* \0 but never the concluding newline sequence. */ /* */ /* The buffer has space for buff_len characters including the concluding */ /* \0. If space runs out, terminate the read early; the unread portion */ /* will be read by the next call to ReadOneLine(). This code assumes */ /* that buff_len is at least 2. */ /* */ /* Return values are as follows: */ /* */ /* 0 Did not read a line because EOF was encountered immediately */ /* 1 Successfully read a line, empty or otherwise, into *buff */ /* 2 Read a line but had to stop early owing to buffer overflow */ /* */ /*****************************************************************************/ int ReadOneLine(FILE *fp, FULL_CHAR *buff, int buff_len) { int ch; int len1 = buff_len - 1; /* read characters up to the end of line or file */ int count = 0; while( (ch = getc(fp)) != EOF && ch != CH_LF && ch != CH_CR ) { buff[count++] = ch; if( count >= len1 ) { /* out of space, have to stop early */ buff[count++] = '\0'; return 2; } } /* terminate gracefully depending what character we stopped at */ if( ch == EOF ) { if( count == 0 ) return 0; } else if( ch == CH_LF ) { /* consume any immediately following CH_CR too */ ch = getc(fp); if( ch != CH_CR ) ungetc(ch, fp); } else /* ch == CH_CR */ { /* consume any immediately following CH_LF too */ ch = getc(fp); if( ch != CH_LF ) ungetc(ch, fp); } buff[count++] = '\0'; return 1; } /* end ReadOneLine */ /*****************************************************************************/ /* */ /* 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. */ /* */ /* As for ReadOneLine above, lines may be terminated by a one or two */ /* character newline sequence, but these characters are never included */ /* in the lines returned. */ /* */ /* 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 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 == CH_LF || ch == CH_CR ) { *bp++ = '\0'; debug1(DEX, D, " finished line: %s", *(lp-1)); /* get rid of following character if part of two-character line ending */ if( ch == CH_LF ) { ch = getc(fp); if( ch != CH_CR ) ungetc(ch, fp); } else /* ch == CH_CR */ { ch = getc(fp); if( ch != CH_LF ) ungetc(ch, fp); } /* 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((char *) STR_NEWLINE, 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_FILE); 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_FILE); 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); }