los_rbtree.c

浏览该文件的文档.

/*
 * Copyright (c) 2013-2019 Huawei Technologies Co., Ltd. All rights reserved.
 * Copyright (c) 2020-2021 Huawei Device Co., Ltd. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this list of
 *    conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
 *    of conditions and the following disclaimer in the documentation and/or other materials
 *    provided with the distribution.
 *
 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
 *    to endorse or promote products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/* *
 * @defgroup los_rbtree Rbtree
 * @ingroup kernel
 */
 
#include "los_rbtree.h"
#include "los_memory.h"
 
 
STATIC VOID OsRbLeftRotateNode(LosRbTree *pstTree, LosRbNode *pstX);
STATIC VOID OsRbRightRotateNode(LosRbTree *pstTree, LosRbNode *pstY);
STATIC VOID OsRbInsertNodeFixup(LosRbTree *pstTree, VOID *pstData);
STATIC VOID OsRbDeleteNodeFixup(LosRbTree *pstTree, LosRbNode *pstNode);
STATIC VOID OsRbDeleteNode(LosRbTree *pstTree, VOID *pstData);
STATIC VOID OsRbInitTree(LosRbTree *pstTree);
STATIC VOID OsRbClearTree(LosRbTree *pstTree);
 
STATIC VOID OsRbLeftRotateNode(LosRbTree *pstTree, LosRbNode *pstX)
{
    LosRbNode *pstY = NULL;
    LosRbNode *pstNilT = NULL;
    LosRbNode *pstParent = NULL;
 
    if (pstTree == NULL || pstX == NULL) {
        return;
    }
    pstNilT = &(pstTree->stNilT);
    /* If pstX or pstY node's either child is NilT node:
     * Left / right rotation might change the NilT's parent.
     * NilT's parent shouldn't be changed.
     * If NilT's parent node changes,
     * then Delete_FixUp function might access NilT's parent's right/left child,
     * which might lead to error.
     * Solution: So we record the NilT's parent and at the end of the rotaion,
     * replace the NilT's parent with the recorded node.
     */
    pstParent = pstNilT->pstParent;
    pstY = pstX->pstRight;
    pstX->pstRight = pstY->pstLeft;
    pstY->pstLeft->pstParent = pstX;
    pstY->pstParent = pstX->pstParent;
    if (pstNilT == pstX->pstParent) {
        pstTree->pstRoot = pstY;
    } else {
        if (pstX == pstX->pstParent->pstLeft) {
            pstX->pstParent->pstLeft = pstY;
        } else {
            pstX->pstParent->pstRight = pstY;
        }
    }
    pstX->pstParent = pstY;
    pstY->pstLeft = pstX;
    pstNilT->pstParent = pstParent;
    return;
}
 
STATIC VOID OsRbRightRotateNode(LosRbTree *pstTree, LosRbNode *pstY)
{
    LosRbNode *pstX = NULL;
    LosRbNode *pstNilT = NULL;
    LosRbNode *pstParent = NULL;
    if (NULL == pstTree || NULL == pstY) {
        return;
    }
 
    pstNilT = &(pstTree->stNilT);
 
    /* If pstX or pstY node's either child is NilT node:
     * Left / right rotation might change the NilT's parent.
     * NilT's parent shouldn't be changed.
     * If NilT's parent node changes,
     * then Delete_FixUp function might access NilT's parent's right/left child,
     * which might lead to error.
     * Solution: So we record the NilT's parent and at the end of the rotaion,
     * replace the NilT's parent with the recorded node.
     */
    pstParent = pstNilT->pstParent;
    pstX = pstY->pstLeft;
    pstY->pstLeft = pstX->pstRight;
    pstX->pstRight->pstParent = pstY;
    pstX->pstParent = pstY->pstParent;
    if (pstNilT == pstY->pstParent) {
        pstTree->pstRoot = pstX;
    } else {
        if (pstY == pstY->pstParent->pstRight) {
            pstY->pstParent->pstRight = pstX;
        } else {
            pstY->pstParent->pstLeft = pstX;
        }
    }
    pstY->pstParent = pstX;
    pstX->pstRight = pstY;
    pstNilT->pstParent = pstParent;
    return;
}
 
