From 00e5d572621ad5f0263999dbfbfcb11e023bf48b Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sat, 18 Nov 2000 18:14:57 +0000 Subject: [PATCH] - Fixed searching - Insertion implemented --- lib/rbl.c | 234 ++++++++++++++++++++++++++++++++++++++++++++++++++---- lib/rbl.h | 25 +++--- 2 files changed, 233 insertions(+), 26 deletions(-) diff --git a/lib/rbl.c b/lib/rbl.c index 765236c2..88027e86 100644 --- a/lib/rbl.c +++ b/lib/rbl.c @@ -17,37 +17,57 @@ 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.1 2000/11/16 09:18:38 guus Exp $ + $Id: rbl.c,v 1.1.2.2 2000/11/18 18:14:57 guus Exp $ */ -rbl_t *new_rbl(rbltree_t *tree) + +/* Allocate a new rbl node */ +rbl_t *new_rbl() { - rbl_t *rbl; + return (rbl_t *)xmalloc_and_zero(sizeof(*rbl)); +} + +/* Free a rbl node */ +void free_rbl(rbl_t *rbl) +{ + free(rbl); +} - rbl = xmalloc(sizeof(*rbl)); +/* Allocate a new rbltree header */ +rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_delete_t *delete) +{ + rbltree_t *tree; - if(rbl) + tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t)); + if(tree) { - memset(rbl, 0, sizeof(*rbl)); - rbl->tree = tree; + tree->compare = compare; + tree->delete = delete; } - - return rbl; + + return tree; } -void free_rbl(rbl_t *rbl) +/* Free a rbltree header */ +void free_rbltree(rbltree_t *tree) { - free(rbl); + free(tree); } +/* Search closest match in the tree */ rbl_t rbl_search_closest(rbltree_t *tree, void *data) { rbl_t *rbl, *next; int result; - for(next = rbltree->head; next; next = rbl) + next = rbl = tree->head; + + while(next) { - result = rbltree->compare(rbl->data, data) + rbl = next; + + result = tree->compare(rbl->data, data); + if(result < 0) next = rbl->left; else if(result > 0) @@ -59,14 +79,20 @@ rbl_t rbl_search_closest(rbltree_t *tree, void *data) return rbl; } +/* Search exact match or return NULL pointer */ rbl_t rbl_search(rbltree_t *tree, void *data) { rbl_t *rbl, *next; int result; - for(next = rbltree->head; next; next = rbl) + next = rbl = tree->head; + + while(next) { - result = rbltree->compare(rbl->data, data) + rbl = next; + + result = tree->compare(rbl->data, data); + if(result < 0) next = rbl->left; else if(result > 0) @@ -78,8 +104,186 @@ rbl_t rbl_search(rbltree_t *tree, void *data) return NULL; } +/* Red-black tree operations taken from Introduction to Algorithms, + Cormen, Leiserson & Rivest, chapter 14. +*/ + +void rbl_left_rotate(rbl_t *x) +{ + rbl_t *y; + + y = x->right; + x->right = y->left; + + if(y->left) + y->left->parent = x; + + y->parent = x->parent; + + if(!x->parent) + x->tree->head = y; + else + if(x == x->parent->left) + 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; + + if(x->right) + x->right->parent = y; + + x->parent = y->parent; + + if(!y->parent) + y->tree->head = x; + else + if(y == y->parent->right) + y->parent->right = x; + else + y->parent->left = x; + + x->right = y; + y->parent = x; +} + +/* Insert a node into the rbl tree */ +rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl) +{ + rbl_t *closest, y; + int result; + + /* Binary tree and linked list insert */ + + if(tree->head) + { + closest = rbl_search_closest(tree, rbl->data); + result = tree->compare(rbl->data, data); + if(result < 0) + { + closest->left = rbl; + rbl->prev = closest->prev; + rbl->next = closest; + closest->prev = rbl; + rbl->prev->next = rbl; + } + else if(result > 0) + { + closest->right = rbl; + rbl->next = closest->right; + rbl->prev = closest; + closest->next = rbl; + rbl->next->prev = rbl; + } + else + return closest; /* Ofcourse, we cannot add two identical things */ + } + else + tree->head = rbl; + + /* Red-black part of insert */ + + rbl->color = RBL_RED; + + while(rbl->parent && rbl->parent->color == RBL_RED) + { + if(rbl->parent == rbl->parent->parent->left) + { + y = rbl->parent->parent->right; + if(y->color == RBL_RED) + { + rbl->parent->color = RBL_BLACK; + y->color = RBL_BLACK; + rbl->parent->parent->color = RBL_RED; + rbl = rbl->parent->parent; + } + else + { + if(rbl == rbl->parent->right) + { + rbl = rbl->parent; + rbl_left_rotate(rbl); + } + rbl->parent->color = RBL_BLACK; + rbl->parent->parent->color = RBL_RED; + rbl_right_rotate(rbl->parent->parent); + } + } + else + { + y = rbl->parent->parent->left; + if(y->color == RBL_RED) + { + rbl->parent->color = RBL_BLACK; + y->color = RBL_BLACK; + rbl->parent->parent->color = RBL_RED; + rbl = rbl->parent->parent; + } + else + { + if(rbl == rbl->parent->left) + { + rbl = rbl->parent; + rbl_right_rotate(rbl); + } + rbl->parent->color = RBL_BLACK; + rbl->parent->parent->color = RBL_RED; + rbl_left_rotate(rbl->parent->parent); + } + } + } + + tree->head->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; + rbl = new_rbl(); + rbl->data = data; + + return rbl_insert_rbl(tree, rbl); +} + +/* Unlink node from the tree, but keep the node intact */ +rbl_t rbl_unlink_rbl(rbl_t *rbl) +{ +} + +/* Search node in tree and unlink it */ +rbl_t rbl_unlink(rbltree_t *tree, void *data) +{ + rbl_t *rbl; + + rbl = rbl_search(tree, data); + + if(rbl) + return rbl_unlink_rbl(rbl); + else + return NULL; +} + +/* Unlink node and free it */ +void rbl_delete_rbl(rbl_t *rbl) +{ + free_rbl(rbl_unlink_rbl(rbl)); +} + +/* Search node in tree, unlink and free it */ +void rbl_delete(rbltree_t *tree, void *data) +{ + free_rbl(rbl_unlink(tree, data)); } diff --git a/lib/rbl.h b/lib/rbl.h index 40a1c69d..bd9ecda3 100644 --- a/lib/rbl.h +++ b/lib/rbl.h @@ -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.h,v 1.1.2.1 2000/11/16 09:18:38 guus Exp $ + $Id: rbl.h,v 1.1.2.2 2000/11/18 18:14:57 guus Exp $ */ typedef int (*rbl_compare_t) (const void *, const void *); @@ -59,13 +59,16 @@ enum RBL_BLACK; }; -extern rbl_t rbl_search(rbltree_t *, void *); -extern rbl_t rbl_search_closest(rbltree_t *, void *); -extern rbl_t rbl_insert(rbltree_t *, void *); -extern rbl_t rbl_unlink(rbltree_t *, void *); -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 rbl_t rbl_prev(rbl_t *); -extern rbl_t rbl_next(rbl_t *); +extern rbl_t *new_rbltree(rbl_compare_t *, rbl_delete_t *); +extern void free_rbltree(rbltree_t *); +extern rbl_t *new_rbl(void); +extern void free_rbl(rbl_t *); + +extern rbl_t *rbl_search(rbltree_t *, void *); +extern rbl_t *rbl_search_closest(rbltree_t *, void *); +extern rbl_t *rbl_insert(rbltree_t *, void *); +extern rbl_t *rbl_unlink(rbltree_t *, void *); +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 *); -- 2.39.5