avltree.h

vxworks 6.x 的全部头文件

/* $Header: /usr/cvsroot/epilogue/attache/h/avltree.h,v 4.13 2001/01/19 22:20:28 paul Exp $ */

/****************************************************************************
 *
 *  *** Restricted Rights Legend ***
 *
 *  The programs and information contained herein are licensed only
 *  pursuant to a license agreement that contains use, reverse
 *  engineering, disclosure, and other restrictions; accordingly, it
 *  is "Unpublished--all rights reserved under the applicable
 *  copyright laws".
 *
 *  Use duplication, or disclosure by the Government is subject to
 *  restrictions as set forth in subparagraph (c)(1)(ii) of the Rights
 *  in Technical Data and Computer Licensed Programs clause of DFARS
 *  52.227 7013.
 *
 *  Copyright 2000-2002 Wind River Systems, Inc.
 *  Copyright 1996-1997 Epilogue Technology Corporation.
 *  Copyright 1998 Integrated Systems, Inc.
 *  All rights reserved.
 *
 *  *** Government Use ***
 *
 *  The Licensed Programs and their documentation were developed at
 *  private expense and no part of them is in the public domain.
 *
 *  The Licensed Programs are "Restricted Computer Software" as that
 *  term is defined in Clause 52.227-19 of the Federal Acquisition
 *  Regulations (FAR) and are "Commercial Computer Software" as that
 *  term is defined in Subpart 227.401 of the Department of Defense
 *  Federal Acquisition Regulation Supplement (DFARS).
 *
 *  (i) If the licensed Programs are supplied to the Department of
 *      Defense (DoD), the Licensed Programs are classified as
 *      "Commercial Computer Software" and the Government is acquiring
 *      only "restricted rights" in the Licensed Programs and their
 *      documentation as that term is defined in Clause 52.227
 *      7013(c)(1) of the DFARS, and
 *
 *  (ii) If the Licensed Programs are supplied to any unit or agency
 *      of the United States Government other than DoD, the
 *      Government's rights in the Licensed Programs and their
 *      documentation will be as defined in Clause 52.227-19(c)(2) of
 *      the FAR.
 ****************************************************************************/

/*
modification history
--------------------
01m,24feb05,spm  performance updates: add pointer redirection (SPR #100995)
01l,31jan05,dlk  Disable BUG_ASSERT() checks by default. Make tree printing
                 routines conditional upon DEBUG definition. Remove 'pfx'
		 and 'avlNodeMask' members of avl_node_t; use 'prefix'
		 exclusively.
01k,28may04,niq  Merging from base6 label POST_ITER5_FRZ16_REBASE
01j,10nov03,cdw  Rebase from base6 iteration 1 view
01i,04nov03,rlm  Ran batch header path update for header re-org.
01h,15sep03,vvv  updated path for new headers
01g,16jan03,syy  Temporary inclusion of assertion function by default
01f,14jan03,syy  Make inclusion of debugging utility prototypes conditional
01e,02jan03,syy  Exclude BUG_ASSERT when DEBUG is not defined
01d,20nov02,syy  Remove unused component node_flags from avl_node_t.
01c,23oct02,syy  Change maskToPfxLength() into a macro.
01b,16oct02,syy  Enable support or IPv4.
01a,20sep02,syy  modified from version 4.13 of the Attache code
*/

/*
 * avltree.h -- 
 * 
 *    This is the include file for AVL tree types and definitions.  
 *    This is a generic datastructure which will be used by various
 *    portions of Attache and Courier, primarily in the routing/
 *    forwarding table code.  
 *
 *    The code for routines to manipulate these structures can be
 *    found in attache/net/avltree.c.
 *
 *    The code for this AVL implementation was loosely based on the
 *    public domain AVL-2.0 implementation by Paul Vixie.  To quote 
 *    from Vixie's readme.txt:
 *       
 *       "I cannot take credit for the algorithms.  See "Algorithms & 
 *       Data Structures," Niklaus Wirth, Prentice-Hall 1986, ISBN 
 *       0-13-022005-1...If you use or redistribute this code, please 
 *       leave my name (and Wirth's) in the comments."
 *
 *    So, I have...
 *
 *    Sadly, as of September 1996, the book is not in print.  
 */

#ifndef _INCavltreeh
#define _INCavltreeh

