/*
rbl.c -- red-black tree + linked list convenience
- Copyright (C) 2000 Ivo Timmermans <itimmermans@bigfoot.com>,
- 2000 Guus Sliepen <guus@sliepen.warande.net>
+ Copyright (C) 2000 Ivo Timmermans <ivo@o2w.nl>,
+ 2000 Guus Sliepen <guus@sliepen.eu.org>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
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.4 2000/11/18 23:22:44 guus Exp $
+ $Id: rbl.c,v 1.1.2.13 2002/06/21 10:11:11 guus Exp $
*/
+#include "config.h"
+
+#include <stdlib.h>
+#include <xalloc.h>
+
+#include "rbl.h"
+#include <system.h>
/* Allocate a new rbl node */
rbl_t *new_rbl()
{
- return (rbl_t *)xmalloc_and_zero(sizeof(*rbl));
+ return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
}
/* Free a rbl node */
void free_rbl(rbl_t *rbl)
{
+ if(rbl->data && rbl->tree->delete)
+ rbl->tree->delete(rbl->data);
free(rbl);
}
/* Allocate a new rbltree header */
-rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_action_t *delete)
+rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
{
rbltree_t *tree;
}
/* Search closest match in the tree */
-rbl_t rbl_search_closest(rbltree_t *tree, void *data)
+rbl_t *rbl_search_closest_rbl(rbltree_t *tree, void *data)
{
rbl_t *rbl, *next;
int result;
-
+
next = rbl = tree->top;
while(next)
{
rbl = next;
- result = tree->compare(rbl->data, data);
+ result = tree->compare(data, rbl->data);
if(result < 0)
next = rbl->left;
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)
+{
+ 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(rbltree_t *tree, void *data)
+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(rbl->data, data);
+ 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;
}
+void *rbl_search(rbltree_t *tree, void *data)
+{
+ rbl_t *rbl;
+
+ rbl = rbl_search_rbl(tree, data);
+
+ if(rbl)
+ return rbl->data;
+ else
+ return NULL;
+}
+
/* Red-black tree operations taken from Introduction to Algorithms,
Cormen, Leiserson & Rivest, chapter 14.
*/
x->parent->left = y;
else
x->parent->right = y;
-
+
y->left = x;
x->parent = y;
}
void rbl_right_rotate(rbl_t *y)
{
rbl_t *x;
-
+
x = y->left;
y->left = x->right;
}
/* Insert a node into the rbl tree */
-rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
+rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
{
- rbl_t *closest, y;
- int result;
+ rbl_t *closest, *x, *y;
+ int result;
+ rbl->tree = tree;
+
/* Binary tree and linked list insert */
if(tree->top)
{
- closest = rbl_search_closest(tree, rbl->data);
- result = tree->compare(rbl->data, data);
+ closest = rbl_search_closest_rbl(tree, rbl->data);
+ result = tree->compare(rbl->data, closest->data);
if(result < 0)
{
closest->left = rbl;
+
rbl->prev = closest->prev;
rbl->next = closest;
closest->prev = rbl;
- rbl->prev->next = rbl;
+
+ if(rbl->prev)
+ rbl->prev->next = rbl;
+ else
+ tree->head = rbl;
}
else if(result > 0)
{
closest->right = rbl;
- rbl->next = closest->right;
+
+ rbl->next = closest->next;
rbl->prev = closest;
closest->next = rbl;
- rbl->next->prev = rbl;
+
+ if(rbl->next)
+ rbl->next->prev = rbl;
+ else
+ tree->tail = rbl;
}
else
return closest; /* Ofcourse, we cannot add two identical things */
+
+ rbl->parent = closest;
}
else
- tree->top = rbl;
-
- /* Linked list fixup */
-
- if(!rbl->prev)
- tree->head = rbl;
-
- if(!rbl->next)
- tree->tail = rbl;
+ {
+ tree->top = rbl;
+ tree->head = rbl;
+ tree->tail = rbl;
+ }
/* Red-black part of insert */
- rbl->color = RBL_RED;
+ x = rbl;
+ x->color = RBL_RED;
- while(rbl->parent && rbl->parent->color == RBL_RED)
+ while(x != tree->top && x->parent->color == RBL_RED)
{
- if(rbl->parent == rbl->parent->parent->left)
+ if(x->parent == x->parent->parent->left)
{
- y = rbl->parent->parent->right;
- if(y->color == RBL_RED)
+ y = x->parent->parent->right;
+ if(y && y->color == RBL_RED)
{
- rbl->parent->color = RBL_BLACK;
+ x->parent->color = RBL_BLACK;
y->color = RBL_BLACK;
- rbl->parent->parent->color = RBL_RED;
- rbl = rbl->parent->parent;
+ x->parent->parent->color = RBL_RED;
+ x = x->parent->parent;
}
else
{
- if(rbl == rbl->parent->right)
+ if(x == x->parent->right)
{
- rbl = rbl->parent;
- rbl_left_rotate(rbl);
+ x = x->parent;
+ rbl_left_rotate(x);
}
- rbl->parent->color = RBL_BLACK;
- rbl->parent->parent->color = RBL_RED;
- rbl_right_rotate(rbl->parent->parent);
+ x->parent->color = RBL_BLACK;
+ x->parent->parent->color = RBL_RED;
+ rbl_right_rotate(x->parent->parent);
}
}
else
{
- y = rbl->parent->parent->left;
- if(y->color == RBL_RED)
+ y = x->parent->parent->left;
+ if(y && y->color == RBL_RED)
{
- rbl->parent->color = RBL_BLACK;
+ x->parent->color = RBL_BLACK;
y->color = RBL_BLACK;
- rbl->parent->parent->color = RBL_RED;
- rbl = rbl->parent->parent;
+ x->parent->parent->color = RBL_RED;
+ x = x->parent->parent;
}
else
{
- if(rbl == rbl->parent->left)
+ if(x == x->parent->left)
{
- rbl = rbl->parent;
- rbl_right_rotate(rbl);
+ x = x->parent;
+ rbl_right_rotate(x);
}
- rbl->parent->color = RBL_BLACK;
- rbl->parent->parent->color = RBL_RED;
- rbl_left_rotate(rbl->parent->parent);
+ x->parent->color = RBL_BLACK;
+ x->parent->parent->color = RBL_RED;
+ rbl_left_rotate(x->parent->parent);
}
}
}
tree->top->color = RBL_BLACK;
-
return rbl;
}
/* Create a new node and insert it into the tree */
-rbl_t rbl_insert(rbltree_t *tree, void *data)
+rbl_t *rbl_insert(rbltree_t *tree, void *data)
{
rbl_t *rbl;
rbl = new_rbl();
rbl->data = data;
- return rbl_insert_rbl(tree, rbl);
+ if(rbl_insert_rbl(tree, rbl) == rbl)
+ return rbl;
+ else
+ {
+ free_rbl(rbl);
+ return NULL;
+ }
}
/* Restore red-black property after violation due to a deletion */
if(w->color == RBL_RED)
{
w->color = RBL_BLACK;
- x->partent->color = RBL_RED;
+ x->parent->color = RBL_RED;
rbl_left_rotate(x->parent);
w = x->parent->right;
}
if(w->color == RBL_RED)
{
w->color = RBL_BLACK;
- x->partent->color = RBL_RED;
+ x->parent->color = RBL_RED;
rbl_right_rotate(x->parent);
w = x->parent->left;
}
}
/* Unlink node from the tree, but keep the node intact. */
-rbl_t rbl_unlink_rbl(rbl_t *rbl)
+rbl_t *rbl_unlink_rbl(rbl_t *rbl)
{
rbl_t *x, *y;
/* Binary tree delete */
-
+
if(rbl->left && rbl->right)
y = rbl->next;
else
/* Red-black part of delete */
- if(y->color == RBL_BLACK)
+ if(y->color == RBL_BLACK && x)
rbl_delete_fixup(x);
-
+
return rbl;
}
/* Search node in tree and unlink it */
-rbl_t rbl_unlink(rbltree_t *tree, void *data)
+rbl_t *rbl_unlink(rbltree_t *tree, void *data)
{
rbl_t *rbl;
- rbl = rbl_search(tree, data);
+ 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_t *rbl;
+
+ rbl = rbl_unlink(tree, data);
+
+ if(rbl)
+ free_rbl(rbl);
+}
+
+/* Optimized unlinking for a complete tree */
+void rbl_unlink_rbltree(rbltree_t *tree)
+{
+ rbl_t *rbl, *next;
+
+ for(rbl = tree->head; rbl; rbl = next)
+ {
+ next = rbl->next;
+ rbl->tree = NULL;
+ rbl->parent = NULL;
+ rbl->left = NULL;
+ rbl->right = NULL;
+ rbl->prev = NULL;
+ rbl->next = NULL;
+ }
+
+ tree->top = NULL;
+ tree->head = NULL;
+ tree->tail = NULL;
+}
+
+/* Optimized deletion for a complete tree */
+void rbl_delete_rbltree(rbltree_t *tree)
+{
+ rbl_t *rbl, *next;
+
+ for(rbl = tree->head; rbl; rbl = next)
+ {
+ next = rbl->next;
+ free_rbl(rbl);
+ }
+
+ tree->top = NULL;
+ tree->head = NULL;
+ tree->tail = NULL;
}
/* Do action for each list entry (in order)
Deletion of entry for which action is called is allowed.
*/
-void rbl_foreach(rbltree_t *tree, rbl_action_t *action)
+void rbl_foreach(rbltree_t *tree, rbl_action_t action)
+{
+ rbl_t *rbl, *next;
+
+ for(rbl = tree->head; rbl; rbl = next)
+ {
+ next = rbl->next;
+ action(rbl->data);
+ }
+}
+
+void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
{
rbl_t *rbl, *next;
- for(rbl = tree->head; rbl; rbl = next);
+ for(rbl = tree->head; rbl; rbl = next)
{
next = rbl->next;
action(rbl);
projects / tinc / blobdiff