home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 155_01 / btree1.c < prev    next >
C/C++ Source or Header  |  1990-10-09  |  16KB  |  436 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <alloc.h>
  4. #include "btree.h"
  5.  
  6. /* Author: Ray Swartz
  7.  *         Berkeley Decision/Systems, Inc.
  8.  *         P.O. Box 2528
  9.  *         Santa Cruz, Calif. 95063
  10.  * Last Modified: 4/28/85
  11.  *
  12.  * ANY USE OF THESE LIBRARY ROUTINES EITHER PERSONAL OR COMMERCIAL
  13.  * IS ALLOWED UPON THE CONDITION THAT THE USER IDENTIFY THEM
  14.  * AS BEING USED IN THE PROGRAM.  IDENTIFYING INFORMATION MUST
  15.  * APPEAR IN THE PROGRAM DOCUMENTATION OR ON THE TERMINAL SCREEN.
  16.  *
  17.  *         #################################    
  18.  *         # UNATTRIBUTED USE IS FORBIDDEN #
  19.  *         #################################
  20.  *
  21.  * The insert routine was directly translated from the algorithm
  22.  *  in D. Knuth's Volume 3 of The Art of Computer Programming
  23.  *  (Sorting and Searching) pages 455 - 457.  Single letter
  24.  *  variables (p, q, r, s) are used to make the algorithm steps
  25.  *  more obvious.
  26.  */
  27. /*
  28.  *    Modifier: Honma Michimasa
  29.  */
  30.  
  31. /**** Function prot. ********/
  32. int insert(char *argkey, long recnbr, struct keyinfo *fileinfo);
  33.                  /* insert key (argkey) into tree */
  34. void link(int alpha1, struct node *node1, int alpha2, struct node *node2);
  35. void nbr_link(long *nbr, int alpha, struct node *node1);
  36.                  /* set a record number according to alpha */
  37. void link_nbr(int alpha, struct node *node1, long nbr);
  38.                  /* set a link according to alpha */
  39. void node_bal(int alpha, struct node *node1, struct node *node2, struct node *node3);
  40.                   /* node balancing in Step A9 */
  41. void delete_key(long node_nbr, struct node *current_node, struct keyinfo *fileinfo);
  42. int get_next(long *node_nbr, struct node *current_node, struct keyinfo *fileinfo);
  43.                   /* retrieve next higher node */
  44. int find_key(char *key1, long *node_nbr, struct node *current_node, struct keyinfo *fileinfo);
  45.                  /* locate a key */
  46.  
  47.  
  48.  
  49. int insert(char *argkey, long recnbr, struct keyinfo *fileinfo) /* insert key (argkey) into tree */
  50. /* struct keyinfo *fileinfo;  file to insert key into */
  51. /* char *argkey;     key to insert */
  52. /* long recnbr;      record number of corresponding data record */
  53. {
  54.     static long top;  /* where balancing will have to take place, if at all */
  55.     static long p_rec;
  56.     static long s_rec;
  57.     static long q_rec;
  58.     static long r_rec;
  59.     static struct node q_node, s_node, r_node, p_node;
  60.     static int alloc_flag = NO;  /* flag for pointer space allocation */
  61.     int compare;   /* holds key comparison values */
  62.     
  63.     if (fileinfo->next_avail >= MAX_NODES) {
  64.         printf("Only %d nodes allowed in a keyfile\n");
  65.         exit(1);
  66.     }
  67.     if(alloc_flag == NO) {   /* set up key pointers in node structures  */
  68.         q_node.key = malloc(fileinfo->keylength + 1); /* first call to */
  69.         s_node.key = malloc(fileinfo->keylength + 1); /* insert function */
  70.         p_node.key = malloc(fileinfo->keylength + 1);
  71.         r_node.key = malloc(fileinfo->keylength + 1);
  72.         alloc_flag = YES;
  73.     }
  74.     if (fileinfo->list_head == 0) {   /* no records in list */
  75.         fileinfo->list_head = 1;  /* insert key as head of list */
  76.         p_node.balance = p_node.right_link = p_node.left_link = 0;
  77.         p_node.delete_flag = NO;
  78.         p_node.rec_nbr = recnbr;
  79.         strcpy(p_node.key, argkey);
  80.         write_node(1L, &p_node, fileinfo);
  81.         fileinfo->next_avail++;
  82.         fileinfo->nbr_in_list++;
  83.         return(YES);
  84.     }
  85.     top = TOP;    /* initialize to see if list head changes */
  86.     p_rec = fileinfo->list_head;   /* Step A1 (find spot to insert) */
  87.     s_rec = fileinfo->list_head;
  88.     while(1) {
  89.         get_node(p_rec, &p_node, fileinfo);
  90.         if ((compare = strcmp(argkey, p_node.key)) < 0) {  /* Step A2 */
  91.             q_rec = p_node.left_link;  /* Step A3 (move left) */
  92.             if (q_rec == END) {  /* insert here */
  93.                 q_rec = fileinfo->next_avail++;
  94.                 p_node.left_link = q_rec;
  95.                 break;  /* loop exit */
  96.             }
  97.             else {  /* look again from this node */
  98.                 get_node(q_rec, &q_node, fileinfo);
  99.                 if (q_node.balance != 0) {
  100.                     top = p_rec;
  101.                     s_rec = q_rec;
  102.                 }
  103.             }
  104.             p_rec = q_rec;
  105.         }
  106.         else  {  /* Step A4 (move right) */
  107.             q_rec = p_node.right_link;
  108.             if (q_rec == END) {  /* insert here */
  109.                 q_rec = fileinfo->next_avail++;
  110.                 p_node.right_link = q_rec;
  111.                 break;  /* loop exit */
  112.             }
  113.             else {  /* look again from this node */
  114.                 get_node(q_rec, &q_node, fileinfo);
  115.                 if (q_node.balance != 0) {
  116.                     top = p_rec;
  117.                     s_rec = q_rec;
  118.                 }
  119.                 p_rec = q_rec;
  120.             }
  121.         }
  122.     } /* end of while loop */
  123. /* Step 5 (insert key at q_node) */      
  124.     q_node.left_link = q_node.right_link = END;
  125.     q_node.balance = 0;
  126.     q_node.delete_flag = NO;
  127.     q_node.rec_nbr = recnbr;
  128.     strcpy(q_node.key, argkey);
  129.     if (write_node(q_rec, &q_node, fileinfo) == NO)
  130.         return(NO);  /* write failed */
  131.     write_node(p_rec, &p_node, fileinfo);
  132.     get_node(s_rec, &s_node, fileinfo); /* Step A6 (adjust balance factors) */
  133.     if (strcmp(argkey, s_node.key) < 0)
  134.         r_rec = p_rec = s_node.left_link;
  135.     else
  136.         r_rec = p_rec = s_node.right_link;
  137.     while (p_rec != q_rec) {
  138.         get_node(p_rec, &p_node, fileinfo);
  139.         if(strcmp(argkey, p_node.key) < 0) {
  140.             p_node.balance = -1;
  141.             write_node(p_rec, &p_node, fileinfo);
  142.             p_rec = p_node.left_link;
  143.         }
  144.         else {
  145.             p_node.balance = 1;
  146.             write_node(p_rec, &p_node, fileinfo);
  147.             p_rec = p_node.right_link;
  148.         }
  149.     }
  150.     compare = (strcmp(argkey, s_node.key) < 0) ? -1 : 1; /* Step A7 */
  151.     if (s_node.balance == 0) {  /* Step A7i */
  152.         fileinfo->nbr_in_list++;
  153.         s_node.balance = compare;
  154.         write_node(s_rec, &s_node, fileinfo);
  155.         return(YES);
  156.     }
  157.     else if(s_node.balance == -compare) {  /* Step A7ii */
  158.         fileinfo->nbr_in_list++;
  159.         s_node.balance = 0;
  160.         write_node(s_rec, &s_node, fileinfo);
  161.         return(YES);
  162.     }
  163.     else { /* Step A7iii (tree out of balance) */
  164.         fileinfo->nbr_in_list++;
  165.         get_node(s_rec, &s_node, fileinfo);
  166.         get_node(r_rec, &r_node, fileinfo);
  167.         if (r_node.balance == compare) { /* Step A8 (single rotate) */
  168.             p_rec = r_rec;
  169.             link(compare, &s_node, -compare, &r_node);
  170.             link_nbr(-compare, &r_node, s_rec);
  171.             s_node.balance = r_node.balance = 0;
  172.         }
  173.         else {   /* Step A9 (double rotate) */
  174.             nbr_link(&p_rec, -compare, &r_node);
  175.             get_node(p_rec, &p_node, fileinfo);
  176.             link(-compare, &r_node, compare, &p_node);
  177.             link_nbr(compare, &p_node, r_rec);
  178.             link(compare, &s_node, -compare, &p_node);
  179.             link_nbr(-compare, &p_node, s_rec);
  180.             node_bal(compare, &p_node, &s_node, &r_node);
  181.             p_node.balance = 0;
  182.             write_node(p_rec, &p_node, fileinfo);
  183.         }
  184.         if (top == TOP)  /* Step A10 */ 
  185.             fileinfo->list_head = p_rec; /* balanced at list head */ 
  186.         else {   /* balanced at top of a sub-tree */
  187.             get_node(top, &q_node, fileinfo); 
  188.             if (s_rec == q_node.right_link)
  189.                 q_node.right_link = p_rec; 
  190.             else
  191.                 q_node.left_link = p_rec;
  192.             write_node(top, &q_node, fileinfo);
  193.         }
  194.         write_node(s_rec, &s_node, fileinfo);
  195.         write_node(r_rec, &r_node, fileinfo);
  196.         return(YES);
  197.     }
  198. }
  199.  
  200.  
  201. void link(int alpha1, struct node *node1, int alpha2, struct node *node2)
  202. /*
  203. int alpha1, alpha2;
  204. struct node *node1, *node2;
  205. */
  206. {
  207.     /* see definition of LINK(a, P) on Knuth pg. 455 (Vol. 3) */
  208.       
  209.     if (alpha1 == -1 && alpha2 == -1)
  210.         node1->left_link = node2->left_link;
  211.     else if(alpha1 == -1 && alpha2 == 1)
  212.         node1->left_link = node2->right_link;
  213.     else if(alpha1 == 1 && alpha2 == -1)
  214.         node1->right_link = node2->left_link;
  215.     else
  216.         node1->right_link = node2->right_link;
  217.     return;
  218. }
  219.  
  220.  
  221. void nbr_link(long *nbr, int alpha, struct node *node1) /* set a record number according to alpha */
  222. /*
  223. long *nbr;
  224. int alpha;
  225. struct node *node1;
  226. */
  227. {
  228.  
  229.     *nbr = (alpha == 1) ? node1->right_link : node1->left_link;
  230.     return;
  231. }
  232.  
  233. void link_nbr(int alpha, struct node *node1, long nbr) /* set a link according to alpha */
  234. /*
  235. int alpha;
  236. struct node *node1;
  237. long nbr;
  238. */
  239. {
  240.  
  241.     if (alpha == 1)
  242.         node1->right_link = nbr;
  243.     else
  244.         node1->left_link = nbr;
  245.     return;
  246. }
  247.  
  248. void node_bal(int alpha, struct node *node1, struct node *node2, struct node *node3)  /* node balancing in Step A9 */
  249. /*
  250. int alpha;
  251. struct node *node1, *node2, *node3;
  252. */
  253. {
  254.  
  255.     if (node1->balance == alpha) {
  256.         node2->balance = -alpha;
  257.         node3->balance = 0;
  258.     } 
  259.     else if(node1->balance == 0)
  260.         node2->balance = node3->balance = 0;
  261.     else {
  262.         node2->balance = 0;
  263.         node3->balance = alpha;
  264.     }
  265.     return;
  266. }
  267.  
  268.  
  269. void delete_key(long node_nbr, struct node *current_node, struct keyinfo *fileinfo)
  270. /* long node_nbr;   node to delete */
  271. /* struct node *current_node;   deleted node's information */
  272. /* struct keyinfo *fileinfo;   keyfile */
  273. {
  274.     if (node_nbr == END)
  275.         printf("DELETE: can't delete node 0\n");
  276.     else {
  277.         current_node->delete_flag = YES;
  278.         if (write_node(node_nbr, current_node, fileinfo) == NO)
  279.             print_msg("DELETE: write_node returned NO");
  280.         else
  281.             fileinfo->nbr_in_list--;
  282.     }
  283.     return;
  284. }
  285.  
  286.  
  287.  
  288. int get_next(long *node_nbr, struct node *current_node, struct keyinfo *fileinfo)  /* retrieve next higher node */
  289. /* struct keyfile(keyinfo ?) *fileinfo; */
  290. /* struct node *current_node;   where to store node's info */
  291. /* long *node_nbr;     node to retrieve */
  292. {
  293.   /*  long pop_left_stack(), pop_right_stack();   ***********/
  294.     long search_node;
  295.    
  296.     search_node = *node_nbr;
  297.     if (*node_nbr == END) {   /* undefined current node */
  298.          print_msg("Must FIND a record first\n");
  299.          return(NO);
  300.     }
  301.     do {
  302.         if(current_node->right_link == END) {  /* can't move right */
  303.             if(left_history.stack_cntr == END) { /* none in stack */
  304.                 /* node_nbr at end of non-deleted elements - retreive it */
  305.                 get_node(*node_nbr, current_node, fileinfo);
  306.                 return(AT_END);
  307.             }
  308.             else {    /* can't go right & stack full (pop stack) */
  309.                 search_node = pop_left_stack();
  310.                 get_node(search_node, current_node, fileinfo);
  311.             }  
  312.         }
  313.         else {  /* move right */
  314.             push_right_stack(search_node);
  315.             search_node = current_node->right_link;
  316.             get_node(search_node, current_node, fileinfo);
  317.             while(current_node->left_link != END) { /* bottom left */
  318.                 push_left_stack(search_node);
  319.                 search_node = current_node->left_link; /* of this sub-tree */
  320.                 get_node(search_node, current_node, fileinfo);
  321.             }
  322.         }
  323.     } while (current_node->delete_flag == YES);
  324.     *node_nbr = search_node;
  325.     return(YES);
  326. }
  327.  
  328.  
  329.  
  330. int find_key(char *key1, long *node_nbr, struct node *current_node, struct keyinfo *fileinfo) /* locate a key */
  331. /* char *key1;   key to find */
  332. /* struct keyinfo *fileinfo;  */
  333. /* long *node_nbr;  number of "found" node */
  334. /* struct node *current_node;   where "found" node is stored */
  335. {
  336.     int direction;   /* flag to determine moving right or left */
  337.     long search_node; /* node presently being searched */
  338.  
  339. /* initalize stacks to empty */
  340.     right_history.stack_cntr = left_history.stack_cntr = END;
  341.     right_history.element[END] = left_history.element[END] = END;
  342.     stack_level = 0;   /* tree level at start of search */
  343.     search_node = fileinfo->list_head;  /* begin at list head */
  344.     get_node(search_node, current_node, fileinfo);
  345.     while((direction = strcmp(key1, current_node->key)) != 0 ||
  346.            current_node->delete_flag == YES) {
  347.         if (direction > 0) { /* search to right */
  348.             if (current_node->right_link != END) { 
  349.                 push_right_stack(search_node); /* not found, more to see */
  350.                 search_node = current_node->right_link;
  351.                 get_node(search_node, current_node, fileinfo);
  352.             }
  353.             else if(current_node->delete_flag == YES) { /* node deleted */
  354.               /* skip all deleted nodes */
  355.                 while(current_node->delete_flag == YES) { 
  356.                    if(get_next(&search_node,current_node,fileinfo) == AT_END){
  357.                         get_previous(&search_node, current_node, fileinfo);
  358.                         *node_nbr = search_node;      
  359.                         return(NOT_FOUND);
  360.                    }
  361.                 }
  362.                 *node_nbr = search_node;
  363.                 return(NOT_FOUND);
  364.             }
  365.             else {  /* at end of a branch */
  366.                 *node_nbr = search_node;
  367.                 return(NOT_FOUND);
  368.             }
  369.         }   
  370.         else {  /* search to left */
  371.             if (current_node->left_link != END) {
  372.                 push_left_stack(search_node); 
  373.                 search_node = current_node->left_link;
  374.                 get_node(search_node, current_node, fileinfo);
  375.             }                         
  376.             else if(current_node->delete_flag == YES) { /* left = END */
  377.                 while(current_node->delete_flag == YES) {
  378.                  if (get_next(&search_node,current_node,fileinfo)==AT_END) {
  379.                        get_previous(&search_node, current_node, fileinfo);
  380.                        *node_nbr = search_node;     
  381.                        return(NOT_FOUND);
  382.                    }
  383.                 }
  384.                 *node_nbr = search_node;
  385.                 return(NOT_FOUND);
  386.             }   
  387.             else {
  388.                 *node_nbr = search_node;
  389.                 return(NOT_FOUND);
  390.             }
  391.         }
  392.     }  /* end of search while loop */
  393.     return(YES);  /* exact match and not deleted only */
  394. }
  395.  
  396.  
  397. get_previous(node_nbr, current_node, fileinfo)
  398. long *node_nbr;
  399. struct node *current_node;
  400. struct keyinfo *fileinfo;
  401. {
  402. /*    long pop_right_stack(), pop_left_stack();  ***********/
  403.     long search_node;
  404.  
  405.     search_node = *node_nbr;
  406.     if (*node_nbr == END) {   /* undefined current node */
  407.         print_msg("Must FIND a record first\n");
  408.         return(NO);
  409.     }
  410.     do {
  411.         if(current_node->left_link == END) {  /* can't move left */
  412.             if(right_history.stack_cntr == END) { /* none in stack */
  413.                 /* node_nbr at end of non-deleted elements - retreive it */
  414.                 get_node(*node_nbr, current_node, fileinfo);
  415.                 return(AT_END);  /* don't reset node_nbr */
  416.             }
  417.             else {    /* can't go left & stack full (pop stack) */
  418.                 search_node = pop_right_stack();
  419.                 get_node(search_node, current_node, fileinfo);
  420.             }  
  421.         }
  422.         else {  /* move left then to bottom right - this is previous one */
  423.             push_left_stack(search_node);
  424.             search_node = current_node->left_link;
  425.             get_node(search_node, current_node, fileinfo);
  426.             while(current_node->right_link != END) { /* bottom right */
  427.                 push_right_stack(search_node);       /* of this sub-tree */
  428.                 search_node = current_node->right_link;
  429.                 get_node(search_node, current_node, fileinfo);
  430.             }
  431.         }
  432.     } while (current_node->delete_flag == YES);
  433.     *node_nbr = search_node;   /* set node_nbr to previous node found */    
  434.     return(YES);
  435. }
  436.