Category : Files from Magazines
Archive   : VOL8N7.ZIP
Filename : SRCHIXF.C

 
Output of file : SRCHIXF.C contained in archive : VOL8N7.ZIP
/*
SRCHIXF.C Searches indexed datafile previously created by MAKEIXF.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 the sorted
index file TESTFILE.IX1 (using both sequential and binary
search algorithms) and the binary tree index file
TESTFILE.IX2. If a match is found, the corresponding
record number and contents from TESTFILE.DAT are displayed,
along with the number of index inspections used by each
method.

Each record in TESTFILE.DAT is RSIZE bytes long. The
format of the index files is defined by the constant
KSIZE and by the structures 'index1' and 'index2'.
All these manifest constants and structures must be kept
synchronized with MAKEIXF.C.
*/

#include
#include
#include
#include
#include
#include
#include


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

static int inspected; /* index entries inspected counter */

struct _index1 { /* sorted sequential index */
char key[KSIZE];
int recno; } ;

struct _index2 { /* binary tree index */
char key[KSIZE];
int recno;
int left;
int right; } ;

int binsearch(int, char *, int, int); /* function prototypes */
int seqsearch(int, char *);
int treesearch(int, char *);

main()
{
int i; /* scratch variable */
int fhdf, fhix1, fhix2; /* file handles */
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);
fhix1 = open("TESTFILE.IX1", O_RDONLY | O_BINARY);
fhix2 = open("TESTFILE.IX2", O_RDONLY | O_BINARY);

if((fhdf == -1) || (fhix1 == -1) || (fhix2 == -1))
{
puts("\nMissing data or index 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);

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 index entries counter */

/* perform sequential search of
TESTFILE.IX1, display results */
printf("\nSequential search result: ");
if((i = seqsearch(fhix1, key)) == -1) printf("record not found,");
else printf("record number is %d,", i);
printf(" %d index entries inspected.", inspected);

inspected = 0; /* reset index entries counter */

/* perform binary search of
TESTFILE.IX1, display results */
printf("\nBinary search result: ");
if((i = binsearch(fhix1, key, 0, frecs-1)) == -1)
printf("record not found,");
else printf("record number is %d,", i);
printf(" %d index entries inspected.", inspected);

inspected = 0; /* reset index entries counter */

/* perform binary tree search of
TESTFILE.IX2, display results */
printf("\nBinary tree result: ");
if((i = treesearch(fhix2, key)) == -1) printf("record not found,");
else printf("record number is %d,", i);
printf(" %d index entries inspected.", inspected);

if(i != -1) /* fetch record from main data */
{ /* file and display it */
lseek(fhdf, (long) (i * RSIZE), SEEK_SET);
read(fhdf, rec, RSIZE);
printf("\nContents of record %2d: %s", i, rec);
}
}

close(fhdf); /* release file handles */
close(fhix1);
close(fhix2);
}

/*
Search index file TESTFILE.IX1 sequentially to match the
specified key. Called with a file handle and key address.
Returns the record number for TESTFILE.DAT if match found,
or -1 to indicate no match.
*/
int seqsearch(int fh, char *kptr)
{
int i; /* scratch variable */
struct _index1 index1; /* receives index file data */

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

/* do until end of file found */
while(read(fh, (char *) &index1, sizeof(index1)) != 0)
{
inspected++; /* inspect index entry */
i = strncmp(kptr, index1.key, KSIZE);

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

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

/*
Binary search of TESTFILE.IX1 to match the specified key.
Called with a file handle, key address, and the first
and last record numbers of the index file segment being
inspected. Returns the record number for TESTFILE.DAT
if match found, or -1 to indicate no match.
*/
int binsearch(int fh, char *kptr, int left, int right)
{
int i, j; /* scratch variables */
struct _index1 index1; /* receives index file data */

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

i = (left + right) / 2; /* calculate record number */

inspected++; /* inspect index entry */
lseek(fh, (long) (i * sizeof(index1)), SEEK_SET);
read(fh, (char *) &index1, sizeof(index1));
j = strncmp(kptr, index1.key, KSIZE);

if(j == 0) return(index1.recno); /* 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);
}


/*
Binary tree search of TESTFILE.IX2 to match the specified
key. Called with a file handle and key address. Returns
the record number for TESTFILE.DAT if match found,
or -1 to indicate no match.
*/
int treesearch(int fh, char *kptr)
{
int i; /* scratch variable */
int node = 0; /* current node being inspected */
struct _index2 index2; /* receives index file data */

while(node != -1) /* do until match or empty subtree */
{
inspected++; /* inspect index entry */
lseek(fh, (long) (node * sizeof(index2)), SEEK_SET);
read(fh, (char *) &index2, sizeof(index2));
i = strncmp(kptr, index2.key, KSIZE);

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

if(i < 0) /* else traverse tree */
node = index2.left;
else node = index2.right;
}

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


  3 Responses to “Category : Files from Magazines
Archive   : VOL8N7.ZIP
Filename : SRCHIXF.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/