home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / vc / pro3 / index.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-12  |  4.8 KB  |  157 lines
  1. ===========================================================================
  2.  BBS: The Abacus * HST/DS * Potterville MI
  3. Date: 05-09-93 (14:13)             Number: 30
  4. From: MARK CORGAN                  Refer#: NONE
  5.   To: ALL                           Recvd: NO  
  6. Subj: INDEX.C                        Conf: (36) C Language
  7. ---------------------------------------------------------------------------
  8. Hello All!
  9.  
  10. The following two mesages are the index and the look-up functions for creating a
  11. nd searching binary trees. INDEX.C creates a binary file from a formatted ascii
  12. file whose format is described in the next message. Each record is stored in alp
  13. habetical order. LOOKUP.C uses the bsearch() function to find a record in the bi
  14. nary file and then prints the information to the screen.
  15.  
  16. This code is hereby donated to the public domain.
  17.  
  18. /* INDEX.C */
  19.  
  20. #include <stdio.h>
  21. #include "defines.h"                  /* definitions for INDEX and LOOKUP */
  22.  
  23. struct tree_node                      /* node in tree */
  24. {
  25.    struct tree_node *l_ptr, *r_ptr;   /* left and right pointers */
  26.    INDEX *data_ptr;                   /* data pointer */
  27. };
  28.  
  29. typedef struct tree_node TREE_NODE;
  30.  
  31. void write_index(void);
  32. void save_tree(TREE_NODE * root, FILE *fp);
  33. TREE_NODE *make_tree(FILE *fp, long *cnt_ptr);
  34. TREE_NODE *insert_tree(TREE_NODE *root, INDEX *rec_ptr, long *cnt_ptr);
  35. FILE *my_fopen(char *file_name, char *mode);
  36. long bsearch(FILE *ifp, long first, long last, char *target);
  37.  
  38. void main(void)
  39. {
  40.    write_index();
  41. }
  42.  
  43. void write_index(void)
  44. {
  45.    FILE *afp, *ifp;                   /* types of files */
  46.    TREE_NODE *root;                   /* index tree */
  47.    static INDEX header = {"!", 0};   /* dummy header node */
  48.  
  49.    afp = my_fopen(ASCII_FILE, "r");
  50.    if((root = make_tree(afp, &header.pos)) != NULL)
  51.    {
  52.       ifp = my_fopen(INDEX_FILE, "wb");
  53.       fwrite((char *) &header, sizeof(header), 1, ifp);
  54.       save_tree(root, ifp);
  55.       fclose(ifp);
  56.       printf("\n%ld records\n", header.pos);
  57.    }
  58.    fclose(afp);
  59. }
  60.  
  61. /* Make index tree */
  62.  
  63. TREE_NODE *make_tree(FILE *fp, long *cnt_ptr) /* file & count of records */
  64. {
  65.    TREE_NODE *root = NULL, *temp_ptr; /* add node to tree */
  66.    char line[MAX_LINE];    /* next line */
  67.    long start_pos = 0;
  68.    INDEX *next_ptr; /* next key, pos pair */
  69.    BOOLEAN new_record = TRUE, have_mem = TRUE; /* starting with new record */
  70.  
  71.    *cnt_ptr = 0;
  72.    while(start_pos = ftell(fp), have_mem && fgets(line,sizeof(line), fp))
  73.    {
  74.       if(new_record)
  75.       {
  76.          if((next_ptr = (INDEX *) malloc(sizeof(INDEX))) != NULL)
  77.          {
  78.             strncpy(next_ptr->key, line, MAX_KEY);
  79.             next_ptr->pos = start_pos;
  80.             if((temp_ptr = insert_tree(root, next_ptr, cnt_ptr)) != NULL)
  81.                root = temp_ptr;
  82.          }
  83.          have_mem = next_ptr && temp_ptr;
  84.       }
  85.       new_record = strcmp(line, END_REC) == 0;
  86.    }
  87.    if(!have_mem)
  88.       fprintf(stderr, "Out of memory. Key: %s\n", line);
  89.    return root;
  90. }
  91.  
  92. /* save the index tree to a file */
  93.  
  94. void save_tree(TREE_NODE *root, FILE *fp)
  95. {
  96.    if(root)
  97.    {
  98.       save_tree(root->l_ptr, fp);
  99.       fwrite(root->data_ptr, sizeof(INDEX), 1, fp);
  100.       save_tree(root->r_ptr, fp);
  101.    }
  102. }
  103.  
  104. /* add record to tree */
  105.  
  106. /* pointer to tree, record to install, nodes in tree */
  107. TREE_NODE *insert_tree(TREE_NODE *root, INDEX *rec_ptr, long *cnt_ptr)
  108. {
  109.    if(root)
  110.    {
  111.       int cmp = strncmp(rec_ptr->key, root->data_ptr->key, MAX_KEY);
  112.  
  113.       if(cmp < 0)   /* left side? */
  114.          root->l_ptr = insert_tree(root->l_ptr, rec_ptr, cnt_ptr);
  115.       else if(cmp > 0)  /* right side */
  116.          root->r_ptr = insert_tree(root->r_ptr, rec_ptr, cnt_ptr);
  117.       else
  118.          fprintf(stderr, "Duplicate key: %s\n", rec_ptr->key);
  119.    }
  120.    else if(root = (TREE_NODE *) malloc(sizeof(TREE_NODE)), root)
  121.    {
  122.       root->data_ptr = rec_ptr;
  123.       root->l_ptr = root->r_ptr = NULL;
  124.       (*cnt_ptr)++;
  125.    }
  126.    return root;
  127. }
  128.  
  129. long bsearch(FILE *ifp, long first, long last, char *target)
  130. {
  131.    long pos, mid =(first + last) / 2;
  132.    INDEX next;
  133.    int cmp;
  134.  
  135.    if(mid < first || fseek(ifp, mid * sizeof(INDEX), 0) != 0 ||
  136.             fread((char *) &next, sizeof(INDEX), 1, ifp) == 0)
  137.       pos = -1;
  138.    else
  139.       pos = ((cmp = strncmp(target, next.key, MAX_KEY)) == 0)
  140.                 ? next.pos
  141.                 : ((cmp < 0) ? bsearch(ifp, first, mid - 1, target)
  142.                              : bsearch(ifp, mid + 1, last, target));
  143.    return pos;
  144. }
  145.  
  146. FILE *my_fopen(char *file_name, char *mode)
  147. {
  148.    FILE *fp = fopen(file_name, mode);
  149.  
  150.    if(!fp)
  151.    {
  152.       fprintf(stderr, "Can't open file \"%s\" for %s\n", file_name,
  153.                       (*mode == 'r')
  154.                            ? "reading"
  155.                            : ((*mode == 'w') ? "writing" : "appending"));
  156.       exit(1);
  157.