*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
*
- * Copyright 2004 The FreeRADIUS server project
+ * Copyright 2004,2006 The FreeRADIUS server project
*/
-static const char rcsid[] = "$Id$";
+#include <freeradius-devel/ident.h>
+RCSID("$Id$")
-#include "autoconf.h"
-
-#include <stdlib.h>
-#include <string.h>
-
-#include "libradius.h"
+#include <freeradius-devel/libradius.h>
/* red-black tree description */
typedef enum { Black, Red } NodeColor;
/*
* Walk the tree, deleting the nodes...
*/
- if (tree->Root != NULL) FreeWalker(tree, tree->Root);
+ if (tree->Root != NIL) FreeWalker(tree, tree->Root);
#ifndef NDEBUG
tree->magic = 0;
/**************************
* rotate Node X to left *
**************************/
-
+
rbnode_t *Y = X->Right;
-
+
/* establish X->Right link */
X->Right = Y->Left;
if (Y->Left != NIL) Y->Left->Parent = X;
-
+
/* establish Y->Parent link */
if (Y != NIL) Y->Parent = X->Parent;
if (X->Parent) {
} else {
tree->Root = Y;
}
-
+
/* link X and Y */
Y->Left = X;
if (X != NIL) X->Parent = Y;
/****************************
* rotate Node X to right *
****************************/
-
+
rbnode_t *Y = X->Left;
-
+
/* establish X->Left link */
X->Left = Y->Right;
if (Y->Right != NIL) Y->Right->Parent = X;
-
+
/* establish Y->Parent link */
if (Y != NIL) Y->Parent = X->Parent;
if (X->Parent) {
} else {
tree->Root = Y;
}
-
+
/* link X and Y */
Y->Right = X;
if (X != NIL) X->Parent = Y;
* maintain red-black tree balance *
* after inserting node X *
*************************************/
-
+
/* check red-black properties */
while (X != tree->Root && X->Parent->Color == Red) {
/* we have a violation */
if (X->Parent == X->Parent->Parent->Left) {
rbnode_t *Y = X->Parent->Parent->Right;
if (Y->Color == Red) {
-
+
/* uncle is red */
X->Parent->Color = Black;
Y->Color = Black;
X->Parent->Parent->Color = Red;
X = X->Parent->Parent;
} else {
-
+
/* uncle is black */
if (X == X->Parent->Right) {
/* make X a left child */
X = X->Parent;
RotateLeft(tree, X);
}
-
+
/* recolor and rotate */
X->Parent->Color = Black;
X->Parent->Parent->Color = Red;
RotateRight(tree, X->Parent->Parent);
}
} else {
-
+
/* mirror image of above code */
rbnode_t *Y = X->Parent->Parent->Left;
if (Y->Color == Red) {
-
+
/* uncle is red */
X->Parent->Color = Black;
Y->Color = Black;
X->Parent->Parent->Color = Red;
X = X->Parent->Parent;
} else {
-
+
/* uncle is black */
if (X == X->Parent->Left) {
X = X->Parent;
int rbtree_insert(rbtree_t *tree, void *Data)
{
rbnode_t *Current, *Parent, *X;
-
+
/***********************************************
* allocate node for Data and insert in tree *
***********************************************/
-
+
/* find where node belongs */
Current = tree->Root;
Parent = NULL;
/*
* Do replace the entry.
*/
+ if (tree->freeNode) tree->freeNode(Current->Data);
Current->Data = Data;
return 1;
}
Parent = Current;
Current = (result < 0) ? Current->Left : Current->Right;
}
-
+
/* setup new node */
if ((X = malloc (sizeof(*X))) == NULL) {
- exit(1);
+ exit(1); /* FIXME! */
}
X->Data = Data;
X->Left = NIL;
X->Right = NIL;
X->Color = Red;
-
+
/* insert node in tree */
if (Parent) {
if (tree->Compare(Data, Parent->Data) <= 0)
} else {
tree->Root = X;
}
-
+
InsertFixup(tree, X);
tree->num_elements++;
return 1;
}
-
-static void DeleteFixup(rbtree_t *tree, rbnode_t *X)
+static void DeleteFixup(rbtree_t *tree, rbnode_t *X, rbnode_t *Parent)
{
/*************************************
* maintain red-black tree balance *
* after deleting node X *
*************************************/
-
+
while (X != tree->Root && X->Color == Black) {
- if (X == X->Parent->Left) {
- rbnode_t *W = X->Parent->Right;
+ if (X == Parent->Left) {
+ rbnode_t *W = Parent->Right;
if (W->Color == Red) {
W->Color = Black;
- X->Parent->Color = Red;
- RotateLeft(tree, X->Parent);
- W = X->Parent->Right;
+ Parent->Color = Red; /* Parent != NIL? */
+ RotateLeft(tree, Parent);
+ W = Parent->Right;
}
if (W->Left->Color == Black && W->Right->Color == Black) {
- W->Color = Red;
- X = X->Parent;
+ if (W != NIL) W->Color = Red;
+ X = Parent;
+ Parent = X->Parent;
} else {
if (W->Right->Color == Black) {
- W->Left->Color = Black;
+ if (W->Left != NIL) W->Left->Color = Black;
W->Color = Red;
RotateRight(tree, W);
- W = X->Parent->Right;
+ W = Parent->Right;
}
- W->Color = X->Parent->Color;
- X->Parent->Color = Black;
- W->Right->Color = Black;
- RotateLeft(tree, X->Parent);
+ W->Color = Parent->Color;
+ if (Parent != NIL) Parent->Color = Black;
+ if (W->Right->Color != Black) {
+ W->Right->Color = Black;
+ }
+ RotateLeft(tree, Parent);
X = tree->Root;
}
} else {
- rbnode_t *W = X->Parent->Left;
+ rbnode_t *W = Parent->Left;
if (W->Color == Red) {
W->Color = Black;
- X->Parent->Color = Red;
- RotateRight(tree, X->Parent);
- W = X->Parent->Left;
+ Parent->Color = Red; /* Parent != NIL? */
+ RotateRight(tree, Parent);
+ W = Parent->Left;
}
if (W->Right->Color == Black && W->Left->Color == Black) {
- W->Color = Red;
- X = X->Parent;
+ if (W != NIL) W->Color = Red;
+ X = Parent;
+ Parent = X->Parent;
} else {
if (W->Left->Color == Black) {
- W->Right->Color = Black;
+ if (W->Right != NIL) W->Right->Color = Black;
W->Color = Red;
RotateLeft(tree, W);
- W = X->Parent->Left;
+ W = Parent->Left;
}
- W->Color = X->Parent->Color;
- X->Parent->Color = Black;
- W->Left->Color = Black;
- RotateRight(tree, X->Parent);
+ W->Color = Parent->Color;
+ if (Parent != NIL) Parent->Color = Black;
+ if (W->Left->Color != Black) {
+ W->Left->Color = Black;
+ }
+ RotateRight(tree, Parent);
X = tree->Root;
}
}
void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
{
rbnode_t *X, *Y;
-
+ rbnode_t *Parent;
+
/*****************************
* delete node Z from tree *
*****************************/
-
+
if (!Z || Z == NIL) return;
-
+
if (Z->Left == NIL || Z->Right == NIL) {
/* Y has a NIL node as a child */
Y = Z;
Y = Z->Right;
while (Y->Left != NIL) Y = Y->Left;
}
-
+
/* X is Y's only child */
if (Y->Left != NIL)
X = Y->Left;
else
- X = Y->Right;
-
+ X = Y->Right; /* may be NIL! */
+
/* remove Y from the parent chain */
- X->Parent = Y->Parent;
- if (Y->Parent)
- if (Y == Y->Parent->Left)
- Y->Parent->Left = X;
+ Parent = Y->Parent;
+ if (X != NIL) X->Parent = Parent;
+
+ if (Parent)
+ if (Y == Parent->Left)
+ Parent->Left = X;
else
- Y->Parent->Right = X;
+ Parent->Right = X;
else
tree->Root = X;
-
+
if (Y != Z) {
/*
* Move the child's data to here, and then
} else if (tree->freeNode) {
tree->freeNode(Z->Data);
}
- if (Y->Color == Black)
- DeleteFixup(tree, X);
+
+ if (Y->Color == Black && X != NIL)
+ DeleteFixup(tree, X, Parent);
free(Y);
}
/*
+ * Delete a node from the tree, based on given data, which MUST
+ * have come from rbtree_finddata().
+ */
+int rbtree_deletebydata(rbtree_t *tree, const void *data)
+{
+ rbnode_t *node = rbtree_find(tree, data);
+
+ if (!node) return 0; /* false */
+
+ rbtree_delete(tree, node);
+
+ return 1;
+}
+
+
+/*
* Find an element in the tree, returning the data, not the node.
*/
-rbnode_t *rbtree_find(rbtree_t *tree, void *Data)
+rbnode_t *rbtree_find(rbtree_t *tree, const void *Data)
{
/*******************************
* find node containing Data *
*******************************/
-
+
rbnode_t *Current = tree->Root;
while (Current != NIL) {
/*
* Find the user data.
*/
-void *rbtree_finddata(rbtree_t *tree, void *Data)
+void *rbtree_finddata(rbtree_t *tree, const void *Data)
{
rbnode_t *X;
* We call ourselves recursively for each function, but that's OK,
* as the stack is only log(N) deep, which is ~12 entries deep.
*/
-static int WalkNodePreOrder(rbnode_t *X, int (*callback)(void *))
+static int WalkNodePreOrder(rbnode_t *X,
+ int (*callback)(void *, void *), void *context)
{
int rcode;
- rcode = callback(X->Data);
+ rcode = callback(context, X->Data);
if (rcode != 0) return rcode;
if (X->Left != NIL) {
- rcode = WalkNodePreOrder(X->Left, callback);
+ rcode = WalkNodePreOrder(X->Left, callback, context);
if (rcode != 0) return rcode;
}
if (X->Right != NIL) {
- rcode = WalkNodePreOrder(X->Right, callback);
+ rcode = WalkNodePreOrder(X->Right, callback, context);
if (rcode != 0) return rcode;
}
/*
* Inorder
*/
-static int WalkNodeInOrder(rbnode_t *X, int (*callback)(void *))
+static int WalkNodeInOrder(rbnode_t *X,
+ int (*callback)(void *, void *), void *context)
{
int rcode;
if (X->Left != NIL) {
- rcode = WalkNodeInOrder(X->Left, callback);
+ rcode = WalkNodeInOrder(X->Left, callback, context);
if (rcode != 0) return rcode;
}
- rcode = callback(X->Data);
+ rcode = callback(context, X->Data);
if (rcode != 0) return rcode;
if (X->Right != NIL) {
- rcode = WalkNodeInOrder(X->Right, callback);
+ rcode = WalkNodeInOrder(X->Right, callback, context);
if (rcode != 0) return rcode;
}
/*
* PostOrder
*/
-static int WalkNodePostOrder(rbnode_t *X, int (*callback)(void *))
+static int WalkNodePostOrder(rbnode_t *X,
+ int (*callback)(void *, void*), void *context)
{
int rcode;
if (X->Left != NIL) {
- rcode = WalkNodeInOrder(X->Left, callback);
+ rcode = WalkNodeInOrder(X->Left, callback, context);
if (rcode != 0) return rcode;
}
if (X->Right != NIL) {
- rcode = WalkNodeInOrder(X->Right, callback);
+ rcode = WalkNodeInOrder(X->Right, callback, context);
if (rcode != 0) return rcode;
}
- rcode = callback(X->Data);
+ rcode = callback(context, X->Data);
if (rcode != 0) return rcode;
return 0; /* we know everything returned zero */
* The callback function should return 0 to continue walking.
* Any other value stops the walk, and is returned.
*/
-int rbtree_walk(rbtree_t *tree, int (*callback)(void *), RBTREE_ORDER order)
+int rbtree_walk(rbtree_t *tree, RBTREE_ORDER order,
+ int (*callback)(void *, void *), void *context)
{
switch (order) {
- case PreOrder:
- return WalkNodePreOrder(tree->Root, callback);
- case InOrder:
- return WalkNodeInOrder(tree->Root, callback);
- case PostOrder:
- return WalkNodePostOrder(tree->Root, callback);
+ case PreOrder:
+ return WalkNodePreOrder(tree->Root, callback, context);
+ case InOrder:
+ return WalkNodeInOrder(tree->Root, callback, context);
+ case PostOrder:
+ return WalkNodePostOrder(tree->Root, callback, context);
default:
break;
*/
void *rbtree_node2data(rbtree_t *tree, rbnode_t *node)
{
+ tree = tree; /* -Wunused */
+
if (!node) return NULL;
return node->Data;
projects / freeradius.git / blobdiff