STATIC VOID OsRbInsertNodeFixup(LosRbTree *pstTree, VOID *pstData)
{
    LosRbNode *pstParent = NULL;
    LosRbNode *pstGParent = NULL;
    LosRbNode *pstY = NULL;
    LosRbNode *pstX = NULL;
 
    if ((NULL == pstTree) || (NULL == pstData)) {
        return;
    }
 
    pstX = (LosRbNode *)pstData;
    /* NilT is forbidden. */
    (pstTree->ulNodes)++;
    while (LOS_RB_RED == pstX->pstParent->lColor) {
        pstParent = pstX->pstParent;
        pstGParent = pstParent->pstParent;
 
        if (pstParent == pstGParent->pstLeft) {
            pstY = pstGParent->pstRight;
            if (LOS_RB_RED == pstY->lColor) {
                pstY->lColor = LOS_RB_BLACK;
                pstParent->lColor = LOS_RB_BLACK;
                pstGParent->lColor = LOS_RB_RED;
                pstX = pstGParent;
                continue;
            }
 
            if (pstParent->pstRight == pstX) {
                pstX = pstParent;
                OsRbLeftRotateNode(pstTree, pstX);
            }
 
            pstX->pstParent->lColor = LOS_RB_BLACK;
            pstGParent->lColor = LOS_RB_RED;
            OsRbRightRotateNode(pstTree, pstGParent);
        } else {
            pstY = pstGParent->pstLeft;
            if (LOS_RB_RED == pstY->lColor) {
                pstY->lColor = LOS_RB_BLACK;
                pstParent->lColor = LOS_RB_BLACK;
                pstGParent->lColor = LOS_RB_RED;
                pstX = pstGParent;
                continue;
            }
 
            if (pstParent->pstLeft == pstX) {
                pstX = pstParent;
                OsRbRightRotateNode(pstTree, pstX);
            }
 
            pstX->pstParent->lColor = LOS_RB_BLACK;
            pstGParent->lColor = LOS_RB_RED;
            OsRbLeftRotateNode(pstTree, pstGParent);
        }
    }
 
    pstTree->pstRoot->lColor = LOS_RB_BLACK;
 
    return;
}
 
STATIC VOID OsRbDeleteNodeFixup(LosRbTree *pstTree, LosRbNode *pstNode)
{
    LosRbNode *pstW = NULL;
 
    if (NULL == pstTree || NULL == pstNode) {
        return;
    }
    while ((pstNode != pstTree->pstRoot) && (LOS_RB_BLACK == pstNode->lColor)) {
        if (pstNode->pstParent->pstLeft == pstNode) {
            pstW = pstNode->pstParent->pstRight;
            if (LOS_RB_RED == pstW->lColor) {
                pstW->lColor = LOS_RB_BLACK;
                pstNode->pstParent->lColor = LOS_RB_RED;
                OsRbLeftRotateNode(pstTree, pstNode->pstParent);
                pstW = pstNode->pstParent->pstRight;
            }
 
            if ((LOS_RB_BLACK == pstW->pstLeft->lColor) && (LOS_RB_BLACK == pstW->pstRight->lColor)) {
                pstW->lColor = LOS_RB_RED;
                pstNode = pstNode->pstParent;
            } else {
                if (LOS_RB_BLACK == pstW->pstRight->lColor) {
                    pstW->pstLeft->lColor = LOS_RB_BLACK;
                    pstW->lColor = LOS_RB_RED;
                    OsRbRightRotateNode(pstTree, pstW);
                    pstW = pstNode->pstParent->pstRight;
                }
                pstW->lColor = pstNode->pstParent->lColor;
                pstNode->pstParent->lColor = LOS_RB_BLACK;
                pstW->pstRight->lColor = LOS_RB_BLACK;
                OsRbLeftRotateNode(pstTree, pstNode->pstParent);
                pstNode = pstTree->pstRoot;
            }
        } else {
            pstW = pstNode->pstParent->pstLeft;
            if (LOS_RB_RED == pstW->lColor) {
                pstW->lColor = LOS_RB_BLACK;
                pstNode->pstParent->lColor = LOS_RB_RED;
                OsRbRightRotateNode(pstTree, pstNode->pstParent);
                pstW = pstNode->pstParent->pstLeft;
            }
            if ((LOS_RB_BLACK == pstW->pstLeft->lColor) && (LOS_RB_BLACK == pstW->pstRight->lColor)) {
                pstW->lColor = LOS_RB_RED;
                pstNode = pstNode->pstParent;
            } else {
                if (LOS_RB_BLACK == pstW->pstLeft->lColor) {
                    pstW->pstRight->lColor = LOS_RB_BLACK;
                    pstW->lColor = LOS_RB_RED;
                    OsRbLeftRotateNode(pstTree, pstW);
                    pstW = pstNode->pstParent->pstLeft;
                }
                pstW->lColor = pstNode->pstParent->lColor;
                pstNode->pstParent->lColor = LOS_RB_BLACK;
                pstW->pstLeft->lColor = LOS_RB_BLACK;
                OsRbRightRotateNode(pstTree, pstNode->pstParent);
                pstNode = pstTree->pstRoot;
            }
        }
    }
    pstNode->lColor = LOS_RB_BLACK;
    if (0 == pstTree->ulNodes) {
        OsRbClearTree(pstTree);
    }
 
    return;
}
 
