diff options
Diffstat (limited to 'src/VBox/Runtime/common/table')
34 files changed, 3507 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..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 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..83334129 --- /dev/null +++ b/src/VBox/Runtime/common/table/avl_Destroy.cpp.h @@ -0,0 +1,120 @@ +/* $Id: avl_Destroy.cpp.h $ */ +/** @file + * kAVLDestroy - Walk the tree calling a callback to destroy all the nodes. + */ + +/* + * 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 _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..88be3623 --- /dev/null +++ b/src/VBox/Runtime/common/table/avl_DoWithAll.cpp.h @@ -0,0 +1,156 @@ +/* $Id: avl_DoWithAll.cpp.h $ */ +/** @file + * kAVLDoWithAll - Do with all nodes routine for 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 _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 */ + Assert(pNode->uchHeight == RT_MAX(AVL_HEIGHTOF(KAVL_GET_POINTER_NULL(&pNode->pLeft)), + AVL_HEIGHTOF(KAVL_GET_POINTER_NULL(&pNode->pRight))) + 1); + 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 */ + Assert(pNode->uchHeight == RT_MAX(AVL_HEIGHTOF(KAVL_GET_POINTER_NULL(&pNode->pLeft)), + AVL_HEIGHTOF(KAVL_GET_POINTER_NULL(&pNode->pRight))) + 1); + 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..3869c31a --- /dev/null +++ b/src/VBox/Runtime/common/table/avl_Enum.cpp.h @@ -0,0 +1,105 @@ +/* $Id: avl_Enum.cpp.h $ */ +/** @file + * Enumeration routines for 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 _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..d3f938ad --- /dev/null +++ b/src/VBox/Runtime/common/table/avl_Get.cpp.h @@ -0,0 +1,77 @@ +/* $Id: avl_Get.cpp.h $ */ +/** @file + * kAVLGet - get routine for 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 _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..d8438456 --- /dev/null +++ b/src/VBox/Runtime/common/table/avl_GetBestFit.cpp.h @@ -0,0 +1,113 @@ +/* $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-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 _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..04a28e34 --- /dev/null +++ b/src/VBox/Runtime/common/table/avl_Range.cpp.h @@ -0,0 +1,94 @@ +/* $Id: avl_Range.cpp.h $ */ +/** @file + * kAVLRange - Range routines for 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 _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..761ac7d2 --- /dev/null +++ b/src/VBox/Runtime/common/table/avl_RemoveBestFit.cpp.h @@ -0,0 +1,80 @@ +/* $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-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 _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..16e851cf --- /dev/null +++ b/src/VBox/Runtime/common/table/avl_RemoveNode.cpp.h @@ -0,0 +1,153 @@ +/* $Id: avl_RemoveNode.cpp.h $ */ +/** @file + * kAVLRemove2 - Remove specific node (by pointer) from an AVL tree. + */ + +/* + * 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 + */ + + +/** + * 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..5863a555 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlgcphys.cpp @@ -0,0 +1,88 @@ +/* $Id: avlgcphys.cpp $ */ +/** @file + * IPRT - AVL tree, RTGCPHYS, unique keys. + */ + +/* + * 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 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..0e263422 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlgcptr.cpp @@ -0,0 +1,88 @@ +/* $Id: avlgcptr.cpp $ */ +/** @file + * IPRT - AVL tree, RTGCPTR, unique keys. + */ + +/* + * 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 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..22395d25 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlhcphys.cpp @@ -0,0 +1,88 @@ +/* $Id: avlhcphys.cpp $ */ +/** @file + * IPRT - AVL tree, RTHCPHYS, unique keys. + */ + +/* + * 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 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..8d81b78f --- /dev/null +++ b/src/VBox/Runtime/common/table/avllu32.cpp @@ -0,0 +1,89 @@ +/* $Id: avllu32.cpp $ */ +/** @file + * IPRT - AVL tree, uint32_t, unique keys. + */ + +/* + * 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 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..12e5ced3 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlogcphys.cpp @@ -0,0 +1,89 @@ +/* $Id: avlogcphys.cpp $ */ +/** @file + * IPRT - AVL tree, RTGCPHYS, unique keys, offset pointers. + */ + +/* + * 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 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..3a6c64cd --- /dev/null +++ b/src/VBox/Runtime/common/table/avlogcptr.cpp @@ -0,0 +1,90 @@ +/* $Id: avlogcptr.cpp $ */ +/** @file + * IPRT - AVL tree, RTGCPTR, unique keys, offset pointers. + */ + +/* + * 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 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..9f43620b --- /dev/null +++ b/src/VBox/Runtime/common/table/avlohcphys.cpp @@ -0,0 +1,89 @@ +/* $Id: avlohcphys.cpp $ */ +/** @file + * IPRT - AVL tree, RTHCPHYS, unique keys, offset pointers. + */ + +/* + * 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 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..ebabd9d5 --- /dev/null +++ b/src/VBox/Runtime/common/table/avloioport.cpp @@ -0,0 +1,89 @@ +/* $Id: avloioport.cpp $ */ +/** @file + * IPRT - AVL tree, RTIOPORT, unique keys, offset pointers. + */ + +/* + * 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 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..2d565d71 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlou32.cpp @@ -0,0 +1,90 @@ +/* $Id: avlou32.cpp $ */ +/** @file + * IPRT - AVL tree, uint_32, unique keys, offset pointers. + */ + +/* + * 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 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..dcce99fc --- /dev/null +++ b/src/VBox/Runtime/common/table/avlpv.cpp @@ -0,0 +1,88 @@ +/* $Id: avlpv.cpp $ */ +/** @file + * IPRT - AVL tree, void *, unique keys. + */ + +/* + * 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 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..f39f9c93 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlrfoff.cpp @@ -0,0 +1,94 @@ +/* $Id: avlrfoff.cpp $ */ +/** @file + * IPRT - AVL tree, RTFOFF, range, unique keys. + */ + +/* + * 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 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..5fad033b --- /dev/null +++ b/src/VBox/Runtime/common/table/avlrgcptr.cpp @@ -0,0 +1,94 @@ +/* $Id: avlrgcptr.cpp $ */ +/** @file + * IPRT - AVL tree, RTGCPTR, range, unique keys. + */ + +/* + * 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 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..e2b9c645 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlrogcphys.cpp @@ -0,0 +1,95 @@ +/* $Id: avlrogcphys.cpp $ */ +/** @file + * IPRT - AVL tree, RTGCPHYS, range, unique keys, offset pointers. + */ + +/* + * 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 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..0908743f --- /dev/null +++ b/src/VBox/Runtime/common/table/avlrogcptr.cpp @@ -0,0 +1,95 @@ +/* $Id: avlrogcptr.cpp $ */ +/** @file + * IPRT - AVL tree, RTGCPTR, range, unique keys, offset pointers. + */ + +/* + * 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 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..07a300d3 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlroioport.cpp @@ -0,0 +1,93 @@ +/* $Id: avlroioport.cpp $ */ +/** @file + * IPRT - AVL tree, RTIOPORT, range, unique keys, offset pointers. + */ + +/* + * 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 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..2e2d1ad2 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlroogcptr.cpp @@ -0,0 +1,102 @@ +/* $Id: avlroogcptr.cpp $ */ +/** @file + * IPRT - AVL tree, RTGCPTR, range, unique keys, overlapping ranges, offset pointers. + */ + +/* + * 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 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..cd6d5d27 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlrpv.cpp @@ -0,0 +1,93 @@ +/* $Id: avlrpv.cpp $ */ +/** @file + * IPRT - AVL tree, void *, range, unique keys. + */ + +/* + * 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 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..18d3b143 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlru64.cpp @@ -0,0 +1,93 @@ +/* $Id: avlru64.cpp $ */ +/** @file + * IPRT - AVL tree, void *, range, unique keys. + */ + +/* + * 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 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..5c99a979 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlruintptr.cpp @@ -0,0 +1,94 @@ +/* $Id: avlruintptr.cpp $ */ +/** @file + * IPRT - AVL tree, RTUINTPTR, range, unique keys. + */ + +/* + * 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 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..35e30b67 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlu32.cpp @@ -0,0 +1,88 @@ +/* $Id: avlu32.cpp $ */ +/** @file + * IPRT - AVL tree, uint32_t, unique keys. + */ + +/* + * 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 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..6f277021 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlu64.cpp @@ -0,0 +1,88 @@ +/* $Id: avlu64.cpp $ */ +/** @file + * IPRT - AVL tree, uint32_t, unique keys. + */ + +/* + * 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 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..f2b9fbd0 --- /dev/null +++ b/src/VBox/Runtime/common/table/avluintptr.cpp @@ -0,0 +1,88 @@ +/* $Id: avluintptr.cpp $ */ +/** @file + * IPRT - AVL tree, RTUINTPTR, unique keys. + */ + +/* + * 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 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..0626d4b3 --- /dev/null +++ b/src/VBox/Runtime/common/table/avlul.cpp @@ -0,0 +1,88 @@ +/* $Id: avlul.cpp $ */ +/** @file + * IPRT - AVL tree, unsigned long, unique keys. + */ + +/* + * 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 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..23ab77e1 --- /dev/null +++ b/src/VBox/Runtime/common/table/table.cpp @@ -0,0 +1,42 @@ +/* $Id: table.cpp $ */ +/** @file + * IPRT - Generic Tables/Containers, just a thought so far. + */ + +/* + * 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 + */ + + +/********************************************************************************************************************************* +* Header Files * +*********************************************************************************************************************************/ +#include <iprt/table.h> + |