1 /* 2 * This file is part of the openHiTLS project. 3 * 4 * openHiTLS is licensed under the Mulan PSL v2. 5 * You can use this software according to the terms and conditions of the Mulan PSL v2. 6 * You may obtain a copy of Mulan PSL v2 at: 7 * 8 * http://license.coscl.org.cn/MulanPSL2 9 * 10 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, 11 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, 12 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE. 13 * See the Mulan PSL v2 for more details. 14 */ 15 16 #ifndef AVL_H 17 #define AVL_H 18 19 #include "hitls_build.h" 20 #ifdef HITLS_BSL_ERR 21 22 #include <stdint.h> 23 24 #ifdef __cplusplus 25 extern "C" { 26 #endif 27 28 typedef void *BSL_ElementData; 29 30 typedef void (*BSL_AVL_DATA_FREE_FUNC)(BSL_ElementData data); 31 32 /* AVL tree node structure */ 33 typedef struct AvlTree { 34 uint32_t height; 35 uint64_t nodeId; 36 struct AvlTree *rightNode; 37 struct AvlTree *leftNode; 38 BSL_ElementData data; 39 } BSL_AvlTree; 40 41 /** 42 * @ingroup bsl_err 43 * @brief Create a tree node. 44 * 45 * @par Description: 46 * Create a tree node and set node data. 47 * 48 * @attention None 49 * @param data [IN] Data pointer of the tree node 50 * @retval BSL_AvlTree *curNode node returned after the application is successful. 51 * NULL application failed 52 */ 53 BSL_AvlTree *BSL_AVL_MakeLeafNode(BSL_ElementData data); 54 55 /** 56 * @ingroup bsl_err 57 * @brief Search for a node. 58 * 59 * @par Description: 60 * Query the node in the AVL tree by nodeId. 61 * 62 * @attention None 63 * @param root [IN] Pointer to the root node of the tree 64 * @param nodeId [IN] node ID of the tree, as the key 65 * @retval NULL No corresponding node is found. 66 * @retval not NULL Pointer to the corresponding node. 67 */ 68 BSL_AvlTree *BSL_AVL_SearchNode(BSL_AvlTree *root, uint64_t nodeId); 69 70 /** 71 * @ingroup bsl_err 72 * @brief Create a node in the tree. 73 * 74 * @par Description: 75 * Create a node in the tree. 76 * 77 * @attention If the nodeId already exists, the insertion fails. 78 * @param root [IN] Pointer to the root node of the tree. 79 * @param nodeId [IN] as the key of the created node 80 * @param node [IN] Tree node 81 * @retval The root node of a non-null tree or subtree 82 */ 83 BSL_AvlTree *BSL_AVL_InsertNode(BSL_AvlTree *root, uint64_t nodeId, BSL_AvlTree *node); 84 85 /** 86 * @ingroup bsl_err 87 * @brief Delete a specific tree node. 88 * 89 * @par Description: 90 * Delete the nodeId corresponding tree node. 91 * 92 * @attention None 93 * @param root [IN] Pointer to the root node of the tree. 94 * @param nodeId [IN] Key of the node to be deleted 95 * @param func [IN] Pointer to the function that releases the data of the deleted node. 96 * @retval NULL All nodes in the tree have been deleted. 97 * @retval not NULL Pointer to the root node of a tree or subtree. 98 */ 99 BSL_AvlTree *BSL_AVL_DeleteNode(BSL_AvlTree *root, uint64_t nodeId, BSL_AVL_DATA_FREE_FUNC func); 100 101 /** 102 * @ingroup bsl_err 103 * @brief Delete all nodes from the tree. 104 * 105 * @par Description: 106 * Delete all nodes in the tree. 107 * 108 * @attention None 109 * @param root [IN] Pointer to the root node of the tree 110 * @param func [IN] Pointer to the function that releases the data of the deleted node. 111 */ 112 void BSL_AVL_DeleteTree(BSL_AvlTree *root, BSL_AVL_DATA_FREE_FUNC func); 113 114 #ifdef __cplusplus 115 } 116 #endif 117 118 #endif /* HITLS_BSL_ERR */ 119 120 #endif // AVL_H