Index: /trunk/include/iprt/avl.h =================================================================== --- /trunk/include/iprt/avl.h (revision 448) +++ /trunk/include/iprt/avl.h (revision 449) @@ -284,7 +284,7 @@ typedef PPAVLGCPTRNODECORE PAVLGCPTRTREE; -/** Callback function for RTAvlroGCPtrDoWithAll(). */ +/** Callback function for RTAvlGCPtrDoWithAll(). */ typedef DECLCALLBACK(int) AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser); -/** Pointer to callback function for RTAvlroGCPtrDoWithAll(). */ +/** Pointer to callback function for RTAvlGCPtrDoWithAll(). */ typedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK; @@ -333,7 +333,7 @@ typedef AVLOGCPTRTREE *PPAVLOGCPTRNODECORE; -/** Callback function for RTAvlroGCPtrDoWithAll(). */ +/** Callback function for RTAvloGCPtrDoWithAll(). */ typedef DECLCALLBACK(int) AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser); -/** Pointer to callback function for RTAvlroGCPtrDoWithAll(). */ +/** Pointer to callback function for RTAvloGCPtrDoWithAll(). */ typedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK; @@ -345,4 +345,54 @@ RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove); RTDECL(int) RTAvloGCPtrDestroy(PAVLOGCPTRTREE pTree, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam); + +/** @} */ + + +/** AVL tree of RTGCPTR ranges. + * @{ + */ + +/** + * AVL Core node. + */ +typedef struct _AVLRGCPtrNodeCore +{ + /** First key value in the range (inclusive). */ + RTGCPTR Key; + /** Last key value in the range (inclusive). */ + RTGCPTR KeyLast; + /** Offset to the left leaf node, relative to this field. */ + struct _AVLRGCPtrNodeCore *pLeft; + /** Offset to the right leaf node, relative to this field. */ + struct _AVLRGCPtrNodeCore *pRight; + /** Height of this tree: max(height(left), height(right)) + 1 */ + unsigned char uchHeight; +} AVLRGCPTRNODECORE, *PAVLRGCPTRNODECORE; + +/** A offset base tree with RTGCPTR keys. */ +typedef PAVLRGCPTRNODECORE AVLRGCPTRTREE; +/** Pointer to a offset base tree with RTGCPTR keys. */ +typedef AVLRGCPTRTREE *PAVLRGCPTRTREE; + +/** Pointer to an internal tree pointer. + * In this case it's a pointer to a relative offset. */ +typedef AVLRGCPTRTREE *PPAVLRGCPTRNODECORE; + +/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */ +typedef DECLCALLBACK(int) AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser); +/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */ +typedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK; + +RTDECL(bool) RTAvlrGCPtrInsert( PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode); +RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key); +RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGet( PAVLRGCPTRTREE pTree, RTGCPTR Key); +RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetBestFit( PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove); +RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeGet( PAVLRGCPTRTREE pTree, RTGCPTR Key); +RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key); +RTDECL(int) RTAvlrGCPtrDoWithAll( PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam); +RTDECL(int) RTAvlrGCPtrDestroy( PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam); +RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRoot( PAVLRGCPTRTREE pTree); +RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetLeft( PAVLRGCPTRNODECORE pNode); +RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRight( PAVLRGCPTRNODECORE pNode); /** @} */ Index: /trunk/src/VBox/Runtime/Makefile =================================================================== --- /trunk/src/VBox/Runtime/Makefile (revision 448) +++ /trunk/src/VBox/Runtime/Makefile (revision 449) @@ -128,4 +128,5 @@ table/avloioport.cpp \ table/avlpv.cpp \ + table/avlrgcptr.cpp \ table/avlrogcphys.cpp \ table/avlrogcptr.cpp \ Index: /trunk/src/VBox/Runtime/table/avlrgcptr.cpp =================================================================== --- /trunk/src/VBox/Runtime/table/avlrgcptr.cpp (revision 449) +++ /trunk/src/VBox/Runtime/table/avlrgcptr.cpp (revision 449) @@ -0,0 +1,78 @@ +/* $Id$ */ +/** @file + * InnoTek Portable Runtime - AVL tree, RTGCPTR, range, unique keys. + */ + +/* + * Copyright (C) 2001-2004 knut st. osmundsen (bird-src-spam@anduin.net) + * Copyright (C) 2006 InnoTek Systemberatung GmbH + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License 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. + * + * If you received this file as part of a commercial VirtualBox + * distribution, then only the terms of your commercial VirtualBox + * license agreement apply instead of the previous paragraph. + */ + +#ifndef NOFILEID +static const char szFileId[] = "Id: kAVLULInt.c,v 1.4 2003/02/13 02:02:38 bird Exp $"; +#endif + +/******************************************************************************* +* Defined Constants And Macros * +*******************************************************************************/ +/* + * AVL configuration. + */ +#define KAVL_FN(a) RTAvlrGCPtr##a +#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */ +#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */ +#define KAVLNODECORE AVLRGCPTRNODECORE +#define PKAVLNODECORE PAVLRGCPTRNODECORE +#define PPKAVLNODECORE PPAVLRGCPTRNODECORE +#define KAVLKEY RTGCPTR +#define PKAVLKEY PRTGCPTR +#define KAVLENUMDATA AVLRGCPTRENUMDATA +#define PKAVLENUMDATA PAVLRGCPTRENUMDATA +#define PKAVLCALLBACK PAVLRGCPTRCALLBACK +#define KAVL_RANGE 1 + + +/* + * AVL Compare macros + */ +#define KAVL_G( key1, key2) ( (RTGCUINTPTR)(key1) > (RTGCUINTPTR)(key2) ) +#define KAVL_E( key1, key2) ( (RTGCUINTPTR)(key1) == (RTGCUINTPTR)(key2) ) +#define KAVL_NE(key1, key2) ( (RTGCUINTPTR)(key1) != (RTGCUINTPTR)(key2) ) +#define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) ( (RTGCUINTPTR)(key1B) == (RTGCUINTPTR)(key2B) && (RTGCUINTPTR)(key1E) == (RTGCUINTPTR)(key2E) ) +#define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (RTGCUINTPTR)(key1B) <= (RTGCUINTPTR)(key2E) && (RTGCUINTPTR)(key1E) >= (RTGCUINTPTR)(key2B) ) +#define KAVL_R_IS_IN_RANGE(key1B, key1E, key2) KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2) + + + +/******************************************************************************* +* Header Files * +*******************************************************************************/ +#include +#include + +/* + * Include the code. + */ +#define SSToDS(ptr) ptr +#define KMAX RT_MAX +#define kASSERT Assert +#include "avl_Base.cpp.h" +#include "avl_Get.cpp.h" +#include "avl_Range.cpp.h" +#include "avl_DoWithAll.cpp.h" +#include "avl_Destroy.cpp.h" +#include "avl_GetBestFit.cpp.h" +#include "avl_Enum.cpp.h" +