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 "lnn_log.h"
24 #include "softbus_adapter_mem.h"
25 #include "softbus_def.h"
26 #include "softbus_errcode.h"
27
28 #define HDF_MIN_MAP_SIZE 8
29 #define HDF_ENLARGE_FACTOR 2
30 #define HDF_MAP_KEY_MAX_SIZE 1000
31 #define HDF_MAP_VALUE_MAX_SIZE 4000
32 #define SHIFT_ALIGN_BYTE 4
33
34 /* BKDR Hash */
MapHash(const char * key)35 static uint32_t MapHash(const char *key)
36 {
37 uint32_t hash = 0;
38 const uint32_t seed = 131;
39 if (key == NULL) {
40 return 0;
41 }
42 uint32_t len = strlen(key);
43 for (uint32_t i = 0; i < len; i++) {
44 hash = (hash * seed) + (*key++);
45 }
46
47 return (hash & 0x7FFFFFFF);
48 }
49
MapHashIdx(const Map * map,uint32_t hash)50 static int32_t MapHashIdx(const Map *map, uint32_t hash)
51 {
52 if (map->bucketSize < 1) {
53 return -1;
54 }
55 return (int32_t)(hash & (map->bucketSize - 1));
56 }
57
MapAddNode(Map * map,MapNode * node)58 static void MapAddNode(Map *map, MapNode *node)
59 {
60 int32_t idx = MapHashIdx(map, node->hash);
61 if (idx < 0) {
62 LNN_LOGE(LNN_STATE, "invalid param, get map hash idx failed");
63 return;
64 }
65 node->next = map->nodes[idx];
66 map->nodes[idx] = node;
67 }
68
MapResize(Map * map,uint32_t size)69 static int32_t MapResize(Map *map, uint32_t size)
70 {
71 uint32_t bucketSize;
72 MapNode **nodes = NULL;
73 MapNode **tmp = NULL;
74
75 nodes = (MapNode **)SoftBusCalloc(size * sizeof(*nodes));
76 if (nodes == NULL) {
77 LNN_LOGE(LNN_STATE, "calloc node fail");
78 return SOFTBUS_MEM_ERR;
79 }
80
81 tmp = map->nodes;
82 bucketSize = map->bucketSize;
83 map->nodes = nodes;
84 map->bucketSize = size;
85
86 if (tmp != NULL) {
87 MapNode *node = NULL;
88 MapNode *next = NULL;
89
90 /* remap node with new map size */
91 for (uint32_t i = 0; i < bucketSize; i++) {
92 node = tmp[i];
93 while (node != NULL) {
94 next = node->next;
95 MapAddNode(map, node);
96 node = next;
97 }
98 }
99 SoftBusFree(tmp);
100 }
101 return SOFTBUS_OK;
102 }
103
MapCreateNode(const char * key,uint32_t hash,const void * value,uint32_t valueSize)104 static MapNode *MapCreateNode(const char *key, uint32_t hash,
105 const void *value, uint32_t valueSize)
106 {
107 uint32_t keySize = strlen(key) + 1;
108 keySize = keySize + (SHIFT_ALIGN_BYTE - keySize % SHIFT_ALIGN_BYTE);
109 MapNode *node = (MapNode *)SoftBusCalloc(sizeof(*node) + keySize + valueSize);
110 if (node == NULL) {
111 LNN_LOGE(LNN_STATE, "calloc node fail");
112 return NULL;
113 }
114
115 node->hash = hash;
116 node->key = (uint8_t *)node + sizeof(*node);
117 node->value = (uint8_t *)node + sizeof(*node) + keySize;
118 node->valueSize = valueSize;
119 if (memcpy_s(node->key, keySize, key, strlen(key) + 1) != EOK) {
120 LNN_LOGE(LNN_STATE, "memcpy node key fail");
121 SoftBusFree(node);
122 return NULL;
123 }
124 if (memcpy_s(node->value, node->valueSize, value, valueSize) != EOK) {
125 LNN_LOGE(LNN_STATE, "memcpy node value fail");
126 SoftBusFree(node);
127 return NULL;
128 }
129 return node;
130 }
131
132 /**
133 * Add map element
134 *
135 * @param : map Map see details in type Map
136 * key Map key
137 * value Map value
138 * valueSize Map value size
139 * @return : SOFTBUS_OK or other error
140 */
LnnMapSet(Map * map,const char * key,const void * value,uint32_t valueSize)141 int32_t LnnMapSet(Map *map, const char *key, const void *value, uint32_t valueSize)
142 {
143 MapNode *node = NULL;
144
145 bool isParamsInvalid = (map == NULL || key == NULL || value == NULL || valueSize == 0);
146 if (isParamsInvalid) {
147 return SOFTBUS_INVALID_PARAM;
148 }
149 if (valueSize > HDF_MAP_VALUE_MAX_SIZE || strlen(key) > HDF_MAP_KEY_MAX_SIZE) {
150 return SOFTBUS_INVALID_PARAM;
151 }
152 uint32_t hash = MapHash(key);
153 if (map->nodeSize > 0 && map->nodes != NULL) {
154 int32_t idx = MapHashIdx(map, hash);
155 if (idx < 0) {
156 LNN_LOGE(LNN_STATE, "invalid param, get map hash idx failed");
157 return SOFTBUS_INVALID_PARAM;
158 }
159 node = map->nodes[idx];
160 while (node != NULL) {
161 if (node->hash != hash || node->key == NULL || strcmp(node->key, key) != 0) {
162 node = node->next;
163 continue;
164 }
165
166 // size unmatch
167 if (node->value == NULL || node->valueSize != valueSize) {
168 return SOFTBUS_INVALID_PARAM;
169 }
170 // update k-v node
171 if (memcpy_s(node->value, node->valueSize, value, valueSize) != EOK) {
172 return SOFTBUS_ERR;
173 }
174
175 return SOFTBUS_OK;
176 }
177 }
178 // for decreasing map search conflict, enlarge bucket Size
179 if (map->nodeSize >= map->bucketSize) {
180 uint32_t size = (map->bucketSize < HDF_MIN_MAP_SIZE) ? HDF_MIN_MAP_SIZE : \
181 (map->bucketSize << HDF_ENLARGE_FACTOR);
182 MapResize(map, size);
183 }
184
185 if (map->nodes == NULL) {
186 LNN_LOGE(LNN_STATE, "map node is null");
187 return SOFTBUS_ERR;
188 }
189 node = MapCreateNode(key, hash, value, valueSize);
190 if (node == NULL) {
191 LNN_LOGE(LNN_STATE, "create node fail");
192 return SOFTBUS_INVALID_PARAM;
193 }
194 MapAddNode(map, node);
195 map->nodeSize++;
196
197 return SOFTBUS_OK;
198 }
199
200 /**
201 * Get map value api
202 *
203 * @param : map Map see details in type Map
204 * key Map key
205 * @return : value of key or NULL
206 */
LnnMapGet(const Map * map,const char * key)207 void* LnnMapGet(const Map *map, const char *key)
208 {
209 if (map == NULL || key == NULL || map->nodeSize == 0 || map->nodes == NULL) {
210 LNN_LOGE(LNN_STATE, "invalid param");
211 return NULL;
212 }
213
214 uint32_t hash = MapHash(key);
215 int32_t idx = MapHashIdx(map, hash);
216 if (idx < 0) {
217 LNN_LOGE(LNN_STATE, "invalid param, get map hash idx failed");
218 return NULL;
219 }
220 MapNode *node = map->nodes[idx];
221
222 while (node != NULL) {
223 if (node->hash == hash && node->key != NULL && !strcmp(node->key, key)) {
224 return node->value;
225 }
226
227 node = node->next;
228 }
229
230 return NULL;
231 }
232
233 /**
234 * Erase map node
235 *
236 * @param : map Map see details in type Map
237 * key Map key
238 */
LnnMapErase(Map * map,const char * key)239 int32_t LnnMapErase(Map *map, const char *key)
240 {
241 if (map == NULL || key == NULL || map->nodeSize == 0 || map->nodes == NULL) {
242 LNN_LOGE(LNN_STATE, "invalid param");
243 return SOFTBUS_INVALID_PARAM;
244 }
245
246 uint32_t hash = MapHash(key);
247 int32_t idx = MapHashIdx(map, hash);
248 if (idx < 0) {
249 LNN_LOGE(LNN_STATE, "invalid param, get map hash idx failed");
250 return SOFTBUS_INVALID_PARAM;
251 }
252 MapNode *node = map->nodes[idx];
253 MapNode *prev = node;
254
255 while (node != NULL) {
256 if (node->hash == hash && node->key != NULL && !strcmp(node->key, key)) {
257 if (map->nodes[idx] == node) {
258 map->nodes[idx] = node->next;
259 } else {
260 prev->next = node->next;
261 }
262 SoftBusFree(node);
263 map->nodeSize--;
264 return SOFTBUS_OK;
265 }
266 prev = node;
267 node = node->next;
268 }
269
270 return SOFTBUS_ERR;
271 }
272
273 /**
274 * get map size
275 *
276 * @param : map Map see details in type Map
277 */
MapGetSize(Map * map)278 uint32_t MapGetSize(Map *map)
279 {
280 return (map == NULL) ? 0 : map->nodeSize;
281 }
282
283 /**
284 * initialize map
285 *
286 * @param : map Map see details in type Map
287 */
LnnMapInit(Map * map)288 void LnnMapInit(Map *map)
289 {
290 if (map == NULL) {
291 return;
292 }
293
294 map->nodes = NULL;
295 map->nodeSize = 0;
296 map->bucketSize = 0;
297 }
298
299 /**
300 * delete map, free the map memory
301 *
302 * @param : map Map see details in type Map
303 */
LnnMapDelete(Map * map)304 void LnnMapDelete(Map *map)
305 {
306 uint32_t i;
307 MapNode *node = NULL;
308 MapNode *next = NULL;
309
310 if (map == NULL || map->nodes == NULL) {
311 LNN_LOGE(LNN_STATE, "invalid param");
312 return;
313 }
314
315 for (i = 0; i < map->bucketSize; i++) {
316 node = map->nodes[i];
317 while (node != NULL) {
318 next = node->next;
319 SoftBusFree(node);
320 node = next;
321 }
322 }
323
324 SoftBusFree(map->nodes);
325
326 map->nodes = NULL;
327 map->nodeSize = 0;
328 map->bucketSize = 0;
329 }
330
331 /**
332 * init LNN map iterator
333 *
334 * @param : map Map see details in type Map
335 */
LnnMapInitIterator(Map * map)336 MapIterator *LnnMapInitIterator(Map *map)
337 {
338 MapIterator *it = NULL;
339 if (map == NULL) {
340 LNN_LOGE(LNN_STATE, "map is null");
341 return NULL;
342 }
343 it = (MapIterator *)SoftBusCalloc(sizeof(MapIterator));
344 if (it == NULL) {
345 LNN_LOGE(LNN_STATE, "calloc iterator fail");
346 return NULL;
347 }
348 it->node = NULL;
349 it->bucketNum = 0;
350 it->nodeNum = 0;
351 it->map = map;
352 return it;
353 }
354
355 /**
356 * Have a next element
357 *
358 * @param : it Iterator see details in type Iterator
359 */
LnnMapHasNext(MapIterator * it)360 bool LnnMapHasNext(MapIterator *it)
361 {
362 if (it->map->nodeSize > HDF_MAP_KEY_MAX_SIZE) {
363 LNN_LOGW(LNN_STATE, "nodeSize=%{public}d", it->map->nodeSize);
364 }
365 return (it->nodeNum < it->map->nodeSize);
366 }
367
368 /**
369 * Get next iterator API
370 *
371 * @param : it Iterator see details in type Iterator
372 */
LnnMapNext(MapIterator * it)373 MapIterator *LnnMapNext(MapIterator *it)
374 {
375 MapNode *node = NULL;
376 if (it == NULL) {
377 return NULL;
378 }
379 if (LnnMapHasNext(it)) {
380 if (it->node != NULL && it->node->next != NULL) {
381 it->nodeNum++;
382 it->node = it->node->next;
383 return it;
384 }
385 while (it->bucketNum < it->map->bucketSize) {
386 node = it->map->nodes[it->bucketNum];
387 it->bucketNum++;
388 if (node != NULL) {
389 it->nodeNum++;
390 it->node = node;
391 return it;
392 }
393 }
394 }
395 return it;
396 }
397
398 /**
399 * deinit iterator and free memory API
400 *
401 * @param : it Iterator see details in type Iterator
402 */
LnnMapDeinitIterator(MapIterator * it)403 void LnnMapDeinitIterator(MapIterator *it)
404 {
405 if (it == NULL) {
406 return;
407 }
408 SoftBusFree(it);
409 }