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.10 2000/11/22 18:54:07 guus Exp $
32 /* Allocate a new rbl node */
35 return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
39 void free_rbl(rbl_t *rbl)
41 if(rbl->data && rbl->tree->delete)
42 rbl->tree->delete(rbl->data);
46 /* Allocate a new rbltree header */
47 rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
51 tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
54 tree->compare = compare;
55 tree->delete = delete;
61 /* Free a rbltree header */
62 void free_rbltree(rbltree_t *tree)
67 /* Search closest match in the tree */
68 rbl_t *rbl_search_closest_rbl(rbltree_t *tree, void *data)
73 next = rbl = tree->top;
79 result = tree->compare(data, rbl->data);
92 void *rbl_search_closest(rbltree_t *tree, void *data)
96 rbl = rbl_search_closest_rbl(tree, data);
104 /* Search exact match or return NULL pointer */
105 rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
114 result = tree->compare(data, rbl->data);
127 void *rbl_search(rbltree_t *tree, void *data)
131 rbl = rbl_search_rbl(tree, data);
139 /* Red-black tree operations taken from Introduction to Algorithms,
140 Cormen, Leiserson & Rivest, chapter 14.
143 void rbl_left_rotate(rbl_t *x)
153 y->parent = x->parent;
158 if(x == x->parent->left)
161 x->parent->right = y;
167 void rbl_right_rotate(rbl_t *y)
175 x->right->parent = y;
177 x->parent = y->parent;
182 if(y == y->parent->right)
183 y->parent->right = x;
191 /* Insert a node into the rbl tree */
192 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
194 rbl_t *closest, *x, *y;
199 /* Binary tree and linked list insert */
203 closest = rbl_search_closest_rbl(tree, rbl->data);
204 result = tree->compare(rbl->data, closest->data);
209 rbl->prev = closest->prev;
214 rbl->prev->next = rbl;
220 closest->right = rbl;
222 rbl->next = closest->next;
227 rbl->next->prev = rbl;
232 return closest; /* Ofcourse, we cannot add two identical things */
234 rbl->parent = closest;
243 /* Red-black part of insert */
248 while(x != tree->top && x->parent->color == RBL_RED)
250 if(x->parent == x->parent->parent->left)
252 y = x->parent->parent->right;
253 if(y && y->color == RBL_RED)
255 x->parent->color = RBL_BLACK;
256 y->color = RBL_BLACK;
257 x->parent->parent->color = RBL_RED;
258 x = x->parent->parent;
262 if(x == x->parent->right)
267 x->parent->color = RBL_BLACK;
268 x->parent->parent->color = RBL_RED;
269 rbl_right_rotate(x->parent->parent);
274 y = x->parent->parent->left;
275 if(y && y->color == RBL_RED)
277 x->parent->color = RBL_BLACK;
278 y->color = RBL_BLACK;
279 x->parent->parent->color = RBL_RED;
280 x = x->parent->parent;
284 if(x == x->parent->left)
289 x->parent->color = RBL_BLACK;
290 x->parent->parent->color = RBL_RED;
291 rbl_left_rotate(x->parent->parent);
296 tree->top->color = RBL_BLACK;
300 /* Create a new node and insert it into the tree */
301 rbl_t *rbl_insert(rbltree_t *tree, void *data)
308 if(rbl_insert_rbl(tree, rbl) == rbl)
317 /* Restore red-black property after violation due to a deletion */
318 void rbl_delete_fixup(rbl_t *x)
322 while(x != x->tree->top && x->color == RBL_BLACK)
324 if(x == x->parent->left)
326 w = x->parent->right;
327 if(w->color == RBL_RED)
329 w->color = RBL_BLACK;
330 x->parent->color = RBL_RED;
331 rbl_left_rotate(x->parent);
332 w = x->parent->right;
334 if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
341 if(w->right->color == RBL_BLACK)
343 w->left->color = RBL_BLACK;
346 w = x->parent->right;
348 w->color = x->parent->color;
349 x->parent->color = RBL_BLACK;
350 w->right->color = RBL_BLACK;
351 rbl_left_rotate(x->parent);
358 if(w->color == RBL_RED)
360 w->color = RBL_BLACK;
361 x->parent->color = RBL_RED;
362 rbl_right_rotate(x->parent);
365 if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
372 if(w->left->color == RBL_BLACK)
374 w->right->color = RBL_BLACK;
379 w->color = x->parent->color;
380 x->parent->color = RBL_BLACK;
381 w->left->color = RBL_BLACK;
382 rbl_right_rotate(x->parent);
388 x->color = RBL_BLACK;
391 /* Unlink node from the tree, but keep the node intact. */
392 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
396 /* Binary tree delete */
398 if(rbl->left && rbl->right)
409 x->parent = y->parent;
414 if(y == y->parent->left)
417 y->parent->right = x;
422 y->right = rbl->right;
423 y->parent = rbl->parent;
424 if(rbl == rbl->parent->left)
425 rbl->parent->left = y;
427 rbl->parent->right = y;
430 /* Linked list delete */
433 rbl->prev->next = rbl->next;
435 rbl->tree->head = rbl->next;
438 rbl->next->prev = rbl->prev;
440 rbl->tree->tail = rbl->prev;
442 /* Red-black part of delete */
444 if(y->color == RBL_BLACK && x)
450 /* Search node in tree and unlink it */
451 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
455 rbl = rbl_search_rbl(tree, data);
463 /* Unlink node and free it */
464 void rbl_delete_rbl(rbl_t *rbl)
470 /* Search node in tree, unlink and free it */
471 void rbl_delete(rbltree_t *tree, void *data)
475 rbl = rbl_unlink(tree, data);
481 /* Optimized unlinking for a complete tree */
482 void rbl_unlink_rbltree(rbltree_t *tree)
486 for(rbl = tree->head; rbl; rbl = next)
502 /* Optimized deletion for a complete tree */
503 void rbl_delete_rbltree(rbltree_t *tree)
507 for(rbl = tree->head; rbl; rbl = next)
518 /* Do action for each list entry (in order)
519 Deletion of entry for which action is called is allowed.
521 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
525 for(rbl = tree->head; rbl; rbl = next)
532 void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
536 for(rbl = tree->head; rbl; rbl = next)