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