home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 155_01 / btree.c < prev    next >
C/C++ Source or Header  |  1990-10-09  |  24KB  |  663 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <alloc.h>
  4. #include "btree.h"
  5. #include "beeprot.h"
  6.  
  7. /* Author: Ray Swartz
  8.  *         Berkeley Decision/Systems, Inc.
  9.  *         P.O. Box 2528
  10.  *         Santa Cruz, Calif. 95063
  11.  * Last Modified: 4/28/85
  12.  *
  13.  * ANY USE OF THESE LIBRARY ROUTINES EITHER PERSONAL OR COMMERCIAL
  14.  * IS ALLOWED UPON THE CONDITION THAT THE USER IDENTIFY THEM
  15.  * AS BEING USED IN THE PROGRAM.  IDENTIFYING INFORMATION MUST
  16.  * APPEAR IN THE PROGRAM DOCUMENTATION OR ON THE TERMINAL SCREEN.
  17.  *
  18.  *         #################################    
  19.  *         # UNATTRIBUTED USE IS FORBIDDEN #
  20.  *         #################################
  21.  *
  22.  * The insert routine was directly translated from the algorithm
  23.  *  in D. Knuth's Volume 3 of The Art of Computer Programming
  24.  *  (Sorting and Searching) pages 455 - 457.  Single letter
  25.  *  variables (p, q, r, s) are used to make the algorithm steps
  26.  *  more obvious.
  27.  */
  28. /*
  29.  *    Modifier: Honma Michimasa
  30.  */
  31.  
  32. STACK right_history, left_history;
  33. int stack_level;   /* tree level at present */
  34. char instr[256];   /* general string input */
  35.  
  36.  
  37. int insert(char *argkey, long recnbr, struct keyinfo *fileinfo) /* insert key (argkey) into tree */
  38. /* struct keyinfo *fileinfo;  file to insert key into */
  39. /* char *argkey;     key to insert */
  40. /* long recnbr;      record number of corresponding data record */
  41. {
  42.     static long top;  /* where balancing will have to take place, if at all */
  43.     static long p_rec;
  44.     static long s_rec;
  45.     static long q_rec;
  46.     static long r_rec;
  47.     static struct node q_node, s_node, r_node, p_node;
  48.     static int alloc_flag = NO;  /* flag for pointer space allocation */
  49.     int compare;   /* holds key comparison values */
  50.     
  51.     if (fileinfo->next_avail >= MAX_NODES) {
  52.         printf("Only %d nodes allowed in a keyfile\n");
  53.         exit(1);
  54.     }
  55.     if(alloc_flag == NO) {   /* set up key pointers in node structures  */
  56.         q_node.key = malloc(fileinfo->keylength + 1); /* first call to */
  57.         s_node.key = malloc(fileinfo->keylength + 1); /* insert function */
  58.         p_node.key = malloc(fileinfo->keylength + 1);
  59.         r_node.key = malloc(fileinfo->keylength + 1);
  60.         alloc_flag = YES;
  61.     }
  62.     if (fileinfo->list_head == 0) {   /* no records in list */
  63.         fileinfo->list_head = 1;  /* insert key as head of list */
  64.         p_node.balance = p_node.right_link = p_node.left_link = 0;
  65.         p_node.delete_flag = NO;
  66.         p_node.rec_nbr = recnbr;
  67.         strcpy(p_node.key, argkey);
  68.         write_node(1L, &p_node, fileinfo);
  69.         fileinfo->next_avail++;
  70.         fileinfo->nbr_in_list++;
  71.         return(YES);
  72.     }
  73.     top = TOP;    /* initialize to see if list head changes */
  74.     p_rec = fileinfo->list_head;   /* Step A1 (find spot to insert) */
  75.     s_rec = fileinfo->list_head;
  76.     while(1) {
  77.         get_node(p_rec, &p_node, fileinfo);
  78.         if ((compare = strcmp(argkey, p_node.key)) < 0) {  /* Step A2 */
  79.             q_rec = p_node.left_link;  /* Step A3 (move left) */
  80.             if (q_rec == END) {  /* insert here */
  81.                 q_rec = fileinfo->next_avail++;
  82.                 p_node.left_link = q_rec;
  83.                 break;  /* loop exit */
  84.             }
  85.             else {  /* look again from this node */
  86.                 get_node(q_rec, &q_node, fileinfo);
  87.                 if (q_node.balance != 0) {
  88.                     top = p_rec;
  89.                     s_rec = q_rec;
  90.                 }
  91.             }
  92.             p_rec = q_rec;
  93.         }
  94.         else  {  /* Step A4 (move right) */
  95.             q_rec = p_node.right_link;
  96.             if (q_rec == END) {  /* insert here */
  97.                 q_rec = fileinfo->next_avail++;
  98.                 p_node.right_link = q_rec;
  99.                 break;  /* loop exit */
  100.             }
  101.             else {  /* look again from this node */
  102.                 get_node(q_rec, &q_node, fileinfo);
  103.                 if (q_node.balance != 0) {
  104.                     top = p_rec;
  105.                     s_rec = q_rec;
  106.                 }
  107.                 p_rec = q_rec;
  108.             }
  109.         }
  110.     } /* end of while loop */
  111. /* Step 5 (insert key at q_node) */      
  112.     q_node.left_link = q_node.right_link = END;
  113.     q_node.balance = 0;
  114.     q_node.delete_flag = NO;
  115.     q_node.rec_nbr = recnbr;
  116.     strcpy(q_node.key, argkey);
  117.     if (write_node(q_rec, &q_node, fileinfo) == NO)
  118.         return(NO);  /* write failed */
  119.     write_node(p_rec, &p_node, fileinfo);
  120.     get_node(s_rec, &s_node, fileinfo); /* Step A6 (adjust balance factors) */
  121.     if (strcmp(argkey, s_node.key) < 0)
  122.         r_rec = p_rec = s_node.left_link;
  123.     else
  124.         r_rec = p_rec = s_node.right_link;
  125.     while (p_rec != q_rec) {
  126.         get_node(p_rec, &p_node, fileinfo);
  127.         if(strcmp(argkey, p_node.key) < 0) {
  128.             p_node.balance = -1;
  129.             write_node(p_rec, &p_node, fileinfo);
  130.             p_rec = p_node.left_link;
  131.         }
  132.         else {
  133.             p_node.balance = 1;
  134.             write_node(p_rec, &p_node, fileinfo);
  135.             p_rec = p_node.right_link;
  136.         }
  137.     }
  138.     compare = (strcmp(argkey, s_node.key) < 0) ? -1 : 1; /* Step A7 */
  139.     if (s_node.balance == 0) {  /* Step A7i */
  140.         fileinfo->nbr_in_list++;
  141.         s_node.balance = compare;
  142.         write_node(s_rec, &s_node, fileinfo);
  143.         return(YES);
  144.     }
  145.     else if(s_node.balance == -compare) {  /* Step A7ii */
  146.         fileinfo->nbr_in_list++;
  147.         s_node.balance = 0;
  148.         write_node(s_rec, &s_node, fileinfo);
  149.         return(YES);
  150.     }
  151.     else { /* Step A7iii (tree out of balance) */
  152.         fileinfo->nbr_in_list++;
  153.         get_node(s_rec, &s_node, fileinfo);
  154.         get_node(r_rec, &r_node, fileinfo);
  155.         if (r_node.balance == compare) { /* Step A8 (single rotate) */
  156.             p_rec = r_rec;
  157.             link(compare, &s_node, -compare, &r_node);
  158.             link_nbr(-compare, &r_node, s_rec);
  159.             s_node.balance = r_node.balance = 0;
  160.         }
  161.         else {   /* Step A9 (double rotate) */
  162.             nbr_link(&p_rec, -compare, &r_node);
  163.             get_node(p_rec, &p_node, fileinfo);
  164.             link(-compare, &r_node, compare, &p_node);
  165.             link_nbr(compare, &p_node, r_rec);
  166.             link(compare, &s_node, -compare, &p_node);
  167.             link_nbr(-compare, &p_node, s_rec);
  168.             node_bal(compare, &p_node, &s_node, &r_node);
  169.             p_node.balance = 0;
  170.             write_node(p_rec, &p_node, fileinfo);
  171.         }
  172.         if (top == TOP)  /* Step A10 */ 
  173.             fileinfo->list_head = p_rec; /* balanced at list head */ 
  174.         else {   /* balanced at top of a sub-tree */
  175.             get_node(top, &q_node, fileinfo); 
  176.             if (s_rec == q_node.right_link)
  177.                 q_node.right_link = p_rec; 
  178.             else
  179.                 q_node.left_link = p_rec;
  180.             write_node(top, &q_node, fileinfo);
  181.         }
  182.         write_node(s_rec, &s_node, fileinfo);
  183.         write_node(r_rec, &r_node, fileinfo);
  184.         return(YES);
  185.     }
  186. }
  187.  
  188.  
  189. void link(int alpha1, struct node *node1, int alpha2, struct node *node2)
  190. /*
  191. int alpha1, alpha2;
  192. struct node *node1, *node2;
  193. */
  194. {
  195.     /* see definition of LINK(a, P) on Knuth pg. 455 (Vol. 3) */
  196.       
  197.     if (alpha1 == -1 && alpha2 == -1)
  198.         node1->left_link = node2->left_link;
  199.     else if(alpha1 == -1 && alpha2 == 1)
  200.         node1->left_link = node2->right_link;
  201.     else if(alpha1 == 1 && alpha2 == -1)
  202.         node1->right_link = node2->left_link;
  203.     else
  204.         node1->right_link = node2->right_link;
  205. }
  206.  
  207.  
  208. void nbr_link(long *nbr, int alpha, struct node *node1) /* set a record number according to alpha */
  209. /*
  210. long *nbr;
  211. int alpha;
  212. struct node *node1;
  213. */
  214. {
  215.     *nbr = (alpha == 1) ? node1->right_link : node1->left_link;
  216. }
  217.  
  218. void link_nbr(int alpha, struct node *node1, long nbr) /* set a link according to alpha */
  219. /*
  220. int alpha;
  221. struct node *node1;
  222. long nbr;
  223. */
  224. {
  225.  
  226.     if (alpha == 1)
  227.         node1->right_link = nbr;
  228.     else
  229.         node1->left_link = nbr;
  230. }
  231.  
  232. void node_bal(int alpha, struct node *node1, struct node *node2, struct node *node3)  /* node balancing in Step A9 */
  233. /*
  234. int alpha;
  235. struct node *node1, *node2, *node3;
  236. */
  237. {
  238.  
  239.     if (node1->balance == alpha) {
  240.         node2->balance = -alpha;
  241.         node3->balance = 0;
  242.     } 
  243.     else if(node1->balance == 0)
  244.         node2->balance = node3->balance = 0;
  245.     else {
  246.         node2->balance = 0;
  247.         node3->balance = alpha;
  248.     }
  249. }
  250.  
  251.  
  252. void delete_key(long node_nbr, struct node *current_node, struct keyinfo *fileinfo)
  253. /* long node_nbr;   node to delete */
  254. /* struct node *current_node;   deleted node's information */
  255. /* struct keyinfo *fileinfo;   keyfile */
  256. {
  257.     if (node_nbr == END)
  258.         printf("DELETE: can't delete node 0\n");
  259.     else {
  260.         current_node->delete_flag = YES;
  261.         if (write_node(node_nbr, current_node, fileinfo) == NO)
  262.             print_msg("DELETE: write_node returned NO");
  263.         else
  264.             fileinfo->nbr_in_list--;
  265.     }
  266. }
  267.  
  268.  
  269.  
  270. int get_next(long *node_nbr, struct node *current_node, struct keyinfo *fileinfo)  /* retrieve next higher node */
  271. /* struct keyfile(keyinfo ?) *fileinfo; */
  272. /* struct node *current_node;   where to store node's info */
  273. /* long *node_nbr;     node to retrieve */
  274. {
  275.     long search_node;
  276.    
  277.     search_node = *node_nbr;
  278.     if (*node_nbr == END) {   /* undefined current node */
  279.          print_msg("Must FIND a record first\n");
  280.          return(NO);
  281.     }
  282.     do {
  283.         if(current_node->right_link == END) {  /* can't move right */
  284.             if(left_history.stack_cntr == END) { /* none in stack */
  285.                 /* node_nbr at end of non-deleted elements - retreive it */
  286.                 get_node(*node_nbr, current_node, fileinfo);
  287.                 return(AT_END);
  288.             }
  289.             else {    /* can't go right & stack full (pop stack) */
  290.                 search_node = pop_left_stack();
  291.                 get_node(search_node, current_node, fileinfo);
  292.             }  
  293.         }
  294.         else {  /* move right */
  295.             push_right_stack(search_node);
  296.             search_node = current_node->right_link;
  297.             get_node(search_node, current_node, fileinfo);
  298.             while(current_node->left_link != END) { /* bottom left */
  299.                 push_left_stack(search_node);
  300.                 search_node = current_node->left_link; /* of this sub-tree */
  301.                 get_node(search_node, current_node, fileinfo);
  302.             }
  303.         }
  304.     } while (current_node->delete_flag == YES);
  305.     *node_nbr = search_node;
  306.     return(YES);
  307. }
  308.  
  309.  
  310.  
  311. int find_key(char *key1, long *node_nbr, struct node *current_node, struct keyinfo *fileinfo) /* locate a key */
  312. /* char *key1;   key to find */
  313. /* struct keyinfo *fileinfo;  */
  314. /* long *node_nbr;  number of "found" node */
  315. /* struct node *current_node;   where "found" node is stored */
  316. {
  317.     int direction;   /* flag to determine moving right or left */
  318.     long search_node; /* node presently being searched */
  319.  
  320. /* initalize stacks to empty */
  321.     right_history.stack_cntr = left_history.stack_cntr = END;
  322.     right_history.element[END] = left_history.element[END] = END;
  323.     stack_level = 0;   /* tree level at start of search */
  324.     search_node = fileinfo->list_head;  /* begin at list head */
  325.     get_node(search_node, current_node, fileinfo);
  326.     while((direction = strcmp(key1, current_node->key)) != 0 ||
  327.            current_node->delete_flag == YES) {
  328.         if (direction > 0) { /* search to right */
  329.             if (current_node->right_link != END) { 
  330.                 push_right_stack(search_node); /* not found, more to see */
  331.                 search_node = current_node->right_link;
  332.                 get_node(search_node, current_node, fileinfo);
  333.             }
  334.             else if(current_node->delete_flag == YES) { /* node deleted */
  335.               /* skip all deleted nodes */
  336.                 while(current_node->delete_flag == YES) { 
  337.                    if(get_next(&search_node,current_node,fileinfo) == AT_END){
  338.                         get_previous(&search_node, current_node, fileinfo);
  339.                         *node_nbr = search_node;      
  340.                         return(NOT_FOUND);
  341.                    }
  342.                 }
  343.                 *node_nbr = search_node;
  344.                 return(NOT_FOUND);
  345.             }
  346.             else {  /* at end of a branch */
  347.                 *node_nbr = search_node;
  348.                 return(NOT_FOUND);
  349.             }
  350.         }   
  351.         else {  /* search to left */
  352.             if (current_node->left_link != END) {
  353.                 push_left_stack(search_node); 
  354.                 search_node = current_node->left_link;
  355.                 get_node(search_node, current_node, fileinfo);
  356.             }                         
  357.             else if(current_node->delete_flag == YES) { /* left = END */
  358.                 while(current_node->delete_flag == YES) {
  359.                  if (get_next(&search_node,current_node,fileinfo)==AT_END) {
  360.                        get_previous(&search_node, current_node, fileinfo);
  361.                        *node_nbr = search_node;     
  362.                        return(NOT_FOUND);
  363.                    }
  364.                 }
  365.                 *node_nbr = search_node;
  366.                 return(NOT_FOUND);
  367.             }   
  368.             else {
  369.                 *node_nbr = search_node;
  370.                 return(NOT_FOUND);
  371.             }
  372.         }
  373.     }  /* end of search while loop */
  374.     return(YES);  /* exact match and not deleted only */
  375. }
  376.  
  377. int get_first(long *node_nbr, struct node *current_node, struct keyinfo *fileinfo)
  378. /*** added function  ****/
  379. {
  380.     int direction;   /* flag to determine moving right or left */
  381.     long search_node; /* node presently being searched */
  382.  
  383. /* initalize stacks to empty */
  384.     right_history.stack_cntr = left_history.stack_cntr = END;
  385.     right_history.element[END] = left_history.element[END] = END;
  386.     stack_level = 0;   /* tree level at start of search */
  387.     search_node = fileinfo->list_head;  /* begin at list head */
  388.     get_node(search_node, current_node, fileinfo);
  389.     while(current_node->left_link != END) {
  390.          push_left_stack(search_node); /* not found, more to see */
  391.          search_node = current_node->left_link;
  392.          get_node(search_node, current_node, fileinfo);
  393.     }
  394.     if(current_node->delete_flag == YES) { /* left = END */
  395.         /* skip all deleted nodes */
  396.          while(current_node->delete_flag == YES) {
  397.              if (get_next(&search_node,current_node,fileinfo)==AT_END) {
  398.                     get_previous(&search_node, current_node, fileinfo);
  399.                     *node_nbr = search_node;     
  400.                     return(YES);
  401.              }
  402.          }
  403.          *node_nbr = search_node;
  404.          return(YES);
  405.     }
  406.     *node_nbr = search_node;
  407.     return(YES);
  408. }
  409.  
  410. int get_last(long *node_nbr, struct node *current_node, struct keyinfo *fileinfo)
  411. /*** added function  ****/
  412. {
  413.     int direction;   /* flag to determine moving right or left */
  414.     long search_node; /* node presently being searched */
  415.  
  416. /* initalize stacks to empty */
  417.     right_history.stack_cntr = left_history.stack_cntr = END;
  418.     right_history.element[END] = left_history.element[END] = END;
  419.     stack_level = 0;   /* tree level at start of search */
  420.     search_node = fileinfo->list_head;  /* begin at list head */
  421.     get_node(search_node, current_node, fileinfo);
  422.     while(current_node->right_link != END) {
  423.         push_right_stack(search_node); /* not found, more to see */
  424.         search_node = current_node->right_link;
  425.         get_node(search_node, current_node, fileinfo);
  426.     }
  427.     if(current_node->delete_flag == YES) { /* node deleted */
  428.         /* skip all deleted nodes */
  429.          while(current_node->delete_flag == YES) { 
  430.              if(get_next(&search_node,current_node,fileinfo) == AT_END){
  431.                    get_previous(&search_node, current_node, fileinfo);
  432.                    *node_nbr = search_node;      
  433.                    return(YES);
  434.               }
  435.          }
  436.          *node_nbr = search_node;
  437.          return(YES);
  438.     }
  439.     *node_nbr = search_node;
  440.     return(YES); 
  441. }
  442.  
  443. int get_previous(long *node_nbr, struct node *current_node, struct keyinfo *fileinfo)
  444. /*
  445. long *node_nbr;
  446. struct node *current_node;
  447. struct keyinfo *fileinfo;
  448. */
  449. {
  450.     long search_node;
  451.  
  452.     search_node = *node_nbr;
  453.     if (*node_nbr == END) {   /* undefined current node */
  454.         print_msg("Must FIND a record first\n");
  455.         return(NO);
  456.     }
  457.     do {
  458.         if(current_node->left_link == END) {  /* can't move left */
  459.             if(right_history.stack_cntr == END) { /* none in stack */
  460.                 /* node_nbr at end of non-deleted elements - retreive it */
  461.                 get_node(*node_nbr, current_node, fileinfo);
  462.                 return(AT_END);  /* don't reset node_nbr */
  463.             }
  464.             else {    /* can't go left & stack full (pop stack) */
  465.                 search_node = pop_right_stack();
  466.                 get_node(search_node, current_node, fileinfo);
  467.             }  
  468.         }
  469.         else {  /* move left then to bottom right - this is previous one */
  470.             push_left_stack(search_node);
  471.             search_node = current_node->left_link;
  472.             get_node(search_node, current_node, fileinfo);
  473.             while(current_node->right_link != END) { /* bottom right */
  474.                 push_right_stack(search_node);       /* of this sub-tree */
  475.                 search_node = current_node->right_link;
  476.                 get_node(search_node, current_node, fileinfo);
  477.             }
  478.         }
  479.     } while (current_node->delete_flag == YES);
  480.     *node_nbr = search_node;   /* set node_nbr to previous node found */    
  481.     return(YES);
  482. }
  483.  
  484.  
  485. FILE *open_keyfile(char *filename, struct keyinfo *fileinfo)   /* used to open keyfile */
  486. /*
  487. char *filename;
  488. struct keyinfo *fileinfo;
  489. */
  490. {
  491.  
  492.     FILE  *fd;
  493.     
  494.     if ((fd = fopen(filename,"r+")) != NULL) {  /* file exists */
  495.         fgets(instr, 2, fd);
  496.         if (*instr != 126) {
  497.             BELL
  498.             printf("%s is not a valid key file\n", filename);
  499.             fclose(fd);
  500.             exit(0);
  501.         } 
  502.         fgets(instr, 3, fd);
  503.         fileinfo->keylength = atoi(instr);
  504.         fgets(instr, 6, fd);
  505.         fileinfo->next_avail = atol(instr); 
  506.         fgets(instr, 6, fd);
  507.         fileinfo->list_head = atol(instr); 
  508.         fgets(instr, 6, fd);
  509.         fileinfo->nbr_in_list = atol(instr); 
  510.         fgets(instr, 2, fd);
  511.         if (*instr != 126) {
  512.             BELL
  513.             printf("%s is not a valid key file\n", filename);
  514.             fclose(fd);
  515.             exit(0);
  516.         } 
  517.     }
  518.     else {    /* file doesn't exist - report error */
  519.         BELL
  520.         printf("\n%s not a valid key file", filename);
  521.         exit(0);
  522.     }
  523.     return(fd);
  524. }
  525.  
  526.  
  527.  
  528. void close_keyfile(struct keyinfo *fileinfo)   /* write out header information and close file */
  529. /*
  530. struct keyinfo *fileinfo;
  531. */
  532. {
  533.     fseek(fileinfo->file, 0L, 0);
  534.     fprintf(fileinfo->file,"%c%2d%5ld%5ld%5ld%c",
  535.                 '~',                  /* keyfile token */
  536.                 fileinfo->keylength,
  537.                 fileinfo->next_avail,
  538.                 fileinfo->list_head,
  539.                 fileinfo->nbr_in_list,
  540.                 '~');
  541.     fclose(fileinfo->file);
  542. }
  543.  
  544. int write_node(long nbr, struct node *nodeinfo, struct keyinfo *fileinfo)   /* write a node's info to file */
  545. /* long nbr;    node to write at */
  546. /* struct node *nodeinfo;   node info to write */
  547. /* struct keyinfo *fileinfo; */
  548. {
  549.     long spot;
  550.     int count;
  551.  
  552.     spot = nbr * (fileinfo->keylength + DATA_LENGTH);
  553.     if (fseek(fileinfo->file, spot, 0) == -1) {  /* error */
  554.         printf("WRITE_NODE: fseek error on node %ld\n", nbr);
  555.         return(NO);
  556.     }
  557.     if (fprintf(fileinfo->file, "%2d%2d%5ld%5ld%5ld",
  558.             nodeinfo->delete_flag,
  559.             nodeinfo->balance,
  560.             nodeinfo->left_link,
  561.             nodeinfo->right_link,
  562.             nodeinfo->rec_nbr) == EOF)
  563.         return(NO);
  564.     for(count = 0; nodeinfo->key[count] != '\0'; count++) /* write out key */
  565.         if (putc(nodeinfo->key[count], fileinfo->file) == EOF)
  566.             return(NO);
  567.     for(; count < fileinfo->keylength; count++)  /* blank fill if necessary */
  568.         if (putc(' ',fileinfo->file) == EOF)
  569.             return(NO);
  570.     return(YES);
  571. }
  572.  
  573. void print_node(struct node *node1)  /* display contents of a node on screen (debug) */
  574. /*
  575. struct node *node1;
  576. */
  577. {
  578.  
  579.     printf("left link: %ld,  right link: %ld\n",
  580.             node1->left_link, node1->right_link);
  581.     printf("key: %s, record nbr: %ld\n",node1->key, node1->rec_nbr);
  582.     printf("balance index: %d\n", node1->balance);
  583. }
  584.  
  585.  
  586. void push_left_stack(long nbr)  /* moved left in tree - record this in stack */
  587. /*
  588. long nbr;
  589. */
  590. {
  591.  
  592.     if (++left_history.stack_cntr >= STACK_LENGTH) {
  593.         printf("PUSH_LEFT_STACK: overflow node number: %ld\n", nbr);
  594.         exit(0);
  595.     }
  596.     left_history.element[left_history.stack_cntr] = nbr;
  597.     left_history.level[left_history.stack_cntr] = ++stack_level;
  598. }
  599.  
  600.  
  601. void push_right_stack(long nbr)  /* moved right in tree - record this in stack */
  602. /*
  603. long nbr;
  604. */
  605. {
  606.     if (++right_history.stack_cntr >= STACK_LENGTH) {
  607.         printf("PUSH_RIGHT_STACK: overflow node number: %ld\n", nbr);
  608.         exit(0);
  609.     }
  610.     right_history.element[right_history.stack_cntr] = nbr;
  611.     right_history.level[right_history.stack_cntr] = ++stack_level;
  612. }
  613.  
  614.   /* return the next one on the stack and keep left stack at proper level */
  615. long pop_right_stack() 
  616. {
  617. /* pop both to stay at same tree level */
  618.     stack_level = right_history.level[right_history.stack_cntr];
  619.     while(left_history.level[left_history.stack_cntr] > stack_level)
  620.         left_history.stack_cntr--;
  621.     if (right_history.stack_cntr == END)
  622.         return(END);
  623.     stack_level--;
  624.     return(right_history.element[right_history.stack_cntr--]);
  625. }
  626.  
  627.  
  628.   /* return the next one on the stack and keep right stack at proper level */
  629. long pop_left_stack()
  630. {
  631. /* pop both to stay at same tree level */
  632.     stack_level = left_history.level[left_history.stack_cntr];
  633.     while(right_history.level[right_history.stack_cntr] > stack_level)
  634.         right_history.stack_cntr--;
  635.     if (left_history.stack_cntr == END)
  636.         return(END);    
  637.     stack_level--;
  638.     return(left_history.element[left_history.stack_cntr--]);
  639. }
  640.  
  641.  
  642. void get_node(long nbr, struct node *nodeinfo, struct keyinfo *fileinfo)  /* read the info stored in node NBR */
  643. /* long nbr;      node to retrieve */
  644. /* struct node *nodeinfo;    where to store the node's information */
  645. /* struct keyinfo *fileinfo; */
  646. {
  647.     long spot;
  648.  
  649.     spot = nbr * (fileinfo->keylength + DATA_LENGTH);
  650.     fseek(fileinfo->file, spot, 0);
  651.     fgets(instr, 3, fileinfo->file);  /* get delete flag */
  652.     nodeinfo->delete_flag = atoi(instr);
  653.     fgets(instr, 3, fileinfo->file);  /* get balance factor */
  654.     nodeinfo->balance = atoi(instr);
  655.     fgets(instr, 6, fileinfo->file);  /* left_link */
  656.     nodeinfo->left_link = atol(instr);
  657.     fgets(instr, 6, fileinfo->file);  /* right_link */
  658.     nodeinfo->right_link = atol(instr);
  659.     fgets(instr, 6, fileinfo->file);
  660.     nodeinfo->rec_nbr = atol(instr);  /* data record number */
  661.     fgets(nodeinfo->key, fileinfo->keylength + 1, fileinfo->file);
  662. }
  663.