From 880cd6f1a94ef76ebebc5bd96dd26d62e3d829f4 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sat, 18 Nov 2000 23:21:01 +0000 Subject: [PATCH] - Implemented deletions - Added rbl_foreach() function --- lib/rbl.c | 162 ++++++++++++++++++++++++++++++++++++++++++++++++++---- lib/rbl.h | 21 +++++-- 2 files changed, 169 insertions(+), 14 deletions(-) diff --git a/lib/rbl.c b/lib/rbl.c index 88027e86..32e87bbd 100644 --- a/lib/rbl.c +++ b/lib/rbl.c @@ -17,7 +17,7 @@ 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.2 2000/11/18 18:14:57 guus Exp $ + $Id: rbl.c,v 1.1.2.3 2000/11/18 23:21:00 guus Exp $ */ @@ -34,7 +34,7 @@ void free_rbl(rbl_t *rbl) } /* Allocate a new rbltree header */ -rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_delete_t *delete) +rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_action_t *delete) { rbltree_t *tree; @@ -60,7 +60,7 @@ rbl_t rbl_search_closest(rbltree_t *tree, void *data) rbl_t *rbl, *next; int result; - next = rbl = tree->head; + next = rbl = tree->top; while(next) { @@ -85,7 +85,7 @@ rbl_t rbl_search(rbltree_t *tree, void *data) rbl_t *rbl, *next; int result; - next = rbl = tree->head; + next = rbl = tree->top; while(next) { @@ -121,7 +121,7 @@ void rbl_left_rotate(rbl_t *x) y->parent = x->parent; if(!x->parent) - x->tree->head = y; + x->tree->top = y; else if(x == x->parent->left) x->parent->left = y; @@ -145,7 +145,7 @@ void rbl_right_rotate(rbl_t *y) x->parent = y->parent; if(!y->parent) - y->tree->head = x; + y->tree->top = x; else if(y == y->parent->right) y->parent->right = x; @@ -164,7 +164,7 @@ rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl) /* Binary tree and linked list insert */ - if(tree->head) + if(tree->top) { closest = rbl_search_closest(tree, rbl->data); result = tree->compare(rbl->data, data); @@ -188,7 +188,7 @@ rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl) return closest; /* Ofcourse, we cannot add two identical things */ } else - tree->head = rbl; + tree->top = rbl; /* Red-black part of insert */ @@ -242,7 +242,7 @@ rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl) } } - tree->head->color = RBL_BLACK; + tree->top->color = RBL_BLACK; return rbl; } @@ -258,9 +258,137 @@ rbl_t rbl_insert(rbltree_t *tree, void *data) return rbl_insert_rbl(tree, rbl); } -/* Unlink node from the tree, but keep the node intact */ +/* Restore red-black property after violation due to a deletion */ +void rbl_delete_fixup(rbl_t *x) +{ + rbl_t *w; + + while(x != x->tree->top && x->color == RBL_BLACK) + { + if(x == x->parent->left) + { + w = x->parent->right; + if(w->color == RBL_RED) + { + w->color = RBL_BLACK; + x->partent->color = RBL_RED; + rbl_left_rotate(x->parent); + w = x->parent->right; + } + if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK) + { + w->color = RBL_RED; + x = x->parent; + } + else + { + if(w->right->color == RBL_BLACK) + { + w->left->color = RBL_BLACK; + w->color = RBL_RED; + rbl_right_rotate(w); + w = x->parent->right; + } + w->color = x->parent->color; + x->parent->color = RBL_BLACK; + w->right->color = RBL_BLACK; + rbl_left_rotate(x->parent); + x = x->tree->top; + } + } + else + { + w = x->parent->left; + if(w->color == RBL_RED) + { + w->color = RBL_BLACK; + x->partent->color = RBL_RED; + rbl_right_rotate(x->parent); + w = x->parent->left; + } + if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK) + { + w->color = RBL_RED; + x = x->parent; + } + else + { + if(w->left->color == RBL_BLACK) + { + w->right->color = RBL_BLACK; + w->color = RBL_RED; + rbl_left_rotate(w); + w = x->parent->left; + } + w->color = x->parent->color; + x->parent->color = RBL_BLACK; + w->left->color = RBL_BLACK; + rbl_right_rotate(x->parent); + x = x->tree->top; + } + } + } + + x->color = RBL_BLACK; +} + +/* Unlink node from the tree, but keep the node intact. */ rbl_t rbl_unlink_rbl(rbl_t *rbl) { + rbl_t *x, *y; + + /* Binary tree delete */ + + if(rbl->left && rbl->right) + y = rbl->next; + else + y = rbl; + + if(y->left) + x = y->left; + else + x = y->right; + + if(x) + x->parent = y->parent; + + if(!y->parent) + rbl->tree->top = x; + else + if(y == y->parent->left) + y->parent->left = x; + else + y->parent->right = x; + + if(y != rbl) + { + y->left = rbl->left; + y->right = rbl->right; + y->parent = rbl->parent; + if(rbl == rbl->parent->left) + rbl->parent->left = y; + else + rbl->parent->right = y; + } + + /* Linked list delete */ + + if(rbl->prev) + rbl->prev->next = rbl->next; + else + rbl->tree->head = rbl->next; + + if(rbl->next) + rbl->next->prev = rbl->prev; + else + rbl->tree->tail = rbl->prev; + + /* Red-black part of delete */ + + if(y->color == RBL_BLACK) + rbl_delete_fixup(x); + + return rbl; } /* Search node in tree and unlink it */ @@ -287,3 +415,17 @@ void rbl_delete(rbltree_t *tree, void *data) { free_rbl(rbl_unlink(tree, data)); } + +/* 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) +{ + rbl_t *rbl, *next; + + for(rbl = tree->head; rbl; rbl = next); + { + next = rbl->next; + action(rbl); + } +} diff --git a/lib/rbl.h b/lib/rbl.h index bd9ecda3..ff81c1bf 100644 --- a/lib/rbl.h +++ b/lib/rbl.h @@ -17,11 +17,11 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: rbl.h,v 1.1.2.2 2000/11/18 18:14:57 guus Exp $ + $Id: rbl.h,v 1.1.2.3 2000/11/18 23:21:01 guus Exp $ */ typedef int (*rbl_compare_t) (const void *, const void *); -typedef void (*rbl_delete_t) (const void *); +typedef void (*rbl_action_t) (const void *); typedef struct rbl_t { @@ -48,9 +48,20 @@ typedef struct rbl_t typedef struct rbltree_t { + /* callback functions */ + rbl_compare_t *compare; - rbl_delete_t *delete; + rbl_action_t *delete; + + /* tree part */ + + struct rbl_t *top; + + /* linked list */ + struct rbl_t *head; + struct rbl_t *tail; + } rbltree_t; enum @@ -59,7 +70,7 @@ enum RBL_BLACK; }; -extern rbl_t *new_rbltree(rbl_compare_t *, rbl_delete_t *); +extern rbl_t *new_rbltree(rbl_compare_t *, rbl_action_t *); extern void free_rbltree(rbltree_t *); extern rbl_t *new_rbl(void); extern void free_rbl(rbl_t *); @@ -72,3 +83,5 @@ extern rbl_t *rbl_delete(rbltree_t *, void *); extern rbl_t *rbl_insert_rbl(rbltree_t *, rbl_t *); extern rbl_t *rbl_unlink_rbl(rbltree_t *, rbl_t *); extern rbl_t *rbl_delete_rbl(rbltree_t *, rbl_t *); + +extern void rbl_foreach(rbltree_t *, rbl_action_t *); -- 2.39.5