#ifdef __cplusplus
extern "C" {
#endif

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "memLib.h"
#include "logLib.h"
#include <route/ipRouteNodeLib.h>

typedef short pool_id_t;
#define AVL_MALLOC(x)      malloc(x)
#define AVL_FREE(x)        free(x)

IMPORT struct ipRouteDispatchTable  avlRouteDispatchTable;

/* Main node structure.  Top (middle) node is pointed to by the
 * avl_head_t (below).  Each AVL node contains pointers to its 
 * corresponding entry and key(s), the actual storage for which
 * is elsewhere, probably in the 'entry'..
 */
typedef struct att_avl_node 
    {
    struct ipRouteNode  avlRibNode;     /* new */
#define avlNodeRtmEntry avlRibNode.pRtmEntry
#define avlNodeAddr     avlRibNode.pAddress
    int                 prefix;         /* prefix length  */
    struct att_avl_node *left;	        /* left/right children */
    struct att_avl_node *right;
    struct att_avl_node *prev;	        /* ordered list of nodes */
    struct att_avl_node *next;
    struct att_avl_node *less_specific; /* list of less specific matches */
    uchar_t  	        balance;        /* node balance state */
    } avl_node_t;

/* Head of AVL tree.  Points to top (middle) AVL node.  Also keeps
 * track of dispatch table and key details.  Code using this AVL
 * implementation should set up an AVL dispatch table (providing the
 * required routines) and define a structure to use as the node
 * entry.  All other access should happen through the AVL primitives 
 * defined in avltree.c.
 */
typedef struct att_avl_head 
    {
    struct ipRibHead    avlIpRibHead;   /* RIB head structure */
    ULONG               routeFormat;    /* supported route format */
    avl_node_t        * tree;    	/* avl tree */
    avl_node_t	      * node_list;	/* ordered list of all nodes */
    uchar_t         	head_flags;	/* tree status flags */
    } avl_head_t;

/* Macros for accessing the AVL nodes */
#define ROUTE_ENTRY_ADDRESS(pRouteNode) \
    ( ((avl_node_t *) (pRouteNode))->avlNodeAddr)

#define MASK2LEN(x, y) \
  ((x) == RIB_FORMAT_IPV4) ? \
     in_mask2len((struct in_addr *)&(y)) : (y)

/* Note, enabling AVL_BUG_ASSERT severely degrades performance */
#undef AVL_BUG_ASSERT	 /* If defined, enable BUG_ASSERT checks. */

#ifdef AVL_BUG_ASSERT
#define BUG_ASSERT(x) \
    if(!(x)) \
     printf("Assertion failed, file %s line %d\n",\
          __FILE__, __LINE__)
#else
#define BUG_ASSERT(x)
#endif /* AVL_BUG_ASSERT */
    
/* Flags for avl_head_t structure. */
#define AVL_CLEAR         0x00  /* flags clear */
#define AVL_CHECK_BALANCE 0x01	/* indicates balance should be checked */
#define AVL_BEST_MATCH    0x02  /* maintain best-match pointers */
#define AVL_CLOSING       0x04  /* tree is being closed down, not balanced */

/* Special 'flag' for calls to avl_create_tree() */
#define AVL_EXACT_MATCH	  0x00

/* Function return codes. */
#define AVL_SUCCESS          0          
#define AVL_ERROR            1 
#define AVL_NODE_NOT_FOUND   2

/* Balance values */
#define AVL_BALANCED         0x00
#define AVL_RIGHT_HEAVY      0x01
#define AVL_LEFT_HEAVY       0xFF

/* function prototypes for avl routines. */

extern STATUS avl_destroy_tree(avl_head_t *head, pool_id_t headp,
			       pool_id_t nodep);
extern avl_node_t *avl_create_node(int);
extern void avl_destroy_node(avl_head_t *head, avl_node_t *node, pool_id_t);
extern int avl_add_node(avl_head_t *, avl_node_t *);
extern int avl_delete (avl_head_t *, void *, int, pool_id_t);
extern avl_node_t *avl_lookup(avl_head_t *, void *, int);    
extern avl_node_t *avl_exact_lookup_in_tree(avl_head_t *, void *, int, int,
                                           ULONG, avl_node_t *, avl_node_t *);
extern avl_node_t *avl_best_match(avl_head_t *, void *, int);
extern avl_node_t *avl_lex_next_match(avl_head_t *, void *, int, int, ULONG);

#ifdef DEBUG
extern int avl_print(avl_head_t *);

/* The following functions are temporary */
extern void printIpAddr (const char *, const void *, ULONG, BOOL);
#endif /* DEBUG */

#ifdef __cplusplus
}
#endif

#endif /* _INCavltreeh */