1 /*
2 * Copyright (c) 2025 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 "netstack_hash_map.h"
17 #include "net_http_inner_types.h"
18 #include "netstack_log.h"
19
20 #define NETSTACK_HASH_FACTOR 31
21
Netstack_Hash(const char * key,uint32_t capacity)22 static uint32_t Netstack_Hash(const char *key, uint32_t capacity)
23 {
24 uint32_t hash = 0;
25 for (uint32_t i = 0; i < strlen(key); i++) {
26 hash = NETSTACK_HASH_FACTOR * hash + key[i];
27 }
28 return hash % capacity;
29 }
30
CreateMap(void)31 Netstack_HashMap *CreateMap(void)
32 {
33 Netstack_HashMap *map = (Netstack_HashMap *)malloc(sizeof(Netstack_HashMap));
34 if (map == nullptr) {
35 NETSTACK_LOGE("failed to alloc memory for map");
36 return nullptr;
37 }
38 map->capacity = DEFAULT_MAP_CAPACITY;
39 map->size = 0;
40 map->entries = (Netstack_HashMapEntry **)calloc(map->capacity, sizeof(Netstack_HashMapEntry *));
41 if (map->entries == nullptr) {
42 NETSTACK_LOGE("failed to alloc memory for map entries");
43 free(map);
44 return nullptr;
45 }
46
47 return map;
48 }
49
Netstack_RehashEntry(Netstack_HashMapEntry * currentPtr,uint32_t newCapacity,Netstack_HashMapEntry ** newEntries)50 static uint32_t Netstack_RehashEntry(Netstack_HashMapEntry *currentPtr,
51 uint32_t newCapacity, Netstack_HashMapEntry **newEntries)
52 {
53 uint32_t size = 0;
54 Netstack_HashMapEntry *nextPtr;
55 do {
56 nextPtr = currentPtr->next;
57 uint32_t newHash = Netstack_Hash(currentPtr->key, newCapacity);
58 if (newEntries[newHash] == nullptr) {
59 newEntries[newHash] = currentPtr;
60 newEntries[newHash]->next = nullptr;
61 size++;
62 } else {
63 currentPtr->next = newEntries[newHash]->next;
64 newEntries[newHash]->next = currentPtr;
65 }
66 currentPtr = nextPtr;
67 } while (currentPtr != nullptr);
68 return size;
69 }
70
NetstackInvalidMap(Netstack_HashMap * map)71 static bool NetstackInvalidMap(Netstack_HashMap *map)
72 {
73 return map == nullptr || map->entries == nullptr || map->capacity < DEFAULT_MAP_CAPACITY ||
74 map->capacity > MAX_MAP_CAPACITY;
75 }
76
NetstackResizeMap(Netstack_HashMap * map)77 static uint32_t NetstackResizeMap(Netstack_HashMap *map)
78 {
79 if (map->capacity >= MAX_MAP_CAPACITY) {
80 NETSTACK_LOGE("map capacity reaches max, skip resize");
81 return OH_HTTP_PARAMETER_ERROR;
82 }
83 uint32_t newCapacity = map->capacity * 2;
84 Netstack_HashMapEntry **newEntries = (Netstack_HashMapEntry **)calloc(newCapacity, sizeof(Netstack_HashMapEntry *));
85 if (newEntries == nullptr) {
86 NETSTACK_LOGE("failed to insert map: no memory for resize");
87 return OH_HTTP_OUT_OF_MEMORY;
88 }
89
90 map->size = 0;
91 for (uint32_t i = 0; i < map->capacity; i++) {
92 if (map->entries[i] != nullptr && map->entries[i]->key != nullptr) {
93 map->size += Netstack_RehashEntry(map->entries[i], newCapacity, newEntries);
94 }
95 }
96
97 NETSTACK_LOGI("success to resize map from %{public}u to %{public}u", map->capacity, newCapacity);
98 free(map->entries);
99 map->entries = newEntries;
100 map->capacity = newCapacity;
101
102 return OH_HTTP_RESULT_OK;
103 }
104
Netstack_PutMapEntry(Netstack_HashMap * map,const char * key,void * value)105 uint32_t Netstack_PutMapEntry(Netstack_HashMap *map, const char *key, void *value)
106 {
107 if (NetstackInvalidMap(map) || key == nullptr) {
108 return OH_HTTP_PARAMETER_ERROR;
109 }
110
111 if (map->size >= map->capacity) {
112 (void)NetstackResizeMap(map);
113 }
114
115 uint32_t idx = Netstack_Hash(key, map->capacity);
116 // set first entry
117 if (map->entries[idx] == nullptr) {
118 Netstack_HashMapEntry *entry = (Netstack_HashMapEntry *)malloc(sizeof(Netstack_HashMapEntry));
119 if (entry == nullptr) {
120 NETSTACK_LOGE("failed to alloc map entry");
121 return OH_HTTP_OUT_OF_MEMORY;
122 }
123 entry->key = strdup(key);
124 if (entry->key == nullptr) {
125 free(entry);
126 return OH_HTTP_OUT_OF_MEMORY;
127 }
128 entry->value = value;
129 entry->next = nullptr;
130 map->entries[idx] = entry;
131 map->size++;
132 return OH_HTTP_RESULT_OK;
133 }
134
135 Netstack_HashMapEntry *ptr = map->entries[idx];
136 while (ptr != nullptr) {
137 // replace exist entry
138 if (strcmp(ptr->key, key) == 0) {
139 ptr->value = value;
140 return OH_HTTP_RESULT_OK;
141 }
142 ptr = ptr->next;
143 }
144
145 // insert after first entry
146 Netstack_HashMapEntry *entry = (Netstack_HashMapEntry *)malloc(sizeof(Netstack_HashMapEntry));
147 if (entry == nullptr) {
148 return OH_HTTP_OUT_OF_MEMORY;
149 }
150 entry->key = strdup(key);
151 if (entry->key == nullptr) {
152 free(entry);
153 return OH_HTTP_OUT_OF_MEMORY;
154 }
155 entry->value = value;
156 entry->next = map->entries[idx]->next;
157 map->entries[idx]->next = entry;
158
159 return OH_HTTP_RESULT_OK;
160 }
161
Netstack_GetMapEntry(Netstack_HashMap * map,const char * key)162 void *Netstack_GetMapEntry(Netstack_HashMap *map, const char *key)
163 {
164 if (NetstackInvalidMap(map) || key == nullptr) {
165 return nullptr;
166 }
167
168 uint32_t idx = Netstack_Hash(key, map->capacity);
169 Netstack_HashMapEntry *entry = map->entries[idx];
170 while (entry != nullptr) {
171 if (strcmp(entry->key, key) == 0) {
172 return entry->value;
173 }
174 entry = entry->next;
175 }
176 return nullptr;
177 }
178
Netstack_DeleteMapEntry(Netstack_HashMap * map,const char * key)179 uint32_t Netstack_DeleteMapEntry(Netstack_HashMap *map, const char *key)
180 {
181 if (NetstackInvalidMap(map) || key == nullptr) {
182 return OH_HTTP_PARAMETER_ERROR;
183 }
184
185 uint32_t idx = Netstack_Hash(key, map->capacity);
186 if (map->entries[idx] == nullptr) {
187 return OH_HTTP_RESULT_OK;
188 }
189
190 if (strcmp(map->entries[idx]->key, key) == 0) {
191 Netstack_HashMapEntry *entry = map->entries[idx];
192 map->entries[idx] = map->entries[idx]->next;
193 free(entry->key);
194 free(entry);
195 if (map->entries[idx] == nullptr) {
196 map->size--;
197 }
198 return OH_HTTP_RESULT_OK;
199 }
200
201 Netstack_HashMapEntry *prev = map->entries[idx];
202 Netstack_HashMapEntry *entry = map->entries[idx]->next;
203 while (entry != nullptr) {
204 if (strcmp(entry->key, key) == 0) {
205 prev->next = entry->next;
206 free(entry->key);
207 free(entry);
208 return OH_HTTP_RESULT_OK;
209 }
210 prev = entry;
211 entry = entry->next;
212 }
213 return OH_HTTP_RESULT_OK;
214 }
215
Netstack_DestroyMapWithValue(Netstack_HashMap * map,Netstack_DestroyValueFunction destroyFunction)216 void Netstack_DestroyMapWithValue(Netstack_HashMap *map, Netstack_DestroyValueFunction destroyFunction)
217 {
218 if (NetstackInvalidMap(map)) {
219 return;
220 }
221 Netstack_HashMapEntry *entry;
222 Netstack_HashMapEntry *next;
223 for (uint32_t i = 0; i < map->capacity; i++) {
224 entry = map->entries[i];
225 while (entry != nullptr) {
226 next = entry->next;
227 entry->next = nullptr;
228 free(entry->key);
229 entry->key = nullptr;
230 if (destroyFunction != nullptr) {
231 destroyFunction(entry->value);
232 entry->value = nullptr;
233 }
234 free(entry);
235 map->entries[i] = nullptr;
236 entry = next;
237 }
238 }
239 free(map->entries);
240 map->entries = nullptr;
241 free(map);
242 }
243
Netstack_DestroyMap(Netstack_HashMap * map)244 void Netstack_DestroyMap(Netstack_HashMap *map)
245 {
246 Netstack_DestroyMapWithValue(map, nullptr);
247 }
248
Netstack_CreateMapIterator(Netstack_HashMap * map)249 Netstack_MapIterator *Netstack_CreateMapIterator(Netstack_HashMap *map)
250 {
251 if (NetstackInvalidMap(map)) {
252 NETSTACK_LOGE("create map iterator failed: invalid map");
253 return nullptr;
254 }
255 Netstack_MapIterator *iterator = (Netstack_MapIterator *)malloc(sizeof(Netstack_MapIterator));
256 if (iterator == nullptr) {
257 NETSTACK_LOGE("failed to alloc memory for map iterator");
258 return nullptr;
259 }
260 iterator->map = map;
261 for (uint32_t i = 0; i < map->capacity; i++) {
262 if (map->entries[i] != nullptr) {
263 iterator->currentIdx = i;
264 iterator->currentEntry = map->entries[i];
265 return iterator;
266 }
267 }
268 NETSTACK_LOGI("map is empty, skip create map iterator");
269 free(iterator);
270 return nullptr;
271 }
272
Netstack_MapIterateNext(Netstack_MapIterator * iterator)273 void Netstack_MapIterateNext(Netstack_MapIterator *iterator)
274 {
275 if (iterator == nullptr || iterator->currentEntry == nullptr || NetstackInvalidMap(iterator->map) ||
276 iterator->currentIdx >= iterator->map->capacity) {
277 return;
278 }
279
280 if (iterator->currentEntry->next != nullptr) {
281 iterator->currentEntry = iterator->currentEntry->next;
282 return;
283 }
284
285 for (uint32_t i = iterator->currentIdx + 1; i < iterator->map->capacity; i++) {
286 if (iterator->map->entries[i] != nullptr) {
287 iterator->currentEntry = iterator->map->entries[i];
288 iterator->currentIdx = i;
289 return;
290 }
291 }
292
293 iterator->currentEntry = nullptr;
294 iterator->currentIdx = iterator->map->capacity;
295 }
296
Netstack_DestroyMapIterator(Netstack_MapIterator * iterator)297 void Netstack_DestroyMapIterator(Netstack_MapIterator *iterator)
298 {
299 free(iterator);
300 }