home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / m / msc7.zip / QSORT.C < prev    next >
C/C++ Source or Header  |  1992-02-17  |  18KB  |  640 lines
  1. /* ----------------------------------------------------------------
  2.  *                QSORT.C
  3.  *
  4.  *    QSORT is a demonstration program which reads data
  5.  *    into memory, and sorts it using the Quicksort algorithm.
  6.  *
  7.  *    The data to be sorted is limited only by memory size.
  8.  *
  9.  *    Note: unlike DOS SORT, the QSORT is CASE-SENSITIVE.
  10.  *
  11.  *    QSORT may be built to use either real mode or protected
  12.  *    mode.  The protected mode version uses DPMI to allocate
  13.  *    extended memory from the DPMI host.  Assuming that sufficient
  14.  *    extended memory is present, the protected mode version 
  15.  *    can sort much larger data sets than the real mode version,
  16.  *    and even the real mode version outstrips the standard DOS
  17.  *    sort command.
  18.  *
  19.  *    This program is intended to demonstrate how to access large
  20.  *    data sets from within a small model C program.
  21.  *
  22.  * ----------------------------------------------------------------
  23.  *    Program usage
  24.  *    Each line in the input stream is one record to be sorted.
  25.  *    Each line may be up to 254 characters long.
  26.  *     
  27.  *    Arguments:
  28.  *
  29.  *        /R        reverse (descending) sort
  30.  *        /+nnn        sort on column nnn
  31.  *        < input        input is always from standard in
  32.  *        > output    output is always to standard out
  33.  *
  34.  *    Possible errors:    record not found
  35.  *                input file error
  36.  *                output file error
  37.  *                bad argument
  38.  *                input line too long (greater than 254 bytes)
  39.  *        
  40.  *
  41.  *
  42.  * ----------------------------------------------------------------
  43.  *    Implementation notes:
  44.  *
  45.  *    o  QSORT can be configured to run in real mode or
  46.  *       in protected mode, by defining the USEREAL symbol.
  47.  *       The program was developed and tested in real mode
  48.  *       in order to make debugging easy.
  49.  *
  50.  *    o  QSORT has been tested with Borland C version 2.0 and 3.0
  51.  *       and with Microsoft C version 6.0 and 7.0.
  52.  *
  53.  * ----------------------------------------------------------------
  54.  *
  55.  *    QSORT internals, data structures, theory of operation
  56.  *
  57.  *    The Quicksort algorithm is described by Donald Knuth in
  58.  *    "The Art of Computer Programming Vol 3: Searching and Sorting"
  59.  *
  60.  *    o  Memory Management
  61.  *
  62.  *
  63.  * Input record storage:
  64.  *    Input records are stored in what we call "raw arrays" which 
  65.  *    are dynamically allocated 64K blocks.  No record crosses
  66.  *    a 64K boundary.  The input records are stored as counted
  67.  *    strings, which are also null terminated to make the sort
  68.  *    comparisons more efficient.
  69.  *
  70.  * Pointer storage:
  71.  *    We store and sort pointers to the input records.
  72.  *    The pointers are also stored in dynamically allocated 
  73.  *    64K blocks.  Each pointer is 4 bytes, thus each 64K block
  74.  *    holds 16K pointers.  Unlike the "huge" memory model, we
  75.  *    do not assume that the blocks are referenced by contiguous
  76.  *    selectors.  Instead, we maintain a master table (the Array
  77.  *    of Arrays, or AA[n]) which is used to locate a pointer.
  78.  *
  79.  * Indices:
  80.  *    An INDEX is essentially a pointer to a pointer.  The INDEX
  81.  *    selects a memory block and a pointer within the block.
  82.  *
  83.  * Graphically, with 32K pointers (requiring 128K to hold pointers)
  84.  *
  85.  
  86.  AA
  87.   [0] ----------> PointerBlock0            RawBlock0
  88.   [1] ------+            [0] --------------->    DataString[0]
  89.         |            [1] ---------+
  90.         |            [2] ...         |
  91.         |             .         +----->    DataString[1]
  92.         |             .
  93.         |             .
  94.         |    
  95.         +---> PointerBlock1        
  96.                     [0] ----+
  97.                 [1] -+    |
  98.                  .   |    |       RawBlockN
  99.                  .   |    +--------->     DataString[16K]
  100.                  .   |
  101.                      +------------>    DataString[16K+1]
  102.  *
  103.  *
  104.  *   So, to get a data pointer from an index, e.g. Index[anum=1, aidx=0]
  105.  *
  106.  *    char **PointerToPointer = AA[anum]
  107.  *    char  *PointerToData = PointerToPointer[aidx]
  108.  *
  109.  *
  110.  */
  111.  
  112. /*
  113.  * If USEREAL is defined, QSORT does not enter protected mode,
  114.  * and uses real mode memory allocation for dynamic storage
  115.  */
  116.  
  117. // #define USEREAL 1
  118.  
  119. #include <stdio.h>
  120. #include <string.h>
  121. #include <stdlib.h>
  122. #include <dos.h>
  123. #include "dpmi.h"
  124.  
  125. #ifdef USEREAL
  126. #include <alloc.h>
  127. #endif
  128.  
  129. #define FARNULL ((void *) 0L)
  130.  
  131.  
  132. /* ----------------------------------------------------------------
  133.  *        Define Data Structures
  134.  * ----------------------------------------------------------------
  135.  */
  136.  
  137. /*    A record is a string of 1-254 bytes
  138.  *       byte 0    = len
  139.  *       byte 1-255    = null-terminated data
  140.  *
  141.  *    An Index refers to a string stored in far memory
  142.  *       anum        = array number (lookup address in AddrPtrArrays)
  143.  *       aidx        = index within array
  144.  *
  145.  *    We maintain aidx as an offset into array, 
  146.  *        i.e. aidx = 0, 4, 8, 12, ...
  147.  *
  148.  *    The real advantage is that therefore the index wraps automatically
  149.  *    into the array number when it overflows, and we needn't check for
  150.  *    overflow.  Remember that we are dereferencing the array each time
  151.  *    we need to get a pointer from an index.
  152.  *
  153.  */
  154.  
  155. union Index_t
  156. {
  157.     unsigned long L;        // Use as long
  158.     struct stag {            // so aidx overflows into anum.
  159.         unsigned int aidx;    // 
  160.         unsigned int anum;    // Use as words for direct access.
  161.     } W;
  162. };
  163.  
  164. typedef union Index_t Index;        // Index  = long or two words
  165. typedef char far *CFPTR;        // CFPTR  = far pointer to char
  166. typedef CFPTR far *CFPTRP;        // CFPTRP = pointer to CFPTR
  167.  
  168. /* ----------------------------------------------------------------
  169.  *        Global Data
  170.  * ----------------------------------------------------------------
  171.  */
  172.  
  173. //    The Raw Arrays hold the raw input data, converted into string records
  174.  
  175. int    Ascending;            // sort order
  176. int    SortColumn;            // input column for sort key
  177. Index    NumRecs;            // number of records read into database ( * 4)
  178. uLong    NumComps = 0;            // Statistics: number of comparisons made
  179. uLong    NumSwaps = 0;            // Statistics: number of swaps made
  180.  
  181. #define NumRawArrays 512        // 512 * 64K = 32Meg maximum data
  182. CFPTR    AddrRawArrays[NumRawArrays];    // array of pointers raw data blocks
  183. uShort    FreeRawArrays[NumRawArrays];    // Next free byte in each array
  184. uShort    SizeRawArrays[NumRawArrays];    // Size in bytes of each array
  185. int    CurrentRawArray = 0;        // current array
  186.  
  187. //    The AA (Address Array) is an array of pointers to 64K blocks.
  188.  
  189. #define NumAA 256            // maximum number of address arrays
  190. CFPTRP    AA[NumAA];            // pointers to array of pointers
  191. uShort    NextFreePtr = 0;        // next free in current array
  192. uShort    CurrentAA = 0;            // current array being filled
  193.  
  194.  
  195. /* ----------------------------------------------------------------
  196.  *         Print usage info and exit
  197.  * ----------------------------------------------------------------
  198. */
  199. void PrintUsage() {
  200.     fprintf(stderr, "QSORT [/R] [/+nnn] [< INFILE] [> OUTFILE]\n");
  201.     fprintf(stderr, "      /R for reverse (descending) sort\n");
  202.     fprintf(stderr, "      /+nnn to sort on column nnn\n");
  203.     fprintf(stderr, "      < INFILE to specify input file\n");
  204.     fprintf(stderr, "      > OUTFILE to specify output file\n");
  205.     exit(1);
  206. }
  207.  
  208. /* ----------------------------------------------------------------
  209.  *         Parse Arguments from Command Line
  210.  *  args:
  211.  *    argc    number of args on command line
  212.  *     argv    vector of argument strings
  213.  *  res:
  214.  *     Exit if cannot parse arguments
  215.  * 
  216.  *     Load global data and flags 
  217.  * ----------------------------------------------------------------
  218. */
  219. void ParseArgs(int argc, char *argv[])
  220. {
  221.     int i;
  222.  
  223. // defaults:
  224.     SortColumn = 1;
  225.     Ascending  = TRUE;
  226.  
  227. // parse command line
  228.     if (argc == 1) return;        // no args, just program name
  229.     if (argc > 3) {
  230.         PrintUsage();
  231.     }
  232.     for (i=1; i<argc; i++) {
  233.         if (stricmp (argv[i], "/R") == 0) {
  234.             Ascending = FALSE;
  235.             continue;
  236.         }
  237.         if ((argv[i][0] == '/') && argv[i][1] == '+') {
  238.             SortColumn = atoi( argv[i] + 2);
  239.             continue;
  240.         }
  241.         PrintUsage();
  242.     }
  243.     if (SortColumn < 1) PrintUsage();
  244.         
  245. }
  246.  
  247.  
  248.  
  249. /* ----------------------------------------------------------------
  250.  *        AllocateRawArray
  251.  * ----------------------------------------------------------------
  252.  */
  253. void AllocateRawArray(int which)
  254. {
  255. #ifndef USEREAL
  256.     struct DPMImemory_t MemStruc;
  257. #endif
  258.  
  259.     if (which >= NumRawArrays) {
  260.         fprintf(stderr, "Allocate Raw Array: exceeded internal limit after %lu records, exiting\n", NumRecs.L/4);
  261.         exit(1);
  262.     }
  263.  
  264. // For now, we always allocate 64K-1 byte arrays
  265.         
  266. #define RAWSIZE ((uShort) 65535)
  267.  
  268. #ifdef USEREAL
  269.     if ((AddrRawArrays[which] = farmalloc(RAWSIZE)) == 0) {
  270. #else
  271.     if ((AddrRawArrays[which] = DPMImalloc(RAWSIZE, &MemStruc)) == 0) {
  272. #endif
  273.         fprintf(stderr, "Allocate Raw Array: Out of room after %lu records, exiting\n", NumRecs.L/4);
  274.         exit(1);
  275.     }
  276.     FreeRawArrays[which] = 0;
  277.     SizeRawArrays[which] = RAWSIZE;
  278. }
  279.  
  280.  
  281. /* ----------------------------------------------------------------
  282.  *        Initialize Arrays
  283.  * ----------------------------------------------------------------
  284.  */
  285. void InitializeArrays()
  286. {
  287.     int    i;
  288.     
  289.     NumRecs.L = 0;
  290.  
  291.     for (i=0; i<NumAA; i++) AA[i] = FARNULL;
  292.  
  293.     for (i=0; i<NumRawArrays; i++) {
  294.         SizeRawArrays[i] = 0;
  295.         FreeRawArrays[i] = 0;
  296.     }
  297.     AllocateRawArray(0);
  298. }
  299.  
  300.  
  301. /* ----------------------------------------------------------------
  302.  *        Store Pointer
  303.  * ----------------------------------------------------------------
  304.  */
  305. void StorePointer(CFPTR ptr)
  306. {
  307. #ifndef USEREAL
  308.     struct DPMImemory_t MemStruc;
  309. #endif
  310.     CFPTRP    PtrArray;
  311.     
  312.     PtrArray = AA[NumRecs.W.anum];
  313.     if (PtrArray == FARNULL) {
  314. #ifdef USEREAL
  315.         PtrArray = farmalloc(65536);
  316. #else
  317.         PtrArray = DPMImalloc(0, &MemStruc);
  318. #endif
  319.         AA[NumRecs.W.anum] = PtrArray;
  320.         if (PtrArray == FARNULL) {
  321.             fprintf(stderr, "Store Pointer: Out of room after %ld records, exiting\n", NumRecs.L / 4);
  322.             exit(1);
  323.         }
  324.     }
  325.  
  326.     /* store the pointer at index indicated by NumRecs */
  327.  
  328.     *((CFPTRP) ( ((CFPTR) AA[NumRecs.W.anum]) + NumRecs.W.aidx)) = ptr;
  329. }
  330.  
  331.  
  332. /* ----------------------------------------------------------------
  333.  *        Read Next Record
  334.  * args:
  335.  *    none
  336.  * ret:
  337.  *    FALSE if end of file
  338.  *    otherwise, new record is loaded with input data
  339.  * ----------------------------------------------------------------
  340.  */     
  341. int ReadNextRecord()
  342. {
  343.     char    far *ptr;        // pointer to store text
  344.     char    far *lenptr;        // pointer to length field
  345.     int    len = 0;        // accumulated length
  346.     int    c;            // input character
  347.  
  348.     if (SizeRawArrays[CurrentRawArray] - FreeRawArrays[CurrentRawArray] < 256)
  349.         AllocateRawArray(++CurrentRawArray);
  350.     ptr = AddrRawArrays[CurrentRawArray] + FreeRawArrays[CurrentRawArray];
  351.  
  352.     lenptr = ptr++;            // remember string start, and advance
  353.  
  354.     while (TRUE) {
  355.         c = getchar();
  356.         if (c == EOF) break;
  357.         if (++len > 254) {
  358.             fprintf(stderr, "Input line too long at %lu, exiting\n", NumRecs.L/4);
  359.             exit(1);
  360.         }
  361.         *ptr++ = c;
  362.         if (c == '\n') break;
  363.     }
  364.     
  365.     *ptr++ = 0;                // terminate with null
  366.     if (len != 0) {
  367.         *ptr = 0;            // mark (len) next string empty
  368.         *lenptr = len;            // record size of this string
  369.         FreeRawArrays[CurrentRawArray] += (len + 3); // record number of bytes consumed
  370.         StorePointer(lenptr);        // store the pointer in the database
  371.         return TRUE;
  372.     }
  373.     else return FALSE;        // no string parsed
  374. }
  375.  
  376.  
  377.  
  378. /* ----------------------------------------------------------------
  379.  *        Read Data
  380.  * ----------------------------------------------------------------
  381.  */     
  382. void ReadData()
  383. {
  384.     while (!feof(stdin)) {
  385.         if (ReadNextRecord()) NumRecs.L += 4;
  386.     }
  387. }
  388.  
  389.  
  390.  
  391.  
  392. /* ----------------------------------------------------------------
  393.  *        Write Data
  394.  * ----------------------------------------------------------------
  395.  */     
  396. void WriteData()
  397. {
  398.     Index    Idx;
  399.     CFPTR    Ptr;
  400.     int    len;
  401.  
  402.     for (Idx.L = 0; Idx.L < NumRecs.L; Idx.L += 4) {
  403.         
  404.         Ptr = *((CFPTRP) ( ((CFPTR) AA[Idx.W.anum]) + Idx.W.aidx));
  405.         len = *Ptr++;
  406.         while (len-- > 0) putchar(*Ptr++);    // write counted string
  407.     }
  408.     fflush(stdout);                    // because we don't go through cleanup code
  409. }
  410.  
  411.  
  412.  
  413. #ifndef USEREAL
  414. /* ----------------------------------------------------------------
  415.  *        Enter protected mode
  416.  * ----------------------------------------------------------------
  417.  */     
  418. void DPMIGoProtectedMode()
  419. {
  420.     uShort    flags;
  421.     uChar    processor;
  422.     uChar    majorVersion;
  423.     uChar    minorVersion;
  424.     uShort    nPrivateDataParas;
  425.     void (far* entryAddress)();
  426.  
  427.     int    Result;
  428.     
  429.     Result = DPMIObtainSwitchEntryPoint(&flags, &processor, &majorVersion,
  430.             &minorVersion, &nPrivateDataParas, &entryAddress);
  431.     if (Result != 0) {
  432.         fprintf(stderr, "No DPMI host found, exiting\n");
  433.         exit(Result);
  434.     }
  435.     
  436.     Result = DPMIEnterProtectedMode(entryAddress, 0,
  437.         nPrivateDataParas);
  438.     if (Result != 0) {
  439.         fprintf(stderr, "Error attempting to enter protected mode, exiting\n");
  440.         exit(Result);
  441.     }
  442. }
  443. #endif
  444.  
  445.  
  446. /* ----------------------------------------------------------------
  447.  *        Compare record referenced by idx1, idx2
  448.  * ret:
  449.  *    =0 if idx1 = idx2
  450.  *    >0 if idx1 > idx2
  451.  *    <0 if idx1 < idx2
  452.  *
  453.  *    Note: this comparison is CASE SENSITIVE!!!
  454.  *
  455.  * ----------------------------------------------------------------
  456.  */     
  457. int CMP(Index idx1, Index idx2)
  458. {
  459.     CFPTR    ptr1;
  460.     CFPTR    ptr2;
  461.     int    len;
  462.     int    result;
  463.     
  464.     NumComps++;
  465.     ptr1 = *((CFPTRP) ( ((CFPTR) AA[idx1.W.anum]) + idx1.W.aidx));
  466.     ptr2 = *((CFPTRP) ( ((CFPTR) AA[idx2.W.anum]) + idx2.W.aidx));
  467.  
  468.     len = min(*ptr1, *ptr2);
  469.     ptr1 += min(*ptr1, SortColumn);
  470.     ptr2 += min(*ptr2, SortColumn);
  471.  
  472. /*
  473.  * Code the inner loop of this comparison in assembler for speed.
  474.  * This is not strictly necessary, of course, but the performance
  475.  * improvement is dramatic.
  476.  */
  477. _asm    mov dx, ds
  478. _asm     les di, ptr1
  479. _asm    lds si, ptr2
  480. _asm    mov cx, len
  481. _asm    cld
  482. _asm    repe cmpsb
  483. _asm    mov al, [si-1]
  484. _asm    mov bl, es:[di-1]
  485. _asm    xor ah, ah
  486. _asm    mov bh, ah
  487. _asm    sub ax, bx
  488. _asm    mov ds, dx
  489. _asm    mov result, ax
  490.  
  491.     return (Ascending ? -result : result);
  492. }
  493.  
  494. void Swap(Index idx1, Index idx2)
  495. {
  496.     CFPTR    temp;            // temp string pointer
  497.     CFPTRP    p1;            // point to idx1 string pointer
  498.     CFPTRP    p2;            // point to idx2 string pointer
  499.     
  500.     NumSwaps++;
  501.  
  502.     p1 = (CFPTRP) (((CFPTR) AA[idx1.W.anum]) + idx1.W.aidx);
  503.     p2 = (CFPTRP) (((CFPTR) AA[idx2.W.anum]) + idx2.W.aidx);
  504.  
  505.     temp = *p1;
  506.     *p1 = *p2;
  507.     *p2 = temp;
  508. }
  509.  
  510.  
  511.  
  512. /* ----------------------------------------------------------------
  513.  *
  514.  * QuickSort works by picking a "pivot", then dividing the data
  515.  * into records less than the pivot and records greater    than the pivot.
  516.  *
  517.  * Then, call Quicksort recursively - once to sort the data below
  518.  * the pivot, and once to sort the data above the pivot.
  519.  *
  520.  * If there are only 2 elements in the range, sort them and return
  521.  * from the recursion.
  522.  *
  523.  * ----------------------------------------------------------------
  524.  */
  525. void Quicksort(Index Low, Index High)
  526. {
  527.     Index Up;        // Up starts at the bottom of the range and walks up
  528.     Index Down;        // Down starts at the top of the range and walks down    
  529.     Index Temp1, Temp2;
  530.  
  531.     /* called with bad argument? */
  532.     if ( Low.L >= High.L) return;
  533.  
  534.     /* if only two elements, swap if needed to get them in order */
  535.     if ( (High.L - Low.L) == 4 ) {
  536.         if ( CMP(Low, High) > 0 )
  537.             Swap(Low, High );
  538.         return;
  539.     }
  540.  
  541.     /* if only three elements, swap as needed */
  542.     if ( (High.L - Low.L) == 8 ) {
  543.         Temp1.L = Low.L + 4;
  544.         Temp2.L = Low.L + 8;
  545.         
  546.         if ( CMP(Low, Temp1) > 0) Swap(Low, Temp1);
  547.         if ( CMP(Low, Temp2) > 0) Swap(Low, Temp2);
  548.         if ( CMP(Temp1, Temp2) > 0) Swap(Temp1, Temp2);
  549.         return;
  550.     }
  551.  
  552.     /* if more than three elements, Quicksort them */      
  553.     do {
  554.     /* Move in from both sides towards the pivot element */
  555.     Up = Low;
  556.     Down = High;
  557.  
  558.     while( (Up.L < Down.L) && (CMP(Up, High) <= 0))
  559.             Up.L += 4;
  560.     while( (Down.L > Up.L) && (CMP(Down, High) >= 0))
  561.             Down.L -= 4;
  562.  
  563.     /* If we haven't reached the pivot, it means that two
  564.      * elements on either side are out of order, so swap them. 
  565.      */
  566.  
  567.     if( Up.L < Down.L ) Swap( Up, Down );
  568.      } while ( Up.L < Down.L );
  569.  
  570.      /* Move pivot element back to its proper place in the array. */
  571.      Swap( Up, High );
  572.  
  573.      /* call for partitions above and below the pivot */
  574.      /* UNLESS the partition in question contains < 2 elements */
  575.  
  576.      /* if lower partition contains 0 or 1 elements, just sort upper */
  577.      if (Up.L <= Low.L+4) {
  578.          Up.L += 4;
  579.          Quicksort(Up, High);
  580.          return;
  581.      }
  582.  
  583.      /* if higher partition contains 0 or 1 elements, just sort lower */
  584.      if (Up.L >= High.L-4) {
  585.          Up.L -= 4;
  586.          Quicksort(Low, Up);
  587.          return;
  588.      }
  589.  
  590.      /* Sort smaller partition first to conserve recursion stack */
  591.  
  592.      if( (Up.L - Low.L) < (High.L - Up.L) ) {
  593.          Up.L -= 4;
  594.          Quicksort( Low,  Up );
  595.          Up.L += 8;
  596.          Quicksort( Up , High );
  597.      }
  598.      else {
  599.          Up.L += 4;
  600.          Quicksort( Up, High );
  601.          Up.L -= 8;
  602.          Quicksort( Low, Up );
  603.      }
  604. }
  605.  
  606.  
  607. /* ----------------------------------------------------------------
  608.  *            Main
  609.  * ----------------------------------------------------------------
  610.  */     
  611. void main(int argc, char *argv[])
  612. {
  613.     Index zero;
  614.     uLong secs;        // elapsed time in seconds
  615.  
  616. #ifndef USEREAL
  617.     DPMIGoProtectedMode();
  618. #endif
  619.  
  620. #ifdef USEREAL
  621.     fprintf(stderr, "QSORT running in real mode\n");
  622. #else
  623.     fprintf(stderr, "QSORT running in protected mode\n");
  624. #endif
  625.  
  626.     ParseArgs(argc, argv);
  627.     InitializeArrays();
  628.     ReadData();
  629.   fprintf(stderr, "Sorting %lu records\n", NumRecs.L/4);
  630.     if (NumRecs.L > 1) {
  631.         NumRecs.L -= 4;
  632.         zero.L = 0;
  633.         Quicksort(zero, NumRecs);
  634.         NumRecs.L += 4;
  635.     }
  636.     WriteData();
  637.   fprintf(stderr, "Comps: %lu  Swaps: %lu\n", NumComps, NumSwaps);
  638.  
  639. }
  640.