1 /*
2  * Copyright (c) 2020-2021 Huawei Device Co., Ltd.
3  *
4  * HDF is dual licensed: you can use it either under the terms of
5  * the GPL, or the BSD license, at your option.
6  * See the LICENSE file in the root of this repository for complete details.
7  */
8 
9 #include "hdf_map.h"
10 #if defined(__KERNEL__)
11 #include <linux/string.h>
12 #else
13 #include <string.h>
14 #endif
15 #include "osal_mem.h"
16 #include "securec.h"
17 #define HDF_UINT32_MAX 0xffffffffu
18 
19 struct MapNode {
20     uint32_t hash;
21     uint32_t valueSize;
22     void *key;
23     void *value;
24     struct MapNode *next;
25 };
26 
27 #define HDF_MIN_MAP_SIZE 8
28 #define HDF_ENLARGE_FACTOR 2
29 #define HDF_MAP_KEY_MAX_SIZE 1000
30 #define HDF_MAP_VALUE_MAX_SIZE 1000
31 
32 const uint32_t HASH_SEED = 131;
33 
34 /* BKDR Hash */
MapHash(const char * hashKey)35 static uint32_t MapHash(const char *hashKey)
36 {
37     uint32_t hashValue = 0;
38 
39     while (hashKey != NULL && *hashKey != 0) {
40         hashValue = hashValue * HASH_SEED + (*hashKey++);
41     }
42 
43     return (hashValue & 0x7FFFFFFF);
44 }
45 
MapHashIdx(const Map * map,uint32_t hash)46 static uint32_t MapHashIdx(const Map *map, uint32_t hash)
47 {
48     if (map->bucketSize < 1 || map->bucketSize > HDF_UINT32_MAX) {
49         return 0;
50     }
51     return (hash & (map->bucketSize - 1));
52 }
53 
MapAddNode(Map * map,struct MapNode * node)54 static void MapAddNode(Map *map, struct MapNode *node)
55 {
56     uint32_t idx = MapHashIdx(map, node->hash);
57     node->next = map->nodes[idx];
58     map->nodes[idx] = node;
59 }
60 
MapResize(Map * map,uint32_t size)61 static int32_t MapResize(Map *map, uint32_t size)
62 {
63     uint32_t bucketSize;
64     struct MapNode **nodes = NULL;
65     struct MapNode **tmp = NULL;
66     uint32_t i;
67 
68     nodes = (struct MapNode **)OsalMemCalloc(size * sizeof(*nodes));
69     if (nodes == NULL) {
70         return HDF_ERR_MALLOC_FAIL;
71     }
72 
73     tmp = map->nodes;
74     bucketSize = map->bucketSize;
75     map->nodes = nodes;
76     map->bucketSize = size;
77 
78     if (tmp != NULL) {
79         struct MapNode *node = NULL;
80         struct MapNode *next = NULL;
81 
82         /* remap node with new map size */
83         for (i = 0; i < bucketSize; i++) {
84             node = tmp[i];
85             while (node != NULL) {
86                 next = node->next;
87                 MapAddNode(map, node);
88                 node = next;
89             }
90         }
91 
92         OsalMemFree(tmp);
93     }
94 
95     return HDF_SUCCESS;
96 }
97 
MapCreateNode(const char * key,uint32_t hash,const void * value,uint32_t valueSize)98 static struct MapNode *MapCreateNode(const char *key, uint32_t hash,
99     const void *value, uint32_t valueSize)
100 {
101     uint32_t keySize = strlen(key) + 1;
102     struct MapNode *node = (struct MapNode *)OsalMemCalloc(sizeof(*node) + keySize + valueSize);
103     if (node == NULL) {
104         return NULL;
105     }
106 
107     node->hash = hash;
108     node->key = (uint8_t *)node + sizeof(*node);
109     node->value = (uint8_t *)node + sizeof(*node) + keySize;
110     node->valueSize = valueSize;
111     if (memcpy_s(node->key, keySize, key, keySize) != EOK) {
112         OsalMemFree(node);
113         return NULL;
114     }
115     if (memcpy_s(node->value, node->valueSize, value, valueSize) != EOK) {
116         OsalMemFree(node);
117         return NULL;
118     }
119 
120     return node;
121 }
122 
MapSetCheckPara(const Map * map,const char * key,const void * value,uint32_t valueSize)123 static int32_t MapSetCheckPara(const Map *map, const char *key, const void *value, uint32_t valueSize)
124 {
125     if (map == NULL || key == NULL || value == NULL || valueSize == 0) {
126         return HDF_ERR_INVALID_PARAM;
127     }
128 
129     if (valueSize > HDF_MAP_KEY_MAX_SIZE || strlen(key) > HDF_MAP_VALUE_MAX_SIZE) {
130         return HDF_ERR_INVALID_PARAM;
131     }
132 
133     return HDF_SUCCESS;
134 }
135 
MapSet(Map * map,const char * key,const void * value,uint32_t valueSize)136 int32_t MapSet(Map *map, const char *key, const void *value, uint32_t valueSize)
137 {
138     struct MapNode *node = NULL;
139     uint32_t hash;
140 
141     if (MapSetCheckPara(map, key, value, valueSize) != HDF_SUCCESS) {
142         return HDF_ERR_INVALID_PARAM;
143     }
144 
145     hash = MapHash(key);
146     if (map->nodeSize > 0 && map->nodes != NULL) {
147         uint32_t idx = MapHashIdx(map, hash);
148         node = map->nodes[idx];
149         while (node != NULL) {
150             if (node->hash != hash || node->key == NULL || strcmp(node->key, key) != 0) {
151                 node = node->next;
152                 continue;
153             }
154 
155             // size mismatch
156             if (node->value == NULL || node->valueSize != valueSize) {
157                 return HDF_ERR_INVALID_OBJECT;
158             }
159             // update k-v node
160             if (memcpy_s(node->value, node->valueSize, value, valueSize) != EOK) {
161                 return HDF_FAILURE;
162             }
163 
164             return HDF_SUCCESS;
165         }
166     }
167     // Increase the bucket size when nodes is nullptr
168     if (map->nodes == NULL) {
169         MapInit(map);
170         if (MapResize(map, HDF_MIN_MAP_SIZE) != HDF_SUCCESS) {
171             return HDF_FAILURE;
172         }
173     }
174     // Increase the bucket size to decrease the possibility of map search conflict.
175     if (map->nodeSize >= map->bucketSize) {
176         uint32_t size = (map->bucketSize < HDF_MIN_MAP_SIZE) ? HDF_MIN_MAP_SIZE : \
177             (map->bucketSize << HDF_ENLARGE_FACTOR);
178         if (MapResize(map, size) != HDF_SUCCESS) {
179             return HDF_FAILURE;
180         }
181     }
182     node = MapCreateNode(key, hash, value, valueSize);
183     if (node == NULL) {
184         return HDF_ERR_INVALID_OBJECT;
185     }
186     MapAddNode(map, node);
187     map->nodeSize++;
188     return HDF_SUCCESS;
189 }
190 
MapGet(const Map * map,const char * key)191 void* MapGet(const Map *map, const char *key)
192 {
193     uint32_t hash;
194     uint32_t idx;
195     struct MapNode *node = NULL;
196 
197     if (map == NULL || key == NULL || map->nodeSize == 0 || map->nodes == NULL) {
198         return NULL;
199     }
200 
201     hash = MapHash(key);
202     idx = MapHashIdx(map, hash);
203     node = map->nodes[idx];
204 
205     while (node != NULL) {
206         if (node->hash == hash && node->key != NULL && !strcmp(node->key, key)) {
207             return node->value;
208         }
209 
210         node = node->next;
211     }
212 
213     return NULL;
214 }
215 
MapErase(Map * map,const char * key)216 int32_t MapErase(Map *map, const char *key)
217 {
218     uint32_t hash;
219     uint32_t idx;
220     struct MapNode *node = NULL;
221     struct MapNode *prev = NULL;
222 
223     if (map == NULL || key == NULL || map->nodeSize == 0 || map->nodes == NULL) {
224         return HDF_ERR_INVALID_PARAM;
225     }
226 
227     hash = MapHash(key);
228     idx = MapHashIdx(map, hash);
229     node = map->nodes[idx];
230     prev = node;
231 
232     while (node != NULL) {
233         if (node->hash == hash && node->key != NULL && !strcmp(node->key, key)) {
234             if (map->nodes[idx] == node) {
235                 map->nodes[idx] = node->next;
236             } else {
237                 prev->next = node->next;
238             }
239             OsalMemFree(node);
240             map->nodeSize--;
241             return HDF_SUCCESS;
242         }
243         prev = node;
244         node = node->next;
245     }
246 
247     return HDF_FAILURE;
248 }
249 
MapInit(Map * map)250 void MapInit(Map *map)
251 {
252     if (map == NULL) {
253         return;
254     }
255 
256     map->nodes = NULL;
257     map->nodeSize = 0;
258     map->bucketSize = 0;
259 }
260 
MapDelete(Map * map)261 void MapDelete(Map *map)
262 {
263     uint32_t i;
264     struct MapNode *node = NULL;
265     struct MapNode *next = NULL;
266 
267     if (map == NULL || map->nodes == NULL) {
268         return;
269     }
270 
271     for (i = 0; i < map->bucketSize; i++) {
272         node = map->nodes[i];
273         while (node != NULL) {
274             next = node->next;
275             OsalMemFree(node);
276             node = next;
277         }
278     }
279 
280     OsalMemFree(map->nodes);
281 
282     map->nodes = NULL;
283     map->nodeSize = 0;
284     map->bucketSize = 0;
285 }
286 
287