1 /*
2 ** Zabbix
3 ** Copyright (C) 2001-2021 Zabbix SIA
4 **
5 ** This program is free software; you can redistribute it and/or modify
6 ** it under the terms of the GNU General Public License as published by
7 ** the Free Software Foundation; either version 2 of the License, or
8 ** (at your option) any later version.
9 **
10 ** This program is distributed in the hope that it will be useful,
11 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
12 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 ** GNU General Public License for more details.
14 **
15 ** You should have received a copy of the GNU General Public License
16 ** along with this program; if not, write to the Free Software
17 ** Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 **/
19
20 #include "common.h"
21 #include "log.h"
22
23 #include "zbxalgo.h"
24
25 static void __hashset_free_entry(zbx_hashset_t *hs, ZBX_HASHSET_ENTRY_T *entry);
26
27 #define CRIT_LOAD_FACTOR 4/5
28 #define SLOT_GROWTH_FACTOR 3/2
29
30 #define ZBX_HASHSET_DEFAULT_SLOTS 10
31
32 /* private hashset functions */
33
__hashset_free_entry(zbx_hashset_t * hs,ZBX_HASHSET_ENTRY_T * entry)34 static void __hashset_free_entry(zbx_hashset_t *hs, ZBX_HASHSET_ENTRY_T *entry)
35 {
36 if (NULL != hs->clean_func)
37 hs->clean_func(entry->data);
38
39 hs->mem_free_func(entry);
40 }
41
zbx_hashset_init_slots(zbx_hashset_t * hs,size_t init_size)42 static int zbx_hashset_init_slots(zbx_hashset_t *hs, size_t init_size)
43 {
44 hs->num_data = 0;
45
46 if (0 < init_size)
47 {
48 hs->num_slots = next_prime(init_size);
49
50 if (NULL == (hs->slots = (ZBX_HASHSET_ENTRY_T **)hs->mem_malloc_func(NULL, hs->num_slots * sizeof(ZBX_HASHSET_ENTRY_T *))))
51 return FAIL;
52
53 memset(hs->slots, 0, hs->num_slots * sizeof(ZBX_HASHSET_ENTRY_T *));
54 }
55 else
56 {
57 hs->num_slots = 0;
58 hs->slots = NULL;
59 }
60
61 return SUCCEED;
62 }
63
64 /* public hashset interface */
65
zbx_hashset_create(zbx_hashset_t * hs,size_t init_size,zbx_hash_func_t hash_func,zbx_compare_func_t compare_func)66 void zbx_hashset_create(zbx_hashset_t *hs, size_t init_size,
67 zbx_hash_func_t hash_func,
68 zbx_compare_func_t compare_func)
69 {
70 zbx_hashset_create_ext(hs, init_size, hash_func, compare_func, NULL,
71 ZBX_DEFAULT_MEM_MALLOC_FUNC,
72 ZBX_DEFAULT_MEM_REALLOC_FUNC,
73 ZBX_DEFAULT_MEM_FREE_FUNC);
74 }
75
zbx_hashset_create_ext(zbx_hashset_t * hs,size_t init_size,zbx_hash_func_t hash_func,zbx_compare_func_t compare_func,zbx_clean_func_t clean_func,zbx_mem_malloc_func_t mem_malloc_func,zbx_mem_realloc_func_t mem_realloc_func,zbx_mem_free_func_t mem_free_func)76 void zbx_hashset_create_ext(zbx_hashset_t *hs, size_t init_size,
77 zbx_hash_func_t hash_func,
78 zbx_compare_func_t compare_func,
79 zbx_clean_func_t clean_func,
80 zbx_mem_malloc_func_t mem_malloc_func,
81 zbx_mem_realloc_func_t mem_realloc_func,
82 zbx_mem_free_func_t mem_free_func)
83 {
84 hs->hash_func = hash_func;
85 hs->compare_func = compare_func;
86 hs->clean_func = clean_func;
87 hs->mem_malloc_func = mem_malloc_func;
88 hs->mem_realloc_func = mem_realloc_func;
89 hs->mem_free_func = mem_free_func;
90
91 zbx_hashset_init_slots(hs, init_size);
92 }
93
zbx_hashset_destroy(zbx_hashset_t * hs)94 void zbx_hashset_destroy(zbx_hashset_t *hs)
95 {
96 int i;
97 ZBX_HASHSET_ENTRY_T *entry, *next_entry;
98
99 for (i = 0; i < hs->num_slots; i++)
100 {
101 entry = hs->slots[i];
102
103 while (NULL != entry)
104 {
105 next_entry = entry->next;
106 __hashset_free_entry(hs, entry);
107 entry = next_entry;
108 }
109 }
110
111 hs->num_data = 0;
112 hs->num_slots = 0;
113
114 if (NULL != hs->slots)
115 {
116 hs->mem_free_func(hs->slots);
117 hs->slots = NULL;
118 }
119
120 hs->hash_func = NULL;
121 hs->compare_func = NULL;
122 hs->mem_malloc_func = NULL;
123 hs->mem_realloc_func = NULL;
124 hs->mem_free_func = NULL;
125 }
126
127 /******************************************************************************
128 * *
129 * Function: zbx_hashset_reserve *
130 * *
131 * Purpose: allocation not less than the required number of slots for hashset *
132 * *
133 * Parameters: hs - [IN] the destination hashset *
134 * num_slots_req - [IN] the number of required slots *
135 * *
136 ******************************************************************************/
zbx_hashset_reserve(zbx_hashset_t * hs,int num_slots_req)137 int zbx_hashset_reserve(zbx_hashset_t *hs, int num_slots_req)
138 {
139 if (0 == hs->num_slots)
140 {
141 /* correction for prevent the second relocation in the case that requires the same number of slots */
142 if (SUCCEED != zbx_hashset_init_slots(hs, MAX(ZBX_HASHSET_DEFAULT_SLOTS,
143 num_slots_req * (2 - CRIT_LOAD_FACTOR) + 1)))
144 {
145 return FAIL;
146 }
147 }
148 else if (num_slots_req >= hs->num_slots * CRIT_LOAD_FACTOR)
149 {
150 int inc_slots, new_slot, slot;
151 void *slots;
152 ZBX_HASHSET_ENTRY_T **prev_next, *curr_entry, *tmp;
153
154 inc_slots = next_prime(hs->num_slots * SLOT_GROWTH_FACTOR);
155
156 if (NULL == (slots = hs->mem_realloc_func(hs->slots, inc_slots * sizeof(ZBX_HASHSET_ENTRY_T *))))
157 return FAIL;
158
159 hs->slots = (ZBX_HASHSET_ENTRY_T **)slots;
160
161 memset(hs->slots + hs->num_slots, 0, (inc_slots - hs->num_slots) * sizeof(ZBX_HASHSET_ENTRY_T *));
162
163 for (slot = 0; slot < hs->num_slots; slot++)
164 {
165 prev_next = &hs->slots[slot];
166 curr_entry = hs->slots[slot];
167
168 while (NULL != curr_entry)
169 {
170 if (slot != (new_slot = curr_entry->hash % inc_slots))
171 {
172 tmp = curr_entry->next;
173 curr_entry->next = hs->slots[new_slot];
174 hs->slots[new_slot] = curr_entry;
175
176 *prev_next = tmp;
177 curr_entry = tmp;
178 }
179 else
180 {
181 prev_next = &curr_entry->next;
182 curr_entry = curr_entry->next;
183 }
184 }
185 }
186
187 hs->num_slots = inc_slots;
188 }
189
190 return SUCCEED;
191 }
192
zbx_hashset_insert(zbx_hashset_t * hs,const void * data,size_t size)193 void *zbx_hashset_insert(zbx_hashset_t *hs, const void *data, size_t size)
194 {
195 return zbx_hashset_insert_ext(hs, data, size, 0);
196 }
197
zbx_hashset_insert_ext(zbx_hashset_t * hs,const void * data,size_t size,size_t offset)198 void *zbx_hashset_insert_ext(zbx_hashset_t *hs, const void *data, size_t size, size_t offset)
199 {
200 int slot;
201 zbx_hash_t hash;
202 ZBX_HASHSET_ENTRY_T *entry;
203
204 if (0 == hs->num_slots && SUCCEED != zbx_hashset_init_slots(hs, ZBX_HASHSET_DEFAULT_SLOTS))
205 return NULL;
206
207 hash = hs->hash_func(data);
208
209 slot = hash % hs->num_slots;
210 entry = hs->slots[slot];
211
212 while (NULL != entry)
213 {
214 if (entry->hash == hash && hs->compare_func(entry->data, data) == 0)
215 break;
216
217 entry = entry->next;
218 }
219
220 if (NULL == entry)
221 {
222 if (SUCCEED != zbx_hashset_reserve(hs, hs->num_data + 1))
223 return NULL;
224
225 /* recalculate new slot */
226 slot = hash % hs->num_slots;
227
228 if (NULL == (entry = (ZBX_HASHSET_ENTRY_T *)hs->mem_malloc_func(NULL, ZBX_HASHSET_ENTRY_OFFSET + size)))
229 return NULL;
230
231 memcpy((char *)entry->data + offset, (const char *)data + offset, size - offset);
232 entry->hash = hash;
233 entry->next = hs->slots[slot];
234 hs->slots[slot] = entry;
235 hs->num_data++;
236 }
237
238 return entry->data;
239 }
240
zbx_hashset_search(zbx_hashset_t * hs,const void * data)241 void *zbx_hashset_search(zbx_hashset_t *hs, const void *data)
242 {
243 int slot;
244 zbx_hash_t hash;
245 ZBX_HASHSET_ENTRY_T *entry;
246
247 if (0 == hs->num_slots)
248 return NULL;
249
250 hash = hs->hash_func(data);
251
252 slot = hash % hs->num_slots;
253 entry = hs->slots[slot];
254
255 while (NULL != entry)
256 {
257 if (entry->hash == hash && hs->compare_func(entry->data, data) == 0)
258 break;
259
260 entry = entry->next;
261 }
262
263 return (NULL != entry ? entry->data : NULL);
264 }
265
266 /******************************************************************************
267 * *
268 * Purpose: remove a hashset entry using comparison with the given data *
269 * *
270 ******************************************************************************/
zbx_hashset_remove(zbx_hashset_t * hs,const void * data)271 void zbx_hashset_remove(zbx_hashset_t *hs, const void *data)
272 {
273 int slot;
274 zbx_hash_t hash;
275 ZBX_HASHSET_ENTRY_T *entry;
276
277 if (0 == hs->num_slots)
278 return;
279
280 hash = hs->hash_func(data);
281
282 slot = hash % hs->num_slots;
283 entry = hs->slots[slot];
284
285 if (NULL != entry)
286 {
287 if (entry->hash == hash && hs->compare_func(entry->data, data) == 0)
288 {
289 hs->slots[slot] = entry->next;
290 __hashset_free_entry(hs, entry);
291 hs->num_data--;
292 }
293 else
294 {
295 ZBX_HASHSET_ENTRY_T *prev_entry;
296
297 prev_entry = entry;
298 entry = entry->next;
299
300 while (NULL != entry)
301 {
302 if (entry->hash == hash && hs->compare_func(entry->data, data) == 0)
303 {
304 prev_entry->next = entry->next;
305 __hashset_free_entry(hs, entry);
306 hs->num_data--;
307 break;
308 }
309
310 prev_entry = entry;
311 entry = entry->next;
312 }
313 }
314 }
315 }
316
317 /******************************************************************************
318 * *
319 * Purpose: remove a hashset entry using a data pointer returned to the user *
320 * by zbx_hashset_insert[_ext]() and zbx_hashset_search() functions *
321 * *
322 ******************************************************************************/
zbx_hashset_remove_direct(zbx_hashset_t * hs,const void * data)323 void zbx_hashset_remove_direct(zbx_hashset_t *hs, const void *data)
324 {
325 int slot;
326 ZBX_HASHSET_ENTRY_T *data_entry, *iter_entry;
327
328 if (0 == hs->num_slots)
329 return;
330
331 data_entry = (ZBX_HASHSET_ENTRY_T *)((const char *)data - ZBX_HASHSET_ENTRY_OFFSET);
332
333 slot = data_entry->hash % hs->num_slots;
334 iter_entry = hs->slots[slot];
335
336 if (NULL != iter_entry)
337 {
338 if (iter_entry == data_entry)
339 {
340 hs->slots[slot] = data_entry->next;
341 __hashset_free_entry(hs, data_entry);
342 hs->num_data--;
343 }
344 else
345 {
346 while (NULL != iter_entry->next)
347 {
348 if (iter_entry->next == data_entry)
349 {
350 iter_entry->next = data_entry->next;
351 __hashset_free_entry(hs, data_entry);
352 hs->num_data--;
353 break;
354 }
355
356 iter_entry = iter_entry->next;
357 }
358 }
359 }
360 }
361
zbx_hashset_clear(zbx_hashset_t * hs)362 void zbx_hashset_clear(zbx_hashset_t *hs)
363 {
364 int slot;
365 ZBX_HASHSET_ENTRY_T *entry;
366
367 for (slot = 0; slot < hs->num_slots; slot++)
368 {
369 while (NULL != hs->slots[slot])
370 {
371 entry = hs->slots[slot];
372 hs->slots[slot] = entry->next;
373 __hashset_free_entry(hs, entry);
374 }
375 }
376
377 hs->num_data = 0;
378 }
379
380 #define ITER_START (-1)
381 #define ITER_FINISH (-2)
382
zbx_hashset_iter_reset(zbx_hashset_t * hs,zbx_hashset_iter_t * iter)383 void zbx_hashset_iter_reset(zbx_hashset_t *hs, zbx_hashset_iter_t *iter)
384 {
385 iter->hashset = hs;
386 iter->slot = ITER_START;
387 }
388
zbx_hashset_iter_next(zbx_hashset_iter_t * iter)389 void *zbx_hashset_iter_next(zbx_hashset_iter_t *iter)
390 {
391 if (ITER_FINISH == iter->slot)
392 return NULL;
393
394 if (ITER_START != iter->slot && NULL != iter->entry && NULL != iter->entry->next)
395 {
396 iter->entry = iter->entry->next;
397 return iter->entry->data;
398 }
399
400 while (1)
401 {
402 iter->slot++;
403
404 if (iter->slot == iter->hashset->num_slots)
405 {
406 iter->slot = ITER_FINISH;
407 return NULL;
408 }
409
410 if (NULL != iter->hashset->slots[iter->slot])
411 {
412 iter->entry = iter->hashset->slots[iter->slot];
413 return iter->entry->data;
414 }
415 }
416 }
417
zbx_hashset_iter_remove(zbx_hashset_iter_t * iter)418 void zbx_hashset_iter_remove(zbx_hashset_iter_t *iter)
419 {
420 if (ITER_START == iter->slot || ITER_FINISH == iter->slot || NULL == iter->entry)
421 {
422 zabbix_log(LOG_LEVEL_CRIT, "removing a hashset entry through a bad iterator");
423 exit(EXIT_FAILURE);
424 }
425
426 if (iter->hashset->slots[iter->slot] == iter->entry)
427 {
428 iter->hashset->slots[iter->slot] = iter->entry->next;
429 __hashset_free_entry(iter->hashset, iter->entry);
430 iter->hashset->num_data--;
431
432 iter->slot--;
433 iter->entry = NULL;
434 }
435 else
436 {
437 ZBX_HASHSET_ENTRY_T *prev_entry = iter->hashset->slots[iter->slot];
438
439 while (prev_entry->next != iter->entry)
440 prev_entry = prev_entry->next;
441
442 prev_entry->next = iter->entry->next;
443 __hashset_free_entry(iter->hashset, iter->entry);
444 iter->hashset->num_data--;
445
446 iter->entry = prev_entry;
447 }
448 }
449