1 /**
2 * @file cstl_hash.c
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 哈希表实现源码
18 * @date 2021-05-14
19 * @version v0.1.0
20 * *******************************************************************************************
21 * @par 修改日志：
22 * <table>
23 * <tr><th>Date <th>Version <th>Author <th>Description
24 * </table>
25 * *******************************************************************************************
26 */
27
28 #include "cstl_rawlist.h"
29 #include "securec.h"
30 #include "cstl_public_inner.h"
31 #include "cstl_hash.h"
32
33 #ifdef __cplusplus
34 extern "C" {
35 #endif /* __cplusplus */
36
37 #define CSTL_HASH_OPTION3 3
38 #define CSTL_HASH_OPTION2 2
39 #define CSTL_HASH_OPTION1 1
40
41 struct TagHashNode {
42 CstlRawListNode node; /**< 链表node */
43 uintptr_t key; /**< key或保存key的地址 */
44 uintptr_t value; /**< value或保存value的地址 */
45 };
46
47 typedef struct TagHashNode CstlHashNode;
48
49 struct CstlHashInfo {
50 CstlDupFreeFuncPair keyFunc; /**< key拷贝、释放函数对 */
51 CstlDupFreeFuncPair valueFunc; /**< value拷贝、释放函数对 */
52 CstlHashMatchFunc matchFunc; /**< 匹配函数 */
53 CstlHashCodeCalcFunc hashFunc; /**< 哈希函数 */
54 size_t bucketSize; /**< Hash表大小 */
55 size_t hashCount; /**< Hash表中表项的个数 */
56 CstlRawList listArray[0]; /**< 链表控制块数组 */
57 };
58
59 /* murmurhash算法 */
60 /* 定义常量 */
61 #define HASH_VC1 0xCC9E2D51
62 #define HASH_VC2 0x1B873593
63 #define HASH_HC1 0xE6546B64
64 #define HASH_HC2 0x85EBCA6B
65 #define HASH_HC3 0xC2B2AE35
66 #define HASH_HC4 5
67
68 #define CHAR_BIT 8
69 #define CHAR_FOR_PER_LOOP 4
70 #define HASH_V_ROTATE 15
71 #define HASH_H_ROTATE 13
72 #define SYS_BUS_WIDTH sizeof(size_t)
73 #define HASH_SEED 0x3B9ACA07 /* 大质数1000000007，种子可以随机也可以指定 */
74
75 enum CstlByte {
76 ONE_BYTE = 1,
77 TWO_BYTE = 2,
78 };
79
80 enum CstlShiftBit {
81 SHIFT8 = 8,
82 SHIFT13 = 13,
83 SHIFT16 = 16,
84 SHIFT24 = 24
85 };
86
87 CstlHashIterator CstlHashPrev(const CstlHash *hash, CstlHashIterator hashNode);
88
CstlHashRotate(size_t v,uint32_t offset)89 CSTL_STATIC size_t CstlHashRotate(size_t v, uint32_t offset)
90 {
91 return ((v << offset) | (v >> (SYS_BUS_WIDTH * CHAR_BIT - offset)));
92 }
93
CstlHashMixV(size_t v)94 CSTL_STATIC size_t CstlHashMixV(size_t v)
95 {
96 v = v * HASH_VC1;
97 v = CstlHashRotate(v, HASH_V_ROTATE);
98 v = v * HASH_VC2;
99
100 return v;
101 }
102
CstlHashMixH(size_t h,size_t v)103 CSTL_STATIC size_t CstlHashMixH(size_t h, size_t v)
104 {
105 size_t res = h;
106
107 res ^= v;
108 res = CstlHashRotate(res, HASH_H_ROTATE);
109 res = res * HASH_HC4 + HASH_HC1;
110
111 return res;
112 }
113
CstlHashCodeCalc(void * key,size_t keySize)114 CSTL_STATIC size_t CstlHashCodeCalc(void *key, size_t keySize)
115 {
116 uint8_t *tmpKey = (uint8_t *)key;
117 size_t i = 0;
118 size_t v;
119 size_t h = HASH_SEED;
120 uint8_t c0, c1, c2, c3;
121 size_t tmpLen = keySize - keySize % CHAR_FOR_PER_LOOP;
122
123 while ((i + CHAR_FOR_PER_LOOP) <= tmpLen) {
124 c0 = tmpKey[i++];
125 c1 = tmpKey[i++];
126 c2 = tmpKey[i++];
127 c3 = tmpKey[i++];
128
129 v = (size_t)c0 | ((size_t)c1 << SHIFT8) |
130 ((size_t)c2 << SHIFT16) | ((size_t)c3 << SHIFT24);
131 v = CstlHashMixV(v);
132 h = CstlHashMixH(h, v);
133 }
134
135 v = 0;
136
137 switch (keySize & CSTL_HASH_OPTION3) {
138 case CSTL_HASH_OPTION3:
139 v ^= ((size_t)tmpKey[i + TWO_BYTE] << SHIFT16);
140 /* (keySize % 4)等于3，fallthrough，其他分支类似。 */
141 /* fall-through */
142 case CSTL_HASH_OPTION2:
143 v ^= ((size_t)tmpKey[i + ONE_BYTE] << SHIFT8);
144 /* fall-through */
145 case CSTL_HASH_OPTION1:
146 v ^= tmpKey[i];
147 v = CstlHashMixV(v);
148 h ^= v;
149 break;
150 default:
151 break;
152 }
153
154 h ^= h >> SHIFT16;
155
156 h *= HASH_HC2;
157 h ^= h >> SHIFT13;
158 h *= HASH_HC3;
159 h ^= h >> SHIFT16;
160
161 return h;
162 }
163
164 /* 内部接口定义 */
CstlHashHookRegister(CstlHash * hash,CstlHashCodeCalcFunc hashFunc,CstlHashMatchFunc matchFunc,CstlDupFreeFuncPair * keyFunc,CstlDupFreeFuncPair * valueFunc)165 CSTL_STATIC void CstlHashHookRegister(CstlHash *hash,
166 CstlHashCodeCalcFunc hashFunc,
167 CstlHashMatchFunc matchFunc,
168 CstlDupFreeFuncPair *keyFunc,
169 CstlDupFreeFuncPair *valueFunc)
170 {
171 CstlDupFreeFuncPair *hashKeyFunc = &hash->keyFunc;
172 CstlDupFreeFuncPair *hashValueFunc = &hash->valueFunc;
173
174 if (hashFunc == NULL) {
175 hash->hashFunc = CstlHashCodeCalcInt;
176 } else {
177 hash->hashFunc = hashFunc;
178 }
179
180 if (matchFunc == NULL) {
181 hash->matchFunc = CstlHashMatchInt;
182 } else {
183 hash->matchFunc = matchFunc;
184 }
185
186 if (keyFunc == NULL) {
187 hashKeyFunc->dupFunc = NULL;
188 hashKeyFunc->freeFunc = NULL;
189 } else {
190 hashKeyFunc->dupFunc = keyFunc->dupFunc;
191 hashKeyFunc->freeFunc = keyFunc->freeFunc;
192 }
193
194 if (valueFunc == NULL) {
195 hashValueFunc->dupFunc = NULL;
196 hashValueFunc->freeFunc = NULL;
197 } else {
198 hashValueFunc->dupFunc = valueFunc->dupFunc;
199 hashValueFunc->freeFunc = valueFunc->freeFunc;
200 }
201 }
202
CstlHashIterEndGet(const CstlHash * hash)203 CSTL_STATIC inline CstlHashIterator CstlHashIterEndGet(const CstlHash *hash)
204 {
205 return (CstlHashIterator)(uintptr_t)(&hash->listArray[hash->bucketSize].head);
206 }
207
CstlHashNodeCreate(const CstlHash * hash,uintptr_t key,size_t keySize,uintptr_t value,size_t valueSize)208 CSTL_STATIC CstlHashNode *CstlHashNodeCreate(const CstlHash *hash, uintptr_t key, size_t keySize,
209 uintptr_t value, size_t valueSize)
210 {
211 uintptr_t tmpKey;
212 uintptr_t tmpValue;
213 CstlHashNode *hashNode;
214 void *tmpPtr;
215
216 hashNode = (CstlHashNode *)malloc(sizeof(CstlHashNode));
217 if (hashNode == NULL) {
218 CSTL_PRINTF("[Cstlhash]: malloc failed. File = %s, line = %d.\r\n", __FILE__, __LINE__);
219 return NULL;
220 }
221
222 if (hash->keyFunc.dupFunc != NULL) {
223 tmpPtr = hash->keyFunc.dupFunc((void *)key, keySize);
224 tmpKey = (uintptr_t)tmpPtr;
225 if (tmpKey == (uintptr_t)NULL) {
226 /* 考虑用户返回失败的场景 */
227 free(hashNode);
228 return NULL;
229 }
230 } else {
231 tmpKey = key;
232 }
233
234 if (hash->valueFunc.dupFunc != NULL) {
235 tmpPtr = hash->valueFunc.dupFunc((void *)value, valueSize);
236 tmpValue = (uintptr_t)tmpPtr;
237 if (tmpValue == (uintptr_t)NULL) {
238 /* 考虑用户返回失败的场景 */
239 if (hash->keyFunc.freeFunc != NULL) {
240 hash->keyFunc.freeFunc((void *)tmpKey);
241 }
242
243 free(hashNode);
244 return NULL;
245 }
246 } else {
247 tmpValue = value;
248 }
249
250 hashNode->key = tmpKey;
251 hashNode->value = tmpValue;
252
253 return hashNode;
254 }
255
CstlHashFindNode(const CstlRawList * list,uintptr_t key,CstlHashMatchFunc matchFunc)256 CSTL_STATIC CstlHashNode *CstlHashFindNode(const CstlRawList *list, uintptr_t key, CstlHashMatchFunc matchFunc)
257 {
258 CstlHashNode *hashNode;
259 CstlRawListNode *rawListNode;
260
261 for (rawListNode = CstlRawListFront(list); rawListNode != NULL; rawListNode = CstlRawListNext(list, rawListNode)) {
262 hashNode = CSTL_CONTAINER_OF(rawListNode, CstlHashNode, node);
263 if (matchFunc(hashNode->key, key)) {
264 return hashNode;
265 }
266 }
267
268 return NULL;
269 }
270
CstlHashFront(const CstlHash * hash)271 CSTL_STATIC CstlHashIterator CstlHashFront(const CstlHash *hash)
272 {
273 uint32_t i = 0;
274 const CstlRawList *list;
275 CstlRawListNode *rawListNode;
276
277 while (i < hash->bucketSize) {
278 list = &hash->listArray[i];
279 rawListNode = CstlRawListFront(list);
280 if (rawListNode != NULL) {
281 return CSTL_CONTAINER_OF(rawListNode, CstlHashNode, node);
282 }
283
284 i++;
285 }
286
287 return CstlHashIterEndGet(hash);
288 }
289
CstlHashNext(const CstlHash * hash,CstlHashIterator hashNode)290 CSTL_STATIC CstlHashIterator CstlHashNext(const CstlHash *hash, CstlHashIterator hashNode)
291 {
292 size_t i;
293 size_t hashCode;
294 const CstlRawList *list;
295 CstlRawListNode *rawListNode;
296
297 hashCode = hash->hashFunc(hashNode->key, hash->bucketSize);
298 if (hashCode >= hash->bucketSize) {
299 CSTL_PRINTF("[Cstlhash]: hashCode is invalid. File = %s, line = %d.\r\n", __FILE__, __LINE__);
300 return CstlHashIterEndGet(hash);
301 }
302
303 list = hash->listArray + hashCode;
304 rawListNode = CstlRawListNext(list, &hashNode->node);
305 if (rawListNode != NULL) {
306 return CSTL_CONTAINER_OF(rawListNode, CstlHashNode, node);
307 }
308
309 for (i = hashCode + 1; i < hash->bucketSize; ++i) {
310 list = &hash->listArray[i];
311 rawListNode = CstlRawListFront(list);
312 if (rawListNode != NULL) {
313 return CSTL_CONTAINER_OF(rawListNode, CstlHashNode, node);
314 }
315 }
316
317 return CstlHashIterEndGet(hash);
318 }
319
CstlHashPrev(const CstlHash * hash,CstlHashIterator hashNode)320 CstlHashIterator CstlHashPrev(const CstlHash *hash, CstlHashIterator hashNode)
321 {
322 ssize_t i;
323 size_t hashCode;
324 const CstlRawList *list;
325 CstlRawListNode *rawListNode;
326
327 hashCode = hash->hashFunc(hashNode->key, hash->bucketSize);
328 if (hashCode >= hash->bucketSize) {
329 CSTL_PRINTF("[Cstlhash]: hashCode is invalid. File = %s, line = %d.\r\n", __FILE__, __LINE__);
330 return CstlHashIterEndGet(hash);
331 }
332
333 list = hash->listArray + hashCode;
334 rawListNode = CstlRawListPrev(list, &hashNode->node);
335 if (rawListNode != NULL) {
336 return CSTL_CONTAINER_OF(rawListNode, CstlHashNode, node);
337 }
338
339 for (i = (ssize_t)(hashCode - 1); i >= 0; --i) {
340 list = &hash->listArray[i];
341 rawListNode = CstlRawListBack(list);
342 if (rawListNode != NULL) {
343 return CSTL_CONTAINER_OF(rawListNode, CstlHashNode, node);
344 }
345 }
346
347 return CstlHashIterEndGet(hash);
348 }
349
CstlHashNodeFree(CstlHash * hash,CstlHashNode * node)350 CSTL_STATIC void CstlHashNodeFree(CstlHash *hash, CstlHashNode *node)
351 {
352 CstlFreeFunc keyFreeFunc = hash->keyFunc.freeFunc;
353 CstlFreeFunc valueFreeFunc = hash->valueFunc.freeFunc;
354
355 if (keyFreeFunc != NULL) {
356 keyFreeFunc((void *)node->key);
357 }
358
359 if (valueFreeFunc != NULL) {
360 valueFreeFunc((void *)node->value);
361 }
362
363 free(node);
364 }
365
CstlHashCodeCalcInt(uintptr_t key,size_t bktSize)366 __attribute__((visibility("default"))) size_t CstlHashCodeCalcInt(uintptr_t key, size_t bktSize)
367 {
368 size_t hashCode = CstlHashCodeCalc(&key, sizeof(key));
369
370 return hashCode % bktSize;
371 }
372
CstlHashMatchInt(uintptr_t key1,uintptr_t key2)373 __attribute__((visibility("default"))) bool CstlHashMatchInt(uintptr_t key1, uintptr_t key2)
374 {
375 return key1 == key2;
376 }
377
CstlHashCodeCalcStr(uintptr_t key,size_t bktSize)378 __attribute__((visibility("default"))) size_t CstlHashCodeCalcStr(uintptr_t key, size_t bktSize)
379 {
380 char *tmpKey = (char *)key;
381 size_t hashCode = CstlHashCodeCalc(tmpKey, strlen(tmpKey));
382
383 return hashCode % bktSize;
384 }
385
CstlHashMatchStr(uintptr_t key1,uintptr_t key2)386 __attribute__((visibility("default"))) bool CstlHashMatchStr(uintptr_t key1, uintptr_t key2)
387 {
388 char *tkey1 = (char *)key1;
389 char *tkey2 = (char *)key2;
390
391 if (strcmp(tkey1, tkey2) == 0) {
392 return true;
393 }
394
395 return false;
396 }
397
CstlHashCreate(size_t bktSize,CstlHashCodeCalcFunc hashFunc,CstlHashMatchFunc matchFunc,CstlDupFreeFuncPair * keyFunc,CstlDupFreeFuncPair * valueFunc)398 __attribute__((visibility("default"))) CstlHash *CstlHashCreate(size_t bktSize,
399 CstlHashCodeCalcFunc hashFunc,
400 CstlHashMatchFunc matchFunc,
401 CstlDupFreeFuncPair *keyFunc,
402 CstlDupFreeFuncPair *valueFunc)
403 {
404 size_t i;
405 size_t size;
406 CstlHash *hash;
407 CstlRawList *listAddr;
408 if (bktSize == 0U) {
409 CSTL_PRINTF("[Cstlhash]: bktSize is 0. File = %s, line = %d.\r\n", __FILE__, __LINE__);
410 return NULL;
411 }
412
413 size = (bktSize + 1) * sizeof(CstlRawList);
414 if (IsMultiOverflow((bktSize + 1), sizeof(CstlRawList)) || IsAddOverflow(size, sizeof(CstlHash))) {
415 CSTL_PRINTF("[Cstlhash]: bktSize is too big. File = %s, line = %d.\r\n", __FILE__, __LINE__);
416 return NULL;
417 }
418
419 size += sizeof(CstlHash);
420 hash = (CstlHash *)malloc(size);
421 if (hash == NULL) {
422 CSTL_PRINTF("[Cstlhash]: malloc failed. File = %s, line = %d.\r\n", __FILE__, __LINE__);
423 return NULL;
424 }
425
426 (void)memset_s(hash, size, 0, size);
427 hash->bucketSize = bktSize;
428 CstlHashHookRegister(hash, hashFunc, matchFunc, keyFunc, valueFunc);
429
430 listAddr = hash->listArray;
431 for (i = 0; i <= bktSize; ++i) {
432 CstlRawListInit(listAddr + i, NULL);
433 }
434
435 return hash;
436 }
437
CstlHashInsertNode(CstlHash * hash,CstlRawList * rawList,const CstlUserData * inputKey,const CstlUserData * inputValue)438 CSTL_STATIC int32_t CstlHashInsertNode(CstlHash *hash, CstlRawList *rawList,
439 const CstlUserData *inputKey, const CstlUserData *inputValue)
440 {
441 CstlHashNode *hashNode =
442 CstlHashNodeCreate(hash, inputKey->inputData, inputKey->dataSize, inputValue->inputData, inputValue->dataSize);
443 if (hashNode == NULL) {
444 CSTL_PRINTF("[Cstlhash]: hashNode create failed. File = %s, line = %d.\r\n", __FILE__, __LINE__);
445 return CSTL_ERROR;
446 }
447
448 CstlRawListPushBack(rawList, &hashNode->node);
449 hash->hashCount++;
450
451 return CSTL_OK;
452 }
453
CstlHashUpdateNode(CstlHash * hash,CstlHashNode * node,uintptr_t value,size_t valueSize)454 static int32_t CstlHashUpdateNode(CstlHash *hash, CstlHashNode *node, uintptr_t value, size_t valueSize)
455 {
456 uintptr_t tmpValue;
457 void *tmpPtr;
458
459 if (hash->valueFunc.dupFunc != NULL) {
460 tmpPtr = hash->valueFunc.dupFunc((void *)value, valueSize);
461 tmpValue = (uintptr_t)tmpPtr;
462 if (tmpValue == (uintptr_t)NULL) {
463 /* 考虑用户返回失败的场景 */
464 return CSTL_ERROR;
465 }
466
467 if (hash->valueFunc.freeFunc != NULL) {
468 hash->valueFunc.freeFunc((void *)node->value);
469 }
470 } else {
471 tmpValue = value;
472 }
473
474 node->value = tmpValue;
475
476 return CSTL_OK;
477 }
478
CstlHashCodeCheck(const CstlHash * hash,uintptr_t key,size_t * hashCode)479 CSTL_STATIC inline int32_t CstlHashCodeCheck(const CstlHash *hash, uintptr_t key, size_t *hashCode)
480 {
481 if (hash == NULL) {
482 CSTL_PRINTF("[Cstlhash]: hash is NULL. File = %s, line = %d.\r\n", __FILE__, __LINE__);
483 return CSTL_ERROR;
484 }
485
486 *hashCode = hash->hashFunc(key, hash->bucketSize);
487 if (*hashCode >= hash->bucketSize) {
488 CSTL_PRINTF("[Cstlhash]: hashCode is invalid. File = %s, line = %d.\r\n", __FILE__, __LINE__);
489 return CSTL_ERROR;
490 }
491
492 return CSTL_OK;
493 }
494
CstlHashInsert(CstlHash * hash,uintptr_t key,size_t keySize,uintptr_t value,size_t valueSize)495 __attribute__((visibility("default"))) int32_t CstlHashInsert(CstlHash *hash, uintptr_t key, size_t keySize,
496 uintptr_t value, size_t valueSize)
497 {
498 int32_t ret;
499 size_t hashCode;
500 CstlHashNode *hashNode;
501 CstlRawList *rawList;
502 CstlUserData inputKey;
503 CstlUserData inputValue;
504
505 ret = CstlHashCodeCheck(hash, key, &hashCode);
506 if (ret != CSTL_OK) {
507 return CSTL_ERROR;
508 }
509
510 rawList = &hash->listArray[hashCode];
511 hashNode = CstlHashFindNode(rawList, key, hash->matchFunc);
512 if (hashNode != NULL) {
513 CSTL_PRINTF("[Cstlhash]: key is exist. File = %s, line = %d.\r\n", __FILE__, __LINE__);
514 return CSTL_ERROR;
515 }
516
517 inputKey.inputData = key;
518 inputKey.dataSize = keySize;
519 inputValue.inputData = value;
520 inputValue.dataSize = valueSize;
521
522 return CstlHashInsertNode(hash, rawList, &inputKey, &inputValue);
523 }
524
CstlHashPut(CstlHash * hash,uintptr_t key,size_t keySize,uintptr_t value,size_t valueSize)525 __attribute__((visibility("default"))) int32_t CstlHashPut(CstlHash *hash, uintptr_t key, size_t keySize,
526 uintptr_t value, size_t valueSize)
527 {
528 int32_t ret;
529 size_t hashCode;
530 CstlRawList *rawList;
531 CstlHashNode *hashNode;
532 CstlUserData inputKey;
533 CstlUserData inputValue;
534
535 ret = CstlHashCodeCheck(hash, key, &hashCode);
536 if (ret != CSTL_OK) {
537 return CSTL_ERROR;
538 }
539
540 rawList = &hash->listArray[hashCode];
541 hashNode = CstlHashFindNode(rawList, key, hash->matchFunc);
542 if (hashNode != NULL) {
543 return CstlHashUpdateNode(hash, hashNode, value, valueSize);
544 }
545
546 inputKey.inputData = key;
547 inputKey.dataSize = keySize;
548 inputValue.inputData = value;
549 inputValue.dataSize = valueSize;
550
551 return CstlHashInsertNode(hash, rawList, &inputKey, &inputValue);
552 }
553
CstlHashAt(const CstlHash * hash,uintptr_t key,uintptr_t * value)554 __attribute__((visibility("default"))) int32_t CstlHashAt(const CstlHash *hash, uintptr_t key, uintptr_t *value)
555 {
556 CstlHashNode *hashNode = CstlHashFind(hash, key);
557
558 if (hashNode == CstlHashIterEndGet(hash)) {
559 return CSTL_ERROR;
560 }
561
562 *value = hashNode->value;
563
564 return CSTL_OK;
565 }
566
CstlHashFind(const CstlHash * hash,uintptr_t key)567 __attribute__((visibility("default"))) CstlHashIterator CstlHashFind(const CstlHash *hash, uintptr_t key)
568 {
569 int32_t ret;
570 size_t hashCode;
571 CstlHashNode *hashNode;
572
573 ret = CstlHashCodeCheck(hash, key, &hashCode);
574 if (ret != CSTL_OK) {
575 return hash == NULL ? NULL : CstlHashIterEndGet(hash);
576 }
577
578 hashNode = CstlHashFindNode(&hash->listArray[hashCode], key, hash->matchFunc);
579 if (hashNode == NULL) {
580 CSTL_PRINTF("[Cstlhash]: key is not exist. File = %s, line = %d.\r\n", __FILE__, __LINE__);
581 return CstlHashIterEndGet(hash);
582 }
583
584 return hashNode;
585 }
586
CstlHashEmpty(const CstlHash * hash)587 __attribute__((visibility("default"))) bool CstlHashEmpty(const CstlHash *hash)
588 {
589 if ((hash == NULL) || (hash->hashCount == 0U)) {
590 return true;
591 }
592
593 return false;
594 }
595
CstlHashSize(const CstlHash * hash)596 __attribute__((visibility("default"))) size_t CstlHashSize(const CstlHash *hash)
597 {
598 if (hash == NULL) {
599 return 0;
600 }
601
602 return hash->hashCount;
603 }
604
CstlHashErase(CstlHash * hash,uintptr_t key)605 __attribute__((visibility("default"))) CstlHashIterator CstlHashErase(CstlHash *hash, uintptr_t key)
606 {
607 size_t hashCode;
608 CstlHashNode *hashNode;
609 CstlHashNode *nextHashNode;
610 CstlHashMatchFunc matchFunc;
611 CstlHashCodeCalcFunc hashFunc;
612
613 if (hash == NULL) {
614 CSTL_PRINTF("[Cstlhash]: hash is NULL. File = %s, line = %d.\r\n", __FILE__, __LINE__);
615 return NULL;
616 }
617
618 hashFunc = hash->hashFunc;
619 hashCode = hashFunc(key, hash->bucketSize);
620 if (hashCode >= hash->bucketSize) {
621 CSTL_PRINTF("[Cstlhash]: hashCode is invalid. File = %s, line = %d.\r\n", __FILE__, __LINE__);
622 return CstlHashIterEndGet(hash);
623 }
624
625 matchFunc = hash->matchFunc;
626 hashNode = CstlHashFindNode(&hash->listArray[hashCode], key, matchFunc);
627 if (hashNode == NULL) {
628 return CstlHashIterEndGet(hash);
629 }
630
631 nextHashNode = CstlHashNext(hash, hashNode);
632 CstlRawListErase(&hash->listArray[hashCode], &hashNode->node);
633 CstlHashNodeFree(hash, hashNode);
634 --hash->hashCount;
635
636 return nextHashNode;
637 }
638
CstlHashClear(CstlHash * hash)639 __attribute__((visibility("default"))) void CstlHashClear(CstlHash *hash)
640 {
641 uint32_t i;
642 CstlRawList *list;
643 CstlHashNode *hashNode;
644 CstlRawListNode *rawListNode;
645
646 if (hash == NULL) {
647 CSTL_PRINTF("[Cstlhash]: hash is NULL. File = %s, line = %d.\r\n", __FILE__, __LINE__);
648 return;
649 }
650
651 for (i = 0; i < hash->bucketSize; ++i) {
652 list = &hash->listArray[i];
653 while (!CstlRawListEmpty(list)) {
654 rawListNode = CstlRawListFront(list);
655 hashNode = CSTL_CONTAINER_OF(rawListNode, CstlHashNode, node);
656 CstlRawListErase(list, rawListNode);
657 CstlHashNodeFree(hash, hashNode);
658 }
659 }
660
661 hash->hashCount = 0;
662 }
663
CstlHashDestory(CstlHash * hash)664 __attribute__((visibility("default"))) void CstlHashDestory(CstlHash *hash)
665 {
666 if (hash == NULL) {
667 CSTL_PRINTF("[Cstlhash]: hash is NULL. File = %s, line = %d.\r\n", __FILE__, __LINE__);
668 return;
669 }
670
671 CstlHashClear(hash);
672 free(hash);
673 }
674
CstlHashIterBegin(const CstlHash * hash)675 __attribute__((visibility("default"))) CstlHashIterator CstlHashIterBegin(const CstlHash *hash)
676 {
677 if (hash == NULL) {
678 CSTL_PRINTF("[Cstlhash]: hash is NULL. File = %s, line = %d.\r\n", __FILE__, __LINE__);
679 return NULL;
680 }
681
682 return CstlHashFront(hash);
683 }
684
CstlHashIterEnd(const CstlHash * hash)685 __attribute__((visibility("default"))) CstlHashIterator CstlHashIterEnd(const CstlHash *hash)
686 {
687 if (hash == NULL) {
688 CSTL_PRINTF("[Cstlhash]: hash is NULL. File = %s, line = %d.\r\n", __FILE__, __LINE__);
689 return NULL;
690 }
691
692 return CstlHashIterEndGet(hash);
693 }
694
CstlHashIterNext(const CstlHash * hash,CstlHashIterator it)695 __attribute__((visibility("default"))) CstlHashIterator CstlHashIterNext(const CstlHash *hash, CstlHashIterator it)
696 {
697 if ((hash == NULL) || (it == CstlHashIterEnd(hash))) {
698 CSTL_PRINTF("[Cstlhash]: hash is NULL. File = %s, line = %d.\r\n", __FILE__, __LINE__);
699 return CstlHashIterEnd(hash);
700 }
701
702 return CstlHashNext(hash, it);
703 }
704
CstlHashIterKey(const CstlHash * hash,CstlHashIterator it)705 __attribute__((visibility("default"))) uintptr_t CstlHashIterKey(const CstlHash *hash, CstlHashIterator it)
706 {
707 if (it == CstlHashIterEnd(hash)) {
708 return 0;
709 }
710
711 return it->key;
712 }
713
CstlHashIterValue(const CstlHash * hash,CstlHashIterator it)714 __attribute__((visibility("default"))) uintptr_t CstlHashIterValue(const CstlHash *hash, CstlHashIterator it)
715 {
716 if (it == CstlHashIterEnd(hash)) {
717 return 0;
718 }
719
720 return it->value;
721 }
722
723 #ifdef __cplusplus
724 }
725 #endif /* __cplusplus */