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 #ifndef ZABBIX_ZBXALGO_H 21 #define ZABBIX_ZBXALGO_H 22 23 #include "common.h" 24 25 /* generic */ 26 27 typedef zbx_uint32_t zbx_hash_t; 28 29 zbx_hash_t zbx_hash_lookup2(const void *data, size_t len, zbx_hash_t seed); 30 zbx_hash_t zbx_hash_modfnv(const void *data, size_t len, zbx_hash_t seed); 31 zbx_hash_t zbx_hash_murmur2(const void *data, size_t len, zbx_hash_t seed); 32 zbx_hash_t zbx_hash_sdbm(const void *data, size_t len, zbx_hash_t seed); 33 zbx_hash_t zbx_hash_djb2(const void *data, size_t len, zbx_hash_t seed); 34 35 #define ZBX_DEFAULT_HASH_ALGO zbx_hash_modfnv 36 #define ZBX_DEFAULT_PTR_HASH_ALGO zbx_hash_modfnv 37 #define ZBX_DEFAULT_UINT64_HASH_ALGO zbx_hash_modfnv 38 #define ZBX_DEFAULT_STRING_HASH_ALGO zbx_hash_modfnv 39 40 typedef zbx_hash_t (*zbx_hash_func_t)(const void *data); 41 42 zbx_hash_t zbx_default_ptr_hash_func(const void *data); 43 zbx_hash_t zbx_default_uint64_hash_func(const void *data); 44 zbx_hash_t zbx_default_string_hash_func(const void *data); 45 zbx_hash_t zbx_default_uint64_pair_hash_func(const void *data); 46 47 #define ZBX_DEFAULT_HASH_SEED 0 48 49 #define ZBX_DEFAULT_PTR_HASH_FUNC zbx_default_ptr_hash_func 50 #define ZBX_DEFAULT_UINT64_HASH_FUNC zbx_default_uint64_hash_func 51 #define ZBX_DEFAULT_STRING_HASH_FUNC zbx_default_string_hash_func 52 #define ZBX_DEFAULT_UINT64_PAIR_HASH_FUNC zbx_default_uint64_pair_hash_func 53 54 typedef int (*zbx_compare_func_t)(const void *d1, const void *d2); 55 56 int zbx_default_int_compare_func(const void *d1, const void *d2); 57 int zbx_default_uint64_compare_func(const void *d1, const void *d2); 58 int zbx_default_uint64_ptr_compare_func(const void *d1, const void *d2); 59 int zbx_default_str_compare_func(const void *d1, const void *d2); 60 int zbx_default_ptr_compare_func(const void *d1, const void *d2); 61 int zbx_default_uint64_pair_compare_func(const void *d1, const void *d2); 62 63 #define ZBX_DEFAULT_INT_COMPARE_FUNC zbx_default_int_compare_func 64 #define ZBX_DEFAULT_UINT64_COMPARE_FUNC zbx_default_uint64_compare_func 65 #define ZBX_DEFAULT_UINT64_PTR_COMPARE_FUNC zbx_default_uint64_ptr_compare_func 66 #define ZBX_DEFAULT_STR_COMPARE_FUNC zbx_default_str_compare_func 67 #define ZBX_DEFAULT_PTR_COMPARE_FUNC zbx_default_ptr_compare_func 68 #define ZBX_DEFAULT_UINT64_PAIR_COMPARE_FUNC zbx_default_uint64_pair_compare_func 69 70 typedef void *(*zbx_mem_malloc_func_t)(void *old, size_t size); 71 typedef void *(*zbx_mem_realloc_func_t)(void *old, size_t size); 72 typedef void (*zbx_mem_free_func_t)(void *ptr); 73 74 void *zbx_default_mem_malloc_func(void *old, size_t size); 75 void *zbx_default_mem_realloc_func(void *old, size_t size); 76 void zbx_default_mem_free_func(void *ptr); 77 78 #define ZBX_DEFAULT_MEM_MALLOC_FUNC zbx_default_mem_malloc_func 79 #define ZBX_DEFAULT_MEM_REALLOC_FUNC zbx_default_mem_realloc_func 80 #define ZBX_DEFAULT_MEM_FREE_FUNC zbx_default_mem_free_func 81 82 typedef void (*zbx_clean_func_t)(void *data); 83 84 #define ZBX_RETURN_IF_NOT_EQUAL(a, b) \ 85 \ 86 if ((a) < (b)) \ 87 return -1; \ 88 if ((a) > (b)) \ 89 return +1 90 91 int is_prime(int n); 92 int next_prime(int n); 93 94 /* pair */ 95 96 typedef struct 97 { 98 void *first; 99 void *second; 100 } 101 zbx_ptr_pair_t; 102 103 typedef struct 104 { 105 zbx_uint64_t first; 106 zbx_uint64_t second; 107 } 108 zbx_uint64_pair_t; 109 110 /* hashset */ 111 112 #define ZBX_HASHSET_ENTRY_T struct zbx_hashset_entry_s 113 114 ZBX_HASHSET_ENTRY_T 115 { 116 ZBX_HASHSET_ENTRY_T *next; 117 zbx_hash_t hash; 118 #if SIZEOF_VOID_P > 4 119 /* the data member must be properly aligned on 64-bit architectures that require aligned memory access */ 120 char padding[sizeof(void *) - sizeof(zbx_hash_t)]; 121 #endif 122 char data[1]; 123 }; 124 125 typedef struct 126 { 127 ZBX_HASHSET_ENTRY_T **slots; 128 int num_slots; 129 int num_data; 130 zbx_hash_func_t hash_func; 131 zbx_compare_func_t compare_func; 132 zbx_clean_func_t clean_func; 133 zbx_mem_malloc_func_t mem_malloc_func; 134 zbx_mem_realloc_func_t mem_realloc_func; 135 zbx_mem_free_func_t mem_free_func; 136 } 137 zbx_hashset_t; 138 139 #define ZBX_HASHSET_ENTRY_OFFSET offsetof(ZBX_HASHSET_ENTRY_T, data) 140 141 void zbx_hashset_create(zbx_hashset_t *hs, size_t init_size, 142 zbx_hash_func_t hash_func, 143 zbx_compare_func_t compare_func); 144 void zbx_hashset_create_ext(zbx_hashset_t *hs, size_t init_size, 145 zbx_hash_func_t hash_func, 146 zbx_compare_func_t compare_func, 147 zbx_clean_func_t clean_func, 148 zbx_mem_malloc_func_t mem_malloc_func, 149 zbx_mem_realloc_func_t mem_realloc_func, 150 zbx_mem_free_func_t mem_free_func); 151 void zbx_hashset_destroy(zbx_hashset_t *hs); 152 153 int zbx_hashset_reserve(zbx_hashset_t *hs, int num_slots_req); 154 void *zbx_hashset_insert(zbx_hashset_t *hs, const void *data, size_t size); 155 void *zbx_hashset_insert_ext(zbx_hashset_t *hs, const void *data, size_t size, size_t offset); 156 void *zbx_hashset_search(zbx_hashset_t *hs, const void *data); 157 void zbx_hashset_remove(zbx_hashset_t *hs, const void *data); 158 void zbx_hashset_remove_direct(zbx_hashset_t *hs, const void *data); 159 160 void zbx_hashset_clear(zbx_hashset_t *hs); 161 162 typedef struct 163 { 164 zbx_hashset_t *hashset; 165 int slot; 166 ZBX_HASHSET_ENTRY_T *entry; 167 } 168 zbx_hashset_iter_t; 169 170 void zbx_hashset_iter_reset(zbx_hashset_t *hs, zbx_hashset_iter_t *iter); 171 void *zbx_hashset_iter_next(zbx_hashset_iter_t *iter); 172 void zbx_hashset_iter_remove(zbx_hashset_iter_t *iter); 173 174 /* hashmap */ 175 176 /* currently, we only have a very specialized hashmap */ 177 /* that maps zbx_uint64_t keys into non-negative ints */ 178 179 #define ZBX_HASHMAP_ENTRY_T struct zbx_hashmap_entry_s 180 #define ZBX_HASHMAP_SLOT_T struct zbx_hashmap_slot_s 181 182 ZBX_HASHMAP_ENTRY_T 183 { 184 zbx_uint64_t key; 185 int value; 186 }; 187 188 ZBX_HASHMAP_SLOT_T 189 { 190 ZBX_HASHMAP_ENTRY_T *entries; 191 int entries_num; 192 int entries_alloc; 193 }; 194 195 typedef struct 196 { 197 ZBX_HASHMAP_SLOT_T *slots; 198 int num_slots; 199 int num_data; 200 zbx_hash_func_t hash_func; 201 zbx_compare_func_t compare_func; 202 zbx_mem_malloc_func_t mem_malloc_func; 203 zbx_mem_realloc_func_t mem_realloc_func; 204 zbx_mem_free_func_t mem_free_func; 205 } 206 zbx_hashmap_t; 207 208 void zbx_hashmap_create(zbx_hashmap_t *hm, size_t init_size); 209 void zbx_hashmap_create_ext(zbx_hashmap_t *hm, size_t init_size, 210 zbx_hash_func_t hash_func, 211 zbx_compare_func_t compare_func, 212 zbx_mem_malloc_func_t mem_malloc_func, 213 zbx_mem_realloc_func_t mem_realloc_func, 214 zbx_mem_free_func_t mem_free_func); 215 void zbx_hashmap_destroy(zbx_hashmap_t *hm); 216 217 int zbx_hashmap_get(zbx_hashmap_t *hm, zbx_uint64_t key); 218 void zbx_hashmap_set(zbx_hashmap_t *hm, zbx_uint64_t key, int value); 219 void zbx_hashmap_remove(zbx_hashmap_t *hm, zbx_uint64_t key); 220 221 void zbx_hashmap_clear(zbx_hashmap_t *hm); 222 223 /* binary heap (min-heap) */ 224 225 /* currently, we only have a very specialized binary heap that can */ 226 /* store zbx_uint64_t keys with arbitrary auxiliary information */ 227 228 #define ZBX_BINARY_HEAP_OPTION_EMPTY 0 229 #define ZBX_BINARY_HEAP_OPTION_DIRECT (1<<0) /* support for direct update() and remove() operations */ 230 231 typedef struct 232 { 233 zbx_uint64_t key; 234 const void *data; 235 } 236 zbx_binary_heap_elem_t; 237 238 typedef struct 239 { 240 zbx_binary_heap_elem_t *elems; 241 int elems_num; 242 int elems_alloc; 243 int options; 244 zbx_compare_func_t compare_func; 245 zbx_hashmap_t *key_index; 246 247 /* The binary heap is designed to work correctly only with memory allocation functions */ 248 /* that return pointer to the allocated memory or quit. Functions that can return NULL */ 249 /* are not supported (process will exit() if NULL return value is encountered). If */ 250 /* using zbx_mem_info_t and the associated memory functions then ensure that allow_oom */ 251 /* is always set to 0. */ 252 zbx_mem_malloc_func_t mem_malloc_func; 253 zbx_mem_realloc_func_t mem_realloc_func; 254 zbx_mem_free_func_t mem_free_func; 255 } 256 zbx_binary_heap_t; 257 258 void zbx_binary_heap_create(zbx_binary_heap_t *heap, zbx_compare_func_t compare_func, int options); 259 void zbx_binary_heap_create_ext(zbx_binary_heap_t *heap, zbx_compare_func_t compare_func, int options, 260 zbx_mem_malloc_func_t mem_malloc_func, 261 zbx_mem_realloc_func_t mem_realloc_func, 262 zbx_mem_free_func_t mem_free_func); 263 void zbx_binary_heap_destroy(zbx_binary_heap_t *heap); 264 265 int zbx_binary_heap_empty(zbx_binary_heap_t *heap); 266 zbx_binary_heap_elem_t *zbx_binary_heap_find_min(zbx_binary_heap_t *heap); 267 void zbx_binary_heap_insert(zbx_binary_heap_t *heap, zbx_binary_heap_elem_t *elem); 268 void zbx_binary_heap_update_direct(zbx_binary_heap_t *heap, zbx_binary_heap_elem_t *elem); 269 void zbx_binary_heap_remove_min(zbx_binary_heap_t *heap); 270 void zbx_binary_heap_remove_direct(zbx_binary_heap_t *heap, zbx_uint64_t key); 271 272 void zbx_binary_heap_clear(zbx_binary_heap_t *heap); 273 274 /* vector */ 275 276 #define ZBX_VECTOR_DECL(__id, __type) \ 277 \ 278 typedef struct \ 279 { \ 280 __type *values; \ 281 int values_num; \ 282 int values_alloc; \ 283 zbx_mem_malloc_func_t mem_malloc_func; \ 284 zbx_mem_realloc_func_t mem_realloc_func; \ 285 zbx_mem_free_func_t mem_free_func; \ 286 } \ 287 zbx_vector_ ## __id ## _t; \ 288 \ 289 void zbx_vector_ ## __id ## _create(zbx_vector_ ## __id ## _t *vector); \ 290 void zbx_vector_ ## __id ## _create_ext(zbx_vector_ ## __id ## _t *vector, \ 291 zbx_mem_malloc_func_t mem_malloc_func, \ 292 zbx_mem_realloc_func_t mem_realloc_func, \ 293 zbx_mem_free_func_t mem_free_func); \ 294 void zbx_vector_ ## __id ## _destroy(zbx_vector_ ## __id ## _t *vector); \ 295 \ 296 void zbx_vector_ ## __id ## _append(zbx_vector_ ## __id ## _t *vector, __type value); \ 297 void zbx_vector_ ## __id ## _append_ptr(zbx_vector_ ## __id ## _t *vector, __type *value); \ 298 void zbx_vector_ ## __id ## _append_array(zbx_vector_ ## __id ## _t *vector, __type const *values, \ 299 int values_num); \ 300 void zbx_vector_ ## __id ## _remove_noorder(zbx_vector_ ## __id ## _t *vector, int index); \ 301 void zbx_vector_ ## __id ## _remove(zbx_vector_ ## __id ## _t *vector, int index); \ 302 \ 303 void zbx_vector_ ## __id ## _sort(zbx_vector_ ## __id ## _t *vector, zbx_compare_func_t compare_func); \ 304 void zbx_vector_ ## __id ## _uniq(zbx_vector_ ## __id ## _t *vector, zbx_compare_func_t compare_func); \ 305 \ 306 int zbx_vector_ ## __id ## _nearestindex(const zbx_vector_ ## __id ## _t *vector, const __type value, \ 307 zbx_compare_func_t compare_func); \ 308 int zbx_vector_ ## __id ## _bsearch(const zbx_vector_ ## __id ## _t *vector, const __type value, \ 309 zbx_compare_func_t compare_func); \ 310 int zbx_vector_ ## __id ## _lsearch(const zbx_vector_ ## __id ## _t *vector, const __type value, int *index,\ 311 zbx_compare_func_t compare_func); \ 312 int zbx_vector_ ## __id ## _search(const zbx_vector_ ## __id ## _t *vector, const __type value, \ 313 zbx_compare_func_t compare_func); \ 314 void zbx_vector_ ## __id ## _setdiff(zbx_vector_ ## __id ## _t *left, const zbx_vector_ ## __id ## _t *right,\ 315 zbx_compare_func_t compare_func); \ 316 \ 317 void zbx_vector_ ## __id ## _reserve(zbx_vector_ ## __id ## _t *vector, size_t size); \ 318 void zbx_vector_ ## __id ## _clear(zbx_vector_ ## __id ## _t *vector); 319 320 #define ZBX_PTR_VECTOR_DECL(__id, __type) \ 321 \ 322 ZBX_VECTOR_DECL(__id, __type) \ 323 \ 324 typedef void (*zbx_ ## __id ## _free_func_t)(__type data); \ 325 \ 326 void zbx_vector_ ## __id ## _clear_ext(zbx_vector_ ## __id ## _t *vector, zbx_ ## __id ## _free_func_t free_func); 327 328 ZBX_VECTOR_DECL(uint64, zbx_uint64_t) 329 ZBX_PTR_VECTOR_DECL(str, char *) 330 ZBX_PTR_VECTOR_DECL(ptr, void *) 331 ZBX_VECTOR_DECL(ptr_pair, zbx_ptr_pair_t) 332 ZBX_VECTOR_DECL(uint64_pair, zbx_uint64_pair_t) 333 334 /* this function is only for use with zbx_vector_XXX_clear_ext() */ 335 /* and only if the vector does not contain nested allocations */ 336 void zbx_ptr_free(void *data); 337 void zbx_str_free(char *data); 338 339 /* 128 bit unsigned integer handling */ 340 #define uset128(base, hi64, lo64) (base)->hi = hi64; (base)->lo = lo64 341 342 void uinc128_64(zbx_uint128_t *base, zbx_uint64_t value); 343 void uinc128_128(zbx_uint128_t *base, const zbx_uint128_t *value); 344 void udiv128_64(zbx_uint128_t *result, const zbx_uint128_t *dividend, zbx_uint64_t value); 345 void umul64_64(zbx_uint128_t *result, zbx_uint64_t value, zbx_uint64_t factor); 346 347 unsigned int zbx_isqrt32(unsigned int value); 348 349 /* expression evaluation */ 350 351 #define ZBX_INFINITY (1.0 / 0.0) /* "Positive infinity" value used as a fatal error code */ 352 #define ZBX_UNKNOWN (-1.0 / 0.0) /* "Negative infinity" value used as a code for "Unknown" */ 353 354 #define ZBX_UNKNOWN_STR "ZBX_UNKNOWN" /* textual representation of ZBX_UNKNOWN */ 355 #define ZBX_UNKNOWN_STR_LEN ZBX_CONST_STRLEN(ZBX_UNKNOWN_STR) 356 357 int evaluate(double *value, const char *expression, char *error, size_t max_error_len, 358 zbx_vector_ptr_t *unknown_msgs); 359 int evaluate_unknown(const char *expression, double *value, char *error, size_t max_error_len); 360 361 /* forecasting */ 362 363 #define ZBX_MATH_ERROR -1.0 364 365 typedef enum 366 { 367 FIT_LINEAR, 368 FIT_POLYNOMIAL, 369 FIT_EXPONENTIAL, 370 FIT_LOGARITHMIC, 371 FIT_POWER, 372 FIT_INVALID 373 } 374 zbx_fit_t; 375 376 typedef enum 377 { 378 MODE_VALUE, 379 MODE_MAX, 380 MODE_MIN, 381 MODE_DELTA, 382 MODE_AVG, 383 MODE_INVALID 384 } 385 zbx_mode_t; 386 387 int zbx_fit_code(char *fit_str, zbx_fit_t *fit, unsigned *k, char **error); 388 int zbx_mode_code(char *mode_str, zbx_mode_t *mode, char **error); 389 double zbx_forecast(double *t, double *x, int n, double now, double time, zbx_fit_t fit, unsigned k, zbx_mode_t mode); 390 double zbx_timeleft(double *t, double *x, int n, double now, double threshold, zbx_fit_t fit, unsigned k); 391 392 393 /* fifo queue of pointers */ 394 395 typedef struct 396 { 397 void **values; 398 int alloc_num; 399 int head_pos; 400 int tail_pos; 401 } 402 zbx_queue_ptr_t; 403 404 #define zbx_queue_ptr_empty(queue) ((queue)->head_pos == (queue)->tail_pos ? SUCCEED : FAIL) 405 406 int zbx_queue_ptr_values_num(zbx_queue_ptr_t *queue); 407 void zbx_queue_ptr_reserve(zbx_queue_ptr_t *queue, int num); 408 void zbx_queue_ptr_compact(zbx_queue_ptr_t *queue); 409 void zbx_queue_ptr_create(zbx_queue_ptr_t *queue); 410 void zbx_queue_ptr_destroy(zbx_queue_ptr_t *queue); 411 void zbx_queue_ptr_push(zbx_queue_ptr_t *queue, void *value); 412 void *zbx_queue_ptr_pop(zbx_queue_ptr_t *queue); 413 void zbx_queue_ptr_remove_value(zbx_queue_ptr_t *queue, const void *value); 414 415 416 417 #endif 418