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_VECTORIMPL_H 21 #define ZABBIX_VECTORIMPL_H 22 23 #define ZBX_VECTOR_ARRAY_GROWTH_FACTOR 3/2 24 25 #define ZBX_VECTOR_IMPL(__id, __type) \ 26 \ 27 static void __vector_ ## __id ## _ensure_free_space(zbx_vector_ ## __id ## _t *vector) \ 28 { \ 29 if (NULL == vector->values) \ 30 { \ 31 vector->values_num = 0; \ 32 vector->values_alloc = 32; \ 33 vector->values = (__type *)vector->mem_malloc_func(NULL, vector->values_alloc * sizeof(__type)); \ 34 } \ 35 else if (vector->values_num == vector->values_alloc) \ 36 { \ 37 vector->values_alloc = MAX(vector->values_alloc + 1, vector->values_alloc * ZBX_VECTOR_ARRAY_GROWTH_FACTOR); \ 38 vector->values = (__type *)vector->mem_realloc_func(vector->values, vector->values_alloc * sizeof(__type)); \ 39 } \ 40 } \ 41 \ 42 void zbx_vector_ ## __id ## _create(zbx_vector_ ## __id ## _t *vector) \ 43 { \ 44 zbx_vector_ ## __id ## _create_ext(vector, \ 45 ZBX_DEFAULT_MEM_MALLOC_FUNC, \ 46 ZBX_DEFAULT_MEM_REALLOC_FUNC, \ 47 ZBX_DEFAULT_MEM_FREE_FUNC); \ 48 } \ 49 \ 50 void zbx_vector_ ## __id ## _create_ext(zbx_vector_ ## __id ## _t *vector, \ 51 zbx_mem_malloc_func_t mem_malloc_func, \ 52 zbx_mem_realloc_func_t mem_realloc_func, \ 53 zbx_mem_free_func_t mem_free_func) \ 54 { \ 55 vector->values = NULL; \ 56 vector->values_num = 0; \ 57 vector->values_alloc = 0; \ 58 \ 59 vector->mem_malloc_func = mem_malloc_func; \ 60 vector->mem_realloc_func = mem_realloc_func; \ 61 vector->mem_free_func = mem_free_func; \ 62 } \ 63 \ 64 void zbx_vector_ ## __id ## _destroy(zbx_vector_ ## __id ## _t *vector) \ 65 { \ 66 if (NULL != vector->values) \ 67 { \ 68 vector->mem_free_func(vector->values); \ 69 vector->values = NULL; \ 70 vector->values_num = 0; \ 71 vector->values_alloc = 0; \ 72 } \ 73 \ 74 vector->mem_malloc_func = NULL; \ 75 vector->mem_realloc_func = NULL; \ 76 vector->mem_free_func = NULL; \ 77 } \ 78 \ 79 void zbx_vector_ ## __id ## _append(zbx_vector_ ## __id ## _t *vector, __type value) \ 80 { \ 81 __vector_ ## __id ## _ensure_free_space(vector); \ 82 vector->values[vector->values_num++] = value; \ 83 } \ 84 \ 85 void zbx_vector_ ## __id ## _append_ptr(zbx_vector_ ## __id ## _t *vector, __type *value) \ 86 { \ 87 __vector_ ## __id ## _ensure_free_space(vector); \ 88 vector->values[vector->values_num++] = *value; \ 89 } \ 90 \ 91 void zbx_vector_ ## __id ## _append_array(zbx_vector_ ## __id ## _t *vector, __type const *values, \ 92 int values_num) \ 93 { \ 94 zbx_vector_ ## __id ## _reserve(vector, vector->values_num + values_num); \ 95 memcpy(vector->values + vector->values_num, values, values_num * sizeof(__type)); \ 96 vector->values_num = vector->values_num + values_num; \ 97 } \ 98 \ 99 void zbx_vector_ ## __id ## _remove_noorder(zbx_vector_ ## __id ## _t *vector, int index) \ 100 { \ 101 if (!(0 <= index && index < vector->values_num)) \ 102 { \ 103 zabbix_log(LOG_LEVEL_CRIT, "removing a non-existent element at index %d", index); \ 104 exit(EXIT_FAILURE); \ 105 } \ 106 \ 107 vector->values[index] = vector->values[--vector->values_num]; \ 108 } \ 109 \ 110 void zbx_vector_ ## __id ## _remove(zbx_vector_ ## __id ## _t *vector, int index) \ 111 { \ 112 if (!(0 <= index && index < vector->values_num)) \ 113 { \ 114 zabbix_log(LOG_LEVEL_CRIT, "removing a non-existent element at index %d", index); \ 115 exit(EXIT_FAILURE); \ 116 } \ 117 \ 118 vector->values_num--; \ 119 memmove(&vector->values[index], &vector->values[index + 1], \ 120 sizeof(__type) * (vector->values_num - index)); \ 121 } \ 122 \ 123 void zbx_vector_ ## __id ## _sort(zbx_vector_ ## __id ## _t *vector, zbx_compare_func_t compare_func) \ 124 { \ 125 if (2 <= vector->values_num) \ 126 qsort(vector->values, vector->values_num, sizeof(__type), compare_func); \ 127 } \ 128 \ 129 void zbx_vector_ ## __id ## _uniq(zbx_vector_ ## __id ## _t *vector, zbx_compare_func_t compare_func) \ 130 { \ 131 if (2 <= vector->values_num) \ 132 { \ 133 int i, j = 1; \ 134 \ 135 for (i = 1; i < vector->values_num; i++) \ 136 { \ 137 if (0 != compare_func(&vector->values[i - 1], &vector->values[i])) \ 138 vector->values[j++] = vector->values[i]; \ 139 } \ 140 \ 141 vector->values_num = j; \ 142 } \ 143 } \ 144 \ 145 int zbx_vector_ ## __id ## _nearestindex(const zbx_vector_ ## __id ## _t *vector, const __type value, \ 146 zbx_compare_func_t compare_func) \ 147 { \ 148 int lo = 0, hi = vector->values_num, mid, c; \ 149 \ 150 while (1 <= hi - lo) \ 151 { \ 152 mid = (lo + hi) / 2; \ 153 \ 154 c = compare_func(&vector->values[mid], &value); \ 155 \ 156 if (0 > c) \ 157 { \ 158 lo = mid + 1; \ 159 } \ 160 else if (0 == c) \ 161 { \ 162 return mid; \ 163 } \ 164 else \ 165 hi = mid; \ 166 } \ 167 \ 168 return hi; \ 169 } \ 170 \ 171 int zbx_vector_ ## __id ## _bsearch(const zbx_vector_ ## __id ## _t *vector, const __type value, \ 172 zbx_compare_func_t compare_func) \ 173 { \ 174 __type *ptr; \ 175 \ 176 ptr = (__type *)zbx_bsearch(&value, vector->values, vector->values_num, sizeof(__type), compare_func); \ 177 \ 178 if (NULL != ptr) \ 179 return (int)(ptr - vector->values); \ 180 else \ 181 return FAIL; \ 182 } \ 183 \ 184 int zbx_vector_ ## __id ## _lsearch(const zbx_vector_ ## __id ## _t *vector, const __type value, int *index,\ 185 zbx_compare_func_t compare_func) \ 186 { \ 187 while (*index < vector->values_num) \ 188 { \ 189 int c = compare_func(&vector->values[*index], &value); \ 190 \ 191 if (0 > c) \ 192 { \ 193 (*index)++; \ 194 continue; \ 195 } \ 196 \ 197 if (0 == c) \ 198 return SUCCEED; \ 199 \ 200 if (0 < c) \ 201 break; \ 202 } \ 203 \ 204 return FAIL; \ 205 } \ 206 \ 207 int zbx_vector_ ## __id ## _search(const zbx_vector_ ## __id ## _t *vector, const __type value, \ 208 zbx_compare_func_t compare_func) \ 209 { \ 210 int index; \ 211 \ 212 for (index = 0; index < vector->values_num; index++) \ 213 { \ 214 if (0 == compare_func(&vector->values[index], &value)) \ 215 return index; \ 216 } \ 217 \ 218 return FAIL; \ 219 } \ 220 \ 221 \ 222 void zbx_vector_ ## __id ## _setdiff(zbx_vector_ ## __id ## _t *left, const zbx_vector_ ## __id ## _t *right,\ 223 zbx_compare_func_t compare_func) \ 224 { \ 225 int c, block_start, deleted = 0, left_index = 0, right_index = 0; \ 226 \ 227 while (left_index < left->values_num && right_index < right->values_num) \ 228 { \ 229 c = compare_func(&left->values[left_index], &right->values[right_index]); \ 230 \ 231 if (0 >= c) \ 232 left_index++; \ 233 \ 234 if (0 <= c) \ 235 right_index++; \ 236 \ 237 if (0 != c) \ 238 continue; \ 239 \ 240 if (0 < deleted++) \ 241 { \ 242 memmove(&left->values[block_start - deleted + 1], &left->values[block_start], \ 243 (left_index - 1 - block_start) * sizeof(__type)); \ 244 } \ 245 \ 246 block_start = left_index; \ 247 } \ 248 \ 249 if (0 < deleted) \ 250 { \ 251 memmove(&left->values[block_start - deleted], &left->values[block_start], \ 252 (left->values_num - block_start) * sizeof(__type)); \ 253 left->values_num -= deleted; \ 254 } \ 255 } \ 256 \ 257 void zbx_vector_ ## __id ## _reserve(zbx_vector_ ## __id ## _t *vector, size_t size) \ 258 { \ 259 if ((int)size > vector->values_alloc) \ 260 { \ 261 vector->values_alloc = (int)size; \ 262 vector->values = (__type *)vector->mem_realloc_func(vector->values, vector->values_alloc * sizeof(__type)); \ 263 } \ 264 } \ 265 \ 266 void zbx_vector_ ## __id ## _clear(zbx_vector_ ## __id ## _t *vector) \ 267 { \ 268 vector->values_num = 0; \ 269 } 270 271 #define ZBX_PTR_VECTOR_IMPL(__id, __type) \ 272 \ 273 ZBX_VECTOR_IMPL(__id, __type) \ 274 \ 275 void zbx_vector_ ## __id ## _clear_ext(zbx_vector_ ## __id ## _t *vector, zbx_ ## __id ## _free_func_t free_func) \ 276 { \ 277 if (0 != vector->values_num) \ 278 { \ 279 int index; \ 280 \ 281 for (index = 0; index < vector->values_num; index++) \ 282 free_func(vector->values[index]); \ 283 \ 284 vector->values_num = 0; \ 285 } \ 286 } 287 288 #endif /* ZABBIX_VECTORIMPL_H */ 289