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.6 2000/11/19 11:05:59 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(rbltree_t *tree, void *data)
66 next = rbl = tree->top;
72 result = tree->compare(data, rbl->data);
85 /* Search exact match or return NULL pointer */
86 rbl_t *rbl_search(rbltree_t *tree, void *data)
91 next = rbl = tree->top;
97 result = tree->compare(data, rbl->data);
110 /* Red-black tree operations taken from Introduction to Algorithms,
111 Cormen, Leiserson & Rivest, chapter 14.
114 void rbl_left_rotate(rbl_t *x)
124 y->parent = x->parent;
129 if(x == x->parent->left)
132 x->parent->right = y;
138 void rbl_right_rotate(rbl_t *y)
146 x->right->parent = y;
148 x->parent = y->parent;
153 if(y == y->parent->right)
154 y->parent->right = x;
162 /* Insert a node into the rbl tree */
163 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
165 rbl_t *closest, *x, *y;
170 /* Binary tree and linked list insert */
174 closest = rbl_search_closest(tree, rbl->data);
175 result = tree->compare(rbl->data, closest->data);
180 rbl->prev = closest->prev;
185 rbl->prev->next = rbl;
191 closest->right = rbl;
193 rbl->next = closest->next;
198 rbl->next->prev = rbl;
203 return closest; /* Ofcourse, we cannot add two identical things */
205 rbl->parent = closest;
214 /* Red-black part of insert */
219 while(x != tree->top && x->parent->color == RBL_RED)
221 if(x->parent == x->parent->parent->left)
223 y = x->parent->parent->right;
224 if(y && y->color == RBL_RED)
226 x->parent->color = RBL_BLACK;
227 y->color = RBL_BLACK;
228 x->parent->parent->color = RBL_RED;
229 x = x->parent->parent;
233 if(x == x->parent->right)
238 x->parent->color = RBL_BLACK;
239 x->parent->parent->color = RBL_RED;
240 rbl_right_rotate(x->parent->parent);
245 y = x->parent->parent->left;
246 if(y && y->color == RBL_RED)
248 x->parent->color = RBL_BLACK;
249 y->color = RBL_BLACK;
250 x->parent->parent->color = RBL_RED;
251 x = x->parent->parent;
255 if(x == x->parent->left)
260 x->parent->color = RBL_BLACK;
261 x->parent->parent->color = RBL_RED;
262 rbl_left_rotate(x->parent->parent);
267 tree->top->color = RBL_BLACK;
271 /* Create a new node and insert it into the tree */
272 rbl_t *rbl_insert(rbltree_t *tree, void *data)
279 if(rbl_insert_rbl(tree, rbl) == rbl)
288 /* Restore red-black property after violation due to a deletion */
289 void rbl_delete_fixup(rbl_t *x)
293 while(x != x->tree->top && x->color == RBL_BLACK)
295 if(x == x->parent->left)
297 w = x->parent->right;
298 if(w->color == RBL_RED)
300 w->color = RBL_BLACK;
301 x->parent->color = RBL_RED;
302 rbl_left_rotate(x->parent);
303 w = x->parent->right;
305 if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
312 if(w->right->color == RBL_BLACK)
314 w->left->color = RBL_BLACK;
317 w = x->parent->right;
319 w->color = x->parent->color;
320 x->parent->color = RBL_BLACK;
321 w->right->color = RBL_BLACK;
322 rbl_left_rotate(x->parent);
329 if(w->color == RBL_RED)
331 w->color = RBL_BLACK;
332 x->parent->color = RBL_RED;
333 rbl_right_rotate(x->parent);
336 if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
343 if(w->left->color == RBL_BLACK)
345 w->right->color = RBL_BLACK;
350 w->color = x->parent->color;
351 x->parent->color = RBL_BLACK;
352 w->left->color = RBL_BLACK;
353 rbl_right_rotate(x->parent);
359 x->color = RBL_BLACK;
362 /* Unlink node from the tree, but keep the node intact. */
363 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
367 /* Binary tree delete */
369 if(rbl->left && rbl->right)
380 x->parent = y->parent;
385 if(y == y->parent->left)
388 y->parent->right = x;
393 y->right = rbl->right;
394 y->parent = rbl->parent;
395 if(rbl == rbl->parent->left)
396 rbl->parent->left = y;
398 rbl->parent->right = y;
401 /* Linked list delete */
404 rbl->prev->next = rbl->next;
406 rbl->tree->head = rbl->next;
409 rbl->next->prev = rbl->prev;
411 rbl->tree->tail = rbl->prev;
413 /* Red-black part of delete */
415 if(y->color == RBL_BLACK && x)
421 /* Search node in tree and unlink it */
422 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
426 rbl = rbl_search(tree, data);
429 return rbl_unlink_rbl(rbl);
434 /* Unlink node and free it */
435 void rbl_delete_rbl(rbl_t *rbl)
437 free_rbl(rbl_unlink_rbl(rbl));
440 /* Search node in tree, unlink and free it */
441 void rbl_delete(rbltree_t *tree, void *data)
443 free_rbl(rbl_unlink(tree, data));
446 rbl_unlink_rbltree_branch(rbl_t *rbl)
449 rbl_unlink_rbltree_branch(rbl->left);
452 rbl_unlink_rbltree_branch(rbl->right);
456 if(rbl == rbl->parent->left)
457 rbl->parent->left = NULL;
459 rbl->parent->right = NULL;
462 /* Optimized unlinking for a complete tree */
463 rbl_unlink_rbltree(rbltree_t *tree)
467 for(rbl = tree->head; rbl; rbl = next)
483 /* Optimized deletion for a complete tree */
484 rbl_delete_rbltree(rbltree_t *tree)
488 for(rbl = tree->head; rbl; rbl = next)
491 tree->delete(rbl->data)
499 /* Do action for each list entry (in order)
500 Deletion of entry for which action is called is allowed.
502 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
506 for(rbl = tree->head; rbl; rbl = next)
513 void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
517 for(rbl = tree->head; rbl; rbl = next)