1 /** 2 * @file cstl_hash.h 3 * @copyright Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved. 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 16 * @brief cstl_hash 对外头文件 17 * @details 1、遍历过程中，迭代器指向冲突链中节点的位置；但end迭代器指向最后一个保留的hash桶，该桶无数据。 18 * 2、关于(key, value)中的value 19 * a) 如果key、value是整型数据，且长度 <= sizeof(uintptr_t)，则直接记录在node后面紧邻位置； 20 * b）其它场景，key或value位置记录的是指针，指向真正的用户key或用户数据； 21 * 此时用户必须注册duplicate函数和free函数对。 22 * 3、duplicate函数：用户需要先根据源数据长度申请内存，在把用户数拷贝到申请的内存中去，最后返回分配的内存地址。 23 * +--------+ 24 * | 控制块 | 25 * +------- + iter--->+------+ iter-->+------+ 26 * | 0 | <-冲突链-> | prev | | prev | 27 * +--------+ | next | 场景1： | next | 场景2: 28 * | 1 | +------+ key长度<=sizeof(uintptr_t) +------+ key长度<sizeof(uintptr_t) 29 * |--------+ | key | value长度<=sizeof(uintptr_t) | key | value长度>sizeof(uintptr_t) 30 * | + +------+ +------+ 或字符串或自定义数据结构 31 * | ... | | value| | data |--+ 32 * +--------+ +------+ | 指针 | + 33 * +------+ + 34 * + 35 * +----->+----------+ 36 * | userdata | 37 * | area | 38 * +----------+ 39 * iter-->+------+ iter-->+------+ 场景4: 40 * | prev | | prev | key长度>sizeof(uintptr_t) 41 * | next | 场景3: | next | 或字符串或自定义数据结构 42 * +------+ key长度>sizeof(uintptr_t)或字符串或自定义数据结构 +------+ 43 * | key |---+ value长度<=sizeof(uintptr_t) | key |---+ value长度>sizeof(uintptr_t) 44 * | 指针 | + | 指针 | + 或字符串或自定义数据结构 45 * +------+ +---->+----------+ +------+ +---->+----------+ 46 * | data | | userkey | | data |--+ | userkey | 47 * +------+ | area | | 指针 | + | area | 48 * +----------+ +------+ + +----------+ 49 * + 50 * +----->+----------+ 51 * | userdata | 52 * | area | 53 * +----------+ 54 * @date 2021-05-14 55 * @version v0.1.0 56 * ******************************************************************************************* 57 * @par 修改日志： 58 * <table> 59 * <tr><th>Date <th>Version <th>Description 60 * <tr><td>2021-05-14 <td>0.1.0 <td>创建初始版本 61 * </table> 62 * ******************************************************************************************* 63 */ 64 65 /** 66 * @defgroup cstl_hash 哈希表 67 * @ingroup cstl 68 */ 69 70 #ifndef CSTL_HASH_H 71 #define CSTL_HASH_H 72 73 #include <stdlib.h> 74 #include <stdbool.h> 75 #include <string.h> 76 #include "cstl_public.h" 77 #include "securec.h" 78 79 #ifdef __cplusplus 80 extern "C" { 81 #endif 82 83 /** 84 * @ingroup cstl_hash 85 * @brief hash表句柄 86 */ 87 typedef struct CstlHashInfo CstlHash; 88 89 /** 90 * @ingroup cstl_hash 91 * @brief hash表迭代器定义，指向hash节点 92 */ 93 typedef struct TagHashNode *CstlHashIterator; 94 95 /** 96 * @ingroup cstl_hash 97 * @brief 根据输入的Key生成hash表索引。 98 * @param key [IN] hash key 99 * @param bktSize [IN] hash桶大小 100 */ 101 typedef size_t (*CstlHashCodeCalcFunc)(uintptr_t key, size_t bktSize); 102 103 /** 104 * @ingroup cstl_hash 105 * @brief 该函数把输入数据与Key进行匹配比较。第一个哈希表中保存的key，第二个是用户需要匹配的Key。如果不匹配，返回值为false。 106 * @param key1 [IN] 哈希表中保存的key 107 * @param key2 [IN] 待匹配的key 108 * @retval #true key1和key2匹配。 109 * @retval #false key1和key2不匹配。 110 */ 111 typedef bool (*CstlHashMatchFunc)(uintptr_t key1, uintptr_t key2); 112 113 /** 114 * @ingroup cstl_hash 115 * @brief 默认整型哈希函数。 116 * @par 默认整型哈希函数。 117 * @attention \n 118 * 1.key为用户调用其他接口时的入参。\n 119 * 2.若key为整型，用户可在创建hash时将该函数作为hashFunc参数。\n 120 * @param key [IN] 待计算的key。 121 * @param bktSize [IN] 哈希桶大小。 122 * @retval #哈希值 根据用户key计算出的哈希值。 123 * @par 依赖：无 124 * <ul><li>cstl_hash.h：该接口声明所在的头文件。</li></ul> 125 */ 126 size_t CstlHashCodeCalcInt(uintptr_t key, size_t bktSize); 127 128 /** 129 * @ingroup cstl_hash 130 * @brief 默认字符串哈希函数。 131 * @par 默认字符串哈希函数。 132 * @attention \n 133 * 1.key为用户调用其他接口时的入参，用户必须保证传入的key为合法的字符串首地址。\n 134 * 2.若key为字符串，用户可在创建hash时将该函数作为hashFunc参数。\n 135 * @param key [IN] 待计算的key。 136 * @param bktSize [IN] 哈希桶大小。 137 * @retval #哈希值 根据用户key计算出的哈希值。 138 * @par 依赖：无 139 * @li cstl_hash.h：该接口声明所在的头文件. 140 */ 141 size_t CstlHashCodeCalcStr(uintptr_t key, size_t bktSize); 142 143 /** 144 * @ingroup cstl_hash 145 * @brief 默认整型匹配函数。 146 * @par 默认整型匹配函数。 147 * @attention \n 148 * 1.key为用户调用其他接口时的入参。\n 149 * 2.若key为整型，用户可在创建hash时将该函数作为matchFunc参数。\n 150 * @param key1 [IN] 待匹配的key。 151 * @param key2 [IN] 待匹配的key。 152 * @retval #true key1和key2匹配。 153 * @retval #false key1和key2不匹配。 154 * @par 依赖：无 155 * @li cstl_hash.h：该接口声明所在的头文件. 156 */ 157 bool CstlHashMatchInt(uintptr_t key1, uintptr_t key2); 158 159 /** 160 * @ingroup cstl_hash 161 * @brief 默认字符串匹配函数。 162 * @par 默认字符串匹配函数。 163 * @attention \n 164 * 1.key1为用户调用其他接口时的入参，用户必须保证传入的key1为合法的字符串首地址。\n 165 * 2.若key为字符串，用户可在创建hash时将该函数作为matchFunc参数。\n 166 * @param key1 [IN] 待匹配的key。 167 * @param key2 [IN] 待匹配的key。 168 * @retval #true key1和key2匹配。 169 * @retval #false key1和key2不匹配。 170 * @par 依赖：无 171 * @li cstl_hash.h：该接口声明所在的头文件. 172 */ 173 bool CstlHashMatchStr(uintptr_t key1, uintptr_t key2); 174 175 /** 176 * @ingroup cstl_hash 177 * @brief 创建一个Hash表，返回Hash表的句柄 178 * @attention \n 179 * 1、关于key和data的拷贝函数：\n 180 * 如下场景不需要注册拷贝函数：如果是int型数据，且长度<=sizeof(uintptr_t)。\n 181 * 其它场景必须注册拷贝函数：\n 182 * a）是int型数据，但长度 >sizeof(uintptr_t)；\n 183 * b）字符串；\n 184 * c）用户自定义数据结构；\n 185 * 2、关于free函数：简单来说，如果注册了duplicate函数，就必须注册相应的free函数。 \n 186 * 3、提供默认的整型、字符串哈希函数：#CstlHashCodeCalcInt、#CstlHashCodeCalcStr。 \n 187 * 4、提供默认的整型、字符串匹配函数：#CstlHashMatchInt、#CstlHashMatchStr。 \n 188 * @param bktSize [IN] hash桶的个数 189 * @param hashCalcFunc [IN] hash值计算函数。如果为NULL，则默认key为整型，使用#CstlHashCodeCalcInt。 190 * @param matchFunc [IN] hash key匹配函数。如为NULL，则默认key为整型，使用#CstlHashMatchInt。 191 * @param keyFunc [IN] hash key拷贝及释放函数对，如果用户未注册keyFunc->dupFunc，则默认为key为整型。 192 * @param valueFunc [IN] hash data拷贝及释放函数对。如果用户未注册valueFunc->dupFunc，则默认为data为整型。 193 * @retval hash表句柄。NULL表示创建失败。 194 * @par 依赖：无 195 * @see #CstlHashCodeCalcInt、#CstlHashCodeCalcStr、#CstlHashMatchInt、#CstlHashMatchStr。 196 * @li cstl_hash.h：该接口声明所在的头文件. 197 */ 198 CstlHash *CstlHashCreate(size_t bktSize, 199 CstlHashCodeCalcFunc hashFunc, 200 CstlHashMatchFunc matchFunc, 201 CstlDupFreeFuncPair *keyFunc, 202 CstlDupFreeFuncPair *valueFunc); 203 204 /** 205 * @ingroup cstl_hash 206 * @brief 插入hash数据 207 * @par 描述：创建节点，把数据(key、value)插入hash表 208 * @attention 209 * 1.不支持重复key。\n 210 * 2.key和value为整型值或指向用户key或value的地址。\n 211 * 3.如果扩展数据的生命周期小于节点的生命周期，则需要在创建哈希表时注册拷贝函数及释放函数。\n 212 * @param hash [IN] hash表的句柄。 213 * @param key [IN] key或保存key的地址。 214 * @param keySize [IN] key拷贝长度，若用户未注册dupFunc，该参数将不被使用 215 * @param value [IN] value或保存value的地址。 216 * @param valueSize [IN] value拷贝长度，若用户未注册dupFunc，该参数将不被使用 217 * @retval #CSTL_OK 插入节点成功。 218 * @retval #CSTL_ERROR 插入失败。 219 * @par 依赖：无 220 * @li cstl_hash.h：该接口声明所在的头文件. 221 */ 222 int32_t CstlHashInsert(CstlHash *hash, uintptr_t key, size_t keySize, uintptr_t value, size_t valueSize); 223 224 /** 225 * @ingroup cstl_hash 226 * @brief 插入或更新hash数据 227 * @par 描述：该接口用于将不存在的key插入到哈希表或更新已存在的key对应的value。 228 * @attention 229 * 1.支持重复key。\n 230 * 2.当key不存在时，该接口的使用与#CstlHashInsert保持一致。\n 231 * 3.当key存在时，该接口会更新value。\n 232 * @param hash [IN] hash表的句柄。 233 * @param key [IN] key或保存key的地址。 234 * @param keySize [IN] key拷贝长度，若用户未注册dupFunc，该参数将不被使用 235 * @param value [IN] value或保存value的地址。 236 * @param valueSize [IN] value拷贝长度，若用户未注册dupFunc，该参数将不被使用 237 * @retval #CSTL_OK 插入或更新节点成功。 238 * @retval #CSTL_ERROR 插入或更新节点失败。 239 * @par 依赖：无 240 * @li cstl_hash.h：该接口声明所在的头文件. 241 */ 242 int32_t CstlHashPut(CstlHash *hash, uintptr_t key, size_t keySize, uintptr_t value, size_t valueSize); 243 244 /** 245 * @ingroup cstl_hash 246 * @brief 查找节点，返回节点数据。 247 * @par 描述: 根据key查找并返回节点数据。 248 * @param hash [IN] hash表的句柄。 249 * @param key [IN] key或保存key的地址。 250 * @param value [OUT] 查到的数据。 251 * @retval #CSTL_OK 查找成功。 252 * @retval #CSTL_ERROR 查找失败。 253 * @par 依赖：无 254 * @li cstl_hash.h：该接口声明所在的头文件. 255 */ 256 int32_t CstlHashAt(const CstlHash *hash, uintptr_t key, uintptr_t *value); 257 258 /** 259 * @ingroup cstl_hash 260 * @brief 查找key所在迭代器。 261 * @par 描述: 根据key查找并返回key所在的迭代器。 262 * @param hash [IN] hash表的句柄。 263 * @param key [IN] key或保存key的地址。 264 * @retval key存在时，返回key所在迭代器（指向Node所在地址）,其他情况返回#CstlHashIterEnd()。 265 * @par 依赖：无 266 * @li cstl_hash.h：该接口声明所在的头文件. 267 */ 268 CstlHashIterator CstlHashFind(const CstlHash *hash, uintptr_t key); 269 270 /** 271 * @ingroup cstl_hash 272 * @brief 判断当前HASH表是否为空。 273 * @par 描述: 判断当前HASH表是否为空，为空返回true，否则返回false。 274 * @param hash [IN] hash表句柄。取值范围为有效指针。 275 * @retval #true， 表示HASH表为空。 276 * @retval #false，表示HASH表非空。 277 * @see #CstlHashSize 278 * @par 依赖：无 279 * @li cstl_hash.h：该接口声明所在的头文件. 280 */ 281 bool CstlHashEmpty(const CstlHash *hash); 282 283 /** 284 * @ingroup cstl_hash 285 * @brief 获取HASH表的节点数量。 286 * @par 描述: 用于获取HASH表的节点数量，返回节点个数。 287 * @param hash [IN] hash表句柄。取值范围为有效指针。 288 * @retval hash节点数。 289 * @par 依赖：无 290 * @li cstl_hash.h：该接口声明所在的头文件. 291 */ 292 size_t CstlHashSize(const CstlHash *hash); 293 294 /** 295 * @ingroup cstl_hash 296 * @brief 从hash表中移除指定结点。 297 * @par 描述: 根据key查找到节点并删除（释放内存），同时释放相应的节点内存。 298 * @param hash [IN] hash表句柄。取值范围为有效指针。 299 * @param key [IN] 移除节点key。 300 * @retval key存在时，返回key所在迭代器的下一个迭代器（指向Node所在地址）,其他则返回#CstlHashIterEnd()。 301 * @par 依赖：无 302 * @li cstl_hash.h：该接口声明所在的头文件. 303 */ 304 CstlHashIterator CstlHashErase(CstlHash *hash, uintptr_t key); 305 306 /** 307 * @ingroup cstl_hash 308 * @brief 删除hash表所有节点。 309 * @par 描述：删除所有节点，回收节点内存（hash表还在，只是没有成员）。 310 * @attention 注意：如果用户数据中有私有资源，则需要在创建时注册free钩子函数。 311 * @param hash [IN] hash表句柄。 312 * @retval 无。 313 * @par 依赖：无 314 * @li cstl_hash.h：该接口声明所在的头文件. 315 */ 316 void CstlHashClear(CstlHash *hash); 317 318 /** 319 * @ingroup cstl_hash 320 * @brief 删除hash表 321 * @par 描述：删除hash表，如里面有节点先删除节点，回收内存。 322 * @attention 注意：如果用户数据中有私有资源，则需要在创建时注册free钩子函数。 323 * @param hash [IN] hash表句柄。 324 * @retval 无。 325 * @par 依赖：无 326 * @li cstl_hash.h：该接口声明所在的头文件. 327 */ 328 void CstlHashDestory(CstlHash *hash); 329 330 /** 331 * @ingroup cstl_hash 332 * @brief 获取hash表中的第一个节点的迭代器。 333 * @par 描述：获取hash表中的第一个节点所在的迭代器。 334 * @param hash [IN] hash表的句柄。 335 * @retval 第一个节点迭代器，若hash为空则返回#CstlHashIterEnd()。 336 * @par 依赖：无 337 * @li cstl_hash.h：该接口声明所在的头文件. 338 */ 339 CstlHashIterator CstlHashIterBegin(const CstlHash *hash); 340 341 /** 342 * @ingroup cstl_hash 343 * @brief 获取hash表中最后一个节点之后预留的迭代器。 344 * @par 描述：获取hash表中的最后一个节点之后预留的迭代器。该节点指向最后保留的hash桶，该桶没有任何成员。 345 * @param hash [IN] hash表的句柄。 346 * @retval 最后一个节点之后预留的迭代器。 347 * @par 依赖：无 348 * @li cstl_hash.h：该接口声明所在的头文件. 349 */ 350 CstlHashIterator CstlHashIterEnd(const CstlHash *hash); 351 352 /** 353 * @ingroup cstl_hash 354 * @brief 获取hash表的下一个节点迭代器。 355 * @par 描述：获取hash表下一个节点迭代器。 356 * @param hash [IN] hash表的句柄。 357 * @param it [IN] 当前迭代器。 358 * @retval 下一个节点迭代器。若当前节点已是最后一个迭代器则返回#CstlHashIterEnd()。 359 * @par 依赖：无 360 * @li cstl_hash.h：该接口声明所在的头文件. 361 */ 362 CstlHashIterator CstlHashIterNext(const CstlHash *hash, CstlHashIterator it); 363 364 /** 365 * @ingroup cstl_hash 366 * @brief 获取迭代器的key。 367 * @par 描述：获取hash表中迭代器当前key。 368 * @attention \n 369 * 1.当hash为空指针或it等于#CstlHashIterEnd()时，接口返回0，该接口无法区分是错误码还是用户数据， 370 * 用户调用该接口时必须保证hash为合法指针，并且it不等于#CstlHashIterEnd() 371 * @param hash [IN] hash表的句柄。 372 * @param it [IN] 当前迭代器。 373 * @retval 迭代器对应的key。it等于#CstlHashIterEnd()时则返回0。 374 * @par 依赖：无 375 * @li cstl_hash.h：该接口声明所在的头文件. 376 */ 377 uintptr_t CstlHashIterKey(const CstlHash *hash, CstlHashIterator it); 378 379 /** 380 * @ingroup cstl_hash 381 * @brief 获取迭代器的value。 382 * @par 描述：获取hash表中迭代器当前key。 383 * @attention \n 384 * 1.当hash为空指针或it等于#CstlHashIterEnd()时，接口返回0，该接口无法区分是错误码还是用户数据， 385 * 用户调用该接口时必须保证hash为合法指针，并且it不等于#CstlHashIterEnd() 386 * @param hash [IN] hash表的句柄。 387 * @param it [IN] 当前迭代器。 388 * @retval 迭代器对应的value。it等于#CstlHashIterEnd()时则返回0。 389 * @par 依赖：无 390 * @li cstl_hash.h：该接口声明所在的头文件. 391 */ 392 uintptr_t CstlHashIterValue(const CstlHash *hash, CstlHashIterator it); 393 394 #ifdef __cplusplus 395 } 396 #endif 397 398 #endif /* CSTL_HASH_H */ 399 400