summaryrefslogtreecommitdiffstats
path: root/src/VBox/Runtime/common/table
diff options
context:
space:
mode:
Diffstat (limited to 'src/VBox/Runtime/common/table')
-rw-r--r--src/VBox/Runtime/common/table/Makefile.kup0
-rw-r--r--src/VBox/Runtime/common/table/avl_Base.cpp.h460
-rw-r--r--src/VBox/Runtime/common/table/avl_Destroy.cpp.h110
-rw-r--r--src/VBox/Runtime/common/table/avl_DoWithAll.cpp.h142
-rw-r--r--src/VBox/Runtime/common/table/avl_Enum.cpp.h95
-rw-r--r--src/VBox/Runtime/common/table/avl_Get.cpp.h67
-rw-r--r--src/VBox/Runtime/common/table/avl_GetBestFit.cpp.h103
-rw-r--r--src/VBox/Runtime/common/table/avl_Range.cpp.h84
-rw-r--r--src/VBox/Runtime/common/table/avl_RemoveBestFit.cpp.h70
-rw-r--r--src/VBox/Runtime/common/table/avl_RemoveNode.cpp.h143
-rw-r--r--src/VBox/Runtime/common/table/avlgcphys.cpp78
-rw-r--r--src/VBox/Runtime/common/table/avlgcptr.cpp78
-rw-r--r--src/VBox/Runtime/common/table/avlhcphys.cpp78
-rw-r--r--src/VBox/Runtime/common/table/avllu32.cpp79
-rw-r--r--src/VBox/Runtime/common/table/avlogcphys.cpp79
-rw-r--r--src/VBox/Runtime/common/table/avlogcptr.cpp80
-rw-r--r--src/VBox/Runtime/common/table/avlohcphys.cpp79
-rw-r--r--src/VBox/Runtime/common/table/avloioport.cpp79
-rw-r--r--src/VBox/Runtime/common/table/avlou32.cpp80
-rw-r--r--src/VBox/Runtime/common/table/avlpv.cpp78
-rw-r--r--src/VBox/Runtime/common/table/avlrfoff.cpp84
-rw-r--r--src/VBox/Runtime/common/table/avlrgcptr.cpp84
-rw-r--r--src/VBox/Runtime/common/table/avlrogcphys.cpp85
-rw-r--r--src/VBox/Runtime/common/table/avlrogcptr.cpp85
-rw-r--r--src/VBox/Runtime/common/table/avlroioport.cpp83
-rw-r--r--src/VBox/Runtime/common/table/avlroogcptr.cpp92
-rw-r--r--src/VBox/Runtime/common/table/avlrpv.cpp83
-rw-r--r--src/VBox/Runtime/common/table/avlru64.cpp83
-rw-r--r--src/VBox/Runtime/common/table/avlruintptr.cpp84
-rw-r--r--src/VBox/Runtime/common/table/avlu32.cpp78
-rw-r--r--src/VBox/Runtime/common/table/avlu64.cpp78
-rw-r--r--src/VBox/Runtime/common/table/avluintptr.cpp78
-rw-r--r--src/VBox/Runtime/common/table/avlul.cpp78
-rw-r--r--src/VBox/Runtime/common/table/table.cpp32
34 files changed, 3169 insertions, 0 deletions
diff --git a/src/VBox/Runtime/common/table/Makefile.kup b/src/VBox/Runtime/common/table/Makefile.kup
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/src/VBox/Runtime/common/table/Makefile.kup
diff --git a/src/VBox/Runtime/common/table/avl_Base.cpp.h b/src/VBox/Runtime/common/table/avl_Base.cpp.h
new file mode 100644
index 00000000..e63e777e
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_Base.cpp.h
@@ -0,0 +1,460 @@
+/* $Id: avl_Base.cpp.h $ */
+/** @file
+ * kAVLBase - basic routines for all AVL trees.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef _kAVLBase_h_
+#define _kAVLBase_h_
+
+
+/** @page pg_rt_kAVL kAVL Template configuration.
+ * @internal
+ *
+ * This is a template made to implement multiple AVL trees. The differences
+ * among the implementations are related to the key used.
+ *
+ * \#define KAVL_FN
+ * Use this to alter the names of the AVL functions.
+ * Must be defined.
+ *
+ * \#define KAVL_EQUAL_ALLOWED
+ * Define this to tell us that equal keys are allowed.
+ * Then Equal keys will be put in a list pointed to by pList in the KAVLNODECORE.
+ * This is by default not defined.
+ *
+ * \#define KAVL_CHECK_FOR_EQUAL_INSERT
+ * Define this to enable insert check for equal nodes.
+ * This is by default not defined.
+ *
+ * \#define KAVL_MAX_STACK
+ * Use this to specify the number of stack entries the stack will use when inserting
+ * and removing nodes from the tree. I think the size should be about
+ * log2(<max nodes>) + 3
+ * Must be defined.
+ *
+ */
+
+/*******************************************************************************
+* Defined Constants And Macros *
+*******************************************************************************/
+#define AVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? pNode->uchHeight : 0))
+
+/** @def KAVL_GET_POINTER
+ * Reads a 'pointer' value.
+ *
+ * @returns The native pointer.
+ * @param pp Pointer to the pointer to read.
+ */
+
+/** @def KAVL_GET_POINTER_NULL
+ * Reads a 'pointer' value which can be KAVL_NULL.
+ *
+ * @returns The native pointer.
+ * @returns NULL pointer if KAVL_NULL.
+ * @param pp Pointer to the pointer to read.
+ */
+
+/** @def KAVL_SET_POINTER
+ * Writes a 'pointer' value.
+ * For offset-based schemes offset relative to pp is calculated and assigned to *pp.
+ *
+ * @returns stored pointer.
+ * @param pp Pointer to where to store the pointer.
+ * @param p Native pointer to assign to *pp.
+ */
+
+/** @def KAVL_SET_POINTER_NULL
+ * Writes a 'pointer' value which can be KAVL_NULL.
+ *
+ * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
+ * if p is not KAVL_NULL of course.
+ *
+ * @returns stored pointer.
+ * @param pp Pointer to where to store the pointer.
+ * @param pp2 Pointer to where to pointer to assign to pp. This can be KAVL_NULL
+ */
+
+#ifndef KAVL_GET_POINTER
+# ifdef KAVL_OFFSET
+# define KAVL_GET_POINTER(pp) ( (PKAVLNODECORE)((intptr_t)(pp) + *(pp)) )
+# define KAVL_GET_POINTER_NULL(pp) ( *(pp) != KAVL_NULL ? KAVL_GET_POINTER(pp) : NULL )
+# define KAVL_SET_POINTER(pp, p) ( (*(pp)) = ((intptr_t)(p) - (intptr_t)(pp)) )
+# define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) != KAVL_NULL ? (intptr_t)KAVL_GET_POINTER(pp2) - (intptr_t)(pp) : KAVL_NULL )
+# else
+# define KAVL_GET_POINTER(pp) ( *(pp) )
+# define KAVL_GET_POINTER_NULL(pp) ( *(pp) )
+# define KAVL_SET_POINTER(pp, p) ( (*(pp)) = (p) )
+# define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) )
+# endif
+#endif
+
+
+/** @def KAVL_NULL
+ * The NULL 'pointer' equivalent.
+ */
+#ifndef KAVL_NULL
+# ifdef KAVL_OFFSET
+# define KAVL_NULL 0
+# else
+# define KAVL_NULL NULL
+# endif
+#endif
+
+#ifndef KAVL_RANGE
+# define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) KAVL_E(key1B, key2B)
+# define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) KAVL_E(key1B, key2B)
+#endif
+
+/** @def KAVL_DECL
+ * Function declation macro in the RTDECL tradition.
+ * @param a_Type The function return type. */
+#ifndef KAVL_DECL
+# define KAVL_DECL(a_Type) RTDECL(a_Type)
+#endif
+
+
+/*******************************************************************************
+* Structures and Typedefs *
+*******************************************************************************/
+/*
+ * A stack used to avoid recursive calls...
+ */
+typedef struct _kAvlStack
+{
+ unsigned cEntries;
+ PPKAVLNODECORE aEntries[KAVL_MAX_STACK];
+} KAVLSTACK, *PKAVLSTACK;
+
+typedef struct _kAvlStack2
+{
+ unsigned cEntries;
+ PKAVLNODECORE aEntries[KAVL_MAX_STACK];
+ char achFlags[KAVL_MAX_STACK];
+} KAVLSTACK2, *PLAVLSTACK2;
+
+
+
+/**
+ * Rewinds a stack of pointers to pointers to nodes, rebalancing the tree.
+ * @param pStack Pointer to stack to rewind.
+ * @sketch LOOP thru all stack entries
+ * BEGIN
+ * Get pointer to pointer to node (and pointer to node) from the stack.
+ * IF 2 higher left subtree than in right subtree THEN
+ * BEGIN
+ * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
+ * * n+2|n+3
+ * / \ / \
+ * n+2 n ==> n+1 n+1|n+2
+ * / \ / \
+ * n+1 n|n+1 n|n+1 n
+ *
+ * Or with keys:
+ *
+ * 4 2
+ * / \ / \
+ * 2 5 ==> 1 4
+ * / \ / \
+ * 1 3 3 5
+ *
+ * ELSE
+ * * n+2
+ * / \ / \
+ * n+2 n n+1 n+1
+ * / \ ==> / \ / \
+ * n n+1 n L R n
+ * / \
+ * L R
+ *
+ * Or with keys:
+ * 6 4
+ * / \ / \
+ * 2 7 ==> 2 6
+ * / \ / \ / \
+ * 1 4 1 3 5 7
+ * / \
+ * 3 5
+ * END
+ * ELSE IF 2 higher in right subtree than in left subtree THEN
+ * BEGIN
+ * Same as above but left <==> right. (invert the picture)
+ * ELSE
+ * IF correct height THEN break
+ * ELSE correct height.
+ * END
+ */
+DECLINLINE(void) KAVL_FN(Rebalance)(PKAVLSTACK pStack)
+{
+ while (pStack->cEntries > 0)
+ {
+ /** @todo Perhaps some of these KAVL_SET_POINTER_NULL() cases could be optimized away.. */
+ PPKAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries];
+ PKAVLNODECORE pNode = KAVL_GET_POINTER(ppNode);
+ PKAVLNODECORE pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
+ unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
+ PKAVLNODECORE pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
+ unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode);
+
+ if (uchRightHeight + 1 < uchLeftHeight)
+ {
+ PKAVLNODECORE pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft);
+ PKAVLNODECORE pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight);
+ unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
+
+ if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
+ {
+ KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight);
+ KAVL_SET_POINTER(&pLeftNode->pRight, pNode);
+ pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
+ KAVL_SET_POINTER(ppNode, pLeftNode);
+ }
+ else
+ {
+ KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft);
+ KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight);
+ KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode);
+ KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode);
+ pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
+ pLeftRightNode->uchHeight = uchLeftHeight;
+ KAVL_SET_POINTER(ppNode, pLeftRightNode);
+ }
+ }
+ else if (uchLeftHeight + 1 < uchRightHeight)
+ {
+ PKAVLNODECORE pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft);
+ unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
+ PKAVLNODECORE pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight);
+
+ if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
+ {
+ KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft);
+ KAVL_SET_POINTER(&pRightNode->pLeft, pNode);
+ pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
+ KAVL_SET_POINTER(ppNode, pRightNode);
+ }
+ else
+ {
+ KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight);
+ KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft);
+ KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode);
+ KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode);
+ pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
+ pRightLeftNode->uchHeight = uchRightHeight;
+ KAVL_SET_POINTER(ppNode, pRightLeftNode);
+ }
+ }
+ else
+ {
+ unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1);
+ if (uchHeight == pNode->uchHeight)
+ break;
+ pNode->uchHeight = uchHeight;
+ }
+ }
+
+}
+
+
+
+
+/**
+ * Inserts a node into the AVL-tree.
+ * @returns TRUE if inserted.
+ * FALSE if node exists in tree.
+ * @param ppTree Pointer to the AVL-tree root node pointer.
+ * @param pNode Pointer to the node which is to be added.
+ * @sketch Find the location of the node (using binary tree algorithm.):
+ * LOOP until KAVL_NULL leaf pointer
+ * BEGIN
+ * Add node pointer pointer to the AVL-stack.
+ * IF new-node-key < node key THEN
+ * left
+ * ELSE
+ * right
+ * END
+ * Fill in leaf node and insert it.
+ * Rebalance the tree.
+ */
+KAVL_DECL(bool) KAVL_FN(Insert)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
+{
+ KAVLSTACK AVLStack;
+ PPKAVLNODECORE ppCurNode = ppTree;
+ PKAVLNODECORE pCurNode;
+ KAVLKEY Key = pNode->Key; NOREF(Key);
+#ifdef KAVL_RANGE
+ KAVLKEY KeyLast = pNode->KeyLast; NOREF(KeyLast);
+#endif
+
+ AVLStack.cEntries = 0;
+
+#ifdef KAVL_RANGE
+ if (Key > KeyLast)
+ return false;
+#endif
+
+ for (;;)
+ {
+ if (*ppCurNode != KAVL_NULL)
+ pCurNode = KAVL_GET_POINTER(ppCurNode);
+ else
+ break;
+
+ kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
+ AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
+#ifdef KAVL_EQUAL_ALLOWED
+ if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
+ {
+ /*
+ * If equal then we'll use a list of equal nodes.
+ */
+ pNode->pLeft = pNode->pRight = KAVL_NULL;
+ pNode->uchHeight = 0;
+ KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
+ KAVL_SET_POINTER(&pCurNode->pList, pNode);
+ return true;
+ }
+#endif
+#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
+ if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
+ return false;
+#endif
+ if (KAVL_G(pCurNode->Key, Key))
+ ppCurNode = &pCurNode->pLeft;
+ else
+ ppCurNode = &pCurNode->pRight;
+ }
+
+ pNode->pLeft = pNode->pRight = KAVL_NULL;
+#ifdef KAVL_EQUAL_ALLOWED
+ pNode->pList = KAVL_NULL;
+#endif
+ pNode->uchHeight = 1;
+ KAVL_SET_POINTER(ppCurNode, pNode);
+
+ KAVL_FN(Rebalance)(SSToDS(&AVLStack));
+ return true;
+}
+
+
+/**
+ * Removes a node from the AVL-tree.
+ * @returns Pointer to the node.
+ * @param ppTree Pointer to the AVL-tree root node pointer.
+ * @param Key Key value of the node which is to be removed.
+ * @sketch Find the node which is to be removed:
+ * LOOP until not found
+ * BEGIN
+ * Add node pointer pointer to the AVL-stack.
+ * IF the keys matches THEN break!
+ * IF remove key < node key THEN
+ * left
+ * ELSE
+ * right
+ * END
+ * IF found THEN
+ * BEGIN
+ * IF left node not empty THEN
+ * BEGIN
+ * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
+ * Start at left node.
+ * LOOP until right node is empty
+ * BEGIN
+ * Add to stack.
+ * go right.
+ * END
+ * Link out the found node.
+ * Replace the node which is to be removed with the found node.
+ * Correct the stack entry for the pointer to the left tree.
+ * END
+ * ELSE
+ * BEGIN
+ * Move up right node.
+ * Remove last stack entry.
+ * END
+ * Balance tree using stack.
+ * END
+ * return pointer to the removed node (if found).
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(Remove)(PPKAVLNODECORE ppTree, KAVLKEY Key)
+{
+ KAVLSTACK AVLStack;
+ PPKAVLNODECORE ppDeleteNode = ppTree;
+ PKAVLNODECORE pDeleteNode;
+
+ AVLStack.cEntries = 0;
+
+ for (;;)
+ {
+ if (*ppDeleteNode != KAVL_NULL)
+ pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
+ else
+ return NULL;
+
+ kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
+ AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
+ if (KAVL_E(pDeleteNode->Key, Key))
+ break;
+
+ if (KAVL_G(pDeleteNode->Key, Key))
+ ppDeleteNode = &pDeleteNode->pLeft;
+ else
+ ppDeleteNode = &pDeleteNode->pRight;
+ }
+
+ if (pDeleteNode->pLeft != KAVL_NULL)
+ {
+ /* find the rightmost node in the left tree. */
+ const unsigned iStackEntry = AVLStack.cEntries;
+ PPKAVLNODECORE ppLeftLeast = &pDeleteNode->pLeft;
+ PKAVLNODECORE pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
+
+ while (pLeftLeast->pRight != KAVL_NULL)
+ {
+ kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
+ AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
+ ppLeftLeast = &pLeftLeast->pRight;
+ pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
+ }
+
+ /* link out pLeftLeast */
+ KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
+
+ /* link it in place of the delete node. */
+ KAVL_SET_POINTER_NULL(&pLeftLeast->pLeft, &pDeleteNode->pLeft);
+ KAVL_SET_POINTER_NULL(&pLeftLeast->pRight, &pDeleteNode->pRight);
+ pLeftLeast->uchHeight = pDeleteNode->uchHeight;
+ KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
+ AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
+ }
+ else
+ {
+ KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
+ AVLStack.cEntries--;
+ }
+
+ KAVL_FN(Rebalance)(SSToDS(&AVLStack));
+ return pDeleteNode;
+}
+
+#endif
diff --git a/src/VBox/Runtime/common/table/avl_Destroy.cpp.h b/src/VBox/Runtime/common/table/avl_Destroy.cpp.h
new file mode 100644
index 00000000..5b17d1b8
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_Destroy.cpp.h
@@ -0,0 +1,110 @@
+/* $Id: avl_Destroy.cpp.h $ */
+/** @file
+ * kAVLDestroy - Walk the tree calling a callback to destroy all the nodes.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef _kAVLDestroy_h_
+#define _kAVLDestroy_h_
+
+
+/**
+ * Destroys the specified tree, starting with the root node and working our way down.
+ *
+ * @returns 0 on success.
+ * @returns Return value from callback on failure. On failure, the tree will be in
+ * an unbalanced condition and only further calls to the Destroy should be
+ * made on it. Note that the node we fail on will be considered dead and
+ * no action is taken to link it back into the tree.
+ * @param ppTree Pointer to the AVL-tree root node pointer.
+ * @param pfnCallBack Pointer to callback function.
+ * @param pvUser User parameter passed on to the callback function.
+ */
+KAVL_DECL(int) KAVL_FN(Destroy)(PPKAVLNODECORE ppTree, PKAVLCALLBACK pfnCallBack, void *pvUser)
+{
+ unsigned cEntries;
+ PKAVLNODECORE apEntries[KAVL_MAX_STACK];
+ int rc;
+
+ if (*ppTree == KAVL_NULL)
+ return VINF_SUCCESS;
+
+ cEntries = 1;
+ apEntries[0] = KAVL_GET_POINTER(ppTree);
+ while (cEntries > 0)
+ {
+ /*
+ * Process the subtrees first.
+ */
+ PKAVLNODECORE pNode = apEntries[cEntries - 1];
+ if (pNode->pLeft != KAVL_NULL)
+ apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+ else if (pNode->pRight != KAVL_NULL)
+ apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+ else
+ {
+#ifdef KAVL_EQUAL_ALLOWED
+ /*
+ * Process nodes with the same key.
+ */
+ while (pNode->pList != KAVL_NULL)
+ {
+ PKAVLNODECORE pEqual = KAVL_GET_POINTER(&pNode->pList);
+ KAVL_SET_POINTER(&pNode->pList, KAVL_GET_POINTER_NULL(&pEqual->pList));
+ pEqual->pList = KAVL_NULL;
+
+ rc = pfnCallBack(pEqual, pvUser);
+ if (rc != VINF_SUCCESS)
+ return rc;
+ }
+#endif
+
+ /*
+ * Unlink the node.
+ */
+ if (--cEntries > 0)
+ {
+ PKAVLNODECORE pParent = apEntries[cEntries - 1];
+ if (KAVL_GET_POINTER(&pParent->pLeft) == pNode)
+ pParent->pLeft = KAVL_NULL;
+ else
+ pParent->pRight = KAVL_NULL;
+ }
+ else
+ *ppTree = KAVL_NULL;
+
+ kASSERT(pNode->pLeft == KAVL_NULL);
+ kASSERT(pNode->pRight == KAVL_NULL);
+ rc = pfnCallBack(pNode, pvUser);
+ if (rc != VINF_SUCCESS)
+ return rc;
+ }
+ } /* while */
+
+ kASSERT(*ppTree == KAVL_NULL);
+
+ return VINF_SUCCESS;
+}
+
+#endif
+
diff --git a/src/VBox/Runtime/common/table/avl_DoWithAll.cpp.h b/src/VBox/Runtime/common/table/avl_DoWithAll.cpp.h
new file mode 100644
index 00000000..02883f58
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_DoWithAll.cpp.h
@@ -0,0 +1,142 @@
+/* $Id: avl_DoWithAll.cpp.h $ */
+/** @file
+ * kAVLDoWithAll - Do with all nodes routine for AVL trees.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef _kAVLDoWithAll_h_
+#define _kAVLDoWithAll_h_
+
+
+/**
+ * Iterates thru all nodes in the given tree.
+ * @returns 0 on success. Return from callback on failure.
+ * @param ppTree Pointer to the AVL-tree root node pointer.
+ * @param fFromLeft TRUE: Left to right.
+ * FALSE: Right to left.
+ * @param pfnCallBack Pointer to callback function.
+ * @param pvParam Userparameter passed on to the callback function.
+ */
+KAVL_DECL(int) KAVL_FN(DoWithAll)(PPKAVLNODECORE ppTree, int fFromLeft, PKAVLCALLBACK pfnCallBack, void * pvParam)
+{
+ KAVLSTACK2 AVLStack;
+ PKAVLNODECORE pNode;
+#ifdef KAVL_EQUAL_ALLOWED
+ PKAVLNODECORE pEqual;
+#endif
+ int rc;
+
+ if (*ppTree == KAVL_NULL)
+ return VINF_SUCCESS;
+
+ AVLStack.cEntries = 1;
+ AVLStack.achFlags[0] = 0;
+ AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree);
+
+ if (fFromLeft)
+ { /* from left */
+ while (AVLStack.cEntries > 0)
+ {
+ pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
+
+ /* left */
+ if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
+ {
+ if (pNode->pLeft != KAVL_NULL)
+ {
+ AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
+ AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+ continue;
+ }
+ }
+
+ /* center */
+ rc = pfnCallBack(pNode, pvParam);
+ if (rc != VINF_SUCCESS)
+ return rc;
+#ifdef KAVL_EQUAL_ALLOWED
+ if (pNode->pList != KAVL_NULL)
+ for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pList))
+ {
+ rc = pfnCallBack(pEqual, pvParam);
+ if (rc != VINF_SUCCESS)
+ return rc;
+ }
+#endif
+
+ /* right */
+ AVLStack.cEntries--;
+ if (pNode->pRight != KAVL_NULL)
+ {
+ AVLStack.achFlags[AVLStack.cEntries] = 0;
+ AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+ }
+ } /* while */
+ }
+ else
+ { /* from right */
+ while (AVLStack.cEntries > 0)
+ {
+ pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
+
+ /* right */
+ if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
+ {
+ if (pNode->pRight != KAVL_NULL)
+ {
+ AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
+ AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+ continue;
+ }
+ }
+
+ /* center */
+ rc = pfnCallBack(pNode, pvParam);
+ if (rc != VINF_SUCCESS)
+ return rc;
+#ifdef KAVL_EQUAL_ALLOWED
+ if (pNode->pList != KAVL_NULL)
+ for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pList))
+ {
+ rc = pfnCallBack(pEqual, pvParam);
+ if (rc != VINF_SUCCESS)
+ return rc;
+ }
+#endif
+
+ /* left */
+ AVLStack.cEntries--;
+ if (pNode->pLeft != KAVL_NULL)
+ {
+ AVLStack.achFlags[AVLStack.cEntries] = 0;
+ AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+ }
+ } /* while */
+ }
+
+ return VINF_SUCCESS;
+}
+
+
+#endif
+
diff --git a/src/VBox/Runtime/common/table/avl_Enum.cpp.h b/src/VBox/Runtime/common/table/avl_Enum.cpp.h
new file mode 100644
index 00000000..4f5212ba
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_Enum.cpp.h
@@ -0,0 +1,95 @@
+/* $Id: avl_Enum.cpp.h $ */
+/** @file
+ * Enumeration routines for AVL trees.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef _kAVLEnum_h_
+#define _kAVLEnum_h_
+
+
+/**
+ * Gets the root node.
+ *
+ * @returns Pointer to the root node.
+ * @returns NULL if the tree is empty.
+ *
+ * @param ppTree Pointer to pointer to the tree root node.
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(GetRoot)(PPKAVLNODECORE ppTree)
+{
+ return KAVL_GET_POINTER_NULL(ppTree);
+}
+
+
+/**
+ * Gets the right node.
+ *
+ * @returns Pointer to the right node.
+ * @returns NULL if no right node.
+ *
+ * @param pNode The current node.
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(GetRight)(PKAVLNODECORE pNode)
+{
+ if (pNode)
+ return KAVL_GET_POINTER_NULL(&pNode->pRight);
+ return NULL;
+}
+
+
+/**
+ * Gets the left node.
+ *
+ * @returns Pointer to the left node.
+ * @returns NULL if no left node.
+ *
+ * @param pNode The current node.
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(GetLeft)(PKAVLNODECORE pNode)
+{
+ if (pNode)
+ return KAVL_GET_POINTER_NULL(&pNode->pLeft);
+ return NULL;
+}
+
+
+# ifdef KAVL_EQUAL_ALLOWED
+/**
+ * Gets the next node with an equal (start) key.
+ *
+ * @returns Pointer to the next equal node.
+ * @returns NULL if the current node was the last one with this key.
+ *
+ * @param pNode The current node.
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(GetNextEqual)(PKAVLNODECORE pNode)
+{
+ if (pNode)
+ return KAVL_GET_POINTER_NULL(&pNode->pList);
+ return NULL;
+}
+# endif /* KAVL_EQUAL_ALLOWED */
+
+#endif
+
diff --git a/src/VBox/Runtime/common/table/avl_Get.cpp.h b/src/VBox/Runtime/common/table/avl_Get.cpp.h
new file mode 100644
index 00000000..ad5fdb36
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_Get.cpp.h
@@ -0,0 +1,67 @@
+/* $Id: avl_Get.cpp.h $ */
+/** @file
+ * kAVLGet - get routine for AVL trees.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef _kAVLGet_h_
+#define _kAVLGet_h_
+
+
+/**
+ * Gets a node from the tree (does not remove it!)
+ * @returns Pointer to the node holding the given key.
+ * @param ppTree Pointer to the AVL-tree root node pointer.
+ * @param Key Key value of the node which is to be found.
+ * @author knut st. osmundsen
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(Get)(PPKAVLNODECORE ppTree, KAVLKEY Key)
+{
+ PKAVLNODECORE pNode = KAVL_GET_POINTER_NULL(ppTree);
+
+ if (pNode)
+ {
+ while (KAVL_NE(pNode->Key, Key))
+ {
+ if (KAVL_G(pNode->Key, Key))
+ {
+ if (pNode->pLeft != KAVL_NULL)
+ pNode = KAVL_GET_POINTER(&pNode->pLeft);
+ else
+ return NULL;
+ }
+ else
+ {
+ if (pNode->pRight != KAVL_NULL)
+ pNode = KAVL_GET_POINTER(&pNode->pRight);
+ else
+ return NULL;
+ }
+ }
+ }
+
+ return pNode;
+}
+
+
+#endif
diff --git a/src/VBox/Runtime/common/table/avl_GetBestFit.cpp.h b/src/VBox/Runtime/common/table/avl_GetBestFit.cpp.h
new file mode 100644
index 00000000..57f8ad4f
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_GetBestFit.cpp.h
@@ -0,0 +1,103 @@
+/* $Id: avl_GetBestFit.cpp.h $ */
+/** @file
+ * kAVLGetBestFit - Get Best Fit routine for AVL trees.
+ * Intended specially on heaps. The tree should allow duplicate keys.
+ *
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef _kAVLGetBestFit_h_
+#define _kAVLGetBestFit_h_
+
+
+/**
+ * Finds the best fitting node in the tree for the given Key value.
+ * @returns Pointer to the best fitting node found.
+ * @param ppTree Pointer to Pointer to the tree root node.
+ * @param Key The Key of which is to be found a best fitting match for..
+ * @param fAbove TRUE: Returned node is have the closest key to Key from above.
+ * FALSE: Returned node is have the closest key to Key from below.
+ * @sketch The best fitting node is always located in the searchpath above you.
+ * >= (above): The node where you last turned left.
+ * <= (below): the node where you last turned right.
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(GetBestFit)(PPKAVLNODECORE ppTree, KAVLKEY Key, bool fAbove)
+{
+ PKAVLNODECORE pNode = KAVL_GET_POINTER_NULL(ppTree);
+ if (pNode)
+ {
+ PKAVLNODECORE pNodeLast = NULL;
+ if (fAbove)
+ { /* pNode->Key >= Key */
+ while (KAVL_NE(pNode->Key, Key))
+ {
+ if (KAVL_G(pNode->Key, Key))
+ {
+ if (pNode->pLeft != KAVL_NULL)
+ {
+ pNodeLast = pNode;
+ pNode = KAVL_GET_POINTER(&pNode->pLeft);
+ }
+ else
+ return pNode;
+ }
+ else
+ {
+ if (pNode->pRight != KAVL_NULL)
+ pNode = KAVL_GET_POINTER(&pNode->pRight);
+ else
+ return pNodeLast;
+ }
+ }
+ }
+ else
+ { /* pNode->Key <= Key */
+ while (KAVL_NE(pNode->Key, Key))
+ {
+ if (KAVL_G(pNode->Key, Key))
+ {
+ if (pNode->pLeft != KAVL_NULL)
+ pNode = KAVL_GET_POINTER(&pNode->pLeft);
+ else
+ return pNodeLast;
+ }
+ else
+ {
+ if (pNode->pRight != KAVL_NULL)
+ {
+ pNodeLast = pNode;
+ pNode = KAVL_GET_POINTER(&pNode->pRight);
+ }
+ else
+ return pNode;
+ }
+ }
+ }
+ }
+
+ /* perfect match or nothing. */
+ return pNode;
+}
+
+
+#endif
diff --git a/src/VBox/Runtime/common/table/avl_Range.cpp.h b/src/VBox/Runtime/common/table/avl_Range.cpp.h
new file mode 100644
index 00000000..989eb069
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_Range.cpp.h
@@ -0,0 +1,84 @@
+/* $Id: avl_Range.cpp.h $ */
+/** @file
+ * kAVLRange - Range routines for AVL trees.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef _kAVLRange_h_
+#define _kAVLRange_h_
+
+/**
+ * Finds the range containing the specified key.
+ *
+ * @returns Pointer to the matching range.
+ *
+ * @param ppTree Pointer to Pointer to the tree root node.
+ * @param Key The Key to find matching range for.
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(RangeGet)(PPKAVLNODECORE ppTree, KAVLKEY Key)
+{
+ PKAVLNODECORE pNode = KAVL_GET_POINTER_NULL(ppTree);
+ if (pNode)
+ {
+ for (;;)
+ {
+ if (KAVL_R_IS_IN_RANGE(pNode->Key, pNode->KeyLast, Key))
+ return pNode;
+ if (KAVL_G(pNode->Key, Key))
+ {
+ if (pNode->pLeft != KAVL_NULL)
+ pNode = KAVL_GET_POINTER(&pNode->pLeft);
+ else
+ return NULL;
+ }
+ else
+ {
+ if (pNode->pRight != KAVL_NULL)
+ pNode = KAVL_GET_POINTER(&pNode->pRight);
+ else
+ return NULL;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+
+/**
+ * Removes the range containing the specified key.
+ *
+ * @returns Pointer to the matching range.
+ *
+ * @param ppTree Pointer to Pointer to the tree root node.
+ * @param Key The Key to remove matching range for.
+ */
+RTDECL(PKAVLNODECORE) KAVL_FN(RangeRemove)(PPKAVLNODECORE ppTree, KAVLKEY Key)
+{
+ PKAVLNODECORE pNode = KAVL_FN(RangeGet)(ppTree, Key);
+ if (pNode)
+ return KAVL_FN(Remove)(ppTree, pNode->Key);
+ return NULL;
+}
+
+#endif
diff --git a/src/VBox/Runtime/common/table/avl_RemoveBestFit.cpp.h b/src/VBox/Runtime/common/table/avl_RemoveBestFit.cpp.h
new file mode 100644
index 00000000..cc5ba6e2
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_RemoveBestFit.cpp.h
@@ -0,0 +1,70 @@
+/* $Id: avl_RemoveBestFit.cpp.h $ */
+/** @file
+ * kAVLRemoveBestFit - Remove Best Fit routine for AVL trees.
+ * Intended specially on heaps. The tree should allow duplicate keys.
+ *
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef _kAVLRemoveBestFit_h_
+#define _kAVLRemoveBestFit_h_
+
+
+/**
+ * Finds the best fitting node in the tree for the given Key value.
+ * And removes it.
+ * @returns Pointer to the best fitting node found.
+ * @param ppTree Pointer to Pointer to the tree root node.
+ * @param Key The Key of which is to be found a best fitting match for..
+ * @param fAbove TRUE: Returned node is have the closest key to Key from above.
+ * FALSE: Returned node is have the closest key to Key from below.
+ * @sketch The best fitting node is always located in the searchpath above you.
+ * >= (above): The node where you last turned left.
+ * <= (below): the node where you last turned right.
+ * @remark This implementation should be speeded up slightly!
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(RemoveBestFit)(PPKAVLNODECORE ppTree, KAVLKEY Key, bool fAbove)
+{
+ /*
+ * If we find anything we'll have to remove the node and return it.
+ * But, if duplicate keys are allowed we'll have to check for multiple
+ * nodes first and return one of them before doing an expensive remove+insert.
+ */
+ PKAVLNODECORE pNode = KAVL_FN(GetBestFit)(ppTree, Key, fAbove);
+ if (pNode != NULL)
+ {
+#ifdef KAVL_EQUAL_ALLOWED
+ if (pNode->pList != KAVL_NULL)
+ {
+ PKAVLNODECORE pRet = KAVL_GET_POINTER(&pNode->pList);
+ KAVL_SET_POINTER_NULL(&pNode->pList, &pRet->pList);
+ return pRet;
+ }
+#endif
+ pNode = KAVL_FN(Remove)(ppTree, pNode->Key);
+ }
+ return pNode;
+}
+
+
+#endif
diff --git a/src/VBox/Runtime/common/table/avl_RemoveNode.cpp.h b/src/VBox/Runtime/common/table/avl_RemoveNode.cpp.h
new file mode 100644
index 00000000..63173f9b
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_RemoveNode.cpp.h
@@ -0,0 +1,143 @@
+/* $Id: avl_RemoveNode.cpp.h $ */
+/** @file
+ * kAVLRemove2 - Remove specific node (by pointer) from an AVL tree.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+
+/**
+ * Removes the specified node from the tree.
+ *
+ * @returns Pointer to the removed node (NULL if not in the tree)
+ * @param ppTree Pointer to the AVL-tree root structure.
+ * @param pNode Pointer to the node to be removed.
+ *
+ * @remark This implementation isn't the most efficient, but it's relatively
+ * short and easier to manage.
+ */
+KAVL_DECL(PKAVLNODECORE) KAVL_FN(RemoveNode)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
+{
+#ifdef KAVL_EQUAL_ALLOWED
+ /*
+ * Find the right node by key together with the parent node.
+ */
+ KAVLKEY const Key = pNode->Key;
+ PKAVLNODECORE pParent = NULL;
+ PKAVLNODECORE pCurNode = KAVL_GET_POINTER_NULL(ppTree);
+ if (!pCurNode)
+ return NULL;
+ while (KAVL_NE(pCurNode->Key, Key))
+ {
+ pParent = pCurNode;
+ if (KAVL_G(pCurNode->Key, Key))
+ {
+ if (pCurNode->pLeft != KAVL_NULL)
+ pCurNode = KAVL_GET_POINTER(&pCurNode->pLeft);
+ else
+ return NULL;
+ }
+ else
+ {
+ if (pCurNode->pRight != KAVL_NULL)
+ pCurNode = KAVL_GET_POINTER(&pCurNode->pRight);
+ else
+ return NULL;
+ }
+ }
+
+ if (pCurNode != pNode)
+ {
+ /*
+ * It's not the one we want, but it could be in the duplicate list.
+ */
+ while (pCurNode->pList != KAVL_NULL)
+ {
+ PKAVLNODECORE pNext = KAVL_GET_POINTER(&pCurNode->pList);
+ if (pNext == pNode)
+ {
+ if (pNode->pList != KAVL_NULL)
+ KAVL_SET_POINTER(&pCurNode->pList, KAVL_GET_POINTER(&pNode->pList));
+ else
+ pCurNode->pList = KAVL_NULL;
+ pNode->pList = KAVL_NULL;
+ return pNode;
+ }
+ pCurNode = pNext;
+ }
+ return NULL;
+ }
+
+ /*
+ * Ok, it's the one we want alright.
+ *
+ * Simply remove it if it's the only one with they Key, if there are
+ * duplicates we'll have to unlink it and insert the first duplicate
+ * in our place.
+ */
+ if (pNode->pList == KAVL_NULL)
+ KAVL_FN(Remove)(ppTree, pNode->Key);
+ else
+ {
+ PKAVLNODECORE pNewUs = KAVL_GET_POINTER(&pNode->pList);
+
+ pNewUs->uchHeight = pNode->uchHeight;
+
+ if (pNode->pLeft != KAVL_NULL)
+ KAVL_SET_POINTER(&pNewUs->pLeft, KAVL_GET_POINTER(&pNode->pLeft));
+ else
+ pNewUs->pLeft = KAVL_NULL;
+
+ if (pNode->pRight != KAVL_NULL)
+ KAVL_SET_POINTER(&pNewUs->pRight, KAVL_GET_POINTER(&pNode->pRight));
+ else
+ pNewUs->pRight = KAVL_NULL;
+
+ if (pParent)
+ {
+ if (KAVL_GET_POINTER_NULL(&pParent->pLeft) == pNode)
+ KAVL_SET_POINTER(&pParent->pLeft, pNewUs);
+ else
+ KAVL_SET_POINTER(&pParent->pRight, pNewUs);
+ }
+ else
+ KAVL_SET_POINTER(ppTree, pNewUs);
+ }
+
+ return pNode;
+
+#else
+ /*
+ * Delete it, if we got the wrong one, reinsert it.
+ *
+ * This ASSUMS that the caller is NOT going to hand us a lot
+ * of wrong nodes but just uses this API for his convenience.
+ */
+ KAVLNODE *pRemovedNode = KAVL_FN(Remove)(pRoot, pNode->Key);
+ if (pRemovedNode == pNode)
+ return pRemovedNode;
+
+ KAVL_FN(Insert)(pRoot, pRemovedNode);
+ return NULL;
+#endif
+}
+
diff --git a/src/VBox/Runtime/common/table/avlgcphys.cpp b/src/VBox/Runtime/common/table/avlgcphys.cpp
new file mode 100644
index 00000000..f7489d76
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlgcphys.cpp
@@ -0,0 +1,78 @@
+/* $Id: avlgcphys.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTGCPHYS, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlGCPhys##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLGCPHYSNODECORE
+#define PKAVLNODECORE PAVLGCPHYSNODECORE
+#define PPKAVLNODECORE PPAVLGCPHYSNODECORE
+#define KAVLKEY RTGCPHYS
+#define PKAVLKEY PRTGCPHYS
+#define KAVLENUMDATA AVLGCPHYSENUMDATA
+#define PKAVLENUMDATA PAVLGCPHYSENUMDATA
+#define PKAVLCALLBACK PAVLGCPHYSCALLBACK
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlgcptr.cpp b/src/VBox/Runtime/common/table/avlgcptr.cpp
new file mode 100644
index 00000000..12262c04
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlgcptr.cpp
@@ -0,0 +1,78 @@
+/* $Id: avlgcptr.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTGCPTR, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef NOFILEID
+static const char szFileId[] = "Id: kAVLPVInt.c,v 1.5 2003/02/13 02:02:35 bird Exp $";
+#endif
+
+
+/*********************************************************************************************************************************
+* Defined Constants And Macros *
+*********************************************************************************************************************************/
+/*
+ * AVL configuration.
+ */
+#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 AVLGCPTRNODECORE
+#define PKAVLNODECORE PAVLGCPTRNODECORE
+#define PPKAVLNODECORE PPAVLGCPTRNODECORE
+#define KAVLKEY RTGCPTR
+#define PKAVLKEY PRTGCPTR
+#define KAVLENUMDATA AVLGCPTRENUMDATA
+#define PKAVLENUMDATA PAVLGCPTRENUMDATA
+#define PKAVLCALLBACK PAVLGCPTRCALLBACK
+
+
+/*
+ * 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) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlhcphys.cpp b/src/VBox/Runtime/common/table/avlhcphys.cpp
new file mode 100644
index 00000000..a38db4a7
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlhcphys.cpp
@@ -0,0 +1,78 @@
+/* $Id: avlhcphys.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTHCPHYS, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlHCPhys##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLHCPHYSNODECORE
+#define PKAVLNODECORE PAVLHCPHYSNODECORE
+#define PPKAVLNODECORE PPAVLHCPHYSNODECORE
+#define KAVLKEY RTHCPHYS
+#define PKAVLKEY PRTHCPHYS
+#define KAVLENUMDATA AVLHCPHYSENUMDATA
+#define PKAVLENUMDATA PAVLHCPHYSENUMDATA
+#define PKAVLCALLBACK PAVLHCPHYSCALLBACK
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avllu32.cpp b/src/VBox/Runtime/common/table/avllu32.cpp
new file mode 100644
index 00000000..e37b7fa7
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avllu32.cpp
@@ -0,0 +1,79 @@
+/* $Id: avllu32.cpp $ */
+/** @file
+ * IPRT - AVL tree, uint32_t, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvllU32##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_EQUAL_ALLOWED 1 /* List duplicate keys! */
+#define KAVLNODECORE AVLLU32NODECORE
+#define PKAVLNODECORE PAVLLU32NODECORE
+#define PPKAVLNODECORE PPAVLLU32NODECORE
+#define KAVLKEY AVLLU32KEY
+#define PKAVLKEY PAVLLU32KEY
+#define KAVLENUMDATA AVLLU32ENUMDATA
+#define PKAVLENUMDATA PAVLLU32ENUMDATA
+#define PKAVLCALLBACK PAVLLU32CALLBACK
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G(key1, key2) ( (key1) > (key2) )
+#define KAVL_E(key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_GetBestFit.cpp.h"
+#include "avl_RemoveNode.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlogcphys.cpp b/src/VBox/Runtime/common/table/avlogcphys.cpp
new file mode 100644
index 00000000..10b9288f
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlogcphys.cpp
@@ -0,0 +1,79 @@
+/* $Id: avlogcphys.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTGCPHYS, unique keys, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvloGCPhys##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLOGCPHYSNODECORE
+#define PKAVLNODECORE PAVLOGCPHYSNODECORE
+#define PPKAVLNODECORE PPAVLOGCPHYSNODECORE
+#define KAVLKEY RTGCPHYS
+#define PKAVLKEY PRTGCPHYS
+#define KAVLENUMDATA AVLOGCPHYSENUMDATA
+#define PKAVLENUMDATA PAVLOGCPHYSENUMDATA
+#define PKAVLCALLBACK PAVLOGCPHYSCALLBACK
+#define KAVL_OFFSET 1
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlogcptr.cpp b/src/VBox/Runtime/common/table/avlogcptr.cpp
new file mode 100644
index 00000000..f069d966
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlogcptr.cpp
@@ -0,0 +1,80 @@
+/* $Id: avlogcptr.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTGCPTR, unique keys, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvloGCPtr##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLOGCPTRNODECORE
+#define PKAVLNODECORE PAVLOGCPTRNODECORE
+#define PPKAVLNODECORE PPAVLOGCPTRNODECORE
+#define KAVLKEY RTGCPTR
+#define PKAVLKEY PRTGCPTR
+#define KAVLENUMDATA AVLOGCPTRENUMDATA
+#define PKAVLENUMDATA PAVLOGCPTRENUMDATA
+#define PKAVLCALLBACK PAVLOGCPTRCALLBACK
+#define KAVL_OFFSET 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) )
+
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlohcphys.cpp b/src/VBox/Runtime/common/table/avlohcphys.cpp
new file mode 100644
index 00000000..14ee1eac
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlohcphys.cpp
@@ -0,0 +1,79 @@
+/* $Id: avlohcphys.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTHCPHYS, unique keys, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvloHCPhys##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLOHCPHYSNODECORE
+#define PKAVLNODECORE PAVLOHCPHYSNODECORE
+#define PPKAVLNODECORE PPAVLOHCPHYSNODECORE
+#define KAVLKEY RTHCPHYS
+#define PKAVLKEY PRTHCPHYS
+#define KAVLENUMDATA AVLOHCPHYSENUMDATA
+#define PKAVLENUMDATA PAVLOHCPHYSENUMDATA
+#define PKAVLCALLBACK PAVLOHCPHYSCALLBACK
+#define KAVL_OFFSET 1
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avloioport.cpp b/src/VBox/Runtime/common/table/avloioport.cpp
new file mode 100644
index 00000000..64319f47
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avloioport.cpp
@@ -0,0 +1,79 @@
+/* $Id: avloioport.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTIOPORT, unique keys, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvloIOPort##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLOIOPORTNODECORE
+#define PKAVLNODECORE PAVLOIOPORTNODECORE
+#define PPKAVLNODECORE PPAVLOIOPORTNODECORE
+#define KAVLKEY RTIOPORT
+#define PKAVLKEY PRTIOPORT
+#define KAVLENUMDATA AVLOIOPORTENUMDATA
+#define PKAVLENUMDATA PAVLOIOPORTENUMDATA
+#define PKAVLCALLBACK PAVLOIOPORTCALLBACK
+#define KAVL_OFFSET 1
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlou32.cpp b/src/VBox/Runtime/common/table/avlou32.cpp
new file mode 100644
index 00000000..2906bdc5
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlou32.cpp
@@ -0,0 +1,80 @@
+/* $Id: avlou32.cpp $ */
+/** @file
+ * IPRT - AVL tree, uint_32, unique keys, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvloU32##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLOU32NODECORE
+#define PKAVLNODECORE PAVLOU32NODECORE
+#define PPKAVLNODECORE PPAVLOU32NODECORE
+#define KAVLKEY AVLOU32KEY
+#define PKAVLKEY AVLOU32KEY *
+#define KAVLENUMDATA AVLOU32ENUMDATA
+#define PKAVLENUMDATA PAVLOU32ENUMDATA
+#define PKAVLCALLBACK PAVLOU32CALLBACK
+#define KAVL_OFFSET 1
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlpv.cpp b/src/VBox/Runtime/common/table/avlpv.cpp
new file mode 100644
index 00000000..92adefe8
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlpv.cpp
@@ -0,0 +1,78 @@
+/* $Id: avlpv.cpp $ */
+/** @file
+ * IPRT - AVL tree, void *, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef NOFILEID
+/*static const char szFileId[] = "Id: kAVLPVInt.c,v 1.5 2003/02/13 02:02:35 bird Exp $";*/
+#endif
+
+
+/*********************************************************************************************************************************
+* Defined Constants And Macros *
+*********************************************************************************************************************************/
+/*
+ * AVL configuration.
+ */
+#define KAVL_FN(a) RTAvlPV##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
+
+
+/*
+ * 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) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlrfoff.cpp b/src/VBox/Runtime/common/table/avlrfoff.cpp
new file mode 100644
index 00000000..a9b5e1da
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlrfoff.cpp
@@ -0,0 +1,84 @@
+/* $Id: avlrfoff.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTFOFF, range, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlrFileOffset##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLRFOFFNODECORE
+#define PKAVLNODECORE PAVLRFOFFNODECORE
+#define PPKAVLNODECORE PPAVLRFOFFNODECORE
+#define KAVLKEY RTFOFF
+#define PKAVLKEY PRTFOFF
+#define KAVLENUMDATA AVLRFOFFENUMDATA
+#define PKAVLENUMDATA PAVLRFOFFENUMDATA
+#define PKAVLCALLBACK PAVLRFOFFCALLBACK
+#define KAVL_RANGE 1
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+#define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) ( (key1B) == (key2B) && (key1E) == (key2E) )
+#define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (key1B) <= (key2E) && (key1E) >= (key2B) )
+#define KAVL_R_IS_IN_RANGE(key1B, key1E, key2) KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2)
+
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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"
+
diff --git a/src/VBox/Runtime/common/table/avlrgcptr.cpp b/src/VBox/Runtime/common/table/avlrgcptr.cpp
new file mode 100644
index 00000000..2dbd75dd
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlrgcptr.cpp
@@ -0,0 +1,84 @@
+/* $Id: avlrgcptr.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTGCPTR, range, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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 <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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"
+
diff --git a/src/VBox/Runtime/common/table/avlrogcphys.cpp b/src/VBox/Runtime/common/table/avlrogcphys.cpp
new file mode 100644
index 00000000..0c8785cc
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlrogcphys.cpp
@@ -0,0 +1,85 @@
+/* $Id: avlrogcphys.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTGCPHYS, range, unique keys, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlroGCPhys##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLROGCPHYSNODECORE
+#define PKAVLNODECORE PAVLROGCPHYSNODECORE
+#define PPKAVLNODECORE PPAVLROGCPHYSNODECORE
+#define KAVLKEY RTGCPHYS
+#define PKAVLKEY PRTGCPHYS
+#define KAVLENUMDATA AVLROGCPHYSENUMDATA
+#define PKAVLENUMDATA PAVLROGCPHYSENUMDATA
+#define PKAVLCALLBACK PAVLROGCPHYSCALLBACK
+#define KAVL_OFFSET 1
+#define KAVL_RANGE 1
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+#define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) ( (key1B) == (key2B) && (key1E) == (key2E) )
+#define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (key1B) <= (key2E) && (key1E) >= (key2B) )
+#define KAVL_R_IS_IN_RANGE(key1B, key1E, key2) KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2)
+
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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"
+
diff --git a/src/VBox/Runtime/common/table/avlrogcptr.cpp b/src/VBox/Runtime/common/table/avlrogcptr.cpp
new file mode 100644
index 00000000..c0e7d5e8
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlrogcptr.cpp
@@ -0,0 +1,85 @@
+/* $Id: avlrogcptr.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTGCPTR, range, unique keys, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlroGCPtr##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 KAVLKEY RTGCPTR
+#define PKAVLKEY PRTGCPTR
+#define KAVLENUMDATA AVLROGCPTRENUMDATA
+#define PKAVLENUMDATA PAVLROGCPTRENUMDATA
+#define PKAVLCALLBACK PAVLROGCPTRCALLBACK
+#define KAVL_OFFSET 1
+#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 <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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"
+
diff --git a/src/VBox/Runtime/common/table/avlroioport.cpp b/src/VBox/Runtime/common/table/avlroioport.cpp
new file mode 100644
index 00000000..6927e382
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlroioport.cpp
@@ -0,0 +1,83 @@
+/* $Id: avlroioport.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTIOPORT, range, unique keys, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlroIOPort##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLROIOPORTNODECORE
+#define PKAVLNODECORE PAVLROIOPORTNODECORE
+#define PPKAVLNODECORE PPAVLROIOPORTNODECORE
+#define KAVLKEY RTIOPORT
+#define PKAVLKEY PRTIOPORT
+#define KAVLENUMDATA AVLROIOPORTENUMDATA
+#define PKAVLENUMDATA PAVLROIOPORTENUMDATA
+#define PKAVLCALLBACK PAVLROIOPORTCALLBACK
+#define KAVL_OFFSET 1
+#define KAVL_RANGE 1
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G( key1, key2) ( (key1) > (key2) )
+#define KAVL_E( key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+#define KAVL_R_IS_IDENTICAL( key1B, key2B, key1E, key2E) ( (key1B) == (key2B) && (key1E) == (key2E) )
+#define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (key1B) <= (key2E) && (key1E) >= (key2B) )
+#define KAVL_R_IS_IN_RANGE( key1B, key1E, key2) KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2)
+
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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"
+
diff --git a/src/VBox/Runtime/common/table/avlroogcptr.cpp b/src/VBox/Runtime/common/table/avlroogcptr.cpp
new file mode 100644
index 00000000..fe5edaf1
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlroogcptr.cpp
@@ -0,0 +1,92 @@
+/* $Id: avlroogcptr.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTGCPTR, range, unique keys, overlapping ranges, offset pointers.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlrooGCPtr##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_EQUAL_ALLOWED 1 /* Duplicate keys allowed */
+#define KAVLNODECORE AVLROOGCPTRNODECORE
+#define PKAVLNODECORE PAVLROOGCPTRNODECORE
+#define PPKAVLNODECORE PPAVLROOGCPTRNODECORE
+#define KAVLKEY RTGCPTR
+#define PKAVLKEY PRTGCPTR
+#define KAVLENUMDATA AVLROOGCPTRENUMDATA
+#define PKAVLENUMDATA PAVLROOGCPTRENUMDATA
+#define PKAVLCALLBACK PAVLROOGCPTRCALLBACK
+#define KAVL_OFFSET 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) )
+
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_Enum.cpp.h"
+
+/*
+ * Defined only for the range functions as we allow for overlapping ranges.
+ */
+#undef KAVL_R_IS_IDENTICAL
+#undef KAVL_R_IS_INTERSECTING
+#undef KAVL_R_IS_IN_RANGE
+#define KAVL_RANGE 1
+#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)
+#include "avl_Range.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlrpv.cpp b/src/VBox/Runtime/common/table/avlrpv.cpp
new file mode 100644
index 00000000..be303f5f
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlrpv.cpp
@@ -0,0 +1,83 @@
+/* $Id: avlrpv.cpp $ */
+/** @file
+ * IPRT - AVL tree, void *, range, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef NOFILEID
+static const char szFileId[] = "Id: kAVLPVInt.c,v 1.5 2003/02/13 02:02:35 bird Exp $";
+#endif
+
+
+/*********************************************************************************************************************************
+* Defined Constants And Macros *
+*********************************************************************************************************************************/
+/*
+ * AVL configuration.
+ */
+#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 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
+
+
+/*
+ * AVL Compare macros
+ */
+#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)
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_GetBestFit.cpp.h"
+#include "avl_Range.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlru64.cpp b/src/VBox/Runtime/common/table/avlru64.cpp
new file mode 100644
index 00000000..c4d6464e
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlru64.cpp
@@ -0,0 +1,83 @@
+/* $Id: avlru64.cpp $ */
+/** @file
+ * IPRT - AVL tree, void *, range, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef NOFILEID
+static const char szFileId[] = "Id: kAVLULInt.c,v 1.5 2003/02/13 02:02:35 bird Exp $";
+#endif
+
+
+/*********************************************************************************************************************************
+* Defined Constants And Macros *
+*********************************************************************************************************************************/
+/*
+ * AVL configuration.
+ */
+#define KAVL_FN(a) RTAvlrU64##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLRU64NODECORE
+#define PKAVLNODECORE PAVLRU64NODECORE
+#define PPKAVLNODECORE PPAVLRU64NODECORE
+#define KAVLKEY AVLRU64KEY
+#define PKAVLKEY PAVLRU64KEY
+#define KAVLENUMDATA AVLRU64ENUMDATA
+#define PKAVLENUMDATA PAVLRU64ENUMDATA
+#define PKAVLCALLBACK PAVLRU64CALLBACK
+#define KAVL_RANGE 1
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G(key1, key2) ( (key1) > (key2) )
+#define KAVL_E(key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+#define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) ( (key1B) == (key2B) && (key1E) == (key2E) )
+#define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (key1B) <= (key2E) && (key1E) >= (key2B) )
+#define KAVL_R_IS_IN_RANGE(key1B, key1E, key2) KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2)
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_GetBestFit.cpp.h"
+#include "avl_Range.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlruintptr.cpp b/src/VBox/Runtime/common/table/avlruintptr.cpp
new file mode 100644
index 00000000..476e9f61
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlruintptr.cpp
@@ -0,0 +1,84 @@
+/* $Id: avlruintptr.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTUINTPTR, range, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlrUIntPtr##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLRUINTPTRNODECORE
+#define PKAVLNODECORE PAVLRUINTPTRNODECORE
+#define PPKAVLNODECORE PPAVLRUINTPTRNODECORE
+#define KAVLKEY RTUINTPTR
+#define PKAVLKEY PRTUINTPTR
+#define KAVLENUMDATA AVLRUINTPTRENUMDATA
+#define PKAVLENUMDATA PAVLRUINTPTRENUMDATA
+#define PKAVLCALLBACK PAVLRUINTPTRCALLBACK
+#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 <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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"
+
diff --git a/src/VBox/Runtime/common/table/avlu32.cpp b/src/VBox/Runtime/common/table/avlu32.cpp
new file mode 100644
index 00000000..ad7dabeb
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlu32.cpp
@@ -0,0 +1,78 @@
+/* $Id: avlu32.cpp $ */
+/** @file
+ * IPRT - AVL tree, uint32_t, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlU32##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLU32NODECORE
+#define PKAVLNODECORE PAVLU32NODECORE
+#define PPKAVLNODECORE PPAVLU32NODECORE
+#define KAVLKEY AVLU32KEY
+#define PKAVLKEY PAVLU32KEY
+#define KAVLENUMDATA AVLU32ENUMDATA
+#define PKAVLENUMDATA PAVLU32ENUMDATA
+#define PKAVLCALLBACK PAVLU32CALLBACK
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G(key1, key2) ( (key1) > (key2) )
+#define KAVL_E(key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlu64.cpp b/src/VBox/Runtime/common/table/avlu64.cpp
new file mode 100644
index 00000000..3f78f9ca
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlu64.cpp
@@ -0,0 +1,78 @@
+/* $Id: avlu64.cpp $ */
+/** @file
+ * IPRT - AVL tree, uint32_t, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlU64##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLU64NODECORE
+#define PKAVLNODECORE PAVLU64NODECORE
+#define PPKAVLNODECORE PPAVLU64NODECORE
+#define KAVLKEY AVLU64KEY
+#define PKAVLKEY PAVLU64KEY
+#define KAVLENUMDATA AVLU64ENUMDATA
+#define PKAVLENUMDATA PAVLU64ENUMDATA
+#define PKAVLCALLBACK PAVLU64CALLBACK
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G(key1, key2) ( (key1) > (key2) )
+#define KAVL_E(key1, key2) ( (key1) == (key2) )
+#define KAVL_NE(key1, key2) ( (key1) != (key2) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avluintptr.cpp b/src/VBox/Runtime/common/table/avluintptr.cpp
new file mode 100644
index 00000000..9e8a58b5
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avluintptr.cpp
@@ -0,0 +1,78 @@
+/* $Id: avluintptr.cpp $ */
+/** @file
+ * IPRT - AVL tree, RTUINTPTR, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlUIntPtr##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLUINTPTRNODECORE
+#define PKAVLNODECORE PAVLUINTPTRNODECORE
+#define PPKAVLNODECORE PPAVLUINTPTRNODECORE
+#define KAVLKEY RTUINTPTR
+#define PKAVLKEY PRTUINTPTR
+#define KAVLENUMDATA AVLUINTPTRENUMDATA
+#define PKAVLENUMDATA PAVLUINTPTRENUMDATA
+#define PKAVLCALLBACK PAVLUINTPTRCALLBACK
+
+
+/*
+ * 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) )
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+#include "avl_GetBestFit.cpp.h"
+#include "avl_Enum.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/avlul.cpp b/src/VBox/Runtime/common/table/avlul.cpp
new file mode 100644
index 00000000..df0ad145
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avlul.cpp
@@ -0,0 +1,78 @@
+/* $Id: avlul.cpp $ */
+/** @file
+ * IPRT - AVL tree, unsigned long, unique keys.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#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) RTAvlUL##a
+#define KAVL_MAX_STACK 27 /* Up to 2^24 nodes. */
+#define KAVL_CHECK_FOR_EQUAL_INSERT 1 /* No duplicate keys! */
+#define KAVLNODECORE AVLULNODECORE
+#define PKAVLNODECORE PAVLULNODECORE
+#define PPKAVLNODECORE PPAVLULNODECORE
+#define KAVLKEY AVLULKEY
+#define PKAVLKEY PAVLULKEY
+#define KAVLENUMDATA AVLULENUMDATA
+#define PKAVLENUMDATA PAVLULENUMDATA
+#define PKAVLCALLBACK PAVLULCALLBACK
+
+
+/*
+ * AVL Compare macros
+ */
+#define KAVL_G(key1, key2) (key1 > key2)
+#define KAVL_E(key1, key2) (key1 == key2)
+#define KAVL_NE(key1, key2) (key1 != key2)
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/avl.h>
+#include <iprt/assert.h>
+#include <iprt/errcore.h>
+
+/*
+ * 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_GetBestFit.cpp.h"
+#include "avl_RemoveBestFit.cpp.h"
+#include "avl_DoWithAll.cpp.h"
+#include "avl_Destroy.cpp.h"
+
diff --git a/src/VBox/Runtime/common/table/table.cpp b/src/VBox/Runtime/common/table/table.cpp
new file mode 100644
index 00000000..825e6fc6
--- /dev/null
+++ b/src/VBox/Runtime/common/table/table.cpp
@@ -0,0 +1,32 @@
+/* $Id: table.cpp $ */
+/** @file
+ * IPRT - Generic Tables/Containers, just a thought so far.
+ */
+
+/*
+ * Copyright (C) 2006-2020 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/table.h>
+