STATIC VOID OsRbDeleteNode(LosRbTree *pstTree, VOID *pstData)
{
    LosRbNode *pstChild = NULL;
    LosRbNode *pstDel = NULL;
    ULONG_T lColor;
    LosRbWalk *pstWalk = NULL;
    LosRbNode *pstNilT = NULL;
    LosRbNode *pstZ = NULL;
    LOS_DL_LIST *pstNode = NULL;
 
    if ((NULL == pstTree) || (NULL == pstData)) {
        return;
    }
 
    pstZ = (LosRbNode *)pstData;
    pstNilT = &(pstTree->stNilT);
 
    /* NilT is forbidden. */
    if (!RB_IS_NOT_NILT(pstZ)) {
        return;
    }
 
    /* check whether the Node is in a tree */
    if ((pstZ->pstParent == pstNilT) && (pstZ->pstLeft == pstNilT) && (pstZ->pstRight == pstNilT) &&
        (pstTree->pstRoot != pstZ)) {
        return;
    }
 
    (pstTree->ulNodes)--;
 
    if (!LOS_ListEmpty(&pstTree->stWalkHead)) {
        LOS_DL_LIST_FOR_EACH(pstNode, &pstTree->stWalkHead)
        {
            pstWalk = LOS_DL_LIST_ENTRY(pstNode, LosRbWalk, stLink);
            if (pstWalk->pstCurrNode == pstZ) {
                pstWalk->pstCurrNode = LOS_RbSuccessorNode(pstTree, pstZ);
            }
        }
    }
 
    if ((pstNilT == pstZ->pstLeft) || (pstNilT == pstZ->pstRight)) {
        pstChild = ((pstNilT != pstZ->pstLeft) ? pstZ->pstLeft : pstZ->pstRight);
        if (NULL == pstChild) { /* Edit by r60958 for Coverity */
            return;
        }
 
        pstChild->pstParent = pstZ->pstParent;
 
        if (pstNilT == pstZ->pstParent) {
            pstTree->pstRoot = pstChild;
        } else {
            if (pstZ->pstParent->pstLeft == pstZ) {
                pstZ->pstParent->pstLeft = pstChild;
            } else {
                pstZ->pstParent->pstRight = pstChild;
            }
        }
 
        if (LOS_RB_BLACK == pstZ->lColor) {
            OsRbDeleteNodeFixup(pstTree, pstChild);
        }
 
        /* re-initialize the pstZ */
        pstZ->lColor = LOS_RB_RED;
        pstZ->pstLeft = pstZ->pstRight = pstZ->pstParent = pstNilT;
 
        return;
    }
 
    /* Here is some different with book "Introduction to Algorithms,
     * Second Edition", book's arithmetic won't delete pstZ, and it deletes
     * pstZ's successor node instead. But we delete pstZ because
     * our data structure has no internal node. So code is some complex.
     */
    pstDel = pstZ;
 
    /* Get pstZ's successor node */
    pstZ = pstZ->pstRight;
    while (pstNilT != pstZ->pstLeft) {
        pstZ = pstZ->pstLeft;
    }
 
    /* Because left is nilT, so child must be right. */
    pstChild = pstZ->pstRight;
    if (NULL == pstChild) { /* Edit by r60958 for Coverity */
        return;
    }
 
    lColor = pstZ->lColor;
 
    /* Remove successor node out of tree. */
    pstChild->pstParent = pstZ->pstParent;
 
    if (pstNilT == pstZ->pstParent) {
        /* In fact, we never go here. */
        pstTree->pstRoot = pstChild;
    } else {
        if (pstZ->pstParent->pstLeft == pstZ) {
            pstZ->pstParent->pstLeft = pstChild;
        } else {
            pstZ->pstParent->pstRight = pstChild;
        }
    }
 
    /* Insert successor node into tree and remove pstZ out of tree. */
    pstZ->pstParent = pstDel->pstParent;
    pstZ->lColor = pstDel->lColor;
    pstZ->pstRight = pstDel->pstRight;
    pstZ->pstLeft = pstDel->pstLeft;
 
    if (pstNilT == pstDel->pstParent) {
        /* if we arrive here, pstTree is no NULL */
        pstTree->pstRoot = pstZ;
    } else {
        if (pstDel->pstParent->pstLeft == pstDel) {
            pstDel->pstParent->pstLeft = pstZ;
        } else {
            pstDel->pstParent->pstRight = pstZ;
        }
    }
 
    pstDel->pstLeft->pstParent = pstZ;
    pstDel->pstRight->pstParent = pstZ;
 
    if (LOS_RB_BLACK == lColor) {
        OsRbDeleteNodeFixup(pstTree, pstChild);
    }
 
    /* re-initialize the pstDel */
    pstDel->lColor = LOS_RB_RED;
    pstDel->pstLeft = pstDel->pstRight = pstDel->pstParent = pstNilT;
    return;
}
 
 
STATIC VOID OsRbInitTree(LosRbTree *pstTree)
{
    if (NULL == pstTree) {
        return;
    }
 
    pstTree->ulNodes = 0;
    pstTree->pstRoot = &(pstTree->stNilT);
    pstTree->stNilT.lColor = LOS_RB_BLACK;
    pstTree->stNilT.pstLeft = NULL;   /* Always NULL */
    pstTree->stNilT.pstRight = NULL;  /* Always NULL */
    pstTree->stNilT.pstParent = NULL; /* Not NULL when tree isn't empty */
    LOS_ListInit(&pstTree->stWalkHead);
 
    pstTree->pfCmpKey = NULL;
    pstTree->pfFree = NULL;
    pstTree->pfGetKey = NULL;
 
    return;
}
 
