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.4 2000/11/18 23:22:44 guus Exp $
24 /* Allocate a new rbl node */
27 return (rbl_t *)xmalloc_and_zero(sizeof(*rbl));
31 void free_rbl(rbl_t *rbl)
36 /* Allocate a new rbltree header */
37 rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_action_t *delete)
41 tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
44 tree->compare = compare;
45 tree->delete = delete;
51 /* Free a rbltree header */
52 void free_rbltree(rbltree_t *tree)
57 /* Search closest match in the tree */
58 rbl_t rbl_search_closest(rbltree_t *tree, void *data)
63 next = rbl = tree->top;
69 result = tree->compare(rbl->data, data);
82 /* Search exact match or return NULL pointer */
83 rbl_t rbl_search(rbltree_t *tree, void *data)
88 next = rbl = tree->top;
94 result = tree->compare(rbl->data, data);
107 /* Red-black tree operations taken from Introduction to Algorithms,
108 Cormen, Leiserson & Rivest, chapter 14.
111 void rbl_left_rotate(rbl_t *x)
121 y->parent = x->parent;
126 if(x == x->parent->left)
129 x->parent->right = y;
135 void rbl_right_rotate(rbl_t *y)
143 x->right->parent = y;
145 x->parent = y->parent;
150 if(y == y->parent->right)
151 y->parent->right = x;
159 /* Insert a node into the rbl tree */
160 rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
165 /* Binary tree and linked list insert */
169 closest = rbl_search_closest(tree, rbl->data);
170 result = tree->compare(rbl->data, data);
174 rbl->prev = closest->prev;
177 rbl->prev->next = rbl;
181 closest->right = rbl;
182 rbl->next = closest->right;
185 rbl->next->prev = rbl;
188 return closest; /* Ofcourse, we cannot add two identical things */
193 /* Linked list fixup */
201 /* Red-black part of insert */
203 rbl->color = RBL_RED;
205 while(rbl->parent && rbl->parent->color == RBL_RED)
207 if(rbl->parent == rbl->parent->parent->left)
209 y = rbl->parent->parent->right;
210 if(y->color == RBL_RED)
212 rbl->parent->color = RBL_BLACK;
213 y->color = RBL_BLACK;
214 rbl->parent->parent->color = RBL_RED;
215 rbl = rbl->parent->parent;
219 if(rbl == rbl->parent->right)
222 rbl_left_rotate(rbl);
224 rbl->parent->color = RBL_BLACK;
225 rbl->parent->parent->color = RBL_RED;
226 rbl_right_rotate(rbl->parent->parent);
231 y = rbl->parent->parent->left;
232 if(y->color == RBL_RED)
234 rbl->parent->color = RBL_BLACK;
235 y->color = RBL_BLACK;
236 rbl->parent->parent->color = RBL_RED;
237 rbl = rbl->parent->parent;
241 if(rbl == rbl->parent->left)
244 rbl_right_rotate(rbl);
246 rbl->parent->color = RBL_BLACK;
247 rbl->parent->parent->color = RBL_RED;
248 rbl_left_rotate(rbl->parent->parent);
253 tree->top->color = RBL_BLACK;
258 /* Create a new node and insert it into the tree */
259 rbl_t rbl_insert(rbltree_t *tree, void *data)
266 return rbl_insert_rbl(tree, rbl);
269 /* Restore red-black property after violation due to a deletion */
270 void rbl_delete_fixup(rbl_t *x)
274 while(x != x->tree->top && x->color == RBL_BLACK)
276 if(x == x->parent->left)
278 w = x->parent->right;
279 if(w->color == RBL_RED)
281 w->color = RBL_BLACK;
282 x->partent->color = RBL_RED;
283 rbl_left_rotate(x->parent);
284 w = x->parent->right;
286 if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
293 if(w->right->color == RBL_BLACK)
295 w->left->color = RBL_BLACK;
298 w = x->parent->right;
300 w->color = x->parent->color;
301 x->parent->color = RBL_BLACK;
302 w->right->color = RBL_BLACK;
303 rbl_left_rotate(x->parent);
310 if(w->color == RBL_RED)
312 w->color = RBL_BLACK;
313 x->partent->color = RBL_RED;
314 rbl_right_rotate(x->parent);
317 if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
324 if(w->left->color == RBL_BLACK)
326 w->right->color = RBL_BLACK;
331 w->color = x->parent->color;
332 x->parent->color = RBL_BLACK;
333 w->left->color = RBL_BLACK;
334 rbl_right_rotate(x->parent);
340 x->color = RBL_BLACK;
343 /* Unlink node from the tree, but keep the node intact. */
344 rbl_t rbl_unlink_rbl(rbl_t *rbl)
348 /* Binary tree delete */
350 if(rbl->left && rbl->right)
361 x->parent = y->parent;
366 if(y == y->parent->left)
369 y->parent->right = x;
374 y->right = rbl->right;
375 y->parent = rbl->parent;
376 if(rbl == rbl->parent->left)
377 rbl->parent->left = y;
379 rbl->parent->right = y;
382 /* Linked list delete */
385 rbl->prev->next = rbl->next;
387 rbl->tree->head = rbl->next;
390 rbl->next->prev = rbl->prev;
392 rbl->tree->tail = rbl->prev;
394 /* Red-black part of delete */
396 if(y->color == RBL_BLACK)
402 /* Search node in tree and unlink it */
403 rbl_t rbl_unlink(rbltree_t *tree, void *data)
407 rbl = rbl_search(tree, data);
410 return rbl_unlink_rbl(rbl);
415 /* Unlink node and free it */
416 void rbl_delete_rbl(rbl_t *rbl)
418 free_rbl(rbl_unlink_rbl(rbl));
421 /* Search node in tree, unlink and free it */
422 void rbl_delete(rbltree_t *tree, void *data)
424 free_rbl(rbl_unlink(tree, data));
427 /* Do action for each list entry (in order)
428 Deletion of entry for which action is called is allowed.
430 void rbl_foreach(rbltree_t *tree, rbl_action_t *action)
434 for(rbl = tree->head; rbl; rbl = next);