mpls_avl.h

技术文件名称：MPLSv1.0软件模块测试规程

#ifndef __MPLS_AVL_H_
#define __MPLS_AVL_H_

/**INC+***********************************************************************/
/* Header:    mpls_avl.h                                                          */
/*                                                                           */
/* Purpose:   AVL tree functions                                             */
/*                                                                           */
/* (C) COPYRIGHT DATA CONNECTION LIMITED 1993 - 2001                         */
/*                                                                           */
/* $Revision::   1.18                  $$Modtime::   09 May 2001 16:08:32   $*/
/**INC-***********************************************************************/

/*****************************************************************************/
/* On VxWorks, AVL_NODE is defined internally.                               */
/*****************************************************************************/
#ifdef MPLS_AVL_NODE
#undef MPLS_AVL_NODE
#endif

/**STRUCT+********************************************************************/
/* Structure: AVL_NODE                                                       */
/*                                                                           */
/* Description: Node in an AVL tree.                                         */
/*****************************************************************************/

typedef struct mpls_avl_node
{
  struct mpls_avl_node *parent;
  struct mpls_avl_node *left;
  struct mpls_avl_node *right;
  short l_height;
  short r_height;
  void *self;
  void *key;
} MPLS_AVL_NODE;

/**STRUCT-********************************************************************/

/*****************************************************************************/
/* compare function                                                          */
/*****************************************************************************/
typedef int(MPLS_AVL_COMPARE)(void *, void *);

/*****************************************************************************/
/* On VxWorks, AVL_TREE is defined internally.                               */
/*****************************************************************************/
#ifdef MPLS_AVL_TREE
#undef MPLS_AVL_TREE
#endif

/**STRUCT+********************************************************************/
/* Structure: AVL_TREE                                                       */
/*                                                                           */
/* Description: AVL tree root.                                               */
/*****************************************************************************/

typedef struct mpls_avl_tree
{
  MPLS_AVL_COMPARE *compare;
  MPLS_AVL_NODE *root;
  MPLS_AVL_NODE *first;
  MPLS_AVL_NODE *last;
} MPLS_AVL_TREE;

/**STRUCT-********************************************************************/

/*****************************************************************************/
/* AVL functions                                                             */
/*****************************************************************************/
void *mpls_avl_insert_or_find(MPLS_AVL_TREE  *, MPLS_AVL_NODE  *);
void mpls_avl_delete(MPLS_AVL_TREE *, MPLS_AVL_NODE *);
void *mpls_avl_find(MPLS_AVL_TREE *, void *);
void *mpls_avl_find_or_find_next(MPLS_AVL_TREE *, void *, unsigned char);
void *mpls_avl_next(MPLS_AVL_NODE *);
void *mpls_avl_prev(MPLS_AVL_NODE *);

/*****************************************************************************/
/* AVL access macros                                                         */
/*****************************************************************************/
#define MPLS_AVL_INIT_TREE(TREE, COMPARE)   (TREE).compare = &(COMPARE);      \
                                       (TREE).first = NULL;              \
                                       (TREE).last = NULL;               \
                                       (TREE).root = NULL

#define MPLS_AVL_INIT_NODE(NODE, SELF, KEY) (NODE).parent = NULL;             \
                                       (NODE).left = NULL;               \
                                       (NODE).right = NULL;              \
                                       (NODE).self = (SELF);             \
                                       (NODE).key = (KEY);               \
                                       (NODE).l_height = -1;             \
                                       (NODE).r_height = -1;

/*****************************************************************************/
/* Macro definitions                                                         */
/*****************************************************************************/
#define MPLS_AVL_INSERT(TREE, NODE)                                                \
               (mpls_avl_insert_or_find(&(TREE), &(NODE)) == NULL)
#define MPLS_AVL_INSERT_OR_FIND(TREE, NODE)                                        \
               mpls_avl_insert_or_find(&(TREE), &(NODE))
#define MPLS_AVL_DELETE(TREE, NODE)     mpls_avl_delete(&(TREE), &(NODE))
#define MPLS_AVL_FIND(TREE, KEY)        mpls_avl_find(&(TREE), (KEY))
#define MPLS_AVL_NEXT(NODE)             mpls_avl_next(&(NODE))
#define MPLS_AVL_PREV(NODE)             mpls_avl_prev(&(NODE))
#define MPLS_AVL_FIRST(TREE)                                                       \
                   (((&(TREE))->first != NULL) ? (&(TREE))->first->self : NULL)

#define MPLS_AVL_LAST(TREE)                                                        \
                     (((&(TREE))->last != NULL) ? (&(TREE))->last->self : NULL)

#define MPLS_AVL_IN_TREE(NODE)  (((NODE).l_height != -1) && ((NODE).r_height != -1))

#define MPLS_AVL_FIND_NEXT(TREE, KEY)                                              \
                      mpls_avl_find_or_find_next(&(TREE), (KEY), TRUE)

#define MPLS_AVL_FIND_OR_FIND_NEXT(TREE, KEY)                                      \
                     mpls_avl_find_or_find_next(&(TREE), (KEY), FALSE)

/*****************************************************************************/
/* Standard compare functions                                                */
/*****************************************************************************/
int mpls_compare_byte(void *, void *);
int mpls_compare_short(void *, void *);
int mpls_compare_ushort(void *, void *);
int mpls_compare_long(void *, void *);
int mpls_compare_ulong(void *, void *);
int mpls_compare_int(void *, void *);
int mpls_compare_uint(void *, void *);


/*****************************************************************************/
/* macro define                                                              */
/*****************************************************************************/
#define MPLS_MIN(X, Y)   (((X)<(Y)) ? (X) : (Y))
#define MPLS_MAX(X, Y)   (((X)>(Y)) ? (X) : (Y))

#endif