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.8 2000/11/20 19:12:10 guus Exp $
28 /* Allocate a new rbl node */
31 return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
35 void free_rbl(rbl_t *rbl)
40 /* Allocate a new rbltree header */
41 rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
45 tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
48 tree->compare = compare;
49 tree->delete = delete;
55 /* Free a rbltree header */
56 void free_rbltree(rbltree_t *tree)
61 /* Search closest match in the tree */
62 rbl_t *rbl_search_closest_rbl(rbltree_t *tree, void *data)
67 next = rbl = tree->top;
73 result = tree->compare(data, rbl->data);
86 void *rbl_search_closest(rbltree_t *tree, void *data)
88 return rbl_search_closest_rbl(tree, data)->data;
91 /* Search exact match or return NULL pointer */
92 rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
97 next = rbl = tree->top;
103 result = tree->compare(data, rbl->data);
116 void *rbl_search(rbltree_t *tree, void *data)
120 rbl = rbl_search_rbl(tree, data);
128 /* Red-black tree operations taken from Introduction to Algorithms,
129 Cormen, Leiserson & Rivest, chapter 14.
132 void rbl_left_rotate(rbl_t *x)
142 y->parent = x->parent;
147 if(x == x->parent->left)
150 x->parent->right = y;
156 void rbl_right_rotate(rbl_t *y)
164 x->right->parent = y;
166 x->parent = y->parent;
171 if(y == y->parent->right)
172 y->parent->right = x;
180 /* Insert a node into the rbl tree */
181 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
183 rbl_t *closest, *x, *y;
188 /* Binary tree and linked list insert */
192 closest = rbl_search_closest_rbl(tree, rbl->data);
193 result = tree->compare(rbl->data, closest->data);
198 rbl->prev = closest->prev;
203 rbl->prev->next = rbl;
209 closest->right = rbl;
211 rbl->next = closest->next;
216 rbl->next->prev = rbl;
221 return closest; /* Ofcourse, we cannot add two identical things */
223 rbl->parent = closest;
232 /* Red-black part of insert */
237 while(x != tree->top && x->parent->color == RBL_RED)
239 if(x->parent == x->parent->parent->left)
241 y = x->parent->parent->right;
242 if(y && y->color == RBL_RED)
244 x->parent->color = RBL_BLACK;
245 y->color = RBL_BLACK;
246 x->parent->parent->color = RBL_RED;
247 x = x->parent->parent;
251 if(x == x->parent->right)
256 x->parent->color = RBL_BLACK;
257 x->parent->parent->color = RBL_RED;
258 rbl_right_rotate(x->parent->parent);
263 y = x->parent->parent->left;
264 if(y && y->color == RBL_RED)
266 x->parent->color = RBL_BLACK;
267 y->color = RBL_BLACK;
268 x->parent->parent->color = RBL_RED;
269 x = x->parent->parent;
273 if(x == x->parent->left)
278 x->parent->color = RBL_BLACK;
279 x->parent->parent->color = RBL_RED;
280 rbl_left_rotate(x->parent->parent);
285 tree->top->color = RBL_BLACK;
289 /* Create a new node and insert it into the tree */
290 rbl_t *rbl_insert(rbltree_t *tree, void *data)
297 if(rbl_insert_rbl(tree, rbl) == rbl)
306 /* Restore red-black property after violation due to a deletion */
307 void rbl_delete_fixup(rbl_t *x)
311 while(x != x->tree->top && x->color == RBL_BLACK)
313 if(x == x->parent->left)
315 w = x->parent->right;
316 if(w->color == RBL_RED)
318 w->color = RBL_BLACK;
319 x->parent->color = RBL_RED;
320 rbl_left_rotate(x->parent);
321 w = x->parent->right;
323 if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
330 if(w->right->color == RBL_BLACK)
332 w->left->color = RBL_BLACK;
335 w = x->parent->right;
337 w->color = x->parent->color;
338 x->parent->color = RBL_BLACK;
339 w->right->color = RBL_BLACK;
340 rbl_left_rotate(x->parent);
347 if(w->color == RBL_RED)
349 w->color = RBL_BLACK;
350 x->parent->color = RBL_RED;
351 rbl_right_rotate(x->parent);
354 if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
361 if(w->left->color == RBL_BLACK)
363 w->right->color = RBL_BLACK;
368 w->color = x->parent->color;
369 x->parent->color = RBL_BLACK;
370 w->left->color = RBL_BLACK;
371 rbl_right_rotate(x->parent);
377 x->color = RBL_BLACK;
380 /* Unlink node from the tree, but keep the node intact. */
381 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
385 /* Binary tree delete */
387 if(rbl->left && rbl->right)
398 x->parent = y->parent;
403 if(y == y->parent->left)
406 y->parent->right = x;
411 y->right = rbl->right;
412 y->parent = rbl->parent;
413 if(rbl == rbl->parent->left)
414 rbl->parent->left = y;
416 rbl->parent->right = y;
419 /* Linked list delete */
422 rbl->prev->next = rbl->next;
424 rbl->tree->head = rbl->next;
427 rbl->next->prev = rbl->prev;
429 rbl->tree->tail = rbl->prev;
431 /* Red-black part of delete */
433 if(y->color == RBL_BLACK && x)
439 /* Search node in tree and unlink it */
440 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
444 rbl = rbl_search_rbl(tree, data);
447 return rbl_unlink_rbl(rbl);
452 /* Unlink node and free it */
453 void rbl_delete_rbl(rbl_t *rbl)
455 free_rbl(rbl_unlink_rbl(rbl));
458 /* Search node in tree, unlink and free it */
459 void rbl_delete(rbltree_t *tree, void *data)
461 free_rbl(rbl_unlink(tree, data));
464 rbl_unlink_rbltree_branch(rbl_t *rbl)
467 rbl_unlink_rbltree_branch(rbl->left);
470 rbl_unlink_rbltree_branch(rbl->right);
474 if(rbl == rbl->parent->left)
475 rbl->parent->left = NULL;
477 rbl->parent->right = NULL;
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)
510 tree->delete(rbl->data);
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)