2 * rbtree.c Red-black balanced binary trees.
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
11 * This library 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 GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
20 * Copyright 2004,2006 The FreeRADIUS server project
23 #include <freeradius-devel/ident.h>
26 #include <freeradius-devel/libradius.h>
28 /* red-black tree description */
29 typedef enum { Black, Red } NodeColor;
32 rbnode_t *Left; /* left child */
33 rbnode_t *Right; /* right child */
34 rbnode_t *Parent; /* parent */
35 NodeColor Color; /* node color (black, red) */
36 void *Data; /* data stored in node */
39 #define NIL &Sentinel /* all leafs are sentinels */
40 static rbnode_t Sentinel = { NIL, NIL, NULL, Black, NULL};
48 int (*Compare)(const void *, const void *);
50 void (*freeNode)(void *);
52 #define RBTREE_MAGIC (0x5ad09c42)
55 * Walks the tree to delete all nodes.
56 * Does NOT re-balance it!
58 static void FreeWalker(rbtree_t *tree, rbnode_t *X)
60 if (X->Left != NIL) FreeWalker(tree, X->Left);
61 if (X->Right != NIL) FreeWalker(tree, X->Right);
63 if (tree->freeNode) tree->freeNode(X->Data);
67 void rbtree_free(rbtree_t *tree)
72 * Walk the tree, deleting the nodes...
74 if (tree->Root != NIL) FreeWalker(tree, tree->Root);
84 * Create a new red-black tree.
86 rbtree_t *rbtree_create(int (*Compare)(const void *, const void *),
87 void (*freeNode)(void *),
92 if (!Compare) return NULL;
94 tree = malloc(sizeof(*tree));
95 if (!tree) return NULL;
97 memset(tree, 0, sizeof(*tree));
99 tree->magic = RBTREE_MAGIC;
102 tree->Compare = Compare;
103 tree->replace_flag = replace_flag;
104 tree->freeNode = freeNode;
110 static void RotateLeft(rbtree_t *tree, rbnode_t *X)
112 /**************************
113 * rotate Node X to left *
114 **************************/
116 rbnode_t *Y = X->Right;
118 /* establish X->Right link */
120 if (Y->Left != NIL) Y->Left->Parent = X;
122 /* establish Y->Parent link */
123 if (Y != NIL) Y->Parent = X->Parent;
125 if (X == X->Parent->Left)
128 X->Parent->Right = Y;
135 if (X != NIL) X->Parent = Y;
138 static void RotateRight(rbtree_t *tree, rbnode_t *X)
140 /****************************
141 * rotate Node X to right *
142 ****************************/
144 rbnode_t *Y = X->Left;
146 /* establish X->Left link */
148 if (Y->Right != NIL) Y->Right->Parent = X;
150 /* establish Y->Parent link */
151 if (Y != NIL) Y->Parent = X->Parent;
153 if (X == X->Parent->Right)
154 X->Parent->Right = Y;
163 if (X != NIL) X->Parent = Y;
166 static void InsertFixup(rbtree_t *tree, rbnode_t *X)
168 /*************************************
169 * maintain red-black tree balance *
170 * after inserting node X *
171 *************************************/
173 /* check red-black properties */
174 while (X != tree->Root && X->Parent->Color == Red) {
175 /* we have a violation */
176 if (X->Parent == X->Parent->Parent->Left) {
177 rbnode_t *Y = X->Parent->Parent->Right;
178 if (Y->Color == Red) {
181 X->Parent->Color = Black;
183 X->Parent->Parent->Color = Red;
184 X = X->Parent->Parent;
188 if (X == X->Parent->Right) {
189 /* make X a left child */
194 /* recolor and rotate */
195 X->Parent->Color = Black;
196 X->Parent->Parent->Color = Red;
197 RotateRight(tree, X->Parent->Parent);
201 /* mirror image of above code */
202 rbnode_t *Y = X->Parent->Parent->Left;
203 if (Y->Color == Red) {
206 X->Parent->Color = Black;
208 X->Parent->Parent->Color = Red;
209 X = X->Parent->Parent;
213 if (X == X->Parent->Left) {
215 RotateRight(tree, X);
217 X->Parent->Color = Black;
218 X->Parent->Parent->Color = Red;
219 RotateLeft(tree, X->Parent->Parent);
224 tree->Root->Color = Black;
229 * Insert an element into the tree.
231 int rbtree_insert(rbtree_t *tree, void *Data)
233 rbnode_t *Current, *Parent, *X;
235 /***********************************************
236 * allocate node for Data and insert in tree *
237 ***********************************************/
239 /* find where node belongs */
240 Current = tree->Root;
242 while (Current != NIL) {
246 * See if two entries are identical.
248 result = tree->Compare(Data, Current->Data);
251 * Don't replace the entry.
253 if (tree->replace_flag == 0) {
258 * Do replace the entry.
260 if (tree->freeNode) tree->freeNode(Current->Data);
261 Current->Data = Data;
266 Current = (result < 0) ? Current->Left : Current->Right;
270 if ((X = malloc (sizeof(*X))) == NULL) {
271 exit(1); /* FIXME! */
280 /* insert node in tree */
282 if (tree->Compare(Data, Parent->Data) <= 0)
290 InsertFixup(tree, X);
292 tree->num_elements++;
297 static void DeleteFixup(rbtree_t *tree, rbnode_t *X, rbnode_t *Parent)
299 /*************************************
300 * maintain red-black tree balance *
301 * after deleting node X *
302 *************************************/
304 while (X != tree->Root && X->Color == Black) {
305 if (X == Parent->Left) {
306 rbnode_t *W = Parent->Right;
307 if (W->Color == Red) {
309 Parent->Color = Red; /* Parent != NIL? */
310 RotateLeft(tree, Parent);
313 if (W->Left->Color == Black && W->Right->Color == Black) {
314 if (W != NIL) W->Color = Red;
318 if (W->Right->Color == Black) {
319 if (W->Left != NIL) W->Left->Color = Black;
321 RotateRight(tree, W);
324 W->Color = Parent->Color;
325 if (Parent != NIL) Parent->Color = Black;
326 if (W->Right->Color != Black) {
327 W->Right->Color = Black;
329 RotateLeft(tree, Parent);
333 rbnode_t *W = Parent->Left;
334 if (W->Color == Red) {
336 Parent->Color = Red; /* Parent != NIL? */
337 RotateRight(tree, Parent);
340 if (W->Right->Color == Black && W->Left->Color == Black) {
341 if (W != NIL) W->Color = Red;
345 if (W->Left->Color == Black) {
346 if (W->Right != NIL) W->Right->Color = Black;
351 W->Color = Parent->Color;
352 if (Parent != NIL) Parent->Color = Black;
353 if (W->Left->Color != Black) {
354 W->Left->Color = Black;
356 RotateRight(tree, Parent);
365 * Delete an element from the tree.
367 void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
372 /*****************************
373 * delete node Z from tree *
374 *****************************/
376 if (!Z || Z == NIL) return;
378 if (Z->Left == NIL || Z->Right == NIL) {
379 /* Y has a NIL node as a child */
382 /* find tree successor with a NIL node as a child */
384 while (Y->Left != NIL) Y = Y->Left;
387 /* X is Y's only child */
391 X = Y->Right; /* may be NIL! */
393 /* remove Y from the parent chain */
395 if (X != NIL) X->Parent = Parent;
398 if (Y == Parent->Left)
407 * Move the child's data to here, and then
408 * re-balance the tree.
410 if (tree->freeNode) tree->freeNode(Z->Data);
413 } else if (tree->freeNode) {
414 tree->freeNode(Z->Data);
417 if (Y->Color == Black && X != NIL)
418 DeleteFixup(tree, X, Parent);
422 tree->num_elements--;
426 * Delete a node from the tree, based on given data, which MUST
427 * have come from rbtree_finddata().
429 int rbtree_deletebydata(rbtree_t *tree, const void *data)
431 rbnode_t *node = rbtree_find(tree, data);
433 if (!node) return 0; /* false */
435 rbtree_delete(tree, node);
442 * Find an element in the tree, returning the data, not the node.
444 rbnode_t *rbtree_find(rbtree_t *tree, const void *Data)
446 /*******************************
447 * find node containing Data *
448 *******************************/
450 rbnode_t *Current = tree->Root;
452 while (Current != NIL) {
453 int result = tree->Compare(Data, Current->Data);
458 Current = (result < 0) ?
459 Current->Left : Current->Right;
466 * Find the user data.
468 void *rbtree_finddata(rbtree_t *tree, const void *Data)
472 X = rbtree_find(tree, Data);
479 * Walk the tree, Pre-order
481 * We call ourselves recursively for each function, but that's OK,
482 * as the stack is only log(N) deep, which is ~12 entries deep.
484 static int WalkNodePreOrder(rbnode_t *X,
485 int (*callback)(void *, void *), void *context)
489 rcode = callback(context, X->Data);
490 if (rcode != 0) return rcode;
492 if (X->Left != NIL) {
493 rcode = WalkNodePreOrder(X->Left, callback, context);
494 if (rcode != 0) return rcode;
497 if (X->Right != NIL) {
498 rcode = WalkNodePreOrder(X->Right, callback, context);
499 if (rcode != 0) return rcode;
502 return 0; /* we know everything returned zero */
508 static int WalkNodeInOrder(rbnode_t *X,
509 int (*callback)(void *, void *), void *context)
513 if (X->Left != NIL) {
514 rcode = WalkNodeInOrder(X->Left, callback, context);
515 if (rcode != 0) return rcode;
518 rcode = callback(context, X->Data);
519 if (rcode != 0) return rcode;
521 if (X->Right != NIL) {
522 rcode = WalkNodeInOrder(X->Right, callback, context);
523 if (rcode != 0) return rcode;
526 return 0; /* we know everything returned zero */
533 static int WalkNodePostOrder(rbnode_t *X,
534 int (*callback)(void *, void*), void *context)
538 if (X->Left != NIL) {
539 rcode = WalkNodeInOrder(X->Left, callback, context);
540 if (rcode != 0) return rcode;
543 if (X->Right != NIL) {
544 rcode = WalkNodeInOrder(X->Right, callback, context);
545 if (rcode != 0) return rcode;
548 rcode = callback(context, X->Data);
549 if (rcode != 0) return rcode;
551 return 0; /* we know everything returned zero */
555 * Walk the entire tree. The callback function CANNOT modify
558 * The callback function should return 0 to continue walking.
559 * Any other value stops the walk, and is returned.
561 int rbtree_walk(rbtree_t *tree, RBTREE_ORDER order,
562 int (*callback)(void *, void *), void *context)
566 return WalkNodePreOrder(tree->Root, callback, context);
568 return WalkNodeInOrder(tree->Root, callback, context);
570 return WalkNodePostOrder(tree->Root, callback, context);
579 int rbtree_num_elements(rbtree_t *tree)
583 return tree->num_elements;
588 * Given a Node, return the data.
590 void *rbtree_node2data(rbtree_t *tree, rbnode_t *node)
592 tree = tree; /* -Wunused */
594 if (!node) return NULL;