home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / PCMAG / VOL8N07.ARC / MAKEIXF.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-01-06  |  9.0 KB  |  255 lines
  1. /*
  2.     MAKEIXF.C   Creates an indexed random access file for use by SRCHIXF.C
  3.     Copyright (C) 1989 Ziff Communications Co.
  4.     PC Magazine * Ray Duncan
  5.  
  6.     The user is prompted to enter from zero to one hundred
  7.     ASCII strings.  These strings are used to build records
  8.     in the main data file TESTFILE.DAT and two index files:
  9.     TESTFILE.IX1, which is a simple sorted index containing
  10.     keys and record numbers, and TESTFILE.IX2, which is a
  11.     binary tree index.
  12.  
  13.     Each record in TESTFILE.DAT is RSIZE bytes long.  The 
  14.     format of the index files is defined by the constant
  15.     KSIZE and by the structures 'index1' and 'index2'.  
  16.     All these manifest constants and structures must be kept 
  17.     synchronized with SRCHIXF.C.
  18. */
  19.  
  20. #include <stdio.h>
  21. #include <string.h>
  22. #include <stdlib.h>
  23. #include <fcntl.h>
  24. #include <sys\types.h>
  25. #include <sys\stat.h>
  26. #include <io.h>
  27.  
  28. #define ISIZE   80                      /* max entry length */
  29. #define N_ITEMS 100                     /* max number of strings */
  30. #define RSIZE   64                      /* fixed record size */
  31. #define KSIZE    8                      /* maximum key length */
  32.  
  33. char items[N_ITEMS * ISIZE];            /* original entries stored here */
  34.  
  35. struct _index1 {                        /* sorted sequential index */
  36.       char key[KSIZE];
  37.       int recno;
  38.     } index1[N_ITEMS] ;
  39.     
  40. struct _index2 {                        /* binary tree index */
  41.       char key[KSIZE];
  42.       int recno;
  43.       int left;
  44.       int right;
  45.     } index2[N_ITEMS + 1] ;
  46.  
  47. int getkeys(void);                      /* function prototypes */
  48. void writedata(int);
  49. void writeindex1(int);
  50. void writeindex2(int);
  51. void treeinsert(int, int);
  52. void dumptree(int);
  53.  
  54. main()
  55. {
  56.     int i;                              /* number of record keys entered */
  57.  
  58.     i = getkeys();                      /* get record keys from user */
  59.     writedata(i);                       /* write main data file */
  60.     writeindex1(i);                     /* write sequential index */
  61.     writeindex2(i);                     /* write binary tree index */
  62.     dumptree(0);                        /* dump binary tree on screen */
  63. }
  64.  
  65. /*
  66.     Get record keys from user, leave them in array 'items',
  67.     return number of keys to caller.
  68. */
  69. int getkeys(void)
  70. {
  71.     int i, j;                           /* scratch variables */
  72.  
  73.     puts("\nEnter keys for file records...");
  74.  
  75.     i = 0;                              /* initialize string count */
  76.  
  77.     while(i < N_ITEMS)                  /* enforce maximum entries */
  78.     {
  79.         printf("%2d: ", i+1);           /* prompt user for next string */
  80.         gets(&items[ISIZE * i]);        /* read keyboard, store in array */
  81.  
  82.                                         /* last entry if empty line */
  83.         if(items[ISIZE * i] == 0) break;
  84.  
  85.         for(j = 0; j < i; j++)          /* make sure not duplicate key */
  86.         {
  87.             if(strncmp(&items[ISIZE * i], &items[ISIZE * j], KSIZE) == 0)
  88.                 break;                  /* exit loop if duplicate found */
  89.         }
  90.  
  91.         if(i == j) i++;                 /* count non-duplicate strings */
  92.         else puts("Duplicate key, try again.");
  93.     }
  94.  
  95.     return (i);                         /* return no. of keys entered */
  96. }
  97.  
  98. /*
  99.     Create main data file TESTFILE.DAT, using strings stored 
  100.     in array 'items'.
  101. */
  102. void writedata(recs)
  103. {
  104.     int i = 0;                          /* scratch variable */
  105.     int fh;                             /* handle for output file */
  106.     char recbuf[RSIZE];                 /* scratch record buffer */
  107.  
  108.                                         /* create main data file */
  109.     fh = open("TESTFILE.DAT", O_WRONLY|O_CREAT|O_TRUNC|O_BINARY, S_IWRITE);
  110.  
  111.     if(fh == -1)                        /* terminate if create failed */
  112.     {
  113.         puts("\nCan't create TESTFILE.DAT.");
  114.         exit(1);
  115.     }
  116.  
  117.     puts("\nWriting TESTFILE.DAT...");
  118.  
  119.     while(i < recs)                     /* build and write records */
  120.     {                              
  121.         memset(recbuf, 0, RSIZE);
  122.         strncpy(recbuf, &items[ISIZE * i], RSIZE);
  123.         write(fh, recbuf, RSIZE);
  124.         i++;
  125.     }
  126.  
  127.     close(fh);                          /* release file handle */
  128. }
  129.  
  130. /*
  131.     Create sequential index file TESTFILE.IX1, using strings stored 
  132.     in array 'items'.  The index is first built in the structure 
  133.     'index1' by copying each key to the structure and associating 
  134.     it with a record number.  The index is then sorted and written 
  135.     to disk.
  136. */
  137. void writeindex1(recs)
  138. {
  139.     int i = 0;                          /* scratch variable */
  140.     int fh;                             /* handle for index file */
  141.  
  142.     while(i < recs)                     /* build index entries */
  143.     {                              
  144.         strncpy(index1[i].key, &items[ISIZE * i], KSIZE);
  145.         index1[i].recno = i;
  146.         i++;               
  147.     }
  148.                                         /* sort the index */
  149.     if(recs != 0) qsort(&index1[0], recs, sizeof(index1[0]), strcmp);
  150.  
  151.                                         /* create sequential index file */
  152.     fh = open("TESTFILE.IX1", O_WRONLY|O_CREAT|O_TRUNC|O_BINARY, S_IWRITE);
  153.  
  154.     if(fh == -1)                        /* terminate if create failed */
  155.     {
  156.         puts("\nCan't create TESTFILE.IX1.");
  157.         exit(1);
  158.     }
  159.  
  160.     puts("\nWriting TESTFILE.IX1...");
  161.  
  162.     for(i = 0; i < recs; i++)           /* write the index file */
  163.         write(fh, (char *) &index1[i], sizeof(index1[0]));
  164.  
  165.     close(fh);                          /* release handle */
  166. }
  167.  
  168. /*
  169.     Create binary tree index file TESTFILE.IX2, using strings 
  170.     stored in array 'items'.  The keys are added into the tree
  171.     in the order of their original entry, and are associated
  172.     with a record number.  The index is then written to disk.
  173. */
  174. void writeindex2(recs)
  175. {
  176.     int i = 0;                          /* scratch variable */
  177.     int fh;                             /* handle for index file */
  178.  
  179.                                         /* initialize tree head */
  180.     memset(&index2[0], 0, sizeof(index2[0]));   /* lowest possible key */
  181.     index2[0].left = -1;                /* link = -1 indicates an */
  182.     index2[0].right = -1;               /* empty subtree */
  183.  
  184.     while(i < recs)                     /* build binary tree */
  185.     {                              
  186.         treeinsert(i, i+1);             /* add new node for current string */
  187.         i++;                            /* and count strings processed */
  188.     }
  189.                                         /* create file to hold binary tree */
  190.     fh = open("TESTFILE.IX2", O_WRONLY|O_CREAT|O_TRUNC|O_BINARY, S_IWRITE);
  191.  
  192.     if(fh == -1)                        /* terminate if create failed */
  193.     {
  194.         puts("\nCan't create TESTFILE.IX2.");
  195.         exit(1);
  196.     }
  197.  
  198.     puts("\nWriting TESTFILE.IX2...");
  199.  
  200.     for(i = 0; i < recs+1; i++)         /* write tree, including head */
  201.         write(fh, (char *) &index2[i], sizeof(index2[0]));
  202.  
  203.     close(fh);                          /* release handle */
  204. }
  205.  
  206. /*
  207.     Add a new node to the binary tree.  Procedure is called with an 
  208.     index to array 'items' (used to locate the key for the node 
  209.     being added and as the record number for TESTFILE.DAT) and the
  210.     number of the next free node.
  211. */
  212. void treeinsert(itemno, new)
  213. {
  214.     int i, j, node = 0;                 /* scratch variables */
  215.  
  216.     do                                  /* find tree insertion point */
  217.     {
  218.         i = node;                       /* save possible parent node */
  219.  
  220.                                         /* to choose subtree, compare this
  221.                                            node to key being added */
  222.         if((j = strncmp(&items[itemno * ISIZE], index2[node].key, KSIZE)) < 0)
  223.              node = index2[node].left;
  224.         else node = index2[node].right;
  225.  
  226.     } while (node != -1);               /* until empty subtree found */
  227.  
  228.     index2[new].left = -1;              /* build a new node; link = -1 */
  229.     index2[new].right = -1;             /* indicates empty subtree */
  230.     index2[new].recno = itemno;         /* record no. for main datafile */
  231.     strncpy(index2[new].key, &items[itemno * ISIZE], KSIZE);
  232.  
  233.     if(j < 0) index2[i].left = new;     /* update parent node link field */
  234.     else  index2[i].right = new;
  235. }
  236.  
  237. /*
  238.     Debugging routine to dump binary tree nodes in order of keys.
  239.     This is just to demonstrate that we are writing a valid and
  240.     correctly ordered tree and that there are no wild link fields.
  241. */
  242. void dumptree(node)
  243. {
  244.     if(node != -1)                      /* ignore empty subtrees */
  245.     {
  246.         dumptree(index2[node].left);    /* display left subtree */
  247.  
  248.         if(node == 0) printf("\nContents of binary tree index:");
  249.         else printf("\nNode = %2d, Record no. = %2d, Record key = %.8s", 
  250.                     node, index2[node].recno, index2[node].key);
  251.  
  252.         dumptree(index2[node].right);   /* display right subtree */
  253.     }                                   
  254. }
  255.