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