home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 December / simtel1292_SIMTEL_1292_Walnut_Creek.iso / msdos / pcmag / vol8n08.arc / SRCHHASH.C < prev    next >
Text File  |  1988-12-20  |  4KB  |  120 lines
  1. /*
  2.     SRCHHASH.C  Searches datafile and hash table created by MAKEHASH.C
  3.  
  4.     Copyright (C) 1988 Ziff Communications Co.
  5.     PC Magazine * Ray Duncan
  6.  
  7.     The user is prompted to enter a search key.  A hash code 
  8.     is generated and is used to probe the hash table stored in 
  9.     the file TESTFILE.HSH.  The record number, if any, found
  10.     in the hash table is used to read a record from TESTFILE.DAT.
  11.     Collisions are resolved by adding a constant increment
  12.     to the hashcode and wrapping when necessary until the
  13.     desired record or an empty hash table position is found.
  14.  
  15.     Each record in TESTFILE.DAT is RSIZE bytes long.  The size
  16.     of the hash table is determined by the constant HASHSIZE.
  17.     The incrementing value for linear probing is HASHINCR.
  18.     All manifest constants and structures must be synchronized
  19.     with MAKEHASH.C.
  20. */
  21.  
  22. #include <stdio.h>
  23. #include <string.h>
  24. #include <stdlib.h>
  25. #include <fcntl.h>
  26. #include <sys\types.h>
  27. #include <sys\stat.h>
  28. #include <io.h>
  29.  
  30. #define RSIZE   64                      /* fixed record size */
  31. #define HASHSIZE 1024                   /* hash table size, should
  32.                                            be power of 2 */
  33. #define HASHINCR 7                      /* incrementing value for
  34.                                            linear probes of hash table */
  35.  
  36. int hashtab[HASHSIZE];                  /* hash table read here */
  37.  
  38. int hashcode(char *);                   /* function prototypes */
  39.  
  40. main()
  41. {
  42.     int i;                              /* scratch variable */
  43.     int fhdf, fhht;                     /* file handles */
  44.     int inspected;                      /* number of hash table
  45.                                            entries inspected */
  46.     long fsize;                         /* size of file in bytes */
  47.     int frecs;                          /* number of records in file */
  48.     char key[80];                       /* key entered by user */
  49.     char rec[RSIZE];                    /* scratch record buffer */
  50.  
  51.                                         /* open all files */
  52.     fhdf = open("TESTFILE.DAT", O_RDONLY | O_BINARY);
  53.     fhht = open("TESTFILE.HSH", O_RDONLY | O_BINARY);
  54.  
  55.     if((fhdf == -1) || (fhht == -1))
  56.     {
  57.         puts("\nMissing data file or hash table file.");
  58.         exit(1);
  59.     }
  60.  
  61.     fsize = lseek(fhdf, 0L, SEEK_END);  /* find file size */
  62.     frecs = fsize / RSIZE;              /* calculate number of records */
  63.  
  64.     printf("\nTESTFILE.DAT contains %ld bytes, %d records.", fsize, frecs);
  65.  
  66.                                         /* read hash table into memory */
  67.     read(fhht, (char *) hashtab, sizeof(hashtab));
  68.     close(fhht);                        /* and release its handle */
  69.  
  70.     while(1)                    
  71.     {
  72.         printf("\n\nEnter key: ");      /* prompt user and */   
  73.         gets(key);                      /* input record key */
  74.  
  75.         if(key[0] == 0) break;          /* terminate if empty line */
  76.  
  77.         inspected = 1;                  /* initialize inspection count */
  78.         i = hashcode(key);              /* calculate hash code */
  79.  
  80.         while(hashtab[i] != -1)         /* inspect datafile records */
  81.         {
  82.             lseek(fhdf, (long) (RSIZE * hashtab[i]), SEEK_SET);
  83.             read(fhdf, rec, RSIZE);     
  84.             
  85.             if(strcmp(rec, key) == 0)   /* if match, we're done */
  86.                 break;
  87.  
  88.             i += HASHINCR;              /* otherwise bump hashcode */
  89.  
  90.             if(i >= HASHSIZE)           /* wrap hashcode if necessary */
  91.                 i -= HASHSIZE;
  92.  
  93.             inspected++;                /* count table inspections */
  94.         }
  95.  
  96.         if(hashtab[i] == -1) printf("\nRecord not found");
  97.         else printf("\nContents of record %d: %s", hashtab[i], rec);
  98.         printf(" --- %d hash table entries inspected", inspected);
  99.     }
  100.  
  101.     close(fhdf);                        /* release data file handle */
  102. }
  103.  
  104.  
  105. /*
  106.     Calculate hash code from supplied ASCII string.  Hash
  107.     code is clamped to the range {0 ... HASHSIZE-1}.  Collisions
  108.     are resolved elsewhere.
  109. */
  110. int hashcode(char *kptr)
  111. {
  112.     int i, j = 0;                       /* scratch variables */
  113.  
  114.                                         /* sum characters of key */
  115.     for(i = 0; i < strlen(kptr); i++) j = (j*2) + kptr[i];
  116.  
  117.     return(j & (HASHSIZE - 1));         /* clamp hash code */
  118. }
  119.  
  120.