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

 
Output of file : MAKEIXF.C contained in archive : VOL8N7.ZIP
/*
MAKEIXF.C Creates an indexed random access file for use by SRCHIXF.C
Copyright (C) 1989 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 two index files:
TESTFILE.IX1, which is a simple sorted index containing
keys and record numbers, and TESTFILE.IX2, which is a
binary tree index.

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 SRCHIXF.C.
*/

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

#define ISIZE 80 /* max entry length */
#define N_ITEMS 100 /* max number of strings */
#define RSIZE 64 /* fixed record size */
#define KSIZE 8 /* maximum key length */

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

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

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

int getkeys(void); /* function prototypes */
void writedata(int);
void writeindex1(int);
void writeindex2(int);
void treeinsert(int, int);
void dumptree(int);

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

i = getkeys(); /* get record keys from user */
writedata(i); /* write main data file */
writeindex1(i); /* write sequential index */
writeindex2(i); /* write binary tree index */
dumptree(0); /* dump binary tree on screen */
}

/*
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(strncmp(&items[ISIZE * i], &items[ISIZE * j], KSIZE) == 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 sequential index file TESTFILE.IX1, using strings stored
in array 'items'. The index is first built in the structure
'index1' by copying each key to the structure and associating
it with a record number. The index is then sorted and written
to disk.
*/
void writeindex1(recs)
{
int i = 0; /* scratch variable */
int fh; /* handle for index file */

while(i < recs) /* build index entries */
{
strncpy(index1[i].key, &items[ISIZE * i], KSIZE);
index1[i].recno = i;
i++;
}
/* sort the index */
if(recs != 0) qsort(&index1[0], recs, sizeof(index1[0]), strcmp);

/* create sequential index file */
fh = open("TESTFILE.IX1", O_WRONLY|O_CREAT|O_TRUNC|O_BINARY, S_IWRITE);

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

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

for(i = 0; i < recs; i++) /* write the index file */
write(fh, (char *) &index1[i], sizeof(index1[0]));

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

/*
Create binary tree index file TESTFILE.IX2, using strings
stored in array 'items'. The keys are added into the tree
in the order of their original entry, and are associated
with a record number. The index is then written to disk.
*/
void writeindex2(recs)
{
int i = 0; /* scratch variable */
int fh; /* handle for index file */

/* initialize tree head */
memset(&index2[0], 0, sizeof(index2[0])); /* lowest possible key */
index2[0].left = -1; /* link = -1 indicates an */
index2[0].right = -1; /* empty subtree */

while(i < recs) /* build binary tree */
{
treeinsert(i, i+1); /* add new node for current string */
i++; /* and count strings processed */
}
/* create file to hold binary tree */
fh = open("TESTFILE.IX2", O_WRONLY|O_CREAT|O_TRUNC|O_BINARY, S_IWRITE);

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

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

for(i = 0; i < recs+1; i++) /* write tree, including head */
write(fh, (char *) &index2[i], sizeof(index2[0]));

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

/*
Add a new node to the binary tree. Procedure is called with an
index to array 'items' (used to locate the key for the node
being added and as the record number for TESTFILE.DAT) and the
number of the next free node.
*/
void treeinsert(itemno, new)
{
int i, j, node = 0; /* scratch variables */

do /* find tree insertion point */
{
i = node; /* save possible parent node */

/* to choose subtree, compare this
node to key being added */
if((j = strncmp(&items[itemno * ISIZE], index2[node].key, KSIZE)) < 0)
node = index2[node].left;
else node = index2[node].right;

} while (node != -1); /* until empty subtree found */

index2[new].left = -1; /* build a new node; link = -1 */

index2[new].right = -1; /* indicates empty subtree */
index2[new].recno = itemno; /* record no. for main datafile */
strncpy(index2[new].key, &items[itemno * ISIZE], KSIZE);

if(j < 0) index2[i].left = new; /* update parent node link field */
else index2[i].right = new;
}

/*
Debugging routine to dump binary tree nodes in order of keys.
This is just to demonstrate that we are writing a valid and
correctly ordered tree and that there are no wild link fields.
*/
void dumptree(node)
{
if(node != -1) /* ignore empty subtrees */
{
dumptree(index2[node].left); /* display left subtree */

if(node == 0) printf("\nContents of binary tree index:");
else printf("\nNode = %2d, Record no. = %2d, Record key = %.8s",
node, index2[node].recno, index2[node].key);

dumptree(index2[node].right); /* display right subtree */
}
}


  3 Responses to “Category : Files from Magazines
Archive   : VOL8N7.ZIP
Filename : MAKEIXF.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/