diff options
Diffstat (limited to 'include/iprt/cpp/hardavlrange.h')
| -rw-r--r-- | include/iprt/cpp/hardavlrange.h | 1284 |
1 files changed, 1284 insertions, 0 deletions
diff --git a/include/iprt/cpp/hardavlrange.h b/include/iprt/cpp/hardavlrange.h new file mode 100644 index 00000000..7020968e --- /dev/null +++ b/include/iprt/cpp/hardavlrange.h @@ -0,0 +1,1284 @@ +/** @file + * IPRT - Hardened AVL tree, unique key ranges. + */ + +/* + * Copyright (C) 2022 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 IPRT_INCLUDED_cpp_hardavlrange_h +#define IPRT_INCLUDED_cpp_hardavlrange_h +#ifndef RT_WITHOUT_PRAGMA_ONCE +# pragma once +#endif + +#include <iprt/cpp/hardavlslaballocator.h> + +/** @defgroup grp_rt_cpp_hardavl Hardened AVL Trees + * @{ + */ + +/** + * Check that the tree heights make sense for the current node. + * + * This is a RT_STRICT test as it's expensive and we should have sufficient + * other checks to ensure safe AVL tree operation. + * + * @note the a_cStackEntries parameter is a hack to avoid running into gcc's + * "the address of 'AVLStack' will never be NULL" errors. + */ +#ifdef RT_STRICT +# define RTHARDAVL_STRICT_CHECK_HEIGHTS(a_pNode, a_pAvlStack, a_cStackEntries) do { \ + NodeType * const pLeftNodeX = a_pAllocator->ptrFromInt(readIdx(&(a_pNode)->idxLeft)); \ + AssertReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNodeX), m_cErrors++, a_pAllocator->ptrErrToStatus((a_pNode))); \ + NodeType * const pRightNodeX = a_pAllocator->ptrFromInt(readIdx(&(a_pNode)->idxRight)); \ + AssertReturnStmt(a_pAllocator->isPtrRetOkay(pRightNodeX), m_cErrors++, a_pAllocator->ptrErrToStatus((a_pNode))); \ + uint8_t const cLeftHeightX = pLeftNodeX ? pLeftNodeX->cHeight : 0; \ + uint8_t const cRightHeightX = pRightNodeX ? pRightNodeX->cHeight : 0; \ + if (RT_LIKELY((a_pNode)->cHeight == RT_MAX(cLeftHeightX, cRightHeightX) + 1)) { /*likely*/ } \ + else \ + { \ + RTAssertMsg2("line %u: %u l=%u r=%u\n", __LINE__, (a_pNode)->cHeight, cLeftHeightX, cRightHeightX); \ + if ((a_cStackEntries)) dumpStack(a_pAllocator, (a_pAvlStack)); \ + AssertMsgReturnStmt((a_pNode)->cHeight == RT_MAX(cLeftHeightX, cRightHeightX) + 1, \ + ("%u l=%u r=%u\n", (a_pNode)->cHeight, cLeftHeightX, cRightHeightX), \ + m_cErrors++, VERR_HARDAVL_BAD_HEIGHT); \ + } \ + AssertMsgReturnStmt(RT_ABS(cLeftHeightX - cRightHeightX) <= 1, ("l=%u r=%u\n", cLeftHeightX, cRightHeightX), \ + m_cErrors++, VERR_HARDAVL_UNBALANCED); \ + Assert(!pLeftNodeX || pLeftNodeX->Key < (a_pNode)->Key); \ + Assert(!pRightNodeX || pRightNodeX->Key > (a_pNode)->Key); \ + } while (0) +#else +# define RTHARDAVL_STRICT_CHECK_HEIGHTS(a_pNode, a_pAvlStack, a_cStackEntries) do { } while (0) +#endif + + +/** + * Hardened AVL tree for nodes with key ranges. + * + * This is very crude and therefore expects the NodeType to feature: + * - Key and KeyLast members of KeyType. + * - idxLeft and idxRight members with type uint32_t. + * - cHeight members of type uint8_t. + * + * The code is very C-ish because of it's sources and initial use (ring-0 + * without C++ exceptions enabled). + */ +template<typename NodeType, typename KeyType> +struct RTCHardAvlRangeTree +{ + /** The root index. */ + uint32_t m_idxRoot; + /** The error count. */ + uint32_t m_cErrors; + /** @name Statistics + * @{ */ + uint64_t m_cInserts; + uint64_t m_cRemovals; + uint64_t m_cRebalancingOperations; + /** @} */ + + /** The max stack depth. */ + enum { kMaxStack = 28 }; + /** The max height value we allow. */ + enum { kMaxHeight = kMaxStack + 1 }; + + /** A stack used internally to avoid recursive calls. + * This is used with operations invoking i_rebalance(). */ + typedef struct HardAvlStack + { + /** Number of entries on the stack. */ + unsigned cEntries; + /** The stack. */ + uint32_t *apidxEntries[kMaxStack]; + } HardAvlStack; + + /** @name Key comparisons + * @{ */ + static inline int areKeyRangesIntersecting(KeyType a_Key1First, KeyType a_Key2First, + KeyType a_Key1Last, KeyType a_Key2Last) RT_NOEXCEPT + { + return a_Key1First <= a_Key2Last && a_Key1Last >= a_Key2First; + } + + static inline int isKeyInRange(KeyType a_Key, KeyType a_KeyFirst, KeyType a_KeyLast) RT_NOEXCEPT + { + return a_Key <= a_KeyLast && a_Key >= a_KeyFirst; + } + + static inline int isKeyGreater(KeyType a_Key1, KeyType a_Key2) RT_NOEXCEPT + { + return a_Key1 > a_Key2; + } + /** @} */ + + /** + * Read an index value trying to prevent the compiler from re-reading it. + */ + DECL_FORCE_INLINE(uint32_t) readIdx(uint32_t volatile *pidx) RT_NOEXCEPT + { + uint32_t idx = *pidx; + ASMCompilerBarrier(); + return idx; + } + + RTCHardAvlRangeTree() RT_NOEXCEPT + : m_idxRoot(0) + , m_cErrors(0) + { } + + RTCHardAvlRangeTree(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator) RT_NOEXCEPT + { + initWithAllocator(a_pAllocator); + } + + void initWithAllocator(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator) RT_NOEXCEPT + { + m_idxRoot = a_pAllocator->kNilIndex; + m_cErrors = 0; + } + + /** + * Inserts a node into the AVL-tree. + * + * @returns IPRT status code. + * @retval VERR_ALREADY_EXISTS if a node with overlapping key range exists. + * + * @param a_pAllocator Pointer to the allocator. + * @param a_pNode Pointer to the node which is to be added. + * + * @code + * 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. + * @endcode + */ + int insert(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, NodeType *a_pNode) RT_NOEXCEPT + { + KeyType const Key = a_pNode->Key; + KeyType const KeyLast = a_pNode->KeyLast; + AssertMsgReturn(Key <= KeyLast, ("Key=%#RX64 KeyLast=%#RX64\n", (uint64_t)Key, (uint64_t)KeyLast), + VERR_HARDAVL_INSERT_INVALID_KEY_RANGE); + + uint32_t *pidxCurNode = &m_idxRoot; + HardAvlStack AVLStack; + AVLStack.cEntries = 0; + for (;;) + { + NodeType *pCurNode = a_pAllocator->ptrFromInt(readIdx(pidxCurNode)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pCurNode), ("*pidxCurNode=%#x pCurNode=%p\n", *pidxCurNode, pCurNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pCurNode)); + if (!pCurNode) + break; + + unsigned const cEntries = AVLStack.cEntries; + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries), + ("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n", pidxCurNode, *pidxCurNode, pCurNode, + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + AVLStack.apidxEntries[cEntries] = pidxCurNode; + AVLStack.cEntries = cEntries + 1; + + RTHARDAVL_STRICT_CHECK_HEIGHTS(pCurNode, &AVLStack, AVLStack.cEntries); + + /* Range check: */ + if (areKeyRangesIntersecting(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast)) + return VERR_ALREADY_EXISTS; + + /* Descend: */ + if (isKeyGreater(pCurNode->Key, Key)) + pidxCurNode = &pCurNode->idxLeft; + else + pidxCurNode = &pCurNode->idxRight; + } + + a_pNode->idxLeft = a_pAllocator->kNilIndex; + a_pNode->idxRight = a_pAllocator->kNilIndex; + a_pNode->cHeight = 1; + + uint32_t const idxNode = a_pAllocator->ptrToInt(a_pNode); + AssertMsgReturn(a_pAllocator->isIdxRetOkay(idxNode), ("pNode=%p idxNode=%#x\n", a_pNode, idxNode), + a_pAllocator->idxErrToStatus(idxNode)); + *pidxCurNode = idxNode; + + m_cInserts++; + return i_rebalance(a_pAllocator, &AVLStack); + } + + /** + * Removes a node from the AVL-tree by a key value. + * + * @returns IPRT status code. + * @retval VERR_NOT_FOUND if not found. + * @param a_pAllocator Pointer to the allocator. + * @param a_Key A key value in the range of the node to be removed. + * @param a_ppRemoved Where to return the pointer to the removed node. + * + * @code + * 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). + * @endcode + */ + int remove(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, KeyType a_Key, NodeType **a_ppRemoved) RT_NOEXCEPT + { + *a_ppRemoved = NULL; + + /* + * Walk the tree till we locate the node that is to be deleted. + */ + uint32_t *pidxDeleteNode = &m_idxRoot; + NodeType *pDeleteNode; + HardAvlStack AVLStack; + AVLStack.cEntries = 0; + for (;;) + { + pDeleteNode = a_pAllocator->ptrFromInt(readIdx(pidxDeleteNode)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pDeleteNode), + ("*pidxCurNode=%#x pDeleteNode=%p\n", *pidxDeleteNode, pDeleteNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pDeleteNode)); + if (pDeleteNode) + { /*likely*/ } + else + return VERR_NOT_FOUND; + + unsigned const cEntries = AVLStack.cEntries; + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries), + ("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n", + pidxDeleteNode, *pidxDeleteNode, pDeleteNode, + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + AVLStack.apidxEntries[cEntries] = pidxDeleteNode; + AVLStack.cEntries = cEntries + 1; + + RTHARDAVL_STRICT_CHECK_HEIGHTS(pDeleteNode, &AVLStack, AVLStack.cEntries); + + /* Range check: */ + if (isKeyInRange(a_Key, pDeleteNode->Key, pDeleteNode->KeyLast)) + break; + + /* Descend: */ + if (isKeyGreater(pDeleteNode->Key, a_Key)) + pidxDeleteNode = &pDeleteNode->idxLeft; + else + pidxDeleteNode = &pDeleteNode->idxRight; + } + + /* + * Do the deletion. + */ + uint32_t const idxDeleteLeftNode = readIdx(&pDeleteNode->idxLeft); + if (idxDeleteLeftNode != a_pAllocator->kNilIndex) + { + /* + * Replace the deleted node with the rightmost node in the left subtree. + */ + NodeType * const pDeleteLeftNode = a_pAllocator->ptrFromInt(idxDeleteLeftNode); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pDeleteLeftNode), + ("idxDeleteLeftNode=%#x pDeleteLeftNode=%p\n", idxDeleteLeftNode, pDeleteLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pDeleteLeftNode)); + + uint32_t const idxDeleteRightNode = readIdx(&pDeleteNode->idxRight); + AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS); + + const unsigned iStackEntry = AVLStack.cEntries; + + uint32_t *pidxLeftBiggest = &pDeleteNode->idxLeft; + uint32_t idxLeftBiggestNode = idxDeleteLeftNode; + NodeType *pLeftBiggestNode = pDeleteLeftNode; + RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftBiggestNode, &AVLStack, AVLStack.cEntries); + + uint32_t idxRightTmp; + while ((idxRightTmp = readIdx(&pLeftBiggestNode->idxRight)) != a_pAllocator->kNilIndex) + { + unsigned const cEntries = AVLStack.cEntries; + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries), + ("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n", + pidxLeftBiggest, *pidxLeftBiggest, pLeftBiggestNode, + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], + AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + AVLStack.apidxEntries[cEntries] = pidxLeftBiggest; + AVLStack.cEntries = cEntries + 1; + + pidxLeftBiggest = &pLeftBiggestNode->idxRight; + idxLeftBiggestNode = idxRightTmp; + pLeftBiggestNode = a_pAllocator->ptrFromInt(idxRightTmp); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftBiggestNode), + ("idxLeftBiggestNode=%#x pLeftBiggestNode=%p\n", idxLeftBiggestNode, pLeftBiggestNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftBiggestNode)); + RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftBiggestNode, &AVLStack, AVLStack.cEntries); + } + + uint32_t const idxLeftBiggestLeftNode = readIdx(&pLeftBiggestNode->idxLeft); + AssertReturnStmt(a_pAllocator->isIntValid(idxLeftBiggestLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS); + + /* link out pLeftBiggestNode */ + *pidxLeftBiggest = idxLeftBiggestLeftNode; + + /* link it in place of the deleted node. */ + if (idxDeleteLeftNode != idxLeftBiggestNode) + pLeftBiggestNode->idxLeft = idxDeleteLeftNode; + pLeftBiggestNode->idxRight = idxDeleteRightNode; + pLeftBiggestNode->cHeight = AVLStack.cEntries > iStackEntry ? pDeleteNode->cHeight : 0; + + *pidxDeleteNode = idxLeftBiggestNode; + + if (AVLStack.cEntries > iStackEntry) + AVLStack.apidxEntries[iStackEntry] = &pLeftBiggestNode->idxLeft; + } + else + { + /* No left node, just pull up the right one. */ + uint32_t const idxDeleteRightNode = readIdx(&pDeleteNode->idxRight); + AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS); + *pidxDeleteNode = idxDeleteRightNode; + AVLStack.cEntries--; + } + *a_ppRemoved = pDeleteNode; + + m_cRemovals++; + return i_rebalance(a_pAllocator, &AVLStack); + } + + /** + * Looks up a node from the tree. + * + * @returns IPRT status code. + * @retval VERR_NOT_FOUND if not found. + * + * @param a_pAllocator Pointer to the allocator. + * @param a_Key A key value in the range of the desired node. + * @param a_ppFound Where to return the pointer to the node. + */ + int lookup(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, KeyType a_Key, NodeType **a_ppFound) RT_NOEXCEPT + { + *a_ppFound = NULL; + + NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); +#ifdef RT_STRICT + HardAvlStack AVLStack; + AVLStack.apidxEntries[0] = &m_idxRoot; + AVLStack.cEntries = 1; +#endif + unsigned cDepth = 0; + while (pNode) + { + RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, &AVLStack, AVLStack.cEntries); + AssertReturn(cDepth <= kMaxHeight, VERR_HARDAVL_LOOKUP_TOO_DEEP); + cDepth++; + + if (isKeyInRange(a_Key, pNode->Key, pNode->KeyLast)) + { + *a_ppFound = pNode; + return VINF_SUCCESS; + } + if (isKeyGreater(pNode->Key, a_Key)) + { +#ifdef RT_STRICT + AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxLeft; +#endif + uint32_t const idxLeft = readIdx(&pNode->idxLeft); + pNode = a_pAllocator->ptrFromInt(idxLeft); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("idxLeft=%#x pNode=%p\n", idxLeft, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); + } + else + { +#ifdef RT_STRICT + AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxRight; +#endif + uint32_t const idxRight = readIdx(&pNode->idxRight); + pNode = a_pAllocator->ptrFromInt(idxRight); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("idxRight=%#x pNode=%p\n", idxRight, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); + } + } + + return VERR_NOT_FOUND; + } + + /** + * Looks up node matching @a a_Key or if no exact match the closest smaller than it. + * + * @returns IPRT status code. + * @retval VERR_NOT_FOUND if not found. + * + * @param a_pAllocator Pointer to the allocator. + * @param a_Key A key value in the range of the desired node. + * @param a_ppFound Where to return the pointer to the node. + */ + int lookupMatchingOrBelow(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, KeyType a_Key, + NodeType **a_ppFound) RT_NOEXCEPT + { + *a_ppFound = NULL; + + NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); +#ifdef RT_STRICT + HardAvlStack AVLStack; + AVLStack.apidxEntries[0] = &m_idxRoot; + AVLStack.cEntries = 1; +#endif + unsigned cDepth = 0; + NodeType *pNodeLast = NULL; + while (pNode) + { + RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, &AVLStack, AVLStack.cEntries); + AssertReturn(cDepth <= kMaxHeight, VERR_HARDAVL_LOOKUP_TOO_DEEP); + cDepth++; + + if (isKeyInRange(a_Key, pNode->Key, pNode->KeyLast)) + { + *a_ppFound = pNode; + return VINF_SUCCESS; + } + if (isKeyGreater(pNode->Key, a_Key)) + { +#ifdef RT_STRICT + AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxLeft; +#endif + uint32_t const idxLeft = readIdx(&pNode->idxLeft); + NodeType *pLeftNode = a_pAllocator->ptrFromInt(idxLeft); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode), ("idxLeft=%#x pLeftNode=%p\n", idxLeft, pLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode)); + if (pLeftNode) + pNode = pLeftNode; + else if (!pNodeLast) + break; + else + { + *a_ppFound = pNodeLast; + return VINF_SUCCESS; + } + } + else + { +#ifdef RT_STRICT + AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxRight; +#endif + uint32_t const idxRight = readIdx(&pNode->idxRight); + NodeType *pRightNode = a_pAllocator->ptrFromInt(idxRight); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode), ("idxRight=%#x pRightNode=%p\n", idxRight, pRightNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode)); + if (pRightNode) + { + pNodeLast = pNode; + pNode = pRightNode; + } + else + { + *a_ppFound = pNode; + return VINF_SUCCESS; + } + } + } + + return VERR_NOT_FOUND; + } + + /** + * Looks up node matching @a a_Key or if no exact match the closest larger than it. + * + * @returns IPRT status code. + * @retval VERR_NOT_FOUND if not found. + * + * @param a_pAllocator Pointer to the allocator. + * @param a_Key A key value in the range of the desired node. + * @param a_ppFound Where to return the pointer to the node. + */ + int lookupMatchingOrAbove(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, KeyType a_Key, + NodeType **a_ppFound) RT_NOEXCEPT + { + *a_ppFound = NULL; + + NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); +#ifdef RT_STRICT + HardAvlStack AVLStack; + AVLStack.apidxEntries[0] = &m_idxRoot; + AVLStack.cEntries = 1; +#endif + unsigned cDepth = 0; + NodeType *pNodeLast = NULL; + while (pNode) + { + RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, &AVLStack, AVLStack.cEntries); + AssertReturn(cDepth <= kMaxHeight, VERR_HARDAVL_LOOKUP_TOO_DEEP); + cDepth++; + + if (isKeyInRange(a_Key, pNode->Key, pNode->KeyLast)) + { + *a_ppFound = pNode; + return VINF_SUCCESS; + } + if (isKeyGreater(pNode->Key, a_Key)) + { +#ifdef RT_STRICT + AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxLeft; +#endif + uint32_t const idxLeft = readIdx(&pNode->idxLeft); + NodeType *pLeftNode = a_pAllocator->ptrFromInt(idxLeft); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode), ("idxLeft=%#x pLeftNode=%p\n", idxLeft, pLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode)); + if (pLeftNode) + { + pNodeLast = pNode; + pNode = pLeftNode; + } + else + { + *a_ppFound = pNode; + return VINF_SUCCESS; + } + } + else + { +#ifdef RT_STRICT + AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxRight; +#endif + uint32_t const idxRight = readIdx(&pNode->idxRight); + NodeType *pRightNode = a_pAllocator->ptrFromInt(idxRight); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode), ("idxRight=%#x pRightNode=%p\n", idxRight, pRightNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode)); + if (pRightNode) + pNode = pRightNode; + else if (!pNodeLast) + break; + else + { + *a_ppFound = pNodeLast; + return VINF_SUCCESS; + } + } + } + + return VERR_NOT_FOUND; + } + + /** + * A callback for doWithAllFromLeft and doWithAllFromRight. + * + * @returns IPRT status code. Any non-zero status causes immediate return from + * the enumeration function. + * @param pNode The current node. + * @param pvUser The user argument. + */ + typedef DECLCALLBACKTYPE(int, FNCALLBACK,(NodeType *pNode, void *pvUser)); + /** Pointer to a callback for doWithAllFromLeft and doWithAllFromRight. */ + typedef FNCALLBACK *PFNCALLBACK; + + /** + * Iterates thru all nodes in the tree from left (smaller) to right. + * + * @returns IPRT status code. + * + * @param a_pAllocator Pointer to the allocator. + * @param a_pfnCallBack Pointer to callback function. + * @param a_pvUser Callback user argument. + * + * @note This is very similar code to doWithAllFromRight() and destroy(). + */ + int doWithAllFromLeft(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, + PFNCALLBACK a_pfnCallBack, void *a_pvUser) RT_NOEXCEPT + { + NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); + if (!pNode) + return VINF_SUCCESS; + + /* + * We simulate recursive calling here. For safety reasons, we do not + * pop before going down the right tree like the original code did. + */ + uint32_t cNodesLeft = a_pAllocator->m_cNodes; + NodeType *apEntries[kMaxStack]; + uint8_t abState[kMaxStack]; + unsigned cEntries = 1; + abState[0] = 0; + apEntries[0] = pNode; + while (cEntries > 0) + { + pNode = apEntries[cEntries - 1]; + switch (abState[cEntries - 1]) + { + /* Go left. */ + case 0: + { + abState[cEntries - 1] = 1; + + NodeType * const pLeftNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxLeft)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode), + ("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode)); + if (pLeftNode) + { +#if RT_GNUC_PREREQ_EX(4,7,1) && defined(RTASSERT_HAVE_STATIC_ASSERT) /* 32-bit 4.4.7 has trouble, dunno when it started working */ + AssertCompile(kMaxStack > 6); /* exactly. Seems having static_assert is required. */ +#endif + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries), + ("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1], + apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4], + apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + apEntries[cEntries] = pLeftNode; + abState[cEntries] = 0; + cEntries++; + + AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES); + cNodesLeft--; + break; + } + RT_FALL_THROUGH(); + } + + /* center then right. */ + case 1: + { + abState[cEntries - 1] = 2; + + RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0); + + int rc = a_pfnCallBack(pNode, a_pvUser); + if (rc != VINF_SUCCESS) + return rc; + + NodeType * const pRightNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxRight)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode), + ("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode)); + if (pRightNode) + { +#if RT_GNUC_PREREQ_EX(4,7,1) && defined(RTASSERT_HAVE_STATIC_ASSERT) /* 32-bit 4.4.7 has trouble, dunno when it started working */ + AssertCompile(kMaxStack > 6); /* exactly. Seems having static_assert is required. */ +#endif + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries), + ("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1], + apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4], + apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + apEntries[cEntries] = pRightNode; + abState[cEntries] = 0; + cEntries++; + + AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES); + cNodesLeft--; + break; + } + RT_FALL_THROUGH(); + } + + default: + /* pop it. */ + cEntries -= 1; + break; + } + } + return VINF_SUCCESS; + } + + /** + * Iterates thru all nodes in the tree from right (larger) to left (smaller). + * + * @returns IPRT status code. + * + * @param a_pAllocator Pointer to the allocator. + * @param a_pfnCallBack Pointer to callback function. + * @param a_pvUser Callback user argument. + * + * @note This is very similar code to doWithAllFromLeft() and destroy(). + */ + int doWithAllFromRight(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, + PFNCALLBACK a_pfnCallBack, void *a_pvUser) RT_NOEXCEPT + { + NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); + if (!pNode) + return VINF_SUCCESS; + + /* + * We simulate recursive calling here. For safety reasons, we do not + * pop before going down the right tree like the original code did. + */ + uint32_t cNodesLeft = a_pAllocator->m_cNodes; + NodeType *apEntries[kMaxStack]; + uint8_t abState[kMaxStack]; + unsigned cEntries = 1; + abState[0] = 0; + apEntries[0] = pNode; + while (cEntries > 0) + { + pNode = apEntries[cEntries - 1]; + switch (abState[cEntries - 1]) + { + /* Go right. */ + case 0: + { + abState[cEntries - 1] = 1; + + NodeType * const pRightNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxRight)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode), + ("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode)); + if (pRightNode) + { +#if RT_GNUC_PREREQ_EX(4,7,1) && defined(RTASSERT_HAVE_STATIC_ASSERT) /* 32-bit 4.4.7 has trouble, dunno when it started working */ + AssertCompile(kMaxStack > 6); /* exactly. Seems having static_assert is required. */ +#endif + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries), + ("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1], + apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4], + apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + apEntries[cEntries] = pRightNode; + abState[cEntries] = 0; + cEntries++; + + AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES); + cNodesLeft--; + break; + } + RT_FALL_THROUGH(); + } + + /* center then left. */ + case 1: + { + abState[cEntries - 1] = 2; + + RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0); + + int rc = a_pfnCallBack(pNode, a_pvUser); + if (rc != VINF_SUCCESS) + return rc; + + NodeType * const pLeftNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxLeft)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode), + ("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode)); + if (pLeftNode) + { +#if RT_GNUC_PREREQ_EX(4,7,1) && defined(RTASSERT_HAVE_STATIC_ASSERT) /* 32-bit 4.4.7 has trouble, dunno when it started working */ + AssertCompile(kMaxStack > 6); /* exactly. Seems having static_assert is required. */ +#endif + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries), + ("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1], + apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4], + apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + apEntries[cEntries] = pLeftNode; + abState[cEntries] = 0; + cEntries++; + + AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES); + cNodesLeft--; + break; + } + RT_FALL_THROUGH(); + } + + default: + /* pop it. */ + cEntries -= 1; + break; + } + } + return VINF_SUCCESS; + } + + /** + * A callback for destroy to do additional cleanups before the node is freed. + * + * @param pNode The current node. + * @param pvUser The user argument. + */ + typedef DECLCALLBACKTYPE(void, FNDESTROYCALLBACK,(NodeType *pNode, void *pvUser)); + /** Pointer to a callback for destroy. */ + typedef FNDESTROYCALLBACK *PFNDESTROYCALLBACK; + + /** + * Destroys the tree, starting with the root node. + * + * This will invoke the freeNode() method on the allocate for every node after + * first doing the callback to let the caller free additional resources + * referenced by the node. + * + * @returns IPRT status code. + * + * @param a_pAllocator Pointer to the allocator. + * @param a_pfnCallBack Pointer to callback function. Optional. + * @param a_pvUser Callback user argument. + * + * @note This is mostly the same code as the doWithAllFromLeft(). + */ + int destroy(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, + PFNDESTROYCALLBACK a_pfnCallBack = NULL, void *a_pvUser = NULL) RT_NOEXCEPT + { + NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); + if (!pNode) + return VINF_SUCCESS; + + /* + * We simulate recursive calling here. For safety reasons, we do not + * pop before going down the right tree like the original code did. + */ + uint32_t cNodesLeft = a_pAllocator->m_cNodes; + NodeType *apEntries[kMaxStack]; + uint8_t abState[kMaxStack]; + unsigned cEntries = 1; + abState[0] = 0; + apEntries[0] = pNode; + while (cEntries > 0) + { + pNode = apEntries[cEntries - 1]; + switch (abState[cEntries - 1]) + { + /* Go left. */ + case 0: + { + abState[cEntries - 1] = 1; + + NodeType * const pLeftNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxLeft)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode), + ("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode)); + if (pLeftNode) + { +#if RT_GNUC_PREREQ_EX(4,7,1) && defined(RTASSERT_HAVE_STATIC_ASSERT) /* 32-bit 4.4.7 has trouble, dunno when it started working */ + AssertCompile(kMaxStack > 6); /* exactly. Seems having static_assert is required. */ +#endif + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries), + ("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1], + apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4], + apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + apEntries[cEntries] = pLeftNode; + abState[cEntries] = 0; + cEntries++; + + AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES); + cNodesLeft--; + break; + } + RT_FALL_THROUGH(); + } + + /* right. */ + case 1: + { + abState[cEntries - 1] = 2; + + NodeType * const pRightNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxRight)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode), + ("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode)); + if (pRightNode) + { +#if RT_GNUC_PREREQ_EX(4,7,1) && defined(RTASSERT_HAVE_STATIC_ASSERT) /* 32-bit 4.4.7 has trouble, dunno when it started working */ + AssertCompile(kMaxStack > 6); /* exactly. Seems having static_assert is required. */ +#endif + AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries), + ("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1], + apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4], + apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]), + m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW); + apEntries[cEntries] = pRightNode; + abState[cEntries] = 0; + cEntries++; + + AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES); + cNodesLeft--; + break; + } + RT_FALL_THROUGH(); + } + + default: + { + /* pop it and destroy it. */ + if (a_pfnCallBack) + a_pfnCallBack(pNode, a_pvUser); + + int rc = a_pAllocator->freeNode(pNode); + AssertRCReturnStmt(rc, m_cErrors++, rc); + + cEntries -= 1; + break; + } + } + } + + Assert(m_idxRoot == a_pAllocator->kNilIndex); + return VINF_SUCCESS; + } + + + /** + * Gets the tree height value (reads cHeigh from the root node). + * + * @retval UINT8_MAX if bogus tree. + */ + uint8_t getHeight(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator) RT_NOEXCEPT + { + NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot)); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode), + m_cErrors++, UINT8_MAX); + if (pNode) + return pNode->cHeight; + return 0; + } + +#ifdef RT_STRICT + + static void dumpStack(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, HardAvlStack const *pStack) RT_NOEXCEPT + { + uint32_t const * const *paidx = pStack->apidxEntries; + RTAssertMsg2("stack: %u:\n", pStack->cEntries); + for (unsigned i = 0; i < pStack->cEntries; i++) + { + uint32_t idx = *paidx[i]; + uint32_t idxNext = i + 1 < pStack->cEntries ? *paidx[i + 1] : UINT32_MAX; + NodeType const *pNode = a_pAllocator->ptrFromInt(idx); + RTAssertMsg2(" #%02u: %p[%#06x] pNode=%p h=%02d l=%#06x%c r=%#06x%c\n", i, paidx[i], idx, pNode, pNode->cHeight, + pNode->idxLeft, pNode->idxLeft == idxNext ? '*' : ' ', + pNode->idxRight, pNode->idxRight == idxNext ? '*' : ' '); + } + } + + static void printTree(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, uint32_t a_idxRoot, + unsigned a_uLevel = 0, unsigned a_uMaxLevel = 8, const char *a_pszDir = "") RT_NOEXCEPT + { + if (a_idxRoot == a_pAllocator->kNilIndex) + RTAssertMsg2("%*snil\n", a_uLevel * 6, a_pszDir); + else if (a_uLevel < a_uMaxLevel) + { + NodeType *pNode = a_pAllocator->ptrFromInt(a_idxRoot); + printTree(a_pAllocator, readIdx(&pNode->idxRight), a_uLevel + 1, a_uMaxLevel, "/ "); + RTAssertMsg2("%*s%#x/%u\n", a_uLevel * 6, a_pszDir, a_idxRoot, pNode->cHeight); + printTree(a_pAllocator, readIdx(&pNode->idxLeft), a_uLevel + 1, a_uMaxLevel, "\\ "); + } + else + RTAssertMsg2("%*stoo deep\n", a_uLevel * 6, a_pszDir); + } + +#endif + +private: + /** + * Rewinds a stack of pointers to pointers to nodes, rebalancing the tree. + * + * @returns IPRT status code. + * + * @param a_pAllocator Pointer to the allocator. + * @param a_pStack Pointer to stack to rewind. + * @param a_fLog Log is done (DEBUG builds only). + * + * @code + * 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 + * @endcode + * @internal + */ + int i_rebalance(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, HardAvlStack *a_pStack, bool a_fLog = false) RT_NOEXCEPT + { + RT_NOREF(a_fLog); + + while (a_pStack->cEntries > 0) + { + /* pop */ + uint32_t * const pidxNode = a_pStack->apidxEntries[--a_pStack->cEntries]; + uint32_t const idxNode = readIdx(pidxNode); + NodeType * const pNode = a_pAllocator->ptrFromInt(idxNode); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), + ("pidxNode=%p[%#x] pNode=%p\n", pidxNode, *pidxNode, pNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pNode)); + + /* Read node properties: */ + uint32_t const idxLeftNode = readIdx(&pNode->idxLeft); + NodeType * const pLeftNode = a_pAllocator->ptrFromInt(idxLeftNode); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode), + ("idxLeftNode=%#x pLeftNode=%p\n", idxLeftNode, pLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode)); + + uint32_t const idxRightNode = readIdx(&pNode->idxRight); + NodeType * const pRightNode = a_pAllocator->ptrFromInt(idxRightNode); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode), + ("idxRight=%#x pRightNode=%p\n", idxRightNode, pRightNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode)); + + uint8_t const cLeftHeight = pLeftNode ? pLeftNode->cHeight : 0; + AssertReturnStmt(cLeftHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_LEFT_HEIGHT); + + uint8_t const cRightHeight = pRightNode ? pRightNode->cHeight : 0; + AssertReturnStmt(cRightHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_RIGHT_HEIGHT); + + /* Decide what needs doing: */ + if (cRightHeight + 1 < cLeftHeight) + { + Assert(cRightHeight + 2 == cLeftHeight); + AssertReturnStmt(pLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT); + + uint32_t const idxLeftLeftNode = readIdx(&pLeftNode->idxLeft); + NodeType * const pLeftLeftNode = a_pAllocator->ptrFromInt(idxLeftLeftNode); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeftNode), + ("idxLeftLeftNode=%#x pLeftLeftNode=%p\n", idxLeftLeftNode, pLeftLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeftNode)); + + uint32_t const idxLeftRightNode = readIdx(&pLeftNode->idxRight); + NodeType * const pLeftRightNode = a_pAllocator->ptrFromInt(idxLeftRightNode); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftRightNode), + ("idxLeftRightNode=%#x pLeftRightNode=%p\n", idxLeftRightNode, pLeftRightNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftRightNode)); + + uint8_t const cLeftRightHeight = pLeftRightNode ? pLeftRightNode->cHeight : 0; + if ((pLeftLeftNode ? pLeftLeftNode->cHeight : 0) >= cLeftRightHeight) + { + AssertReturnStmt(cLeftRightHeight + 2 <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT); + pNode->idxLeft = idxLeftRightNode; + pNode->cHeight = (uint8_t)(cLeftRightHeight + 1); + pLeftNode->cHeight = (uint8_t)(cLeftRightHeight + 2); + pLeftNode->idxRight = idxNode; + *pidxNode = idxLeftNode; +#ifdef DEBUG + if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #1\n", a_pStack->cEntries); +#endif + } + else + { + AssertReturnStmt(cLeftRightHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_RIGHT_HEIGHT); + AssertReturnStmt(pLeftRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT); + + uint32_t const idxLeftRightLeftNode = readIdx(&pLeftRightNode->idxLeft); + AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS); + uint32_t const idxLeftRightRightNode = readIdx(&pLeftRightNode->idxRight); + AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS); + pLeftNode->idxRight = idxLeftRightLeftNode; + pNode->idxLeft = idxLeftRightRightNode; + + pLeftRightNode->idxLeft = idxLeftNode; + pLeftRightNode->idxRight = idxNode; + pLeftNode->cHeight = cLeftRightHeight; + pNode->cHeight = cLeftRightHeight; + pLeftRightNode->cHeight = cLeftHeight; + *pidxNode = idxLeftRightNode; +#ifdef DEBUG + if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #2\n", a_pStack->cEntries); +#endif + } + m_cRebalancingOperations++; + } + else if (cLeftHeight + 1 < cRightHeight) + { + Assert(cLeftHeight + 2 == cRightHeight); + AssertReturnStmt(pRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT); + + uint32_t const idxRightLeftNode = readIdx(&pRightNode->idxLeft); + NodeType * const pRightLeftNode = a_pAllocator->ptrFromInt(idxRightLeftNode); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightLeftNode), + ("idxRightLeftNode=%#x pRightLeftNode=%p\n", idxRightLeftNode, pRightLeftNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pRightLeftNode)); + + uint32_t const idxRightRightNode = readIdx(&pRightNode->idxRight); + NodeType * const pRightRightNode = a_pAllocator->ptrFromInt(idxRightRightNode); + AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightRightNode), + ("idxRightRightNode=%#x pRightRightNode=%p\n", idxRightRightNode, pRightRightNode), + m_cErrors++, a_pAllocator->ptrErrToStatus(pRightRightNode)); + + uint8_t const cRightLeftHeight = pRightLeftNode ? pRightLeftNode->cHeight : 0; + if ((pRightRightNode ? pRightRightNode->cHeight : 0) >= cRightLeftHeight) + { + AssertReturnStmt(cRightLeftHeight + 2 <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT); + + pNode->idxRight = idxRightLeftNode; + pRightNode->idxLeft = idxNode; + pNode->cHeight = (uint8_t)(cRightLeftHeight + 1); + pRightNode->cHeight = (uint8_t)(cRightLeftHeight + 2); + *pidxNode = idxRightNode; +#ifdef DEBUG + if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #3 h=%d, *pidxNode=%#x\n", a_pStack->cEntries, pRightNode->cHeight, *pidxNode); +#endif + RTHARDAVL_STRICT_CHECK_HEIGHTS(pRightNode, NULL, 0); + RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0); + } + else + { + AssertReturnStmt(cRightLeftHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_LEFT_HEIGHT); + AssertReturnStmt(pRightLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT); + + uint32_t const idxRightLeftRightNode = readIdx(&pRightLeftNode->idxRight); + AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS); + uint32_t const idxRightLeftLeftNode = readIdx(&pRightLeftNode->idxLeft); + AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS); + pRightNode->idxLeft = idxRightLeftRightNode; + pNode->idxRight = idxRightLeftLeftNode; + + pRightLeftNode->idxRight = idxRightNode; + pRightLeftNode->idxLeft = idxNode; + pRightNode->cHeight = cRightLeftHeight; + pNode->cHeight = cRightLeftHeight; + pRightLeftNode->cHeight = cRightHeight; + *pidxNode = idxRightLeftNode; +#ifdef DEBUG + if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #4 h=%d, *pidxNode=%#x\n", a_pStack->cEntries, pRightLeftNode->cHeight, *pidxNode); +#endif + } + m_cRebalancingOperations++; + } + else + { + uint8_t const cHeight = (uint8_t)(RT_MAX(cLeftHeight, cRightHeight) + 1); + AssertReturnStmt(cHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT); + if (cHeight == pNode->cHeight) + { +#ifdef DEBUG + if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #5, h=%d - done\n", a_pStack->cEntries, cHeight); +#endif + RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0); + if (pLeftNode) + RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftNode, NULL, 0); + if (pRightNode) + RTHARDAVL_STRICT_CHECK_HEIGHTS(pRightNode, NULL, 0); + break; + } +#ifdef DEBUG + if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #5, h=%d - \n", a_pStack->cEntries, cHeight); +#endif + pNode->cHeight = cHeight; + } + } + return VINF_SUCCESS; + } +}; + +/** @} */ + +#endif /* !IPRT_INCLUDED_cpp_hardavlrange_h */ + |