Changeset 33268 in vbox

Timestamp:

Oct 20, 2010 3:37:15 PM (14 years ago)

Author:

vboxsync

Message:

IPRT: Added an AVL tree taking void * ranges.

Location:

trunk

Files:

• include/iprt/avl.h (modified) (1 diff)
• src/VBox/Runtime/common/table/avlrpv.cpp (copied) (copied from trunk/src/VBox/Runtime/common/table/avlpv.cpp ) (4 diffs)

trunk/include/iprt/avl.h

@@ -124 +124 @@
 
 
+/** AVL tree of void pointer ranges.
+ * @{
+ */
+
+/**
+ * AVL key type
+ */
+typedef void *AVLRPVKEY;
+
+/**
+ * AVL Core node.
+ */
+typedef struct AVLRPVNodeCore
+{
+    AVLRPVKEY               Key;        /**< First key value in the range (inclusive). */
+    AVLRPVKEY               KeyLast;    /**< Last key value in the range (inclusive). */
+    struct AVLRPVNodeCore  *pLeft;      /**< Pointer to left leaf node. */
+    struct AVLRPVNodeCore  *pRight;     /**< Pointer to right leaf node. */
+    unsigned char           uchHeight;  /**< Height of this tree: max(height(left), height(right)) + 1 */
+} AVLRPVNODECORE, *PAVLRPVNODECORE, **PPAVLRPVNODECORE;
+
+/** A tree with void pointer keys. */
+typedef PAVLRPVNODECORE    AVLRPVTREE;
+/** Pointer to a tree with void pointer keys. */
+typedef PPAVLRPVNODECORE   PAVLRPVTREE;
+
+/** Callback function for AVLPVDoWithAll(). */
+typedef DECLCALLBACK(int) AVLRPVCALLBACK(PAVLRPVNODECORE, void *);
+/** Pointer to callback function for AVLPVDoWithAll(). */
+typedef AVLRPVCALLBACK *PAVLRPVCALLBACK;
+
+/*
+ * Functions.
+ */
+RTDECL(bool)            RTAvlrPVInsert(PAVLRPVTREE ppTree, PAVLRPVNODECORE pNode);
+RTDECL(PAVLRPVNODECORE) RTAvlrPVRemove(PAVLRPVTREE ppTree, AVLRPVKEY Key);
+RTDECL(PAVLRPVNODECORE) RTAvlrPVGet(PAVLRPVTREE ppTree, AVLRPVKEY Key);
+RTDECL(PAVLRPVNODECORE) RTAvlrPVRangeGet(PAVLRPVTREE ppTree, AVLRPVKEY Key);
+RTDECL(PAVLRPVNODECORE) RTAvlrPVRangeRemove(PAVLRPVTREE ppTree, AVLRPVKEY Key);
+RTDECL(PAVLRPVNODECORE) RTAvlrPVGetBestFit(PAVLRPVTREE ppTree, AVLRPVKEY Key, bool fAbove);
+RTDECL(PAVLRPVNODECORE) RTAvlrPVRemoveBestFit(PAVLRPVTREE ppTree, AVLRPVKEY Key, bool fAbove);
+RTDECL(int)             RTAvlrPVDoWithAll(PAVLRPVTREE ppTree, int fFromLeft, PAVLRPVCALLBACK pfnCallBack, void *pvParam);
+RTDECL(int)             RTAvlrPVDestroy(PAVLRPVTREE ppTree, PAVLRPVCALLBACK pfnCallBack, void *pvParam);
+
+/** @} */
+
+
+
 /** AVL tree of uint32_t
  * @{

trunk/src/VBox/Runtime/common/table/avlrpv.cpp

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * IPRT - AVL tree, void *, unique keys.
+ * IPRT - AVL tree, void *, range, unique keys.
  */
 
@@ -35 +35 @@
  * AVL configuration.
  */
-#define KAVL_FN(a)                  RTAvlPV##a
+#define KAVL_FN(a)                  RTAvlrPV##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                AVLRPVNODECORE
+#define PKAVLNODECORE               PAVLRPVNODECORE
+#define PPKAVLNODECORE              PPAVLRPVNODECORE
+#define KAVLKEY                     AVLRPVKEY
+#define PKAVLKEY                    PAVLRPVKEY
+#define KAVLENUMDATA                AVLRPVENUMDATA
+#define PKAVLENUMDATA               PAVLRPVENUMDATA
+#define PKAVLCALLBACK               PAVLRPVCALLBACK
+#define KAVL_RANGE                  1
 
 
@@ -51 +52 @@
  * 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)          ( (uintptr_t)(key1) >  (uintptr_t)(key2) )
+#define KAVL_E(key1, key2)          ( (uintptr_t)(key1) == (uintptr_t)(key2) )
+#define KAVL_NE(key1, key2)         ( (uintptr_t)(key1) != (uintptr_t)(key2) )
+#define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E)     ( (uintptr_t)(key1B) == (uintptr_t)(key2B) && (uintptr_t)(key1E) == (uintptr_t)(key2E) )
+#define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E)  ( (uintptr_t)(key1B) <= (uintptr_t)(key2E) && (uintptr_t)(key1E) >= (uintptr_t)(key2B) )
+#define KAVL_R_IS_IN_RANGE(key1B, key1E, key2)              KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2)
 
 
@@ -72 +76 @@
 #include "avl_Get.cpp.h"
 #include "avl_GetBestFit.cpp.h"
+#include "avl_Range.cpp.h"
 #include "avl_RemoveBestFit.cpp.h"
 #include "avl_DoWithAll.cpp.h"