home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 3 Comm / 03-Comm.zip / QSORT21.ZIP / QSORT.C < prev    next >
Text File  |  1989-11-29  |  14KB  |  470 lines
  1.  
  2. /* QSort/2 2.1, vaguely based on Use_Sort version 2.3, 25 November 1988 */
  3.  
  4. /*
  5.    This program sorts a text file (FIDOUSER.LST) according to specified
  6.    sort keys.  Valid key specifications (following input, output) are:
  7.      / = begin key field definition
  8.    +|- = direction, ascending|descending
  9.      C = starting column number, beginning with 1
  10.      : = end of column, beginning of length
  11.      L = length of key field, beginning with 1
  12.    ... = repeating for up to 10 key fields.
  13.  
  14.    For example, ParseLst calls QSort(/2) with this command line:
  15.  
  16.    QSort(/2) FidoUser.$$1 /+1:41 /-61:5 /-41:13 /+55:6
  17.  
  18.    Which will cause the lines in FidoUser.$$1 to be ordered by those
  19.    fields, with equal key fields causing the next field to be tested.
  20.    When all the specified key field tests are done, otherwise equal
  21.    lines will be left as is.
  22.  
  23. -----------------------------------------------------------------------------
  24. QSort/2 is written in IBM C/2 1.1, roughly equivalent to MSC 5.1, but will
  25. be intended to run solely in OS/2 Protected mode, duplicating the function
  26. of Ben Baker's excellent DOS-only QSORT program regarding ParseLst.
  27.  
  28. In the spirit of BBS (Bit Bucket Software), this program is also entered
  29. into the Public Domain.  This means that if you mess with it, and break
  30. it, you own both pieces.
  31.  
  32. -----------------------------------------------------------------------------
  33. [Notice in the original source file from which QSort/2 is derived:]
  34.  
  35. Copyright (c) 1988 by Jeffrey J. Nonken. Released to public domain
  36. September 1988. This is public domain; no strings, no bullshit. Do what you
  37. want with it. Nobody owns it.
  38.  
  39. However, I would like it if you would refer all changes and enhancements to
  40. me. This way I can maintain it properly. Thanks.
  41.  
  42. Jeffrey J. Nonken: sysop of Opus 103/522 Orange, Ca. (714)997-8958
  43. Please send correspondence to:
  44. 507 Ave. Presidio
  45. San Clemente, Ca. 92672
  46.  
  47. This was [originally] written in Microsoft C 5.1.
  48.  
  49.  */
  50.  
  51. #include <stdio.h>
  52. #include <stdlib.h>
  53. #include <malloc.h>
  54. #include <sys\types.h>
  55. #include <sys\stat.h>
  56. #include <string.h>
  57. #include <io.h>
  58. #include <ctype.h>
  59.  
  60. #include "stuff.h"
  61.  
  62.  
  63. #define lint        long int
  64. #define word        unsigned int
  65. #define byte        unsigned char
  66. #define NEAR        near
  67.  
  68. /* #define DEBUG       debug */
  69.  
  70. typedef struct
  71.    {
  72.       int  key;            /* ASCENDING=0, DESCENDING!=0   */
  73.       int  scol;           /* Key starting column, 0-based */
  74.       int  klen;           /* Key field length in columns  */
  75.     } sortkey;
  76.  
  77. sortkey keys[10];
  78.  
  79. char far ** NEAR ptr = NULL;
  80. lint     U1O = -1;
  81. lint     U2O = -1;
  82.  
  83. char one_record[MAX_REC];
  84.  
  85. int numkeys=0;               /* Number of keys defined       */
  86. word file_size;            /* Number of records in file    */
  87.  
  88. int flag = FALSE;
  89. int show=FALSE;            /* Show-only switch               */
  90. int slash=FALSE;           /* key entered switch           */
  91.  
  92. FILE_TYPE input_file;
  93. FILE_TYPE output_file;
  94. FILE_TYPE temp_out;
  95.  
  96. FILE        * NEAR old_file;          /* file to sort */
  97. FILE        * NEAR new_file;         /* destination of sorted file. */
  98.  
  99.  
  100. /****************************************************************************
  101.                      Comparison routine for qsort.
  102. ****************************************************************************/
  103. int compare(char far **user1,char far **user2);
  104. /* Return *user1-*user2 for ascending, reverse for descending */
  105. int compare(char far **user1,char far **user2)
  106. {
  107. register int    j;
  108. register int    k;
  109. sortkey       *SK;      /* pointer to successive entries     */
  110. char   far      *U1;      /* de-referenced pointer to *user1 */
  111. char   far      *U2;      /* de-referenced pointer to *user2 */
  112.  
  113. /*
  114.   Not much is left of the original algorithm referred to below.  If you
  115.   cook up anything better, here's where the biggest buy-back will come.
  116.  
  117.   This routine is passed the NEAR array entries of FAR pointers to the
  118.   in-memory lines to be compared by the "numkeys" number of "keys".
  119.  
  120.   Comment from the original USE-SORT 2.3, updated:
  121.  
  122.   This may take a little explanation. k goes through the sort key array,
  123.   picking out the next sort key. j is simply the result of each compare.
  124.   i is used to perform the compare based on the entry in sortkey keys.
  125.   Each loop through tests one key. As long as j == 0, the entries are
  126.   identical. If j != 0 then there was a difference, and we drop through
  127.   to check for descending order and return the result. If j never becomes
  128.   non-0 we will reach the end of order[] and return a 0 result.
  129.  
  130.   I lifted this algorithm from Mike Housky's PAKSORT program. Thanks, Mike.
  131.  */
  132.  
  133. /* Get the two records to be compared */
  134.  
  135.     SK = keys;
  136. #ifdef DEBUG
  137.     (void)printf("U1 = %s\n",*user1);
  138.     (void)printf("U2 = %s\n",*user2);
  139. #endif
  140.     for (j = k = 0; (k < numkeys) && (!j); ++k)
  141.     {
  142. #ifdef DEBUG
  143.         (void) printf("scol = %d, klen = %d, user1 len = %d\n",SK->scol,SK->klen,strlen(*user1));
  144. #endif
  145.         if (SK->scol < (int)(strlen(*user1)))
  146.         {
  147.             U1 = *user1 + SK->scol;
  148.             U2 = *user2 + SK->scol;
  149.  
  150.             if (j = strnicmp( U1, U2, SK->klen))
  151.             {
  152.                 if (SK->key)
  153.                    j = -j;
  154.                 break;
  155.             }
  156.         }
  157.         ++SK;
  158.     }
  159. #ifdef DEBUG
  160.     (void)printf("compare = %d\n", j);
  161. #endif
  162.     if (j)
  163.     {
  164.         flag = TRUE;
  165.     }
  166.     return(j);
  167. }
  168.  
  169. /* #pragma check_stack- */
  170.  
  171. /* Now write the new file based on pointers in ptr[] */
  172. int write_new_file(void);
  173. int write_new_file(void)
  174. {
  175. register word i;
  176. char far **pntr;
  177.  
  178.     (void) printf(" Writing new file...");
  179.     if ((new_file = fopen(temp_out.filename,"w")) == NULL)
  180.     {
  181.         (void) fprintf (stderr,"Cannot open output file %s!\n", temp_out.filename);
  182.         return(3);
  183.     }
  184.     pntr = ptr;
  185.     for ( i = 0; i < file_size; ++i)
  186.     {
  187.         if (fputs (*(pntr++), new_file))
  188.         {
  189.             (void) fprintf(stderr,"Error writing output file!\n");
  190.             (void) fclose(new_file);
  191.             return(3);
  192.         }
  193.     }
  194.     (void) fclose (new_file);
  195.     if ( strcmp ( output_file.filename, temp_out.filename) != 0 )
  196.     {
  197.         (void) printf (" Renaming...");
  198.         unlink (output_file.filename);
  199.         rename (temp_out.filename, output_file.filename);
  200.     }
  201.     (void) printf(" done.\n");
  202.     return(0);
  203. }
  204. /* #pragma check_stack+ */
  205.  
  206. /****************************************************************************
  207. Step 1: build array of pointers to in-memory far lines of the old file.
  208. Step 2: quicksort.
  209. Step 3: if not already in order, write the lines in array order.
  210. ****************************************************************************/
  211. int do_sort(void);
  212. int do_sort()
  213. {
  214. lint i;
  215. int j;
  216. struct stat stat_buff;
  217. sortkey *kp;
  218. char far ** pntr;
  219.  
  220.     if (show == TRUE)
  221.     {
  222.         for (j = 0; j < numkeys; ++j)
  223.         {
  224.             kp = &keys[j];
  225.             (void) printf("key %d is %c, from %d for %d columns\n", j+1, kp->key ? '-' : '+', kp->scol + 1, kp->klen);
  226.         }
  227.     }
  228.     old_file = fopen(input_file.filename,"r");     /* open for text */
  229.     if (old_file == NULL)                          /* was there one? */
  230.     {
  231.         (void) fprintf(stderr,"Cannot open file %s!\n",input_file.filename);
  232.         return(2);
  233.     }
  234.     (void) stat(input_file.filename,&stat_buff);                /* how big? */
  235.     (void) fgets(one_record, (int) sizeof(one_record), old_file);
  236.     file_size = (word)(((lint)stat_buff.st_size) / ((lint) ((lint)strlen(one_record))+1L));
  237.     (void) fseek(old_file,0L,SEEK_SET);                         /* rec 0 */
  238.     if ((int) strlen(one_record) >= (int) sizeof(one_record))    /* check line len */
  239.     {
  240.         (void) fprintf(stderr,"Lines too long to sort.\n");     /* too long to sort */
  241.         (void) fclose(old_file);
  242.         return(1);
  243.     }
  244.     if (file_size == 0)                                 /* # entries */
  245.     {
  246.         (void) fprintf(stderr,"Empty file.\n");              /* empty, nothing done */
  247.         (void) fclose(old_file);
  248.         return(1);
  249.     }
  250.     (void) printf("File has %d entries, %d long each.\n",file_size, strlen(one_record)+1);
  251.     ptr = (char far **)calloc(file_size,sizeof(char far *));
  252.     if (ptr == NULL)                    /* allocate array of far pointers */
  253.     {
  254.         (void) fprintf(stderr,"Cannot allocate enough memory for pointers!\n");
  255.         (void) fclose(old_file);
  256.         return(2);
  257.     }
  258.  
  259.     (void) printf(" Reading old file...");
  260.     pntr = ptr;
  261.     for (i = 0; i < file_size; ++i)
  262.     {
  263.         if (!(*pntr = (char far *) _fmalloc(sizeof(one_record))))
  264.         {
  265.             (void) fprintf(stderr,"Cannot allocate enough memory for records!\n");
  266.             (void) fclose(old_file);
  267.             return(2);
  268.         }
  269.         if (!(fgets(*(pntr++), (int) sizeof(one_record), old_file)))
  270.         {
  271.             (void) fprintf(stderr,"Error reading input file!\n");
  272.             (void) fclose(old_file);
  273.             return(2);
  274.         }
  275.     }
  276.     (void) fclose(old_file);
  277.  
  278. /*
  279. Rather than sort the array of entries, we sort the array of pointers.
  280. This allows us to sort a near array of char far lines.
  281. Huge pointer arithmetic is expensive.
  282. */
  283.  
  284.     (void) printf(" Sorting old file...");
  285. #ifdef DEBUG
  286.     (void) printf("\nnumkeys = %d\n",numkeys);
  287. #endif
  288.     qsort((void far *)&ptr[0], (size_t)file_size, sizeof(char far *), compare);
  289.  
  290.     if (!flag)
  291.     {
  292.         (void) printf("\nFile already sorted! Nothing done.\n");
  293.         return(0);
  294.     }
  295.     return(write_new_file());
  296. }
  297.  
  298. /****************************************************************************
  299.                     Process command-line parameters.
  300.  
  301.     input_file = replaces input and output (stdin, stdout) filenames
  302.     output_file= replaces output (copied from input) filename
  303.     ?  = print help screen and exit
  304.     /? = display keys after parsing, without sorting
  305.     /+ = key field, ascending
  306.     /- = key field, descending
  307.  
  308.  sort key format:
  309.   /sccc:lll
  310.   s = sequence (Ascending or Descending)
  311.   c = scol, starting column, 0-based
  312.   l = klen, length of key field in columns
  313. ***************************************************************************/
  314. int process_args(char *arg);
  315. int process_args(char *arg)
  316. {
  317. char    *tok;
  318. static char token[] = "   ";
  319. sortkey *kp;
  320. int slen;
  321.  
  322.     kp = &keys[numkeys];               /* init to next entry in keys */
  323.  
  324.     tok = strtok(arg,"\n");
  325.     if ((tok != NULL) && (*tok != '\0'))
  326.     {
  327.         switch(toupper(*tok))
  328.         {
  329.             case '/':
  330.                 slash = TRUE;
  331.                 ++tok;
  332.                 switch(toupper(*tok))
  333.                 {
  334.                     case '?':
  335.                         if (show || (*(++tok) != '\0'))
  336.                         {
  337.                             (void) fprintf(stderr,"Invalid sort criterion: /?.\n");
  338.                            return(1);
  339.                         }
  340.                         show = TRUE;
  341.                         break;
  342.                     case '-':   /* Process descending key */
  343.                     case '+':   /* Process ascending key  */
  344.                         if (++numkeys > 9)
  345.                         {
  346.                             (void) fprintf(stderr,"Too many sort keys.\n");
  347.                             return(1);
  348.                         }
  349.                         kp->key = *tok -  '+';
  350.                         ++tok;
  351.                         slen = strcspn(tok, ":");
  352.                         if ((strchr (tok, (int) ':') == NULL) || (slen < 1) || (slen > 3))
  353.                         {
  354.                             (void) fprintf(stderr,"Invalid sort criterion: /%s.\n",--tok);
  355.                             return(1);
  356.                         }
  357.                         (void) strncpy( token, tok, (size_t) slen);
  358.                         kp->scol = atoi(token) - 1;
  359.                         tok += slen + 1;
  360.                         slen = (int) strlen(tok);
  361.                         if ((slen < 1) || (slen > 3))
  362.                         {
  363.                             (void) fprintf(stderr,"Invalid sort criterion: /...%s.\n",--tok);
  364.                             return(1);
  365.                         }
  366.                         kp->klen = atoi(tok);
  367.                         break;
  368.                     default:             /* Oops */
  369.                         (void) fprintf(stderr,"Invalid sort criterion: /%s.\n",tok);
  370.                         return(1);
  371.                 }
  372.                 break;
  373.             case '?':
  374.                 (void) fprintf(stderr,"Invalid sort criterion: %s.\n",tok);
  375.                 return(1);
  376.             default:             /* Process filein, fileout */
  377.                 if (!slash)
  378.                 {
  379.                     if (strcmp( input_file.filename, "stdin") == 0)
  380.                     {
  381.                         (void) strcpy( input_file.filename, tok);
  382.                         (void) strcpy( output_file.filename, tok);
  383.                         (void) strcpy( temp_out.filename, "QSORT.$$$");
  384.                         break;
  385.                     }
  386.                     if (strcmp( output_file.filename, input_file.filename) == 0)
  387.                     {
  388.                         (void) strcpy( output_file.filename, tok);
  389.                         (void) strcpy( temp_out.filename, tok);
  390.                         break;
  391.                     }
  392.                 }
  393.                 else
  394.                 {
  395.                     (void) fprintf(stderr,"Invalid sort criterion: %s.\n",tok);
  396.                     return(1);
  397.                 }
  398.         }
  399.     }
  400.     return(0);
  401. }
  402.  
  403. /****************************************************************************
  404.                     Display this if ? was specified.
  405. ****************************************************************************/
  406. void print_help(void);
  407. void print_help()
  408. {
  409.     (void) printf("QSort/2 Syntax: [input [output]] [?|keys]\n\n");
  410.     (void) printf("Copyright 1989 by William R. Andrus, released to Public Domain.\n\n");
  411.     (void) printf("QSort/2 will sort a file by up to 10 key fields.  Its intended for\n");
  412.     (void) printf("use by ParseLst in OS/2 Protected Mode.  If neither filename is\n");
  413.     (void) printf("given, they default to stdin and stdout.  If one filename is given,\n");
  414.     (void) printf("it becomes both the input and output filename.  Key fields are\n");
  415.     (void) printf("specified in descending order of priority.  Valid keys are:\n");
  416.     (void) printf("  /s[c[c[c]]:l[l[l]]]\n");
  417.     (void) printf("  / : identifies a key\n");
  418.     (void) printf("  s : one of + (ascending), - (descending), or ? (show)\n");
  419.     (void) printf("  c : beginning column number, 1-999\n");
  420.     (void) printf("  l : length of field, 1-999\n");
  421.     (void) printf("Each key must contain a +, -, or ?, with no spaces permitted.\n");
  422.     (void) printf("If a key contains a + or -, the c:l must be specified.");
  423.     (void) printf("If a key contains ?, no other data is permitted.");
  424.     (void) printf("If a key containing ? is given, no sort is performed but the list of\n");
  425.     (void) printf("keys is displayed on stdout.\n\n");
  426.     (void) printf("QSort/2 requires fixed length records, up to 128 characters in length.\n\n");
  427.     exit(0);
  428. }
  429.  
  430. /****************************************************************************
  431.                                Main program.
  432. ****************************************************************************/
  433. main(int,char **);
  434. main(argc,argv)
  435. int argc;
  436. char    *argv[];
  437.  
  438. {
  439. int     i, j;
  440.  
  441.     if (argc > 1) if (argv[1][0] == '?')
  442.         print_help();
  443.  
  444.     (void) printf("QSort/2: OS/2 Text file sort program.\n");
  445.     (void) printf("Version 2.1  29 November 1989\n\n");
  446.  
  447.     /* Initialize file names */
  448.     (void) strcpy( input_file.filename, "stdin");
  449.     (void) strcpy( output_file.filename, "stdout");
  450.     (void) strcpy( temp_out.filename, "stdout");
  451.  
  452.     for (i = 1; i < argc; ++i)
  453.         if (process_args(argv[i]))
  454.             return(1);
  455.  
  456.     i = do_sort();
  457.  
  458.     if (i)
  459.         return(i);
  460.     if (ptr != NULL) {
  461.         for (j = 0; j < file_size; ++j) {
  462.             if (ptr[j])
  463.                 _ffree(ptr[j]);
  464.         }
  465.         free((char *)ptr);
  466.     }
  467.     (void) fcloseall();
  468.     return(i);
  469. }
  470.