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.9 2000/11/21 09:13:59 guus Exp $
31 /* Allocate a new rbl node */
34 return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
38 void free_rbl(rbl_t *rbl)
40 if(rbl->data && rbl->tree->delete)
41 rbl->tree->delete(rbl->data);
45 /* Allocate a new rbltree header */
46 rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
50 tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
53 tree->compare = compare;
54 tree->delete = delete;
60 /* Free a rbltree header */
61 void free_rbltree(rbltree_t *tree)
66 /* Search closest match in the tree */
67 rbl_t *rbl_search_closest_rbl(rbltree_t *tree, void *data)
72 next = rbl = tree->top;
78 result = tree->compare(data, rbl->data);
91 void *rbl_search_closest(rbltree_t *tree, void *data)
93 return rbl_search_closest_rbl(tree, data)->data;
96 /* Search exact match or return NULL pointer */
97 rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
102 next = rbl = tree->top;
108 result = tree->compare(data, rbl->data);
121 void *rbl_search(rbltree_t *tree, void *data)
125 rbl = rbl_search_rbl(tree, data);
133 /* Red-black tree operations taken from Introduction to Algorithms,
134 Cormen, Leiserson & Rivest, chapter 14.
137 void rbl_left_rotate(rbl_t *x)
147 y->parent = x->parent;
152 if(x == x->parent->left)
155 x->parent->right = y;
161 void rbl_right_rotate(rbl_t *y)
169 x->right->parent = y;
171 x->parent = y->parent;
176 if(y == y->parent->right)
177 y->parent->right = x;
185 /* Insert a node into the rbl tree */
186 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
188 rbl_t *closest, *x, *y;
193 /* Binary tree and linked list insert */
197 closest = rbl_search_closest_rbl(tree, rbl->data);
198 result = tree->compare(rbl->data, closest->data);
203 rbl->prev = closest->prev;
208 rbl->prev->next = rbl;
214 closest->right = rbl;
216 rbl->next = closest->next;
221 rbl->next->prev = rbl;
226 return closest; /* Ofcourse, we cannot add two identical things */
228 rbl->parent = closest;
237 /* Red-black part of insert */
242 while(x != tree->top && x->parent->color == RBL_RED)
244 if(x->parent == x->parent->parent->left)
246 y = x->parent->parent->right;
247 if(y && y->color == RBL_RED)
249 x->parent->color = RBL_BLACK;
250 y->color = RBL_BLACK;
251 x->parent->parent->color = RBL_RED;
252 x = x->parent->parent;
256 if(x == x->parent->right)
261 x->parent->color = RBL_BLACK;
262 x->parent->parent->color = RBL_RED;
263 rbl_right_rotate(x->parent->parent);
268 y = x->parent->parent->left;
269 if(y && y->color == RBL_RED)
271 x->parent->color = RBL_BLACK;
272 y->color = RBL_BLACK;
273 x->parent->parent->color = RBL_RED;
274 x = x->parent->parent;
278 if(x == x->parent->left)
283 x->parent->color = RBL_BLACK;
284 x->parent->parent->color = RBL_RED;
285 rbl_left_rotate(x->parent->parent);
290 tree->top->color = RBL_BLACK;
294 /* Create a new node and insert it into the tree */
295 rbl_t *rbl_insert(rbltree_t *tree, void *data)
302 if(rbl_insert_rbl(tree, rbl) == rbl)
311 /* Restore red-black property after violation due to a deletion */
312 void rbl_delete_fixup(rbl_t *x)
316 while(x != x->tree->top && x->color == RBL_BLACK)
318 if(x == x->parent->left)
320 w = x->parent->right;
321 if(w->color == RBL_RED)
323 w->color = RBL_BLACK;
324 x->parent->color = RBL_RED;
325 rbl_left_rotate(x->parent);
326 w = x->parent->right;
328 if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
335 if(w->right->color == RBL_BLACK)
337 w->left->color = RBL_BLACK;
340 w = x->parent->right;
342 w->color = x->parent->color;
343 x->parent->color = RBL_BLACK;
344 w->right->color = RBL_BLACK;
345 rbl_left_rotate(x->parent);
352 if(w->color == RBL_RED)
354 w->color = RBL_BLACK;
355 x->parent->color = RBL_RED;
356 rbl_right_rotate(x->parent);
359 if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
366 if(w->left->color == RBL_BLACK)
368 w->right->color = RBL_BLACK;
373 w->color = x->parent->color;
374 x->parent->color = RBL_BLACK;
375 w->left->color = RBL_BLACK;
376 rbl_right_rotate(x->parent);
382 x->color = RBL_BLACK;
385 /* Unlink node from the tree, but keep the node intact. */
386 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
390 /* Binary tree delete */
392 if(rbl->left && rbl->right)
403 x->parent = y->parent;
408 if(y == y->parent->left)
411 y->parent->right = x;
416 y->right = rbl->right;
417 y->parent = rbl->parent;
418 if(rbl == rbl->parent->left)
419 rbl->parent->left = y;
421 rbl->parent->right = y;
424 /* Linked list delete */
427 rbl->prev->next = rbl->next;
429 rbl->tree->head = rbl->next;
432 rbl->next->prev = rbl->prev;
434 rbl->tree->tail = rbl->prev;
436 /* Red-black part of delete */
438 if(y->color == RBL_BLACK && x)
444 /* Search node in tree and unlink it */
445 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
449 rbl = rbl_search_rbl(tree, data);
452 return rbl_unlink_rbl(rbl);
457 /* Unlink node and free it */
458 void rbl_delete_rbl(rbl_t *rbl)
460 free_rbl(rbl_unlink_rbl(rbl));
463 /* Search node in tree, unlink and free it */
464 void rbl_delete(rbltree_t *tree, void *data)
466 free_rbl(rbl_unlink(tree, data));
469 rbl_unlink_rbltree_branch(rbl_t *rbl)
472 rbl_unlink_rbltree_branch(rbl->left);
475 rbl_unlink_rbltree_branch(rbl->right);
479 if(rbl == rbl->parent->left)
480 rbl->parent->left = NULL;
482 rbl->parent->right = NULL;
486 /* Optimized unlinking for a complete tree */
487 void rbl_unlink_rbltree(rbltree_t *tree)
491 for(rbl = tree->head; rbl; rbl = next)
507 /* Optimized deletion for a complete tree */
508 void rbl_delete_rbltree(rbltree_t *tree)
512 for(rbl = tree->head; rbl; rbl = next)
516 tree->delete(rbl->data);
524 /* Do action for each list entry (in order)
525 Deletion of entry for which action is called is allowed.
527 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
531 for(rbl = tree->head; rbl; rbl = next)
538 void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
542 for(rbl = tree->head; rbl; rbl = next)