Index: /trunk/include/iprt/cpp/hardavlrange.h
===================================================================
--- /trunk/include/iprt/cpp/hardavlrange.h	(revision 93671)
+++ /trunk/include/iprt/cpp/hardavlrange.h	(revision 93671)
@@ -0,0 +1,818 @@
+/** @file
+ * IPRT - Hardened AVL tree, unique key ranges.
+ */
+
+/*
+ * Copyright (C) 2022 Oracle Corporation
+ *
+ * This file is part of VirtualBox Open Source Edition (OSE), as
+ * available from http://www.virtualbox.org. This file is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU
+ * General Public License (GPL) as published by the Free Software
+ * Foundation, in version 2 as it comes in the "COPYING" file of the
+ * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
+ * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef 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
+ * @{
+ */
+
+/**
+ * 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;
+
+    /** 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;
+    }
+    /** @} */
+
+    RTCHardAvlRangeTree()
+        : m_idxRoot(0)
+        , m_cErrors(0)
+    { }
+
+    RTCHardAvlRangeTree(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator)
+        : 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)
+    {
+        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(*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;
+
+            /* 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;
+
+        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)
+    {
+        *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(*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;
+
+            /* 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.
+         */
+        if (pDeleteNode->idxLeft != a_pAllocator->kNilIndex)
+        {
+            /* find the rightmost node in the left tree. */
+            const unsigned  iStackEntry      = AVLStack.cEntries;
+            uint32_t       *pidxLeftLeast    = &pDeleteNode->idxLeft;
+            uint32_t        idxLeftLeastNode = pDeleteNode->idxLeft;
+            NodeType       *pLeftLeastNode   = a_pAllocator->ptrFromInt(idxLeftLeastNode);
+            AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeastNode),
+                                ("idxLeftLeastNode=%#x pLeftLeastNode=%p\n", idxLeftLeastNode, pLeftLeastNode),
+                                m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeastNode));
+
+            while (pLeftLeastNode->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",
+                                     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;
+
+                pidxLeftLeast    = &pLeftLeastNode->idxRight;
+                idxLeftLeastNode = pLeftLeastNode->idxRight;
+                pLeftLeastNode   = a_pAllocator->ptrFromInt(idxLeftLeastNode);
+                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeastNode),
+                                    ("idxLeftLeastNode=%#x pLeftLeastNode=%p\n", idxLeftLeastNode, pLeftLeastNode),
+                                    m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeastNode));
+            }
+
+            uint32_t const idxLeftLeastLeftNode = pLeftLeastNode->idxLeft;
+            AssertReturnStmt(a_pAllocator->isIntValid(idxLeftLeastLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
+
+            uint32_t const idxDeleteLeftNode  = pDeleteNode->idxLeft;
+            AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
+            uint32_t const idxDeleteRightNode = pDeleteNode->idxRight;
+            AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
+
+            /* link out pLeftLeast */
+            *pidxLeftLeast = idxLeftLeastLeftNode;
+
+            /* link it in place of the delete node. */
+            pLeftLeastNode->idxLeft   = idxDeleteLeftNode;
+            pLeftLeastNode->idxRight  = idxDeleteRightNode;
+            pLeftLeastNode->cHeight   = pDeleteNode->cHeight;
+            *pidxDeleteNode = idxLeftLeastNode;
+            AVLStack.apidxEntries[iStackEntry] = &pLeftLeastNode->idxLeft;
+        }
+        else
+        {
+            /* No left node, just pull up the right one. */
+            uint32_t const idxDeleteRightNode = pDeleteNode->idxRight;
+            AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
+            *pidxDeleteNode = idxDeleteRightNode;
+            AVLStack.cEntries--;
+        }
+        *a_ppRemoved = pDeleteNode;
+
+        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)
+    {
+        *a_ppFound = NULL;
+
+        NodeType *pNode = a_pAllocator->ptrFromInt(m_idxRoot);
+        AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
+                            m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
+
+        unsigned cDepth = 0;
+        while (pNode)
+        {
+            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))
+            {
+                uint32_t const idxLeft = 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
+            {
+                uint32_t const idxRight = 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;
+    }
+
+    /**
+     * 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.
+     */
+    int doWithAllFromLeft(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, PFNCALLBACK a_pfnCallBack, void *a_pvUser)
+    {
+        NodeType *pNode = a_pAllocator->ptrFromInt(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(pNode->idxLeft);
+                    AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
+                                        ("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
+                                        m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
+                    if (pLeftNode)
+                    {
+                        AssertCompile(kMaxStack > 6);
+                        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;
+
+                    int rc = a_pfnCallBack(pNode, a_pvUser);
+                    if (rc != VINF_SUCCESS)
+                        return rc;
+
+                    NodeType * const pRightNode = a_pAllocator->ptrFromInt(pNode->idxRight);
+                    AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
+                                        ("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
+                                        m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
+                    if (pRightNode)
+                    {
+                        AssertCompile(kMaxStack > 6);
+                        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;
+    }
+
+    /**
+     * 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)
+    {
+        NodeType *pNode = a_pAllocator->ptrFromInt(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(pNode->idxLeft);
+                    AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
+                                        ("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
+                                        m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
+                    if (pLeftNode)
+                    {
+                        AssertCompile(kMaxStack > 6);
+                        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(pNode->idxRight);
+                    AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
+                                        ("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
+                                        m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
+                    if (pRightNode)
+                    {
+                        AssertCompile(kMaxStack > 6);
+                        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;
+    }
+
+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.
+     *
+     * @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)
+    {
+        while (a_pStack->cEntries > 0)
+        {
+            /* pop */
+            uint32_t * const pidxNode  = a_pStack->apidxEntries[--a_pStack->cEntries];
+            uint32_t const   idxNode   = *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 = 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 = 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)
+            {
+                AssertReturnStmt(pLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
+
+                uint32_t const   idxLeftLeftNode = 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 = 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;
+                }
+                else
+                {
+                    AssertReturnStmt(cLeftRightHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_RIGHT_HEIGHT);
+                    AssertReturnStmt(pLeftRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
+
+                    uint32_t const idxLeftRightLeftNode  = pLeftRightNode->idxLeft;
+                    AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
+                    uint32_t const idxLeftRightRightNode = 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;
+                }
+            }
+            else if (cLeftHeight + 1 < cRightHeight)
+            {
+                AssertReturnStmt(pRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
+
+                uint32_t const   idxRightLeftNode = 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 = 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;
+                }
+                else
+                {
+                    AssertReturnStmt(cRightLeftHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_LEFT_HEIGHT);
+                    AssertReturnStmt(pRightLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
+
+                    uint32_t const idxRightLeftRightNode = pRightLeftNode->idxRight;
+                    AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
+                    uint32_t const idxRightLeftLeftNode  = 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;
+                }
+            }
+            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)
+                    break;
+                pNode->cHeight = cHeight;
+            }
+        }
+        return VINF_SUCCESS;
+    }
+};
+
+/** @} */
+
+#endif /* !IPRT_INCLUDED_cpp_hardavlrange_h */
+
Index: /trunk/include/iprt/cpp/hardavlslaballocator.h
===================================================================
--- /trunk/include/iprt/cpp/hardavlslaballocator.h	(revision 93671)
+++ /trunk/include/iprt/cpp/hardavlslaballocator.h	(revision 93671)
@@ -0,0 +1,188 @@
+/** @file
+ * IPRT - Hardened AVL tree slab allocator.
+ */
+
+/*
+ * Copyright (C) 2022 Oracle Corporation
+ *
+ * This file is part of VirtualBox Open Source Edition (OSE), as
+ * available from http://www.virtualbox.org. This file is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU
+ * General Public License (GPL) as published by the Free Software
+ * Foundation, in version 2 as it comes in the "COPYING" file of the
+ * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
+ * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+#ifndef IPRT_INCLUDED_cpp_hardavlslaballocator_h
+#define IPRT_INCLUDED_cpp_hardavlslaballocator_h
+#ifndef RT_WITHOUT_PRAGMA_ONCE
+# pragma once
+#endif
+
+#include <iprt/asm.h>
+#include <iprt/assert.h>
+#include <iprt/err.h>
+#include <iprt/string.h>
+
+/** @addtogroup grp_rt_cpp_hardavl
+ * @{
+ */
+
+
+/**
+ * Slab allocator for the hardened AVL tree.
+ */
+template<typename NodeType>
+struct RTCHardAvlTreeSlabAllocator
+{
+    /** Pointer to an array of nodes. */
+    NodeType   *m_paNodes;
+    /** Node allocation bitmap: 1 = free, 0 = allocated. */
+    uint64_t   *m_pbmAlloc;
+    /** Max number of nodes in m_paNodes and valid bits in m_pbmAlloc. */
+    uint32_t    m_cNodes;
+    /** Pointer error counter. */
+    uint32_t    m_cErrors;
+    /** Allocation hint. */
+    uint32_t    m_idxAllocHint;
+    uint32_t    m_uPadding;
+
+    enum
+    {
+        kNilIndex              = 0,
+        kErr_IndexOutOfBound   = -1,
+        kErr_PointerOutOfBound = -2,
+        kErr_MisalignedPointer = -3,
+        kErr_NodeIsFree        = -4,
+        kErr_Last              = kErr_NodeIsFree
+    };
+
+    RTCHardAvlTreeSlabAllocator() RT_NOEXCEPT
+        : m_paNodes(NULL)
+        , m_pbmAlloc(NULL)
+        , m_cNodes(0)
+        , m_cErrors(0)
+        , m_idxAllocHint(0)
+        , m_uPadding(0)
+    {}
+
+    inline void initSlabAllocator(uint32_t a_cNodes, NodeType *a_paNodes, uint64_t *a_pbmAlloc) RT_NOEXCEPT
+    {
+        m_cNodes   = a_cNodes;
+        m_paNodes  = a_paNodes;
+        m_pbmAlloc = a_pbmAlloc;
+
+        /* Initialize the allocation bit. */
+        RT_BZERO(a_pbmAlloc, (a_cNodes + 63) / 64 * 8);
+        ASMBitSetRange(a_pbmAlloc, 0, a_cNodes);
+    }
+
+    inline NodeType *ptrFromInt(uint32_t a_idxNode1) RT_NOEXCEPT
+    {
+        if (a_idxNode1 == (uint32_t)kNilIndex)
+            return NULL;
+        AssertMsgReturnStmt(a_idxNode1 <= m_cNodes, ("a_idxNode1=%#x m_cNodes=%#x\n", a_idxNode1, m_cNodes),
+                            m_cErrors++, (NodeType *)(intptr_t)kErr_IndexOutOfBound);
+        AssertMsgReturnStmt(ASMBitTest(m_pbmAlloc, a_idxNode1 - 1) == false, ("a_idxNode1=%#x\n", a_idxNode1),
+                            m_cErrors++, (NodeType *)(intptr_t)kErr_NodeIsFree);
+        return &m_paNodes[a_idxNode1 - 1];
+    }
+
+    static inline bool isPtrRetOkay(NodeType *a_pNode) RT_NOEXCEPT
+    {
+        return (uintptr_t)a_pNode < (uintptr_t)kErr_Last;
+    }
+
+    static inline int ptrErrToStatus(NodeType *a_pNode) RT_NOEXCEPT
+    {
+        return (int)(intptr_t)a_pNode - (VERR_HARDAVL_INDEX_OUT_OF_BOUNDS - kErr_IndexOutOfBound);
+    }
+
+    inline uint32_t ptrToInt(NodeType *a_pNode) RT_NOEXCEPT
+    {
+        if (a_pNode == NULL)
+            return 0;
+        uintptr_t const offNode  = (uintptr_t)a_pNode - (uintptr_t)m_paNodes;
+        uintptr_t const idxNode0 = offNode / sizeof(m_paNodes[0]);
+        AssertMsgReturnStmt((offNode % sizeof(m_paNodes[0])) == 0,
+                            ("pNode=%p / offNode=%#zx vs m_paNodes=%p L %#x, each %#x bytes\n",
+                             a_pNode, offNode, m_paNodes, m_cNodes, sizeof(m_paNodes[0])),
+                            m_cErrors++, (uint32_t)kErr_MisalignedPointer);
+        AssertMsgReturnStmt(idxNode0 < m_cNodes,
+                            ("pNode=%p vs m_paNodes=%p L %#x\n", a_pNode, m_paNodes, m_cNodes),
+                            m_cErrors++, (uint32_t)kErr_PointerOutOfBound);
+        AssertMsgReturnStmt(ASMBitTest(m_pbmAlloc, idxNode0) == false, ("a_pNode=%p idxNode0=%#x\n", a_pNode, idxNode0),
+                            m_cErrors++, (uint32_t)kErr_NodeIsFree);
+        return idxNode0 + 1;
+    }
+
+    static inline bool isIdxRetOkay(uint32_t a_idxNode) RT_NOEXCEPT
+    {
+        return a_idxNode < (uint32_t)kErr_Last;
+    }
+
+    static inline int idxErrToStatus(uint32_t a_idxNode) RT_NOEXCEPT
+    {
+        return (int)a_idxNode - (VERR_HARDAVL_INDEX_OUT_OF_BOUNDS - kErr_IndexOutOfBound);
+    }
+
+    inline bool isIntValid(uint32_t a_idxNode1)
+    {
+        return a_idxNode1 <= m_cNodes;
+    }
+
+    inline int freeNode(NodeType *a_pNode) RT_NOEXCEPT
+    {
+        uint32_t idxNode1 = ptrToInt(a_pNode);
+        if (idxNode1 == (uint32_t)kNilIndex)
+            return 0;
+        if (idxNode1 < (uint32_t)kErr_Last)
+        {
+            AssertMsgReturnStmt(ASMAtomicBitTestAndSet(m_pbmAlloc, idxNode1 - 1) == false,
+                                ("a_pNode=%p idxNode1=%#x\n", a_pNode, idxNode1),
+                                m_cErrors++, kErr_NodeIsFree);
+            return 0;
+        }
+        return (int)idxNode1;
+    }
+
+    inline NodeType *allocateNode(void) RT_NOEXCEPT
+    {
+        /*
+         * Use the hint first, then scan the whole bitmap.
+         * Note! We don't expect concurrent allocation calls, so no need to repeat.
+         */
+        uint32_t const idxHint = m_idxAllocHint;
+        uint32_t       idxNode0;
+        if (   idxHint >= m_cNodes
+            || (int32_t)(idxNode0 = (uint32_t)ASMBitNextSet(m_pbmAlloc, m_cNodes, idxHint)) < 0)
+            idxNode0 = (uint32_t)ASMBitFirstSet(m_pbmAlloc, m_cNodes);
+        if ((int32_t)idxNode0 >= 0)
+        {
+            if (ASMAtomicBitTestAndClear(m_pbmAlloc, idxNode0) == true)
+            {
+                m_idxAllocHint = idxNode0;
+                return &m_paNodes[idxNode0];
+            }
+            AssertMsgFailed(("idxNode0=%#x\n", idxNode0));
+            m_cErrors++;
+        }
+        return NULL;
+    }
+
+};
+
+/** @} */
+
+#endif /* !IPRT_INCLUDED_cpp_hardavlslaballocator_h */
+
Index: /trunk/include/iprt/err.h
===================================================================
--- /trunk/include/iprt/err.h	(revision 93670)
+++ /trunk/include/iprt/err.h	(revision 93671)
@@ -2727,4 +2727,5 @@
 /** @} */
 
+
 /** @name FTP status codes
  * @{ */
@@ -2756,4 +2757,35 @@
 /** @} */
 
+
+/** @name Hardened AVL tree status codes.
+ * @{ */
+/** Node index is out of bounds. */
+#define VERR_HARDAVL_INDEX_OUT_OF_BOUNDS                        (-26801)
+/** Node pointer is not within the memory allocated for nodes. */
+#define VERR_HARDAVL_POINTER_OUT_OF_BOUNDS                      (-26802)
+/** Node pointer does not point to the start of a node. */
+#define VERR_HARDAVL_MISALIGNED_POINTER                         (-26803)
+/** Bogus reference to freed node. */
+#define VERR_HARDAVL_NODE_IS_FREE                               (-26804)
+/** Stack overflow during AVL tree operation. */
+#define VERR_HARDAVL_STACK_OVERFLOW                             (-26810)
+/** Attempted to insert mode with invalid key range. */
+#define VERR_HARDAVL_INSERT_INVALID_KEY_RANGE                   (-26811)
+/** Bad left tree height. */
+#define VERR_HARDAVL_BAD_LEFT_HEIGHT                            (-26812)
+/** Bad left right height. */
+#define VERR_HARDAVL_BAD_RIGHT_HEIGHT                           (-26813)
+/** Bad new tree height. */
+#define VERR_HARDAVL_BAD_NEW_HEIGHT                             (-26814)
+/** Unexpected NULL pointer to left subtree. */
+#define VERR_HARDAVL_UNEXPECTED_NULL_LEFT                       (-26815)
+/** Unexpected NULL pointer to right subtree. */
+#define VERR_HARDAVL_UNEXPECTED_NULL_RIGHT                      (-26816)
+/** Tree traversal encountered more nodes than available in the allocator. */
+#define VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES                   (-26817)
+/** Too deep walk during lookup.  */
+#define VERR_HARDAVL_LOOKUP_TOO_DEEP                            (-26818)
+/** @} */
+
 /* SED-END */
 
Index: /trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp
===================================================================
--- /trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp	(revision 93670)
+++ /trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp	(revision 93671)
@@ -30,4 +30,5 @@
 *********************************************************************************************************************************/
 #include <iprt/avl.h>
+#include <iprt/cpp/hardavlrange.h>
 
 #include <iprt/asm.h>
@@ -1024,4 +1025,171 @@
 
 
+/*********************************************************************************************************************************
+*   RTCHardAvlRangeTreeGCPhys                                                                                                    *
+*********************************************************************************************************************************/
+
+typedef struct TESTNODE
+{
+    RTGCPHYS Key, KeyLast;
+    uint32_t idxLeft, idxRight;
+    uint8_t  cHeight;
+} MYTESTNODE;
+
+static DECLCALLBACK(int) hardAvlRangeTreeGCPhysEnumCallbackAscBy4(TESTNODE *pNode, void *pvUser)
+{
+    PRTGCPHYS pExpect = (PRTGCPHYS)pvUser;
+    if (pNode->Key != *pExpect)
+        RTTestIFailed("Key=%RGp, expected %RGp\n", pNode->Key, *pExpect);
+    *pExpect = pNode->Key + 4;
+    return VINF_SUCCESS;
+}
+
+/** @return meaningless, just for return RTTestIFailed(); */
+int hardAvlRangeTreeGCPhys(RTTEST hTest)
+{
+    RTTestISubF("RTCHardAvlRangeTreeGCPhys");
+
+    /*
+     * Tree and allocator variables.
+     */
+    RTCHardAvlTreeSlabAllocator<MYTESTNODE>   Allocator;
+    RTCHardAvlRangeTree<MYTESTNODE, RTGCPHYS> Tree(&Allocator);
+    AssertCompileSize(Tree, sizeof(uint32_t) * 2);
+    AssertCompileSize(Allocator, sizeof(void *) * 2 + sizeof(uint32_t) * 4);
+
+    /* Initialize the allocator with a decent slab of memory. */
+    const uint32_t cItems = 16384;
+    void *pvItems;
+    RTTESTI_CHECK_RC_RET(RTTestGuardedAlloc(hTest, sizeof(MYTESTNODE) * cItems,
+                                            sizeof(uint64_t), false, &pvItems), VINF_SUCCESS, 1);
+    void *pbmBitmap;
+    RTTESTI_CHECK_RC_RET(RTTestGuardedAlloc(hTest, RT_ALIGN_32(cItems, 64) / 64 * 8,
+                                            sizeof(uint64_t), false, &pbmBitmap), VINF_SUCCESS, 1);
+    Allocator.initSlabAllocator(cItems, (TESTNODE *)pvItems, (uint64_t *)pbmBitmap);
+
+    /*
+     * Simple linear insert, get and remove.
+     */
+    /* insert */
+    for (unsigned i = 0; i < 65536; i += 4)
+    {
+        MYTESTNODE *pNode = Allocator.allocateNode();
+        if (!pNode)
+            return RTTestIFailed("out of nodes: i=%#x", i);
+        pNode->Key = i;
+        pNode->KeyLast = i + 3;
+        int rc = Tree.insert(&Allocator, pNode);
+        if (rc != VINF_SUCCESS)
+            RTTestIFailed("linear insert i=%#x failed: %Rrc", i, rc);
+
+        /* look it up again immediately */
+        for (unsigned j = 0; j < 4; j++)
+        {
+            MYTESTNODE *pNode2;
+            rc = Tree.lookup(&Allocator, i + j, &pNode2);
+            if (rc != VINF_SUCCESS || pNode2 != pNode)
+                return RTTestIFailed("get after insert i=%#x j=%#x: %Rrc pNode=%p pNode2=%p", i, j, rc, pNode, pNode2);
+        }
+
+        /* Do negative inserts if we've got more free nodes. */
+        if (i / 4 + 1 < cItems)
+        {
+            MYTESTNODE *pNode2 = Allocator.allocateNode();
+            if (!pNode2)
+                return RTTestIFailed("out of nodes: i=%#x (#2)", i);
+            RTTESTI_CHECK(pNode2 != pNode);
+
+            *pNode2 = *pNode;
+            for (unsigned j = i >= 32 ? i - 32 : 0; j <= i + 3; j++)
+            {
+                for (unsigned k = i; k < i + 32; k++)
+                {
+                    pNode2->Key     = RT_MIN(j, k);
+                    pNode2->KeyLast = RT_MAX(k, j);
+                    rc = Tree.insert(&Allocator, pNode2);
+                    if (rc != VERR_ALREADY_EXISTS)
+                        return RTTestIFailed("linear negative insert: %Rrc, expected VERR_ALREADY_EXISTS; i=%#x j=%#x k=%#x; Key2=%RGp KeyLast2=%RGp vs Key=%RGp KeyLast=%RGp",
+                                             rc, i, j, k, pNode2->Key, pNode2->KeyLast, pNode->Key, pNode->KeyLast);
+                }
+                if (j == 0)
+                    break;
+            }
+
+            rc = Allocator.freeNode(pNode2);
+            if (rc != VINF_SUCCESS)
+                return RTTestIFailed("freeNode(pNode2=%p) failed: %Rrc (i=%#x)", pNode2, rc, i);
+        }
+    }
+
+    /* do gets. */
+    for (unsigned i = 0; i < 65536; i += 4)
+    {
+        MYTESTNODE *pNode;
+        int rc = Tree.lookup(&Allocator, i, &pNode);
+        if (rc != VINF_SUCCESS || pNode == NULL)
+            return RTTestIFailed("linear get i=%#x: %Rrc pNode=%p", i, rc, pNode);
+        if (i < pNode->Key || i > pNode->KeyLast)
+            return RTTestIFailed("linear get i=%#x Key=%RGp KeyLast=%RGp\n", i, pNode->Key, pNode->KeyLast);
+
+        for (unsigned j = 1; j < 4; j++)
+        {
+            MYTESTNODE *pNode2;
+            rc = Tree.lookup(&Allocator, i + j, &pNode2);
+            if (rc != VINF_SUCCESS || pNode2 != pNode)
+                return RTTestIFailed("linear get i=%#x j=%#x: %Rrc pNode=%p pNode2=%p", i, j, rc, pNode, pNode2);
+        }
+    }
+
+    /* negative get */
+    for (unsigned i = 65536; i < 65536 * 2; i += 1)
+    {
+        MYTESTNODE *pNode = (MYTESTNODE *)(uintptr_t)i;
+        int rc = Tree.lookup(&Allocator, i, &pNode);
+        if (rc != VERR_NOT_FOUND || pNode != NULL)
+            return RTTestIFailed("linear negative get i=%#x: %Rrc pNode=%p, expected VERR_NOT_FOUND and NULL", i, rc, pNode);
+    }
+
+    /* enumerate */
+    {
+        RTGCPHYS Expect = 0;
+        int rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackAscBy4, &Expect);
+        if (rc != VINF_SUCCESS)
+            RTTestIFailed("enumeration after linear insert failed: %Rrc", rc);
+    }
+
+    /* remove */
+    for (unsigned i = 0, j = 0; i < 65536; i += 4, j += 3)
+    {
+        MYTESTNODE *pNode;
+        int rc = Tree.remove(&Allocator, i + (j % 4), &pNode);
+        if (rc != VINF_SUCCESS || pNode == NULL)
+            return RTTestIFailed("linear remove(%#x): %Rrc pNode=%p", i + (j % 4), rc, pNode);
+        if (i < pNode->Key || i > pNode->KeyLast)
+            return RTTestIFailed("linear remove i=%#x Key=%RGp KeyLast=%RGp\n", i, pNode->Key, pNode->KeyLast);
+
+        memset(pNode, 0xcc, sizeof(*pNode));
+        Allocator.freeNode(pNode);
+
+        /* negative */
+        for (unsigned k = i; k < i + 4; k++)
+        {
+            pNode = (MYTESTNODE *)(uintptr_t)k;
+            rc = Tree.remove(&Allocator, k, &pNode);
+            if (rc != VERR_NOT_FOUND || pNode != NULL)
+                return RTTestIFailed("linear negative remove(%#x): %Rrc pNode=%p", k, rc, pNode);
+        }
+    }
+
+    /*
+     * Randomized stuff.
+     */
+    /** @todo add randomized testing step.  Split the address space up into equal
+     *        portition and pick what to insert/remove/lookup using a random
+     *        function against a insertion status bitmap. */
+
+    return 0;
+}
+
+
 int main()
 {
@@ -1066,4 +1234,5 @@
     avlrogcphys();
     avlul();
+    hardAvlRangeTreeGCPhys(hTest);
 
     /*
