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) {
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
MapSet(Map * map,const char * key,const void * value,uint32_t valueSize)119 int32_t MapSet(Map *map, const char *key, const void *value, uint32_t valueSize)
120 {
121 struct MapNode *node = NULL;
122 uint32_t hash;
123
124 if (map == NULL || key == NULL || value == NULL || valueSize == 0) {
125 return HDF_ERR_INVALID_PARAM;
126 }
127 if (valueSize > HDF_MAP_KEY_MAX_SIZE || strlen(key) > HDF_MAP_VALUE_MAX_SIZE) {
128 return HDF_ERR_INVALID_PARAM;
129 }
130 hash = MapHash(key);
131 if (map->nodeSize > 0 && map->nodes != NULL) {
132 uint32_t idx = MapHashIdx(map, hash);
133 node = map->nodes[idx];
134 while (node != NULL) {
135 if (node->hash != hash || node->key == NULL || strcmp(node->key, key) != 0) {
136 node = node->next;
137 continue;
138 }
139
140 // size mismatch
141 if (node->value == NULL || node->valueSize != valueSize) {
142 return HDF_ERR_INVALID_OBJECT;
143 }
144 // update k-v node
145 if (memcpy_s(node->value, node->valueSize, value, valueSize) != EOK) {
146 return HDF_FAILURE;
147 }
148
149 return HDF_SUCCESS;
150 }
151 }
152 // Increase the bucket size to decrease the possibility of map search conflict.
153 if (map->nodeSize >= map->bucketSize) {
154 uint32_t size = (map->bucketSize < HDF_MIN_MAP_SIZE) ? HDF_MIN_MAP_SIZE : \
155 (map->bucketSize << HDF_ENLARGE_FACTOR);
156 MapResize(map, size);
157 }
158
159 node = MapCreateNode(key, hash, value, valueSize);
160 if (node == NULL) {
161 return HDF_ERR_INVALID_OBJECT;
162 }
163 MapAddNode(map, node);
164 map->nodeSize++;
165
166 return HDF_SUCCESS;
167 }
168
MapGet(const Map * map,const char * key)169 void* MapGet(const Map *map, const char *key)
170 {
171 uint32_t hash;
172 uint32_t idx;
173 struct MapNode *node = NULL;
174
175 if (map == NULL || key == NULL || map->nodeSize == 0 || map->nodes == NULL) {
176 return NULL;
177 }
178
179 hash = MapHash(key);
180 idx = MapHashIdx(map, hash);
181 node = map->nodes[idx];
182
183 while (node != NULL) {
184 if (node->hash == hash && node->key != NULL && !strcmp(node->key, key)) {
185 return node->value;
186 }
187
188 node = node->next;
189 }
190
191 return NULL;
192 }
193
MapErase(Map * map,const char * key)194 int32_t MapErase(Map *map, const char *key)
195 {
196 uint32_t hash;
197 uint32_t idx;
198 struct MapNode *node = NULL;
199 struct MapNode *prev = NULL;
200
201 if (map == NULL || key == NULL || map->nodeSize == 0 || map->nodes == NULL) {
202 return HDF_ERR_INVALID_PARAM;
203 }
204
205 hash = MapHash(key);
206 idx = MapHashIdx(map, hash);
207 node = map->nodes[idx];
208 prev = node;
209
210 while (node != NULL) {
211 if (node->hash == hash && node->key != NULL && !strcmp(node->key, key)) {
212 if (map->nodes[idx] == node) {
213 map->nodes[idx] = node->next;
214 } else {
215 prev->next = node->next;
216 }
217 OsalMemFree(node);
218 map->nodeSize--;
219 return HDF_SUCCESS;
220 }
221 prev = node;
222 node = node->next;
223 }
224
225 return HDF_FAILURE;
226 }
227
MapInit(Map * map)228 void MapInit(Map *map)
229 {
230 if (map == NULL) {
231 return;
232 }
233
234 map->nodes = NULL;
235 map->nodeSize = 0;
236 map->bucketSize = 0;
237 }
238
MapDelete(Map * map)239 void MapDelete(Map *map)
240 {
241 uint32_t i;
242 struct MapNode *node = NULL;
243 struct MapNode *next = NULL;
244
245 if (map == NULL || map->nodes == NULL) {
246 return;
247 }
248
249 for (i = 0; i < map->bucketSize; i++) {
250 node = map->nodes[i];
251 while (node != NULL) {
252 next = node->next;
253 OsalMemFree(node);
254 node = next;
255 }
256 }
257
258 OsalMemFree(map->nodes);
259
260 map->nodes = NULL;
261 map->nodeSize = 0;
262 map->bucketSize = 0;
263 }
264
265