STATIC VOID OsRbClearTree(LosRbTree *pstTree)
{
    LosRbWalk *pstWalk = NULL;
    LOS_DL_LIST *pstNode = NULL;
 
    if (NULL == pstTree) {
        return;
    }
 
    pstNode = LOS_DL_LIST_FIRST(&pstTree->stWalkHead);
    while (!LOS_DL_LIST_IS_END(&pstTree->stWalkHead, pstNode)) {
        pstWalk = LOS_DL_LIST_ENTRY(pstNode, LosRbWalk, stLink);
        pstWalk->pstCurrNode = NULL;
        pstWalk->pstTree = NULL;
 
        LOS_ListDelete(pstNode);
        pstNode = LOS_DL_LIST_FIRST(&pstTree->stWalkHead);
    }
 
    return;
}
 
LosRbWalk *LOS_RbCreateWalk(LosRbTree *pstTree)
{
    LosRbNode *pstNode = NULL;
    LosRbWalk *pstWalk = NULL;
 
    if (NULL == pstTree) {
        return NULL;
    }
 
    pstNode = LOS_RbFirstNode(pstTree);
    if (NULL == pstNode) {
        return NULL;
    }
 
    pstWalk = (LosRbWalk *)LOS_MemAlloc(m_aucSysMem0, sizeof(LosRbWalk));
    if (NULL == pstWalk) {
        return NULL;
    }
 
    LOS_ListAdd(&pstTree->stWalkHead, &pstWalk->stLink);
    pstWalk->pstCurrNode = pstNode;
    pstWalk->pstTree = pstTree;
    return pstWalk;
}
 
