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.11 2000/11/22 19:14:08 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)
95 rbl = rbl_search_closest_rbl(tree, data);
103 /* Search exact match or return NULL pointer */
104 rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
113 result = tree->compare(data, rbl->data);
126 void *rbl_search(rbltree_t *tree, void *data)
130 rbl = rbl_search_rbl(tree, data);
138 /* Red-black tree operations taken from Introduction to Algorithms,
139 Cormen, Leiserson & Rivest, chapter 14.
142 void rbl_left_rotate(rbl_t *x)
152 y->parent = x->parent;
157 if(x == x->parent->left)
160 x->parent->right = y;
166 void rbl_right_rotate(rbl_t *y)
174 x->right->parent = y;
176 x->parent = y->parent;
181 if(y == y->parent->right)
182 y->parent->right = x;
190 /* Insert a node into the rbl tree */
191 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
193 rbl_t *closest, *x, *y;
198 /* Binary tree and linked list insert */
202 closest = rbl_search_closest_rbl(tree, rbl->data);
203 result = tree->compare(rbl->data, closest->data);
208 rbl->prev = closest->prev;
213 rbl->prev->next = rbl;
219 closest->right = rbl;
221 rbl->next = closest->next;
226 rbl->next->prev = rbl;
231 return closest; /* Ofcourse, we cannot add two identical things */
233 rbl->parent = closest;
242 /* Red-black part of insert */
247 while(x != tree->top && x->parent->color == RBL_RED)
249 if(x->parent == x->parent->parent->left)
251 y = x->parent->parent->right;
252 if(y && y->color == RBL_RED)
254 x->parent->color = RBL_BLACK;
255 y->color = RBL_BLACK;
256 x->parent->parent->color = RBL_RED;
257 x = x->parent->parent;
261 if(x == x->parent->right)
266 x->parent->color = RBL_BLACK;
267 x->parent->parent->color = RBL_RED;
268 rbl_right_rotate(x->parent->parent);
273 y = x->parent->parent->left;
274 if(y && y->color == RBL_RED)
276 x->parent->color = RBL_BLACK;
277 y->color = RBL_BLACK;
278 x->parent->parent->color = RBL_RED;
279 x = x->parent->parent;
283 if(x == x->parent->left)
288 x->parent->color = RBL_BLACK;
289 x->parent->parent->color = RBL_RED;
290 rbl_left_rotate(x->parent->parent);
295 tree->top->color = RBL_BLACK;
299 /* Create a new node and insert it into the tree */
300 rbl_t *rbl_insert(rbltree_t *tree, void *data)
307 if(rbl_insert_rbl(tree, rbl) == rbl)
316 /* Restore red-black property after violation due to a deletion */
317 void rbl_delete_fixup(rbl_t *x)
321 while(x != x->tree->top && x->color == RBL_BLACK)
323 if(x == x->parent->left)
325 w = x->parent->right;
326 if(w->color == RBL_RED)
328 w->color = RBL_BLACK;
329 x->parent->color = RBL_RED;
330 rbl_left_rotate(x->parent);
331 w = x->parent->right;
333 if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
340 if(w->right->color == RBL_BLACK)
342 w->left->color = RBL_BLACK;
345 w = x->parent->right;
347 w->color = x->parent->color;
348 x->parent->color = RBL_BLACK;
349 w->right->color = RBL_BLACK;
350 rbl_left_rotate(x->parent);
357 if(w->color == RBL_RED)
359 w->color = RBL_BLACK;
360 x->parent->color = RBL_RED;
361 rbl_right_rotate(x->parent);
364 if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
371 if(w->left->color == RBL_BLACK)
373 w->right->color = RBL_BLACK;
378 w->color = x->parent->color;
379 x->parent->color = RBL_BLACK;
380 w->left->color = RBL_BLACK;
381 rbl_right_rotate(x->parent);
387 x->color = RBL_BLACK;
390 /* Unlink node from the tree, but keep the node intact. */
391 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
395 /* Binary tree delete */
397 if(rbl->left && rbl->right)
408 x->parent = y->parent;
413 if(y == y->parent->left)
416 y->parent->right = x;
421 y->right = rbl->right;
422 y->parent = rbl->parent;
423 if(rbl == rbl->parent->left)
424 rbl->parent->left = y;
426 rbl->parent->right = y;
429 /* Linked list delete */
432 rbl->prev->next = rbl->next;
434 rbl->tree->head = rbl->next;
437 rbl->next->prev = rbl->prev;
439 rbl->tree->tail = rbl->prev;
441 /* Red-black part of delete */
443 if(y->color == RBL_BLACK && x)
449 /* Search node in tree and unlink it */
450 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
454 rbl = rbl_search_rbl(tree, data);
462 /* Unlink node and free it */
463 void rbl_delete_rbl(rbl_t *rbl)
469 /* Search node in tree, unlink and free it */
470 void rbl_delete(rbltree_t *tree, void *data)
474 rbl = rbl_unlink(tree, data);
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)
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)