1/*
2 * Copyright (c) 2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15#include "init_hashmap.h"
16#include "init_log.h"
17
18typedef struct {
19    HashNodeCompare nodeCompare;
20    HashKeyCompare keyCompare;
21    HashNodeFunction nodeHash;
22    HashKeyFunction keyHash;
23    HashNodeOnFree nodeFree;
24    int maxBucket;
25    uint32_t tableId;
26    HashNode *buckets[0];
27} HashTab;
28
29static uint32_t g_tableId = 0;
30int32_t OH_HashMapCreate(HashMapHandle *handle, const HashInfo *info)
31{
32    INIT_ERROR_CHECK(handle != NULL, return -1, "Invalid hash handle");
33    INIT_ERROR_CHECK(info != NULL && info->maxBucket > 0, return -1, "Invalid hash info");
34    INIT_ERROR_CHECK(info->keyHash != NULL && info->nodeHash != NULL, return -1, "Invalid hash key");
35    INIT_ERROR_CHECK(info->nodeCompare != NULL && info->keyCompare != NULL, return -1, "Invalid hash compare");
36    HashTab *tab = (HashTab *)calloc(1, sizeof(HashTab) + sizeof(HashNode*) * info->maxBucket);
37    INIT_ERROR_CHECK(tab != NULL, return -1, "Failed to create hash tab");
38    tab->maxBucket = info->maxBucket;
39    tab->keyHash = info->keyHash;
40    tab->nodeCompare = info->nodeCompare;
41    tab->keyCompare = info->keyCompare;
42    tab->nodeHash = info->nodeHash;
43    tab->nodeFree = info->nodeFree;
44    tab->tableId = g_tableId++;
45    *handle = (HashMapHandle)tab;
46    return 0;
47}
48
49static HashNode *GetHashNodeByNode(const HashTab *tab, const HashNode *root, const HashNode *new)
50{
51    HashNode *node = (HashNode *)root;
52    while (node != NULL) {
53        int ret = tab->nodeCompare(node, new);
54        if (ret == 0) {
55            return node;
56        }
57        node = node->next;
58    }
59    return NULL;
60}
61
62static HashNode *GetHashNodeByKey(const HashTab *tab, const HashNode *root, const void *key, HashKeyCompare keyCompare)
63{
64    (void)tab;
65    HashNode *node = (HashNode *)root;
66    while (node != NULL) {
67        int ret = keyCompare(node, key);
68        if (ret == 0) {
69            return node;
70        }
71        node = node->next;
72    }
73    return NULL;
74}
75
76int32_t OH_HashMapAdd(HashMapHandle handle, HashNode *node)
77{
78    INIT_ERROR_CHECK(handle != NULL, return -1, "Invalid hash handle");
79    INIT_ERROR_CHECK(node != NULL && node->next == NULL, return -1, "Invalid param");
80    HashTab *tab = (HashTab *)handle;
81    int hashCode = tab->nodeHash(node);
82    hashCode = (hashCode < 0) ? -hashCode : hashCode;
83    hashCode = hashCode % tab->maxBucket;
84    INIT_ERROR_CHECK(hashCode < tab->maxBucket, return -1, "Invalid hashcode %d %d", tab->maxBucket, hashCode);
85
86    // check key exist
87    HashNode *tmp = GetHashNodeByNode(tab, tab->buckets[hashCode], node);
88    if (tmp != NULL) {
89        INIT_LOGE("node hash been exist");
90        return -1;
91    }
92    node->next = tab->buckets[hashCode];
93    tab->buckets[hashCode] = node;
94    return 0;
95}
96
97void OH_HashMapRemove(HashMapHandle handle, const void *key)
98{
99    INIT_ERROR_CHECK(handle != NULL && key != NULL, return, "Invalid hash handle key:%s", key);
100    HashTab *tab = (HashTab *)handle;
101    int hashCode = tab->keyHash(key);
102    hashCode = (hashCode < 0) ? -hashCode : hashCode;
103    hashCode = hashCode % tab->maxBucket;
104    INIT_ERROR_CHECK(hashCode < tab->maxBucket, return, "Invalid hashcode %d %d", tab->maxBucket, hashCode);
105
106    HashNode *node = tab->buckets[hashCode];
107    HashNode *preNode = node;
108    while (node != NULL) {
109        int ret = tab->keyCompare(node, key);
110        if (ret == 0) {
111            if (node == tab->buckets[hashCode]) {
112                tab->buckets[hashCode] = node->next;
113            } else {
114                preNode->next = node->next;
115            }
116            return;
117        }
118        preNode = node;
119        node = node->next;
120    }
121}
122
123HashNode *OH_HashMapGet(HashMapHandle handle, const void *key)
124{
125    INIT_ERROR_CHECK(handle != NULL && key != NULL, return NULL, "Invalid hash handle key:%s", key);
126    HashTab *tab = (HashTab *)handle;
127    int hashCode = tab->keyHash(key);
128    hashCode = (hashCode < 0) ? -hashCode : hashCode;
129    hashCode = hashCode % tab->maxBucket;
130    INIT_ERROR_CHECK(hashCode < tab->maxBucket, return NULL,
131        "Invalid hashcode %d %d", tab->maxBucket, hashCode);
132    return GetHashNodeByKey(tab, tab->buckets[hashCode], key, tab->keyCompare);
133}
134
135static void HashListFree(HashTab *tab, HashNode *root, void *context)
136{
137    if (root == NULL) {
138        return;
139    }
140    HashNode *node = root;
141    while (node != NULL) {
142        HashNode *next = node->next;
143        if (tab->nodeFree != NULL) {
144            tab->nodeFree(node, context);
145        }
146        node = next;
147    }
148}
149
150void OH_HashMapDestory(HashMapHandle handle, void *context)
151{
152    INIT_ERROR_CHECK(handle != NULL, return, "Invalid hash handle");
153    HashTab *tab = (HashTab *)handle;
154    for (int i = 0; i < tab->maxBucket; i++) {
155        HashListFree(tab, tab->buckets[i], context);
156    }
157    free(tab);
158}
159
160HashNode *OH_HashMapFind(HashMapHandle handle,
161    int hashCode, const void *key, HashKeyCompare keyCompare)
162{
163    INIT_ERROR_CHECK(handle != NULL, return NULL, "Invalid hash handle");
164    INIT_ERROR_CHECK(key != NULL && keyCompare != NULL, return NULL, "Invalid hash key");
165    HashTab *tab = (HashTab *)handle;
166    INIT_ERROR_CHECK((hashCode < tab->maxBucket) && (hashCode >= 0), return NULL,
167        "Invalid hash code %d %d", tab->maxBucket, hashCode);
168    return GetHashNodeByKey(tab, tab->buckets[hashCode], key, keyCompare);
169}
170
171void OH_HashMapTraverse(HashMapHandle handle, void (*hashNodeTraverse)(const HashNode *node, const void *context),
172    const void *context)
173{
174    INIT_ERROR_CHECK(handle != NULL && hashNodeTraverse != NULL, return, "Invalid hash handle");
175    HashTab *tab = (HashTab *)handle;
176    for (int i = 0; i < tab->maxBucket; i++) {
177        HashNode *node = tab->buckets[i];
178        while (node != NULL) {
179            HashNode *next = node->next;
180            hashNodeTraverse(node, context);
181            node = next;
182        }
183    }
184}
185
186int OH_HashMapIsEmpty(HashMapHandle handle)
187{
188    INIT_ERROR_CHECK(handle != NULL, return 1, "Invalid hash handle");
189    HashTab *tab = (HashTab *)handle;
190    for (int i = 0; i < tab->maxBucket; i++) {
191        HashNode *node = tab->buckets[i];
192        if (node != NULL) {
193            return 0;
194        }
195    }
196    return 1;
197}
198