/*
    SRCHHASH.C  Searches datafile and hash table created by MAKEHASH.C

    Copyright (C) 1988 Ziff Communications Co.
    PC Magazine * Ray Duncan

    The user is prompted to enter a search key.  A hash code 
    is generated and is used to probe the hash table stored in 
    the file TESTFILE.HSH.  The record number, if any, found
    in the hash table is used to read a record from TESTFILE.DAT.
    Collisions are resolved by adding a constant increment
    to the hashcode and wrapping when necessary until the
    desired record or an empty hash table position is found.

    Each record in TESTFILE.DAT is RSIZE bytes long.  The size
    of the hash table is determined by the constant HASHSIZE.
    The incrementing value for linear probing is HASHINCR.
    All manifest constants and structures must be synchronized
    with MAKEHASH.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 HASHSIZE 1024                   /* hash table size, should
                                           be power of 2 */
#define HASHINCR 7                      /* incrementing value for
                                           linear probes of hash table */

int hashtab[HASHSIZE];                  /* hash table read here */

int hashcode(char *);                   /* function prototypes */

main()
{
    int i;                              /* scratch variable */
    int fhdf, fhht;                     /* file handles */
    int inspected;                      /* number of hash table
                                           entries inspected */
    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 all files */
    fhdf = open("TESTFILE.DAT", O_RDONLY | O_BINARY);
    fhht = open("TESTFILE.HSH", O_RDONLY | O_BINARY);

    if((fhdf == -1) || (fhht == -1))
    {
        puts("\nMissing data file or hash table file.");
        exit(1);
    }

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

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

                                        /* read hash table into memory */
    read(fhht, (char *) hashtab, sizeof(hashtab));
    close(fhht);                        /* and release its handle */

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

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

        inspected = 1;                  /* initialize inspection count */
        i = hashcode(key);              /* calculate hash code */

        while(hashtab[i] != -1)         /* inspect datafile records */
        {
            lseek(fhdf, (long) (RSIZE * hashtab[i]), SEEK_SET);
            read(fhdf, rec, RSIZE);     
            
            if(strcmp(rec, key) == 0)   /* if match, we're done */
                break;

            i += HASHINCR;              /* otherwise bump hashcode */

            if(i >= HASHSIZE)           /* wrap hashcode if necessary */
                i -= HASHSIZE;

            inspected++;                /* count table inspections */
        }

        if(hashtab[i] == -1) printf("\nRecord not found");
        else printf("\nContents of record %d: %s", hashtab[i], rec);
        printf(" --- %d hash table entries inspected", inspected);
    }

    close(fhdf);                        /* release data file handle */
}


/*
    Calculate hash code from supplied ASCII string.  Hash
    code is clamped to the range {0 ... HASHSIZE-1}.  Collisions
    are resolved elsewhere.
*/
int hashcode(char *kptr)
{
    int i, j = 0;                       /* scratch variables */

                                        /* sum characters of key */
    for(i = 0; i < strlen(kptr); i++) j = (j*2) + kptr[i];

    return(j & (HASHSIZE - 1));         /* clamp hash code */
}