Changeset 449 in vbox

Timestamp:

Jan 30, 2007 11:03:57 PM (18 years ago)

Author:

vboxsync

svn:sync-xref-src-repo-rev:

18030

Message:

RTAvlrGCPtr*

Location:

trunk

Files:

• include/iprt/avl.h (modified) (3 diffs)
• src/VBox/Runtime/Makefile (modified) (1 diff)
• src/VBox/Runtime/table/avlrgcptr.cpp (copied) (copied from trunk/src/VBox/Runtime/table/avlrogcptr.cpp ) (2 diffs)

trunk/include/iprt/avl.h

@@ -284 +284 @@
 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 +333 @@
 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 +345 @@
 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);
 
 /** @} */

trunk/src/VBox/Runtime/Makefile

@@ -128 +128 @@
         table/avloioport.cpp \
         table/avlpv.cpp \
+        table/avlrgcptr.cpp \
         table/avlrogcphys.cpp \
         table/avlrogcptr.cpp \

trunk/src/VBox/Runtime/table/avlrgcptr.cpp

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * InnoTek Portable Runtime - AVL tree, RTGCPTR, range, unique keys, offset pointers.
+ * InnoTek Portable Runtime - AVL tree, RTGCPTR, range, unique keys.
  */
 
@@ -31 +31 @@
  * AVL configuration.
  */
-#define KAVL_FN(a)                  RTAvlroGCPtr##a
+#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                AVLROGCPTRNODECORE
-#define PKAVLNODECORE               PAVLROGCPTRNODECORE
-#define PPKAVLNODECORE              PPAVLROGCPTRNODECORE
+#define KAVLNODECORE                AVLRGCPTRNODECORE
+#define PKAVLNODECORE               PAVLRGCPTRNODECORE
+#define PPKAVLNODECORE              PPAVLRGCPTRNODECORE
 #define KAVLKEY                     RTGCPTR
 #define PKAVLKEY                    PRTGCPTR
-#define KAVLENUMDATA                AVLROGCPTRENUMDATA
-#define PKAVLENUMDATA               PAVLROGCPTRENUMDATA
-#define PKAVLCALLBACK               PAVLROGCPTRCALLBACK
-#define KAVL_OFFSET                 1
+#define KAVLENUMDATA                AVLRGCPTRENUMDATA
+#define PKAVLENUMDATA               PAVLRGCPTRENUMDATA
+#define PKAVLCALLBACK               PAVLRGCPTRCALLBACK
 #define KAVL_RANGE                  1