Changeset 33268 in vbox for trunk/src

Timestamp:

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

Author:

vboxsync

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

66828

Message:

IPRT: Added an AVL tree taking void * ranges.

File:

• trunk/src/VBox/Runtime/common/table/avlrpv.cpp (copied) (copied from trunk/src/VBox/Runtime/common/table/avlpv.cpp ) (4 diffs)

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"