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_locate.c,v 1.3 2006/07/13 19:16:23 klmitch Exp $ 00020 */ 00028 #include "dbprim.h" 00029 #include "dbprim_int.h" 00030 00031 RCSTAG("@(#)$Id: _rb_locate.c,v 1.3 2006/07/13 19:16:23 klmitch Exp $"); 00032 00033 /* Locate a given node, placing the given node if necessary */ 00034 rb_node_t * 00035 _rb_locate(rb_tree_t *tree, rb_node_t *node, db_key_t *key) 00036 { 00037 rb_node_t *tmp; 00038 int comp; 00039 00040 if (!tree->rt_root) { 00041 tree->rt_root = node; /* store node at root of tree... */ 00042 if (node) { 00043 node->rn_color = RB_COLOR_BLACK; /* it's at the root, make it black */ 00044 node->rn_tree = tree; /* what tree is it in? */ 00045 node->rn_parent = 0; /* what's its parent? */ 00046 node->rn_left = 0; /* node has no children... */ 00047 node->rn_right = 0; 00048 node->rn_key = *key; /* fill in the key! */ 00049 tree->rt_count++; /* keep a count of the number of nodes in the tree */ 00050 } 00051 return node; 00052 } else if (!(comp = (*tree->rt_comp)(tree, key, 00053 rn_key(tmp = tree->rt_root)))) 00054 return tree->rt_root; /* Oh, the root of the tree matches the key */ 00055 00056 while (1) /* Search for the key in the tree... */ 00057 if (comp < 0) { /* desired node is to the left */ 00058 if (!tmp->rn_left) { 00059 tmp->rn_left = node; /* add the node here */ 00060 break; /* We're done with the loop... */ 00061 } else if (!(comp = (*tree->rt_comp)(tree, key, 00062 rn_key(tmp = tmp->rn_left)))) 00063 return tmp; /* found the node in the tree, return it */ 00064 } else { /* desired node is to the right */ 00065 if (!tmp->rn_right) { 00066 tmp->rn_right = node; /* add the node here */ 00067 break; /* We're done with the loop... */ 00068 } else if (!(comp = (*tree->rt_comp)(tree, key, 00069 rn_key(tmp = tmp->rn_right)))) 00070 return tmp; /* found the node in the tree, return it */ 00071 } 00072 00073 if (node) { 00074 node->rn_color = RB_COLOR_RED; /* color it red... */ 00075 node->rn_tree = tree; /* what tree is it in? */ 00076 node->rn_parent = tmp; /* what's its parent? */ 00077 node->rn_left = 0; /* node has no children... */ 00078 node->rn_right = 0; 00079 node->rn_key = *key; /* fill in the key! */ 00080 tree->rt_count++; /* keep a count of the number of nodes in the tree */ 00081 } 00082 00083 return node; /* return the node */ 00084 }
1.4.4