1 /*
2 * Copyright (c) 2013-2019 Huawei Technologies Co., Ltd. All rights reserved.
3 * Copyright (c) 2020-2021 Huawei Device Co., Ltd. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this list of
9 * conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 * of conditions and the following disclaimer in the documentation and/or other materials
13 * provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
16 * to endorse or promote products derived from this software without specific prior written
17 * permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /* *
33 * @defgroup los_rbtree Rbtree
34 * @ingroup kernel
35 */
36
37 #include "los_rbtree.h"
38 #include "los_memory.h"
39
40
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);
48
OsRbLeftRotateNode(LosRbTree * pstTree,LosRbNode * pstX)49 STATIC VOID OsRbLeftRotateNode(LosRbTree *pstTree, LosRbNode *pstX)
50 {
51 LosRbNode *pstY = NULL;
52 LosRbNode *pstNilT = NULL;
53 LosRbNode *pstParent = NULL;
54
55 if (pstTree == NULL || pstX == NULL) {
56 return;
57 }
58 pstNilT = &(pstTree->stNilT);
59 /* If pstX or pstY node's either child is NilT node:
60 * Left / right rotation might change the NilT's parent.
61 * NilT's parent shouldn't be changed.
62 * If NilT's parent node changes,
63 * then Delete_FixUp function might access NilT's parent's right/left child,
64 * which might lead to error.
65 * Solution: So we record the NilT's parent and at the end of the rotaion,
66 * replace the NilT's parent with the recorded node.
67 */
68 pstParent = pstNilT->pstParent;
69 pstY = pstX->pstRight;
70 pstX->pstRight = pstY->pstLeft;
71 pstY->pstLeft->pstParent = pstX;
72 pstY->pstParent = pstX->pstParent;
73 if (pstNilT == pstX->pstParent) {
74 pstTree->pstRoot = pstY;
75 } else {
76 if (pstX == pstX->pstParent->pstLeft) {
77 pstX->pstParent->pstLeft = pstY;
78 } else {
79 pstX->pstParent->pstRight = pstY;
80 }
81 }
82 pstX->pstParent = pstY;
83 pstY->pstLeft = pstX;
84 pstNilT->pstParent = pstParent;
85 return;
86 }
87
OsRbRightRotateNode(LosRbTree * pstTree,LosRbNode * pstY)88 STATIC VOID OsRbRightRotateNode(LosRbTree *pstTree, LosRbNode *pstY)
89 {
90 LosRbNode *pstX = NULL;
91 LosRbNode *pstNilT = NULL;
92 LosRbNode *pstParent = NULL;
93 if (NULL == pstTree || NULL == pstY) {
94 return;
95 }
96
97 pstNilT = &(pstTree->stNilT);
98
99 /* If pstX or pstY node's either child is NilT node:
100 * Left / right rotation might change the NilT's parent.
101 * NilT's parent shouldn't be changed.
102 * If NilT's parent node changes,
103 * then Delete_FixUp function might access NilT's parent's right/left child,
104 * which might lead to error.
105 * Solution: So we record the NilT's parent and at the end of the rotaion,
106 * replace the NilT's parent with the recorded node.
107 */
108 pstParent = pstNilT->pstParent;
109 pstX = pstY->pstLeft;
110 pstY->pstLeft = pstX->pstRight;
111 pstX->pstRight->pstParent = pstY;
112 pstX->pstParent = pstY->pstParent;
113 if (pstNilT == pstY->pstParent) {
114 pstTree->pstRoot = pstX;
115 } else {
116 if (pstY == pstY->pstParent->pstRight) {
117 pstY->pstParent->pstRight = pstX;
118 } else {
119 pstY->pstParent->pstLeft = pstX;
120 }
121 }
122 pstY->pstParent = pstX;
123 pstX->pstRight = pstY;
124 pstNilT->pstParent = pstParent;
125 return;
126 }
127
OsRbInsertNodeFixup(LosRbTree * pstTree,VOID * pstData)128 STATIC VOID OsRbInsertNodeFixup(LosRbTree *pstTree, VOID *pstData)
129 {
130 LosRbNode *pstParent = NULL;
131 LosRbNode *pstGParent = NULL;
132 LosRbNode *pstY = NULL;
133 LosRbNode *pstX = NULL;
134
135 if ((NULL == pstTree) || (NULL == pstData)) {
136 return;
137 }
138
139 pstX = (LosRbNode *)pstData;
140 /* NilT is forbidden. */
141 (pstTree->ulNodes)++;
142 while (LOS_RB_RED == pstX->pstParent->lColor) {
143 pstParent = pstX->pstParent;
144 pstGParent = pstParent->pstParent;
145
146 if (pstParent == pstGParent->pstLeft) {
147 pstY = pstGParent->pstRight;
148 if (LOS_RB_RED == pstY->lColor) {
149 pstY->lColor = LOS_RB_BLACK;
150 pstParent->lColor = LOS_RB_BLACK;
151 pstGParent->lColor = LOS_RB_RED;
152 pstX = pstGParent;
153 continue;
154 }
155
156 if (pstParent->pstRight == pstX) {
157 pstX = pstParent;
158 OsRbLeftRotateNode(pstTree, pstX);
159 }
160
161 pstX->pstParent->lColor = LOS_RB_BLACK;
162 pstGParent->lColor = LOS_RB_RED;
163 OsRbRightRotateNode(pstTree, pstGParent);
164 } else {
165 pstY = pstGParent->pstLeft;
166 if (LOS_RB_RED == pstY->lColor) {
167 pstY->lColor = LOS_RB_BLACK;
168 pstParent->lColor = LOS_RB_BLACK;
169 pstGParent->lColor = LOS_RB_RED;
170 pstX = pstGParent;
171 continue;
172 }
173
174 if (pstParent->pstLeft == pstX) {
175 pstX = pstParent;
176 OsRbRightRotateNode(pstTree, pstX);
177 }
178
179 pstX->pstParent->lColor = LOS_RB_BLACK;
180 pstGParent->lColor = LOS_RB_RED;
181 OsRbLeftRotateNode(pstTree, pstGParent);
182 }
183 }
184
185 pstTree->pstRoot->lColor = LOS_RB_BLACK;
186
187 return;
188 }
189
OsRbDeleteNodeFixup(LosRbTree * pstTree,LosRbNode * pstNode)190 STATIC VOID OsRbDeleteNodeFixup(LosRbTree *pstTree, LosRbNode *pstNode)
191 {
192 LosRbNode *pstW = NULL;
193
194 if (NULL == pstTree || NULL == pstNode) {
195 return;
196 }
197 while ((pstNode != pstTree->pstRoot) && (LOS_RB_BLACK == pstNode->lColor)) {
198 if (pstNode->pstParent->pstLeft == pstNode) {
199 pstW = pstNode->pstParent->pstRight;
200 if (LOS_RB_RED == pstW->lColor) {
201 pstW->lColor = LOS_RB_BLACK;
202 pstNode->pstParent->lColor = LOS_RB_RED;
203 OsRbLeftRotateNode(pstTree, pstNode->pstParent);
204 pstW = pstNode->pstParent->pstRight;
205 }
206
207 if ((LOS_RB_BLACK == pstW->pstLeft->lColor) && (LOS_RB_BLACK == pstW->pstRight->lColor)) {
208 pstW->lColor = LOS_RB_RED;
209 pstNode = pstNode->pstParent;
210 } else {
211 if (LOS_RB_BLACK == pstW->pstRight->lColor) {
212 pstW->pstLeft->lColor = LOS_RB_BLACK;
213 pstW->lColor = LOS_RB_RED;
214 OsRbRightRotateNode(pstTree, pstW);
215 pstW = pstNode->pstParent->pstRight;
216 }
217 pstW->lColor = pstNode->pstParent->lColor;
218 pstNode->pstParent->lColor = LOS_RB_BLACK;
219 pstW->pstRight->lColor = LOS_RB_BLACK;
220 OsRbLeftRotateNode(pstTree, pstNode->pstParent);
221 pstNode = pstTree->pstRoot;
222 }
223 } else {
224 pstW = pstNode->pstParent->pstLeft;
225 if (LOS_RB_RED == pstW->lColor) {
226 pstW->lColor = LOS_RB_BLACK;
227 pstNode->pstParent->lColor = LOS_RB_RED;
228 OsRbRightRotateNode(pstTree, pstNode->pstParent);
229 pstW = pstNode->pstParent->pstLeft;
230 }
231 if ((LOS_RB_BLACK == pstW->pstLeft->lColor) && (LOS_RB_BLACK == pstW->pstRight->lColor)) {
232 pstW->lColor = LOS_RB_RED;
233 pstNode = pstNode->pstParent;
234 } else {
235 if (LOS_RB_BLACK == pstW->pstLeft->lColor) {
236 pstW->pstRight->lColor = LOS_RB_BLACK;
237 pstW->lColor = LOS_RB_RED;
238 OsRbLeftRotateNode(pstTree, pstW);
239 pstW = pstNode->pstParent->pstLeft;
240 }
241 pstW->lColor = pstNode->pstParent->lColor;
242 pstNode->pstParent->lColor = LOS_RB_BLACK;
243 pstW->pstLeft->lColor = LOS_RB_BLACK;
244 OsRbRightRotateNode(pstTree, pstNode->pstParent);
245 pstNode = pstTree->pstRoot;
246 }
247 }
248 }
249 pstNode->lColor = LOS_RB_BLACK;
250 if (0 == pstTree->ulNodes) {
251 OsRbClearTree(pstTree);
252 }
253
254 return;
255 }
256
OsRbDeleteNode(LosRbTree * pstTree,VOID * pstData)257 STATIC VOID OsRbDeleteNode(LosRbTree *pstTree, VOID *pstData)
258 {
259 LosRbNode *pstChild = NULL;
260 LosRbNode *pstDel = NULL;
261 ULONG_T lColor;
262 LosRbWalk *pstWalk = NULL;
263 LosRbNode *pstNilT = NULL;
264 LosRbNode *pstZ = NULL;
265 LOS_DL_LIST *pstNode = NULL;
266
267 if ((NULL == pstTree) || (NULL == pstData)) {
268 return;
269 }
270
271 pstZ = (LosRbNode *)pstData;
272 pstNilT = &(pstTree->stNilT);
273
274 /* NilT is forbidden. */
275 if (!RB_IS_NOT_NILT(pstZ)) {
276 return;
277 }
278
279 /* check whether the Node is in a tree */
280 if ((pstZ->pstParent == pstNilT) && (pstZ->pstLeft == pstNilT) && (pstZ->pstRight == pstNilT) &&
281 (pstTree->pstRoot != pstZ)) {
282 return;
283 }
284
285 (pstTree->ulNodes)--;
286
287 if (!LOS_ListEmpty(&pstTree->stWalkHead)) {
288 LOS_DL_LIST_FOR_EACH(pstNode, &pstTree->stWalkHead)
289 {
290 pstWalk = LOS_DL_LIST_ENTRY(pstNode, LosRbWalk, stLink);
291 if (pstWalk->pstCurrNode == pstZ) {
292 pstWalk->pstCurrNode = LOS_RbSuccessorNode(pstTree, pstZ);
293 }
294 }
295 }
296
297 if ((pstNilT == pstZ->pstLeft) || (pstNilT == pstZ->pstRight)) {
298 pstChild = ((pstNilT != pstZ->pstLeft) ? pstZ->pstLeft : pstZ->pstRight);
299 if (NULL == pstChild) { /* Edit by r60958 for Coverity */
300 return;
301 }
302
303 pstChild->pstParent = pstZ->pstParent;
304
305 if (pstNilT == pstZ->pstParent) {
306 pstTree->pstRoot = pstChild;
307 } else {
308 if (pstZ->pstParent->pstLeft == pstZ) {
309 pstZ->pstParent->pstLeft = pstChild;
310 } else {
311 pstZ->pstParent->pstRight = pstChild;
312 }
313 }
314
315 if (LOS_RB_BLACK == pstZ->lColor) {
316 OsRbDeleteNodeFixup(pstTree, pstChild);
317 }
318
319 /* re-initialize the pstZ */
320 pstZ->lColor = LOS_RB_RED;
321 pstZ->pstLeft = pstZ->pstRight = pstZ->pstParent = pstNilT;
322
323 return;
324 }
325
326 /* Here is some different with book "Introduction to Algorithms,
327 * Second Edition", book's arithmetic won't delete pstZ, and it deletes
328 * pstZ's successor node instead. But we delete pstZ because
329 * our data structure has no internal node. So code is some complex.
330 */
331 pstDel = pstZ;
332
333 /* Get pstZ's successor node */
334 pstZ = pstZ->pstRight;
335 while (pstNilT != pstZ->pstLeft) {
336 pstZ = pstZ->pstLeft;
337 }
338
339 /* Because left is nilT, so child must be right. */
340 pstChild = pstZ->pstRight;
341 if (NULL == pstChild) { /* Edit by r60958 for Coverity */
342 return;
343 }
344
345 lColor = pstZ->lColor;
346
347 /* Remove successor node out of tree. */
348 pstChild->pstParent = pstZ->pstParent;
349
350 if (pstNilT == pstZ->pstParent) {
351 /* In fact, we never go here. */
352 pstTree->pstRoot = pstChild;
353 } else {
354 if (pstZ->pstParent->pstLeft == pstZ) {
355 pstZ->pstParent->pstLeft = pstChild;
356 } else {
357 pstZ->pstParent->pstRight = pstChild;
358 }
359 }
360
361 /* Insert successor node into tree and remove pstZ out of tree. */
362 pstZ->pstParent = pstDel->pstParent;
363 pstZ->lColor = pstDel->lColor;
364 pstZ->pstRight = pstDel->pstRight;
365 pstZ->pstLeft = pstDel->pstLeft;
366
367 if (pstNilT == pstDel->pstParent) {
368 /* if we arrive here, pstTree is no NULL */
369 pstTree->pstRoot = pstZ;
370 } else {
371 if (pstDel->pstParent->pstLeft == pstDel) {
372 pstDel->pstParent->pstLeft = pstZ;
373 } else {
374 pstDel->pstParent->pstRight = pstZ;
375 }
376 }
377
378 pstDel->pstLeft->pstParent = pstZ;
379 pstDel->pstRight->pstParent = pstZ;
380
381 if (LOS_RB_BLACK == lColor) {
382 OsRbDeleteNodeFixup(pstTree, pstChild);
383 }
384
385 /* re-initialize the pstDel */
386 pstDel->lColor = LOS_RB_RED;
387 pstDel->pstLeft = pstDel->pstRight = pstDel->pstParent = pstNilT;
388 return;
389 }
390
391
OsRbInitTree(LosRbTree * pstTree)392 STATIC VOID OsRbInitTree(LosRbTree *pstTree)
393 {
394 if (NULL == pstTree) {
395 return;
396 }
397
398 pstTree->ulNodes = 0;
399 pstTree->pstRoot = &(pstTree->stNilT);
400 pstTree->stNilT.lColor = LOS_RB_BLACK;
401 pstTree->stNilT.pstLeft = NULL; /* Always NULL */
402 pstTree->stNilT.pstRight = NULL; /* Always NULL */
403 pstTree->stNilT.pstParent = NULL; /* Not NULL when tree isn't empty */
404 LOS_ListInit(&pstTree->stWalkHead);
405
406 pstTree->pfCmpKey = NULL;
407 pstTree->pfFree = NULL;
408 pstTree->pfGetKey = NULL;
409
410 return;
411 }
412
OsRbClearTree(LosRbTree * pstTree)413 STATIC VOID OsRbClearTree(LosRbTree *pstTree)
414 {
415 LosRbWalk *pstWalk = NULL;
416 LOS_DL_LIST *pstNode = NULL;
417
418 if (NULL == pstTree) {
419 return;
420 }
421
422 pstNode = LOS_DL_LIST_FIRST(&pstTree->stWalkHead);
423 while (!LOS_DL_LIST_IS_END(&pstTree->stWalkHead, pstNode)) {
424 pstWalk = LOS_DL_LIST_ENTRY(pstNode, LosRbWalk, stLink);
425 pstWalk->pstCurrNode = NULL;
426 pstWalk->pstTree = NULL;
427
428 LOS_ListDelete(pstNode);
429 pstNode = LOS_DL_LIST_FIRST(&pstTree->stWalkHead);
430 }
431
432 return;
433 }
434
LOS_RbCreateWalk(LosRbTree * pstTree)435 LosRbWalk *LOS_RbCreateWalk(LosRbTree *pstTree)
436 {
437 LosRbNode *pstNode = NULL;
438 LosRbWalk *pstWalk = NULL;
439
440 if (NULL == pstTree) {
441 return NULL;
442 }
443
444 pstNode = LOS_RbFirstNode(pstTree);
445 if (NULL == pstNode) {
446 return NULL;
447 }
448
449 pstWalk = (LosRbWalk *)LOS_MemAlloc(m_aucSysMem0, sizeof(LosRbWalk));
450 if (NULL == pstWalk) {
451 return NULL;
452 }
453
454 LOS_ListAdd(&pstTree->stWalkHead, &pstWalk->stLink);
455 pstWalk->pstCurrNode = pstNode;
456 pstWalk->pstTree = pstTree;
457 return pstWalk;
458 }
459
LOS_RbWalkNext(LosRbWalk * pstWalk)460 VOID *LOS_RbWalkNext(LosRbWalk *pstWalk)
461 {
462 LosRbNode *pstNode = NULL;
463
464 /*
465 * Here, in the previous code, we didn't check pstCurrNode
466 * pstTree, but in some circumstance, we will delete a tree
467 * (by calling function RB_ClearTree), meanwhile, we will
468 * evaluate pstCurrNode and pstTree to NULL, but at present,
469 * if we are walking groups and ports, then we will call this
470 * function(LOS_RbWalkNext), but the tree has been deleted already
471 */
472 if ((NULL == pstWalk) || (NULL == pstWalk->pstCurrNode) || (NULL == pstWalk->pstTree)) {
473 return NULL;
474 }
475
476 pstNode = pstWalk->pstCurrNode;
477 pstWalk->pstCurrNode = LOS_RbSuccessorNode(pstWalk->pstTree, pstNode);
478 return pstNode;
479 }
480
LOS_RbDeleteWalk(LosRbWalk * pstWalk)481 VOID LOS_RbDeleteWalk(LosRbWalk *pstWalk)
482 {
483 if (NULL == pstWalk) {
484 return;
485 }
486
487 if (LOS_DL_LIST_IS_ON_QUEUE(&pstWalk->stLink)) {
488 LOS_ListDelete(&pstWalk->stLink);
489 }
490 pstWalk->pstCurrNode = NULL;
491 pstWalk->pstTree = NULL;
492 LOS_MemFree(m_aucSysMem0, pstWalk);
493
494 return;
495 }
496
LOS_RbInsertOneNodeProcess(LosRbTree * pstTree,LosRbNode * pstParent,LosRbNode * pstNew)497 VOID LOS_RbInsertOneNodeProcess(LosRbTree *pstTree, LosRbNode *pstParent, LosRbNode *pstNew)
498 {
499 LosRbNode *pstNilT = &pstTree->stNilT;
500 VOID *pNodeKey = NULL;
501 VOID *pKey = NULL;
502 ULONG_T ulCmpResult;
503
504 pstNew->lColor = LOS_RB_RED;
505 pstNew->pstLeft = pstNew->pstRight = pstNilT;
506 if ((pstNew->pstParent = pstParent) == pstNilT) {
507 pstTree->pstRoot = pstNew;
508 } else {
509 pNodeKey = pstTree->pfGetKey(pstNew);
510 pKey = pstTree->pfGetKey(pstParent);
511 ulCmpResult = pstTree->pfCmpKey(pNodeKey, pKey);
512 if (RB_SMALLER == ulCmpResult) {
513 pstParent->pstLeft = pstNew;
514 } else {
515 pstParent->pstRight = pstNew;
516 }
517 }
518
519 OsRbInsertNodeFixup(pstTree, pstNew);
520
521 return;
522 }
523
LOS_RbInitTree(LosRbTree * pstTree,pfRBCmpKeyFn pfCmpKey,pfRBFreeFn pfFree,pfRBGetKeyFn pfGetKey)524 VOID LOS_RbInitTree(LosRbTree *pstTree, pfRBCmpKeyFn pfCmpKey, pfRBFreeFn pfFree, pfRBGetKeyFn pfGetKey)
525 {
526 if (NULL == pstTree) {
527 return;
528 }
529
530 OsRbInitTree(pstTree);
531
532 pstTree->pfCmpKey = pfCmpKey;
533 pstTree->pfFree = pfFree;
534 pstTree->pfGetKey = pfGetKey;
535
536 return;
537 }
538
LOS_RbDestroyTree(LosRbTree * pstTree)539 VOID LOS_RbDestroyTree(LosRbTree *pstTree)
540 {
541 LosRbNode *pstNode = NULL;
542
543 if (NULL == pstTree) {
544 return;
545 }
546 if (NULL == pstTree->pfFree) {
547 return;
548 }
549
550 RB_WALK(pstTree, pstNode, pstWalk)
551 {
552 OsRbDeleteNode(pstTree, pstNode);
553 (VOID)pstTree->pfFree(pstNode);
554 }
555 RB_WALK_END(pstTree, pstNode, pstWalk);
556
557 OsRbClearTree(pstTree);
558
559 return;
560 }
561
LOS_RbFirstNode(LosRbTree * pstTree)562 VOID *LOS_RbFirstNode(LosRbTree *pstTree)
563 {
564 LosRbNode *pstNode = NULL;
565 LosRbNode *pstNilT = NULL;
566
567 if (NULL == pstTree) {
568 return NULL;
569 }
570
571 pstNode = pstTree->pstRoot;
572 if (pstNode == NULL) {
573 return NULL;
574 }
575 pstNilT = &(pstTree->stNilT);
576
577 if (pstNilT == pstNode) {
578 return NULL;
579 }
580
581 while (pstNilT != pstNode->pstLeft) {
582 pstNode = pstNode->pstLeft;
583 }
584
585 return pstNode;
586 }
587
LOS_RbSuccessorNode(LosRbTree * pstTree,VOID * pstData)588 VOID *LOS_RbSuccessorNode(LosRbTree *pstTree, VOID *pstData)
589 {
590 LosRbNode *pstY = NULL;
591 LosRbNode *pstNilT = NULL;
592 LosRbNode *pstNode = NULL;
593
594 if (NULL == pstTree) {
595 return NULL;
596 }
597
598 pstNode = (LosRbNode *)pstData;
599
600 if (NULL == pstNode) {
601 return NULL;
602 }
603
604 /* NilT is forbidden. */
605 if (!RB_IS_NOT_NILT(pstNode)) {
606 return NULL;
607 }
608
609 /* if we arrive here, pstTree is no NULL */
610 pstNilT = &(pstTree->stNilT);
611
612 if (pstNilT != pstNode->pstRight) {
613 pstNode = pstNode->pstRight;
614 while (pstNilT != pstNode->pstLeft) {
615 pstNode = pstNode->pstLeft;
616 }
617
618 return pstNode;
619 }
620
621 pstY = pstNode->pstParent;
622
623 while ((pstNilT != pstY) && (pstNode == pstY->pstRight)) {
624 pstNode = pstY;
625 pstY = pstY->pstParent;
626 }
627
628 return ((pstNilT == pstY) ? NULL : pstY);
629 }
630
LOS_RbGetNextNode(LosRbTree * pstTree,VOID * pKey)631 LosRbNode *LOS_RbGetNextNode(LosRbTree *pstTree, VOID *pKey)
632 {
633 LosRbNode *pNode = NULL;
634
635 if (TRUE == LOS_RbGetNode(pstTree, pKey, &pNode)) {
636 return LOS_RbSuccessorNode(pstTree, pNode);
637 } else if ((NULL == pNode) || (&pstTree->stNilT == pNode)) {
638 return NULL;
639 } else if (RB_BIGGER == pstTree->pfCmpKey(pKey, pstTree->pfGetKey(pNode))) {
640 while (NULL != pNode) {
641 pNode = LOS_RbSuccessorNode(pstTree, pNode);
642 if (NULL == pNode) {
643 return NULL;
644 }
645
646 if (RB_SMALLER == pstTree->pfCmpKey(pKey, pstTree->pfGetKey(pNode))) {
647 break;
648 }
649 }
650 return pNode;
651 } else {
652 return pNode;
653 }
654 }
655
LOS_RbGetNode(LosRbTree * pstTree,VOID * pKey,LosRbNode ** ppstNode)656 ULONG_T LOS_RbGetNode(LosRbTree *pstTree, VOID *pKey, LosRbNode **ppstNode)
657 {
658 LosRbNode *pstNilT = NULL;
659 LosRbNode *pstX = NULL;
660 LosRbNode *pstY = NULL;
661 VOID *pNodeKey = NULL;
662 ULONG_T ulCmpResult;
663
664 if ((NULL == pstTree) || (NULL == pKey) || (NULL == ppstNode)) {
665 if (NULL != ppstNode) {
666 *ppstNode = NULL;
667 }
668 return FALSE;
669 }
670 if ((NULL == pstTree->pfGetKey) || (NULL == pstTree->pfCmpKey)) {
671 *ppstNode = NULL;
672 return FALSE;
673 }
674
675 pstNilT = &pstTree->stNilT;
676 pstY = pstTree->pstRoot;
677 pstX = pstY;
678
679 while (pstX != pstNilT) {
680 pNodeKey = pstTree->pfGetKey(pstX);
681
682 ulCmpResult = pstTree->pfCmpKey(pKey, pNodeKey);
683 if (RB_EQUAL == ulCmpResult) {
684 *ppstNode = pstX;
685 return TRUE;
686 }
687 if (RB_SMALLER == ulCmpResult) {
688 pstY = pstX;
689 pstX = pstX->pstLeft;
690 } else {
691 pstY = pstX;
692 pstX = pstX->pstRight;
693 }
694 }
695
696 *ppstNode = pstY;
697 return FALSE;
698 }
699
LOS_RbDelNode(LosRbTree * pstTree,LosRbNode * pstNode)700 VOID LOS_RbDelNode(LosRbTree *pstTree, LosRbNode *pstNode)
701 {
702 OsRbDeleteNode(pstTree, pstNode);
703 }
704
LOS_RbAddNode(LosRbTree * pstTree,LosRbNode * pstNew)705 ULONG_T LOS_RbAddNode(LosRbTree *pstTree, LosRbNode *pstNew)
706 {
707 ULONG_T ulSearchNode;
708 VOID *pNodeKey = NULL;
709 LosRbNode *pstX = NULL;
710
711 if ((NULL == pstTree) || (NULL == pstNew)) {
712 return FALSE;
713 }
714 if ((NULL == pstTree->pfGetKey) || (NULL == pstTree->pfCmpKey)) {
715 return FALSE;
716 }
717
718 pNodeKey = pstTree->pfGetKey(pstNew);
719 ulSearchNode = LOS_RbGetNode(pstTree, pNodeKey, &pstX);
720 if (TRUE == ulSearchNode) {
721 return FALSE;
722 }
723
724 if (NULL == pstX) {
725 return FALSE;
726 }
727
728 LOS_RbInsertOneNodeProcess(pstTree, pstX, pstNew);
729
730 return TRUE;
731 }
732