pana_rbtree.h

/* BEGIN_COPYRIGHT                                                        */
/*                                                                        */
/* Open Diameter: Open-source software for the Diameter and               */
/*                Diameter related protocols                              */
/*                                                                        */
/* Copyright (C) 2002-2004 Open Diameter Project                          */
/*                                                                        */
/* This library is free software; you can redistribute it and/or modify   */
/* it under the terms of the GNU Lesser General Public License as         */
/* published by the Free Software Foundation; either version 2.1 of the   */
/* License, or (at your option) any later version.                        */
/*                                                                        */
/* This library is distributed in the hope that it will be useful,        */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of         */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU      */
/* Lesser General Public License for more details.                        */
/*                                                                        */
/* 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.                                                                   */
/*                                                                        */
/* In addition, when you copy and redistribute some or the entire part of */
/* the source code of this software with or without modification, you     */
/* MUST include this copyright notice in each copy.                       */
/*                                                                        */
/* If you make any changes that are appeared to be useful, please send    */
/* sources that include the changed part to                               */
/* diameter-developers@lists.sourceforge.net so that we can reflect your  */
/* changes to one unified version of this software.                       */
/*                                                                        */
/* END_COPYRIGHT                                                          */

#ifndef __UTL_RBTREE_H__
#define __UTL_RBTREE_H__

typedef enum {
   RBTREE_CLR_BLACK,
   RBTREE_CLR_RED
} RbTreeNodeColor;

class RbTreeData {
   public:
      // constructor
      RbTreeData() { payload = this; };
      virtual ~RbTreeData() {};
  
      // exposed functions
      void *payload;
  
      // methods
      virtual int operator < (RbTreeData &cmp) = 0;
      virtual int operator == (RbTreeData &cmp) = 0;
      virtual void clear(void *userData = 0) = 0;

      // debugging only
      virtual void Dump(void *userData) {};
};

class RbTreeNode {
   public:
      // constructor
      RbTreeNode();
  
      // exposed members
      RbTreeNode *left;
      RbTreeNode *right;
      RbTreeNode *parent;
      RbTreeNodeColor color;
      RbTreeData *data;

      // methods
      RbTreeNode &operator=(RbTreeNode &source);
};

class RbTreeTree {
   public:
      // constructor
      RbTreeTree() { root = &nil; };

      // methods
      RbTreeData *Insert(RbTreeData *data);
      RbTreeData *Find(RbTreeData *data);
      RbTreeData *Remove(RbTreeData *data);
      void Clear(void *userData = 0);

      // debugging only
      void Dump(RbTreeNode *x = 0, void *userData = 0);

   private:
      RbTreeNode *root;
      RbTreeNode nil;

      void FixupInsert(RbTreeNode *x);
      void FixupRemove(RbTreeNode *x);
      void RotateLeft(RbTreeNode *x);
      void RotateRight(RbTreeNode *x);
};

#endif /* __UTL_RBTREE_H__ */

---