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

_rb_rotate.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: _rb_rotate.c,v 1.2 2006/07/13 19:16:23 klmitch Exp $
00020 */
00028 #include "dbprim.h"
00029 #include "dbprim_int.h"
00030 
00031 RCSTAG("@(#)$Id: _rb_rotate.c,v 1.2 2006/07/13 19:16:23 klmitch Exp $");
00032 
00033 /* Swap a child with its parent, effecting a rotation */
00034 void
00035 _rb_rotate(rb_tree_t *tree, rb_node_t *child)
00036 {
00037   rb_node_t *parent;
00038 
00039   if (!(parent = child->rn_parent)) /* make sure it has a parent... */
00040     return;
00041 
00042   /* Figure out what points to the parent and repoint it to the child */
00043   if (!parent->rn_parent) /* is the parent the root? */
00044     tree->rt_root = child;
00045   else if (rn_isleft(parent)) /* OK, is it a left node? */
00046     parent->rn_parent->rn_left = child;
00047   else /* ok, must be a right node */
00048     parent->rn_parent->rn_right = child;
00049 
00050   /* Now update the parent pointers of parent and child... */
00051   child->rn_parent = parent->rn_parent;
00052   parent->rn_parent = child;
00053 
00054   /* Finally, move the child nodes around a little... */
00055   if (parent->rn_right == child) { /* right child? */
00056     if (child->rn_left) /* update grandchild's parent pointer */
00057       child->rn_left->rn_parent = parent;
00058     parent->rn_right = child->rn_left; /* then move the child to the parent */
00059     child->rn_left = parent; /* Finally, link the parent to the child */
00060   } else { /* OK, left child! */
00061     if (child->rn_right) /* update grandchild's parent pointer */
00062       child->rn_right->rn_parent = parent;
00063     parent->rn_left = child->rn_right; /* then move the child to the parent */
00064     child->rn_right = parent; /* Finally, link the parent to the child */
00065   }
00066 }

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