home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / text_cla / csort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-12  |  27.0 KB  |  1,214 lines
  1. /*        CSORT - Tal - Rework from Jsort code of 1985 by Tal
  2.  
  3.         This is your classic sort-merge. 
  4.  
  5.     Sorting
  6.  
  7.         Step 1.  Read input file for as many records as will fit into memory
  8.         Step 2.  Sort records in memory
  9.         Step 3.  Write sorted records to unique disk file
  10.         Step 4.  Repeat to step 1 until all data read and sorted
  11.         Step 5.    If only 1 unique sorted disk file then stop
  12.  
  13.     Merging
  14.  
  15.         Step 6.    Open as many unique sorted disk files until all opened or
  16.                     no file handles left.
  17.         Step 7.    Select lowest record from each disk file
  18.         Step 8.    Write lowest record to unique disk file
  19.         Step 9.    Read next record from particular disk file or eof
  20.         Step 10.    Repeat to step 7 till all open input files have been read
  21.         Step 11.    Delete unique input files
  22.         Step 12.    If more than one new unique merged file exists then
  23.                     Repeat to step 6
  24.  
  25.  
  26.         Latest Edits: Fall '92
  27.  
  28. */
  29.  
  30.  
  31. #include <stdlib.h>
  32. #include <string.h>
  33. #include <stdio.h>
  34. #include <io.h>
  35. #include <memincs.h>
  36.  
  37. #include <str.h>
  38.  
  39. #define LIM_HANDLES  16        /* max number of files handles to try opening */
  40. #define MAX_REC_LEN  1024  /* max length of a record */
  41. #define MAX_FIELDS     16    /* max number of key fields */
  42.  
  43. #define TRUE 1
  44. #define FALSE 0
  45.  
  46. #define safekill(f)  unlink(f)
  47.  
  48. #define MIN(A,B) ( (A) < (B) ? (A) : (B) )
  49. #define MAX(A,B) ( (A) > (B) ? (A) : (B) )
  50.  
  51.  
  52. #include <csort.h>
  53.  
  54. struct SORT_REC_S
  55. {
  56.    long  lCur;
  57.     long    lMax;    /*  tracking for work files during merging */
  58. };
  59.  
  60. typedef struct SORT_REC_S SORT_REC_T;
  61. typedef SORT_REC_T * SORT_REC_P;
  62.  
  63.  
  64. struct KDATA_S
  65. {   /*  data itself */
  66.     char *pcPtr;      /*  original record */
  67.     char *key;      /*  sort key */
  68.     long  rec;      /*  original record number */
  69. };
  70.  
  71. typedef struct KDATA_S KDATA_T;
  72.  
  73.  
  74. struct SORT_WKA_S
  75. {
  76.     /* following are dynamically allocated during runtime */
  77.    char     * *pcPtr;
  78.     char     *    *pcKey;
  79.     KDATA_T  * * pstKdata;
  80.     long        lMaxMemRecs;
  81.    int        iMaxHandles;
  82.     int        iSortBlocks;
  83.     int        iSortErr;
  84.     int        iWorkRecLen;
  85. };
  86.  
  87. typedef struct SORT_WKA_S SORT_WKA_T;
  88. typedef SORT_WKA_T * SORT_WKA_P;
  89.  
  90. unsigned iKeyLen;  /* so main and other functions can see it */
  91.  
  92. void StrAnd(char * n);
  93.  
  94. void MakeTempFileName(char * pcFileName,int iSortBlocks);
  95. int SortFile(SORT_PARMS_P pSortParms);
  96. int SortOpenFile(SORT_WKA_P pSortWka, SORT_PARMS_P pSortParms, char * pcFile, FILE ** fp, long * plRecs);
  97. void ShellSort(KDATA_T * v[], long n, int iSize);
  98. int SortInit(SORT_WKA_P pSortWka, SORT_PARMS_P pSortParms);
  99. int SortLoadRec(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms,char * pcBuffer,int iNdx);
  100. int SortWriteRec(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms,FILE * fp,int iNdx,int iLast);
  101. int SortFilesIn(SORT_WKA_P pSortWka, SORT_PARMS_P pSortParms);
  102. int SortFindHandles(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms);
  103. int SortMerge(SORT_WKA_P pSortWka, SORT_PARMS_P pSortParms);
  104. int SortTerminate(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms);
  105. void MakeKey(char *result,char *szBuffer,KEY_FIELD_T  *pstKeyField,int iFields);
  106.  
  107.  
  108. /*************************************************************************
  109. **
  110. **   M A I N
  111. **
  112. /*************************************************************************/
  113.  
  114. #ifdef TEST
  115. main()
  116. {
  117.    SORT_PARMS_T  stSortParms;
  118.  
  119.    memset(&stSortParms,0,sizeof(SORT_PARMS_T));
  120.  
  121.    stSortParms.iSortType = SORT_TYPE_RECORD;
  122.    stSortParms.iFileType = SORT_FILE_RELATIVE;
  123.    strcpy(stSortParms.szSourceFile,"c:\\archive\\test.1");
  124.    strcpy(stSortParms.szDestFile,"c:\\archive\\test.2");
  125.    stSortParms.iRecLen   = 8;
  126.    stSortParms.lMemoryToUse = 512000;
  127.    stSortParms.iNumSortFields = 8;
  128.    stSortParms.pSortFields = calloc(8,sizeof(KEY_FIELD_T));
  129.  
  130.     stSortParms.pSortFields[0].iBeg = 7;
  131.     stSortParms.pSortFields[0].iLen = 1;
  132.     stSortParms.pSortFields[0].iOrder = SORT_DESCENDING;
  133.  
  134.     stSortParms.pSortFields[1].iBeg = 6;
  135.     stSortParms.pSortFields[1].iLen = 1;
  136.     stSortParms.pSortFields[1].iOrder = SORT_DESCENDING;
  137.  
  138.     stSortParms.pSortFields[2].iBeg = 5;
  139.     stSortParms.pSortFields[2].iLen = 1;
  140.     stSortParms.pSortFields[2].iOrder = SORT_DESCENDING;
  141.  
  142.     stSortParms.pSortFields[3].iBeg = 4;
  143.     stSortParms.pSortFields[3].iLen = 1;
  144.     stSortParms.pSortFields[3].iOrder = SORT_DESCENDING;
  145.  
  146.     stSortParms.pSortFields[4].iBeg = 3;
  147.     stSortParms.pSortFields[4].iLen = 1;
  148.     stSortParms.pSortFields[4].iOrder = SORT_DESCENDING;
  149.  
  150.     stSortParms.pSortFields[5].iBeg = 2;
  151.     stSortParms.pSortFields[5].iLen = 1;
  152.     stSortParms.pSortFields[5].iOrder = SORT_DESCENDING;
  153.  
  154.     stSortParms.pSortFields[6].iBeg = 1;
  155.     stSortParms.pSortFields[6].iLen = 1;
  156.     stSortParms.pSortFields[6].iOrder = SORT_DESCENDING;
  157.  
  158.     stSortParms.pSortFields[7].iBeg = 0;
  159.     stSortParms.pSortFields[7].iLen = 1;
  160.     stSortParms.pSortFields[7].iOrder = SORT_DESCENDING;
  161.  
  162.     SortFile(&stSortParms);    
  163.  
  164.     return(0);
  165. }
  166. #endif
  167.  
  168.  
  169. /********************************************************************
  170. **
  171. **  SortFile, central sort function
  172. **
  173. *********************************************************************/
  174.  
  175. int SortFile(SORT_PARMS_P pSortParms)
  176. {
  177.     SORT_WKA_T  stSortWka;
  178.     SORT_WKA_P  pSortWka;
  179.  
  180.     pSortWka = &stSortWka;
  181.  
  182.  
  183.     /* calloc memory */
  184.  
  185.     SortInit(pSortWka,pSortParms);
  186.  
  187.  
  188.     /* determine available file handles */
  189.  
  190.     SortFindHandles(pSortWka,pSortParms);
  191.  
  192.  
  193.     /* sort/split input file */
  194.  
  195.     SortFilesIn(pSortWka,pSortParms);
  196.  
  197.  
  198.     /* if files to merge then do so */
  199.  
  200.     if(pSortWka -> iSortBlocks > 1)
  201.         SortMerge(pSortWka,pSortParms);
  202.  
  203.  
  204.     /* clean up */
  205.  
  206.     SortTerminate(pSortWka,pSortParms);
  207.  
  208.     
  209.     return(pSortWka -> iSortErr);
  210. }
  211.  
  212.  
  213.  
  214.  
  215. /*
  216. **  SortInit, setup memory
  217. */
  218.  
  219. int SortInit(SORT_WKA_P pSortWka, SORT_PARMS_P pSortParms)
  220. {
  221.  
  222.     int        iMemPerRec;
  223.     int        iCnt;
  224.     void    *  pvTempPtr;
  225.     long        lCnt;
  226.  
  227.     pSortWka -> iSortErr = 0;
  228.  
  229.    iMemPerRec = sizeof(KDATA_T);
  230.  
  231.     /*
  232.     **  Allocate Memory
  233.     */
  234.  
  235.    /*  Add up length of all keys */
  236.  
  237.    for(iCnt = 0, iKeyLen = 0; iCnt < pSortParms -> iNumSortFields; iCnt++)
  238.       iKeyLen += pSortParms -> pSortFields[iCnt].iLen;
  239.  
  240.    /*  malloc area for each */
  241.  
  242.    iMemPerRec = sizeof(KDATA_T) + iKeyLen;  
  243.  
  244.     if(pSortParms -> iSortType == SORT_TYPE_RECORD)
  245.         iMemPerRec += pSortParms -> iRecLen;
  246.     else
  247.         iMemPerRec += (int) sizeof(int);
  248.  
  249.     iMemPerRec += sizeof(char *);        /* pcPtr */
  250.     iMemPerRec += sizeof(char *);        /* pcKey */
  251.  
  252.     pSortWka -> lMaxMemRecs = pSortParms -> lMemoryToUse / (long) iMemPerRec; 
  253.  
  254.     /*
  255.     ** determine if memory available 
  256.     */
  257.  
  258.    while((pvTempPtr = (void *) calloc(pSortWka -> lMaxMemRecs,iMemPerRec)) == NULL)
  259.       pSortWka -> lMaxMemRecs--;
  260.  
  261.     /*
  262.     **    free temp ptr used for inspecting memory
  263.     */
  264.  
  265.     free(pvTempPtr);
  266.  
  267.    /* setup Kdata work structures */
  268.  
  269.     /* calloc array of pointers */
  270.  
  271.     pSortWka -> pstKdata = calloc(pSortWka -> lMaxMemRecs,sizeof(KDATA_T *));
  272.  
  273.    for(lCnt = 0; lCnt < pSortWka -> lMaxMemRecs; lCnt++)
  274.       pSortWka -> pstKdata[lCnt] = (KDATA_T *) calloc(1,sizeof(KDATA_T));
  275.  
  276.  
  277.     /* calloc array of char ptrs */
  278.  
  279.     pSortWka -> pcKey = (char **) calloc(pSortWka -> lMaxMemRecs,sizeof(char *));
  280.  
  281.     if(pSortParms -> iSortType == SORT_TYPE_RECORD)
  282.      pSortWka -> pcPtr = (char **) calloc(pSortWka -> lMaxMemRecs,sizeof(char *));
  283.  
  284.  
  285.    for(lCnt = 0; lCnt < pSortWka -> lMaxMemRecs; lCnt++)
  286.    {
  287.       pSortWka -> pcKey[lCnt] = (char *) malloc(iKeyLen + 1);
  288.  
  289.         if(pSortParms -> iSortType == SORT_TYPE_RECORD)
  290.          pSortWka -> pcPtr[lCnt] = (char *) calloc(1,pSortParms -> iRecLen + 1);
  291.    }
  292.  
  293.  
  294.    /*  malloc'ing the key and pcPtr pointers seperately so we can use qsort */
  295.  
  296.    for(lCnt = 0; lCnt < pSortWka -> lMaxMemRecs; lCnt++)
  297.    {
  298.       pSortWka -> pstKdata[lCnt] -> key = pSortWka -> pcKey[lCnt];
  299.       if(pSortParms -> iSortType == SORT_TYPE_RECORD)
  300.          pSortWka -> pstKdata[lCnt] -> pcPtr = pSortWka -> pcPtr[lCnt];
  301.    }
  302.  
  303.     return(0);
  304. }
  305.  
  306.  
  307.  
  308. int SortWriteRec(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms,FILE * fp,int iNdx,int iLast)
  309. {
  310.     if(pSortParms -> iSortType == SORT_TYPE_RECORD)
  311.     {
  312.            /*  full record sort, write out original string */
  313.  
  314.         if(pSortParms -> iFileType == SORT_FILE_RELATIVE)
  315.             fwrite(pSortWka -> pstKdata[iNdx]->pcPtr,pSortWka -> iWorkRecLen,1,fp);
  316.         else
  317.             fprintf(fp,"%s",pSortWka -> pstKdata[iNdx]->pcPtr);
  318.     }
  319.     else
  320.     {
  321.         /*  pointer sort, write only key and orig rec number */
  322.  
  323.         if(iLast)
  324.         {
  325.              /*  if this is dest file */
  326.  
  327.             if(pSortParms -> iSortType == SORT_TYPE_RECORD)
  328.                 fwrite(&(pSortWka -> pstKdata[iNdx]->rec),sizeof(long),1,fp);
  329.             else
  330.                 fprintf(fp,"%d\n",pSortWka -> pstKdata[iNdx]->rec);
  331.         }
  332.         else
  333.         {
  334.                 if(pSortParms -> iSortType == SORT_TYPE_RECORD)
  335.              {
  336.                 fwrite(&(pSortWka -> pstKdata[iNdx] -> rec),sizeof(long),1,fp);
  337.                 fwrite(pSortWka -> pstKdata[iNdx]->key,iKeyLen,1,fp);
  338.              }
  339.              else
  340.              {
  341.                     fprintf(fp,"%d %s",pSortWka -> pstKdata[iNdx]->rec,pSortWka -> pstKdata[iNdx]->key);
  342.              }
  343.         }
  344.     }  /*  if pSortParms -> iSortType == SORT_TYPE_RECORD */
  345.  
  346.     return(0);
  347. }
  348.  
  349.  
  350. /*
  351. **  SortFilesIn, break up input file
  352. */
  353.  
  354. int SortFilesIn(SORT_WKA_P pSortWka, SORT_PARMS_P pSortParms)
  355. {
  356.  
  357.     long        lSortRec;
  358.     long        lSortIn;
  359.     char        szFoutStr[64];
  360.     FILE        *fpOrigFile;
  361.     FILE        *fpOutFile;
  362.     char        szBuffer[MAX_REC_LEN];   /* max 1K record length */
  363.     long        lSortItems;
  364.     int        i;
  365.     int        iTemp;
  366.  
  367.     lSortItems = 0;
  368.  
  369.  
  370.    pSortWka -> iSortBlocks = 0;
  371.  
  372.    lSortRec = 0;
  373.  
  374.    if(pSortParms -> iSortType == SORT_TYPE_RECORD)    /* size of items written to work files */
  375.       pSortWka -> iWorkRecLen = pSortParms -> iRecLen;
  376.    else
  377.       pSortWka -> iWorkRecLen = iKeyLen + sizeof(long);
  378.  
  379.  
  380.     /*
  381.     **  Open source file
  382.     */
  383.  
  384.     SortOpenFile(pSortWka,pSortParms,pSortParms -> szSourceFile,&(fpOrigFile),&lSortItems);
  385.  
  386.  
  387.     /*
  388.     **  While processing the file
  389.     */
  390.  
  391.     while(lSortRec < lSortItems) 
  392.     {
  393.         lSortIn = 0;
  394.  
  395.         while((lSortIn < pSortWka -> lMaxMemRecs) && (lSortRec < lSortItems)) 
  396.         {
  397.             if(pSortParms -> iFileType == SORT_FILE_RELATIVE)
  398.                 iTemp = fread(szBuffer,1,pSortParms -> iRecLen,fpOrigFile);  /* read into szBuffer */
  399.             else
  400.             {
  401.                 fgets(szBuffer,pSortParms -> iRecLen,fpOrigFile);  /* read into szBuffer */
  402.                 iTemp = strlen(szBuffer) + 1;
  403.             }
  404.  
  405.             if(pSortParms -> iSortType == SORT_TYPE_RECORD)   /*  only copy string if full record sort */
  406.                 memcpy(pSortWka -> pstKdata[lSortIn]->pcPtr,szBuffer,iTemp);
  407.  
  408.             pSortWka -> pstKdata[lSortIn]->rec = lSortRec;   /* original record number */
  409.  
  410.             MakeKey(pSortWka -> pstKdata[lSortIn] -> key,
  411.                   szBuffer,
  412.                   pSortParms->pSortFields,
  413.                   pSortParms -> iNumSortFields);
  414.  
  415.             lSortIn++;
  416.             lSortRec++;
  417.         }
  418.  
  419.         /*
  420.         **  Sort what is currently loaded into memory
  421.         */
  422.  
  423.         ShellSort(pSortWka -> pstKdata,lSortIn,iKeyLen);
  424.  
  425.         /*
  426.         **  Write merged block out to disk file for later merging
  427.         */
  428.          
  429.         pSortWka -> iSortBlocks++;
  430.  
  431.         if( (pSortWka -> iSortBlocks == 1) && (lSortRec == lSortItems) ) 
  432.         {
  433.          /*  it only took one pass to sort this file in memory,
  434.             write the dest file now */
  435.  
  436.             strcpy(szFoutStr,pSortParms -> szDestFile);
  437.             safekill(pSortParms -> szDestFile);
  438.         } 
  439.         else 
  440.         {
  441.             /*  otherwise write merge file for next level */
  442.  
  443.          MakeTempFileName(szFoutStr,pSortWka -> iSortBlocks-1);
  444.         }
  445.  
  446.  
  447.         /* TAL - check if crlf or relative, will change fopen from "wb" to "w" */
  448.  
  449.        if(pSortParms -> iFileType == SORT_FILE_RELATIVE)
  450.             fpOutFile = fopen(szFoutStr,"wb");
  451.         else
  452.             fpOutFile = fopen(szFoutStr,"w");
  453.  
  454.         if(fpOutFile == NULL)
  455.         {
  456.             pSortWka -> iSortErr = 8;
  457.             goto done_work;
  458.         }
  459.  
  460.         /*  write sorted contents of memory to disk */
  461.  
  462.         for(i = 0; i < (int) lSortIn; i++)
  463.         {
  464.             SortWriteRec(pSortWka,
  465.                             pSortParms,
  466.                             fpOutFile,
  467.                             i,
  468.                             (pSortWka -> iSortBlocks == 1) && (lSortRec == lSortItems) );
  469.  
  470.         }
  471.  
  472.         fclose(fpOutFile);
  473.  
  474.     } /* while processing the file */
  475.  
  476.     fclose(fpOrigFile);
  477.  
  478.  
  479.     /*
  480.     **  Check if must merge files 
  481.     */
  482.  
  483.     pSortParms -> lRecsSorted = lSortItems;    /* Returned var */
  484.  
  485. done_work:
  486.  
  487.     return(pSortWka -> iSortErr);
  488. }
  489.  
  490.  
  491. /*
  492. **  SortFindHandles, find how many file handles are available to use
  493. */
  494.  
  495. int SortFindHandles(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms)
  496. {
  497.     int    iGetting;
  498.     int    i;
  499.     int    iTemp;
  500.     FILE        *fpWorkFiles[LIM_HANDLES];
  501.  
  502.  
  503.     /*   Now that the original file has been sorted into iSortBlocks number
  504.        of files to merge, see how many file handles are available and
  505.        then start mergeing from level to level till we are done  */
  506.     
  507.     pSortWka -> iMaxHandles=0;     /*  scan for max file handles */
  508.     
  509.     iGetting = TRUE;   /*  try and open as many file handles as possible */
  510.     
  511.     
  512.     for(pSortWka -> iMaxHandles=0; iGetting; pSortWka -> iMaxHandles++)
  513.     {
  514.         if(pSortWka -> iMaxHandles <= pSortWka -> iSortBlocks)
  515.         {    
  516.                 /*  
  517.                 **        open handles till we know we have enough to cover 
  518.                 **     the sort blocks on disk for a simutaneous merge or 
  519.                 **     until the system runs out which is denoted by a 
  520.                 **     NULL file pointer 
  521.                 **
  522.                 **        Efficieny of this merging from level to level is 
  523.                 **        x^handles
  524.                 */
  525.     
  526.                if(pSortParms -> iFileType == SORT_FILE_RELATIVE)
  527.                     fpWorkFiles[pSortWka -> iMaxHandles] = fopen(pSortParms -> szDestFile,"wb");
  528.                 else
  529.                     fpWorkFiles[pSortWka -> iMaxHandles] = fopen(pSortParms -> szDestFile,"w");
  530.     
  531.                 if(fpWorkFiles[pSortWka -> iMaxHandles] == NULL)
  532.                 {
  533.                     iGetting = FALSE;  /*  hit the end, ran out */
  534.                     break;
  535.                 }
  536.         }
  537.         else
  538.         {
  539.             iGetting = FALSE;   /* have enough */
  540.         }
  541.     }
  542.     
  543.     /*
  544.     **  Close all files 
  545.     */
  546.     
  547.     for(i=0; i < pSortWka -> iMaxHandles; i++)
  548.         iTemp = fclose(fpWorkFiles[i]);
  549.  
  550.     return(pSortWka -> iSortErr);
  551. }
  552.  
  553.  
  554.  
  555. /*
  556. **  SortOpenFile, open an input file
  557. */
  558.  
  559. int SortOpenFile(SORT_WKA_P pSortWka, SORT_PARMS_P pSortParms, char * pcFile, FILE ** fp, long * plRecs)
  560. {
  561.     char    szBuffer[MAX_REC_LEN + 1];
  562.  
  563.  
  564.    if(pSortParms -> iFileType == SORT_FILE_RELATIVE)
  565.     {
  566.         *fp = fopen(pcFile,"rb");
  567.         *plRecs = (long) (filelength(fileno(*fp)) / pSortWka -> iWorkRecLen);
  568.     }
  569.    else
  570.     {
  571.       /*
  572.         ** if merging text files, must count first 
  573.         */
  574.  
  575.         *fp = fopen(pcFile,"r");
  576.  
  577.       if(pSortParms -> lRecsInFile != 0)
  578.         {
  579.          *plRecs = pSortParms -> lRecsInFile;
  580.         }
  581.       else
  582.         {
  583.             *plRecs = 0;
  584.  
  585.               while(!feof(*fp))
  586.            {
  587.                fgets(szBuffer,MAX_REC_LEN,*fp);
  588.                (*plRecs)++;
  589.               }
  590.  
  591.            rewind(*fp);
  592.         }
  593.     }
  594.  
  595.     return(0);
  596. }
  597.  
  598.  
  599.  
  600. /*
  601. **  SortLoadRec, load a record 
  602. */
  603.  
  604. int SortLoadRec(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms,char * pcBuffer,int iNdx)
  605. {
  606.     long    lTemp;
  607.  
  608.     if(pSortParms -> iSortType == SORT_TYPE_RECORD) 
  609.     {
  610.  
  611.         memcpy(pSortWka -> pstKdata[iNdx] -> pcPtr,pcBuffer,pSortWka -> iWorkRecLen);
  612.  
  613.         MakeKey(pSortWka -> pstKdata[iNdx] -> key,
  614.                    pSortWka -> pstKdata[iNdx] -> pcPtr,
  615.                    pSortParms -> pSortFields,
  616.                    pSortParms -> iNumSortFields);
  617.     }
  618.     else
  619.     {
  620.  
  621.         memcpy(&lTemp,pcBuffer,sizeof(long));
  622.  
  623.         pSortWka -> pstKdata[iNdx] -> rec = lTemp;
  624.  
  625.         memcpy(pSortWka -> pstKdata[iNdx] -> key,pcBuffer+sizeof(long),iKeyLen);
  626.     }
  627.  
  628.     return(0);
  629. }
  630.  
  631.  
  632. /*
  633. **  SortFindLowKey, find the lowest key in used buffers
  634. */
  635.  
  636. int SortFindLowKey(SORT_WKA_P pSortWka,int iInBuffers,SORT_REC_P pSortRec,char * pcHighKey, int *piLow)
  637. {
  638.     char        szTempStr[MAX_REC_LEN + 1];
  639.     int        i;
  640.  
  641.  
  642.     if(pSortRec[0].lCur <= pSortRec[0].lMax)
  643.     {
  644.         /*  if we have them, then take them from stSortRec[0] */
  645.  
  646.         memcpy(szTempStr,pSortWka -> pstKdata[0]->key,iKeyLen);
  647.  
  648.         *piLow = 0;
  649.     }
  650.     else
  651.     {
  652.         /*  otherwise use the pcHighKey */
  653.  
  654.         memcpy(szTempStr,pcHighKey,iKeyLen);
  655.  
  656.         *piLow = 0;
  657.  
  658.         for(i = 1; i < iInBuffers; i++)
  659.         {
  660.             if(pSortRec[i].lCur <= pSortRec[i].lMax)
  661.             {
  662.                 *piLow = i;
  663.                 memcpy(szTempStr,pSortWka -> pstKdata[i] -> key,iKeyLen);
  664.             }
  665.         }
  666.     }
  667.  
  668.     /*  here szTempStr is the iLowest value string */
  669.     /*  the multiple iInBuffers work as a priority queue, the szBuffer with
  670.           the iLowest value key has its data written out.  If there is more
  671.           data for that szBuffer/file it is loaded else iDoneBuffers++  */
  672.  
  673.     for(i = 1; i < iInBuffers; i++)
  674.     {
  675.         if((pSortRec[i].lCur <= pSortRec[i].lMax))
  676.         {
  677.             if(memcmp(pSortWka -> pstKdata[i] -> key,szTempStr,iKeyLen) < 0)
  678.             {
  679.                 memcpy(szTempStr,pSortWka -> pstKdata[i] -> key,iKeyLen);
  680.                 *piLow = i;
  681.             }
  682.         }
  683.     }
  684.  
  685.     return(0);
  686.  
  687. }
  688.  
  689.  
  690.  
  691.  
  692. int SortMergeBuffers(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms,int iInBuffers,SORT_REC_P pSortRec, FILE * fpWorkFiles[],FILE * fpOutFile,char * pcHighKey)
  693. {
  694.     int    iMergeFiles = TRUE;
  695.     int    iDoneBuffers = 0;
  696.     char    szBuffer[MAX_REC_LEN + 1];
  697.     int    iLow;
  698.  
  699.     while(iMergeFiles)
  700.     {
  701.         /*
  702.         **  Find & Remember the Lowest key in the merge buffers
  703.         */
  704.  
  705.         SortFindLowKey(pSortWka,iInBuffers,pSortRec,pcHighKey,&iLow);
  706.  
  707.         /*  
  708.         **     Write out this iLowest record to next level merge file or
  709.         **     directly into dest file if this is last merge 
  710.         */
  711.  
  712.         SortWriteRec(pSortWka,
  713.                         pSortParms,
  714.                         fpOutFile,
  715.                         iLow,
  716.                         ((pSortWka -> iSortBlocks-1) <= iInBuffers));
  717.  
  718.         /*
  719.         **  Begin to reset for next pass on internal buffers
  720.         */
  721.  
  722.         pSortRec[iLow].lCur++;   /*  pointer for this szBuffer */
  723.  
  724.         /*
  725.         **  Determine if more records to load from file from which
  726.         **  last record was written or if file is done
  727.         */
  728.  
  729.         if(pSortRec[iLow].lCur <= pSortRec[iLow].lMax)
  730.         {
  731.               /* ^ if there are more records for this file read one in */
  732.            
  733.             if(pSortParms -> iFileType == SORT_FILE_RELATIVE)
  734.                 fread(szBuffer,1,pSortWka -> iWorkRecLen,fpWorkFiles[iLow]);
  735.             else
  736.                 fgets(szBuffer,pSortWka -> iWorkRecLen,fpWorkFiles[iLow]);
  737.  
  738.             /* 
  739.             ** load into memory
  740.             */
  741.  
  742.             SortLoadRec(pSortWka,pSortParms,szBuffer,iLow);
  743.         }
  744.         else
  745.             iDoneBuffers++;  /*  no more records this file */
  746.  
  747.         /*
  748.         **  Check if all data from merge files at this level are merged 
  749.         **  into output file
  750.         */
  751.  
  752.         if(iDoneBuffers == iInBuffers)
  753.             iMergeFiles = FALSE;   
  754.  
  755.     }  /* while iMergeFiles */
  756.  
  757.     return(0);
  758. }                        
  759.  
  760.  
  761.  
  762. /*********************************************************************
  763. **
  764. **    Beginning Of Merging
  765. **
  766. *********************************************************************/
  767.  
  768. int SortMerge(SORT_WKA_P pSortWka, SORT_PARMS_P pSortParms)
  769. {
  770.     int        iWorkBlock;
  771.     int        iLevelBlock;
  772.     int        iLevelBlocks;
  773.     int        iOldLevelBlocks;
  774.     int        iInBuffers;
  775.     char        szFoutStr[64];
  776.     char        szHighKey[64 + 1];
  777.     char        szFworkStr[LIM_HANDLES-1][64];
  778.     FILE        *fpWorkFiles[LIM_HANDLES];
  779.     char        szBuffer[MAX_REC_LEN];   /* max 1K record length */
  780.     int        iMerging;
  781.     int        i;
  782.     FILE        * fpOutFile;
  783.     SORT_REC_T    stSortRec[LIM_HANDLES-1];
  784.  
  785.  
  786.  
  787.     iLevelBlocks = pSortWka -> iSortBlocks;
  788.     iWorkBlock = 1;
  789.     iLevelBlock = 1;
  790.  
  791.  
  792.     iInBuffers = MIN(pSortWka -> iMaxHandles-1,pSortWka -> iSortBlocks);
  793.  
  794.     iMerging = TRUE;
  795.  
  796.    while(iMerging)
  797.     {
  798.         /*
  799.         **  Calculate current status of merging
  800.         **  Determine if merging is completed
  801.         */
  802.  
  803.         if(iLevelBlock > iLevelBlocks)
  804.         {
  805.             iOldLevelBlocks = iLevelBlocks;
  806.             iLevelBlocks = pSortWka -> iSortBlocks - iLevelBlocks;
  807.             iLevelBlock = 1;
  808.  
  809.             if(iOldLevelBlocks < pSortWka -> iMaxHandles)
  810.             {
  811.             /* there were 2 blocks on the last level which are
  812.                     now one block, so we must be all done */
  813.  
  814.                 iMerging = FALSE;
  815.                 goto done_work;
  816.             }
  817.         }
  818.  
  819.         /*
  820.         **  Calculate how many files to merge
  821.         */
  822.  
  823.         iInBuffers = MIN(pSortWka -> iMaxHandles-1,iLevelBlocks);
  824.         iInBuffers = MIN(iInBuffers,iLevelBlocks-iLevelBlock+1);
  825.       
  826.         for(i = 0; i < iInBuffers; i++)
  827.          MakeTempFileName(szFworkStr[i],i + iWorkBlock -1);
  828.  
  829.         pSortWka -> iSortBlocks++;
  830.  
  831.         if(iLevelBlocks <= iInBuffers) 
  832.         {  
  833.             /*
  834.             ** this is last pass, go straight into dest file 
  835.             */
  836.  
  837.             strcpy(szFoutStr,pSortParms -> szDestFile);
  838.  
  839.             safekill(pSortParms -> szDestFile);
  840.         }
  841.       else 
  842.         {
  843.          MakeTempFileName(szFoutStr,pSortWka -> iSortBlocks -1);
  844.         }
  845.  
  846.  
  847.         /*
  848.         **  open target file
  849.         */
  850.  
  851.         if(pSortParms -> iFileType == SORT_FILE_RELATIVE)
  852.             fpOutFile = fopen(szFoutStr,"wb");
  853.         else
  854.             fpOutFile = fopen(szFoutStr,"w");
  855.  
  856. #ifdef DEBUG
  857.         printf("Writing to merge file %s\n\n", szFoutStr);
  858. #endif
  859.  
  860.         if(fpOutFile == NULL)
  861.         {
  862.             pSortWka -> iSortErr = 9;  /*  cant open enough files */
  863.             goto done_work;
  864.         }
  865.  
  866.       /*
  867.         **  open all the incoming files 
  868.         */
  869.  
  870.         for(i = 0; i < iInBuffers; i++)
  871.         {
  872.             stSortRec[i].lCur = 1;
  873.  
  874. #ifdef DEBUG
  875.             printf("Opening merge file %s\n", szFworkStr[i]);
  876. #endif
  877.  
  878.             /* 
  879.             **  For opening merge files, must reset lRecsInFile so
  880.             **  forces count if crlf files
  881.             */
  882.  
  883.             pSortParms -> lRecsInFile = 0;
  884.  
  885.             SortOpenFile(pSortWka,pSortParms,szFworkStr[i],&(fpWorkFiles[i]),&(stSortRec[i].lMax));
  886.         
  887.             /*
  888.             **  initial read from files
  889.             */
  890.  
  891.             if(pSortParms -> iFileType == SORT_FILE_RELATIVE)
  892.                 fread(szBuffer,1,pSortWka -> iWorkRecLen,fpWorkFiles[i]);
  893.             else
  894.                 fgets(szBuffer,pSortWka -> iWorkRecLen,fpWorkFiles[i]);
  895.  
  896.             /* 
  897.             ** load into memory
  898.             */
  899.  
  900.             SortLoadRec(pSortWka,pSortParms,szBuffer,i);
  901.  
  902.       }  /* for */
  903.  
  904.  
  905.         if(pSortParms -> pSortFields[0].iOrder == SORT_DESCENDING)
  906.         {
  907.             /* if first key is descending than the high key would be all 0's */
  908.             memset(szHighKey,0,iKeyLen);
  909.         }
  910.       else
  911.         {
  912.             /* if ascending then 255's are high */
  913.             memset(szHighKey,255,iKeyLen);
  914.         }
  915.  
  916.  
  917.         /*************************
  918.         **     Main Merging Process
  919.         **************************/
  920.  
  921.         SortMergeBuffers(pSortWka,pSortParms,iInBuffers,stSortRec,fpWorkFiles,fpOutFile,szHighKey);
  922.  
  923.         /*
  924.         **  Remove Source Files from this merge level
  925.         */
  926.  
  927.         for(i = 0; i < iInBuffers; i++)
  928.         { 
  929.          /*  get rid of last merge files */
  930.  
  931.             fclose(fpWorkFiles[i]);
  932.             safekill(szFworkStr[i]);
  933.         }
  934.    
  935.         fclose(fpOutFile);
  936.  
  937.         /*
  938.         **     The total number of iWorkBlocks is increased by the 
  939.         **  number of input merge files just processed  
  940.         */
  941.  
  942.         iWorkBlock += iInBuffers;  
  943.         iLevelBlock += iInBuffers;
  944.  
  945.  
  946.     }  /* while iMerging */
  947.  
  948. done_work:
  949.  
  950.     return(pSortWka -> iSortErr);
  951. }
  952.  
  953.  
  954.  
  955.  
  956. int SortTerminate(SORT_WKA_P pSortWka,SORT_PARMS_P pSortParms)
  957. {
  958.     long    lCnt;
  959.  
  960.     /*
  961.     **  Sort/Merge Completed, clean up
  962.     */
  963.  
  964.     for(lCnt = 0; lCnt < pSortWka -> lMaxMemRecs; lCnt++)  /* was to iMaxHandles?? Oct 92 Tal */
  965.     {
  966.         free(pSortWka -> pstKdata[lCnt]->key);
  967.  
  968.         if(pSortParms -> iSortType == SORT_TYPE_RECORD)
  969.             free(pSortWka -> pstKdata[lCnt] -> pcPtr);   /*  de-allocate in reverse, like PUSH POP / POP PUSH  */
  970.  
  971.         free(pSortWka -> pstKdata[lCnt]);
  972.     }
  973.  
  974.     free(pSortWka -> pstKdata);
  975.     free(pSortWka -> pcKey);
  976.     free(pSortWka -> pcPtr);
  977.  
  978.     return(pSortWka -> iSortErr);
  979. }
  980.  
  981.  
  982.  
  983.  
  984. void
  985. MakeKey(char *result,
  986.         char *szBuffer,
  987.         KEY_FIELD_T  *pstKeyField,
  988.         int iFields)
  989. {
  990.     int i,offs;
  991.     char  szTempStr[1024];
  992.  
  993.     *result = '\0';  /* null it out */
  994.     offs = 0;
  995.  
  996.     /* make the key  */
  997.     for(i = 0; i < iFields; i++, pstKeyField++)
  998.     {
  999.  
  1000.         /*  copy this portion of string into key work area = szTempStr */
  1001.         StrMid(szTempStr,szBuffer,pstKeyField->iBeg,pstKeyField->iLen);
  1002.  
  1003.         if(pstKeyField->iOrder == SORT_DESCENDING)  /*  if descending sequence */
  1004.             StrAnd(szTempStr);     /*  and the string's bytes with 255 to reverse values */
  1005.  
  1006.         if(i == 0)        /* if first, copy, otherwise concatenate it */
  1007.             memcpy(result,szTempStr,pstKeyField->iLen);
  1008.         else
  1009.             memcpy(result+offs,szTempStr,pstKeyField->iLen);
  1010.  
  1011.         offs += pstKeyField->iLen;
  1012.  
  1013.     }
  1014. }
  1015.  
  1016.  
  1017. void ShellSort(KDATA_T * v[], long n, int iSize)
  1018. {
  1019.     int    gap;
  1020.     int    i;
  1021.     int    j;
  1022.     int    k;
  1023.     KDATA_T  *iTemp;
  1024.  
  1025.     for(gap = (int) (n/2); gap > 0; gap /= 2)
  1026.     {
  1027.         for(i = gap; i < (int) n; i++)
  1028.         {
  1029.             for(j = i-gap; j >= 0; j -= gap)
  1030.             {
  1031.                 if(memcmp(v[j]->key, v[j+gap]->key,iSize) <= 0)  /* comparing szBuffers, so use memcmp not strcmp */
  1032.                     break;
  1033.  
  1034.                 k = j+gap;
  1035.                 iTemp = v[j];
  1036.                 v[j] = v[k];
  1037.                 v[k] = iTemp;
  1038.             }
  1039.         }
  1040.     }
  1041. }             
  1042.  
  1043. #if 0
  1044. quick_sort1(v,n)
  1045. char *v[];
  1046. int n;
  1047. {
  1048.     int  i,l,r,p;
  1049.     int  stack[50];
  1050.  
  1051.     l = 1;
  1052.     r = n;
  1053.     p = 2;
  1054.     do{
  1055.         if(r < l)
  1056.         {
  1057.             i = (l + r)/2;
  1058.           if((i-1) > (r-i)){
  1059.               stack[p] = l;
  1060.               stack[p+1] = i-1;
  1061.               l = i+1;
  1062.           } else {
  1063.               stack[p] = i+1;
  1064.               stack[p+1] = r;
  1065.               r = i-1;
  1066.           }
  1067.           p += 2;
  1068.         } else {     
  1069.             p -= 2;
  1070.           l = stack[p];
  1071.           r = stack[p+1];
  1072.         }
  1073.     }   while(p != 0);
  1074. }
  1075. #endif
  1076.  
  1077.  
  1078. #if 0
  1079. void itohex(hex_ret,h)
  1080. char *hex_ret;
  1081. unsigned h;
  1082.   {
  1083.     int   hex_iTemp,i,h_ing,h_len;
  1084.     char  hex_mas[17];
  1085.  
  1086.     hex_ret[0] = '\0';
  1087.     strcpy(hex_mas,"0123456789ABCDEF");
  1088.  
  1089.  
  1090.     h_ing = 1;
  1091.     while(h_ing){
  1092.        hex_iTemp = h & 0x0F;
  1093.  
  1094.        h_len = strlen(hex_ret);
  1095.        if(h_len > 0)
  1096.       for(i = h_len; i > 0; i--)
  1097.          hex_ret[i] = hex_ret[i-1];
  1098.  
  1099.        i = h_len+1;
  1100.        hex_ret[i] = '\0';
  1101.        /* ^ shift string down */
  1102.        hex_ret[0] = hex_mas[hex_iTemp];
  1103.        if(h == 0)
  1104.       h_ing = 0;
  1105.        h >>= 4;  /* div 16 */
  1106.        if(h_ing && (h == 0))
  1107.       h_ing = 0;
  1108.     }
  1109.     
  1110. }
  1111. #endif
  1112.  
  1113.  
  1114. void StrAnd(char * n)
  1115. {
  1116.     int i;
  1117.  
  1118.     for(i = 0; n[i]; i++)
  1119.         n[i] = ((char) 255) - n[i];
  1120. }
  1121.  
  1122.  
  1123.  
  1124. #if 0
  1125. void qsort1(rec,recs)
  1126. char *rec[];
  1127. unsigned  recs;
  1128. {
  1129.      int  stackl[16],stackr[16];
  1130.      int  s,l,r,i,j,xoffs,q;
  1131.      char *iTemp;
  1132.  
  1133.                   s = 0;
  1134.           stackl[0] = 0;
  1135.           stackr[0] = recs-1;
  1136.           while(s >= 0){
  1137.               l = stackl[s];
  1138.               r = stackr[s];
  1139.               s--;
  1140.           qs10:
  1141.               i = l;
  1142.               j = r;
  1143.               xoffs = (l + r + 1) >> 1;   /*  / 2;  */
  1144.               printf("xoffs = %d\n",xoffs);
  1145.           qs20:
  1146.               while(strcmp(rec[i],rec[xoffs]) < 0){
  1147.                  i++;
  1148.               }
  1149.               while(strcmp(rec[xoffs],rec[j]) < 0){
  1150.                  j--;
  1151.               }
  1152.               /* for( ; strcmp(rec[i],rec[xoffs]) != 0; i++); */
  1153.               /* for( ; strcmp(rec[xoffs],rec[j]) != 0; j--); */
  1154.               if(i > j)
  1155.                 goto qs30;
  1156.  
  1157.               printf("swapping %s and %s \n",rec[i],rec[j]);
  1158.  
  1159.               iTemp = rec[i];
  1160.               rec[i] = rec[j];
  1161.               rec[j] = iTemp;
  1162.               i++;
  1163.               j--;
  1164.               /*
  1165.               for(q=0; q <= recs; q++)
  1166.                  puts(rec[q]);
  1167.               */
  1168.           qs30:
  1169.               if(i <= j)
  1170.                 goto qs20;
  1171.               if((j-l) >= (r-i))
  1172.                 goto qs50;
  1173.               if(i >= r)
  1174.                 goto qs40;
  1175.               s++;
  1176.               stackl[s] = i;
  1177.               stackr[s] = r;
  1178.           qs40:
  1179.               r = j;
  1180.               goto qs70;
  1181.           qs50:
  1182.               if(l >= j)
  1183.                 goto qs60;
  1184.               s++;
  1185.               stackl[s] = l;
  1186.               stackl[s] = j;
  1187.           qs60:
  1188.               l = i;
  1189.           qs70:
  1190.               if(l < r)
  1191.                 goto qs10;
  1192.           }
  1193.  
  1194.  
  1195.  }
  1196.  
  1197. qcompare(k1,k2)
  1198. KDATA_T *k1, *k2;
  1199. {
  1200.   return(memcmp(k1->key,k2->key,iKeyLen));
  1201. }
  1202. #endif
  1203.  
  1204.  
  1205. void MakeTempFileName(char * pcFileName,int iSortBlocks)
  1206. {
  1207.    char  szHexStr[5];
  1208.  
  1209.     strcpy(pcFileName,"CS");
  1210.     sprintf(szHexStr,"%x",iSortBlocks);
  1211.     strcat(pcFileName,szHexStr);
  1212. }
  1213.  
  1214.