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