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 swap(zbx_binary_heap_t *heap, int index_1, int index_2);
26
27 static void __binary_heap_ensure_free_space(zbx_binary_heap_t *heap);
28
29 static int __binary_heap_bubble_up(zbx_binary_heap_t *heap, int index);
30 static int __binary_heap_bubble_down(zbx_binary_heap_t *heap, int index);
31
32 #define ARRAY_GROWTH_FACTOR 3/2
33
34 #define HAS_DIRECT_OPTION(heap) (0 != (heap->options & ZBX_BINARY_HEAP_OPTION_DIRECT))
35
36 /* helper functions */
37
swap(zbx_binary_heap_t * heap,int index_1,int index_2)38 static void swap(zbx_binary_heap_t *heap, int index_1, int index_2)
39 {
40 zbx_binary_heap_elem_t tmp;
41
42 tmp = heap->elems[index_1];
43 heap->elems[index_1] = heap->elems[index_2];
44 heap->elems[index_2] = tmp;
45
46 if (HAS_DIRECT_OPTION(heap))
47 {
48 zbx_hashmap_set(heap->key_index, heap->elems[index_1].key, index_1);
49 zbx_hashmap_set(heap->key_index, heap->elems[index_2].key, index_2);
50 }
51 }
52
53 /* private binary heap functions */
54
__binary_heap_ensure_free_space(zbx_binary_heap_t * heap)55 static void __binary_heap_ensure_free_space(zbx_binary_heap_t *heap)
56 {
57 int tmp_elems_alloc = heap->elems_alloc;
58
59 /* In order to prevent memory corruption heap->elems_alloc is set only after successful allocation. */
60 /* Otherwise, in case of shared memory, other processes might read or write past the actually */
61 /* allocated memory. */
62
63 if (NULL == heap->elems)
64 {
65 heap->elems_num = 0;
66 tmp_elems_alloc = 32;
67 }
68 else if (heap->elems_num == heap->elems_alloc)
69 tmp_elems_alloc = MAX(heap->elems_alloc + 1, heap->elems_alloc * ARRAY_GROWTH_FACTOR);
70
71 if (heap->elems_alloc != tmp_elems_alloc)
72 {
73 heap->elems = (zbx_binary_heap_elem_t *)heap->mem_realloc_func(heap->elems, tmp_elems_alloc * sizeof(zbx_binary_heap_elem_t));
74
75 if (NULL == heap->elems)
76 {
77 THIS_SHOULD_NEVER_HAPPEN;
78 exit(EXIT_FAILURE);
79 }
80
81 heap->elems_alloc = tmp_elems_alloc;
82 }
83 }
84
__binary_heap_bubble_up(zbx_binary_heap_t * heap,int index)85 static int __binary_heap_bubble_up(zbx_binary_heap_t *heap, int index)
86 {
87 while (0 != index)
88 {
89 if (heap->compare_func(&heap->elems[(index - 1) / 2], &heap->elems[index]) <= 0)
90 break;
91
92 swap(heap, (index - 1) / 2, index);
93 index = (index - 1) / 2;
94 }
95
96 return index;
97 }
98
__binary_heap_bubble_down(zbx_binary_heap_t * heap,int index)99 static int __binary_heap_bubble_down(zbx_binary_heap_t *heap, int index)
100 {
101 while (1)
102 {
103 int left = 2 * index + 1;
104 int right = 2 * index + 2;
105
106 if (left >= heap->elems_num)
107 break;
108
109 if (right >= heap->elems_num)
110 {
111 if (heap->compare_func(&heap->elems[index], &heap->elems[left]) > 0)
112 {
113 swap(heap, index, left);
114 index = left;
115 }
116
117 break;
118 }
119
120 if (heap->compare_func(&heap->elems[left], &heap->elems[right]) <= 0)
121 {
122 if (heap->compare_func(&heap->elems[index], &heap->elems[left]) > 0)
123 {
124 swap(heap, index, left);
125 index = left;
126 }
127 else
128 break;
129 }
130 else
131 {
132 if (heap->compare_func(&heap->elems[index], &heap->elems[right]) > 0)
133 {
134 swap(heap, index, right);
135 index = right;
136 }
137 else
138 break;
139 }
140 }
141
142 return index;
143 }
144
145 /* public binary heap interface */
146
zbx_binary_heap_create(zbx_binary_heap_t * heap,zbx_compare_func_t compare_func,int options)147 void zbx_binary_heap_create(zbx_binary_heap_t *heap, zbx_compare_func_t compare_func, int options)
148 {
149 zbx_binary_heap_create_ext(heap, compare_func, options,
150 ZBX_DEFAULT_MEM_MALLOC_FUNC,
151 ZBX_DEFAULT_MEM_REALLOC_FUNC,
152 ZBX_DEFAULT_MEM_FREE_FUNC);
153 }
154
zbx_binary_heap_create_ext(zbx_binary_heap_t * heap,zbx_compare_func_t compare_func,int options,zbx_mem_malloc_func_t mem_malloc_func,zbx_mem_realloc_func_t mem_realloc_func,zbx_mem_free_func_t mem_free_func)155 void zbx_binary_heap_create_ext(zbx_binary_heap_t *heap, zbx_compare_func_t compare_func, int options,
156 zbx_mem_malloc_func_t mem_malloc_func,
157 zbx_mem_realloc_func_t mem_realloc_func,
158 zbx_mem_free_func_t mem_free_func)
159 {
160 heap->elems = NULL;
161 heap->elems_num = 0;
162 heap->elems_alloc = 0;
163 heap->compare_func = compare_func;
164 heap->options = options;
165
166 if (HAS_DIRECT_OPTION(heap))
167 {
168 heap->key_index = (zbx_hashmap_t *)mem_malloc_func(NULL, sizeof(zbx_hashmap_t));
169 zbx_hashmap_create_ext(heap->key_index, 512,
170 ZBX_DEFAULT_UINT64_HASH_FUNC,
171 ZBX_DEFAULT_UINT64_COMPARE_FUNC,
172 mem_malloc_func,
173 mem_realloc_func,
174 mem_free_func);
175 }
176 else
177 heap->key_index = NULL;
178
179 heap->mem_malloc_func = mem_malloc_func;
180 heap->mem_realloc_func = mem_realloc_func;
181 heap->mem_free_func = mem_free_func;
182 }
183
zbx_binary_heap_destroy(zbx_binary_heap_t * heap)184 void zbx_binary_heap_destroy(zbx_binary_heap_t *heap)
185 {
186 if (NULL != heap->elems)
187 {
188 heap->mem_free_func(heap->elems);
189 heap->elems = NULL;
190 heap->elems_num = 0;
191 heap->elems_alloc = 0;
192 }
193
194 heap->compare_func = NULL;
195
196 if (HAS_DIRECT_OPTION(heap))
197 {
198 zbx_hashmap_destroy(heap->key_index);
199 heap->mem_free_func(heap->key_index);
200 heap->key_index = NULL;
201 heap->options = 0;
202 }
203
204 heap->mem_malloc_func = NULL;
205 heap->mem_realloc_func = NULL;
206 heap->mem_free_func = NULL;
207 }
208
zbx_binary_heap_empty(zbx_binary_heap_t * heap)209 int zbx_binary_heap_empty(zbx_binary_heap_t *heap)
210 {
211 return (0 == heap->elems_num ? SUCCEED : FAIL);
212 }
213
zbx_binary_heap_find_min(zbx_binary_heap_t * heap)214 zbx_binary_heap_elem_t *zbx_binary_heap_find_min(zbx_binary_heap_t *heap)
215 {
216 if (0 == heap->elems_num)
217 {
218 zabbix_log(LOG_LEVEL_CRIT, "asking for a minimum in an empty heap");
219 exit(EXIT_FAILURE);
220 }
221
222 return &heap->elems[0];
223 }
224
zbx_binary_heap_insert(zbx_binary_heap_t * heap,zbx_binary_heap_elem_t * elem)225 void zbx_binary_heap_insert(zbx_binary_heap_t *heap, zbx_binary_heap_elem_t *elem)
226 {
227 int index;
228
229 if (HAS_DIRECT_OPTION(heap) && FAIL != zbx_hashmap_get(heap->key_index, elem->key))
230 {
231 zabbix_log(LOG_LEVEL_CRIT, "inserting a duplicate key into a heap with direct option");
232 exit(EXIT_FAILURE);
233 }
234
235 __binary_heap_ensure_free_space(heap);
236
237 index = heap->elems_num++;
238 heap->elems[index] = *elem;
239
240 index = __binary_heap_bubble_up(heap, index);
241
242 if (HAS_DIRECT_OPTION(heap) && index == heap->elems_num - 1)
243 zbx_hashmap_set(heap->key_index, elem->key, index);
244 }
245
zbx_binary_heap_update_direct(zbx_binary_heap_t * heap,zbx_binary_heap_elem_t * elem)246 void zbx_binary_heap_update_direct(zbx_binary_heap_t *heap, zbx_binary_heap_elem_t *elem)
247 {
248 int index;
249
250 if (!HAS_DIRECT_OPTION(heap))
251 {
252 zabbix_log(LOG_LEVEL_CRIT, "direct update operation is not supported for this heap");
253 exit(EXIT_FAILURE);
254 }
255
256 if (FAIL != (index = zbx_hashmap_get(heap->key_index, elem->key)))
257 {
258 heap->elems[index] = *elem;
259
260 if (index == __binary_heap_bubble_up(heap, index))
261 __binary_heap_bubble_down(heap, index);
262 }
263 else
264 {
265 zabbix_log(LOG_LEVEL_CRIT, "element with key " ZBX_FS_UI64 " not found in heap for update", elem->key);
266 exit(EXIT_FAILURE);
267 }
268 }
269
zbx_binary_heap_remove_min(zbx_binary_heap_t * heap)270 void zbx_binary_heap_remove_min(zbx_binary_heap_t *heap)
271 {
272 int index;
273
274 if (0 == heap->elems_num)
275 {
276 zabbix_log(LOG_LEVEL_CRIT, "removing a minimum from an empty heap");
277 exit(EXIT_FAILURE);
278 }
279
280 if (HAS_DIRECT_OPTION(heap))
281 zbx_hashmap_remove(heap->key_index, heap->elems[0].key);
282
283 if (0 != (--heap->elems_num))
284 {
285 heap->elems[0] = heap->elems[heap->elems_num];
286 index = __binary_heap_bubble_down(heap, 0);
287
288 if (HAS_DIRECT_OPTION(heap) && index == 0)
289 zbx_hashmap_set(heap->key_index, heap->elems[index].key, index);
290 }
291 }
292
zbx_binary_heap_remove_direct(zbx_binary_heap_t * heap,zbx_uint64_t key)293 void zbx_binary_heap_remove_direct(zbx_binary_heap_t *heap, zbx_uint64_t key)
294 {
295 int index;
296
297 if (!HAS_DIRECT_OPTION(heap))
298 {
299 zabbix_log(LOG_LEVEL_CRIT, "direct remove operation is not supported for this heap");
300 exit(EXIT_FAILURE);
301 }
302
303 if (FAIL != (index = zbx_hashmap_get(heap->key_index, key)))
304 {
305 zbx_hashmap_remove(heap->key_index, key);
306
307 if (index != (--heap->elems_num))
308 {
309 heap->elems[index] = heap->elems[heap->elems_num];
310
311 if (index == __binary_heap_bubble_up(heap, index))
312 if (index == __binary_heap_bubble_down(heap, index))
313 zbx_hashmap_set(heap->key_index, heap->elems[index].key, index);
314 }
315 }
316 else
317 {
318 zabbix_log(LOG_LEVEL_CRIT, "element with key " ZBX_FS_UI64 " not found in heap for remove", key);
319 exit(EXIT_FAILURE);
320 }
321 }
322
zbx_binary_heap_clear(zbx_binary_heap_t * heap)323 void zbx_binary_heap_clear(zbx_binary_heap_t *heap)
324 {
325 heap->elems_num = 0;
326
327 if (HAS_DIRECT_OPTION(heap))
328 zbx_hashmap_clear(heap->key_index);
329 }
330