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.5 2000/11/19 02:04:29 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);
74 // fprintf(stderr, "comparing %s with %s = %d\n", rbl->data, data, result);
87 /* Search exact match or return NULL pointer */
88 rbl_t *rbl_search(rbltree_t *tree, void *data)
93 next = rbl = tree->top;
99 result = tree->compare(rbl->data, data);
112 /* Red-black tree operations taken from Introduction to Algorithms,
113 Cormen, Leiserson & Rivest, chapter 14.
116 void rbl_left_rotate(rbl_t *x)
126 y->parent = x->parent;
131 if(x == x->parent->left)
134 x->parent->right = y;
140 void rbl_right_rotate(rbl_t *y)
148 x->right->parent = y;
150 x->parent = y->parent;
155 if(y == y->parent->right)
156 y->parent->right = x;
164 /* Insert a node into the rbl tree */
165 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
167 rbl_t *closest, *x, *y;
172 /* Binary tree and linked list insert */
176 closest = rbl_search_closest(tree, rbl->data);
177 result = tree->compare(rbl->data, closest->data);
182 rbl->prev = closest->prev;
187 rbl->prev->next = rbl;
193 closest->right = rbl;
195 rbl->next = closest->next;
200 rbl->next->prev = rbl;
205 return closest; /* Ofcourse, we cannot add two identical things */
207 rbl->parent = closest;
216 /* Red-black part of insert */
221 while(x != tree->top && x->parent->color == RBL_RED)
223 if(x->parent == x->parent->parent->left)
225 y = x->parent->parent->right;
226 if(y && y->color == RBL_RED)
228 x->parent->color = RBL_BLACK;
229 y->color = RBL_BLACK;
230 x->parent->parent->color = RBL_RED;
231 x = x->parent->parent;
235 if(x == x->parent->right)
240 x->parent->color = RBL_BLACK;
241 x->parent->parent->color = RBL_RED;
242 rbl_right_rotate(x->parent->parent);
247 y = x->parent->parent->left;
248 if(y && y->color == RBL_RED)
250 x->parent->color = RBL_BLACK;
251 y->color = RBL_BLACK;
252 x->parent->parent->color = RBL_RED;
253 x = x->parent->parent;
257 if(x == x->parent->left)
262 x->parent->color = RBL_BLACK;
263 x->parent->parent->color = RBL_RED;
264 rbl_left_rotate(x->parent->parent);
269 tree->top->color = RBL_BLACK;
273 /* Create a new node and insert it into the tree */
274 rbl_t *rbl_insert(rbltree_t *tree, void *data)
281 if(rbl_insert_rbl(tree, rbl) == rbl)
290 /* Restore red-black property after violation due to a deletion */
291 void rbl_delete_fixup(rbl_t *x)
295 while(x != x->tree->top && x->color == RBL_BLACK)
297 if(x == x->parent->left)
299 w = x->parent->right;
300 if(w->color == RBL_RED)
302 w->color = RBL_BLACK;
303 x->parent->color = RBL_RED;
304 rbl_left_rotate(x->parent);
305 w = x->parent->right;
307 if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
314 if(w->right->color == RBL_BLACK)
316 w->left->color = RBL_BLACK;
319 w = x->parent->right;
321 w->color = x->parent->color;
322 x->parent->color = RBL_BLACK;
323 w->right->color = RBL_BLACK;
324 rbl_left_rotate(x->parent);
331 if(w->color == RBL_RED)
333 w->color = RBL_BLACK;
334 x->parent->color = RBL_RED;
335 rbl_right_rotate(x->parent);
338 if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
345 if(w->left->color == RBL_BLACK)
347 w->right->color = RBL_BLACK;
352 w->color = x->parent->color;
353 x->parent->color = RBL_BLACK;
354 w->left->color = RBL_BLACK;
355 rbl_right_rotate(x->parent);
361 x->color = RBL_BLACK;
364 /* Unlink node from the tree, but keep the node intact. */
365 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
369 /* Binary tree delete */
371 if(rbl->left && rbl->right)
382 x->parent = y->parent;
387 if(y == y->parent->left)
390 y->parent->right = x;
395 y->right = rbl->right;
396 y->parent = rbl->parent;
397 if(rbl == rbl->parent->left)
398 rbl->parent->left = y;
400 rbl->parent->right = y;
403 /* Linked list delete */
406 rbl->prev->next = rbl->next;
408 rbl->tree->head = rbl->next;
411 rbl->next->prev = rbl->prev;
413 rbl->tree->tail = rbl->prev;
415 /* Red-black part of delete */
417 if(y->color == RBL_BLACK)
423 /* Search node in tree and unlink it */
424 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
428 rbl = rbl_search(tree, data);
431 return rbl_unlink_rbl(rbl);
436 /* Unlink node and free it */
437 void rbl_delete_rbl(rbl_t *rbl)
439 free_rbl(rbl_unlink_rbl(rbl));
442 /* Search node in tree, unlink and free it */
443 void rbl_delete(rbltree_t *tree, void *data)
445 free_rbl(rbl_unlink(tree, data));
448 /* Do action for each list entry (in order)
449 Deletion of entry for which action is called is allowed.
451 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
455 for(rbl = tree->head; rbl; rbl = next)