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 /** 17 * @defgroup bsl_list bidirectional linked list 18 * @ingroup bsl 19 */ 20 21 #ifndef BSL_HASH_LIST_H 22 #define BSL_HASH_LIST_H 23 24 #include "hitls_build.h" 25 #ifdef HITLS_BSL_HASH 26 27 #include <stdint.h> 28 #include <stdbool.h> 29 #include <stddef.h> 30 31 #ifdef __cplusplus 32 extern "C" { 33 #endif 34 35 /** 36 * @ingroup bsl_list 37 * @brief User data copy function prototype 38 * @attention Note: The source buffer length needs to be obtained by the caller. 39 * Because the data type and length are unknown, the hook function needs to be implemented by the service side. 40 * @param ptr [IN] Pointer to user data 41 * @param size [IN] User data copy length 42 * @retval Destination buffer. NULL indicates failure. 43 */ 44 typedef void *(*ListDupFunc)(void *ptr, size_t size); 45 46 /** 47 * @ingroup bsl_list 48 * @brief User memory release function prototype 49 * @par Description: resource release function prototype, which is generally used to release memory in batches. 50 * The memory may contain private resources, which need to be released by users. 51 * @param ptr [IN] Pointer to user data 52 * @retval None 53 */ 54 typedef void (*ListFreeFunc)(void *ptr); 55 56 /** 57 * @ingroup bsl_list 58 * @brief Match the function prototype. 59 * @par Description: used to match the query. 60 * @attention Note: Only the function prototype is defined here. Because the user query matching mechanism is unknown, 61 * the hook function needs to be implemented by the service side. 62 * @param node [IN] Algorithm structure node 63 * @param data [IN] Key information 64 * @retval true: Matching succeeded. 65 * @retval false Matching failure 66 */ 67 typedef bool (*ListMatchFunc)(const void *node, uintptr_t data); 68 69 /** 70 * @ingroup bsl_list 71 * @brief Compare function prototype 72 * @par Description: Compare function prototype, which is used in sorting. 73 * @attention Note: Only the comparison function prototype is defined here. The data type and length are unknown. 74 * Therefore, the hook function needs to be implemented by the service side. 75 * The current source code has a default comparison function. This function is not provided externally. 76 * If the default comparison method is not specified, it will be invoked. 77 * The comparison method is to convert the current data into a signed number for comparison, 78 * that is, to process the case with negative numbers in ascending order. 79 * If the data to be stored is of the unsigned integer type, The sorting result may not be expected at this time. 80 * To compare data in this case, we need to customize the comparison function. 81 * For example, for a BIGNUM A = uintptr_t(-1) and a BIGNUM B = 1ULL << 50, the current function considers A < B. 82 * Actually, A is greater than B. 83 * To sum up, the user should write the comparison function based on the data type 84 * (including descending order or other comparison rules). 85 */ 86 typedef int32_t (*ListKeyCmpFunc)(uintptr_t key1, uintptr_t key2); 87 88 /** 89 * @ingroup bsl_list 90 * @brief Hook for saving memory application and release. 91 */ 92 typedef struct { 93 ListDupFunc dupFunc; 94 ListFreeFunc freeFunc; 95 } ListDupFreeFuncPair; 96 97 /** 98 * @ingroup bsl_list 99 * list header 100 */ 101 typedef struct BslListSt BSL_List; 102 103 /** 104 * @ingroup bsl_list 105 * Linked list iterator (node) definition 106 */ 107 typedef struct BslListNodeSt *BSL_ListIterator; 108 109 /** 110 * @ingroup bsl_list 111 * @brief Initialize the linked list. 112 * @par Description: Initialize the linked list and 113 * register the user data dup function and user data resource free function as required. 114 * @attention 115 * 1. If the data to be stored is of the integer type and the length <= sizeof(uintptr_t), 116 * do not need to register dataFunc&dupFunc and assign it empty. 117 * 2. If the user data is string or other customized complex data type 118 * and the data life cycle is shorter than the node life cycle, user must register dataFunc->dupFunc for data copy. 119 * @param list [IN] Linked list 120 * @param dataFunc [IN] User data copy and release function pair. If dataFunc and dupFunc are not registered, 121 * the default data type is integer. 122 * @retval #BSL_SUCCESS 0 indicates that the linked list is successfully initialized. 123 */ 124 int32_t BSL_ListInit(BSL_List *list, const ListDupFreeFuncPair *dataFunc); 125 126 /** 127 * @ingroup bsl_list 128 * @brief Clear the node in the linked list and delete all nodes. 129 * @par Description: Clear the linked list node, delete all nodes, invoke the free function registered by the user 130 * to release user resources, and return to the status after initialization of the linked list. 131 * @param list [IN] Linked list 132 * @retval #BSL_SUCCESS 0. The linked list is cleared successfully. 133 */ 134 int32_t BSL_ListClear(BSL_List *list); 135 136 /** 137 * @ingroup bsl_list 138 * @brief Deinitialize the linked list. 139 * @par Description: Deinitialize the linked list: Delete all nodes, 140 * invoke the free function registered by the user to release user resources, and deregister the hook function. 141 * @param list [IN] Linked list 142 * @retval #BSL_SUCCESS 0. The linked list is successfully de-initialized. 143 */ 144 int32_t BSL_ListDeinit(BSL_List *list); 145 146 /** 147 * @ingroup bsl_list 148 * @brief Check whether the linked list is empty. 149 * @param list [IN] Linked list to be checked 150 * @retval #true 1: The linked list is null or no data exists. 151 * @retval #false 0: The linked list is not empty. 152 * @li bsl_list.h: header file where the API declaration is located. 153 */ 154 bool BSL_ListIsEmpty(const BSL_List *list); 155 156 /** 157 * @ingroup bsl_list 158 * @brief Obtain the number of nodes in the linked list. 159 * @param list [IN] Linked list 160 * @retval Number of linked list nodes 161 * @li bsl_list.h: header file where the API declaration is located. 162 */ 163 size_t BSL_ListSize(const BSL_List *list); 164 165 /** 166 * @ingroup bsl_list 167 * @brief Insert user data into the header of the linked list. 168 * @param list [IN] Linked list 169 * @param userData [IN] Data to be inserted or pointer to user private data 170 * @param userDataSize [IN] Data copy length. If the user has not registered the dupFunc, this parameter is not used. 171 * @retval #BSL_SUCCESS Data is successfully inserted. 172 * @li bsl_list.h: header file where this function declaration is located. 173 */ 174 int32_t BSL_ListPushFront(BSL_List *list, uintptr_t userData, size_t userDataSize); 175 176 /** 177 * @ingroup bsl_list 178 * @brief Insert user data to the end of the linked list. 179 * @param list [IN] Linked list 180 * @param userData [IN] Data to be inserted or pointer to user private data 181 * @param userDataSize [IN] Data copy length. If the user has not registered the dupFunc, this parameter is not used. 182 * @retval #BSL_SUCCESS Data is successfully inserted. 183 * @li bsl_list.h: header file where this function declaration is located. 184 */ 185 int32_t BSL_ListPushBack(BSL_List *list, uintptr_t userData, size_t userDataSize); 186 187 /** 188 * @ingroup bsl_list 189 * @brief POP a node from the header of the linked list. 190 * @par Description: Remove the head node from the linked list and release the node memory. 191 * If the free function is registered during initialization, the hook function is called to release private resources. 192 * If the linked list is empty, nothing will be done. 193 * @param list [IN] Linked list 194 * @retval #BSL_SUCCESS 0. The header is removed successfully. 195 * @li bsl_list.h: header file where the API declaration is located. 196 */ 197 int32_t BSL_ListPopFront(BSL_List *list); 198 199 /** 200 * @ingroup bsl_list 201 * @brief POP a node from the end of the linked list. 202 * @par Description: Remove the tail node from the linked list and release the node memory. 203 * If the free function is registered during initialization, the hook function is called to release private resources. 204 * If the linked list is empty, nothing will be done. 205 * @param list [IN] Linked list 206 * @retval #BSL_SUCCESS 0. The tail is removed successfully. 207 * @li bsl_list.h: header file where the API declaration is located. 208 */ 209 int32_t BSL_ListPopBack(BSL_List *list); 210 211 /** 212 * @ingroup bsl_list 213 * @brief Access the header node of the linked list and return the user data of the header node. 214 * @par Description: Access the header node of the linked list and return the user data of the header node. 215 * @attention Note: If the linked list is empty, 216 * it cannot be distinguished whether the linked list is empty and the returned data is 0. 217 * Therefore, before calling this function, we must check whether the linked list is empty. 218 * @param list [IN] Linked list 219 * @retval User data/pointer of the head node. If the linked list is empty, 0 is returned. 220 * @li bsl_list.h: header file where this function declaration is located. 221 */ 222 uintptr_t BSL_ListFront(const BSL_List *list); 223 224 /** 225 * @ingroup bsl_list 226 * @brief Access the tail node of the linked list and return the user data of the tail node. 227 * @attention Note: If the linked list is empty, 228 * it cannot be distinguished whether the linked list is empty and the returned data is 0. 229 * Therefore, we must check whether the linked list is empty before calling this function. 230 * @param list [IN] Linked list 231 * @retval User data/pointer of the tail node. If the linked list is empty, 0 is returned. 232 * @li bsl_list.h: header file where the API declaration is located. 233 */ 234 uintptr_t BSL_ListBack(const BSL_List *list); 235 236 /** 237 * @ingroup bsl_list 238 * @brief Obtain the iterator of the header node of the linked list. 239 * @param list [IN] Linked list 240 * @retval Head node iterator of the linked list. If the linked list is empty, it points to the header. 241 * @li bsl_list.h: header file where this function declaration is located. 242 */ 243 BSL_ListIterator BSL_ListIterBegin(const BSL_List *list); 244 245 /** 246 * @ingroup bsl_list 247 * @brief Obtain the iterator of the next node of the tail. 248 * @param list [IN] Linked list 249 * @attention If the input list is NULL, NULL will be returned. Therefore, user need to use correct parameters. 250 * @retval Next node iterator of the tail (pointing to the head of the linked list). 251 * @li bsl_list.h: header file where the API declaration is located. 252 */ 253 BSL_ListIterator BSL_ListIterEnd(BSL_List *list); 254 255 /** 256 * @ingroup bsl_list 257 * @brief Obtain the iterator of the previous node. 258 * @param list [IN] Linked list 259 * @param it [IN] Iterator 260 * @attention If the input list is NULL or iterator it is not a valid part of the list, NULL is returned. 261 * Therefore, user need to use the correct parameter. 262 * @retval list is not empty, return the previous node iterator. 263 * @retval list is NULL, and NULL is returned. 264 * @li bsl_list.h: header file where the API declaration is located. 265 */ 266 BSL_ListIterator BSL_ListIterPrev(const BSL_List *list, const BSL_ListIterator it); 267 268 /** 269 * @ingroup bsl_list 270 * @brief Obtain the iterator of the next node. 271 * @param list [IN] Linked list 272 * @param it [IN] Iterator 273 * @attention If the input list is NULL or iterator it is not a valid part of the list, NULL is returned. 274 * Therefore, user need to use the correct parameter. 275 * @retval Returns the iterator of the next node if the value is not null. 276 * @retval list is NULL, and NULL is returned. 277 * @li bsl_list.h: header file where the API declaration is located. 278 */ 279 BSL_ListIterator BSL_ListIterNext(const BSL_List *list, const BSL_ListIterator it); 280 281 /** 282 * @ingroup bsl_list 283 * @brief Insert data before the node pointed to by the specified iterator. 284 * @param list [IN] Linked list 285 * @param it [IN] Current iterator position 286 * @param userData [IN] Data to be inserted or pointer to user private data 287 * @param userDataSize [IN] Data copy length. If the user has not registered the dupFunc, this parameter is not used. 288 * @retval #BSL_SUCCESS Data is successfully inserted. 289 * @li bsl_list.h: header file where this function declaration is located. 290 */ 291 int32_t BSL_ListInsert(BSL_List *list, const BSL_ListIterator it, uintptr_t userData, size_t userDataSize); 292 293 /** 294 * @ingroup bsl_list 295 * @brief Delete a specified node from the linked list and release the node memory. 296 * @par Description: Delete the specified node from the linked list and release the node memory. 297 * If the free function is registered during initialization, 298 * the hook function is invoked to release private resources such as handles and pointers in user data 299 * @attention If the input list is NULL or iterator it is not a valid part of the list, NULL is returned. 300 * Therefore, user need to use the correct parameter. 301 * @param list [IN] Linked list 302 * @param it [IN] Iterator of the node to be deleted. 303 * @retval Next node iterator of the deleted node. If the deleted node is the tail node, 304 * the returned iterator points to the header of the linked list. 305 * @li bsl_list.h: header file where this function declaration is located. 306 */ 307 BSL_ListIterator BSL_ListIterErase(BSL_List *list, BSL_ListIterator it); 308 309 /** 310 * @ingroup bsl_list 311 * @brief Obtain user data. 312 * @attention The caller must ensure the validity of the parameter. If the input parameter is invalid, 0 is returned. 313 * The caller cannot distinguish whether the returned value 0 is normal data 314 * or whether the returned value is 0 due to invalid parameters. 315 * @param it [IN] Linked list iterator 316 * @retval User data 317 * @li bsl_list.h: header file where this function declaration is located. 318 */ 319 uintptr_t BSL_ListIterData(const BSL_ListIterator it); 320 321 /** 322 * @ingroup bsl_list 323 * @brief Searches for the desired iterator, that is, the node pointer, 324 * based on the user-defined iterator matching function. 325 * @par Description: Searches for the desired iterator, that is, the node pointer, 326 * based on the user-defined iterator matching function. 327 * @attention 328 * 1. Traversefrom the header and call the matching function for each node in turn 329 * until the first matching node is found or the traversal ends at the tail of the linked list. 330 * 2. The first input parameter address of the matching function hook entered by the user 331 * is the userdata of each node to be searched. The input parameter type is uintptr_t. 332 * 3. If the input list is NULL or the comparison function is NULL, NULL is returned. 333 * Therefore, user need to use correct parameters. 334 * @param list [IN] Linked list 335 * @param iterCmpFunc [IN] Hook of match function. 336 * @param data [IN] Data information 337 * @retval not NULL Query succeeded, the matching node iterator is returned. 338 * @retval NULL Query failed. 339 * @li bsl_list.h: header file where this function declaration is located. 340 */ 341 BSL_ListIterator BSL_ListIterFind(BSL_List *list, ListKeyCmpFunc iterCmpFunc, uintptr_t data); 342 343 #ifdef __cplusplus 344 } 345 #endif 346 347 #endif /* HITLS_BSL_HASH */ 348 349 #endif // BSL_HASH_LIST_H 350