72 lines
2.3 KiB
C
72 lines
2.3 KiB
C
/* avltLib.h - header file for AVL tree */
|
|
|
|
/* Copyright 1999-2003 Wind River Systems, Inc. */
|
|
|
|
/*
|
|
modification history
|
|
--------------------
|
|
01c,03may04,rp removed avlTreeErase
|
|
01b,06apr04,rp added avlInsertInform, avlRemoveInsert and avlTreeErase
|
|
01a,08feb03,zl moved out uint key version to avlUintLib, replaced
|
|
GENERIC_ARGUMENT with void *.
|
|
01g,08aug03,zl resolved avlLib aliasing problem.
|
|
01f,24jan01,sn end file with newline(!) to avoid cpp errors
|
|
01e,10feb00,abd added avlMinimumGet and avlMaximumGet
|
|
01d,10feb00,abd added avlTreeWalk, avlTreePrint, avlTreeErase, avlTreePrintErase
|
|
01c,03feb00,abd added avlInsertInform, avlRemoveInsert
|
|
01b,24jan00,abd added avlSuccessorGet and avlPredecessorGet
|
|
01a,08feb99,wkn created.
|
|
*/
|
|
|
|
#ifndef __INCavlLibh
|
|
#define __INCavlLibh
|
|
|
|
#ifdef __cplusplus
|
|
extern "C" {
|
|
#endif
|
|
|
|
#ifndef _ASMLANGUAGE
|
|
|
|
/* typedefs */
|
|
|
|
typedef struct avl_node
|
|
{
|
|
struct avl_node * left; /* pointer to the left subtree */
|
|
struct avl_node * right; /* pointer to the right subtree */
|
|
int height; /* height of the subtree rooted at this node */
|
|
} AVL_NODE;
|
|
|
|
typedef AVL_NODE * AVL_TREE; /* points to the root node of the tree */
|
|
|
|
typedef STATUS (*AVL_COMPARE)(AVL_NODE *pNode, void * pKey);
|
|
|
|
/* callback routines for avlUintTreeWalk */
|
|
|
|
typedef STATUS (*AVL_CALLBACK)(AVL_NODE *pNode, void * pArg);
|
|
|
|
/* function declarations */
|
|
|
|
STATUS avlInsert (AVL_TREE * pRoot, AVL_NODE * pNode, void * pKey,
|
|
AVL_COMPARE cmpRtn);
|
|
AVL_NODE * avlDelete (AVL_TREE * pRoot, void * pKey, AVL_COMPARE cmpRtn);
|
|
AVL_NODE * avlSearch (AVL_TREE root, void * pKey, AVL_COMPARE cmpRtn);
|
|
AVL_NODE * avlSuccessorGet (AVL_TREE root, void * pKey, AVL_COMPARE cmpRtn);
|
|
AVL_NODE * avlPredecessorGet (AVL_TREE root, void * pKey, AVL_COMPARE cmpRtn);
|
|
AVL_NODE * avlMinimumGet (AVL_TREE root);
|
|
AVL_NODE * avlMaximumGet (AVL_TREE root);
|
|
STATUS avlTreeWalk (AVL_TREE pRoot, AVL_CALLBACK preRtn, void * preArg,
|
|
AVL_CALLBACK inRtn, void * inArg,
|
|
AVL_CALLBACK postRtn, void * postArg);
|
|
STATUS avlInsertInform (AVL_TREE * pRoot, void * pNewNode, void * key,
|
|
void ** ppKeyHolder, AVL_COMPARE cmpRtn);
|
|
void * avlRemoveInsert (AVL_TREE * pRoot, void * pNewNode, void * key,
|
|
AVL_COMPARE cmpRtn);
|
|
|
|
#endif /* _ASMLANGUAGE */
|
|
|
|
#ifdef __cplusplus
|
|
}
|
|
#endif
|
|
|
|
#endif /* __INCavlLibh */
|