Lines Matching refs:pstTree
41 STATIC VOID OsRbLeftRotateNode(LosRbTree *pstTree, LosRbNode *pstX);
42 STATIC VOID OsRbRightRotateNode(LosRbTree *pstTree, LosRbNode *pstY);
43 STATIC VOID OsRbInsertNodeFixup(LosRbTree *pstTree, VOID *pstData);
44 STATIC VOID OsRbDeleteNodeFixup(LosRbTree *pstTree, LosRbNode *pstNode);
45 STATIC VOID OsRbDeleteNode(LosRbTree *pstTree, VOID *pstData);
46 STATIC VOID OsRbInitTree(LosRbTree *pstTree);
47 STATIC VOID OsRbClearTree(LosRbTree *pstTree);
49 STATIC VOID OsRbLeftRotateNode(LosRbTree *pstTree, LosRbNode *pstX) in OsRbLeftRotateNode() argument
55 if (pstTree == NULL || pstX == NULL) { in OsRbLeftRotateNode()
58 pstNilT = &(pstTree->stNilT); in OsRbLeftRotateNode()
74 pstTree->pstRoot = pstY; in OsRbLeftRotateNode()
88 STATIC VOID OsRbRightRotateNode(LosRbTree *pstTree, LosRbNode *pstY) in OsRbRightRotateNode() argument
93 if (NULL == pstTree || NULL == pstY) { in OsRbRightRotateNode()
97 pstNilT = &(pstTree->stNilT); in OsRbRightRotateNode()
114 pstTree->pstRoot = pstX; in OsRbRightRotateNode()
128 STATIC VOID OsRbInsertNodeFixup(LosRbTree *pstTree, VOID *pstData) in OsRbInsertNodeFixup() argument
135 if ((NULL == pstTree) || (NULL == pstData)) { in OsRbInsertNodeFixup()
141 (pstTree->ulNodes)++; in OsRbInsertNodeFixup()
158 OsRbLeftRotateNode(pstTree, pstX); in OsRbInsertNodeFixup()
163 OsRbRightRotateNode(pstTree, pstGParent); in OsRbInsertNodeFixup()
176 OsRbRightRotateNode(pstTree, pstX); in OsRbInsertNodeFixup()
181 OsRbLeftRotateNode(pstTree, pstGParent); in OsRbInsertNodeFixup()
185 pstTree->pstRoot->lColor = LOS_RB_BLACK; in OsRbInsertNodeFixup()
190 STATIC VOID OsRbDeleteNodeFixup(LosRbTree *pstTree, LosRbNode *pstNode) in OsRbDeleteNodeFixup() argument
194 if (NULL == pstTree || NULL == pstNode) { in OsRbDeleteNodeFixup()
197 while ((pstNode != pstTree->pstRoot) && (LOS_RB_BLACK == pstNode->lColor)) { in OsRbDeleteNodeFixup()
203 OsRbLeftRotateNode(pstTree, pstNode->pstParent); in OsRbDeleteNodeFixup()
214 OsRbRightRotateNode(pstTree, pstW); in OsRbDeleteNodeFixup()
220 OsRbLeftRotateNode(pstTree, pstNode->pstParent); in OsRbDeleteNodeFixup()
221 pstNode = pstTree->pstRoot; in OsRbDeleteNodeFixup()
228 OsRbRightRotateNode(pstTree, pstNode->pstParent); in OsRbDeleteNodeFixup()
238 OsRbLeftRotateNode(pstTree, pstW); in OsRbDeleteNodeFixup()
244 OsRbRightRotateNode(pstTree, pstNode->pstParent); in OsRbDeleteNodeFixup()
245 pstNode = pstTree->pstRoot; in OsRbDeleteNodeFixup()
250 if (0 == pstTree->ulNodes) { in OsRbDeleteNodeFixup()
251 OsRbClearTree(pstTree); in OsRbDeleteNodeFixup()
257 STATIC VOID OsRbDeleteNode(LosRbTree *pstTree, VOID *pstData) in OsRbDeleteNode() argument
267 if ((NULL == pstTree) || (NULL == pstData)) { in OsRbDeleteNode()
272 pstNilT = &(pstTree->stNilT); in OsRbDeleteNode()
281 (pstTree->pstRoot != pstZ)) { in OsRbDeleteNode()
285 (pstTree->ulNodes)--; in OsRbDeleteNode()
287 if (!LOS_ListEmpty(&pstTree->stWalkHead)) { in OsRbDeleteNode()
288 LOS_DL_LIST_FOR_EACH(pstNode, &pstTree->stWalkHead) in OsRbDeleteNode()
292 pstWalk->pstCurrNode = LOS_RbSuccessorNode(pstTree, pstZ); in OsRbDeleteNode()
306 pstTree->pstRoot = pstChild; in OsRbDeleteNode()
316 OsRbDeleteNodeFixup(pstTree, pstChild); in OsRbDeleteNode()
352 pstTree->pstRoot = pstChild; in OsRbDeleteNode()
369 pstTree->pstRoot = pstZ; in OsRbDeleteNode()
382 OsRbDeleteNodeFixup(pstTree, pstChild); in OsRbDeleteNode()
392 STATIC VOID OsRbInitTree(LosRbTree *pstTree) in OsRbInitTree() argument
394 if (NULL == pstTree) { in OsRbInitTree()
398 pstTree->ulNodes = 0; in OsRbInitTree()
399 pstTree->pstRoot = &(pstTree->stNilT); in OsRbInitTree()
400 pstTree->stNilT.lColor = LOS_RB_BLACK; in OsRbInitTree()
401 pstTree->stNilT.pstLeft = NULL; /* Always NULL */ in OsRbInitTree()
402 pstTree->stNilT.pstRight = NULL; /* Always NULL */ in OsRbInitTree()
403 pstTree->stNilT.pstParent = NULL; /* Not NULL when tree isn't empty */ in OsRbInitTree()
404 LOS_ListInit(&pstTree->stWalkHead); in OsRbInitTree()
406 pstTree->pfCmpKey = NULL; in OsRbInitTree()
407 pstTree->pfFree = NULL; in OsRbInitTree()
408 pstTree->pfGetKey = NULL; in OsRbInitTree()
413 STATIC VOID OsRbClearTree(LosRbTree *pstTree) in OsRbClearTree() argument
418 if (NULL == pstTree) { in OsRbClearTree()
422 pstNode = LOS_DL_LIST_FIRST(&pstTree->stWalkHead); in OsRbClearTree()
423 while (!LOS_DL_LIST_IS_END(&pstTree->stWalkHead, pstNode)) { in OsRbClearTree()
426 pstWalk->pstTree = NULL; in OsRbClearTree()
429 pstNode = LOS_DL_LIST_FIRST(&pstTree->stWalkHead); in OsRbClearTree()
435 LosRbWalk *LOS_RbCreateWalk(LosRbTree *pstTree) in LOS_RbCreateWalk() argument
440 if (NULL == pstTree) { in LOS_RbCreateWalk()
444 pstNode = LOS_RbFirstNode(pstTree); in LOS_RbCreateWalk()
454 LOS_ListAdd(&pstTree->stWalkHead, &pstWalk->stLink); in LOS_RbCreateWalk()
456 pstWalk->pstTree = pstTree; in LOS_RbCreateWalk()
472 if ((NULL == pstWalk) || (NULL == pstWalk->pstCurrNode) || (NULL == pstWalk->pstTree)) { in LOS_RbWalkNext()
477 pstWalk->pstCurrNode = LOS_RbSuccessorNode(pstWalk->pstTree, pstNode); in LOS_RbWalkNext()
491 pstWalk->pstTree = NULL; in LOS_RbDeleteWalk()
497 VOID LOS_RbInsertOneNodeProcess(LosRbTree *pstTree, LosRbNode *pstParent, LosRbNode *pstNew) in LOS_RbInsertOneNodeProcess() argument
499 LosRbNode *pstNilT = &pstTree->stNilT; in LOS_RbInsertOneNodeProcess()
507 pstTree->pstRoot = pstNew; in LOS_RbInsertOneNodeProcess()
509 pNodeKey = pstTree->pfGetKey(pstNew); in LOS_RbInsertOneNodeProcess()
510 pKey = pstTree->pfGetKey(pstParent); in LOS_RbInsertOneNodeProcess()
511 ulCmpResult = pstTree->pfCmpKey(pNodeKey, pKey); in LOS_RbInsertOneNodeProcess()
519 OsRbInsertNodeFixup(pstTree, pstNew); in LOS_RbInsertOneNodeProcess()
524 VOID LOS_RbInitTree(LosRbTree *pstTree, pfRBCmpKeyFn pfCmpKey, pfRBFreeFn pfFree, pfRBGetKeyFn pfGe… in LOS_RbInitTree() argument
526 if (NULL == pstTree) { in LOS_RbInitTree()
530 OsRbInitTree(pstTree); in LOS_RbInitTree()
532 pstTree->pfCmpKey = pfCmpKey; in LOS_RbInitTree()
533 pstTree->pfFree = pfFree; in LOS_RbInitTree()
534 pstTree->pfGetKey = pfGetKey; in LOS_RbInitTree()
539 VOID LOS_RbDestroyTree(LosRbTree *pstTree) in LOS_RbDestroyTree() argument
543 if (NULL == pstTree) { in LOS_RbDestroyTree()
546 if (NULL == pstTree->pfFree) { in LOS_RbDestroyTree()
550 RB_WALK(pstTree, pstNode, pstWalk) in LOS_RbDestroyTree()
552 OsRbDeleteNode(pstTree, pstNode); in LOS_RbDestroyTree()
553 (VOID)pstTree->pfFree(pstNode); in LOS_RbDestroyTree()
555 RB_WALK_END(pstTree, pstNode, pstWalk); in LOS_RbDestroyTree()
557 OsRbClearTree(pstTree); in LOS_RbDestroyTree()
562 VOID *LOS_RbFirstNode(LosRbTree *pstTree) in LOS_RbFirstNode() argument
567 if (NULL == pstTree) { in LOS_RbFirstNode()
571 pstNode = pstTree->pstRoot; in LOS_RbFirstNode()
575 pstNilT = &(pstTree->stNilT); in LOS_RbFirstNode()
588 VOID *LOS_RbSuccessorNode(LosRbTree *pstTree, VOID *pstData) in LOS_RbSuccessorNode() argument
594 if (NULL == pstTree) { in LOS_RbSuccessorNode()
610 pstNilT = &(pstTree->stNilT); in LOS_RbSuccessorNode()
631 LosRbNode *LOS_RbGetNextNode(LosRbTree *pstTree, VOID *pKey) in LOS_RbGetNextNode() argument
635 if (TRUE == LOS_RbGetNode(pstTree, pKey, &pNode)) { in LOS_RbGetNextNode()
636 return LOS_RbSuccessorNode(pstTree, pNode); in LOS_RbGetNextNode()
637 } else if ((NULL == pNode) || (&pstTree->stNilT == pNode)) { in LOS_RbGetNextNode()
639 } else if (RB_BIGGER == pstTree->pfCmpKey(pKey, pstTree->pfGetKey(pNode))) { in LOS_RbGetNextNode()
641 pNode = LOS_RbSuccessorNode(pstTree, pNode); in LOS_RbGetNextNode()
646 if (RB_SMALLER == pstTree->pfCmpKey(pKey, pstTree->pfGetKey(pNode))) { in LOS_RbGetNextNode()
656 ULONG_T LOS_RbGetNode(LosRbTree *pstTree, VOID *pKey, LosRbNode **ppstNode) in LOS_RbGetNode() argument
664 if ((NULL == pstTree) || (NULL == pKey) || (NULL == ppstNode)) { in LOS_RbGetNode()
670 if ((NULL == pstTree->pfGetKey) || (NULL == pstTree->pfCmpKey)) { in LOS_RbGetNode()
675 pstNilT = &pstTree->stNilT; in LOS_RbGetNode()
676 pstY = pstTree->pstRoot; in LOS_RbGetNode()
680 pNodeKey = pstTree->pfGetKey(pstX); in LOS_RbGetNode()
682 ulCmpResult = pstTree->pfCmpKey(pKey, pNodeKey); in LOS_RbGetNode()
700 VOID LOS_RbDelNode(LosRbTree *pstTree, LosRbNode *pstNode) in LOS_RbDelNode() argument
702 OsRbDeleteNode(pstTree, pstNode); in LOS_RbDelNode()
705 ULONG_T LOS_RbAddNode(LosRbTree *pstTree, LosRbNode *pstNew) in LOS_RbAddNode() argument
711 if ((NULL == pstTree) || (NULL == pstNew)) { in LOS_RbAddNode()
714 if ((NULL == pstTree->pfGetKey) || (NULL == pstTree->pfCmpKey)) { in LOS_RbAddNode()
718 pNodeKey = pstTree->pfGetKey(pstNew); in LOS_RbAddNode()
719 ulSearchNode = LOS_RbGetNode(pstTree, pNodeKey, &pstX); in LOS_RbAddNode()
728 LOS_RbInsertOneNodeProcess(pstTree, pstX, pstNew); in LOS_RbAddNode()