home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / t / tags18.zip / SORT.C < prev    next >
C/C++ Source or Header  |  1992-05-03  |  50KB  |  1,831 lines
  1. /* sort.c - sort lines of text (with all kinds of options).
  2.    Copyright 1989 Free Software Foundation
  3.                   Written December 1988 by Mike Haertel.
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 1, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.    The author may be reached (Email) at the address mike@ai.mit.edu,
  20.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  21.  
  22. /* MS-DOS port (c) 1990 by Thorsten Ohl, td12@ddagsi3.bitnet
  23.    This port is also distributed under the terms of the
  24.    GNU General Public License as published by the
  25.    Free Software Foundation.
  26.  
  27.    $Header: e:/gnu/sort/RCS/sort.c'v 0.3.0.4 90/08/26 19:03:05 tho Exp $
  28.  */
  29.  
  30. static char version[] = "GNU sort, version 0.3";
  31.  
  32. #include "std.h"
  33.  
  34. #ifndef MSDOS
  35. #include "unix.h"
  36. #endif /* not MSDOS */
  37.  
  38. #ifdef SORT_MODULE
  39. #include "sort.h"
  40. #endif
  41.  
  42. #include <errno.h>
  43. #include <signal.h>
  44. #include <stdio.h>
  45. #include <string.h>
  46.  
  47. #ifdef MSDOS
  48. #include <process.h>
  49. static void cleanup (void);
  50. static void assert_lines (int lines);
  51. void *xmalloc (unsigned int size);
  52. void *xrealloc (void *ptr, unsigned int size);
  53. static FILE *xfopen (char *file, char *how);
  54. static void xfclose (FILE *fp);
  55. static void xfwrite (char *buf, int size, int nelem, FILE *fp);
  56. static char *tempname (void);
  57. static void zaptemp (char *name);
  58. static void inittables (void);
  59. static void initbuf (struct buffer *buf, int alloc);
  60. static int fillbuf (struct buffer *buf, FILE *fp);
  61. static void initlines (struct lines *lines, int alloc);
  62. static char *begfield (struct line *line, struct keyfield *key);
  63. static char *limfield (struct line *line, struct keyfield *key);
  64. static void findlines (struct buffer *buf, struct lines *lines);
  65. static int fraccompare (char *a, char *b);
  66. static int numcompare (char *a, char *b);
  67. static int getmonth (char *s, int len);
  68. static int keycompare (struct line *a, struct line *b);
  69. static int compare (struct line *a, struct line *b);
  70. static int checkfp (FILE *fp);
  71. static void mergefps (FILE **fps, int nfps, FILE *ofp);
  72. static void sortlines (struct line *lines, int nlines, struct line *temp);
  73. static int check (char **files, int nfiles);
  74. static void merge (char **files, int nfiles, FILE *ofp);
  75. static void sort (char **files, int nfiles, FILE *ofp);
  76. static void insertkey (struct keyfield *key);
  77. static void usage (void);
  78. static void badfieldspec (char *s);
  79. static void __cdecl inthandler (void);
  80. #ifndef SORT_MODULE
  81. int main (int argc, char **argv);
  82. #endif
  83. #endif /* MSDOS */
  84.  
  85. /* A few useful macros. */
  86. #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
  87. #define MIN(a, b) ((a) < (b) ? (a) : (b))
  88. #define UCHAR_LIM (UCHAR_MAX + 1)
  89. #define UCHAR(c) ((unsigned char) (c))
  90.  
  91. /* Table of digits. */
  92. static int digits[UCHAR_LIM];
  93.  
  94. /* Table of white space. */
  95. static int blanks[UCHAR_LIM];
  96.  
  97. /* Table of non-printing characters. */
  98. static int nonprinting[UCHAR_LIM];
  99.  
  100. /* Table of non-dictionary characters (not letters, digits, or blanks). */
  101. static int nondictionary[UCHAR_LIM];
  102.  
  103. /* Translation table folding upper case to lower. */
  104. static char fold_tolower[UCHAR_LIM];
  105.  
  106. /* Table mapping 3-letter month names to integers.
  107.    Alphabetic order allows binary search. */
  108. static struct month {
  109.   char *name;
  110.   int val;
  111. } monthtab[] = {
  112.   "apr", 4,
  113.   "aug", 8,
  114.   "dec", 12,
  115.   "feb", 2,
  116.   "jan", 1,
  117.   "jul", 7,
  118.   "jun", 6,
  119.   "mar", 3,
  120.   "may", 5,
  121.   "nov", 11,
  122.   "oct", 10,
  123.   "sep", 9
  124. };
  125.  
  126. /* During the merge phase, the number of files to merge at once. */
  127. #ifdef MSDOS
  128. /* 14 (= 20 - 5 - 1) is a hard upper limit for MeSsy DOS versions <3.2
  129.    (and a soft one for later versions...) */
  130. #define NMERGE 12
  131. #else /* not MSDOS */
  132. #define NMERGE 16
  133. #endif /* not MSDOS */
  134.  
  135. /* Initial buffer size for in core sorting.  Will not grow unless a
  136.    line longer than this is seen. */
  137. #ifdef MSDOS
  138. static int sortalloc = 32767;
  139. #else /* not MSDOS */
  140. static int sortalloc = 524288;
  141. #endif /* not MSDOS */
  142.  
  143. /* Initial buffer size for in core merge buffers.  Bear in mind that
  144.    up to NMERGE * mergealloc bytes may be allocated for merge buffers. */
  145. static int mergealloc = 16384;
  146.  
  147. /* Guess of average line length. */
  148. static int linelength = 30;
  149.  
  150. /* Prefix for temporary file names. */
  151. #ifdef MSDOS
  152. static char *prefix;
  153. #else /* not MSDOS */
  154. static char *prefix = "/tmp";
  155. #endif /* not MSDOS */
  156.  
  157. /* Flag to reverse the order of all comparisons. */
  158. static int reverse;
  159.  
  160. /* Tab character separating fields.  If NUL, then fields are separated
  161.    by the empty string between a non-whitespace character and a whitespace
  162.    character. */
  163. static char tab;
  164.  
  165. /* Flag to remove consecutive duplicate lines from the output.
  166.    Only the last of a sequence of equal lines will be output. */
  167. static int unique;
  168.  
  169. /* Lines are held in core as counted strings. */
  170. struct line
  171. {
  172.   char *text;                   /* Text of the line. */
  173.   int length;                   /* Length not including final newline. */
  174.   char *keybeg;                 /* Start of first key. */
  175.   char *keylim;                 /* Limit of first key. */
  176. };
  177.  
  178. #ifdef MSDOS
  179. /* Using _huge line arrays under MS-DOS is terribly inefficient, so we
  180.    impose an upper limit on the number of lines cosidered at once.  The
  181.    user can break the input into digestable pieces by using the `-S' option
  182.    to adjust the input buffer size.
  183.    This only matters for files with very short lines ( < 8 chars).  */
  184. static int maxlines
  185.   = (int) (((1L << 16) - 1L) / sizeof (struct line));
  186.  
  187. void
  188. assert_lines (int lines)
  189. {
  190.   if (lines >= maxlines)
  191.     {
  192.       fprintf (stderr,
  193.                "sort: the number of lines per input buffer is restricted in\n"
  194.                "      the MS-DOS version.  For files with short lines, use\n"
  195.                "      the `-S <num>' option to reduce the buffer size.\n");
  196.       cleanup ();
  197. #ifdef SORT_MODULE
  198.       external_cleanup();
  199. #endif
  200.       exit (-1);
  201.     }
  202. }
  203. #endif /* MSDOS */
  204.  
  205. /* Arrays of lines. */
  206. struct lines
  207. {
  208.   struct line *lines;           /* Dynamically allocated array of lines. */
  209.   int used;                     /* Number of slots used. */
  210.   int alloc;                    /* Number of slots allocated. */
  211. };
  212.  
  213. /* Input buffers. */
  214. struct buffer
  215. {
  216.   char *buf;                    /* Dynamically allocated buffer. */
  217.   int used;                     /* Number of bytes used. */
  218.   int alloc;                    /* Number of bytes allocated. */
  219.   int left;                     /* Number of bytes left after line parsing. */
  220. };
  221.  
  222. /* Lists of key field comparisons to be tried. */
  223. static struct keyfield
  224. {
  225.   int sword;                    /* Zero-origin 'word' to start at. */
  226.   int schar;                    /* Additional characters to skip. */
  227.   int skipsblanks;              /* Skip leading white space at start. */
  228.   int eword;                    /* Zero-origin first word after field. */
  229.   int echar;                    /* Additional characters in field. */
  230.   int skipeblanks;              /* Skip trailing white space at finish. */
  231.   int *ignore;                  /* Boolean array of characters to ignore. */
  232.   char *translate;              /* Translation applied to characters. */
  233.   int numeric;                  /* Flag for numeric comparison. */
  234.   int month;                    /* Flag for comparison by month name. */
  235.   int reverse;                  /* Reverse the sense of comparison. */
  236.   struct keyfield *next;        /* Next keyfield to try. */
  237. } keyhead;
  238.  
  239. /* The list of temporary files. */
  240. static struct tempnode
  241. {
  242.   char *name;
  243.   struct tempnode *next;
  244. } temphead;
  245.  
  246. /* Clean up any remaining temporary files. */
  247. static void
  248. cleanup()
  249. {
  250.   struct tempnode *node;
  251.  
  252. #ifdef MSDOS
  253.   _fcloseall();
  254. #endif
  255.     
  256.   for (node = temphead.next; node; node = node->next)
  257.     remove(node->name);
  258. }
  259.  
  260. /* Interfaces to library routines. */
  261. #ifdef MSDOS
  262.  
  263. void *
  264. xmalloc (size_t size)
  265. {
  266.   void *r = malloc (size);
  267.  
  268.   if (r)
  269.     return r;
  270.   fprintf (stderr, "sort: memory exausted\n");
  271.   cleanup ();
  272. #ifdef SORT_MODULE
  273.   external_cleanup();
  274. #endif
  275.   exit (-1);
  276. }
  277.  
  278. void *
  279. xrealloc (void *ptr, size_t size)
  280. {
  281.   void *r = realloc (ptr, size);
  282.  
  283.   if (r)
  284.     return r;
  285.   fprintf (stderr, "sort: memory exhausted\n");
  286.   cleanup ();
  287. #ifdef SORT_MODULE
  288.   external_cleanup();
  289. #endif
  290.   exit (-1);
  291. }
  292.  
  293. #else /* not MSDOS */
  294.  
  295. static char *
  296. xmalloc(n)
  297.      int n;
  298. {
  299.   char *r = malloc(n);
  300.  
  301.   if (r)
  302.     return r;
  303.   fprintf(stderr, "sort: memory exausted\n");
  304.   cleanup();
  305. #ifdef SORT_MODULE
  306.   external_cleanup();
  307. #endif
  308.   exit(-1);
  309. }
  310.  
  311. static char *
  312. xrealloc(p, n)
  313.      char *p;
  314.      int n;
  315. {
  316.   char *r = realloc(p, n);
  317.  
  318.   if (r)
  319.     return r;
  320.   fprintf(stderr, "sort: memory exhausted\n");
  321.   cleanup();
  322. #ifdef SORT_MODULE
  323.   external_cleanup();
  324. #endif
  325.   exit(-1);
  326. }
  327.  
  328. #endif /* not MSDOS */
  329.  
  330. static FILE *
  331. xfopen(file, how)
  332.      char *file, *how;
  333. {
  334.   FILE *fp = strcmp(file, "-") ? fopen(file, how) : stdin;
  335.  
  336.   if (fp)
  337.     return fp;
  338.   fprintf(stderr, "sort: cannot open %s (%s): %s\n", file, how,
  339.           strerror(errno));
  340.   cleanup();
  341. #ifdef SORT_MODULE
  342.   external_cleanup();
  343. #endif
  344.   exit(-1);
  345. }
  346.  
  347. static void
  348. xfclose(fp)
  349.      FILE *fp;
  350. {
  351.   fflush(fp);
  352.   if (fp != stdin && fp != stdout)
  353.     if (fclose(fp) != 0)
  354.       {
  355.         fprintf(stderr, "sort: error in fclose: %s\n", strerror(errno));
  356.         cleanup();
  357. #ifdef SORT_MODULE
  358.         external_cleanup();
  359. #endif
  360.         exit(-1);
  361.       }
  362. }
  363.  
  364. static void
  365. xfwrite(buf, size, nelem, fp)
  366.      char *buf;
  367.      int size, nelem;
  368.      FILE *fp;
  369. {
  370. #ifdef MSDOS
  371.   if (fwrite(buf, size, nelem, fp) < (unsigned) nelem)
  372. #else /* not MSDOS */
  373.   if (fwrite(buf, size, nelem, fp) < 0)
  374. #endif /* not MSDOS */
  375.     {
  376.       fprintf(stderr, "sort: error in fwrite: %s\n", strerror(errno));
  377.       cleanup();
  378. #ifdef SORT_MODULE
  379.       external_cleanup();
  380. #endif
  381.       exit(-1);
  382.     }
  383. }
  384.  
  385. /* Return a name for a temporary file. */
  386. static char *
  387. tempname()
  388. {
  389.   static int seq;
  390.   int len = strlen(prefix);
  391.   char *name = xmalloc(len + 16);
  392.   struct tempnode *node =
  393.     (struct tempnode *) xmalloc(sizeof (struct tempnode));
  394.  
  395. #ifdef MSDOS
  396.   if (len && prefix[len - 1] != '/' && prefix[len - 1] != '\\')
  397.     sprintf(name, "%s/sort%4.4x.%3.3x", prefix, _getpid(), ++seq);
  398.   else
  399.     sprintf(name, "%ssort%4.4x.%3.3x", prefix, _getpid(), ++seq);
  400. #else /* not MSDOS */
  401.   if (len && prefix[len - 1] != '/')
  402.     sprintf(name, "%s/sort%5.5d%5.5d", prefix, _getpid(), ++seq);
  403.   else
  404.     sprintf(name, "%ssort%5.5d%5.5d", prefix, _getpid(), ++seq);
  405. #endif /* not MSDOS */
  406.   node->name = name;
  407.   node->next = temphead.next;
  408.   temphead.next = node;
  409.   return name;
  410. }
  411.  
  412. /* Search through the list of temporary files for the given name;
  413.    remove it if it is found on the list. */
  414. static void
  415. zaptemp(name)
  416.      char *name;
  417. {
  418.   struct tempnode *node, *temp;
  419.  
  420.   for (node = &temphead; node->next; node = node->next)
  421.     if (!strcmp(name, node->next->name))
  422.       break;
  423.   if (node->next)
  424.     {
  425.       temp = node->next;
  426.       remove(temp->name);
  427.       free(temp->name);
  428.       node->next = temp->next;
  429.       free((char *) temp);
  430.     }
  431. }
  432.  
  433. /* Initialize the character class tables. */
  434. static void
  435. inittables()
  436. {
  437.   int i;
  438.  
  439.   for (i = 0; i < UCHAR_LIM; ++i)
  440.     {
  441.       if (ISBLANK(i))
  442.         blanks[i] = 1;
  443.       if (ISDIGIT(i))
  444.         digits[i] = 1;
  445.       if (!ISPRINT(i))
  446.         nonprinting[i] = 1;
  447.       if (!ISALNUM(i) && !ISBLANK(i))
  448.         nondictionary[i] = 1;
  449.       if (ISUPPER(i))
  450.         fold_tolower[i] = tolower(i);
  451.       else
  452.         fold_tolower[i] = i;
  453.     }
  454. }
  455.  
  456. /* Initialize BUF allocating ALLOC bytes initially. */
  457. static void
  458. initbuf(buf, alloc)
  459.      struct buffer *buf;
  460.      int alloc;
  461. {
  462.   buf->alloc = alloc;
  463.   buf->buf = xmalloc(buf->alloc);
  464.   buf->used = buf->left = 0;
  465. }
  466.  
  467. /* Fill BUF reading from FP, moving buf->left bytes from the end
  468.    of buf->buf to the beginning first.  If EOF is reached and the
  469.    file wasn't terminated by a newline, supply one.  Return a count
  470.    of bytes actually read. */
  471. static int
  472. fillbuf(buf, fp)
  473.      struct buffer *buf;
  474.      FILE *fp;
  475. {
  476.   int cc, total = 0;
  477.  
  478.   memmove(buf->buf, buf->buf + buf->used - buf->left, buf->left);
  479.   buf->used = buf->left;
  480.  
  481.   while (!feof(fp) && !memchr(buf->buf, '\n', buf->used))
  482.     {
  483.       if (buf->used == buf->alloc)
  484. #ifdef MSDOS
  485.         {
  486.           fprintf (stderr,
  487.                    "sort: lines longer than 32k are not supported under\n"
  488.                    "      MS-DOS because of performance considerations.\n");
  489.           cleanup ();
  490. #ifdef SORT_MODULE
  491.           external_cleanup();
  492. #endif
  493.           exit (-1);
  494.         }
  495. #else /* not MSDOS */
  496.         buf->buf = xrealloc(buf->buf, buf->alloc *= 2);
  497. #endif /* not MSDOS */
  498.       cc = fread(buf->buf + buf->used, 1, buf->alloc - buf->used, fp);
  499.       if (cc < 0)
  500.         {
  501.           fprintf(stderr, "sort: read error (%s)\n", strerror(errno));
  502.           cleanup();
  503. #ifdef SORT_MODULE
  504.           external_cleanup();
  505. #endif
  506.           exit(-1);
  507.         }
  508.       buf->used += cc;
  509.       total += cc;
  510.     }
  511.  
  512.   if (feof(fp) && buf->used && buf->buf[buf->used - 1] != '\n')
  513.     {
  514.       if (buf->used == buf->alloc)
  515. #ifdef MSDOS
  516.         {
  517.           fprintf (stderr,
  518.                    "sort: lines longer than 32k are not supported under\n"
  519.                    "      MS-DOS because of performance considerations.\n");
  520.           cleanup ();
  521. #ifdef SORT_MODULE
  522.           external_cleanup();
  523. #endif
  524.           exit (-1);
  525.         }
  526. #else /* not MSDOS */
  527.         buf->buf = xrealloc(buf->buf, buf->alloc *= 2);
  528. #endif /* not MSDOS */
  529.       buf->buf[buf->used++] = '\n';
  530.       ++total;
  531.     }
  532.  
  533.   return total;
  534. }
  535.  
  536. /* Initialize LINES, allocating space for ALLOC lines initially. */
  537. static void
  538. initlines(lines, alloc)
  539.      struct lines *lines;
  540.      int alloc;
  541. {
  542.   lines->alloc = alloc;
  543. #ifdef MSDOS
  544.   assert_lines (lines->alloc);
  545. #endif /* MSDOS */
  546.   lines->lines = (struct line *) xmalloc(lines->alloc * sizeof (struct line));
  547.   lines->used = 0;
  548. }
  549.  
  550. /* Return a pointer to the first character of a field. */
  551. static char *
  552. begfield(line, key)
  553.      struct line *line;
  554.      struct keyfield *key;
  555. {
  556.   register char *ptr = line->text, *lim = ptr + line->length;
  557.   register int sword = key->sword, schar = key->schar;
  558.  
  559.   if (tab)
  560.     while (ptr < lim && sword--)
  561.       {
  562.         while (ptr < lim && *ptr != tab)
  563.           ++ptr;
  564.         if (ptr < lim)
  565.           ++ptr;
  566.       }
  567.   else
  568.     while (ptr < lim && sword--)
  569.       {
  570.         while (ptr < lim && blanks[UCHAR(*ptr)])
  571.           ++ptr;
  572.         while (ptr < lim && !blanks[UCHAR(*ptr)])
  573.           ++ptr;
  574.       }
  575.  
  576.   if (key->skipsblanks)
  577.     while (ptr < lim && blanks[UCHAR(*ptr)])
  578.       ++ptr;
  579.  
  580.   while (ptr < lim && schar--)
  581.     ++ptr;
  582.  
  583.   return ptr;
  584. }
  585.  
  586. /* Find the limit of a field; i.e., a pointer to the first character
  587.    after the field. */
  588. static char *
  589. limfield(line, key)
  590.      struct line *line;
  591.      struct keyfield *key;
  592. {
  593.   register char *ptr = line->text, *lim = ptr + line->length;
  594.   register int eword = key->eword, echar = key->echar;
  595.  
  596.   if (tab)
  597.     while (ptr < lim && eword--)
  598.       {
  599.         while (ptr < lim && *ptr != tab)
  600.           ++ptr;
  601.         if (ptr < lim && (eword || key->skipeblanks))
  602.           ++ptr;
  603.       }
  604.   else
  605.     while (ptr < lim && eword--)
  606.       {
  607.         while (ptr < lim && blanks[UCHAR(*ptr)])
  608.           ++ptr;
  609.         while (ptr < lim && !blanks[UCHAR(*ptr)])
  610.           ++ptr;
  611.       }
  612.  
  613.   if (key->skipeblanks)
  614.     while (ptr < lim && blanks[UCHAR(*ptr)])
  615.       ++ptr;
  616.  
  617.   while (ptr < lim && echar--)
  618.     ++ptr;
  619.  
  620.   return ptr;
  621. }
  622.  
  623. /* Find the lines in BUF, storing pointers and lengths in LINES.
  624.    Also replace newlines with NULs. */
  625. static void
  626. findlines(buf, lines)
  627.      struct buffer *buf;
  628.      struct lines *lines;
  629. {
  630.   register char *beg = buf->buf, *lim = buf->buf + buf->used, *ptr;
  631.   struct keyfield *key = keyhead.next;
  632.  
  633.   lines->used = 0;
  634.  
  635.   while (beg < lim && (ptr = memchr(beg, '\n', lim - beg)))
  636.     {
  637.       /* There are various places in the code that rely on a NUL
  638.          being at the end of in-core lines; NULs inside the lines
  639.          will not cause trouble, though. */
  640.       *ptr = '\0';
  641.  
  642.       if (lines->used == lines->alloc)
  643.         lines->lines =
  644.           (struct line *) xrealloc((char *) lines->lines,
  645.                                    (lines->alloc *= 2) * sizeof (struct line));
  646.  
  647. #ifdef MSDOS
  648.       assert_lines (lines->alloc);
  649. #endif /* MSDOS */
  650.  
  651.       lines->lines[lines->used].text = beg;
  652.       lines->lines[lines->used].length = ptr - beg;
  653.  
  654.       /* Precompute the position of the first key for efficiency. */
  655.       if (key)
  656.         {
  657.           if (key->eword >= 0)
  658.             lines->lines[lines->used].keylim =
  659.               limfield(&lines->lines[lines->used], key);
  660.           else
  661.             lines->lines[lines->used].keylim = ptr;
  662.  
  663.           if (key->sword >= 0)
  664.             lines->lines[lines->used].keybeg =
  665.               begfield(&lines->lines[lines->used], key);
  666.           else
  667.             {
  668.               if (key->skipsblanks)
  669.                 while (blanks[UCHAR(*beg)])
  670.                   ++beg;
  671.               lines->lines[lines->used].keybeg = beg;
  672.             }
  673.         }
  674.  
  675.       ++lines->used;
  676.       beg = ptr + 1;
  677.     }
  678.  
  679.   buf->left = lim - beg;
  680. }
  681.  
  682. /* Compare two strings containing decimal fractions < 1.  Each string
  683.    should begin with a decimal point followed immediately by the digits
  684.    of the fraction.  Strings not of this form are considered to be zero. */
  685. static int
  686. fraccompare(a, b)
  687.      register char *a, *b;
  688. {
  689.   register tmpa = UCHAR(*a), tmpb = UCHAR(*b);
  690.  
  691.   if (tmpa == '.' && tmpb == '.')
  692.     {
  693.       do
  694.         tmpa = UCHAR(*++a), tmpb = UCHAR(*++b);
  695.       while (tmpa == tmpb && digits[tmpa]);
  696.       if (digits[tmpa] && digits[tmpb])
  697.         return tmpa - tmpb;
  698.       if (digits[tmpa])
  699.         {
  700.           while (tmpa == '0')
  701.             tmpa = UCHAR(*++a);
  702.           if (digits[tmpa])
  703.             return 1;
  704.           return 0;
  705.         }
  706.       if (digits[tmpb])
  707.         {
  708.           while (tmpb == '0')
  709.             tmpb = UCHAR(*++b);
  710.           if (digits[tmpb])
  711.             return -1;
  712.           return 0;
  713.         }
  714.       return 0;
  715.     }
  716.   else if (tmpa == '.')
  717.     {
  718.       do
  719.         tmpa = UCHAR(*++a);
  720.       while (tmpa == '0');
  721.       if (digits[tmpa])
  722.         return 1;
  723.       return 0;
  724.     }
  725.   else if (tmpb == '.')
  726.     {
  727.       do
  728.         tmpb = UCHAR(*++b);
  729.       while (tmpb == '0');
  730.       if (digits[tmpb])
  731.         return -1;
  732.       return 0;
  733.     }
  734.   return 0;
  735. }
  736.  
  737. /* Compare two strings as numbers without explicitly converting them to
  738.    machine numbers.  Comparatively slow for short strings, but asymptotically
  739.    hideously fast. */
  740. static int
  741. numcompare(a, b)
  742.      register char *a, *b;
  743. {
  744.   register int tmpa, tmpb, loga, logb, tmp;
  745.  
  746.   tmpa = UCHAR(*a), tmpb = UCHAR(*b);
  747.  
  748.   if (tmpa == '-')
  749.     {
  750.       tmpa = UCHAR(*++a);
  751.       if (tmpb != '-')
  752.         {
  753.           if (digits[tmpa] && digits[tmpb])
  754.             return -1;
  755.           return 0;
  756.         }
  757.       tmpb = UCHAR(*++b);
  758.  
  759.       while (tmpa == '0')
  760.         tmpa = UCHAR(*++a);
  761.       while (tmpb == '0')
  762.         tmpb = UCHAR(*++b);
  763.  
  764.       while (tmpa == tmpb && digits[tmpa])
  765.         tmpa = UCHAR(*++a), tmpb = UCHAR(*++b);
  766.  
  767.       if (tmpa == '.' && !digits[tmpb] || tmpb == '.' && !digits[tmpa])
  768.         return -fraccompare(a, b);
  769.  
  770.       if (digits[tmpa])
  771.         for (loga = 1; digits[UCHAR(*++a)]; ++loga)
  772.           ;
  773.       else
  774.         loga = 0;
  775.  
  776.       if (digits[tmpb])
  777.         for (logb = 1; digits[UCHAR(*++b)]; ++logb)
  778.           ;
  779.       else
  780.         logb = 0;
  781.  
  782.       if (tmp = logb - loga)
  783.         return tmp;
  784.  
  785.       if (! loga)
  786.         return 0;
  787.  
  788.       return tmpb - tmpa;
  789.     }
  790.   else if (tmpb == '-')
  791.     {
  792.       if (digits[UCHAR(tmpa)] && digits[UCHAR(*++b)])
  793.         return 1;
  794.       return 0;
  795.     }
  796.   else
  797.     {
  798.       while (tmpa == '0')
  799.         tmpa = UCHAR(*++a);
  800.       while (tmpb == '0')
  801.         tmpb = UCHAR(*++b);
  802.  
  803.       while (tmpa == tmpb && digits[tmpa])
  804.         tmpa = UCHAR(*++a), tmpb = UCHAR(*++b);
  805.  
  806.       if (tmpa == '.' && !digits[tmpb] || tmpb == '.' && !digits[tmpa])
  807.         return fraccompare(a, b);
  808.  
  809.       if (digits[tmpa])
  810.         for (loga = 1; digits[UCHAR(*++a)]; ++loga)
  811.           ;
  812.       else
  813.         loga = 0;
  814.  
  815.       if (digits[tmpb])
  816.         for (logb = 1; digits[UCHAR(*++b)]; ++logb)
  817.           ;
  818.       else
  819.         logb = 0;
  820.  
  821.       if (tmp = loga - logb)
  822.         return tmp;
  823.  
  824.       if (! loga)
  825.         return 0;
  826.  
  827.       return tmpa - tmpb;
  828.     }
  829. }
  830.  
  831. /* Return an integer <= 12 associated with a month name (0 if the name
  832.    is not recognized. */
  833. static int
  834. getmonth(s, len)
  835.      char *s;
  836.      int len;
  837. {
  838.   char month[4];
  839.   register int i, lo = 0, hi = 12;
  840.  
  841.   if (len < 3)
  842.     return 0;
  843.  
  844.   for (i = 0; i < 3; ++i)
  845.     month[i] = fold_tolower[UCHAR(s[i])];
  846.   month[3] = '\0';
  847.  
  848.   while (hi - lo > 1)
  849.     if (strcmp(month, monthtab[(lo + hi) / 2].name) < 0)
  850.       hi = (lo + hi) / 2;
  851.     else
  852.       lo = (lo + hi) / 2;
  853.   if (!strcmp(month, monthtab[lo].name))
  854.     return monthtab[lo].val;
  855.   return 0;
  856. }
  857.  
  858. /* Compare two lines trying every key in sequence until there
  859.    are no more keys or a difference is found. */
  860. static int
  861. keycompare(a, b)
  862.      struct line *a, *b;
  863. {
  864.   register char *texta, *textb, *lima, *limb, *translate;
  865.   register int *ignore;
  866.   struct keyfield *key;
  867.   int diff = 0, iter = 0, lena, lenb;
  868.  
  869.   for (key = keyhead.next; key; key = key->next, ++iter)
  870.     {
  871.       ignore = key->ignore;
  872.       translate = key->translate;
  873.  
  874.       /* Find the beginning and limit of each field. */
  875.       if (iter)
  876.         {
  877.           if (key->eword >= 0)
  878.             lima = limfield(a, key), limb = limfield(b, key);
  879.           else
  880.             lima = a->text + a->length, limb = b->text + b->length;
  881.  
  882.           if (key->sword >= 0)
  883.             texta = begfield(a, key), textb = begfield(b, key);
  884.           else
  885.             {
  886.               texta = a->text, textb = b->text;
  887.               if (key->skipsblanks)
  888.                 {
  889.                   while (texta < lima && blanks[UCHAR(*texta)])
  890.                     ++texta;
  891.                   while (textb < limb && blanks[UCHAR(*textb)])
  892.                     ++textb;
  893.                 }
  894.             }
  895.         }
  896.       else
  897.         {
  898.           /* For the first iteration only, the key positions have
  899.              been precomputed for us. */
  900.           texta = a->keybeg, lima = a->keylim;
  901.           textb = b->keybeg, limb = b->keylim;
  902.         }
  903.  
  904.       /* Find the lengths. */
  905.       lena = lima - texta, lenb = limb - textb;
  906.       if (lena < 0)
  907.         lena = 0;
  908.       if (lenb < 0)
  909.         lenb = 0;
  910.  
  911.       /* Actually compare the fields. */
  912.       if (key->numeric)
  913.         {
  914.           if (*lima || *limb)
  915.             {
  916.               char savea = *lima, saveb = *limb;
  917.  
  918.               *lima = *limb = '\0';
  919.               diff = numcompare(texta, textb);
  920.               *lima = savea, *limb = saveb;
  921.             }
  922.           else
  923.             diff = numcompare(texta, textb);
  924.  
  925.           if (diff)
  926.             return key->reverse ? -diff : diff;
  927.           continue;
  928.         }
  929.       else if (key->month)
  930.         {
  931.           diff = getmonth(texta, lena) - getmonth(textb, lenb);
  932.           if (diff)
  933.             return key->reverse ? -diff : diff;
  934.           continue;
  935.         }
  936.       else if (ignore && translate)
  937.         while (texta < lima && textb < limb)
  938.           {
  939.             while (texta < lima && ignore[UCHAR(*texta)])
  940.               ++texta;
  941.             while (textb < limb && ignore[UCHAR(*textb)])
  942.               ++textb;
  943.             if (texta < lima && textb < limb &&
  944.                 translate[UCHAR(*texta++)] != translate[UCHAR(*textb++)])
  945.               {
  946.                 diff = translate[UCHAR(*--texta)] - translate[UCHAR(*--textb)];
  947.                 break;
  948.               }
  949.           }
  950.       else if (ignore)
  951.         while (texta < lima && textb < limb)
  952.           {
  953.             while (texta < lima && ignore[UCHAR(*texta)])
  954.               ++texta;
  955.             while (textb < limb && ignore[UCHAR(*textb)])
  956.               ++textb;
  957.             if (texta < lima && textb < limb && *texta++ != *textb++)
  958.               {
  959.                 diff = *--texta - *--textb;
  960.                 break;
  961.               }
  962.           }
  963.       else if (translate)
  964.         while (texta < lima && textb < limb)
  965.           {
  966.             if (translate[UCHAR(*texta++)] != translate[UCHAR(*textb++)])
  967.               {
  968.                 diff = translate[UCHAR(*--texta)] - translate[UCHAR(*--textb)];
  969.                 break;
  970.               }
  971.           }
  972.       else
  973.         diff = memcmp(texta, textb, MIN(lena, lenb));
  974.  
  975.       if (diff)
  976.         return key->reverse ? -diff : diff;
  977.       if (diff = lena - lenb)
  978.         return key->reverse ? -diff : diff;
  979.     }
  980.  
  981.   return 0;
  982. }
  983.  
  984. /* Compare two lines, returning negative, zero, or positive depending on
  985.    whether A compares less than, equal to, or greater than B. */
  986. static int
  987. compare(a, b)
  988.      register struct line *a, *b;
  989. {
  990.   int diff, tmpa, tmpb, min;
  991.  
  992.   if (keyhead.next)
  993.     {
  994.       if (diff = keycompare(a, b))
  995.         return diff;
  996.       if (!unique)
  997.         {
  998.           tmpa = a->length, tmpb = b->length;
  999.           diff = memcmp(a->text, b->text, MIN(tmpa, tmpb));
  1000.           if (! diff)
  1001.             diff = tmpa - tmpb;
  1002.         }
  1003.     }
  1004.   else
  1005.     {
  1006.       tmpa = a->length, tmpb = b->length;
  1007.       min = MIN(tmpa, tmpb);
  1008.       if (min == 0)
  1009.         diff = tmpa - tmpb;
  1010.       else
  1011.         {
  1012.           char *ap = a->text, *bp = b->text;
  1013.  
  1014.           diff = *ap - *bp;
  1015.           if (diff == 0)
  1016.             {
  1017.               diff = memcmp(ap, bp, min);
  1018.               if (diff == 0)
  1019.                 diff = tmpa - tmpb;
  1020.             }
  1021.         }
  1022.     }
  1023.  
  1024.   return reverse ? -diff : diff;
  1025. }
  1026.  
  1027. /* Check that the lines read from the given FP come in order.  Return
  1028.    1 if they do and 0 if there is a disorder. */
  1029. static int
  1030. checkfp(fp)
  1031.      FILE *fp;
  1032. {
  1033.   struct buffer buf;            /* Input buffer. */
  1034.   struct lines lines;           /* Lines scanned from the buffer. */
  1035.   struct line temp;             /* Copy of previous line. */
  1036.   int cc;                       /* Character count. */
  1037.   int cmp;                      /* Result of calling compare. */
  1038.   int alloc, i, success = 1;
  1039.  
  1040.   initbuf(&buf, mergealloc);
  1041.   initlines(&lines, mergealloc / linelength + 1);
  1042.   alloc = linelength;
  1043.   temp.text = xmalloc(alloc);
  1044.  
  1045.   cc = fillbuf(&buf, fp);
  1046.   findlines(&buf, &lines);
  1047.  
  1048.   if (cc)
  1049.     do
  1050.       {
  1051.         /* Compare each line in the buffer with its successor. */
  1052.         for (i = 0; i < lines.used - 1; ++i)
  1053.           {
  1054.             cmp = compare(&lines.lines[i], &lines.lines[i + 1]);
  1055.             if (unique && cmp >= 0 || cmp > 0)
  1056.               {
  1057.                 success = 0;
  1058.                 goto finish;
  1059.               }
  1060.           }
  1061.  
  1062.         /* Save the last line of the buffer and refill the buffer. */
  1063.         if (lines.lines[lines.used - 1].length > alloc)
  1064.           {
  1065.             while (lines.lines[lines.used - 1].length + 1 > alloc)
  1066.               alloc *= 2;
  1067.             temp.text = xrealloc(temp.text, alloc);
  1068.           }
  1069.         memcpy(temp.text, lines.lines[lines.used - 1].text,
  1070.                lines.lines[lines.used - 1].length + 1);
  1071.         temp.length = lines.lines[lines.used - 1].length;
  1072.  
  1073.         cc = fillbuf(&buf, fp);
  1074.         if (cc)
  1075.           {
  1076.             findlines(&buf, &lines);
  1077.             /* Make sure the line saved from the old buffer contents is
  1078.                less than or equal to the first line of the new buffer. */
  1079.             cmp = compare(&temp, &lines.lines[0]);
  1080.             if (unique && cmp >= 0 || cmp > 0)
  1081.               {
  1082.                 success = 0;
  1083.                 break;
  1084.               }
  1085.           }
  1086.       }
  1087.     while (cc);
  1088.  
  1089.  finish:
  1090.   xfclose(fp);
  1091.   free(buf.buf);
  1092.   free((char *) lines.lines);
  1093.   free(temp.text);
  1094.   return success;
  1095. }
  1096.  
  1097. /* Merge lines from FPS onto OFP.  NFPS cannot be greater than NMERGE.
  1098.    Close FPS before returning. */
  1099. static void
  1100. mergefps(fps, nfps, ofp)
  1101.      FILE *fps[], *ofp;
  1102.      register int nfps;
  1103. {
  1104.   struct buffer buffer[NMERGE]; /* Input buffers for each file. */
  1105.   struct lines lines[NMERGE];   /* Line tables for each buffer. */
  1106.   struct line saved;            /* Saved line for unique check. */
  1107.   int savedflag = 0;            /* True if there is a saved line. */
  1108.   int savealloc;                /* Size allocated for the saved line. */
  1109.   int cur[NMERGE];              /* Current line in each line table. */
  1110.   int ord[NMERGE];              /* Table representing a permutation of fps,
  1111.                                    such that lines[ord[0]].lines[cur[ord[0]]]
  1112.                                    is the smallest line and will be next
  1113.                                    output. */
  1114.   register int i, j, t;
  1115.  
  1116.   /* Allocate space for a saved line if necessary. */
  1117.   if (unique)
  1118.     saved.text = xmalloc(savealloc = linelength);
  1119.  
  1120.   /* Read initial lines from each input file. */
  1121.   for (i = 0; i < nfps; ++i)
  1122.     {
  1123.       initbuf(&buffer[i], mergealloc);
  1124.       /* If a file is empty, eliminate it from future consideration. */
  1125.       while (i < nfps && !fillbuf(&buffer[i], fps[i]))
  1126.         {
  1127.           xfclose(fps[i]);
  1128.           --nfps;
  1129.           for (j = i; j < nfps; ++j)
  1130.             fps[j] = fps[j + 1];
  1131.         }
  1132.       if (i == nfps)
  1133.         free(buffer[i].buf);
  1134.       else
  1135.         {
  1136.           initlines(&lines[i], mergealloc / linelength + 1);
  1137.           findlines(&buffer[i], &lines[i]);
  1138.           cur[i] = 0;
  1139.         }
  1140.     }
  1141.  
  1142.   /* Set up the ord table according to comparisons among input lines.
  1143.      Since this only reorders two items if one is strictly greater than
  1144.      the other, it is stable. */
  1145.   for (i = 0; i < nfps; ++i)
  1146.     ord[i] = i;
  1147.   for (i = 1; i < nfps; ++i)
  1148.     if (compare(&lines[ord[i - 1]].lines[cur[ord[i - 1]]],
  1149.                 &lines[ord[i]].lines[cur[ord[i]]]) > 0)
  1150.       t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;
  1151.  
  1152.   /* Repeatedly output the smallest line until no input remains. */
  1153.   while (nfps)
  1154.     {
  1155.       /* If uniqified output is turned out, output only the last of
  1156.          an identical series of lines. */
  1157.       if (unique)
  1158.         {
  1159.           if (savedflag && compare(&saved, &lines[ord[0]].lines[cur[ord[0]]]))
  1160.             {
  1161.               xfwrite(saved.text, 1, saved.length, ofp);
  1162.               putc('\n', ofp);
  1163.             }
  1164.           if (savealloc < lines[ord[0]].lines[cur[ord[0]]].length + 1)
  1165.             {
  1166.               while (savealloc < lines[ord[0]].lines[cur[ord[0]]].length + 1)
  1167.                 savealloc *= 2;
  1168.               saved.text = xrealloc(saved.text, savealloc);
  1169.             }
  1170.           saved.length = lines[ord[0]].lines[cur[ord[0]]].length;
  1171.           memcpy(saved.text, lines[ord[0]].lines[cur[ord[0]]].text,
  1172.                  saved.length + 1);
  1173.           saved.keybeg = lines[ord[0]].lines[cur[ord[0]]].keybeg;
  1174.           saved.keylim = lines[ord[0]].lines[cur[ord[0]]].keylim;
  1175.           savedflag = 1;
  1176.         }
  1177.       else
  1178.         {
  1179.           xfwrite(lines[ord[0]].lines[cur[ord[0]]].text, 1,
  1180.                  lines[ord[0]].lines[cur[ord[0]]].length, ofp);
  1181.           putc('\n', ofp);
  1182.         }
  1183.  
  1184.       /* Check if we need to read more lines into core. */
  1185.       if (++cur[ord[0]] == lines[ord[0]].used)
  1186.         if (fillbuf(&buffer[ord[0]], fps[ord[0]]))
  1187.           {
  1188.             findlines(&buffer[ord[0]], &lines[ord[0]]);
  1189.             cur[ord[0]] = 0;
  1190.           }
  1191.         else
  1192.           {
  1193.             /* We reached EOF on fps[ord[0]]. */
  1194.             for (i = 1; i < nfps; ++i)
  1195.               if (ord[i] > ord[0])
  1196.                 --ord[i];
  1197.             --nfps;
  1198.             xfclose(fps[ord[0]]);
  1199.             free(buffer[ord[0]].buf);
  1200.             free((char *) lines[ord[0]].lines);
  1201.             for (i = ord[0]; i < nfps; ++i)
  1202.               {
  1203.                 fps[i] = fps[i + 1];
  1204.                 buffer[i] = buffer[i + 1];
  1205.                 lines[i] = lines[i + 1];
  1206.                 cur[i] = cur[i + 1];
  1207.               }
  1208.             for (i = 0; i < nfps; ++i)
  1209.               ord[i] = ord[i + 1];
  1210.             continue;
  1211.           }
  1212.  
  1213.       /* The new line just read in may be larger than other lines
  1214.          already in core; push it back in the queue until we encounter
  1215.          a line larger than it. */
  1216.       for (i = 1; i < nfps; ++i)
  1217.         {
  1218.           t = compare(&lines[ord[0]].lines[cur[ord[0]]],
  1219.                       &lines[ord[i]].lines[cur[ord[i]]]);
  1220.           if (! t)
  1221.             t = ord[0] - ord[i];
  1222.           if (t < 0)
  1223.             break;
  1224.         }
  1225.       t = ord[0];
  1226.       for (j = 1; j < i; ++j)
  1227.         ord[j - 1] = ord[j];
  1228.       ord[i - 1] = t;
  1229.     }
  1230.  
  1231.   if (unique && savedflag)
  1232.     {
  1233.       xfwrite(saved.text, 1, saved.length, ofp);
  1234.       putc('\n', ofp);
  1235.       free(saved.text);
  1236.     }
  1237. }
  1238.  
  1239. /* Sort the array LINES using TEMP for temporary space. */
  1240. static void
  1241. sortlines(lines, nlines, temp)
  1242.      struct line *lines, *temp;
  1243.      int nlines;
  1244. {
  1245.   register struct line *lo, *hi, *t;
  1246.   register int nlo, nhi;
  1247.  
  1248.   if (nlines == 2)
  1249.     {
  1250.       if (compare(&lines[0], &lines[1]) > 0)
  1251.         *temp = lines[0], lines[0] = lines[1], lines[1] = *temp;
  1252.       return;
  1253.     }
  1254.  
  1255.   nlo = nlines / 2;
  1256.   lo = lines;
  1257.   nhi = nlines - nlo;
  1258.   hi = lines + nlo;
  1259.  
  1260.   if (nlo > 1)
  1261.     sortlines(lo, nlo, temp);
  1262.  
  1263.   if (nhi > 1)
  1264.     sortlines(hi, nhi, temp);
  1265.  
  1266.   t = temp;
  1267.  
  1268.   while (nlo && nhi)
  1269.     if (compare(lo, hi) <= 0)
  1270.       *t++ = *lo++, --nlo;
  1271.     else
  1272.       *t++ = *hi++, --nhi;
  1273.   while (nlo--)
  1274.     *t++ = *lo++;
  1275.  
  1276.   for (lo = lines, nlo = nlines - nhi, t = temp; nlo; --nlo)
  1277.     *lo++ = *t++;
  1278. }
  1279.  
  1280. /* Check that each of the given FILES is ordered.
  1281.    Return a count of disordered files. */
  1282. static int
  1283. check(files, nfiles)
  1284.      char *files[];
  1285.      int nfiles;
  1286. {
  1287.   int i, disorders = 0;
  1288.   FILE *fp;
  1289.  
  1290.   for (i = 0; i < nfiles; ++i)
  1291.     {
  1292.       fp = xfopen(files[i], "r");
  1293.       if (! checkfp(fp))
  1294.         {
  1295.           printf("sort: disorder on %s\n", files[i]);
  1296.           ++disorders;
  1297.         }
  1298.     }
  1299.   return disorders;
  1300. }
  1301.  
  1302. /* Merge any number of FILES onto the given OFP. */
  1303. static void
  1304. merge(files, nfiles, ofp)
  1305.      char *files[];
  1306.      int nfiles;
  1307.      FILE *ofp;
  1308. {
  1309.   int i, j, t;
  1310.   char *temp;
  1311.   FILE *fps[NMERGE], *tfp;
  1312.  
  1313.   while (nfiles > NMERGE)
  1314.     {
  1315.       t = 0;
  1316.       for (i = 0; i < nfiles / NMERGE; ++i)
  1317.         {
  1318.           for (j = 0; j < NMERGE; ++j)
  1319.             fps[j] = xfopen(files[i * NMERGE + j], "r");
  1320.           tfp = xfopen(temp = tempname(), "w");
  1321.           mergefps(fps, NMERGE, tfp);
  1322.           xfclose(tfp);
  1323.           for (j = 0; j < NMERGE; ++j)
  1324.             zaptemp(files[i * NMERGE + j]);
  1325.           files[t++] = temp;
  1326.         }
  1327.       for (j = 0; j < nfiles % NMERGE; ++j)
  1328.         fps[j] = xfopen(files[i * NMERGE + j], "r");
  1329.       tfp = xfopen(temp = tempname(), "w");
  1330.       mergefps(fps, nfiles % NMERGE, tfp);
  1331.       xfclose(tfp);
  1332.       for (j = 0; j < nfiles % NMERGE; ++j)
  1333.         zaptemp(files[i * NMERGE + j]);
  1334.       files[t++] = temp;
  1335.       nfiles = t;
  1336.     }
  1337.  
  1338.   for (i = 0; i < nfiles; ++i)
  1339.     fps[i] = xfopen(files[i], "r");
  1340.   mergefps(fps, i, ofp);
  1341.   for (i = 0; i < nfiles; ++i)
  1342.     zaptemp(files[i]);
  1343. }
  1344.  
  1345. /* Sort any number of FILES onto the given OFP. */
  1346. static void
  1347. sort(files, nfiles, ofp)
  1348.      char **files;
  1349.      int nfiles;
  1350.      FILE *ofp;
  1351. {
  1352.   struct buffer buf;
  1353.   struct lines lines;
  1354.   struct line *tmp;
  1355.   int i, ntmp;
  1356.   FILE *fp, *tfp;
  1357.   struct tempnode *node;
  1358.   int ntemp = 0;
  1359.   char **tempfiles;
  1360.  
  1361.   initbuf(&buf, sortalloc);
  1362.   initlines(&lines, sortalloc / linelength + 1);
  1363.   ntmp = lines.alloc;
  1364. #ifdef MSDOS
  1365.   assert_lines (ntmp);
  1366. #endif /* MSDOS */
  1367.   tmp = (struct line *) xmalloc(ntmp * sizeof (struct line));
  1368.  
  1369.   while (nfiles--)
  1370.     {
  1371.       fp = xfopen(*files++, "r");
  1372.       while (fillbuf(&buf, fp))
  1373.         {
  1374.           findlines(&buf, &lines);
  1375.           if (lines.used > ntmp)
  1376.             {
  1377.               while (lines.used > ntmp)
  1378.                 ntmp *= 2;
  1379. #ifdef MSDOS
  1380.               assert_lines (ntmp);
  1381. #endif /* MSDOS */
  1382.               tmp = (struct line *) xrealloc((char *) tmp,
  1383.                                              ntmp * sizeof (struct line));
  1384.             }
  1385.           sortlines(lines.lines, lines.used, tmp);
  1386.           if (feof(fp) && !nfiles && !ntemp)
  1387.             tfp = ofp;
  1388.           else
  1389.             {
  1390.               ++ntemp;
  1391.               tfp = xfopen(tempname(), "w");
  1392.             }
  1393.           for (i = 0; i < lines.used; ++i)
  1394.             if (!unique || i == lines.used - 1
  1395.                 || compare(&lines.lines[i], &lines.lines[i + 1]))
  1396.               {
  1397.                 xfwrite(lines.lines[i].text, 1, lines.lines[i].length, tfp);
  1398.                 putc('\n', tfp);
  1399.               }
  1400.           if (tfp != ofp)
  1401.             xfclose(tfp);
  1402.         }
  1403.       xfclose(fp);
  1404.     }
  1405.  
  1406.   free(buf.buf);
  1407.   free((char *) lines.lines);
  1408.   free((char *) tmp);
  1409.  
  1410.   if (ntemp)
  1411.     {
  1412.       tempfiles = (char **) xmalloc(ntemp * sizeof (char *));
  1413.       i = ntemp;
  1414.       for (node = temphead.next; node; node = node->next)
  1415.         tempfiles[--i] = node->name;
  1416.       merge(tempfiles, ntemp, ofp);
  1417.       free((char *) tempfiles);
  1418.     }
  1419. }
  1420.  
  1421. /* Insert a key at the end of the list. */
  1422. static void
  1423. insertkey(key)
  1424.      struct keyfield *key;
  1425. {
  1426.   struct keyfield *k = &keyhead;
  1427.  
  1428.   while (k->next)
  1429.     k = k->next;
  1430.   k->next = key;
  1431.   key->next = NULL;
  1432. }
  1433.  
  1434. static void
  1435. usage()
  1436. {
  1437.   fprintf(stderr,
  1438.           "usage: sort [ -cmu ] [ -tc ] [ -o file ] [ -T dir ]\n");
  1439.   fprintf(stderr,
  1440.           "            [ -bdfiMnr ] [ +n [ -m ] . . . ] [ files . . . ]\n");
  1441.   exit(-1);
  1442. }
  1443.  
  1444. static void
  1445. badfieldspec(s)
  1446.      char *s;
  1447. {
  1448.   fprintf(stderr, "sort: bad field specification %s\n", s);
  1449.   exit(-1);
  1450. }
  1451.  
  1452. /* Handle interrupts and hangups. */
  1453. static void
  1454. #ifdef MSDOS
  1455. __cdecl inthandler()
  1456. #else
  1457. inthandler()
  1458. #endif
  1459. {
  1460.   signal(SIGINT, SIG_DFL);
  1461.   cleanup();
  1462. #ifdef SORT_MODULE
  1463.   external_cleanup();
  1464. #endif
  1465. #ifdef MSDOS
  1466.   abort ();
  1467. #else /* not MSDOS */
  1468.   kill(_getpid(), SIGINT);
  1469. #endif /* not MSDOS */
  1470. }
  1471.  
  1472. #ifndef MSDOS
  1473. static void
  1474. huphandler()
  1475. {
  1476.   signal(SIGHUP, SIG_DFL);
  1477.   cleanup();
  1478.   kill(_getpid(), SIGHUP);
  1479. }
  1480. #endif /* not MSDOS */
  1481.  
  1482. int
  1483. #ifdef SORT_MODULE
  1484. sort_main(argc, argv)
  1485. #else
  1486. main(argc, argv)
  1487. #endif
  1488.      int argc;
  1489.      char *argv[];
  1490. {
  1491.   struct keyfield *key = NULL, gkey;
  1492.   char *s;
  1493.   int i, t, t2;
  1494.   int checkonly = 0, mergeonly = 0, nfiles;
  1495.   char *minus = "-", *outfile = minus, **files, *tmp;
  1496.   FILE *ofp;
  1497.  
  1498. #ifdef MSDOS
  1499.   prefix = getenv ("TMP");
  1500.   if (!prefix)
  1501.     prefix = ".";
  1502. #endif /* MSDOS */
  1503.  
  1504.   inittables();
  1505.  
  1506.   if (signal(SIGINT, SIG_IGN) != SIG_IGN)
  1507.     signal(SIGINT, inthandler);
  1508. #ifndef MSDOS
  1509.   if (signal(SIGHUP, SIG_IGN) != SIG_IGN)
  1510.     signal(SIGHUP, huphandler);
  1511. #endif /* not MSDOS */
  1512.  
  1513.   gkey.sword = gkey.eword = -1;
  1514.   gkey.ignore = NULL;
  1515.   gkey.translate = NULL;
  1516.   gkey.numeric = gkey.month = gkey.reverse = 0;
  1517.   gkey.skipsblanks = gkey.skipeblanks = 0;
  1518.  
  1519.   for (i = 1; i < argc; ++i)
  1520.     {
  1521.       if (argv[i][0] == '+')
  1522.         {
  1523.           if (key)
  1524.             insertkey(key);
  1525.           key = (struct keyfield *) xmalloc(sizeof (struct keyfield));
  1526.           key->eword = -1;
  1527.           key->ignore = NULL;
  1528.           key->translate = NULL;
  1529.           key->skipsblanks = key->skipeblanks = 0;
  1530.           key->numeric = key->month = key->reverse = 0;
  1531.           s = argv[i] + 1;
  1532.           if (!digits[UCHAR(*s)])
  1533.             badfieldspec(argv[i]);
  1534.           for (t = 0; digits[UCHAR(*s)]; ++s)
  1535.             t = 10 * t + *s - '0';
  1536.           t2 = 0;
  1537.           if (*s == '.')
  1538.             for (++s; digits[UCHAR(*s)]; ++s)
  1539.               t2 = 10 * t2 + *s - '0';
  1540.           if (t2 || t)
  1541.             {
  1542.               key->sword = t;
  1543.               key->schar = t2;
  1544.             }
  1545.           else
  1546.             key->sword = -1;
  1547.           while (*s)
  1548.             {
  1549.               switch (*s)
  1550.                 {
  1551.                 case 'b':
  1552.                   key->skipsblanks = 1;
  1553.                   break;
  1554.                 case 'd':
  1555.                   key->ignore = nondictionary;
  1556.                   break;
  1557.                 case 'f':
  1558.                   key->translate = fold_tolower;
  1559.                   break;
  1560.                 case 'i':
  1561.                   key->ignore = nonprinting;
  1562.                 case 'M':
  1563.                   key->skipsblanks = key->skipeblanks = key->month = 1;
  1564.                   break;
  1565.                 case 'n':
  1566.                   key->skipsblanks = key->skipeblanks = key->numeric = 1;
  1567.                   break;
  1568.                 case 'r':
  1569.                   key->reverse = 1;
  1570.                   break;
  1571.                 default:
  1572.                   badfieldspec(argv[i]);
  1573.                   break;
  1574.                 }
  1575.               ++s;
  1576.             }
  1577.         }
  1578.       else if (argv[i][0] == '-')
  1579.         {
  1580.           if (!strcmp("-", argv[i]))
  1581.             break;
  1582.           s = argv[i] + 1;
  1583.           if (digits[UCHAR(*s)])
  1584.             {
  1585.               if (! key)
  1586.                 usage();
  1587.               for (t = 0; digits[UCHAR(*s)]; ++s)
  1588.                 t = t * 10 + *s - '0';
  1589.               t2 = 0;
  1590.               if (*s == '.')
  1591.                 for (++s; digits[UCHAR(*s)]; ++s)
  1592.                   t2 = t2 * 10 + *s - '0';
  1593.               key->eword = t;
  1594.               key->echar = t2;
  1595.               while (*s)
  1596.                 {
  1597.                   switch (*s)
  1598.                     {
  1599.                     case 'b':
  1600.                       key->skipeblanks = 1;
  1601.                       break;
  1602.                     case 'd':
  1603.                       key->ignore = nondictionary;
  1604.                       break;
  1605.                     case 'f':
  1606.                       key->translate = fold_tolower;
  1607.                       break;
  1608.                     case 'i':
  1609.                       key->ignore = nonprinting;
  1610.                     case 'M':
  1611.                       key->skipsblanks = key->skipeblanks = key->month = 1;
  1612.                       break;
  1613.                     case 'n':
  1614.                       key->skipsblanks = key->skipeblanks = key->numeric = 1;
  1615.                       break;
  1616.                     case 'r':
  1617.                       key->reverse = 1;
  1618.                       break;
  1619.                     default:
  1620.                       badfieldspec(argv[i]);
  1621.                       break;
  1622.                     }
  1623.                   ++s;
  1624.                 }
  1625.               insertkey(key);
  1626.               key = NULL;
  1627.             }
  1628.           else
  1629.             while (*s)
  1630.               {
  1631.                 switch (*s)
  1632.                   {
  1633.                   case 'b':
  1634.                     gkey.skipsblanks = gkey.skipeblanks = 1;
  1635.                     break;
  1636.                   case 'c':
  1637.                     checkonly = 1;
  1638.                     break;
  1639.                   case 'd':
  1640.                     gkey.ignore = nondictionary;
  1641.                     break;
  1642.                   case 'f':
  1643.                     gkey.translate = fold_tolower;
  1644.                     break;
  1645.                   case 'i':
  1646.                     gkey.ignore = nonprinting;
  1647.                     break;
  1648.                   case 'M':
  1649.                     gkey.skipsblanks = gkey.skipeblanks = gkey.month = 1;
  1650.                     break;
  1651.                   case 'm':
  1652.                     mergeonly = 1;
  1653.                     break;
  1654.                   case 'n':
  1655.                     gkey.skipsblanks = gkey.skipeblanks = gkey.numeric = 1;
  1656.                     break;
  1657.                   case 'o':
  1658.                     if (s[1])
  1659.                       outfile = s + 1;
  1660.                     else
  1661.                       {
  1662.                         if (i == argc - 1)
  1663.                           {
  1664.                             fprintf(stderr, "sort: missing argument to -o\n");
  1665.                             exit(-1);
  1666.                           }
  1667.                         else
  1668.                           outfile = argv[++i];
  1669.                       }
  1670.                     goto outer;
  1671.                   case 'r':
  1672.                     gkey.reverse = reverse = 1;
  1673.                     break;
  1674.                   case 'T':
  1675.                     if (s[1])
  1676.                       prefix = s + 1;
  1677.                     else
  1678.                       {
  1679.                         if (i == argc - 1)
  1680.                           {
  1681.                             fprintf(stderr, "sort: missing argument to -T\n");
  1682.                             exit(-1);
  1683.                           }
  1684.                         else
  1685.                           prefix = argv[++i];
  1686.                       }
  1687.                     goto outer;
  1688.                   case 't':
  1689.                     if (s[1])
  1690.                       tab = *++s;
  1691.                     else if (i < argc - 1)
  1692.                       {
  1693.                         tab = *argv[++i];
  1694.                         goto outer;
  1695.                       }
  1696.                     else
  1697.                       {
  1698.                         fprintf(stderr, "sort: missing character for -tc\n");
  1699.                         exit(-1);
  1700.                       }
  1701.                     break;
  1702.                   case 'u':
  1703.                     unique = 1;
  1704.                     break;
  1705.                   case 'V':
  1706.                     fprintf(stderr, "%s\n", version);
  1707.                     break;
  1708. #ifdef MSDOS
  1709.                   case 'S':
  1710.                     {
  1711.                       long num;
  1712.                       if (s[1])
  1713.                         num = atol (s + 1);
  1714.                       else
  1715.                         {
  1716.                           if (i == argc - 1)
  1717.                             {
  1718.                               fprintf(stderr, "sort: missing argument to -S\n");
  1719.                               exit(-1);
  1720.                             }
  1721.                           else
  1722.                             num = atol (argv[++i]);
  1723.                         }
  1724.                       if (num > 32767 || num <= 0)
  1725.                         fprintf(stderr, "sort: argument to -S must be < 32k\n");
  1726.                       else
  1727.                         sortalloc = (int) num;
  1728.                     }
  1729.                     goto outer;
  1730. #endif /* MSDOS */
  1731.                   default:
  1732.                     usage();
  1733.                     exit(-1);
  1734.                   }
  1735.                 ++s;
  1736.               }
  1737.         }
  1738.       else
  1739.         break;
  1740.     outer:;
  1741.     }
  1742.  
  1743.   if (key)
  1744.     insertkey(key);
  1745.  
  1746.   /* Inheritance of global options to individual keys. */
  1747.   for (key = keyhead.next; key; key = key->next)
  1748.     if (!key->ignore && !key->translate && !key->skipsblanks && !key->reverse
  1749.         && !key->skipeblanks && !key->month && !key->numeric)
  1750.       {
  1751.         key->ignore = gkey.ignore;
  1752.         key->translate = gkey.translate;
  1753.         key->skipsblanks = gkey.skipsblanks;
  1754.         key->skipeblanks = gkey.skipeblanks;
  1755.         key->month = gkey.month;
  1756.         key->numeric = gkey.numeric;
  1757.         key->reverse = gkey.reverse;
  1758.       }
  1759.  
  1760.   if (! keyhead.next && (gkey.ignore || gkey.translate || gkey.skipsblanks
  1761.                          || gkey.reverse || gkey.skipeblanks
  1762.                          || gkey.month || gkey.numeric))
  1763.     insertkey(&gkey);
  1764.  
  1765.   if (i < argc)
  1766.     {
  1767.       nfiles = argc - i;
  1768.       files = &argv[i];
  1769.     }
  1770.   else
  1771.     {
  1772.       nfiles = 1;
  1773.       files = −
  1774.     }
  1775.  
  1776.   if (checkonly)
  1777.     exit(check(files, nfiles));
  1778.  
  1779.   if (strcmp(outfile, "-"))
  1780.     {
  1781.       for (i = 0; i < nfiles; ++i)
  1782.         if (!strcmp(outfile, files[i]))
  1783.           break;
  1784.       if (i == nfiles)
  1785.         ofp = xfopen(outfile, "w");
  1786.       else
  1787.         {
  1788.           char buf[8192];
  1789.           FILE *fp = xfopen(outfile, "r");
  1790.           int cc;
  1791.  
  1792.           tmp = tempname();
  1793.           ofp = xfopen(tmp, "w");
  1794.           while (cc = fread(buf, 1, sizeof buf, fp))
  1795.             if (cc < 0)
  1796.               {
  1797.                 fprintf(stderr, "sort: error in fread (%s)\n",
  1798.                         strerror(errno));
  1799.                 cleanup();
  1800.                 exit(-1);
  1801.               }
  1802.             else
  1803.               xfwrite(buf, 1, cc, ofp);
  1804.           xfclose(ofp);
  1805.           xfclose(fp);
  1806.           files[i] = tmp;
  1807.           ofp = xfopen(outfile, "w");
  1808.         }
  1809.     }
  1810.   else
  1811.     ofp = stdout;
  1812.  
  1813.   if (mergeonly)
  1814.     merge(files, nfiles, ofp);
  1815.   else
  1816.     sort(files, nfiles, ofp);
  1817.  
  1818.   /* close the file */
  1819.   if (ofp != stdout)
  1820.     fclose(ofp);
  1821.  
  1822.   cleanup();
  1823.  
  1824. #ifdef SORT_MODULE
  1825.   return(0);
  1826. #else /* not SORT_MODULE */
  1827.   exit(0);
  1828. #endif /* not SORT_MODULE */
  1829.  
  1830. }
  1831.