home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / text_cla / binsrch.c next >
Encoding:
C/C++ Source or Header  |  1992-07-23  |  7.2 KB  |  368 lines
  1. #ifdef SIMPLE_ONE
  2.  
  3. /*
  4. **  BINSRCH.C
  5. **
  6. **     this is a conceptual prototype to prove the ability
  7. **     to do binary search access on a standard flat file.
  8. **
  9. **     John Tal    March 1, 1991
  10. **
  11. **
  12. */
  13.  
  14.  
  15.  
  16.  
  17. #include <stdio.h>
  18.  
  19. #define  FALSE  0
  20. #define  TRUE  -1
  21.  
  22. #define  FORM_ID_LEN 4    /* form id len for ICR */
  23.  
  24. #define  BUFF_LEN  80     /* working buffer size */
  25.  
  26.  
  27.  
  28.  
  29.  
  30. main()
  31. {
  32.  
  33.    FILE  * psFile;                   /* file we will look for form ids in */
  34.    short   sSts;                     /* working status code */
  35.    char    szBuffer[BUFF_LEN + 1];   /* buffer for file input/fgets */
  36.  
  37.  
  38.    psFile = fopen("test.dat","r");    /* open a file */
  39.  
  40.    sSts = BinarySearch(psFile,"1232",szBuffer);   /* search for 1232 */
  41.    sSts = BinarySearch(psFile,"1233",szBuffer);   /* search for 1233 */
  42.  
  43.    fclose(psFile);   /* close */
  44. }
  45.  
  46.  
  47. /*
  48. **  The following function, FormIdCompareFunc, is supplied
  49. **  to BinarySearch.  This way BinarySearch can be used
  50. **  on many types of flat files.  The logic for key matching
  51. **  is provided by the application to BinarySearch through
  52. **  a compare function.  FormIdCompareFunc() will compare
  53. **  form ids.
  54. */
  55.  
  56. FormIdCompareFunc(pcData1,pcData2)
  57. char  * pcData1;
  58. char  * pcData2;
  59. {
  60.    return(strncmp(pcData1,pcData2,FORM_ID_LEN));
  61. }
  62.  
  63.  
  64.  
  65. BinarySearch(psFile,pcKey,pcBuffer,sCompareFunc)
  66. FILE * psFile;
  67. char * pcKey;
  68. char * pcBuffer;
  69. int  (*sCompareFunc)();
  70. {
  71.    static char init = 0;
  72.  
  73.    static long * plPos;
  74.  
  75.    static long lRecs;
  76.    long        lFirst;
  77.    long        lLast;
  78.    long        lMidPoint;
  79.  
  80.    short       sCmp;
  81.  
  82.    char        fFound;
  83.  
  84.    if(!init)
  85.    {
  86.        fseek(psFile,0L,0);
  87.  
  88.        lRecs = 0;
  89.  
  90.        while(!feof(psFile))
  91.        {
  92.           fgets(pcBuffer,BUFF_LEN, psFile);
  93.           if(!feof(psFile))
  94.           {
  95.              lRecs++;
  96.           }
  97.        }
  98.  
  99.        /*
  100.        **  Allocate array of longs to hold offsets
  101.        */
  102.  
  103.        plPos = (long *) calloc(lRecs,sizeof(long));
  104.  
  105.        fseek(psFile,0L,0);
  106.  
  107.        lRecs = 0;
  108.        plPos[lRecs] = 0;
  109.        while(!feof(psFile))
  110.        {
  111.           fgets(pcBuffer,BUFF_LEN, psFile);
  112.           if(!feof(psFile))
  113.           {
  114.             lRecs++;
  115.             plPos[lRecs] = ftell(psFile);
  116.           }
  117.        }
  118.  
  119.        init = 1;
  120.    }
  121.  
  122.  
  123.    /*
  124.    **  In either case, search for data, (heart of binary search)
  125.    */
  126.  
  127.    fFound = FALSE;
  128.    lFirst = 0;
  129.    lLast = lRecs;
  130.  
  131.    while( (lFirst <= lLast) && !fFound)
  132.    {
  133.        lMidPoint = (lFirst + lLast) >> 1;   /*  dividing by 2 */
  134.  
  135.        fseek(psFile,plPos[lMidPoint],0);
  136.  
  137.        fgets(pcBuffer,BUFF_LEN,psFile);
  138.  
  139.        sCmp = (*sCompareFunc)(pcBuffer,pcKey);
  140.  
  141.        if(sCmp == 0)
  142.          fFound = TRUE;
  143.        else if(sCmp > 0)
  144.          lLast = lMidPoint - 1;
  145.        else
  146.          lFirst = lMidPoint + 1;
  147.  
  148.    }
  149.  
  150.    if(fFound)
  151.      return(0);
  152.    else
  153.      return(-1);
  154.  
  155. }
  156.  
  157.  
  158. #endif
  159.  
  160.  
  161.  
  162. /*
  163. **  BINSRCH.C
  164. **
  165. **     this is a conceptual prototype to prove the ability
  166. **     to do binary search access on a standard flat file.
  167. **
  168. **     John Tal    March 1, 1991
  169. **
  170. **
  171. */
  172.  
  173.  
  174.  
  175.  
  176. #include <stdio.h>
  177.  
  178. #define  FALSE  0
  179. #define  TRUE  -1
  180.  
  181. #define  FORM_ID_LEN 4    /* form id len for ICR */
  182.  
  183. #define  BUFF_LEN  80     /* working buffer size */
  184.  
  185.  
  186.  
  187. /*
  188. **  The following function, FormIdCompareFunc, is supplied
  189. **  to BinarySearch.  This way BinarySearch can be used
  190. **  on many types of flat files.  The logic for key matching
  191. **  is provided by the application to BinarySearch through
  192. **  a compare function.  FormIdCompareFunc() will compare
  193. **  form ids.
  194. */
  195.  
  196. FormIdCompareFunc(pcData1,pcData2)
  197. char  * pcData1;   /* data from file */
  198. char  * pcData2;   /* key looking for */
  199. {
  200.    return(strncmp(pcData1,pcData2,FORM_ID_LEN));
  201. }
  202.  
  203.  
  204.  
  205.  
  206.  
  207. /*
  208. **  BIN_SEARCH is used in all communication with the BinarySearch
  209. **  function.  This way, many files may be processed by the
  210. **  routine simultaneously
  211. */
  212.  
  213. struct BIN_SEARCH_S{
  214.       FILE  * psFile;
  215.       char  * pcKey;
  216.       char  * pcBuffer;
  217.       int  (* sCompareFunc)();
  218.       char    init;
  219.       long    lRecs;
  220.       long  * plPos;
  221. };
  222.  
  223. typedef struct BIN_SEARCH_S BIN_SEARCH_T;
  224. typedef BIN_SEARCH_T * BIN_SEARCH_P;
  225.  
  226.  
  227.  
  228. main()
  229. {
  230.  
  231.    FILE  * psFile;                   /* file we will look for form ids in */
  232.    short   sSts;                     /* working status code */
  233.    char    szBuffer[BUFF_LEN + 1];   /* buffer for file input/fgets */
  234.  
  235.    BIN_SEARCH_T  stBin;
  236.  
  237.  
  238.    psFile = fopen("test.dat","r");    /* open a file */
  239.  
  240.  
  241.    /*
  242.    **  Set up the binary search control structure
  243.    */
  244.  
  245.    stBin.psFile = psFile;
  246.    stBin.sCompareFunc = FormIdCompareFunc;
  247.    stBin.init = FALSE;
  248.    stBin.pcBuffer = szBuffer;
  249.  
  250.  
  251.    stBin.pcKey = "1232";
  252.    sSts = BinarySearch(&stBin);   /* search for 1232 */
  253.  
  254.    stBin.pcKey = "1233";
  255.    sSts = BinarySearch(psFile,"1233",szBuffer);   /* search for 1233 */
  256.  
  257.    fclose(psFile);   /* close */
  258. }
  259.  
  260.  
  261.  
  262.  
  263. /*
  264. **  Binary Search
  265. **
  266. **    Searches file psFile for key pcKey.  If found, entire
  267. **    record is placed in pcBuffer.   At each record checked,
  268. **    the application supplied function sCompareFunc is called
  269. **    to check if the current record matches the key desired.
  270. **
  271. **    Assumption:  All keys in a file are unique and the
  272. **                 file is sorted by those unique keys.
  273. **
  274. **                 A binary search on an unsorted file is worthless.
  275. **
  276. **    Returns:      0 = key found
  277. **              non-0 = key not found
  278. **
  279. */
  280.  
  281.  
  282.  
  283.  
  284. BinarySearch(psBin)
  285. BIN_SEARCH_P  psBin;   /* binary search control structure */
  286. {
  287.    long        lFirst;
  288.    long        lLast;
  289.    long        lMidPoint;
  290.  
  291.    short       sCmp;
  292.  
  293.    char        fFound;
  294.  
  295.    if(!psBin -> init)
  296.    {
  297.        fseek(psBin -> psFile,0L,0);
  298.  
  299.        psBin -> lRecs = 0;
  300.  
  301.        while(!feof(psBin -> psFile))
  302.        {
  303.           fgets(psBin -> pcBuffer,BUFF_LEN, psBin -> psFile);
  304.           if(!feof(psBin -> psFile))
  305.           {
  306.              psBin -> lRecs++;
  307.           }
  308.        }
  309.  
  310.        /*
  311.        **  Allocate array of longs to hold offsets
  312.        */
  313.  
  314.        psBin -> plPos = (long *) calloc(psBin -> lRecs,sizeof(long));
  315.  
  316.        fseek(psBin -> psFile,0L,0);
  317.  
  318.        psBin -> lRecs = 0;
  319.        psBin -> plPos[psBin -> lRecs] = 0;
  320.        while(!feof(psBin -> psFile))
  321.        {
  322.           fgets(psBin -> pcBuffer,BUFF_LEN, psBin -> psFile);
  323.           if(!feof(psBin -> psFile))
  324.           {
  325.             psBin -> lRecs++;
  326.             psBin -> plPos[psBin -> lRecs] = ftell(psBin -> psFile);
  327.           }
  328.        }
  329.  
  330.        psBin -> init = TRUE;   /* mark as having been loaded */
  331.    }
  332.  
  333.  
  334.    /*
  335.    **  In either case, search for data, (heart of binary search)
  336.    */
  337.  
  338.    fFound = FALSE;
  339.    lFirst = 0;
  340.    lLast = psBin -> lRecs;
  341.  
  342.    while( (lFirst <= lLast) && !fFound)
  343.    {
  344.        lMidPoint = (lFirst + lLast) >> 1;   /*  dividing by 2 */
  345.  
  346.        fseek(psBin -> psFile,psBin -> plPos[lMidPoint],0);
  347.  
  348.        fgets(psBin -> pcBuffer,BUFF_LEN,psBin -> psFile);
  349.  
  350.        sCmp = (*psBin -> sCompareFunc)(psBin -> pcBuffer,psBin -> pcKey);
  351.  
  352.        if(sCmp == 0)
  353.          fFound = TRUE;
  354.        else if(sCmp > 0)
  355.          lLast = lMidPoint - 1;
  356.        else
  357.          lFirst = lMidPoint + 1;
  358.  
  359.    }
  360.  
  361.    if(fFound)
  362.      return(0);
  363.    else
  364.      return(-1);
  365.  
  366. }
  367.  
  368.