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_hash hash table 18 * @ingroup bsl 19 */ 20 21 #ifndef BSL_HASH_H 22 #define BSL_HASH_H 23 24 #include "hitls_build.h" 25 #ifdef HITLS_BSL_HASH 26 27 #include <stdlib.h> 28 #include <stdbool.h> 29 #include <stdint.h> 30 #include "bsl_hash_list.h" 31 32 #ifdef __cplusplus 33 extern "C" { 34 #endif 35 36 /** 37 * @ingroup bsl_hash 38 * @brief Handle of the hash table, which indicates the elements contained in the hash table. 39 */ 40 typedef struct BSL_HASH_Info BSL_HASH_Hash; 41 42 /** 43 * @ingroup bsl_hash 44 * @brief Definition of the iterator of the hash table, pointing to the hash node. 45 */ 46 typedef struct BSL_HASH_TagNode *BSL_HASH_Iterator; 47 48 /** 49 * @ingroup bsl_hash 50 * @brief Generates a hash table index based on the entered key. 51 * @param key [IN] hash key 52 * @param bktSize [IN] hash bucket size 53 */ 54 typedef uint32_t (*BSL_HASH_CodeCalcFunc)(uintptr_t key, uint32_t bktSize); 55 56 /** 57 * @ingroup bsl_hash 58 * @brief This function is used to match the input data with the key. 59 * Key1 stored in the hash table, and the key2 to be matched. If no, false is returned. 60 * @param key1 [IN] Key stored in the hash table 61 * @param key2 [IN] Key to be matched 62 * @retval #true key1 matches key2. 63 * @retval #false key1 and key2 do not match. 64 */ 65 typedef bool (*BSL_HASH_MatchFunc)(uintptr_t key1, uintptr_t key2); 66 67 /** 68 * @ingroup bsl_hash 69 * @brief Function for updating a node in the hash table. 70 * @par Description: This function is used to update the value of an existing node in the hash table. 71 * @attention 72 * 1. This function is called when a key already exists in the hash table and needs to be updated. 73 * 2. The user can provide a custom implementation of this function to handle specific update logic. 74 * @param hash [IN] Handle of the hash table. 75 * @param node [IN] Pointer to the node to be updated. 76 * @param value [IN] New value or address for storing the new value. 77 * @param valueSize [IN] Size of the new value. If the user has not registered a dupFunc, this parameter is not used. 78 * @retval #BSL_SUCCESS The node was successfully updated. 79 * @retval #BSL_INTERNAL_EXCEPTION Failed to update the node. 80 * @par Dependency: None 81 * @li bsl_hash.h: Header file where this function type is declared. 82 */ 83 typedef int32_t (*BSL_HASH_UpdateNodeFunc)(BSL_HASH_Hash *hash, BSL_HASH_Iterator node, 84 uintptr_t value, uint32_t valueSize); 85 86 /** 87 * @ingroup bsl_hash 88 * @brief Hash function. 89 * @par Description: Calculate the hash value based on the key value. 90 * The hash value does not modulate the size of the hash table and cannot be directly used for hash indexing. 91 * @attention 92 * 1. The key is the input parameter when the user invokes other interfaces. 93 * 2. If the key is an integer, you can use this function as the hashFunc parameter when creating a hash. 94 * @param key [IN] Key to be calculated. 95 * @param keySize [IN] Size of the key value. 96 * @retval #Hash value calculated based on the user key. The hash value is not modulated by the hash table size 97 * and cannot be directly used for hash indexing. 98 * @par Dependency: None 99 * @li bsl_hash.h: header file where this function's declaration is located. 100 */ 101 uint32_t BSL_HASH_CodeCalc(void *key, uint32_t keySize); 102 103 /** 104 * @ingroup bsl_hash 105 * @brief Default integer hash function. 106 * @par Default integer hash function. 107 * @attention 108 * 1. The key parameter is the input parameter when the user invokes other interfaces. 109 * 2. If the key is an integer, you can use this function as the hashFunc parameter when creating a hash. 110 * @param key [IN] Key to be calculated. 111 * @param bktSize [IN] Hash bucket size. 112 * @retval #Hash value calculated based on the user key. 113 * @par Dependency: None 114 * @li bsl_hash.h: header file where this function's declaration is located. 115 */ 116 uint32_t BSL_HASH_CodeCalcInt(uintptr_t key, uint32_t bktSize); 117 118 /** 119 * @ingroup bsl_hash 120 * @brief Default string hash function. 121 * @par Default string hash function. 122 * @attention 123 * 1. The key is an input parameter when the user invokes other interfaces. 124 * Ensure that the input key is a valid string start address. 125 * 2. If the key is a string, you can use this function as the hashFunc parameter when creating a hash. 126 * @param key [IN] Key to be calculated. 127 * @param bktSize [IN] Hash bucket size. 128 * @retval #Hash valueThe hash value calculated based on the user key. 129 * @par Dependency: None 130 * @li bsl_hash.h: header file where this function's declaration is located. 131 */ 132 uint32_t BSL_HASH_CodeCalcStr(uintptr_t key, uint32_t bktSize); 133 134 /** 135 * @ingroup bsl_hash 136 * @brief Default integer matching function. 137 * @par Default integer matching function. 138 * @attention 139 * 1. The key is the input parameter when the user invokes other interfaces. 140 * 2. If the key is an integer, you can use this function as the matchFunc parameter when creating a hash. 141 * @param key1 [IN] Key to be matched. 142 * @param key2 [IN] Key to be matched. 143 * @retval #true key1 matches key2. 144 * @retval #false key1 and key2 do not match. 145 * @par Dependency: None 146 * @li bsl_hash.h: header file where this function's declaration is located. 147 */ 148 bool BSL_HASH_MatchInt(uintptr_t key1, uintptr_t key2); 149 150 /** 151 * @ingroup bsl_hash 152 * @brief Default string matching function. 153 * @par Default string matching function. 154 * @attention 155 * 1. Key1 is the input parameter when the user invokes other interfaces. 156 * Ensure that the input key1 is a valid string start address. 157 * 2. If the key is a string, you can use this function as the matchFunc parameter when creating the hash. 158 * @param key1 [IN] Key to be matched. 159 * @param key2 [IN] Key to be matched. 160 * @retval #true key1 matches key2. 161 * @retval #false key1 and key2 do not match. 162 * @par Dependency: None 163 * @li bsl_hash.h: header file where this function's declaration is located. 164 */ 165 bool BSL_HASH_MatchStr(uintptr_t key1, uintptr_t key2); 166 167 /** 168 * @ingroup bsl_hash 169 * @brief Create a hash table and return the handle of the hash table. 170 * @attention 171 * 1. Copy functions for keys and data: 172 * You do not need to register the copy function in the following case: 173 * a) Data is the int type and the length <= sizeof(uintptr_t). 174 * The copy function must be registered in the following cases: 175 * a) Data is the int type, but the length is greater than sizeof(uintptr_t); 176 * b) string; 177 * c) User-defined data structure. 178 * 2. About the free function: Simply put, if the duplicate function is registered, 179 * the corresponding free function must be registered. 180 * 3. Provide the default integer and string hash functions: #BSL_HASH_CodeCalcInt and #BSL_HASH_CodeCalcStr. 181 * 4. Provide default integer and string matching functions: #BSL_HASH_MatchInt and #BSL_HASH_MatchStr. 182 * @param bktSize [IN] Number of hash buckets. 183 * @param hashCalcFunc [IN] Hash value calculation function. 184 * If the value is NULL, the default key is an integer. Use #BSL_HASH_CodeCalcInt. 185 * @param matchFunc [IN] hash key matching function. 186 * If the value is NULL, the default key is an integer. Use #BSL_HASH_MatchInt. 187 * @param keyFunc [IN] hash key copy and release function pair. 188 * If the keyFunc->dupFunc is not registered, the key is an integer by default. 189 * @param valueFunc [IN] hash data copy and release function pair. 190 * If the user has not registered valueFunc->dupFunc, the data type is an integer by default. 191 * @retval hash table handle. NULL indicates that the creation fails. 192 * @par Dependency: None 193 * @see #BSL_HASH_CodeCalcInt, #BSL_HASH_CodeCalcStr, #BSL_HASH_MatchInt, #BSL_HASH_MatchStr. 194 * @li bsl_hash.h: header file where this function's declaration is located. 195 */ 196 BSL_HASH_Hash *BSL_HASH_Create(uint32_t bktSize, BSL_HASH_CodeCalcFunc hashFunc, BSL_HASH_MatchFunc matchFunc, 197 ListDupFreeFuncPair *keyFunc, ListDupFreeFuncPair *valueFunc); 198 199 /** 200 * @ingroup bsl_hash 201 * @brief Insert the hash data. 202 * @par Description: Create a node and insert data (key and value) into the hash table. 203 * @attention 204 * 1. Duplicate keys are not supported. 205 * 2. The key and value are integer values or addresses pointing to the user key or value. 206 * 3. If the life cycle of the extended data is shorter than the life cycle of the node, 207 * you need to register the copy function and release function when creating the hash table. 208 * @param hash [IN] handle of the hash table 209 * @param key [IN] key or address for storing the key 210 * @param keySize [IN] Copy length of key. If the user has not registered the dupFunc, this parameter is not used. 211 * @param value [IN] value or the address for storing the value. 212 * @param valueSize [IN] Copy length of value. If user has not registered the dupFunc, this parameter is not used. 213 * @retval #BSL_SUCCESS Succeeded in inserting the node. 214 * @retval #BSL_INTERNAL_EXCEPTION Insertion fails. 215 * @par Dependency: None 216 * @li bsl_hash.h: header file where this function's declaration is located. 217 */ 218 int32_t BSL_HASH_Insert(BSL_HASH_Hash *hash, uintptr_t key, uint32_t keySize, uintptr_t value, uint32_t valueSize); 219 220 /** 221 * @ingroup bsl_hash 222 * @brief Insert or update the hash data. 223 * @par Description: This function is used to insert a nonexistent key into the hash table 224 * or update the value corresponding to an existing key. 225 * @attention 226 * 1. Duplicate keys are supported. 227 * 2. When the key does not exist, the usage of this function is the same as that of #BSL_HASH_Insert. 228 * 3. When the key exists, this function updates the value. 229 * @param hash [IN] Handle of the hash table. 230 * @param key [IN] key or address for storing the key. 231 * @param keySize [IN] Copy length of key. If the user has not registered the dupFunc, this parameter is not used. 232 * @param value [IN] value or the address for storing the value. 233 * @param valueSize [IN] Copy length of value. If user has not registered the dupFunc, this parameter is not used. 234 * @param updateNodeFunc [IN] Callback function for updating a node. If NULL, the default update function will be used. 235 * This function allows custom logic for updating existing nodes. 236 * @retval #BSL_SUCCESS Succeeded in inserting or updating the node. 237 * @retval #BSL_INTERNAL_EXCEPTION Failed to insert or update the node. 238 * @par Dependency: None 239 * @li bsl_hash.h: header file where this function's declaration is located. 240 */ 241 int32_t BSL_HASH_Put(BSL_HASH_Hash *hash, uintptr_t key, uint32_t keySize, uintptr_t value, uint32_t valueSize, 242 BSL_HASH_UpdateNodeFunc updateNodeFunc); 243 244 /** 245 * @ingroup bsl_hash 246 * @brief Search for a node and return the node data. 247 * @par Description: Searches for and returns node data based on the key. 248 * @param hash [IN] Handle of the hash table. 249 * @param key [IN] key or address for storing the key. 250 * @param value [OUT] Data found. 251 * @retval #BSL_SUCCESS found successfully. 252 * @retval #BSL_INTERNAL_EXCEPTION query failed. 253 * @par Dependency: None 254 * @li bsl_hash.h: header file where this function's declaration is located. 255 */ 256 int32_t BSL_HASH_At(const BSL_HASH_Hash *hash, uintptr_t key, uintptr_t *value); 257 258 /** 259 * @ingroup bsl_hash 260 * @brief Search for the iterator where the key is located. 261 * @par Description: Searches for and returns the iterator where the key is located based on the key. 262 * @param hash [IN] Handle of the hash table. 263 * @param key [IN] key or address for storing the key. 264 * @retval If the key exists, the iterator (pointing to the address of the node) where the key is located is returned. 265 * In other cases, #BSL_HASH_IterEnd() is returned. 266 * @par Dependency: None 267 * @li bsl_hash.h: header file where this function's declaration is located. 268 */ 269 BSL_HASH_Iterator BSL_HASH_Find(const BSL_HASH_Hash *hash, uintptr_t key); 270 271 /** 272 * @ingroup bsl_hash 273 * @brief Check whether the current hash table is empty. 274 * @par Description: Check whether the current hash table is empty. 275 * If the hash table is empty, true is returned. Otherwise, false is returned. 276 * @param hash [IN] Handle of the hash table. The value range is valid pointer. 277 * @retval #true, indicating that the hash table is empty. 278 * @retval #false, indicating that the hash table is not empty. 279 * @see #BSL_HASH_Size 280 * @par Dependency: None 281 * @li bsl_hash.h: header file where the interface declaration is stored. 282 */ 283 bool BSL_HASH_Empty(const BSL_HASH_Hash *hash); 284 285 /** 286 * @ingroup bsl_hash 287 * @brief Obtain the number of nodes in the hash table. 288 * @par Description: Obtains the number of nodes in the hash table and returns the number of nodes. 289 * @param hash [IN] Handle of the hash table. The value range is valid pointer. 290 * @retval Number of hash nodes. 291 * @par Dependency: None 292 * @li bsl_hash.h: header file where this function's declaration is located. 293 */ 294 uint32_t BSL_HASH_Size(const BSL_HASH_Hash *hash); 295 296 /** 297 * @ingroup bsl_hash 298 * @brief Remove a specified node from the hash table. 299 * @par Description: Find the node based on the key, delete the node (release it), 300 * and release the memory of the corresponding node. 301 * @param hash [IN] Handle of the hash table. The value range is a valid pointer. 302 * @param key [IN] Remove a node key. 303 * @retval If the key exists, 304 * the next iterator (pointing to the address of the node) of the iterator where the key is located is returned. 305 * Otherwise, #BSL_HASH_IterEnd() is returned. 306 * @par Dependency: None 307 * @li bsl_hash.h: header file where this function's declaration is located. 308 */ 309 BSL_HASH_Iterator BSL_HASH_Erase(BSL_HASH_Hash *hash, uintptr_t key); 310 311 /** 312 * @ingroup bsl_hash 313 * @brief Delete all nodes in the hash table. 314 * @par Description: Delete all nodes and reclaim the node memory. The hash table still exists, but there are no members 315 * @attention Note: If the user data contains private resources, need to register the free hook function during creation 316 * @param hash [IN] Handle of the hash table. 317 * @retval none. 318 * @par Dependency: None 319 * @li bsl_hash.h: header file where this function's declaration is located. 320 */ 321 void BSL_HASH_Clear(BSL_HASH_Hash *hash); 322 323 /** 324 * @ingroup bsl_hash 325 * @brief Delete the hash table. 326 * @par Description: Delete the hash table. If a node exists in the table, delete the node first and reclaim the memory. 327 * @attention Note: If the user data contains private resources, need to register the free hook function during creation 328 * @param hash [IN] Handle of the hash table. 329 * @retval none. 330 * @par Dependency: None 331 * @li bsl_hash.h: header file where this function's declaration is located. 332 */ 333 void BSL_HASH_Destory(BSL_HASH_Hash *hash); 334 335 /** 336 * @ingroup bsl_hash 337 * @brief Obtain the iterator of the first node in the hash table. 338 * @par Description: Obtains the iterator where the first node in the hash table is located. 339 * @param hash [IN] Handle of the hash table. 340 * @retval Iterator of the first node. If the hash is empty, #BSL_HASH_IterEnd() is returned. 341 * @par Dependency: None 342 * @li bsl_hash.h: header file where this function's declaration is located. 343 */ 344 BSL_HASH_Iterator BSL_HASH_IterBegin(const BSL_HASH_Hash *hash); 345 346 /** 347 * @ingroup bsl_hash 348 * @brief Obtain the iterator reserved after the last node in the hash table. 349 * @par Description: Obtain the iterator reserved after the last node in the hash table. 350 * This node points to the last reserved hash bucket, which has no members. 351 * @param hash [IN] Handle of the hash table. 352 * @retval Iterator reserved after the last node. 353 * @par Dependency: None 354 * @li bsl_hash.h: header file where this function's declaration is located. 355 */ 356 BSL_HASH_Iterator BSL_HASH_IterEnd(const BSL_HASH_Hash *hash); 357 358 /** 359 * @ingroup bsl_hash 360 * @brief Obtain the iterator of the next node in the hash table. 361 * @par Description: Obtains the iterator of the next node in the hash table. 362 * @param hash [IN] Handle of the hash table. 363 * @param it [IN] Current iterator. 364 * @retval Next node iterator. If the current node is the last iterator, #BSL_HASH_IterEnd() is returned. 365 * @par Dependency: None 366 * @li bsl_hash.h: header file where this function's declaration is located. 367 */ 368 BSL_HASH_Iterator BSL_HASH_IterNext(const BSL_HASH_Hash *hash, BSL_HASH_Iterator it); 369 370 /** 371 * @ingroup bsl_hash 372 * @brief Obtain the key of the iterator. 373 * @par Description: Obtains the current key of the iterator in the hash table. 374 * @attention 375 * 1. When the hash pointer is null or iterator it is equal to #BSL_HASH_IterEnd(), this function returns 0. 376 * This function cannot distinguish whether the error code or user data, 377 * 2. Before calling this function, ensure that hash is a valid pointer 378 * and iterator it is not equal to #BSL_HASH_IterEnd(). 379 * @param hash [IN] Handle of the hash table. 380 * @param it [IN] Current iterator. 381 * @retval Key corresponding to the iterator. If iterator it equals #BSL_HASH_IterEnd(), 0 is returned. 382 * @par Dependency: None 383 * @li bsl_hash.h: header file where this function's declaration is located. 384 */ 385 uintptr_t BSL_HASH_HashIterKey(const BSL_HASH_Hash *hash, BSL_HASH_Iterator it); 386 387 /** 388 * @ingroup bsl_hash 389 * @brief Obtain the value of the iterator. 390 * @par Description: Obtains the current value of the iterator in the hash table. 391 * @attention 392 * 1. When the hash pointer is null or it is equal to #BSL_HASH_IterEnd(), the interface returns 0. 393 * This function cannot distinguish whether the error code or user data, 394 * 2. Before calling this function, ensure that hash is a valid pointer 395 * and iterator it is not equal to #BSL_HASH_IterEnd(). 396 * @param hash [IN] Handle of the hash table. 397 * @param it [IN] Current iterator. 398 * @retval Value corresponding to the iterator. If iterator it equals #BSL_HASH_IterEnd(), 0 is returned. 399 * @par Dependency: None 400 * @li bsl_hash.h: header file where this function's declaration is located. 401 */ 402 uintptr_t BSL_HASH_IterValue(const BSL_HASH_Hash *hash, BSL_HASH_Iterator it); 403 404 #ifdef __cplusplus 405 } 406 #endif 407 408 #endif /* HITLS_BSL_HASH */ 409 410 #endif // BSL_HASH_H 411