VOID *LOS_RbWalkNext(LosRbWalk *pstWalk)
{
    LosRbNode *pstNode = NULL;
 
    /*
     * Here, in the previous code, we didn't check pstCurrNode
     * pstTree, but in some circumstance, we will delete a tree
     * (by calling function RB_ClearTree), meanwhile, we will
     * evaluate pstCurrNode and pstTree to NULL, but at present,
     * if we are walking groups and ports, then we will call this
     * function(LOS_RbWalkNext), but the tree has been deleted already
     */
    if ((NULL == pstWalk) || (NULL == pstWalk->pstCurrNode) || (NULL == pstWalk->pstTree)) {
        return NULL;
    }
 
    pstNode = pstWalk->pstCurrNode;
    pstWalk->pstCurrNode = LOS_RbSuccessorNode(pstWalk->pstTree, pstNode);
    return pstNode;
}
 
VOID LOS_RbDeleteWalk(LosRbWalk *pstWalk)
{
    if (NULL == pstWalk) {
        return;
    }
 
    if (LOS_DL_LIST_IS_ON_QUEUE(&pstWalk->stLink)) {
        LOS_ListDelete(&pstWalk->stLink);
    }
    pstWalk->pstCurrNode = NULL;
    pstWalk->pstTree = NULL;
    LOS_MemFree(m_aucSysMem0, pstWalk);
 
    return;
}
 
VOID LOS_RbInsertOneNodeProcess(LosRbTree *pstTree, LosRbNode *pstParent, LosRbNode *pstNew)
{
    LosRbNode *pstNilT = &pstTree->stNilT;
    VOID *pNodeKey = NULL;
    VOID *pKey = NULL;
    ULONG_T ulCmpResult;
 
    pstNew->lColor = LOS_RB_RED;
    pstNew->pstLeft = pstNew->pstRight = pstNilT;
    if ((pstNew->pstParent = pstParent) == pstNilT) {
        pstTree->pstRoot = pstNew;
    } else {
        pNodeKey = pstTree->pfGetKey(pstNew);
        pKey = pstTree->pfGetKey(pstParent);
        ulCmpResult = pstTree->pfCmpKey(pNodeKey, pKey);
        if (RB_SMALLER == ulCmpResult) {
            pstParent->pstLeft = pstNew;
        } else {
            pstParent->pstRight = pstNew;
        }
    }
 
    OsRbInsertNodeFixup(pstTree, pstNew);
 
    return;
}
 
VOID LOS_RbInitTree(LosRbTree *pstTree, pfRBCmpKeyFn pfCmpKey, pfRBFreeFn pfFree, pfRBGetKeyFn pfGetKey)
{
    if (NULL == pstTree) {
        return;
    }
 
    OsRbInitTree(pstTree);
 
    pstTree->pfCmpKey = pfCmpKey;
    pstTree->pfFree = pfFree;
    pstTree->pfGetKey = pfGetKey;
 
    return;
}
 
VOID LOS_RbDestroyTree(LosRbTree *pstTree)
{
    LosRbNode *pstNode = NULL;
 
    if (NULL == pstTree) {
        return;
    }
    if (NULL == pstTree->pfFree) {
        return;
    }
 
    RB_WALK(pstTree, pstNode, pstWalk)
    {
        OsRbDeleteNode(pstTree, pstNode);
        (VOID)pstTree->pfFree(pstNode);
    }
    RB_WALK_END(pstTree, pstNode, pstWalk);
 
    OsRbClearTree(pstTree);
 
    return;
}
 
VOID *LOS_RbFirstNode(LosRbTree *pstTree)
{
    LosRbNode *pstNode = NULL;
    LosRbNode *pstNilT = NULL;
 
    if (NULL == pstTree) {
        return NULL;
    }
 
    pstNode = pstTree->pstRoot;
    if (pstNode == NULL) {
        return NULL;
    }
    pstNilT = &(pstTree->stNilT);
 
    if (pstNilT == pstNode) {
        return NULL;
    }
 
    while (pstNilT != pstNode->pstLeft) {
        pstNode = pstNode->pstLeft;
    }
 
    return pstNode;
}
 
