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