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