Massively cleaned up #include's, so they're in a consistent

[freeradius.git] / src / lib / rbtree.c

diff --git a/src/lib/rbtree.c b/src/lib/rbtree.c
index a079610..f656b9a 100644 (file)
--- a/src/lib/rbtree.c
+++ b/src/lib/rbtree.c
@@ -15,19 +15,15 @@
  *
  *   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;
@@ -41,7 +37,7 @@ struct rbnode_t {
 };
 
 #define NIL &Sentinel           /* all leafs are sentinels */
-static const rbnode_t Sentinel = { NIL, NIL, NULL, Black, NULL};
+static rbnode_t Sentinel = { NIL, NIL, NULL, Black, NULL};
 
 struct rbtree_t {
 #ifndef NDEBUG
@@ -232,7 +228,7 @@ static void InsertFixup(rbtree_t *tree, rbnode_t *X)
 /*
  *     Insert an element into the tree.
  */
-int rbtree_insert(rbtree_t *tree, const void *Data)
+int rbtree_insert(rbtree_t *tree, void *Data)
 {
        rbnode_t *Current, *Parent, *X;
 
@@ -272,7 +268,7 @@ int rbtree_insert(rbtree_t *tree, const void *Data)
 
        /* setup new node */
        if ((X = malloc (sizeof(*X))) == NULL) {
-               exit(1);
+               exit(1);        /* FIXME! */
        }
 
        X->Data = Data;
@@ -298,8 +294,7 @@ int rbtree_insert(rbtree_t *tree, const void *Data)
        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  *
@@ -307,52 +302,58 @@ static void DeleteFixup(rbtree_t *tree, rbnode_t *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;
                        }
                }
@@ -366,6 +367,7 @@ static void DeleteFixup(rbtree_t *tree, rbnode_t *X)
 void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
 {
        rbnode_t *X, *Y;
+       rbnode_t *Parent;
 
        /*****************************
         *  delete node Z from tree  *
@@ -386,15 +388,17 @@ void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
        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;
 
@@ -409,8 +413,9 @@ void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
        } 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);