2 rbl.c -- red-black tree + linked list convenience
3 Copyright (C) 2000 Ivo Timmermans <itimmermans@bigfoot.com>,
4 2000 Guus Sliepen <guus@sliepen.warande.net>
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 $Id: rbl.c,v 1.1.2.2 2000/11/18 18:14:57 guus Exp $
24 /* Allocate a new rbl node */
27 return (rbl_t *)xmalloc_and_zero(sizeof(*rbl));
31 void free_rbl(rbl_t *rbl)
36 /* Allocate a new rbltree header */
37 rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_delete_t *delete)
41 tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
44 tree->compare = compare;
45 tree->delete = delete;
51 /* Free a rbltree header */
52 void free_rbltree(rbltree_t *tree)
57 /* Search closest match in the tree */
58 rbl_t rbl_search_closest(rbltree_t *tree, void *data)
63 next = rbl = tree->head;
69 result = tree->compare(rbl->data, data);
82 /* Search exact match or return NULL pointer */
83 rbl_t rbl_search(rbltree_t *tree, void *data)
88 next = rbl = tree->head;
94 result = tree->compare(rbl->data, data);
107 /* Red-black tree operations taken from Introduction to Algorithms,
108 Cormen, Leiserson & Rivest, chapter 14.
111 void rbl_left_rotate(rbl_t *x)
121 y->parent = x->parent;
126 if(x == x->parent->left)
129 x->parent->right = y;
135 void rbl_right_rotate(rbl_t *y)
143 x->right->parent = y;
145 x->parent = y->parent;
150 if(y == y->parent->right)
151 y->parent->right = x;
159 /* Insert a node into the rbl tree */
160 rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
165 /* Binary tree and linked list insert */
169 closest = rbl_search_closest(tree, rbl->data);
170 result = tree->compare(rbl->data, data);
174 rbl->prev = closest->prev;
177 rbl->prev->next = rbl;
181 closest->right = rbl;
182 rbl->next = closest->right;
185 rbl->next->prev = rbl;
188 return closest; /* Ofcourse, we cannot add two identical things */
193 /* Red-black part of insert */
195 rbl->color = RBL_RED;
197 while(rbl->parent && rbl->parent->color == RBL_RED)
199 if(rbl->parent == rbl->parent->parent->left)
201 y = rbl->parent->parent->right;
202 if(y->color == RBL_RED)
204 rbl->parent->color = RBL_BLACK;
205 y->color = RBL_BLACK;
206 rbl->parent->parent->color = RBL_RED;
207 rbl = rbl->parent->parent;
211 if(rbl == rbl->parent->right)
214 rbl_left_rotate(rbl);
216 rbl->parent->color = RBL_BLACK;
217 rbl->parent->parent->color = RBL_RED;
218 rbl_right_rotate(rbl->parent->parent);
223 y = rbl->parent->parent->left;
224 if(y->color == RBL_RED)
226 rbl->parent->color = RBL_BLACK;
227 y->color = RBL_BLACK;
228 rbl->parent->parent->color = RBL_RED;
229 rbl = rbl->parent->parent;
233 if(rbl == rbl->parent->left)
236 rbl_right_rotate(rbl);
238 rbl->parent->color = RBL_BLACK;
239 rbl->parent->parent->color = RBL_RED;
240 rbl_left_rotate(rbl->parent->parent);
245 tree->head->color = RBL_BLACK;
250 /* Create a new node and insert it into the tree */
251 rbl_t rbl_insert(rbltree_t *tree, void *data)
258 return rbl_insert_rbl(tree, rbl);
261 /* Unlink node from the tree, but keep the node intact */
262 rbl_t rbl_unlink_rbl(rbl_t *rbl)
266 /* Search node in tree and unlink it */
267 rbl_t rbl_unlink(rbltree_t *tree, void *data)
271 rbl = rbl_search(tree, data);
274 return rbl_unlink_rbl(rbl);
279 /* Unlink node and free it */
280 void rbl_delete_rbl(rbl_t *rbl)
282 free_rbl(rbl_unlink_rbl(rbl));
285 /* Search node in tree, unlink and free it */
286 void rbl_delete(rbltree_t *tree, void *data)
288 free_rbl(rbl_unlink(tree, data));