/*
    SRCHNIF.C   Searches file previously created by MAKENIF.EXE
    Copyright (c) 1989 Ziff Communications Co.
    PC Magazine * Ray Duncan

    The user is prompted to enter a search key.  The first
    8 characters of the key are used to search TESTFILE.DAT,
    using both the sequential and binary search algorithms.
    The success or failure of the search is reported along
    with the number of records inspected by each method.

    Each record in TESTFILE.DAT is RSIZE bytes long.  Bytes 
    0 to (KSIZE-1) of the record are the ASCII key for searches
    by SRCHNIF.C.  Bytes KSIZE to (RSIZE-1) of the record
    are initialized to zero and are not used.  RSIZE and KSIZE
    must be kept synchronized with their definitions in MAKENIF.C.
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <fcntl.h>
#include <sys\types.h>
#include <sys\stat.h>
#include <io.h>

#define RSIZE   64                      /* fixed record size */
#define KSIZE    8                      /* maximum key length */

static int inspected;                   /* records inspected counter */

main()
{
    int i, j;                           /* some scratch variables */
    int fh;                             /* handle for data file */
    long fsize;                         /* size of file in bytes */
    int frecs;                          /* number of records in file */
    char key[80];                       /* key entered by user */
    char rec[RSIZE];                    /* scratch record buffer */

                                        /* open our data file */
    fh = open("TESTFILE.DAT", O_RDONLY | O_BINARY);

    if(fh == -1)                        /* terminate if open failed */
    {
        puts("\nCan't find TESTFILE.DAT.");
        exit(1);
    }

    fsize = lseek(fh, 0L, SEEK_END);    /* find file size */
    frecs = fsize / RSIZE;              /* calculate number of records */

    printf("\nTESTFILE.DAT contains %ld bytes, %d records.", fsize, frecs);

    while(1)                    
    {
        printf("\n\nEnter key: ");      /* prompt user and */   
        gets(key);                      /* input record key */

        if(key[0] == 0) break;          /* terminate if empty line */

        if(strlen(key) > KSIZE) 
            printf("\nWarning:  key truncated to %d characters.", KSIZE);

        inspected = 0;                  /* reset record counter */

                                        /* perform sequential search */
                                        /* and display results */
        printf("\nSequential search result:  ");
        if((i = seqsearch(fh, key)) == -1) printf("record not found,");
        else printf("record number is %d,", i);
        printf("  %d records inspected.", inspected);
 
        inspected = 0;                  /* reset record counter */

                                        /* perform binary search */
                                        /* and display results */
        printf("\nBinary search result:      ");
        if((i = binsearch(fh, key, 0, frecs-1)) == -1) 
            printf("record not found,");
        else printf("record number is %d,", i);
        printf("  %d records inspected.", inspected);
    }

    close(fh);                          /* release file handle */
}

/*
    Search the file sequentially to match the specified key.
    Called with a file handle and key address.  Returns the record 
    number if match found, or -1 to indicate no match.
*/
int seqsearch(int fh, char *kptr)
{
    int i;                              /* scratch variable */
    char fbuff[RSIZE];                  /* file record buffer */

    lseek(fh, 0L, SEEK_SET);            /* rewind to start of file */

    while(read(fh, fbuff, RSIZE) != 0)  /* do until end of file found */
    {
        inspected++;                    /* count records inspected */
        
        i = strncmp(kptr, fbuff, KSIZE);    /* compare keys */

        if(i == 0) return(inspected-1); /* if matched, return record no. */
        else if(i < 0) break;           /* if record absent, end search */
    }

    return(-1);                         /* no match, return -1 */
}

/*
    Binary search the file to match the specified key.
    Called with a file handle, key address, and the first 
    and last record numbers of the file segment being 
    inspected.  Returns the record number if match found, 
    or -1 to indicate no match.
*/
int binsearch(int fh, char *kptr, int left, int right)
{
    int i, j;                           /* scratch variables */
    char fbuff[RSIZE];                  /* file record buffer */

    if(left > right) return(-1);        /* end search if record absent */

    i = (left + right) / 2;             /* calculate record number */
                                        
    inspected++;                        /* count records inspected */
    lseek(fh, (long) (i * RSIZE), SEEK_SET);
    read(fh, fbuff, RSIZE);             /* read the record */

    j = strncmp(kptr, fbuff, KSIZE);    /* compare keys */

    if(j == 0) return(i);               /* if matched, return record no. */

                                        /* otherwise bisect file, recurse
                                           to inspect next record */
    if(j < 0) binsearch(fh, kptr, left, i-1);
    else      binsearch(fh, kptr, i+1, right);
}