Main Page | Modules | Alphabetical List | Data Structures | File List | Data Fields | Globals

rt_add.c

Go to the documentation of this file.
00001 /*
00002 ** Copyright (C) 2003 by Kevin L. Mitchell <klmitch@mit.edu>
00003 **
00004 ** This library is free software; you can redistribute it and/or
00005 ** modify it under the terms of the GNU Library General Public
00006 ** License as published by the Free Software Foundation; either
00007 ** version 2 of the License, or (at your option) any later version.
00008 **
00009 ** This library is distributed in the hope that it will be useful,
00010 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012 ** Library General Public License for more details.
00013 **
00014 ** You should have received a copy of the GNU Library General Public
00015 ** License along with this library; if not, write to the Free
00016 ** Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00017 ** MA 02111-1307, USA
00018 **
00019 ** @(#)$Id: rt_add.c,v 1.2 2006/07/13 19:16:24 klmitch Exp $
00020 */
00028 #include "dbprim.h"
00029 #include "dbprim_int.h"
00030 
00031 RCSTAG("@(#)$Id: rt_add.c,v 1.2 2006/07/13 19:16:24 klmitch Exp $");
00032 
00045 #define uncle(node)     (rn_isleft((node)->rn_parent) ? \
00046                          (node)->rn_parent->rn_parent->rn_right : \
00047                          (node)->rn_parent->rn_parent->rn_left)
00048 
00057 #define flip(node)      ((node)->rn_color = \
00058                          ((node)->rn_color == RB_COLOR_BLACK) ? \
00059                          RB_COLOR_RED : RB_COLOR_BLACK)
00060 
00061 unsigned long
00062 rt_add(rb_tree_t *tree, rb_node_t *node, db_key_t *key)
00063 {
00064   initialize_dbpr_error_table(); /* initialize error table */
00065 
00066   if (!rt_verify(tree) || !rn_verify(node) || !key) /* verify arguments */
00067     return DB_ERR_BADARGS;
00068 
00069   if (node->rn_tree) /* it's already in a tree... */
00070     return DB_ERR_BUSY;
00071 
00072   if (tree->rt_flags & RBT_FLAG_FREEZE) /* don't add to frozen trees */
00073     return DB_ERR_FROZEN;
00074 
00075   if (_rb_locate(tree, node, key) != node) /* add it to the tree... */
00076     return DB_ERR_DUPLICATE; /* We don't allow duplication! */
00077 
00078   /* OK, node has been added, now let's rebalance the tree... */
00079   while (!rn_isblack(node) && !rn_isblack(node->rn_parent))
00080     if (rn_isred(uncle(node))) {
00081       flip(node->rn_parent); /* Flip the colors of parent and grandparent */
00082       flip(node->rn_parent->rn_parent);
00083       flip(uncle(node)); /* and flip the color of the uncle */
00084       node = node->rn_parent->rn_parent; /* grandparent need balancing? */
00085     } else if ((rn_isleft(node->rn_parent) && rn_isright(node)) ||
00086                (rn_isright(node->rn_parent) && rn_isleft(node))) {
00087       flip(node); /* flip the colors that need flipping... */
00088       flip(node->rn_parent->rn_parent);
00089       _rb_rotate(tree, node); /* rotate the node up two levels */
00090       _rb_rotate(tree, node);
00091     } else {
00092       flip(node->rn_parent); /* flip the colors that need flipping... */
00093       flip(node->rn_parent->rn_parent);
00094       _rb_rotate(tree, node->rn_parent); /* move the parent up a level */
00095       node = node->rn_parent; /* new parent need balancing? */
00096     }
00097 
00098   /* Make sure the root node is black */
00099   tree->rt_root->rn_color = RB_COLOR_BLACK;
00100 
00101   return 0;
00102 }

Generated on Sat Jul 15 14:10:33 2006 for DatabasePrimitivesLibrary by  doxygen 1.4.4