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

rt_remove.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_remove.c,v 1.3 2006/07/13 19:16:24 klmitch Exp $
00020 */
00028 #include "dbprim.h"
00029 #include "dbprim_int.h"
00030 
00031 RCSTAG("@(#)$Id: rt_remove.c,v 1.3 2006/07/13 19:16:24 klmitch Exp $");
00032 
00042 #define _rn_clear(node)                                                       \
00043 do {                                                                          \
00044   (node)->rn_color = RB_COLOR_NONE; /* no color... */                         \
00045   (node)->rn_tree = 0; /* no tree... */                                       \
00046   (node)->rn_parent = 0; /* no parent... */                                   \
00047   (node)->rn_left = 0; /* and no children */                                  \
00048   (node)->rn_right = 0;                                                       \
00049 } while (0)
00050 
00064 #define _rt_update_parent(tree, node, new)                                    \
00065 do {                                                                          \
00066   if (!(node)->rn_parent) /* node must be at root of tree... */               \
00067     (tree)->rt_root = (new); /* so update the root */                         \
00068   else if (rn_isleft(node)) /* maybe it's a left child? */                    \
00069     (node)->rn_parent->rn_left = (new); /* OK, save new value there */        \
00070   else                                                                        \
00071     (node)->rn_parent->rn_right = (new); /* OK, right child, save tere */     \
00072 } while (0)
00073 
00087 #define isleft(par, n)  ((par)->rn_left == (n))
00088 
00104 #define sel_lr(t, n)    ((t) ? (n)->rn_right : (n)->rn_left)
00105 
00119 #define sibling(par, n) (sel_lr(isleft((par), (n)), (par)))
00120 
00135 #define l_neph(par, n)  (sel_lr(!isleft((par), (n)), sibling((par), (n))))
00136 
00151 #define r_neph(par, n)  (sel_lr(isleft((par), (n)), sibling((par), (n))))
00152 
00153 unsigned long
00154 rt_remove(rb_tree_t *tree, rb_node_t *node)
00155 {
00156   rb_color_t col;
00157   rb_node_t *nchild, *nparent;
00158 
00159   initialize_dbpr_error_table(); /* initialize error table */
00160 
00161   if (!rt_verify(tree) || !rn_verify(node)) /* verify arguments */
00162     return DB_ERR_BADARGS;
00163 
00164   if (!node->rn_tree) /* it's not in a tree... */
00165     return DB_ERR_UNUSED;
00166   if (node->rn_tree != tree) /* it's in the wrong tree */
00167     return DB_ERR_WRONGTABLE;
00168 
00169   if (tree->rt_flags & RBT_FLAG_FREEZE) /* don't remove from frozen trees */
00170     return DB_ERR_FROZEN;
00171 
00172   if (tree->rt_count == 1) { /* only the one node... */
00173     _rn_clear(node); /* clear the node */
00174 
00175     tree->rt_root = 0; /* clear the root pointer... */
00176     tree->rt_count--; /* update the node count */
00177 
00178     return 0; /* and we're done...gee, that was simple */
00179   }
00180 
00181   /* If the node has both children, swap it with one of its great-*
00182    * grandchildren that has only one child.
00183    */
00184   if (node->rn_left && node->rn_right) {
00185     rb_node_t *ggchild;
00186 
00187     for (ggchild = node->rn_right; ggchild->rn_left;
00188          ggchild = ggchild->rn_left)
00189       ; /* find the left-most great-* grandchild on the right subtree */
00190 
00191     /* remember that node's parent... */
00192     nparent = (ggchild->rn_parent == node) ? ggchild : ggchild->rn_parent;
00193     nchild = ggchild->rn_right; /* ...child... */
00194     col = ggchild->rn_color; /* ...and color */
00195 
00196     /* next, groom great-* grandchild to replace node */
00197     ggchild->rn_left = node->rn_left;
00198     ggchild->rn_right = node->rn_right == ggchild ? 0 : node->rn_right;
00199     ggchild->rn_parent = node->rn_parent;
00200     ggchild->rn_color = node->rn_color;
00201 
00202     /* let's update the node's parent to point at great-* grandchild */
00203     _rt_update_parent(tree, node, ggchild);
00204 
00205     ggchild->rn_left->rn_parent = ggchild; /* ...and its children... */
00206     if (ggchild->rn_right)
00207       ggchild->rn_right->rn_parent = ggchild;
00208 
00209     /* Then update great-* grandchild's original parent... */
00210     if (nparent != ggchild)
00211       nparent->rn_left = nchild; /* it's by definition a left child */
00212     else
00213       nparent->rn_right = nchild; /* don't lose the thing! */
00214   } else { /* it's already an external node, so remove it... */
00215     nparent = node->rn_parent; /* remember node's parent... */
00216     nchild = node->rn_left ? node->rn_left : node->rn_right; /* ...child... */
00217     col = node->rn_color; /* ...and color */
00218 
00219     /* update node's parent to point at node's child */
00220     _rt_update_parent(tree, node, nchild);
00221   }
00222 
00223   if (nchild) /* now, if there was a child... */
00224     nchild->rn_parent = nparent; /* update its parent pointer */
00225 
00226   if (col == RB_COLOR_BLACK) { /* removed a black node, gotta rebalance... */
00227     /* work our way up the tree, stopping on the first red node */
00228     while (nparent && rn_isblack(nchild)) {
00229       /* If the sibling is red... */
00230       if (rn_isred(sibling(nparent, nchild))) {
00231         _rb_rotate(tree, sibling(nparent, nchild)); /* move it up... */
00232         nparent->rn_color = RB_COLOR_RED; /* and recolor the nodes */
00233         nparent->rn_parent->rn_color = RB_COLOR_BLACK; /* old sibling */
00234       }
00235 
00236       /* Sibling is black, are the nephews? */
00237       if (rn_isblack(l_neph(nparent, nchild)) &&
00238           rn_isblack(r_neph(nparent, nchild))) {
00239         sibling(nparent, nchild)->rn_color = RB_COLOR_RED; /* recolor sib... */
00240         nchild = nparent; /* then move up the tree... */
00241         nparent = nparent->rn_parent;
00242         continue; /* go through loop once more... */
00243       }
00244 
00245       /* OK, one or the other (or both!) of the nephews is red. */
00246       if (rn_isred(l_neph(nparent, nchild))) /* is the closer one red? */
00247         _rb_rotate(tree, l_neph(nparent, nchild)); /* then rotate it up */
00248       _rb_rotate(tree, sibling(nparent, nchild)); /* now rotate sibling up */
00249 
00250       /* set old sibling color to be the same as parent. */
00251       nparent->rn_parent->rn_color = nparent->rn_color;
00252       nparent->rn_color = RB_COLOR_BLACK; /* set parent black... */
00253       /* now set the parent's new sibling black */
00254       sibling(nparent->rn_parent, nparent)->rn_color = RB_COLOR_BLACK;
00255       break; /* this is a terminal case; we're done. */
00256     }
00257 
00258     if (rn_isred(nchild)) /* if we hit a red node, turn it black */
00259       nchild->rn_color = RB_COLOR_BLACK;
00260   }
00261 
00262   _rn_clear(node); /* clear the node */
00263 
00264   tree->rt_count--; /* update the node count */
00265 
00266   return 0; /* and we're done...gee, that was simple */
00267 }

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