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.7 2000/11/19 22:12:46 guus Exp $
27 /* Allocate a new rbl node */
30 return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
34 void free_rbl(rbl_t *rbl)
39 /* Allocate a new rbltree header */
40 rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
44 tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
47 tree->compare = compare;
48 tree->delete = delete;
54 /* Free a rbltree header */
55 void free_rbltree(rbltree_t *tree)
60 /* Search closest match in the tree */
61 rbl_t *rbl_search_closest_rbl(rbltree_t *tree, void *data)
66 next = rbl = tree->top;
72 result = tree->compare(data, rbl->data);
85 void *rbl_search_closest(rbltree_t *tree, void *data)
87 return rbl_search_closest_rbl(tree, data)->data;
90 /* Search exact match or return NULL pointer */
91 rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
96 next = rbl = tree->top;
102 result = tree->compare(data, rbl->data);
115 void *rbl_search(rbltree_t *tree, void *data)
119 rbl = rbl_search_rbl(tree, data);
127 /* Red-black tree operations taken from Introduction to Algorithms,
128 Cormen, Leiserson & Rivest, chapter 14.
131 void rbl_left_rotate(rbl_t *x)
141 y->parent = x->parent;
146 if(x == x->parent->left)
149 x->parent->right = y;
155 void rbl_right_rotate(rbl_t *y)
163 x->right->parent = y;
165 x->parent = y->parent;
170 if(y == y->parent->right)
171 y->parent->right = x;
179 /* Insert a node into the rbl tree */
180 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
182 rbl_t *closest, *x, *y;
187 /* Binary tree and linked list insert */
191 closest = rbl_search_closest_rbl(tree, rbl->data);
192 result = tree->compare(rbl->data, closest->data);
197 rbl->prev = closest->prev;
202 rbl->prev->next = rbl;
208 closest->right = rbl;
210 rbl->next = closest->next;
215 rbl->next->prev = rbl;
220 return closest; /* Ofcourse, we cannot add two identical things */
222 rbl->parent = closest;
231 /* Red-black part of insert */
236 while(x != tree->top && x->parent->color == RBL_RED)
238 if(x->parent == x->parent->parent->left)
240 y = x->parent->parent->right;
241 if(y && y->color == RBL_RED)
243 x->parent->color = RBL_BLACK;
244 y->color = RBL_BLACK;
245 x->parent->parent->color = RBL_RED;
246 x = x->parent->parent;
250 if(x == x->parent->right)
255 x->parent->color = RBL_BLACK;
256 x->parent->parent->color = RBL_RED;
257 rbl_right_rotate(x->parent->parent);
262 y = x->parent->parent->left;
263 if(y && y->color == RBL_RED)
265 x->parent->color = RBL_BLACK;
266 y->color = RBL_BLACK;
267 x->parent->parent->color = RBL_RED;
268 x = x->parent->parent;
272 if(x == x->parent->left)
277 x->parent->color = RBL_BLACK;
278 x->parent->parent->color = RBL_RED;
279 rbl_left_rotate(x->parent->parent);
284 tree->top->color = RBL_BLACK;
288 /* Create a new node and insert it into the tree */
289 rbl_t *rbl_insert(rbltree_t *tree, void *data)
296 if(rbl_insert_rbl(tree, rbl) == rbl)
305 /* Restore red-black property after violation due to a deletion */
306 void rbl_delete_fixup(rbl_t *x)
310 while(x != x->tree->top && x->color == RBL_BLACK)
312 if(x == x->parent->left)
314 w = x->parent->right;
315 if(w->color == RBL_RED)
317 w->color = RBL_BLACK;
318 x->parent->color = RBL_RED;
319 rbl_left_rotate(x->parent);
320 w = x->parent->right;
322 if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
329 if(w->right->color == RBL_BLACK)
331 w->left->color = RBL_BLACK;
334 w = x->parent->right;
336 w->color = x->parent->color;
337 x->parent->color = RBL_BLACK;
338 w->right->color = RBL_BLACK;
339 rbl_left_rotate(x->parent);
346 if(w->color == RBL_RED)
348 w->color = RBL_BLACK;
349 x->parent->color = RBL_RED;
350 rbl_right_rotate(x->parent);
353 if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
360 if(w->left->color == RBL_BLACK)
362 w->right->color = RBL_BLACK;
367 w->color = x->parent->color;
368 x->parent->color = RBL_BLACK;
369 w->left->color = RBL_BLACK;
370 rbl_right_rotate(x->parent);
376 x->color = RBL_BLACK;
379 /* Unlink node from the tree, but keep the node intact. */
380 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
384 /* Binary tree delete */
386 if(rbl->left && rbl->right)
397 x->parent = y->parent;
402 if(y == y->parent->left)
405 y->parent->right = x;
410 y->right = rbl->right;
411 y->parent = rbl->parent;
412 if(rbl == rbl->parent->left)
413 rbl->parent->left = y;
415 rbl->parent->right = y;
418 /* Linked list delete */
421 rbl->prev->next = rbl->next;
423 rbl->tree->head = rbl->next;
426 rbl->next->prev = rbl->prev;
428 rbl->tree->tail = rbl->prev;
430 /* Red-black part of delete */
432 if(y->color == RBL_BLACK && x)
438 /* Search node in tree and unlink it */
439 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
443 rbl = rbl_search_rbl(tree, data);
446 return rbl_unlink_rbl(rbl);
451 /* Unlink node and free it */
452 void rbl_delete_rbl(rbl_t *rbl)
454 free_rbl(rbl_unlink_rbl(rbl));
457 /* Search node in tree, unlink and free it */
458 void rbl_delete(rbltree_t *tree, void *data)
460 free_rbl(rbl_unlink(tree, data));
463 rbl_unlink_rbltree_branch(rbl_t *rbl)
466 rbl_unlink_rbltree_branch(rbl->left);
469 rbl_unlink_rbltree_branch(rbl->right);
473 if(rbl == rbl->parent->left)
474 rbl->parent->left = NULL;
476 rbl->parent->right = NULL;
480 /* Optimized unlinking for a complete tree */
481 void rbl_unlink_rbltree(rbltree_t *tree)
485 for(rbl = tree->head; rbl; rbl = next)
501 /* Optimized deletion for a complete tree */
502 void rbl_delete_rbltree(rbltree_t *tree)
506 for(rbl = tree->head; rbl; rbl = next)
509 tree->delete(rbl->data);
517 /* Do action for each list entry (in order)
518 Deletion of entry for which action is called is allowed.
520 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
524 for(rbl = tree->head; rbl; rbl = next)
531 void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
535 for(rbl = tree->head; rbl; rbl = next)