Changeset 96 in vbox

Timestamp:

Jan 17, 2007 1:22:21 PM (18 years ago)

Author:

vboxsync

Message:

RTAvlGCPtr.

Location:

trunk

Files:

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

trunk/include/iprt/avl.h

@@ -260 +260 @@
 
 
+/** AVL tree of RTGCPTRs.
+ * @{
+ */
+
+/**
+ * AVL Core node.
+ */
+typedef struct _AVLGCPtrNodeCore
+{
+    /** Key value. */
+    RTGCPTR             Key;
+    /** Pointer to the left node. */
+    struct _AVLGCPtrNodeCore *pLeft;
+    /** Pointer to the right node. */
+    struct _AVLGCPtrNodeCore *pRight;
+    /** Height of this tree: max(height(left), height(right)) + 1 */
+    unsigned char       uchHeight;
+} AVLGCPTRNODECORE, *PAVLGCPTRNODECORE, **PPAVLGCPTRNODECORE;
+
+/** A tree of RTGCPTR keys. */
+typedef PAVLGCPTRNODECORE     AVLGCPTRTREE;
+/** Pointer to a tree of RTGCPTR keys. */
+typedef PPAVLGCPTRNODECORE    PAVLGCPTRTREE;
+
+/** Callback function for RTAvlroGCPtrDoWithAll(). */
+typedef DECLCALLBACK(int)   AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser);
+/** Pointer to callback function for RTAvlroGCPtrDoWithAll(). */
+typedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK;
+
+RTDECL(bool)                    RTAvlGCPtrInsert(PAVLGCPTRTREE pTree, PAVLGCPTRNODECORE pNode);
+RTDECL(PAVLGCPTRNODECORE)       RTAvlGCPtrRemove(PAVLGCPTRTREE pTree, RTGCPTR Key);
+RTDECL(PAVLGCPTRNODECORE)       RTAvlGCPtrGet(PAVLGCPTRTREE pTree, RTGCPTR Key);
+RTDECL(int)                     RTAvlGCPtrDoWithAll(PAVLGCPTRTREE pTree, int fFromLeft, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
+RTDECL(PAVLGCPTRNODECORE)       RTAvlGCPtrGetBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
+RTDECL(PAVLGCPTRNODECORE)       RTAvlGCPtrRemoveBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
+RTDECL(int)                     RTAvlGCPtrDestroy(PAVLGCPTRTREE pTree, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
+
+/** @} */
+
+
 /** AVL tree of RTGCPTRs - using relative offsets internally.
  * @{

trunk/src/VBox/Runtime/Makefile

@@ -123 +123 @@
         assert.cpp \
         table/avlhcphys.cpp \
+        table/avlgcptr.cpp \
         table/avlogcphys.cpp \
         table/avlogcptr.cpp \
@@ -465 +466 @@
         assert.cpp \
         table/avlhcphys.cpp \
+        table/avlgcptr.cpp \
         table/avlogcphys.cpp \
         table/avlohcphys.cpp \

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

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * InnoTek Portable Runtime - AVL tree, void *, unique keys.
+ * InnoTek Portable Runtime - AVL tree, RTGCPTR, unique keys.
  */
 
@@ -30 +30 @@
  * AVL configuration.
  */
-#define KAVL_FN(a)                  RTAvlPV##a
+#define KAVL_FN(a)                  RTAvlGCPtr##a
 #define KAVL_MAX_STACK              27  /* Up to 2^24 nodes. */
 #define KAVL_CHECK_FOR_EQUAL_INSERT 1   /* No duplicate keys! */
-#define KAVLNODECORE                AVLPVNODECORE
-#define PKAVLNODECORE               PAVLPVNODECORE
-#define PPKAVLNODECORE              PPAVLPVNODECORE
-#define KAVLKEY                     AVLPVKEY
-#define PKAVLKEY                    PAVLPVKEY
-#define KAVLENUMDATA                AVLPVENUMDATA
-#define PKAVLENUMDATA               PAVLPVENUMDATA
-#define PKAVLCALLBACK               PAVLPVCALLBACK
+#define KAVLNODECORE                AVLGCPTRNODECORE
+#define PKAVLNODECORE               PAVLGCPTRNODECORE
+#define PPKAVLNODECORE              PPAVLGCPTRNODECORE
+#define KAVLKEY                     RTGCPTR
+#define PKAVLKEY                    PRTGCPTR
+#define KAVLENUMDATA                AVLGCPTRENUMDATA
+#define PKAVLENUMDATA               PAVLGCPTRENUMDATA
+#define PKAVLCALLBACK               PAVLGCPTRCALLBACK
 
 
@@ -46 +46 @@
  * AVL Compare macros
  */
-#define KAVL_G(key1, key2)          ( (const char*)(key1) >  (const char*)(key2) )
-#define KAVL_E(key1, key2)          ( (const char*)(key1) == (const char*)(key2) )
-#define KAVL_NE(key1, key2)         ( (const char*)(key1) != (const char*)(key2) )
+#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) )