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 #ifndef _LOS_RBTREE_H 38 #define _LOS_RBTREE_H 39 40 #include "los_list.h" 41 42 #ifdef __cplusplus 43 #if __cplusplus 44 extern "C" { 45 #endif /* __cplusplus */ 46 #endif /* __cplusplus */ 47 48 #define LOS_RB_RED 0 49 #define LOS_RB_BLACK 1 50 51 typedef struct TagRbNode { 52 struct TagRbNode *pstParent; 53 struct TagRbNode *pstRight; 54 struct TagRbNode *pstLeft; 55 ULONG_T lColor; 56 } LosRbNode; 57 58 typedef ULONG_T (*pfRBCmpKeyFn)(const VOID *, const VOID *); 59 typedef ULONG_T (*pfRBFreeFn)(LosRbNode *); 60 typedef VOID *(*pfRBGetKeyFn)(LosRbNode *); 61 62 typedef struct TagRbTree { 63 LosRbNode *pstRoot; 64 LosRbNode stNilT; 65 LOS_DL_LIST stWalkHead; 66 ULONG_T ulNodes; 67 68 pfRBCmpKeyFn pfCmpKey; 69 pfRBFreeFn pfFree; 70 pfRBGetKeyFn pfGetKey; 71 } LosRbTree; 72 73 typedef struct TagRbWalk { 74 LOS_DL_LIST stLink; 75 LosRbNode *pstCurrNode; 76 struct TagRbTree *pstTree; 77 } LosRbWalk; 78 79 #define RB_EQUAL (0) 80 #define RB_BIGGER (1) 81 #define RB_SMALLER (2) 82 83 #define RB_SCAN(pstTree, pstNode) do { \ 84 (pstNode) = LOS_RbFirstNode((pstTree)); \ 85 for (; NULL != (pstNode); (pstNode) = LOS_RbSuccessorNode((pstTree), (pstNode))) { 86 87 #define RB_SCAN_END(pstTree, pstNode) } \ 88 } \ 89 while (0); 90 91 #define RB_SCAN_SAFE(pstTree, pstNode, pstNodeTemp) do { \ 92 (pstNode) = LOS_RbFirstNode((pstTree)); \ 93 (pstNodeTemp) = LOS_RbSuccessorNode((pstTree), (pstNode)); \ 94 for (; NULL != (pstNode); (pstNode) = (pstNodeTemp), (pstNodeTemp) = LOS_RbSuccessorNode((pstTree), (pstNode))) { 95 96 #define RB_SCAN_SAFE_END(pstTree, pstNode, pstNodeTemp) } \ 97 } \ 98 while (0); 99 100 #define RB_MID_SCAN(pstTree, pstNode) do { \ 101 for (; NULL != (pstNode); (pstNode) = LOS_RbSuccessorNode((pstTree), (pstNode))) { 102 103 #define RB_MID_SCAN_END(pstTree, pstNode) } \ 104 } \ 105 while (0); 106 107 #define RB_WALK(pstTree, pstNode, pstRbWalk) do { \ 108 LosRbWalk *(pstRbWalk) = NULL; \ 109 pstRbWalk = LOS_RbCreateWalk(pstTree); \ 110 (pstNode) = LOS_RbWalkNext(pstRbWalk); \ 111 for (; NULL != (pstNode); (pstNode) = LOS_RbWalkNext(pstRbWalk)) { 112 113 #define RB_WALK_END(pstTree, pstNode, pstRbWalk) } \ 114 LOS_RbDeleteWalk(pstRbWalk); \ 115 } \ 116 while (0); 117 118 #define RB_WALK_TERMINATE(pstRbWalk) LOS_RbDeleteWalk(pstRbWalk); 119 #define RB_COUNT(pstTree) ((pstTree)->ulNodes) 120 #define RB_IS_NOT_NILT(pstX) ((NULL != (pstX)->pstLeft) && (NULL != (pstX)->pstRight)) 121 122 VOID *LOS_RbFirstNode(LosRbTree *pstTree); 123 VOID *LOS_RbSuccessorNode(LosRbTree *pstTree, VOID *pstData); 124 VOID LOS_RbInitTree(LosRbTree *pstTree, pfRBCmpKeyFn pfCmpKey, pfRBFreeFn pfFree, pfRBGetKeyFn pfGetKey); 125 VOID LOS_RbDestroyTree(LosRbTree *pstTree); 126 LosRbNode *LOS_RbGetNextNode(LosRbTree *pstTree, VOID *pKey); 127 ULONG_T LOS_RbGetNode(LosRbTree *pstTree, VOID *pKey, LosRbNode **ppstNode); 128 VOID LOS_RbDelNode(LosRbTree *pstTree, LosRbNode *pstNode); 129 ULONG_T LOS_RbAddNode(LosRbTree *pstTree, LosRbNode *pstNew); 130 131 /* Following 3 functions support protection walk. */ 132 LosRbWalk *LOS_RbCreateWalk(LosRbTree *pstTree); 133 VOID *LOS_RbWalkNext(LosRbWalk *pstWalk); 134 VOID LOS_RbDeleteWalk(LosRbWalk *pstWalk); 135 136 #ifdef __cplusplus 137 #if __cplusplus 138 } 139 #endif /* __cplusplus */ 140 #endif /* __cplusplus */ 141 142 #endif /* _LOS_RBTREE_H */ 143