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

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

1 files changed, 1285 insertions, 0 deletions

diff --git a/include/iprt/cpp/hardavlrange.h b/include/iprt/cpp/hardavlrange.h
new file mode 100644
index 00000000..3c07a667
--- /dev/null
+++ b/include/iprt/cpp/hardavlrange.h
@@ -0,0 +1,1285 @@
+/** @file
+ * IPRT - Hardened AVL tree, unique key ranges.
+ */
+
+/*
+ * Copyright (C) 2022-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 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
+ * @ingroup grp_rt_cpp
+ * @{
+ */
+
+/**
+ * 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 */
+