home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / OBJASM.ZIP / OUINSERT.C < prev    next >
C/C++ Source or Header  |  1990-05-18  |  7KB  |  171 lines
  1. #include <stdio.h>
  2. #include "o.h"
  3.  
  4. void swap( NODE_T *, int, NODE_T *, int );
  5.  
  6. void swap( node_A, direct_A, node_B, direct_B )
  7.     NODE_T  *node_A;
  8.     int     direct_A;
  9.     NODE_T  *node_B;
  10.     int     direct_B;
  11. {
  12.     /* Swap the pointers (unless they are already threads) */
  13.     if ( node_A->thread[direct_A] ) {
  14.         node_B->ptr[direct_B] = node_A;
  15.         node_B->thread[direct_B] = TRUE;
  16.         node_A->thread[direct_A] = FALSE;
  17.     } else {
  18.         node_B->ptr[direct_B] = node_A->ptr[direct_A];
  19.         node_A->ptr[direct_A] = node_B;
  20.     }
  21. }
  22.  
  23.  
  24. NODE_T *insert( data, root_node, cmp_routine )
  25.     char    *data;                              /* pointer to data to save */
  26.     NODE_T  *root_node;                         /* pointer to root node    */
  27.     int     (*cmp_routine)( void *, void * );   /* routine used to compare */
  28.                                                 /* values at two nodes     */
  29. {
  30.     NODE_T      *insert_node;
  31.     NODE_T      *curr_node;         /* Current node we are visiting      */
  32.     NODE_T      *son_node;
  33.     NODE_T      *grand_son;
  34.     NODE_T      *path[32];          /* 32 levels (2^32 records!) */
  35.     int         direct[32];
  36.     int         level;
  37.     int         curr_direct;
  38.     int         con_direct;
  39.  
  40.     /* Prepare initial value for tree traversal */
  41.     level    = 0;
  42.     son_node = root_node;
  43.  
  44.     /*
  45.     **  Traverse tree looking for the place to insert this new node.  If
  46.     **  we find a node which gives a comparison result of 0 (equal), then
  47.     **  we cannot insert this new node.  To indicate this duplicate value,
  48.     **  a pointer to the node which contains the duplicate value is returned.
  49.     */
  50.     do  {
  51.         curr_node = son_node;               /* Advance to new son_node */
  52.  
  53.         /*  Compare this new node with the node at this position in the
  54.             tree and determine which direction to proceed from here.
  55.         */
  56.         curr_direct = (* cmp_routine)( curr_node->data, data );
  57.  
  58.         /*  is this node is a duplicate node?
  59.         */
  60.         if ( curr_direct == EQUAL ) {
  61.             if ( root_node->balance == LEFT ) { /* Duplicates allowed? */
  62.                 curr_direct = LEFT;             /* see new_tree()!!!!  */
  63.             } else {
  64.                 return ( curr_node );
  65.             }
  66.         }
  67.  
  68.         path[level] = curr_node;
  69.         direct[level] = curr_direct;
  70.         level++;
  71.  
  72.         son_node = curr_node->ptr[curr_direct];
  73.  
  74.     } while ( !curr_node->thread[curr_direct]);
  75.  
  76.     /*  Now, we have found the place to insert this node,
  77.         make the last visited node point to this new node.
  78.     */
  79.     con_direct = 1-curr_direct;
  80.  
  81.     /* Set up default values for this node which we are going to insert */
  82.     insert_node = (NODE_T *)o_malloc( sizeof(NODE_T) );
  83.  
  84.     insert_node->data                = data;
  85.     insert_node->balance             = BALANCED;
  86.     insert_node->thread[curr_direct] = TRUE;
  87.     insert_node->thread[con_direct ] = TRUE;
  88.     insert_node->ptr   [curr_direct] = curr_node->ptr[curr_direct];
  89.     insert_node->ptr   [con_direct ] = curr_node;
  90.  
  91.     curr_node->thread  [curr_direct] = FALSE;
  92.     curr_node->ptr     [curr_direct] = insert_node;
  93.  
  94.  
  95.     /*  Now loop through 'un-stacking' the path which we took on our
  96.         way to get this guy inserted.  Keep in mind that this process
  97.         is done in stack-order, so the last node visited will be the
  98.         first node processed, etc.  Also keep in mind that the loop
  99.         may be terminated before back-tracking completely to the root
  100.         node (ie. the entire path is not processed).
  101.     */
  102.     do {
  103.         son_node = curr_node;
  104.  
  105.         level--;
  106.  
  107.         /*  If we have gotten back out to the root of the tree,
  108.             then the height of the tree has increase.
  109.         */
  110.         if ( level == 0 ) {         /* Increment depth (see new_tree()!!!) */
  111.             root_node->ptr[LEFT] = (NODE_T *) (((int)root_node->ptr[LEFT])+1);
  112.             break;
  113.         }
  114.  
  115.         /*  Get path information at this stack level
  116.         */
  117.         curr_node = path[level];
  118.         curr_direct = direct[level];
  119.  
  120.         /*  If the node at this position along the path was BALANCED,
  121.             then make it lean in the direction we took from it on our
  122.             way down.
  123.         */
  124.         if ( curr_node->balance == BALANCED ) {
  125.             curr_node->balance = curr_direct;
  126.         } else {
  127.             /*  Otherwise, two cases may arise.
  128.                 1.  The node was unbalanced in the opposite
  129.                     direction to the direction we took.
  130.                     (In this case that node will become balanced)
  131.             */
  132.             if ( curr_node->balance != curr_direct ) {
  133.                 curr_node->balance = BALANCED;
  134.                 break;
  135.             } else {
  136.                 /* or 2.  The node was already unbalanced in the same
  137.                           direction we took. If this happens we may need to
  138.                           do single or double rotation.  Single rotation
  139.                           happens if the node (which is in the opposite
  140.                           direction to the direction we took) is leaning
  141.                           the direction we took (from the current node).
  142.                           Otherwise to double rotation.
  143.                 */
  144.                 con_direct = 1 - curr_direct;
  145.                 if ( son_node->balance == curr_direct ) {
  146.                     swap( son_node, con_direct, curr_node, curr_direct );
  147.                     curr_node->balance = BALANCED;
  148.                 } else {
  149.                     grand_son = son_node->ptr[con_direct];
  150.                     swap( grand_son, curr_direct,  son_node,  con_direct );
  151.                     swap( grand_son,  con_direct, curr_node, curr_direct );
  152.                     son_node->balance = (grand_son->balance == con_direct) ?
  153.                                             curr_direct : BALANCED;
  154.                     curr_node->balance = (grand_son->balance == curr_direct) ?
  155.                                             con_direct : BALANCED;
  156.                     son_node = grand_son;
  157.                 }
  158.                 son_node->balance = BALANCED;
  159.  
  160.                 /* now make parent point to new rotated node */
  161.                 path[level-1]->ptr[direct[level-1]] = son_node;
  162.                 break;
  163.             }
  164.         }
  165.     } while ( TRUE );
  166.  
  167.     /*  Return a pointer to the node inserted */
  168.     return ( insert_node );
  169. }
  170.  
  171.