Programmer 7500/MAX_PROGRAMMERS.iso/INFO/PCMAG/VOL8N08.ARC/MAKEHASH.C

C/C++ Source or Header | 1988-12-20 | 5.8 KB | 173 lines

/*
    MAKEHASH.C - Creates a data file and hash table for SRCHHASH.C

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

    The user is prompted to enter from zero to one hundred ASCII
    strings.  These strings are used to build records in the
    main data file TESTFILE.DAT and a hash table TESTFILE.HSH.

    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 SRCHHASH.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 ISIZE    80                     /* max entry length */
#define N_ITEMS  100                    /* max number of strings */
#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 */

char items[N_ITEMS * ISIZE];            /* original entries stored here */

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

int getkeys(void);                      /* function prototypes */
void writedata(int);
void writehash(int);
int hashcode(char *);

main()
{
    int i;                              /* number of keys entered */

    i = getkeys();                      /* get record keys from user */
    writedata(i);                       /* write main data file */
    writehash(i);                       /* write hash table */
}

/*
    Get record keys from user, leave them in array 'items',
    return number of keys to caller.
*/
int getkeys(void)
{
    int i, j;                           /* scratch variables */

    puts("\nEnter keys for file records...");

    i = 0;                              /* initialize string count */

    while(i < N_ITEMS)                  /* enforce maximum entries */
    {
        printf("%2d: ", i+1);           /* prompt user for next string */
        gets(&items[ISIZE * i]);        /* read keyboard, store in array */

                                        /* last entry if empty line */
        if(items[ISIZE * i] == 0) break;

        for(j = 0; j < i; j++)          /* make sure not duplicate key */
        {
            if(strcmp(&items[ISIZE * i], &items[ISIZE * j]) == 0)
                break;                  /* exit loop if duplicate found */
        }

        if(i == j) i++;                 /* count non-duplicate strings */
        else puts("Duplicate key, try again.");
    }

    return (i);                         /* return no. of keys entered */
}

/*
    Create main data file TESTFILE.DAT, using strings stored
    in array 'items'.
*/
void writedata(recs)
{
    int i = 0;                          /* scratch variable */
    int fh;                             /* handle for output file */
    char recbuf[RSIZE];                 /* scratch record buffer */

                                        /* create main data file */
    fh = open("TESTFILE.DAT", O_WRONLY|O_CREAT|O_TRUNC|O_BINARY, S_IWRITE);

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

    puts("\nWriting TESTFILE.DAT...");

    while(i < recs)                     /* build and write records */
    {
        memset(recbuf, 0, RSIZE);
        strncpy(recbuf, &items[ISIZE * i], RSIZE);
        write(fh, recbuf, RSIZE);
        i++;
    }

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

/*
    Create hash table, using strings stored in the array 'items'.
    Write hash table into the file TESTFILE.HSH.
*/
void writehash(recs)
{
    int i = 0, j;                       /* scratch variables */
    int fh;                             /* hash table file handle */

    memset(hashtab,-1,sizeof(hashtab)); /* initialize hash table */

    while(i < recs)                     /* build hash table */
    {
        j = hashcode(&items[ISIZE*i]);  /* calculate hash code */
        hashtab[j] = i++;               /* put pointer into table */
    }

                                        /* create hash table file */
    fh = open("TESTFILE.HSH", O_WRONLY|O_CREAT|O_TRUNC|O_BINARY, S_IWRITE);

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

    puts("\nWriting TESTFILE.HSH...");  /* write hash table */
    write(fh, (char *) hashtab, sizeof(hashtab));
    close(fh);                          /* release file handle */
}

/*
    Calculate hash code from supplied ASCII string.  Probe hash
    table and increment hashcode if necessary in order to return
    the hashcode of an unused position in the hash table.  Hash
    code is clamped to the range {0 ... HASHSIZE-1}.
*/
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];
    j = j & (HASHSIZE - 1);             /* clamp hash code */

    while(hashtab[j] != -1)             /* search for unused slot */
    {
        j += HASHINCR;                  /* increment hash code */

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

    return(j);                          /* return hash code */
}