VOID *LOS_RbSuccessorNode(LosRbTree *pstTree, VOID *pstData)
{
    LosRbNode *pstY = NULL;
    LosRbNode *pstNilT = NULL;
    LosRbNode *pstNode = NULL;
 
    if (NULL == pstTree) {
        return NULL;
    }
 
    pstNode = (LosRbNode *)pstData;
 
    if (NULL == pstNode) {
        return NULL;
    }
 
    /* NilT is forbidden. */
    if (!RB_IS_NOT_NILT(pstNode)) {
        return NULL;
    }
 
    /* if we arrive here, pstTree is no NULL */
    pstNilT = &(pstTree->stNilT);
 
    if (pstNilT != pstNode->pstRight) {
        pstNode = pstNode->pstRight;
        while (pstNilT != pstNode->pstLeft) {
            pstNode = pstNode->pstLeft;
        }
 
        return pstNode;
    }
 
    pstY = pstNode->pstParent;
 
    while ((pstNilT != pstY) && (pstNode == pstY->pstRight)) {
        pstNode = pstY;
        pstY = pstY->pstParent;
    }
 
    return ((pstNilT == pstY) ? NULL : pstY);
}
 
LosRbNode *LOS_RbGetNextNode(LosRbTree *pstTree, VOID *pKey)
{
    LosRbNode *pNode = NULL;
 
    if (TRUE == LOS_RbGetNode(pstTree, pKey, &pNode)) {
        return LOS_RbSuccessorNode(pstTree, pNode);
    } else if ((NULL == pNode) || (&pstTree->stNilT == pNode)) {
        return NULL;
    } else if (RB_BIGGER == pstTree->pfCmpKey(pKey, pstTree->pfGetKey(pNode))) {
        while (NULL != pNode) {
            pNode = LOS_RbSuccessorNode(pstTree, pNode);
            if (NULL == pNode) {
                return NULL;
            }
 
            if (RB_SMALLER == pstTree->pfCmpKey(pKey, pstTree->pfGetKey(pNode))) {
                break;
            }
        }
        return pNode;
    } else {
        return pNode;
    }
}
 
ULONG_T LOS_RbGetNode(LosRbTree *pstTree, VOID *pKey, LosRbNode **ppstNode)
{
    LosRbNode *pstNilT = NULL;
    LosRbNode *pstX = NULL;
    LosRbNode *pstY = NULL;
    VOID *pNodeKey = NULL;
    ULONG_T ulCmpResult;
 
    if ((NULL == pstTree) || (NULL == pKey) || (NULL == ppstNode)) {
        if (NULL != ppstNode) {
            *ppstNode = NULL;
        }
        return FALSE;
    }
    if ((NULL == pstTree->pfGetKey) || (NULL == pstTree->pfCmpKey)) {
        *ppstNode = NULL;
        return FALSE;
    }
 
    pstNilT = &pstTree->stNilT;
    pstY = pstTree->pstRoot;
    pstX = pstY;
 
    while (pstX != pstNilT) {
        pNodeKey = pstTree->pfGetKey(pstX);
 
        ulCmpResult = pstTree->pfCmpKey(pKey, pNodeKey);
        if (RB_EQUAL == ulCmpResult) {
            *ppstNode = pstX;
            return TRUE;
        }
        if (RB_SMALLER == ulCmpResult) {
            pstY = pstX;
            pstX = pstX->pstLeft;
        } else {
            pstY = pstX;
            pstX = pstX->pstRight;
        }
    }
 
    *ppstNode = pstY;
    return FALSE;
}
 
VOID LOS_RbDelNode(LosRbTree *pstTree, LosRbNode *pstNode)
{
    OsRbDeleteNode(pstTree, pstNode);
}
 
ULONG_T LOS_RbAddNode(LosRbTree *pstTree, LosRbNode *pstNew)
{
    ULONG_T ulSearchNode;
    VOID *pNodeKey = NULL;
    LosRbNode *pstX = NULL;
 
    if ((NULL == pstTree) || (NULL == pstNew)) {
        return FALSE;
    }
    if ((NULL == pstTree->pfGetKey) || (NULL == pstTree->pfCmpKey)) {
        return FALSE;
    }
 
    pNodeKey = pstTree->pfGetKey(pstNew);
    ulSearchNode = LOS_RbGetNode(pstTree, pNodeKey, &pstX);
    if (TRUE == ulSearchNode) {
        return FALSE;
    }
 
    if (NULL == pstX) {
        return FALSE;
    }
 
    LOS_RbInsertOneNodeProcess(pstTree, pstX, pstNew);
 
    return TRUE;
}