VirtualBox

Changeset 93684 in vbox for trunk/include/iprt/cpp


Ignore:
Timestamp:
Feb 11, 2022 1:23:40 AM (3 years ago)
Author:
vboxsync
Message:

IPRT/hardavl: Fixed the removal bug. Extended testcase and sanity checks. bugref:10093

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/include/iprt/cpp/hardavlrange.h

    r93672 r93684  
    3737
    3838/**
     39 * Check that the tree heights make sense for the current node.
     40 *
     41 * This is a RT_STRICT test as it's expensive and we should have sufficient
     42 * other checks to ensure safe AVL tree operation.
     43 *
     44 * @note the a_cStackEntries parameter is a hack to avoid running into gcc's
     45 *       "the address of ‘AVLStack’ will never be NULL" errors.
     46 */
     47#ifdef RT_STRICT
     48# define RTHARDAVL_STRICT_CHECK_HEIGHTS(a_pNode, a_pAvlStack, a_cStackEntries) do { \
     49        NodeType * const pLeftNodeX    = a_pAllocator->ptrFromInt((a_pNode)->idxLeft); \
     50        AssertReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNodeX), m_cErrors++, a_pAllocator->ptrErrToStatus((a_pNode))); \
     51        NodeType * const pRightNodeX   = a_pAllocator->ptrFromInt((a_pNode)->idxRight); \
     52        AssertReturnStmt(a_pAllocator->isPtrRetOkay(pRightNodeX), m_cErrors++, a_pAllocator->ptrErrToStatus((a_pNode))); \
     53        uint8_t const    cLeftHeightX  = pLeftNodeX  ? pLeftNodeX->cHeight  : 0; \
     54        uint8_t const    cRightHeightX = pRightNodeX ? pRightNodeX->cHeight : 0; \
     55        if (RT_LIKELY((a_pNode)->cHeight == RT_MAX(cLeftHeightX, cRightHeightX) + 1)) { /*likely*/ } \
     56        else \
     57        { \
     58            RTAssertMsg2("line %u: %u l=%u r=%u\n", __LINE__, (a_pNode)->cHeight, cLeftHeightX, cRightHeightX); \
     59            if ((a_cStackEntries)) dumpStack(a_pAllocator, (a_pAvlStack)); \
     60            AssertMsgReturnStmt((a_pNode)->cHeight == RT_MAX(cLeftHeightX, cRightHeightX) + 1, \
     61                                ("%u l=%u r=%u\n", (a_pNode)->cHeight, cLeftHeightX, cRightHeightX), \
     62                                m_cErrors++, VERR_HARDAVL_BAD_HEIGHT); \
     63        } \
     64        AssertMsgReturnStmt(RT_ABS(cLeftHeightX - cRightHeightX) <= 1, ("l=%u r=%u\n", cLeftHeightX, cRightHeightX), \
     65                            m_cErrors++, VERR_HARDAVL_UNBALANCED); \
     66        Assert(!pLeftNodeX  || pLeftNodeX->Key < (a_pNode)->Key); \
     67        Assert(!pRightNodeX || pRightNodeX->Key > (a_pNode)->Key); \
     68    } while (0)
     69#else
     70# define RTHARDAVL_STRICT_CHECK_HEIGHTS(a_pNode, a_pAvlStack, a_cStackEntries) do { } while (0)
     71#endif
     72
     73
     74/**
    3975 * Hardened AVL tree for nodes with key ranges.
    4076 *
    … …  
    152188            AVLStack.cEntries = cEntries + 1;
    153189
     190            RTHARDAVL_STRICT_CHECK_HEIGHTS(pCurNode, &AVLStack, AVLStack.cEntries);
     191
    154192            /* Range check: */
    155193            if (areKeyRangesIntersecting(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
    … …  
    174212        return i_rebalance(a_pAllocator, &AVLStack);
    175213    }
     214
     215#ifdef RT_STRICT
     216
     217    static void dumpStack(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, HardAvlStack const *pStack)
     218    {
     219        uint32_t const * const *paidx = pStack->apidxEntries;
     220        RTAssertMsg2("stack: %u:\n", pStack->cEntries);
     221        for (unsigned i = 0; i < pStack->cEntries; i++)
     222        {
     223            uint32_t idx     = *paidx[i];
     224            uint32_t idxNext = i + 1 < pStack->cEntries ? *paidx[i + 1] : UINT32_MAX;
     225            NodeType const *pNode = a_pAllocator->ptrFromInt(idx);
     226            RTAssertMsg2(" #%02u: %p[%#06x] pNode=%p h=%02d l=%#06x%c r=%#06x%c\n", i, paidx[i], idx, pNode, pNode->cHeight,
     227                         pNode->idxLeft,  pNode->idxLeft  == idxNext ? '*' : ' ',
     228                         pNode->idxRight, pNode->idxRight == idxNext ? '*' : ' ');
     229        }
     230    }
     231
     232    static void printTree(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, uint32_t a_idxRoot, unsigned iLevel = 0)
     233    {
     234        if (a_idxRoot == a_pAllocator->kNilIndex)
     235            RTAssertMsg2("%*snil\n", iLevel * 6, "");
     236        else if (iLevel < 7)
     237        {
     238            NodeType *pNode = a_pAllocator->ptrFromInt(a_idxRoot);
     239            printTree(a_pAllocator, pNode->idxRight, iLevel + 1);
     240            RTAssertMsg2("%*s%#x/%u\n", iLevel * 6, "", a_idxRoot, pNode->cHeight);
     241            printTree(a_pAllocator, pNode->idxLeft, iLevel + 1);
     242        }
     243        else
     244            RTAssertMsg2("%*stoo deep\n", iLevel * 6, "");
     245    }
     246
     247#endif
    176248
    177249    /**
    … …  
    255327            AVLStack.cEntries = cEntries + 1;
    256328
     329            RTHARDAVL_STRICT_CHECK_HEIGHTS(pDeleteNode, &AVLStack, AVLStack.cEntries);
     330
    257331            /* Range check: */
    258332            if (isKeyInRange(a_Key, pDeleteNode->Key, pDeleteNode->KeyLast))
    … …  
    269343         * Do the deletion.
    270344         */
    271         if (pDeleteNode->idxLeft != a_pAllocator->kNilIndex)
     345        uint32_t const idxDeleteLeftNode = pDeleteNode->idxLeft;
     346        if (idxDeleteLeftNode != a_pAllocator->kNilIndex)
    272347        {
    273             /* find the rightmost node in the left tree. */
    274             const unsigned  iStackEntry      = AVLStack.cEntries;
    275             uint32_t       *pidxLeftLeast    = &pDeleteNode->idxLeft;
    276             uint32_t        idxLeftLeastNode = pDeleteNode->idxLeft;
    277             NodeType       *pLeftLeastNode   = a_pAllocator->ptrFromInt(idxLeftLeastNode);
    278             AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeastNode),
    279                                 ("idxLeftLeastNode=%#x pLeftLeastNode=%p\n", idxLeftLeastNode, pLeftLeastNode),
    280                                 m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeastNode));
    281 
    282             while (pLeftLeastNode->idxRight != a_pAllocator->kNilIndex)
     348            /*
     349             * Replace the deleted node with the rightmost node in the left subtree.
     350             */
     351            NodeType * const  pDeleteLeftNode   = a_pAllocator->ptrFromInt(idxDeleteLeftNode);
     352            AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pDeleteLeftNode),
     353                                ("idxDeleteLeftNode=%#x pDeleteLeftNode=%p\n", idxDeleteLeftNode, pDeleteLeftNode),
     354                                m_cErrors++, a_pAllocator->ptrErrToStatus(pDeleteLeftNode));
     355
     356            uint32_t const   idxDeleteRightNode = pDeleteNode->idxRight;
     357            AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
     358
     359            const unsigned   iStackEntry = AVLStack.cEntries;
     360
     361            uint32_t *pidxLeftBiggest    = &pDeleteNode->idxLeft;
     362            uint32_t  idxLeftBiggestNode = idxDeleteLeftNode;
     363            NodeType *pLeftBiggestNode   = pDeleteLeftNode;
     364            RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftBiggestNode, &AVLStack, AVLStack.cEntries);
     365
     366            while (pLeftBiggestNode->idxRight != a_pAllocator->kNilIndex)
    283367            {
    284368                unsigned const cEntries = AVLStack.cEntries;
    285369                AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries),
    286370                                    ("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n",
    287                                      pidxDeleteNode, *pidxDeleteNode, pDeleteNode,
     371                                     pidxLeftBiggest, *pidxLeftBiggest, pLeftBiggestNode,
    288372                                     AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1],
    289373                                     AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2],
    … …  
    292376                                     AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]),
    293377                                    m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
    294                 AVLStack.apidxEntries[cEntries] = pidxLeftLeast;
     378                AVLStack.apidxEntries[cEntries] = pidxLeftBiggest;
    295379                AVLStack.cEntries = cEntries + 1;
    296380
    297                 pidxLeftLeast    = &pLeftLeastNode->idxRight;
    298                 idxLeftLeastNode = pLeftLeastNode->idxRight;
    299                 pLeftLeastNode   = a_pAllocator->ptrFromInt(idxLeftLeastNode);
    300                 AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeastNode),
    301                                     ("idxLeftLeastNode=%#x pLeftLeastNode=%p\n", idxLeftLeastNode, pLeftLeastNode),
    302                                     m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeastNode));
     381                pidxLeftBiggest    = &pLeftBiggestNode->idxRight;
     382                idxLeftBiggestNode = pLeftBiggestNode->idxRight;
     383                pLeftBiggestNode   = a_pAllocator->ptrFromInt(idxLeftBiggestNode);
     384                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftBiggestNode),
     385                                    ("idxLeftBiggestNode=%#x pLeftBiggestNode=%p\n", idxLeftBiggestNode, pLeftBiggestNode),
     386                                    m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftBiggestNode));
     387                RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftBiggestNode, &AVLStack, AVLStack.cEntries);
    303388            }
    304389
    305             uint32_t const idxLeftLeastLeftNode = pLeftLeastNode->idxLeft;
    306             AssertReturnStmt(a_pAllocator->isIntValid(idxLeftLeastLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    307 
    308             uint32_t const idxDeleteLeftNode  = pDeleteNode->idxLeft;
    309             AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    310             uint32_t const idxDeleteRightNode = pDeleteNode->idxRight;
    311             AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    312 
    313             /* link out pLeftLeast */
    314             *pidxLeftLeast = idxLeftLeastLeftNode;
    315 
    316             /* link it in place of the delete node. */
    317             pLeftLeastNode->idxLeft   = idxDeleteLeftNode;
    318             pLeftLeastNode->idxRight  = idxDeleteRightNode;
    319             pLeftLeastNode->cHeight   = pDeleteNode->cHeight;
    320             *pidxDeleteNode = idxLeftLeastNode;
    321             AVLStack.apidxEntries[iStackEntry] = &pLeftLeastNode->idxLeft;
     390            uint32_t const idxLeftBiggestLeftNode = pLeftBiggestNode->idxLeft;
     391            AssertReturnStmt(a_pAllocator->isIntValid(idxLeftBiggestLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
     392
     393            /* link out pLeftBiggestNode */
     394            *pidxLeftBiggest = idxLeftBiggestLeftNode;
     395
     396            /* link it in place of the deleted node. */
     397            if (idxDeleteLeftNode != idxLeftBiggestNode)
     398                pLeftBiggestNode->idxLeft = idxDeleteLeftNode;
     399            pLeftBiggestNode->idxRight    = idxDeleteRightNode;
     400            pLeftBiggestNode->cHeight     = AVLStack.cEntries > iStackEntry ? pDeleteNode->cHeight : 0;
     401
     402            *pidxDeleteNode = idxLeftBiggestNode;
     403
     404            if (AVLStack.cEntries > iStackEntry)
     405                AVLStack.apidxEntries[iStackEntry] = &pLeftBiggestNode->idxLeft;
    322406        }
    323407        else
    … …  
    351435        AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
    352436                            m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
    353 
     437#ifdef RT_STRICT
     438        HardAvlStack  AVLStack;
     439        AVLStack.apidxEntries[0] = &m_idxRoot;
     440        AVLStack.cEntries = 1;
     441#endif
    354442        unsigned cDepth = 0;
    355443        while (pNode)
    356444        {
     445            RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, &AVLStack, AVLStack.cEntries);
    357446            AssertReturn(cDepth <= kMaxHeight, VERR_HARDAVL_LOOKUP_TOO_DEEP);
    358447            cDepth++;
    … …  
    365454            if (isKeyGreater(pNode->Key, a_Key))
    366455            {
     456#ifdef RT_STRICT
     457                AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxLeft;
     458#endif
    367459                uint32_t const idxLeft = pNode->idxLeft;
    368460                pNode = a_pAllocator->ptrFromInt(idxLeft);
    … …  
    372464            else
    373465            {
     466#ifdef RT_STRICT
     467                AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxRight;
     468#endif
    374469                uint32_t const idxRight = pNode->idxRight;
    375470                pNode = a_pAllocator->ptrFromInt(idxRight);
    … …  
    461556                    abState[cEntries - 1] = 2;
    462557
     558                    RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0);
     559
    463560                    int rc = a_pfnCallBack(pNode, a_pvUser);
    464561                    if (rc != VINF_SUCCESS)
    … …  
    684781     * @internal
    685782     */
    686     int i_rebalance(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, HardAvlStack *a_pStack)
    687     {
     783    int i_rebalance(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, HardAvlStack *a_pStack, bool fLog = false)
     784    {
     785        RT_NOREF(fLog);
     786
    688787        while (a_pStack->cEntries > 0)
    689788        {
    … …  
    718817            if (cRightHeight + 1 < cLeftHeight)
    719818            {
     819                Assert(cRightHeight + 2 == cLeftHeight);
    720820                AssertReturnStmt(pLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
    721821
    … …  
    741841                    pLeftNode->idxRight = idxNode;
    742842                    *pidxNode = idxLeftNode;
     843#ifdef DEBUG
     844                    if (fLog) RTAssertMsg2("rebalance: %#2u: op #1\n", a_pStack->cEntries);
     845#endif
    743846                }
    744847                else
    … …  
    760863                    pLeftRightNode->cHeight  = cLeftHeight;
    761864                    *pidxNode = idxLeftRightNode;
     865#ifdef DEBUG
     866                    if (fLog) RTAssertMsg2("rebalance: %#2u: op #2\n", a_pStack->cEntries);
     867#endif
    762868                }
    763869            }
    764870            else if (cLeftHeight + 1 < cRightHeight)
    765871            {
     872                Assert(cLeftHeight + 2 == cRightHeight);
    766873                AssertReturnStmt(pRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
    767874
    … …  
    788895                    pRightNode->cHeight = (uint8_t)(cRightLeftHeight + 2);
    789896                    *pidxNode = idxRightNode;
     897#ifdef DEBUG
     898                    if (fLog) RTAssertMsg2("rebalance: %#2u: op #3 h=%d, *pidxNode=%#x\n", a_pStack->cEntries, pRightNode->cHeight, *pidxNode);
     899#endif
     900                    RTHARDAVL_STRICT_CHECK_HEIGHTS(pRightNode, NULL, 0);
     901                    RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0);
    790902                }
    791903                else
    … …  
    800912                    pRightNode->idxLeft      = idxRightLeftRightNode;
    801913                    pNode->idxRight          = idxRightLeftLeftNode;
     914
    802915                    pRightLeftNode->idxRight = idxRightNode;
    803916                    pRightLeftNode->idxLeft  = idxNode;
    … …  
    806919                    pRightLeftNode->cHeight  = cRightHeight;
    807920                    *pidxNode = idxRightLeftNode;
     921#ifdef DEBUG
     922                    if (fLog) RTAssertMsg2("rebalance: %#2u: op #4 h=%d, *pidxNode=%#x\n", a_pStack->cEntries, pRightLeftNode->cHeight, *pidxNode);
     923#endif
    808924                }
    809925            }
    … …  
    813929                AssertReturnStmt(cHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT);
    814930                if (cHeight == pNode->cHeight)
     931                {
     932#ifdef DEBUG
     933                    if (fLog) RTAssertMsg2("rebalance: %#2u: op #5, h=%d - done\n", a_pStack->cEntries, cHeight);
     934#endif
     935                    RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0);
     936                    if (pLeftNode)
     937                        RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftNode, NULL, 0);
     938                    if (pRightNode)
     939                        RTHARDAVL_STRICT_CHECK_HEIGHTS(pRightNode, NULL, 0);
    815940                    break;
     941                }
     942#ifdef DEBUG
     943                if (fLog) RTAssertMsg2("rebalance: %#2u: op #5, h=%d - \n", a_pStack->cEntries, cHeight);
     944#endif
    816945                pNode->cHeight = cHeight;
    817946            }
Note: See TracChangeset for help on using the changeset viewer.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette