along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- $Id: rbl.c,v 1.1.2.9 2000/11/21 09:13:59 guus Exp $
+ $Id: rbl.c,v 1.1.2.12 2000/11/24 23:12:59 guus Exp $
*/
#include "config.h"
{
rbl_t *rbl, *next;
int result;
-
+
next = rbl = tree->top;
while(next)
return rbl;
}
+/* Search closest match in the tree */
+rbl_t *rbl_search_closest_greater_rbl(rbltree_t *tree, void *data)
+{
+ rbl_t *rbl;
+
+ rbl = rbl_search_closest_rbl(tree, data);
+
+ if(rbl)
+ {
+ if(tree->compare(data, rbl->data) > 0)
+ rbl = rbl->next;
+ }
+
+ return rbl;
+}
+
+/* Search closest match in the tree */
+rbl_t *rbl_search_closest_smaller_rbl(rbltree_t *tree, void *data)
+{
+ rbl_t *rbl;
+
+ rbl = rbl_search_closest_rbl(tree, data);
+
+ if(rbl)
+ {
+ if(tree->compare(data, rbl->data) < 0)
+ rbl = rbl->next;
+ }
+
+ return rbl;
+}
+
void *rbl_search_closest(rbltree_t *tree, void *data)
{
- return rbl_search_closest_rbl(tree, data)->data;
+ rbl_t *rbl;
+
+ rbl = rbl_search_closest_rbl(tree, data);
+
+ if(rbl)
+ return rbl->data;
+ else
+ return NULL;
+}
+
+void *rbl_search_closest_greater(rbltree_t *tree, void *data)
+{
+ rbl_t *rbl;
+
+ rbl = rbl_search_closest_greater_rbl(tree, data);
+
+ if(rbl)
+ return rbl->data;
+ else
+ return NULL;
+}
+
+void *rbl_search_closest_smaller(rbltree_t *tree, void *data)
+{
+ rbl_t *rbl;
+
+ rbl = rbl_search_closest_smaller_rbl(tree, data);
+
+ if(rbl)
+ return rbl->data;
+ else
+ return NULL;
}
/* Search exact match or return NULL pointer */
rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
{
- rbl_t *rbl, *next;
+ rbl_t *rbl;
int result;
+
+ rbl = tree->top;
- next = rbl = tree->top;
-
- while(next)
+ while(rbl)
{
- rbl = next;
-
result = tree->compare(data, rbl->data);
if(result < 0)
- next = rbl->left;
+ rbl = rbl->left;
else if(result > 0)
- next = rbl->right;
+ rbl = rbl->right;
else
return rbl;
}
-
+
return NULL;
}
if(y->color == RBL_BLACK && x)
rbl_delete_fixup(x);
-
+
return rbl;
}
rbl = rbl_search_rbl(tree, data);
if(rbl)
- return rbl_unlink_rbl(rbl);
- else
- return NULL;
+ rbl_unlink_rbl(rbl);
+
+ return rbl;
}
/* Unlink node and free it */
void rbl_delete_rbl(rbl_t *rbl)
{
- free_rbl(rbl_unlink_rbl(rbl));
+ rbl_unlink_rbl(rbl);
+ free_rbl(rbl);
}
/* Search node in tree, unlink and free it */
void rbl_delete(rbltree_t *tree, void *data)
{
- free_rbl(rbl_unlink(tree, data));
-}
-
-rbl_unlink_rbltree_branch(rbl_t *rbl)
-{
- if(rbl->left)
- rbl_unlink_rbltree_branch(rbl->left);
+ rbl_t *rbl;
- if(rbl->right)
- rbl_unlink_rbltree_branch(rbl->right);
+ rbl = rbl_unlink(tree, data);
- if(rbl->parent)
- {
- if(rbl == rbl->parent->left)
- rbl->parent->left = NULL;
- else
- rbl->parent->right = NULL;
- }
+ if(rbl)
+ free_rbl(rbl);
}
/* Optimized unlinking for a complete tree */
for(rbl = tree->head; rbl; rbl = next)
{
next = rbl->next;
- if(tree->delete)
- tree->delete(rbl->data);
+ free_rbl(rbl);
}
tree->top = NULL;