binsrch.c

语法分析器 完成从c/c++向C++转变

#ifdef SIMPLE_ONE

/*
**  BINSRCH.C
**
**     this is a conceptual prototype to prove the ability
**     to do binary search access on a standard flat file.
**
**     John Tal    March 1, 1991
**
**
*/




#include <stdio.h>

#define  FALSE  0
#define  TRUE  -1

#define  FORM_ID_LEN 4    /* form id len for ICR */

#define  BUFF_LEN  80     /* working buffer size */





main()
{

   FILE  * psFile;                   /* file we will look for form ids in */
   short   sSts;                     /* working status code */
   char    szBuffer[BUFF_LEN + 1];   /* buffer for file input/fgets */


   psFile = fopen("test.dat","r");    /* open a file */

   sSts = BinarySearch(psFile,"1232",szBuffer);   /* search for 1232 */
   sSts = BinarySearch(psFile,"1233",szBuffer);   /* search for 1233 */

   fclose(psFile);   /* close */
}


/*
**  The following function, FormIdCompareFunc, is supplied
**  to BinarySearch.  This way BinarySearch can be used
**  on many types of flat files.  The logic for key matching
**  is provided by the application to BinarySearch through
**  a compare function.  FormIdCompareFunc() will compare
**  form ids.
*/

FormIdCompareFunc(pcData1,pcData2)
char  * pcData1;
char  * pcData2;
{
   return(strncmp(pcData1,pcData2,FORM_ID_LEN));
}



BinarySearch(psFile,pcKey,pcBuffer,sCompareFunc)
FILE * psFile;
char * pcKey;
char * pcBuffer;
int  (*sCompareFunc)();
{
   static char init = 0;

   static long * plPos;

   static long lRecs;
   long        lFirst;
   long        lLast;
   long        lMidPoint;

   short       sCmp;

   char        fFound;

   if(!init)
   {
       fseek(psFile,0L,0);

       lRecs = 0;

       while(!feof(psFile))
       {
   	   fgets(pcBuffer,BUFF_LEN, psFile);
   	   if(!feof(psFile))
   	   {
   	      lRecs++;
   	   }
       }

       /*
       **  Allocate array of longs to hold offsets
       */

       plPos = (long *) calloc(lRecs,sizeof(long));

       fseek(psFile,0L,0);

       lRecs = 0;
       plPos[lRecs] = 0;
       while(!feof(psFile))
       {
	      fgets(pcBuffer,BUFF_LEN, psFile);
   	   if(!feof(psFile))
   	   {
	        lRecs++;
   	     plPos[lRecs] = ftell(psFile);
   	   }
	   }

   	init = 1;
   }


   /*
   **  In either case, search for data, (heart of binary search)
   */

   fFound = FALSE;
   lFirst = 0;
   lLast = lRecs;

   while( (lFirst <= lLast) && !fFound)
   {
       lMidPoint = (lFirst + lLast) >> 1;   /*  dividing by 2 */

       fseek(psFile,plPos[lMidPoint],0);

       fgets(pcBuffer,BUFF_LEN,psFile);

       sCmp = (*sCompareFunc)(pcBuffer,pcKey);

       if(sCmp == 0)
	     fFound = TRUE;
       else if(sCmp > 0)
   	  lLast = lMidPoint - 1;
       else
   	  lFirst = lMidPoint + 1;

   }

   if(fFound)
     return(0);
   else
     return(-1);

}


#endif



/*
**  BINSRCH.C
**
**     this is a conceptual prototype to prove the ability
**     to do binary search access on a standard flat file.
**
**     John Tal    March 1, 1991
**
**
*/




#include <stdio.h>

#define  FALSE  0
#define  TRUE  -1

#define  FORM_ID_LEN 4    /* form id len for ICR */

#define  BUFF_LEN  80     /* working buffer size */



/*
**  The following function, FormIdCompareFunc, is supplied
**  to BinarySearch.  This way BinarySearch can be used
**  on many types of flat files.  The logic for key matching
**  is provided by the application to BinarySearch through
**  a compare function.  FormIdCompareFunc() will compare
**  form ids.
*/

