1 /*
2 * Copyright (c) 2021 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "lnn_map.h"
17
18 #include <stdlib.h>
19 #include <string.h>
20
21 #include <securec.h>
22
23 #include "softbus_adapter_mem.h"
24 #include "softbus_def.h"
25 #include "softbus_errcode.h"
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 3000
31 #define SHIFT_ALIGN_BYTE 4
32
33 /* BKDR Hash */
MapHash(const char * key)34 static uint32_t MapHash(const char *key)
35 {
36 uint32_t hash = 0;
37 const uint32_t seed = 131;
38 if (key == NULL) {
39 return 0;
40 }
41 uint32_t len = strlen(key);
42 for (uint32_t i = 0; i < len; i++) {
43 hash = (hash * seed) + (*key++);
44 }
45
46 return (hash & 0x7FFFFFFF);
47 }
48
MapHashIdx(const Map * map,uint32_t hash)49 static uint32_t MapHashIdx(const Map *map, uint32_t hash)
50 {
51 return (hash & (map->bucketSize - 1));
52 }
53
MapAddNode(Map * map,MapNode * node)54 static void MapAddNode(Map *map, 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 MapNode **nodes = NULL;
65 MapNode **tmp = NULL;
66
67 nodes = (MapNode **)SoftBusCalloc(size * sizeof(*nodes));
68 if (nodes == NULL) {
69 return SOFTBUS_MEM_ERR;
70 }
71
72 tmp = map->nodes;
73 bucketSize = map->bucketSize;
74 map->nodes = nodes;
75 map->bucketSize = size;
76
77 if (tmp != NULL) {
78 MapNode *node = NULL;
79 MapNode *next = NULL;
80
81 /* remap node with new map size */
82 for (uint32_t i = 0; i < bucketSize; i++) {
83 node = tmp[i];
84 while (node != NULL) {
85 next = node->next;
86 MapAddNode(map, node);
87 node = next;
88 }
89 }
90 SoftBusFree(tmp);
91 }
92 return SOFTBUS_OK;
93 }
94
MapCreateNode(const char * key,uint32_t hash,const void * value,uint32_t valueSize)95 static MapNode *MapCreateNode(const char *key, uint32_t hash,
96 const void *value, uint32_t valueSize)
97 {
98 uint32_t keySize = strlen(key) + 1;
99 keySize = keySize + (SHIFT_ALIGN_BYTE - keySize % SHIFT_ALIGN_BYTE);
100 MapNode *node = (MapNode *)SoftBusCalloc(sizeof(*node) + keySize + valueSize);
101 if (node == NULL) {
102 return NULL;
103 }
104
105 node->hash = hash;
106 node->key = (uint8_t *)node + sizeof(*node);
107 node->value = (uint8_t *)node + sizeof(*node) + keySize;
108 node->valueSize = valueSize;
109 if (memcpy_s(node->key, keySize, key, strlen(key) + 1) != EOK) {
110 SoftBusFree(node);
111 return NULL;
112 }
113 if (memcpy_s(node->value, node->valueSize, value, valueSize) != EOK) {
114 SoftBusFree(node);
115 return NULL;
116 }
117 return node;
118 }
119
120 /**
121 * Add map element
122 *
123 * @param : map Map see details in type Map
124 * key Map key
125 * value Map value
126 * valueSize Map value size
127 * @return : SOFTBUS_OK or other error
128 */
LnnMapSet(Map * map,const char * key,const void * value,uint32_t valueSize)129 NO_SANITIZE("cfi") int32_t LnnMapSet(Map *map, const char *key, const void *value, uint32_t valueSize)
130 {
131 MapNode *node = NULL;
132
133 if (map == NULL || key == NULL || value == NULL || valueSize == 0) {
134 return SOFTBUS_INVALID_PARAM;
135 }
136 if (valueSize > HDF_MAP_VALUE_MAX_SIZE || strlen(key) > HDF_MAP_KEY_MAX_SIZE) {
137 return SOFTBUS_INVALID_PARAM;
138 }
139 uint32_t hash = MapHash(key);
140 if (map->nodeSize > 0 && map->nodes != NULL) {
141 uint32_t idx = MapHashIdx(map, hash);
142 node = map->nodes[idx];
143 while (node != NULL) {
144 if (node->hash != hash || node->key == NULL || strcmp(node->key, key) != 0) {
145 node = node->next;
146 continue;
147 }
148
149 // size unmatch
150 if (node->value == NULL || node->valueSize != valueSize) {
151 return SOFTBUS_INVALID_PARAM;
152 }
153 // update k-v node
154 if (memcpy_s(node->value, node->valueSize, value, valueSize) != EOK) {
155 return SOFTBUS_ERR;
156 }
157
158 return SOFTBUS_OK;
159 }
160 }
161 // for decreasing map search conflict, enlarge bucket Size
162 if (map->nodeSize >= map->bucketSize) {
163 uint32_t size = (map->bucketSize < HDF_MIN_MAP_SIZE) ? HDF_MIN_MAP_SIZE : \
164 (map->bucketSize << HDF_ENLARGE_FACTOR);
165 MapResize(map, size);
166 }
167
168 if (map->nodes == NULL) {
169 return SOFTBUS_ERR;
170 }
171 node = MapCreateNode(key, hash, value, valueSize);
172 if (node == NULL) {
173 return SOFTBUS_INVALID_PARAM;
174 }
175 MapAddNode(map, node);
176 map->nodeSize++;
177
178 return SOFTBUS_OK;
179 }
180
181 /**
182 * Get map value api
183 *
184 * @param : map Map see details in type Map
185 * key Map key
186 * @return : value of key or NULL
187 */
LnnMapGet(const Map * map,const char * key)188 NO_SANITIZE("cfi") void* LnnMapGet(const Map *map, const char *key)
189 {
190 if (map == NULL || key == NULL || map->nodeSize == 0 || map->nodes == NULL) {
191 return NULL;
192 }
193
194 uint32_t hash = MapHash(key);
195 uint32_t idx = MapHashIdx(map, hash);
196 MapNode *node = map->nodes[idx];
197
198 while (node != NULL) {
199 if (node->hash == hash && node->key != NULL && !strcmp(node->key, key)) {
200 return node->value;
201 }
202
203 node = node->next;
204 }
205
206 return NULL;
207 }
208
209 /**
210 * Erase map node
211 *
212 * @param : map Map see details in type Map
213 * key Map key
214 */
LnnMapErase(Map * map,const char * key)215 NO_SANITIZE("cfi") int32_t LnnMapErase(Map *map, const char *key)
216 {
217 if (map == NULL || key == NULL || map->nodeSize == 0 || map->nodes == NULL) {
218 return SOFTBUS_INVALID_PARAM;
219 }
220
221 uint32_t hash = MapHash(key);
222 uint32_t idx = MapHashIdx(map, hash);
223 MapNode *node = map->nodes[idx];
224 MapNode *prev = node;
225
226 while (node != NULL) {
227 if (node->hash == hash && node->key != NULL && !strcmp(node->key, key)) {
228 if (map->nodes[idx] == node) {
229 map->nodes[idx] = node->next;
230 } else {
231 prev->next = node->next;
232 }
233 SoftBusFree(node);
234 map->nodeSize--;
235 return SOFTBUS_OK;
236 }
237 prev = node;
238 node = node->next;
239 }
240
241 return SOFTBUS_ERR;
242 }
243
MapGetSize(Map * map)244 NO_SANITIZE("cfi") uint32_t MapGetSize(Map *map)
245 {
246 return (map == NULL) ? 0 : map->nodeSize;
247 }
248 /**
249 * initialize map
250 *
251 * @param : map Map see details in type Map
252 */
LnnMapInit(Map * map)253 NO_SANITIZE("cfi") void LnnMapInit(Map *map)
254 {
255 if (map == NULL) {
256 return;
257 }
258
259 map->nodes = NULL;
260 map->nodeSize = 0;
261 map->bucketSize = 0;
262 }
263
264 /**
265 * delete map, free the map memory
266 *
267 * @param : map Map see details in type Map
268 */
LnnMapDelete(Map * map)269 NO_SANITIZE("cfi") void LnnMapDelete(Map *map)
270 {
271 uint32_t i;
272 MapNode *node = NULL;
273 MapNode *next = NULL;
274
275 if (map == NULL || map->nodes == NULL) {
276 return;
277 }
278
279 for (i = 0; i < map->bucketSize; i++) {
280 node = map->nodes[i];
281 while (node != NULL) {
282 next = node->next;
283 SoftBusFree(node);
284 node = next;
285 }
286 }
287
288 SoftBusFree(map->nodes);
289
290 map->nodes = NULL;
291 map->nodeSize = 0;
292 map->bucketSize = 0;
293 }
294
295 /**
296 * init LNN map iterator
297 *
298 * @param : map Map see details in type Map
299 */
LnnMapInitIterator(Map * map)300 NO_SANITIZE("cfi") MapIterator *LnnMapInitIterator(Map *map)
301 {
302 MapIterator *it = NULL;
303 if (map == NULL) {
304 return NULL;
305 }
306 it = (MapIterator *)SoftBusCalloc(sizeof(MapIterator));
307 if (it == NULL) {
308 return NULL;
309 }
310 it->node = NULL;
311 it->bucketNum = 0;
312 it->nodeNum = 0;
313 it->map = map;
314 return it;
315 }
316
317 /**
318 * Have a next element
319 *
320 * @param : it Iterator see details in type Iterator
321 */
LnnMapHasNext(MapIterator * it)322 NO_SANITIZE("cfi") bool LnnMapHasNext(MapIterator *it)
323 {
324 return (it->nodeNum < it->map->nodeSize);
325 }
326
327 /**
328 * Get next iterator API
329 *
330 * @param : it Iterator see details in type Iterator
331 */
LnnMapNext(MapIterator * it)332 NO_SANITIZE("cfi") MapIterator *LnnMapNext(MapIterator *it)
333 {
334 MapNode *node = NULL;
335 if (it == NULL) {
336 return NULL;
337 }
338 if (LnnMapHasNext(it)) {
339 if (it->node != NULL && it->node->next != NULL) {
340 it->nodeNum++;
341 it->node = it->node->next;
342 return it;
343 }
344 while (it->bucketNum < it->map->bucketSize) {
345 node = it->map->nodes[it->bucketNum];
346 it->bucketNum++;
347 if (node != NULL) {
348 it->nodeNum++;
349 it->node = node;
350 return it;
351 }
352 }
353 }
354 return it;
355 }
356
357 /**
358 * deinit iterator and free memory API
359 *
360 * @param : it Iterator see details in type Iterator
361 */
LnnMapDeinitIterator(MapIterator * it)362 NO_SANITIZE("cfi") void LnnMapDeinitIterator(MapIterator *it)
363 {
364 if (it == NULL) {
365 return;
366 }
367 SoftBusFree(it);
368 }