home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 155_01 / btree0.c < prev    next >
C/C++ Source or Header  |  1990-10-09  |  8KB  |  245 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "btree.h"
  4.  
  5. /* Author: Ray Swartz
  6.  *         Berkeley Decision/Systems, Inc.
  7.  *         P.O. Box 2528
  8.  *         Santa Cruz, Calif. 95063
  9.  * Last Modified: 4/28/85
  10.  *
  11.  * ANY USE OF THESE LIBRARY ROUTINES EITHER PERSONAL OR COMMERCIAL
  12.  * IS ALLOWED UPON THE CONDITION THAT THE USER IDENTIFY THEM
  13.  * AS BEING USED IN THE PROGRAM.  IDENTIFYING INFORMATION MUST
  14.  * APPEAR IN THE PROGRAM DOCUMENTATION OR ON THE TERMINAL SCREEN.
  15.  *
  16.  *         #################################    
  17.  *         # UNATTRIBUTED USE IS FORBIDDEN #
  18.  *         #################################
  19.  *
  20.  *
  21.  *
  22.  * keyfiles are created with a tilde (~) as the first character
  23.  *  in the file, a 2 byte integer (keylength), a 5 byte integer
  24.  *  (next available node), a 5 byte integer (head of the list),
  25.  *  a 5 byte integer (number in the list), and another tilde.
  26.  */
  27.  
  28. /*
  29.  *    Modifier: Honma Michimasa
  30.  */
  31.  
  32. /**** function prot. ***********/
  33. FILE *open_keyfile(char *filename, struct keyinfo *fileinfo);
  34.                /* used to open keyfile */
  35. void close_keyfile(struct keyinfo *fileinfo);
  36.                /* write out header information and close file */
  37. int write_node(long nbr, struct node *nodeinfo, struct keyinfo *fileinfo);
  38.                /* write a node's info to file */
  39. void print_node(struct node *node1);
  40.               /* display contents of a node on screen (debug) */
  41. void push_left_stack(long nbr);
  42.               /* moved left in tree - record this in stack */
  43. void push_right_stack(long nbr);
  44.               /* moved right in tree - record this in stack */
  45. long pop_right_stack();
  46. long pop_left_stack();
  47. void get_node(long nbr, struct node *nodeinfo, struct keyinfo *fileinfo);
  48.               /* read the info stored in node NBR */
  49.  
  50.  
  51.  
  52. FILE *open_keyfile(char *filename, struct keyinfo *fileinfo)   /* used to open keyfile */
  53. /*
  54. char *filename;
  55. struct keyinfo *fileinfo;
  56. */
  57. {
  58.     extern char instr[];
  59.  
  60.     FILE *fopen(), *fd;
  61.     
  62.     if ((fd = fopen(filename,"r+")) != NULL) {  /* file exists */
  63.         fgets(instr, 2, fd);
  64.         if (*instr != 126) {
  65.             BELL
  66.             printf("%s is not a valid key file\n", filename);
  67.             fclose(fd);
  68.             exit(0);
  69.         } 
  70.         fgets(instr, 3, fd);
  71.         fileinfo->keylength = atoi(instr);
  72.         fgets(instr, 6, fd);
  73.         fileinfo->next_avail = atol(instr); 
  74.         fgets(instr, 6, fd);
  75.         fileinfo->list_head = atol(instr); 
  76.         fgets(instr, 6, fd);
  77.         fileinfo->nbr_in_list = atol(instr); 
  78.         fgets(instr, 2, fd);
  79.         if (*instr != 126) {
  80.             BELL
  81.             printf("%s is not a valid key file\n", filename);
  82.             fclose(fd);
  83.             exit(0);
  84.         } 
  85.     }
  86.     else {    /* file doesn't exist - report error */
  87.         BELL
  88.         printf("\n%s not a valid key file", filename);
  89.         exit(0);
  90.     }
  91.     return(fd);
  92. }
  93.  
  94.  
  95.  
  96. void close_keyfile(struct keyinfo *fileinfo)   /* write out header information and close file */
  97. /*
  98. struct keyinfo *fileinfo;
  99. */
  100. {
  101.     fseek(fileinfo->file, 0L, 0);
  102.     fprintf(fileinfo->file,"%c%2d%5ld%5ld%5ld%c",
  103.                 '~',                  /* keyfile token */
  104.                 fileinfo->keylength,
  105.                 fileinfo->next_avail,
  106.                 fileinfo->list_head,
  107.                 fileinfo->nbr_in_list,
  108.                 '~');
  109.     fclose(fileinfo->file);
  110.     return;
  111. }
  112.  
  113. int write_node(long nbr, struct node *nodeinfo, struct keyinfo *fileinfo)   /* write a node's info to file */
  114. /* long nbr;    node to write at */
  115. /* struct node *nodeinfo;   node info to write */
  116. /* struct keyinfo *fileinfo; */
  117. {
  118.     long spot;
  119.     int count;
  120.  
  121.     spot = nbr * (fileinfo->keylength + DATA_LENGTH);
  122.     if (fseek(fileinfo->file, spot, 0) == -1) {  /* error */
  123.         printf("WRITE_NODE: fseek error on node %ld\n", nbr);
  124.         return(NO);
  125.     }
  126.     if (fprintf(fileinfo->file, "%2d%2d%5ld%5ld%5ld",
  127.             nodeinfo->delete_flag,
  128.             nodeinfo->balance,
  129.             nodeinfo->left_link,
  130.             nodeinfo->right_link,
  131.             nodeinfo->rec_nbr) == EOF)
  132.         return(NO);
  133.     for(count = 0; nodeinfo->key[count] != '\0'; count++) /* write out key */
  134.         if (putc(nodeinfo->key[count], fileinfo->file) == EOF)
  135.             return(NO);
  136.     for(; count < fileinfo->keylength; count++)  /* blank fill if necessary */
  137.         if (putc(' ',fileinfo->file) == EOF)
  138.             return(NO);
  139.     return(YES);
  140. }
  141.  
  142. void print_node(struct node *node1)  /* display contents of a node on screen (debug) */
  143. /*
  144. struct node *node1;
  145. */
  146. {
  147.  
  148.     printf("left link: %ld,  right link: %ld\n",
  149.             node1->left_link, node1->right_link);
  150.     printf("key: %s, record nbr: %ld\n",node1->key, node1->rec_nbr);
  151.     printf("balance index: %d\n", node1->balance);
  152.     return;
  153. }
  154.  
  155.  
  156. void push_left_stack(long nbr)  /* moved left in tree - record this in stack */
  157. /*
  158. long nbr;
  159. */
  160. {
  161.     extern int stack_level;
  162.  
  163.     if (++left_history.stack_cntr >= STACK_LENGTH) {
  164.         printf("PUSH_LEFT_STACK: overflow node number: %ld\n", nbr);
  165.         exit(0);
  166.     }
  167.     left_history.element[left_history.stack_cntr] = nbr;
  168.     left_history.level[left_history.stack_cntr] = ++stack_level;
  169.     return;
  170. }
  171.  
  172.  
  173. void push_right_stack(long nbr)  /* moved right in tree - record this in stack */
  174. /*
  175. long nbr;
  176. */
  177. {
  178.     extern int stack_level;
  179.  
  180.     if (++right_history.stack_cntr >= STACK_LENGTH) {
  181.         printf("PUSH_RIGHT_STACK: overflow node number: %ld\n", nbr);
  182.         exit(0);
  183.     }
  184.     right_history.element[right_history.stack_cntr] = nbr;
  185.     right_history.level[right_history.stack_cntr] = ++stack_level;
  186.     return;
  187. }
  188.  
  189.   /* return the next one on the stack and keep left stack at proper level */
  190. long pop_right_stack() 
  191. {
  192.     extern int stack_level;
  193.  
  194. /* pop both to stay at same tree level */
  195.     stack_level = right_history.level[right_history.stack_cntr];
  196.     while(left_history.level[left_history.stack_cntr] > stack_level)
  197.         left_history.stack_cntr--;
  198.     if (right_history.stack_cntr == END)
  199.         return(END);
  200.     stack_level--;
  201.     return(right_history.element[right_history.stack_cntr--]);
  202. }
  203.  
  204.  
  205.   /* return the next one on the stack and keep right stack at proper level */
  206. long pop_left_stack()
  207. {
  208.     extern int stack_level;
  209.  
  210. /* pop both to stay at same tree level */
  211.     stack_level = left_history.level[left_history.stack_cntr];
  212.     while(right_history.level[right_history.stack_cntr] > stack_level)
  213.         right_history.stack_cntr--;
  214.     if (left_history.stack_cntr == END)
  215.         return(END);    
  216.     stack_level--;
  217.     return(left_history.element[left_history.stack_cntr--]);
  218. }
  219.  
  220.  
  221. void get_node(long nbr, struct node *nodeinfo, struct keyinfo *fileinfo)  /* read the info stored in node NBR */
  222. /* long nbr;      node to retrieve */
  223. /* struct node *nodeinfo;    where to store the node's information */
  224. /* struct keyinfo *fileinfo; */
  225. {
  226.     extern char instr[];
  227.  
  228.     long spot;
  229.  
  230.     spot = nbr * (fileinfo->keylength + DATA_LENGTH);
  231.     fseek(fileinfo->file, spot, 0);
  232.     fgets(instr, 3, fileinfo->file);  /* get delete flag */
  233.     nodeinfo->delete_flag = atoi(instr);
  234.     fgets(instr, 3, fileinfo->file);  /* get balance factor */
  235.     nodeinfo->balance = atoi(instr);
  236.     fgets(instr, 6, fileinfo->file);  /* left_link */
  237.     nodeinfo->left_link = atol(instr);
  238.     fgets(instr, 6, fileinfo->file);  /* right_link */
  239.     nodeinfo->right_link = atol(instr);
  240.     fgets(instr, 6, fileinfo->file);
  241.     nodeinfo->rec_nbr = atol(instr);  /* data record number */
  242.     fgets(nodeinfo->key, fileinfo->keylength + 1, fileinfo->file);
  243.     return;
  244. }
  245.