Logo Search packages:      
Sourcecode: rapple version File versions  Download package

static rpl_reg_link rpl_reg_insert_r ( rpl_reg_link  link,
rpl_reg_item  item,
rpl_reg_color  color 
) [static]

Perform local insertions required to insert an item into the registry. This (recursive) function is called by the rpl_reg_insert function which starts the insertion from the registry root.

Parameters:
link pointer to the (local) insert item.
item the item to be inserted into the registry.
type indicator of whether this is a red or black link.
Returns:

Definition at line 173 of file registry.c.

References rpl_reg_node_s::color, rpl_reg_node_s::item, rpl_reg_node_s::left, rpl_reg_node_s::right, rpl_reg_get_key(), rpl_reg_less(), rpl_reg_new(), rpl_reg_rot_l(), and rpl_reg_rot_r().

Referenced by rpl_reg_insert().

{
      rpl_reg_key item_key; 

      item_key = rpl_reg_get_key(item);
      if(link == RPL_REG_NULL)
            return rpl_reg_new(item, RPL_REG_NULL, RPL_REG_NULL, 1, RPL_REG_RED);
      if((link->left->color == RPL_REG_RED) && (link->right->color == RPL_REG_RED))
      {
            link->color = RPL_REG_RED;
            link->left->color = RPL_REG_BLACK;
            link->right->color = RPL_REG_BLACK;
      }
      if(rpl_reg_less(item_key, rpl_reg_get_key(link->item)))
      {
            link->left = rpl_reg_insert_r(link->left, item, RPL_REG_BLACK);
            if((link->color == RPL_REG_RED) 
                        && (link->left->color == RPL_REG_RED) 
                              && (color == RPL_REG_RED))
            {
                  link = rpl_reg_rot_r(link);
            }
            if((link->left->color == RPL_REG_RED) && (link->left->left->color == RPL_REG_RED))
            {
                  link = rpl_reg_rot_r(link);
                  link->color = RPL_REG_BLACK;
                  link->right->color = RPL_REG_RED;
                  
            }
      } else {
            link->right = rpl_reg_insert_r(link->right, item, RPL_REG_RED);
            if((link->color == RPL_REG_RED) 
                        && (link->right->color == RPL_REG_RED) 
                              && (color == RPL_REG_BLACK))
            {
                  link = rpl_reg_rot_l(link);
            }
            if((link->right->color == RPL_REG_RED) && (link->right->right->color == RPL_REG_RED))
            {
                  link = rpl_reg_rot_l(link);
                  link->color = RPL_REG_BLACK;
                  link->left->color = RPL_REG_RED;
            }
      }
      /* fixN(link) ?? */
      return link;
}


Generated by  Doxygen 1.6.0   Back to index