Adding upstream version 7.0.14-dfsg.upstream/7.0.14-dfsg

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 474 insertions, 0 deletions

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..6c38dff3
--- /dev/null
+++ b/src/VBox/Runtime/common/table/avl_Base.cpp.h
@@ -0,0 +1,474 @@
+/* $Id: avl_Base.cpp.h $ */
+/** @file
+ * kAVLBase - basic routines for all AVL trees.
+ */
+
+/*
+ * Copyright (C) 2006-2023 Oracle and/or its affiliates.
+ *
+ * This file is part of VirtualBox base platform packages, as
+ * available from https://www.virtualbox.org.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation, in version 3 of the
+ * License.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <https://www.gnu.org/licenses>.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
+ * in the VirtualBox 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.
+ *
+ * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
+ */
+
+#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;
+        Assert(pCurNode->uchHeight == RT_MAX(AVL_HEIGHTOF(KAVL_GET_POINTER_NULL(&pCurNode->pLeft)),
+                                             AVL_HEIGHTOF(KAVL_GET_POINTER_NULL(&pCurNode->pRight))) + 1);
+
+        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;
+        Assert(pDeleteNode->uchHeight == RT_MAX(AVL_HEIGHTOF(KAVL_GET_POINTER_NULL(&pDeleteNode->pLeft)),
+                                                AVL_HEIGHTOF(KAVL_GET_POINTER_NULL(&pDeleteNode->pRight))) + 1);
+
+        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