los_rbtree.h 文件参考

浏览源代码.

结构体
struct	TagRbNode
struct	TagRbTree
struct	TagRbWalk
	记录步数 更多...

类型定义
typedef struct TagRbNode	LosRbNode
typedef ULONG_T(*	pfRBCmpKeyFn) (const VOID *, const VOID *)
typedef ULONG_T(*	pfRBFreeFn) (LosRbNode *)
typedef VOID *(*	pfRBGetKeyFn) (LosRbNode *)
typedef struct TagRbTree	LosRbTree
typedef struct TagRbWalk	LosRbWalk
	记录步数 更多...

函数
VOID *	LOS_RbFirstNode (LosRbTree *pstTree)
VOID *	LOS_RbSuccessorNode (LosRbTree *pstTree, VOID *pstData)
VOID	LOS_RbInitTree (LosRbTree *pstTree, pfRBCmpKeyFn pfCmpKey, pfRBFreeFn pfFree, pfRBGetKeyFn pfGetKey)
VOID	LOS_RbDestroyTree (LosRbTree *pstTree)
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)
LosRbWalk *	LOS_RbCreateWalk (LosRbTree *pstTree)
VOID *	LOS_RbWalkNext (LosRbWalk *pstWalk)
VOID	LOS_RbDeleteWalk (LosRbWalk *pstWalk)

类型定义说明

LosRbNode

typedef struct TagRbNode LosRbNode

LosRbTree

typedef struct TagRbTree LosRbTree

LosRbWalk

typedef struct TagRbWalk LosRbWalk

记录步数

pfRBCmpKeyFn

typedef ULONG_T(* pfRBCmpKeyFn) (const VOID *, const VOID *)

在文件 los_rbtree.h 第 58 行定义.

pfRBFreeFn

typedef ULONG_T(* pfRBFreeFn) (LosRbNode *)

在文件 los_rbtree.h 第 59 行定义.

pfRBGetKeyFn

typedef VOID *(* pfRBGetKeyFn) (LosRbNode *)

在文件 los_rbtree.h 第 60 行定义.

函数说明

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

函数调用图: