home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 185_01 / ssort.c < prev    next >
Encoding:
Text File  |  1985-08-19  |  21.6 KB  |  880 lines
  1. /*
  2.  * SSORT.C - Selecta-SORT
  3.  * version 1.0
  4.  * This is a modified version of LEXSORT which permits a command line
  5.  * option to select the collating sequence from a "magic" file.
  6.  * The name was changed only due to the fact that LEXSORT was no longer
  7.  * (if it ever was) appropriate.  LEXSORT.LBR should be retired.
  8.  *
  9.  * Differences from LEXSORT.C:
  10.  *
  11.  * The only changed functions were options() and usage(). Two functions
  12.  * were added: get_collating_sequence(), collate_file().
  13.  * Four #defines were added:  INPUT, ABSOLUTE, FUDGE, COLLATE_NAME.
  14.  * The signon message was changed.  Globals were not modified.
  15.  *
  16.  *    Harvey Moran    2/26/84
  17.  *
  18.  * To build with BDS C vers 1.5:
  19.  *    cc ssort -o -e 3800
  20.  *    casm lexlate
  21.  *    asm lexlate.DDz        ;choose drives (D) to suit
  22.  *    ddt
  23.  *    f100,1000,0  (not necessary, makes file compares of '.crl' meaningful)
  24.  *    iLEXLATE.HEX
  25.  *    g0
  26.  *    save 4 lexlate.crl
  27.  *    l2 ssort lexlate
  28.  *
  29.  * Usage:
  30.  *
  31.  *    SSORT <infile> <outfile> [-c<index 0 to n>] [-k<key field selections>]
  32.  *
  33.  *    -c<n> seletcs the n'th sort order precedence table from the
  34.  *    "magic" file SSORT.OVL to be overlayed into lexlate().  See
  35.  *    SORTORDR.ASM for the definition of these tables. ASseMble and LOAD
  36.  *    SORTORDR.ASM, then rename to SSORT.OVL. 
  37.  *    If -c is not used, the default remains the same lexicographical
  38.  *    increasing order sort from LEXSORT (or whatever you "wire" into
  39.  *    LEXLATE.CRL).
  40.  *
  41.  *    All other command line syntax remains the same as LEXSORT.
  42.  *
  43.  *        Harvey Moran 2/26/84
  44.  *
  45.  * =====================================================================
  46.  * LEXSORT.C (modified SORT3.C for lexicographical ordering) HRM 11/6/83
  47.  * version 1.0
  48.  * To build with BDS C vers 1.5:
  49.  *    cc lexsort -o -e 3400
  50.  *    casm lexlate
  51.  *    asm lexlate.DDz        ;choose drives (D) to suit
  52.  *    ddt
  53.  *    f100,1000,0  (not necessary, makes file compares of '.crl' meaningful)
  54.  *    iLEXLATE.HEX
  55.  *    g0
  56.  *    save 4 lexlate.crl
  57.  *    l2 lexsort lexlate
  58.  *
  59.  * Usage: lexsort <infile> <outfile> [-k<sort key list>]
  60.  *
  61.  * where <sort key list> is:
  62.  *
  63.  * A comma separated list of column numbers or ranges
  64.  * specifing the sort key positions.
  65.  *    e.g.
  66.  * lexsort messy.dat neat.dat -k3-5,7-9,1-2,12
  67.  *
  68.  * specifies that:
  69.  * the  input file is MESSY.DAT
  70.  * the output file is  NEAT.DAT
  71.  *
  72.  *         The primary sort key is columns  3 thru 5
  73.  * The first secondary sort key is columns  7 thru 9
  74.  * The next  secondary sort key is columns  1 thru 2
  75.  * The last  secondary sort key is columns 12 thru end of line
  76.  *
  77.  * A sort key of 1 column may be specified as 3-3 for example.
  78.  * A sort key which goes to end of line need NOT be the last one.
  79.  *
  80.  * The leftmost column is numbered 1.
  81.  * The default sort key is the entire line.
  82.  *
  83.  * Implementation note:
  84.  *
  85.  *    LEXLATE.CSM contains function lexlate() which determines the
  86.  *    character ordering for the character set.  This concept includes
  87.  *    the notion of totally INGOREing some characters.  The LEXLATE.CSM
  88.  *    provided IGNOREs all characters but space, A-Z, a-z, 0-9.  It also
  89.  *    treats 'A' as less than but adjacent to 'a', etc.  If a specified
  90.  *    key field consists entirely of IGNORE characters, it is considered
  91.  *    the lowest order for that key.  A line which has no entry for the
  92.  *    specified key field (because it is too short) will be the next lowest
  93.  *    order in the sort for that field.
  94.  *
  95.  * Derived from: SORT3.C by H.R. Moran, Jr. 11/5/83
  96.  * changes made:
  97.  *    1) Re-format, indent, and comment to suit me, including deletion
  98.  *       of some extraneous declarations and code lines.
  99.  *    2) Re-write compar(), and include use of lexlate()
  100.  *    3) Add options() to allow key field selections.
  101.  *
  102.  * SORT3.C comments follow:
  103.  * --------------------------------------------------------------------------- 
  104.  *    Sort/Merge from Software Tools
  105.  *
  106.  *    Last Modified : 21 September 1982
  107.  *
  108.  *    Converted from Software Tools RATFOR to BDS C by Leor Zolman
  109.  *    Sep 2, 1982
  110.  *
  111.  *    Usage: sort <infile> <outfile>
  112.  *
  113.  *    Main variables have been made external; this is pretty much in
  114.  *    line with the RATFOR call-by-name convention anyway.
  115.  *
  116.  *    Requires lots of disk space, up to around three times the length
  117.  *    of the file file being sorted. This program is intended for files
  118.  *    bigger than memory; simpler, faster sorts can be implemented for
  119.  *    really short files (like ALPH.C)
  120.  *        -leor
  121.  *
  122.  *    Compile & Link:
  123.  *        A>cc sort.c -e2800 -o
  124.  *        A>l2 sort
  125.  *    (or...)
  126.  *        A>cc sort.c -e2900 -o
  127.  *        A>clink sort
  128.  *
  129.  */
  130.  
  131.  
  132. #include <bdscio.h>
  133.  
  134. #define SIGNON "ssort version 1.0 - 2/26/84 - hrm\n"
  135.  
  136. #define FUDGE 0xe /* offset into the lexlate function for table address */
  137. #define COLLATE_NAME collate_file()
  138.  
  139. /* #define DEBUG */    /* enables debug printout when defined */
  140.  
  141. #define BOOL  int        /* BOOlean */
  142. #define PROC  int        /* PROCedure */
  143. #define TRIAD int        /* -1, 0, or +1 */
  144.  
  145. #define IGNORE 0xff        /* lexlate() token to ignore the character */
  146.  
  147. #define VERBOSE 1        /* give running account of file activity */
  148.  
  149. #define MAXLINE 200        /* longest line we want to deal with */
  150. #define NBUFS 7            /* Max number of open buffered files */
  151. #define MAXPTR  3000        /* Max number of lines (set for dict) */
  152. #define MERGEORDER (NBUFS-1)    /* Max # of intermediate files to merge */
  153. #define NAMESIZE 20        /* Max Filename size */
  154. #define LOGPTR 13        /* smallest value >= log (base 2) of  MAXPTR */
  155. #define EOS '\0'        /* string termination character */
  156. #define FILE struct _buf
  157.  
  158. #define stderr 4
  159. #define fputc putc
  160.  
  161. char name[NAMESIZE], name2[NAMESIZE + 10];
  162. FILE buffers[NBUFS + 1];    /* up to NBUFS general-purp. buffered files */
  163. FILE *infil[MERGEORDER + 1];    /* tmp file ptrs for sort operation */
  164. unsigned linptr[MAXPTR + 1], nlines;
  165. int temp;
  166. unsigned maxtext;        /* max # of chars in main text buffer */
  167.  
  168. /*
  169.  * KEY FIELD selection support variables - hrm
  170.  */
  171. #define MAXFIELDS 20
  172. #define FIELDS struct _fields
  173.  
  174. FIELDS {
  175.   int _numfields;
  176.   int _strtcol[MAXFIELDS];
  177.   int _stopcol[MAXFIELDS];
  178.   } sortfields;
  179.  
  180. #define FASTLOCAL
  181.  
  182. #ifdef FASTLOCAL
  183.  
  184. /*
  185.  * FAST locals for compar()
  186.  */
  187. struct {
  188.   unsigned i, j;
  189.   unsigned k, l;
  190.   unsigned x1, x2;
  191.   unsigned len_i, len_j;
  192.   char c1, c2;
  193.   } z;
  194. #endif
  195.  
  196. #ifdef DEBUG
  197. char spacebuffer[200];
  198. #endif
  199.  
  200. /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
  201. /*!!!!!!!!!!!!!!!!              WARNING  (H.Moran)             !!!!!!!!! */
  202. /*! The algorithm INSISTS that THIS name be the LAST global           ! */
  203. /*!                                                                    ! */
  204. char *linbuf;        /* text area starts after this variable */
  205. /*                                                                       */
  206. /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
  207.  
  208. main(argc, argv)
  209.   int argc;
  210.   char *argv[];
  211. {
  212.  
  213.     int min(), gtext();
  214.  
  215.     FILE *infile, *outfile;        /* main input and output streams */
  216.     FILE *tmpfile;
  217.     unsigned high, lim, low;
  218.     BOOL more_text;
  219.  
  220.     puts(SIGNON);
  221.     linbuf = endext();        /* start of text buffer area */
  222.     maxtext = topofmem() - endext() - 500;
  223.     tmpfile = buffers[0];
  224.     options(&argc, argv);    /* process command line options */
  225.     if ( argc != 3 ) {
  226.       usage("");
  227.       }
  228.     infile = buffers[1];
  229.     if ( fopen(argv[1], infile) == ERROR ) {
  230.       puts("Can't open ");
  231.       puts(argv[1]);
  232.       exit(-1);
  233.       }
  234. #if VERBOSE
  235.     fputs("Beginning initial formation run\n", stderr);
  236. #endif
  237.     high = 0;        /* Initial formation of runs:    */
  238.     do {
  239.       more_text = gtext(infile);
  240.       quick(nlines);        
  241.       high++;
  242.       makfil(high, tmpfile);
  243.       ptext(tmpfile);
  244.       fclout(tmpfile);
  245.       } while ( more_text );
  246.     fclose(infile);        /* free up the input file buffer */
  247. #if VERBOSE
  248.     fputs("Beginning merge operation\n", stderr);
  249. #endif
  250.     for ( low = 1; low < high; low += MERGEORDER ) { /* merge */
  251.       lim = min(low + MERGEORDER - 1, high);
  252.       gopen(low, lim);        /* open files */
  253.       high++;
  254.       makfil(high, tmpfile);
  255.       merge(lim - low + 1, tmpfile);
  256.       fclout(tmpfile);    /* terminate, flush and close file */
  257.       gremov(low, lim);
  258.       }
  259.     /*
  260.      * Now write the sorted output file:
  261.      */
  262. #if VERBOSE
  263.     fputs("Merge complete. Writing output file.\n", stderr);
  264. #endif
  265.     gname(high, name);    /* create name of result file */
  266.     infile = buffers[0];
  267.     if ( fopen(name, infile) == ERROR ) {
  268.       puts("Something's screwy; I can't open ");
  269.       puts(name);
  270.       exit(-1);
  271.       }
  272.     outfile = buffers[1];
  273.     while ( fcreat(argv[2], outfile) == ERROR ) {
  274.       puts("Can't create ");
  275.       puts(argv[2]);
  276.       puts("\nEnter another name to call the output: ");
  277.       gets(name2);
  278.       argv[2] = &name2;
  279.       }
  280.     while ( fgets(linbuf, infile) ) {
  281.       fputs(linbuf, outfile);
  282.       fputs("\r\n", outfile);
  283.       }
  284.     fclout(outfile);
  285.     fabort(infile->_fd);
  286.     unlink(name);
  287. }
  288.  
  289.  
  290. PROC
  291. options(pac, av)
  292.   int *pac;
  293.   char *av[];
  294. {
  295.     int i, j;
  296.     char *s;
  297.  
  298.     sortfields._numfields  = 1;
  299.     sortfields._strtcol[0] = 0;
  300.     sortfields._stopcol[0] = 32767;
  301.     for ( i = 1; i < *pac; ++i ) {
  302.       if ( *av[i] == '-' && tolower(av[i][1]) == 'c' ) {
  303.         get_collating_sequence(atoi(&av[i][2]));
  304.         for ( j = i; j < *pac; ++j ) /* remove options from av[] */
  305.           av[j] = av[j+1];
  306.         *pac -= 1;
  307.         }
  308.       if ( *av[i] == '-' && tolower(av[i][1]) == 'k' ) {
  309.         s = av[i] + 2;
  310.         for ( j = 0; isdigit(*s) && j < MAXFIELDS; ++j ) {
  311.           sortfields._strtcol[j] = 0;
  312.           while ( isdigit(*s) ) {
  313.             sortfields._strtcol[j] *= 10;
  314.             sortfields._strtcol[j] += (*s++ - '0');
  315.             }
  316.           if ( (sortfields._strtcol[j] -= 1) < 0 )
  317.             sortfields._strtcol[j] = 0;
  318.           sortfields._stopcol[j] = 32767;
  319.           if ( *s == '-' ) {
  320.             ++s;
  321.             sortfields._stopcol[j] = 0;
  322.             while ( isdigit(*s) ) {
  323.               sortfields._stopcol[j] *= 10;
  324.               sortfields._stopcol[j] += (*s++ - '0');
  325.               }
  326.             if ( (sortfields._stopcol[j] -= 1) < 0 )
  327.               sortfields._stopcol[j] = 32767;
  328.             if ( *s != ',' )
  329.               break;
  330.             ++s;
  331.             }
  332.           else if ( *s != ',' )
  333.             break;
  334.           else
  335.             ++s;
  336.           sortfields._numfields++;
  337.           }
  338.         for ( j = i; j < *pac; ++j ) /* remove options from av[] */
  339.           av[j] = av[j+1];
  340.         *pac -= 1;
  341.         }
  342.       }
  343.     for ( i = 0; i < sortfields._numfields; ++i )
  344.       if ( sortfields._strtcol[i] > sortfields._stopcol[i] )
  345.         usage("ILLEGAL SORT KEY SPECIFICATION");
  346. }
  347.  
  348. PROC
  349. fclout(obuf)
  350.   FILE *obuf;
  351. {
  352.     putc(CPMEOF, obuf);
  353.     fflush(obuf);
  354.     fclose(obuf);
  355. }
  356.  
  357.  
  358. /*
  359.  * Quick: Quicksort for character lines
  360.  */
  361.  
  362. PROC
  363. quick(nlines)
  364.   unsigned nlines;
  365. {
  366.     unsigned i, j, lv[LOGPTR + 1], p, pivlin, uv[LOGPTR + 1];
  367.     int compar();
  368.  
  369.     lv[1] = 1;
  370.     uv[1] = nlines;
  371.     p = 1;
  372.     while ( p > 0 )
  373.       if ( lv[p] >= uv[p] )    /* only 1 element in this subset */
  374.         p--;        /* pop stack            */
  375.       else {
  376.         i = lv[p] - 1;
  377.         j = uv[p];
  378.         pivlin = linptr[j];    /* pivot line        */
  379.         while ( i < j ) {
  380.           for ( i++; compar(linptr[i], pivlin) < 0; i++ )
  381.             ;
  382.           for ( j--; j > i; j-- )
  383.             if ( compar(linptr[j], pivlin) <= 0 )
  384.               break;
  385.           if ( i < j ) {    /* out of order pair        */
  386. #ifdef DEBUG
  387.             printf("SWAPPING:\n%s\n%s\n\n",
  388.             &linbuf[linptr[i]], &linbuf[linptr[j]]);
  389. #endif
  390.             temp = linptr[i];
  391.             linptr[i] = linptr[j];
  392.             linptr[j] = temp;
  393.             }
  394.           }
  395.       j = uv[p];        /* move pivot to position 1     */
  396.       temp = linptr[i];
  397.       linptr[i] = linptr[j];
  398.       linptr[j] = temp;
  399.       if ( (i - lv[p]) < (uv[p] - i) ) {
  400.         lv[p + 1] = lv[p];
  401.         uv[p + 1] = i - 1;
  402.         lv[p] = i + 1;
  403.         }
  404.       else {
  405.         lv[p + 1] = i + 1;
  406.         uv[p + 1] = uv[p];
  407.         uv[p] = i - 1;
  408.         }
  409.       p++;
  410.       }            
  411. }            
  412.  
  413.  
  414. /*
  415.  * Ptext: output text lines from linbuf onto the buffered output file given
  416.  */
  417.  
  418. PROC
  419. ptext(outfil)
  420.   FILE *outfil;
  421. {
  422.     int i;
  423.  
  424.     for ( i = 1; i <= nlines; i++ ) {
  425.       fputs(&linbuf[linptr[i]], outfil);
  426.       fputc('\0', outfil);    /* terminate the line */
  427.       }
  428. }
  429.  
  430.  
  431. /*
  432.  * Gtext: Get text lines from the buffered input file provided, and
  433.  *       place them into linbuf
  434.  */
  435.  
  436. int
  437. gtext(infile)
  438.   FILE *infile;
  439. {
  440.     unsigned lbp, len;
  441.  
  442.     nlines = 0;
  443.     lbp = 1;
  444.     do {
  445.       if ( (len = fgets(&linbuf[lbp], infile)) == NULL )
  446.         break;
  447.       len = strlen(&linbuf[lbp]);
  448.       linbuf[lbp + len - 1] = '\0';
  449.       nlines++;
  450.       linptr[nlines] = lbp;
  451.       lbp += len;    /* drop '\n', but keep NULL at end of string */
  452.       } while ( lbp < (maxtext - MAXLINE) && nlines < MAXPTR );
  453.     return (len);        /* return 0 if done with file */
  454. }
  455.  
  456.  
  457. /*
  458.  * Makfil: Make a temporary file having suffix 'n' and open it for
  459.  *        output via the supplied buffer
  460.  */
  461.  
  462. PROC
  463. makfil(n, obuf)    /* make temp file having suffix 'n' */
  464.   int n;
  465.   FILE *obuf;
  466. {
  467.     FILE *fp;
  468.     char name[20];
  469.     gname(n, name);
  470.     if ( fcreat(name, obuf) == ERROR ) {
  471.       puts("Can't create ");
  472.       puts(name);
  473.       exit(-1);
  474.       }
  475. }
  476.  
  477.  
  478. /*
  479.  * Gname: Make temporary filename having suffix 'n'
  480.  */
  481.  
  482. char *
  483. gname(n, name)
  484.   char *name;
  485.   int n;
  486. {
  487.     char tmptext[10];
  488.  
  489.     strcpy(name, "TEMP");        /* create "TEMPn.$$$"    */
  490.     strcat(name, itoa(tmptext, n));
  491.     strcat(name, ".$$$");
  492.     return (name);        /* return a pointer to it    */
  493. }
  494.  
  495.  
  496. /*
  497.  * Itoa: convert integer value n into ASCII representation at strptr,
  498.  *      and return a pointer to it
  499.  */
  500.  
  501. char *
  502. itoa(strptr, n)
  503.   char *strptr;
  504.   int n;
  505. {
  506.     int length;
  507.  
  508.     if ( n < 0 ) {
  509.       *strptr++ = '-';
  510.       strptr++;
  511.       n = -n;
  512.       }
  513.     if ( n < 10 ) {
  514.       *strptr++ = (n + '0');
  515.       *strptr = '\0';
  516.       return (strptr - 1);
  517.       }
  518.     else {
  519.       length = strlen(itoa(strptr, n/10));
  520.       itoa(&strptr[length], n % 10);
  521.       return (strptr);
  522.       }
  523. }
  524.  
  525.  
  526. /*
  527.  * Gopen: open group of files low...lim
  528.  */
  529.  
  530. PROC
  531. gopen(low, lim)
  532.   int lim, low;
  533. {
  534.     int i;
  535.  
  536. #if VERBOSE
  537.     fprintf(stderr, "Opening temp files %d-%d\n", low, lim);
  538. #endif
  539.  
  540.     for ( i = 1; i <= (lim - low + 1); i++ ) {
  541.       gname(low + i - 1, name);
  542.       if ( fopen(name, buffers[i]) == ERROR ) {
  543.         puts("Can't open: ");
  544.         puts(name);
  545.         exit(-1);
  546.         }
  547.       infil[i] = &buffers[i];
  548.       }
  549. }
  550.  
  551.  
  552. /*
  553.  * Remove group of files low...lim
  554.  *        (should use "close" instead of "fabort" for MP/M II)
  555.  */
  556.  
  557. PROC
  558. gremov(low, lim)
  559.   int lim, low;
  560. {
  561.     int i;
  562.  
  563. #if VERBOSE
  564.     fprintf(stderr, "Removing temp files %d-%d\n", low, lim);
  565. #endif
  566.     for ( i = 1; i <= (lim - low + 1); i++ ) {
  567.       fabort(infil[i]->_fd);        /* forget about the file */
  568.       gname(low + i - 1, name);
  569.       unlink(name);            /* and physically remove it */
  570.       }
  571. }
  572.  
  573. /*
  574.  * Fputs: special version that doesn't epand LF's and aborts on error
  575.  */
  576.  
  577. PROC
  578. fputs(s, iobuf)
  579.   char *s;
  580.   FILE *iobuf;
  581. {
  582.     char c;
  583.  
  584.     while ( c = *s++ )
  585.       if ( putc(c, iobuf) == ERROR ) {
  586.         fputs("Error on file output\n", stderr);
  587.         exit(-1);
  588.         }
  589. }
  590.  
  591.  
  592. /*
  593.  * Merge: merge infil[1]...infil[nfiles] onto outfil
  594.  */
  595.  
  596. PROC
  597. merge(nfiles, outfil)
  598.   FILE *outfil;
  599. {
  600.     char *fgets();
  601.  
  602.     int i, inf, lbp, lp1, nf;
  603.  
  604.     lbp = 1;
  605.     nf = 0;
  606.     for ( i = 1; i <= nfiles; i++)  /* get one line from each file */
  607.       if ( fgets(&linbuf[lbp], infil[i]) != NULL ) {
  608.         nf++;
  609.         linptr[nf] = lbp;
  610.         lbp += MAXLINE;    /* leave room for largest line */
  611.         }
  612.     quick(nf);        /* make initial heap */
  613.     while ( nf > 0 ) {
  614.       lp1 = linptr[1];
  615.       fputs(&linbuf[lp1], outfil);                
  616.       fputc('\0', outfil);
  617.       inf = lp1 / MAXLINE + 1;    /* compute file index */
  618.       if ( fgets(&linbuf[lp1], infil[inf]) == NULL ) {
  619.         linptr[1] = linptr[nf];
  620.         nf--;
  621.         }
  622.       reheap(nf);
  623.       }
  624. }
  625.  
  626.         
  627. /*
  628.  * Reheap: propogate linbuf[linptr[1]] to proper place in heap
  629.  */
  630.  
  631. PROC
  632. reheap(nf)
  633.   unsigned nf;
  634. {
  635.     unsigned i, j;
  636.  
  637.     for ( i = 1; (i + i) <= nf; i = j ) {
  638.       j = i + i;
  639.       if ( j < nf && compar(linptr[j], linptr[j + 1]) > 0 )
  640.         j++;
  641.       if ( compar(linptr[i], linptr[j]) <= 0 )
  642.         break;
  643.       temp = linptr[i];
  644.       linptr[i] = linptr[j];
  645.       linptr[j] = temp;
  646.       }
  647. }
  648.  
  649. /*
  650.  * Just like regular library version, except that NULL is also
  651.  * taken as a string terminator.
  652.  */
  653.  
  654. char *
  655. fgets(s, iobuf)
  656.   char *s;
  657.   FILE *iobuf;
  658. {
  659.     int count, c;
  660.     char *cptr;
  661.     count = MAXLINE;
  662.     cptr = s;
  663.     if ( (c = getc(iobuf)) == CPMEOF || c == EOF )
  664.       return (NULL);
  665.     do {
  666.       if ( (*cptr++ = c) == '\n' ) {
  667.         if ( cptr>s+1 && *(cptr-2) == '\r' )
  668.           *(--cptr - 1) = '\n';
  669.         break;
  670.         }
  671.       if ( ! c )
  672.         break;
  673.        } while ( count-- && (c=getc(iobuf)) != EOF && c != CPMEOF );
  674.     if ( c == CPMEOF )
  675.       ungetc(c, iobuf);    /* push back control-Z */
  676.     *cptr = '\0';
  677.     return (s);
  678. }
  679.  
  680.  
  681. PROC
  682. usage(s)
  683.   char *s;
  684. {
  685.     fprintf(stderr, "\n%s\nUsage:\n", s);
  686.     fputs("\tssort <infile> <outfile> [-c<collating sequence>] [-k<sort key list>]\n",
  687.         stderr);
  688.     fputs("where <sort key list> is:\n", stderr);
  689.     fputs(" a comma separated list of column numbers or ranges\n", stderr);
  690.     fputs("specifing the sort key columns\n\te.g.\n", stderr);
  691.     fputs("-k3-5,7-9,1-2,12\n\tspecifies that\n", stderr);
  692.     fputs("       the primary sort key is columns  3 thru 5\n", stderr);
  693.     fputs("the next secondary sort key is columns  7 thru 9\n", stderr);
  694.     fputs("the next secondary sort key is columns  1 thru 2\n", stderr);
  695.     fputs("the last secondary sort key is columns 12 thru end of line.\n",
  696.         stderr);
  697.     fputs("\nThe leftmost column is numbered 1.\n", stderr);
  698.     fputs("The default sort key is the entire line.\n", stderr);
  699.     fputs("\n-c<n> selects the n'th collating sequence from the \"magic\"\n", stderr);
  700.     fprintf(stderr, "file %s. Where sequences are numbered from zero.\n",
  701.         COLLATE_NAME); 
  702.     exit();
  703. }
  704.  
  705.  
  706. /*
  707.  * Compar: Compare two strings; return 0 if equal, -1 if first is
  708.  *       lexically smaller, or 1 if first is bigger
  709.  */
  710.  
  711.  
  712.  
  713. TRIAD
  714. compar(lp1, lp2)
  715.   unsigned lp1, lp2;
  716. {
  717.     char lexlate();
  718.  
  719. #ifndef FASTLOCAL
  720.     struct {
  721.       unsigned i, j; /* string relative char positions being considered */
  722.       unsigned k, l;        /* scratch for # keys, key columns */
  723.       unsigned x1, x2;    /* string relative end of key field columns */
  724.       unsigned len_i, len_j; /* lengths of the two incoming strings */
  725.       char c1, c2;        /* characters currently being considered */
  726.       } z;
  727. #endif
  728.  
  729.     z.len_i = strlen(&linbuf[lp1]);
  730.     z.len_j = strlen(&linbuf[lp2]);
  731.     for ( z.k = 0; z.k < sortfields._numfields; ++z.k ) {
  732.       z.l  = sortfields._strtcol[z.k];    /* for each sort key */
  733.       z.i  = lp1 + min(z.l, z.len_i);
  734.       z.j  = lp2 + min(z.l, z.len_j);
  735.       z.l  = sortfields._stopcol[z.k];
  736.       z.x1 = lp1 + min(z.l, z.len_i);
  737.       z.x2 = lp2 + min(z.l, z.len_j);
  738.       do {                /* for each char position in a key */
  739.         while ( (z.c1=lexlate(linbuf[z.i])) == IGNORE )
  740.           if ( ++z.i > z.x1 )
  741.             break;
  742.         while ( (z.c2=lexlate(linbuf[z.j])) == IGNORE )
  743.           if ( ++z.j > z.x2 )
  744.             break;
  745.         if ( (z.i > z.x1) && (z.j <= z.x2) ) {
  746. #ifdef DEBUG
  747.           printf("END FIELD LESS THAN:\n%s\n%s\n",
  748.             &linbuf[lp1], spaces(z.i-lp1));
  749.           printf("%s\n%s\n\n", &linbuf[lp2], spaces(z.j-lp2));
  750. #endif
  751.           return (-1);
  752.           }
  753.         if ( (z.j > z.x2) && (z.i <= z.x1) ) {
  754. #ifdef DEBUG
  755.           printf("END FIELD GREATER THAN:\n%s\n%s\n",
  756.             &linbuf[lp1], spaces(z.i-lp1));
  757.           printf("%s\n%s\n\n", &linbuf[lp2], spaces(z.j-lp2));
  758. #endif
  759.           return (1);
  760.           }
  761.         if ( (z.i > z.x1) && (z.j > z.x2) )
  762.           break;
  763.         if ( z.c1 != z.c2 ) {
  764.           if ( z.c1 == IGNORE ) /* terminated on IGNORE class of char */
  765.             z.c1 = 0;
  766.           if ( z.c2 == IGNORE ) /* terminated on IGNORE class of char */
  767.             z.c2 = 0;
  768.           if ( z.c1 == z.c2 ) {
  769. #ifdef DEBUG
  770.             printf("MAPPED MISMATCH EQUAL TO:\n%s\n%s\n",
  771.             &linbuf[lp1], spaces(z.i-lp1));
  772.             printf("%s\n%s\n\n", &linbuf[lp2], spaces(z.j-lp2));
  773. #endif
  774.             return (0);
  775.             }
  776. #ifdef DEBUG
  777.           if ( z.c1 < z.c2 ) {
  778.             printf("MAPPED MISMATCH LESS THAN:\n%s\n%s\n",
  779.             &linbuf[lp1], spaces(z.i-lp1));
  780.             printf("%s\n%s\n\n", &linbuf[lp2], spaces(z.j-lp2));
  781.             }
  782.           else {
  783.             printf("MAPPED MISMATCH GREATER THAN:\n%s\n%s\n",
  784.             &linbuf[lp1], spaces(z.i-lp1));
  785.             printf("%s\n%s\n\n", &linbuf[lp2], spaces(z.j-lp2));
  786.             }
  787. #endif
  788.           return ((z.c1 < z.c2) ? -1 : 1);
  789.           }
  790.         ++z.i;
  791.         ++z.j;
  792.         } while ( 1 );
  793.       /*
  794.        * end of sort key field with equal keys, use next key field
  795.        */
  796.       }
  797.     /*
  798.      * Final result at end of ALL sort key fields
  799.      */
  800.     if ( z.c1 == IGNORE ) /* terminated on the IGNORE class of char */
  801.       z.c1 = 0;
  802.     if ( z.c2 == IGNORE ) /* terminated on the IGNORE class of char */
  803.       z.c2 = 0;
  804.     if ( z.c1 == z.c2 ) {
  805. #ifdef DEBUG
  806.       printf("FINAL EQUAL TO:\n%s\n%s\n",
  807.         &linbuf[lp1], spaces(z.i-lp1));
  808.       printf("%s\n%s\n\n", &linbuf[lp2], spaces(z.j-lp2));
  809. #endif
  810.       return (0);
  811.       }
  812. #ifdef DEBUG
  813.     if ( z.c1 < z.c2 ) {
  814.       printf("FINAL LESS THAN:\n%s\n%s\n",
  815.         &linbuf[lp1], spaces(z.i-lp1));
  816.       printf("%s\n%s\n\n", &linbuf[lp2], spaces(z.j-lp2));
  817.       }
  818.     else {
  819.       printf("FINAL GREATER THAN:\n%s\n%s\n",
  820.         &linbuf[lp1], spaces(z.i-lp1));
  821.       printf("%s\n%s\n\n", &linbuf[lp2], spaces(z.j-lp2));
  822.       }
  823. #endif
  824.     return ((z.c1 < z.c2) ? -1 : 1);
  825. }
  826.  
  827.  
  828. #ifdef DEBUG
  829. spaces(n)
  830. {
  831.     int i;
  832.  
  833.     spacebuffer[0] = '\0';
  834.     for ( i = 0; i < n; ++i )
  835.       spacebuffer[i] = ' ';
  836.     spacebuffer[i++] = '^';
  837.     spacebuffer[i] = '\0';
  838.     return (spacebuffer);
  839. }
  840. #endif
  841.  
  842.  
  843.  
  844. PROC
  845. get_collating_sequence(n)
  846.   int n;
  847. {
  848.     int lexlate();
  849.     char *p;
  850.     int f;
  851.  
  852. #define INPUT 0
  853. #define ABSOLUTE 0
  854.     if ( (f=open(COLLATE_NAME, INPUT)) < 0 ) {
  855.       fprintf(stderr, "Can't find file %s\n", COLLATE_NAME);
  856.       exit();
  857.       }
  858.     if ( seek(f, 2*n, ABSOLUTE) < 0 ) {
  859.       fprintf(stderr, "Error in seeking on file %s\n", COLLATE_NAME);
  860.       exit();
  861.       }
  862.     p = lexlate;
  863.     p += FUDGE;
  864.     if ( read(f, p, 2) != 2 ) {
  865.       fprintf(stderr, "Error in reading file %s\n", COLLATE_NAME);
  866.       exit();
  867.       }
  868.     fabort(f);
  869. }
  870.  
  871.  
  872. char *
  873. collate_file()
  874. {
  875.     return ("SSORT.OVL\0xxxxxxxxx");
  876. }
  877. .j-lp2));
  878.       }
  879.     else {
  880.       printf("FINAL GREATER THAN:\n%s\