FormIdCompareFunc(pcData1,pcData2)
char  * pcData1;   /* data from file */
char  * pcData2;   /* key looking for */
{
   return(strncmp(pcData1,pcData2,FORM_ID_LEN));
}





/*
**  BIN_SEARCH is used in all communication with the BinarySearch
**  function.  This way, many files may be processed by the
**  routine simultaneously
*/

struct BIN_SEARCH_S{
      FILE  * psFile;
      char  * pcKey;
      char  * pcBuffer;
      int  (* sCompareFunc)();
      char    init;
      long    lRecs;
      long  * plPos;
};

typedef struct BIN_SEARCH_S BIN_SEARCH_T;
typedef BIN_SEARCH_T * BIN_SEARCH_P;



main()
{

   FILE  * psFile;                   /* file we will look for form ids in */
   short   sSts;                     /* working status code */
   char    szBuffer[BUFF_LEN + 1];   /* buffer for file input/fgets */

   BIN_SEARCH_T  stBin;


   psFile = fopen("test.dat","r");    /* open a file */


   /*
   **  Set up the binary search control structure
   */

   stBin.psFile = psFile;
   stBin.sCompareFunc = FormIdCompareFunc;
   stBin.init = FALSE;
   stBin.pcBuffer = szBuffer;


   stBin.pcKey = "1232";
   sSts = BinarySearch(&stBin);   /* search for 1232 */

   stBin.pcKey = "1233";
   sSts = BinarySearch(psFile,"1233",szBuffer);   /* search for 1233 */

   fclose(psFile);   /* close */
}




/*
**  Binary Search
**
**    Searches file psFile for key pcKey.  If found, entire
**    record is placed in pcBuffer.   At each record checked,
**    the application supplied function sCompareFunc is called
**    to check if the current record matches the key desired.
**
**    Assumption:  All keys in a file are unique and the
**                 file is sorted by those unique keys.
**
**                 A binary search on an unsorted file is worthless.
**
**    Returns:      0 = key found
**              non-0 = key not found
**
*/




BinarySearch(psBin)
BIN_SEARCH_P  psBin;   /* binary search control structure */
{
   long        lFirst;
   long        lLast;
   long        lMidPoint;

   short       sCmp;

   char        fFound;

   if(!psBin -> init)
   {
       fseek(psBin -> psFile,0L,0);

       psBin -> lRecs = 0;

       while(!feof(psBin -> psFile))
       {
   	   fgets(psBin -> pcBuffer,BUFF_LEN, psBin -> psFile);
   	   if(!feof(psBin -> psFile))
   	   {
   	      psBin -> lRecs++;
   	   }
       }

       /*
       **  Allocate array of longs to hold offsets
       */

       psBin -> plPos = (long *) calloc(psBin -> lRecs,sizeof(long));

       fseek(psBin -> psFile,0L,0);

       psBin -> lRecs = 0;
       psBin -> plPos[psBin -> lRecs] = 0;
       while(!feof(psBin -> psFile))
       {
	      fgets(psBin -> pcBuffer,BUFF_LEN, psBin -> psFile);
   	   if(!feof(psBin -> psFile))
	      {
	        psBin -> lRecs++;
   	     psBin -> plPos[psBin -> lRecs] = ftell(psBin -> psFile);
	      }
   	}

   	psBin -> init = TRUE;   /* mark as having been loaded */
   }


   /*
   **  In either case, search for data, (heart of binary search)
   */

   fFound = FALSE;
   lFirst = 0;
   lLast = psBin -> lRecs;

   while( (lFirst <= lLast) && !fFound)
   {
       lMidPoint = (lFirst + lLast) >> 1;   /*  dividing by 2 */

       fseek(psBin -> psFile,psBin -> plPos[lMidPoint],0);

       fgets(psBin -> pcBuffer,BUFF_LEN,psBin -> psFile);

       sCmp = (*psBin -> sCompareFunc)(psBin -> pcBuffer,psBin -> pcKey);

       if(sCmp == 0)
	     fFound = TRUE;
       else if(sCmp > 0)
   	  lLast = lMidPoint - 1;
       else
	     lFirst = lMidPoint + 1;

   }

   if(fFound)
     return(0);
   else
     return(-1);

}