los_rbtree.c 文件参考

浏览源代码.

函数
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)
LosRbWalk *	LOS_RbCreateWalk (LosRbTree *pstTree)
VOID *	LOS_RbWalkNext (LosRbWalk *pstWalk)
VOID	LOS_RbDeleteWalk (LosRbWalk *pstWalk)
VOID	LOS_RbInsertOneNodeProcess (LosRbTree *pstTree, LosRbNode *pstParent, LosRbNode *pstNew)
VOID	LOS_RbInitTree (LosRbTree *pstTree, pfRBCmpKeyFn pfCmpKey, pfRBFreeFn pfFree, pfRBGetKeyFn pfGetKey)
VOID	LOS_RbDestroyTree (LosRbTree *pstTree)
VOID *	LOS_RbFirstNode (LosRbTree *pstTree)
VOID *	LOS_RbSuccessorNode (LosRbTree *pstTree, VOID *pstData)
LosRbNode *	LOS_RbGetNextNode (LosRbTree *pstTree, VOID *pKey)
ULONG_T	LOS_RbGetNode (LosRbTree *pstTree, VOID *pKey, LosRbNode **ppstNode)
VOID	LOS_RbDelNode (LosRbTree *pstTree, LosRbNode *pstNode)
ULONG_T	LOS_RbAddNode (LosRbTree *pstTree, LosRbNode *pstNew)

函数说明

LOS_RbAddNode()

ULONG_T LOS_RbAddNode	(	LosRbTree *	pstTree,
		LosRbNode *	pstNew
	)

在文件 los_rbtree.c 第 705 行定义.

{
    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;
}

函数调用图:

这是这个函数的调用关系图:

LOS_RbCreateWalk()

LosRbWalk * LOS_RbCreateWalk

(

LosRbTree *

pstTree

)

在文件 los_rbtree.c 第 435 行定义.

{
    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;
}

函数调用图:

LOS_RbDeleteWalk()

VOID LOS_RbDeleteWalk

(

LosRbWalk *

pstWalk

)

在文件 los_rbtree.c 第 481 行定义.

{
    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;
}

函数调用图:

LOS_RbDelNode()

VOID LOS_RbDelNode	(	LosRbTree *	pstTree,
		LosRbNode *	pstNode
	)

在文件 los_rbtree.c 第 700 行定义.

{
    OsRbDeleteNode(pstTree, pstNode);
}

函数调用图:

这是这个函数的调用关系图:

LOS_RbDestroyTree()

VOID LOS_RbDestroyTree

(

LosRbTree *

pstTree

)

在文件 los_rbtree.c 第 539 行定义.

{
    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;
}

函数调用图:

LOS_RbFirstNode()

VOID * LOS_RbFirstNode

(

LosRbTree *

pstTree

)

在文件 los_rbtree.c 第 562 行定义.

{
    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;
}

这是这个函数的调用关系图:

LOS_RbGetNextNode()

LosRbNode * LOS_RbGetNextNode	(	LosRbTree *	pstTree,
		VOID *	pKey
	)

在文件 los_rbtree.c 第 631 行定义.

{
    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;
    }
}

函数调用图:

LOS_RbGetNode()

ULONG_T LOS_RbGetNode	(	LosRbTree *	pstTree,
		VOID *	pKey,
		LosRbNode **	ppstNode
	)

在文件 los_rbtree.c 第 656 行定义.

{
    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;
}

这是这个函数的调用关系图:

LOS_RbInitTree()

VOID LOS_RbInitTree	(	LosRbTree *	pstTree,
		pfRBCmpKeyFn	pfCmpKey,
		pfRBFreeFn	pfFree,
		pfRBGetKeyFn	pfGetKey
	)

在文件 los_rbtree.c 第 524 行定义.

{
    if (NULL == pstTree) {
        return;
    }
 
    OsRbInitTree(pstTree);
 
    pstTree->pfCmpKey = pfCmpKey;
    pstTree->pfFree = pfFree;
    pstTree->pfGetKey = pfGetKey;
 
    return;
}

函数调用图:

这是这个函数的调用关系图:

LOS_RbInsertOneNodeProcess()

VOID LOS_RbInsertOneNodeProcess	(	LosRbTree *	pstTree,
		LosRbNode *	pstParent,
		LosRbNode *	pstNew
	)

在文件 los_rbtree.c 第 497 行定义.

{
    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;
}

函数调用图:

这是这个函数的调用关系图:

LOS_RbSuccessorNode()

VOID * LOS_RbSuccessorNode	(	LosRbTree *	pstTree,
		VOID *	pstData
	)

在文件 los_rbtree.c 第 588 行定义.

{
    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);
}

这是这个函数的调用关系图:

LOS_RbWalkNext()

VOID * LOS_RbWalkNext

(

LosRbWalk *

pstWalk

)

在文件 los_rbtree.c 第 460 行定义.

{
    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;
}

函数调用图:

OsRbClearTree()

STATIC VOID OsRbClearTree

(

LosRbTree *

pstTree

)

在文件 los_rbtree.c 第 413 行定义.

{
    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;
}

函数调用图:

这是这个函数的调用关系图:

OsRbDeleteNode()

STATIC VOID OsRbDeleteNode	(	LosRbTree *	pstTree,
		VOID *	pstData
	)

在文件 los_rbtree.c 第 257 行定义.

{
    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;
}

函数调用图:

这是这个函数的调用关系图:

OsRbDeleteNodeFixup()

STATIC VOID OsRbDeleteNodeFixup	(	LosRbTree *	pstTree,
		LosRbNode *	pstNode
	)

在文件 los_rbtree.c 第 190 行定义.

{
    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;
}

函数调用图:

这是这个函数的调用关系图:

OsRbInitTree()

STATIC VOID OsRbInitTree

(

LosRbTree *

pstTree

)

在文件 los_rbtree.c 第 392 行定义.

{
    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;
}

函数调用图:

这是这个函数的调用关系图:

OsRbInsertNodeFixup()

STATIC VOID OsRbInsertNodeFixup	(	LosRbTree *	pstTree,
		VOID *	pstData
	)

在文件 los_rbtree.c 第 128 行定义.

{
    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;
}

函数调用图:

这是这个函数的调用关系图:

OsRbLeftRotateNode()

STATIC VOID OsRbLeftRotateNode	(	LosRbTree *	pstTree,
		LosRbNode *	pstX
	)

在文件 los_rbtree.c 第 49 行定义.

{
    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;
}

这是这个函数的调用关系图:

OsRbRightRotateNode()

STATIC VOID OsRbRightRotateNode	(	LosRbTree *	pstTree,
		LosRbNode *	pstY
	)

在文件 los_rbtree.c 第 88 行定义.

{
    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;
}

这是这个函数的调用关系图: