avl_Base.cpp.h revision 210e87cc03f92d54681b81a81cc1fdbd48a9d2c8
/* $Id$ */
/** @file
* kAVLBase - basic routines for all AVL trees.
*/
/*
* Copyright (C) 2001-2002 knut st. osmundsen (bird-src-spam@anduin.net)
*
* This file is part of VirtualBox Open Source Edition (OSE), as
* available from http://www.virtualbox.org. This file is free software;
* General Public License (GPL) as published by the Free Software
* Foundation, in version 2 as it comes in the "COPYING" file of the
* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
*
* The contents of this file may alternatively be used under the terms
* of the Common Development and Distribution License Version 1.0
* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
* VirtualBox OSE distribution, in which case the provisions of the
* CDDL are applicable instead of those of the GPL.
*
* You may elect to license modified versions of this file under the
* terms and conditions of either the GPL or the CDDL or both.
*/
#ifndef _kAVLBase_h_
#define _kAVLBase_h_
/** @page pg_rt_kAVL kAVL Template configuration.
* @internal
*
* This is a template made to implement multiple AVL trees. The differences
* among the implementations are related to the key used.
*
* \#define KAVL_FN
* Use this to alter the names of the AVL functions.
* Must be defined.
*
* \#define KAVL_EQUAL_ALLOWED
* Define this to tell us that equal keys are allowed.
* Then Equal keys will be put in a list pointed to by pList in the KAVLNODECORE.
* This is by default not defined.
*
* \#define KAVL_CHECK_FOR_EQUAL_INSERT
* Define this to enable insert check for equal nodes.
* This is by default not defined.
*
* \#define KAVL_MAX_STACK
* Use this to specify the number of stack entries the stack will use when inserting
* and removing nodes from the tree. I think the size should be about
* log2(<max nodes>) + 3
* Must be defined.
*
*/
/*******************************************************************************
* Defined Constants And Macros *
*******************************************************************************/
/** @def KAVL_GET_POINTER
* Reads a 'pointer' value.
*
* @returns The native pointer.
* @param pp Pointer to the pointer to read.
*/
/** @def KAVL_GET_POINTER_NULL
* Reads a 'pointer' value which can be KAVL_NULL.
*
* @returns The native pointer.
* @returns NULL pointer if KAVL_NULL.
* @param pp Pointer to the pointer to read.
*/
/** @def KAVL_SET_POINTER
* Writes a 'pointer' value.
* For offset-based schemes offset relative to pp is calculated and assigned to *pp.
*
* @returns stored pointer.
* @param pp Pointer to where to store the pointer.
* @param p Native pointer to assign to *pp.
*/
/** @def KAVL_SET_POINTER_NULL
* Writes a 'pointer' value which can be KAVL_NULL.
*
* For offset-based schemes offset relative to pp is calculated and assigned to *pp,
* if p is not KAVL_NULL of course.
*
* @returns stored pointer.
* @param pp Pointer to where to store the pointer.
* @param pp2 Pointer to where to pointer to assign to pp. This can be KAVL_NULL
*/
#ifndef KAVL_GET_POINTER
# ifdef KAVL_OFFSET
# define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) != KAVL_NULL ? (intptr_t)KAVL_GET_POINTER(pp2) - (intptr_t)(pp) : KAVL_NULL )
# else
# endif
#endif
/** @def KAVL_NULL
* The NULL 'pointer' equivalent.
*/
#ifndef KAVL_NULL
# ifdef KAVL_OFFSET
# define KAVL_NULL 0
# else
# endif
#endif
#ifndef KAVL_RANGE
#endif
/** @def KAVL_DECL
* Function declation macro in the RTDECL tradition.
* @param a_Type The function return type. */
#ifndef KAVL_DECL
#endif
/*******************************************************************************
* Structures and Typedefs *
*******************************************************************************/
/*
* A stack used to avoid recursive calls...
*/
typedef struct _kAvlStack
{
unsigned cEntries;
} KAVLSTACK, *PKAVLSTACK;
typedef struct _kAvlStack2
{
unsigned cEntries;
char achFlags[KAVL_MAX_STACK];
} KAVLSTACK2, *PLAVLSTACK2;
/**
* Rewinds a stack of pointers to pointers to nodes, rebalancing the tree.
* @param pStack Pointer to stack to rewind.
* @sketch LOOP thru all stack entries
* BEGIN
* Get pointer to pointer to node (and pointer to node) from the stack.
* IF 2 higher left subtree than in right subtree THEN
* BEGIN
* IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
* * n+2|n+3
* / \ / \
* n+2 n ==> n+1 n+1|n+2
* / \ / \
* n+1 n|n+1 n|n+1 n
*
* Or with keys:
*
* 4 2
* / \ / \
* 2 5 ==> 1 4
* / \ / \
* 1 3 3 5
*
* ELSE
* * n+2
* / \ / \
* n+2 n n+1 n+1
* / \ ==> / \ / \
* n n+1 n L R n
* / \
* L R
*
* Or with keys:
* 6 4
* / \ / \
* 2 7 ==> 2 6
* / \ / \ / \
* 1 4 1 3 5 7
* / \
* 3 5
* END
* ELSE IF 2 higher in right subtree than in left subtree THEN
* BEGIN
* Same as above but left <==> right. (invert the picture)
* ELSE
* IF correct height THEN break
* ELSE correct height.
* END
*/
{
{
/** @todo Perhaps some of these KAVL_SET_POINTER_NULL() cases could be optimized away.. */
{
{
pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
}
else
{
}
}
{
{
pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
}
else
{
}
}
else
{
break;
}
}
}
/**
* Inserts a node into the AVL-tree.
* @returns TRUE if inserted.
* FALSE if node exists in tree.
* @param ppTree Pointer to the AVL-tree root node pointer.
* @param pNode Pointer to the node which is to be added.
* @sketch Find the location of the node (using binary tree algorithm.):
* LOOP until KAVL_NULL leaf pointer
* BEGIN
* Add node pointer pointer to the AVL-stack.
* IF new-node-key < node key THEN
* left
* ELSE
* right
* END
* Fill in leaf node and insert it.
* Rebalance the tree.
*/
{
register PKAVLNODECORE pCurNode;
#ifdef KAVL_RANGE
#endif
#ifdef KAVL_RANGE
return false;
#endif
for (;;)
{
else
break;
#ifdef KAVL_EQUAL_ALLOWED
{
/*
* If equal then we'll use a list of equal nodes.
*/
return true;
}
#endif
#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
return false;
#endif
else
}
#ifdef KAVL_EQUAL_ALLOWED
#endif
return true;
}
/**
* Removes a node from the AVL-tree.
* @returns Pointer to the node.
* @param ppTree Pointer to the AVL-tree root node pointer.
* @param Key Key value of the node which is to be removed.
* @sketch Find the node which is to be removed:
* LOOP until not found
* BEGIN
* Add node pointer pointer to the AVL-stack.
* IF the keys matches THEN break!
* IF remove key < node key THEN
* left
* ELSE
* right
* END
* IF found THEN
* BEGIN
* IF left node not empty THEN
* BEGIN
* Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
* Start at left node.
* LOOP until right node is empty
* BEGIN
* Add to stack.
* go right.
* END
* Link out the found node.
* Replace the node which is to be removed with the found node.
* Correct the stack entry for the pointer to the left tree.
* END
* ELSE
* BEGIN
* Move up right node.
* Remove last stack entry.
* END
* Balance tree using stack.
* END
* return pointer to the removed node (if found).
*/
{
register PKAVLNODECORE pDeleteNode;
for (;;)
{
if (*ppDeleteNode != KAVL_NULL)
else
return NULL;
break;
else
}
{
/* find the rightmost node in the left tree. */
{
}
/* link out pLeftLeast */
/* link it in place of the delete node. */
}
else
{
}
return pDeleteNode;
}
#endif