home *** CD-ROM | disk | FTP | other *** search
/ Boston 2 / boston-2.iso / DOS / PROGRAM / C / PDSORT / PDSORT.C < prev    next >
C/C++ Source or Header  |  1993-12-01  |  13KB  |  466 lines
  1. /*
  2.    ****************************  NOTICE!  **************************
  3.    *   Contrary to the current trend  in  MS-DOS  software  this   *
  4.    *   program,  for  whatever  it is worth,  is NOT copyrighted   *
  5.    *   (with the exception of the runtime library  from  Borland   *
  6.    *   International's  Turbo  C)!  The program,  in whole or in   *
  7.    *   part,  may be used freely in any fashion  or  environment   *
  8.    *   desired.  If  you  find this program to be useful to you,   *
  9.    *   do NOT send any contribution to the author;  in the words   *
  10.    *   of  Rick  Conn,   'Enjoy!'  However,   if  you  make  any   *
  11.    *   improvements,  I would enjoy  receiving  a  copy  of  the   *
  12.    *   modified  source.  I  can  be reached,  usually within 24   *
  13.    *   hours,  by  messages  on  any  of  the  Phoenix  systems,   *
  14.    *   particularly:                                               *
  15.    *                                                               *
  16.    *               Technoids Anonymous     [PCBOARD]               *
  17.    *                   (602) 899-4876   300/1200/2400 bps          *
  18.    *                                                               *
  19.    *   All can be reached through PC Pursuit.                      *
  20.    *                                                               *
  21.    *   or:                                                         *
  22.    *                on GEnie, mail address: DON-WILL               *
  23.    *                on CompuServ:           75410,543              *
  24.    *                                                               *
  25.    *   Every  effort has been made to avoid error and moderately   *
  26.    *   extensive testing has been  performed  on  this  program,   *
  27.    *   however, the author does not warrant it to be fit for any   *
  28.    *   purpose  or  to  be  free  from  error  and disclaims any   *
  29.    *   liability for actual or any other damage arising from the   *
  30.    *   use of this program.                                        *
  31.    *****************************************************************
  32. */
  33.  
  34. #include <stdlib.h>
  35. #include <stdio.h>
  36. #include <string.h>
  37. #include <alloc.h>
  38. #include <ctype.h>
  39. #include <dir.h>
  40. #include <dos.h>
  41. #include <limits.h>
  42.  
  43. #include "queue.h"
  44.  
  45. void            GetArgs(int argc, char *argv[]);
  46. void            InvalArgu(char *Msg);
  47. unsigned        FillSortArray(void);
  48. void            Usage(void);
  49. int             isdevice(int handle);
  50.  
  51. void            Merge(void);
  52.  
  53. unsigned long   MaxMem;
  54. unsigned        S_ArraySize;
  55. char          **SortArray;
  56. int             KeyCount = 0;
  57. int             RecLen = -1;
  58. unsigned long   DiskAdr = 0;
  59. unsigned long   NextAdr = 0;
  60. unsigned long   EndAdr;
  61. long            TotalRecs = 0;
  62. long            OutCount = 0;
  63. char            *Buffer;
  64. FILE           *fin = NULL;
  65. FILE           *fint, *fout;
  66. unsigned long   lnno = 0;
  67. QUE_DEF        *Keys, Runs;
  68. long            BufSize;
  69. char            IntPath[65] = "";
  70.  
  71. unsigned        DeBug = 0;
  72.  
  73. struct KeyEntry {
  74.     int             Begin;
  75.     int             Len;
  76.     char            Order;
  77.     char            Case;
  78.     char            Type;
  79.     };
  80.  
  81. typedef struct RunStruct {
  82.     unsigned long   Begin;
  83.     unsigned long   Count;
  84.     }               RUN_ENT;
  85.  
  86. char            InputName[65] = "";
  87. char            OutName[65] = "";
  88. char            IntName[65] = "";
  89. long            Temp;
  90. int             QuietSwt = 0;
  91. int                Verbose  = 0;
  92.  
  93.  void
  94. main (int argc, char *argv[]) {
  95.     extern int      comp();
  96.  
  97.     unsigned        i;
  98.     unsigned        Count;
  99.     RUN_ENT        *r;
  100.     struct dfree    DiskTab;
  101.     char           *p;
  102.     char            OutDisk;
  103.     char            IntDisk;
  104.     long            DiskFree;
  105.     struct KeyEntry *t;
  106.  
  107.     if ((Keys = malloc(sizeof(QUE_DEF))) == NULL) {
  108.         fprintf(stderr, "Insufficient memory for Key queue.\n");
  109.         exit(12);
  110.         }
  111.     InitQueue(Keys);
  112.     InitQueue(&Runs);
  113.     if (argc < 2) {
  114.         fin = stdin;
  115.         fout = stdout;
  116.         }
  117.     else {
  118.         GetArgs(argc, argv);
  119.         }
  120.     if (RecLen == -1) RecLen = 258;
  121.     if (!QuietSwt)
  122.         fprintf(stderr, "PDSORT Version 3.1.0:  April 15, 1991\n");
  123.     if ( (Buffer = malloc(RecLen + 2)) == NULL) {
  124.         fprintf(stderr, "Insufficient memory for input buffer!\n");
  125.         exit(1);
  126.         }
  127.     if (fin != stdin) {
  128.         if ((fin = fopen(InputName, "r")) == NULL) {
  129.             fprintf(stderr, "I can't find input file: %s", InputName);
  130.             perror("");
  131.             exit(2);
  132.             }
  133.         }
  134.     if (!isdevice(fileno(fin))) {
  135.         fseek(fin, 0, SEEK_END);
  136.         EndAdr = ftell(fin);
  137.         fseek(fin, 0, SEEK_SET);
  138.         }
  139.     else EndAdr = 0;
  140.  
  141.     if (fin != stdin) {
  142.         if ((p = strchr(OutName, ':')) != NULL) OutDisk = toupper(OutName[0]);
  143.         else OutDisk = getdisk() + 1;
  144.         getdfree(OutDisk, &DiskTab);
  145.         DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
  146.         if (DiskFree < EndAdr) {
  147.             fprintf(stderr, "Insufficient space on output disk.\n");
  148.             exit(5);
  149.             }
  150.         if (IntPath[0] != '\0') {
  151.             if (IntPath[1] == ':') IntDisk = toupper(IntPath[0]);
  152.             else IntDisk = getdisk() + 1;
  153.             }
  154.         else {
  155.             if ((p = strrchr(OutName, '\\')) != NULL)
  156.                 strncpy(IntPath, OutName, (int) (p - OutName + 1));
  157.             else {
  158.                 IntPath[0] = OutDisk + '@';
  159.                 IntPath[1] = ':';
  160.                 IntPath[2] = '\\';
  161.                 getcurdir(OutDisk, &IntPath[3]);
  162.                 }
  163.             if (strchr(IntPath, ':') == NULL) IntDisk = OutDisk;
  164.             else IntDisk = IntPath[0] - '@';
  165.             }
  166.         getdfree(IntDisk, &DiskTab);
  167.         DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
  168.         if (DiskFree < EndAdr) {
  169.             fprintf(stderr, "Insufficient space on intermediate disk.\n");
  170.             exit(6);
  171.             }
  172.         }
  173.     if (Keys->Count == 0) {
  174.         if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
  175.             fprintf(stderr, "Insufficient memory for Key entry.\n");
  176.             exit(12);
  177.             }
  178.         t->Order = 'a';
  179.         t->Case = 'm';
  180.         t->Type = 'c';
  181.         t->Begin = 0;
  182.         t->Len = RecLen;
  183.         Enque(Keys, t);
  184.         }
  185.     MaxMem = coreleft();
  186.     MaxMem -= 4 * 1024L;
  187.  
  188.     S_ArraySize = (unsigned) (MaxMem / (RecLen + 2 + sizeof(char far *) + 10));
  189.     if (S_ArraySize > UINT_MAX / sizeof(char far *))
  190.         S_ArraySize = UINT_MAX / sizeof(char far *);
  191.     if ((SortArray = malloc(S_ArraySize * sizeof(char far *))) == NULL) {
  192.         fprintf(stderr, "Major Error! Insufficient memory for Sort Array.\n");
  193.         exit(12);
  194.         }
  195.  
  196.     for (i = 0;
  197.          (i < S_ArraySize && coreleft() >= ((4 * 1024L) + RecLen + 2));
  198.          i++) {
  199.         if ((SortArray[i] = malloc(RecLen + 2)) == NULL) {
  200.             fprintf(stderr, "Major Error! Insufficient memory for sort item.\n");
  201.             exit(12);
  202.             }
  203.         }
  204.     S_ArraySize = i;
  205.     if (!QuietSwt)
  206.         fprintf(stderr, "Max records per run = %d\n", S_ArraySize);
  207.  
  208.     BufSize = (coreleft() - 1024) / 2;
  209.  
  210.     if (Verbose && !QuietSwt) printf(" Run # %d\n", Runs.Count + 1);
  211.     Count = FillSortArray();
  212.  
  213.     TotalRecs += Count;
  214.     if (NextAdr >= EndAdr) {
  215.         if (!QuietSwt)
  216.             fprintf(stderr, "Total records read = %ld\n", TotalRecs);
  217.         if (fin != stdin) {
  218.             fclose(fin);
  219.             if ((fout = fopen(OutName, "w")) == NULL) {
  220.                 fprintf(stderr, "I can't create output file: %s", OutName);
  221.                 perror("");
  222.                 exit(7);
  223.                 }
  224.             }
  225.         errno = 0;
  226.         if (Verbose && !QuietSwt) printf("\tSorting\n");
  227.         qsort(SortArray, Count, sizeof(char far *), comp);
  228.  
  229.         if (Verbose && !QuietSwt) printf("\tWriting\n");
  230.         for (i = 0; i < Count; i++) {
  231.             fputs(SortArray[i], fout);
  232.             if (errno) {
  233.                 perror("I/O error on output file");
  234.                 exit(8);
  235.                 }
  236.             OutCount++;
  237.             }
  238.         }
  239.     else {
  240.         while (Count > 0) {
  241.             if (fint == NULL) {
  242.                 strcpy(IntName, IntPath);
  243.                 strcat(IntName, "\\SORT.$$$");
  244.                 if ((fint = fopen(IntName, "w")) == NULL) {
  245.                     fprintf(stderr, "I can't create sort intermediate file: %s", IntName);
  246.                     perror("");
  247.                     exit(9);
  248.                     }
  249.                 errno = 0;
  250.                 }
  251.             DiskAdr = ftell(fint);
  252.  
  253.             if (Verbose && !QuietSwt) printf("\tSorting\n");
  254.             qsort(SortArray, Count, sizeof(char far *), comp);
  255.  
  256.             if ((r = malloc(sizeof(RUN_ENT))) == NULL) {
  257.                 fprintf(stderr, "Insufficient memory for Run Entry!\n");
  258.                 exit(12);
  259.                 }
  260.             r->Begin = DiskAdr;
  261.             r->Count = Count;
  262.             Enque(&Runs, r);
  263.  
  264.             if (Verbose && !QuietSwt) printf("\tWriting\n");
  265.             for (i = 0; i < Count; i++) {
  266.                 fputs(SortArray[i], fint);
  267.                 if (errno) {
  268.                     perror("I/O error on intermediate file");
  269.                     exit(10);
  270.                     }
  271.                 }
  272.             if (Verbose && !QuietSwt) printf("    Run # %d\n", Runs.Count + 1);
  273.             Count = FillSortArray();
  274.             TotalRecs += Count;
  275.             }
  276.         if (!QuietSwt)
  277.             fprintf(stderr, "Total records read = %ld\n", TotalRecs);
  278.         if (fin != stdin) {
  279.             fclose(fin);
  280.             if ((fout = fopen(OutName, "w")) == NULL) {
  281.                 fprintf(stderr, "I can't create output file: %s", OutName);
  282.                 perror("");
  283.                 exit(7);
  284.                 }
  285.             }
  286.         errno = 0;
  287.         if (Verbose && !QuietSwt) printf("\tSorting\n");
  288.         qsort(SortArray, Count, sizeof(char far *), comp);
  289.         for (i = 0; i < Count; i++) {
  290.             fputs(SortArray[i], fout);
  291.             if (errno) {
  292.                 perror("I/O error on output file");
  293.                 exit(8);
  294.                 }
  295.             }
  296.         Merge();
  297.         }
  298.     unlink(IntName);
  299.     if (!QuietSwt)
  300.         fprintf(stderr, "Total records written = %ld\n", OutCount);
  301.     exit(0);
  302.     }
  303.  
  304.  
  305.  void
  306. GetArgs (int argc, char *argv[]) {
  307.     extern int      QuietSwt;
  308.     extern int        Verbose;
  309.  
  310.     int             i;
  311.     char           *p1, *p2;
  312.     struct KeyEntry *t;
  313.  
  314.     for (i = 1; i < argc; ++i) {
  315.         if (argv[i][0] != '-') continue;
  316.         if (!strcmp(argv[i], "-")) {
  317.             fin = stdin;
  318.             fout = stdout;
  319.             continue;
  320.             }
  321.         switch (tolower(argv[i][1])) {
  322.             case 't':
  323.                 strcpy(IntPath, &argv[i][2]);
  324.                 break;
  325.             case 'q':
  326.                 QuietSwt = 1;
  327.                 break;
  328.             case 'v':
  329.                 Verbose = 1;
  330.                 break;
  331.             default:
  332.                 fprintf(stderr, "Invalid option: %s\n", argv[i]);
  333.                 Usage();
  334.             }
  335.         }
  336.  
  337.     for (i = 1; i < argc; ++i) {
  338.         if (argv[i][0] == '-') continue;
  339.         if (fin == NULL) {
  340.             if (InputName[0] == '\0') {
  341.                 strcpy(InputName, argv[i]);
  342.                 continue;
  343.                 }
  344.             else if (OutName[0] == '\0') {
  345.                 strcpy(OutName, argv[i]);
  346.                 continue;
  347.                 }
  348.             }
  349.         p1 = argv[i];
  350.         if (!isdigit(p1[0])) InvalArgu(argv[i]);
  351.         if ((RecLen == -1) && (strspn(p1, "0123456789") == strlen(p1))) {
  352.             RecLen = atoi(argv[i]);
  353.             continue;
  354.             }
  355.         p2 = &p1[strspn(p1, "0123456789")];
  356.         if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
  357.             fprintf(stderr, "Insufficient memory for Key entry.\n");
  358.             exit(12);
  359.             }
  360.         t->Order = 'a';
  361.         t->Case = 'm';
  362.         t->Type = 'c';
  363.         t->Begin = atoi(p1) - 1;
  364.         if (*p2 == ':') t->Len = atoi(++p2);
  365.         else if (*p2 == '-') t->Len = atoi(++p2) - t->Begin;
  366.         else InvalArgu(argv[i]);
  367.         p1 = p2;
  368.         p2 = &p1[strspn(p1, "0123456789")];
  369.         if (*p2 == ':') {
  370.             p1 = ++p2;
  371.             while (*p1 != '\0') {
  372.                 switch (tolower(*p1++)) {
  373.                     case 'd':
  374.                         t->Order = 'd';
  375.                         break;
  376.                     case 'a':
  377.                         t->Order = 'a';
  378.                         break;
  379.                     case 'i':
  380.                         t->Case = 'i';
  381.                         break;
  382.                     case 'm':
  383.                         t->Case = 'm';
  384.                         break;
  385.                     case 'c':
  386.                         t->Type = 'c';
  387.                         break;
  388.                     default:
  389.                         InvalArgu(argv[i]);
  390.                     }
  391.                 }
  392.             }
  393.         else if (*p2 != '\0') InvalArgu(argv[i]);
  394.         Enque(Keys, t);
  395.         }
  396.     }
  397.  
  398.  void
  399. InvalArgu (char *Msg) {
  400.     fprintf(stderr, "Invalid argument: %s.\n", Msg);
  401.     Usage();
  402.     }
  403.  
  404.  
  405.  unsigned
  406. FillSortArray (void) {
  407.     int             i;
  408.  
  409.     if (Verbose && !QuietSwt) printf("\tReading\n");
  410.     for (i = 0; i < S_ArraySize; i++) {
  411.         if (fgets(Buffer, RecLen + 1, fin) == NULL) return (i);
  412.         if (errno) {
  413.             perror("I/O error on input file");
  414.             exit(3);
  415.             }
  416.         NextAdr = ftell(fin);
  417.         lnno++;
  418.         if (Buffer[strlen(Buffer) - 1] != '\n') {
  419.             fprintf(stderr, "Record #%d exceeds maximum length %d\n",
  420.                     lnno, RecLen);
  421.             exit(4);
  422.             }
  423.         strcpy(SortArray[i], Buffer);
  424.         }
  425.     return (i);
  426.     }
  427.  
  428.  
  429.  int
  430. comp (const void *aa, const void *bb) {
  431.     char          **a, **b;
  432.     char            HoldA, HoldB;
  433.     int             End, Result;
  434.     QUE_ENTRY      *t;
  435.     struct KeyEntry *v;
  436.  
  437.     a = (char **) aa;
  438.     b = (char **) bb;
  439.     if (*a == *b) return (0);
  440.     if (*a == NULL) return (1);
  441.     if (*b == NULL) return (-1);
  442.     for (Result = 0, t = Keys->Head; (t != NULL) && (Result == 0); t = t->Next) {
  443.         v = t->Body;
  444.         End = v->Begin + v->Len;
  445.         HoldA = (*a)[End];
  446.         (*a)[End] = '\0';
  447.         HoldB = (*b)[End];
  448.         (*b)[End] = '\0';
  449.         Result = (v->Order == 'a') ?
  450.             (v->Case == 'i') ? stricmp(&(*a)[v->Begin], &(*b)[v->Begin])
  451.             : strcmp(&(*a)[v->Begin], &(*b)[v->Begin])
  452.             : (v->Case == 'i') ? stricmp(&(*b)[v->Begin], &(*a)[v->Begin])
  453.             : strcmp(&(*b)[v->Begin], &(*a)[v->Begin]);
  454.         (*a)[End] = HoldA;
  455.         (*b)[End] = HoldB;
  456.         }
  457.     return (Result);
  458.     }
  459.  
  460.  
  461.  void
  462. Usage (void) {
  463.     fprintf(stderr, "USAGE: pdsort input_file output_file rec_len\n");
  464.     exit(1);
  465.     }
  466.