| 1 | // SPDX-License-Identifier: LGPL-3.0-or-later |
| 2 | |
| 3 | #include "../libnetdata.h" |
| 4 | |
| 5 | /* ------------------------------------------------------------------------- */ |
| 6 | /* |
| 7 | * avl_insert(), avl_remove() and avl_search() |
| 8 | * are adaptations (by Netdata Inc.) of the AVL algorithm found in libavl |
| 9 | * v2.0.3, so that they do not use any memory allocations and their memory |
| 10 | * footprint is optimized (by eliminating non-necessary data members). |
| 11 | * |
| 12 | * libavl - library for manipulation of binary trees. |
| 13 | * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004 Free Software |
| 14 | * Foundation, Inc. |
| 15 | */ |
| 16 | |
| 17 | |
| 18 | /* Search |tree| for an item matching |item|, and return it if found. |
| 19 | Otherwise return |NULL|. */ |
| 20 | avl_t *avl_search(avl_tree_type *tree, avl_t *item) { |
| 21 | avl_t *p; |
| 22 | |
| 23 | // assert (tree != NULL && item != NULL); |
| 24 | |
| 25 | for (p = tree->root; p != NULL; ) { |
| 26 | int cmp = tree->compar(item, p); |
| 27 | |
| 28 | if (cmp < 0) |
| 29 | p = p->avl_link[0]; |
| 30 | else if (cmp > 0) |
| 31 | p = p->avl_link[1]; |
| 32 | else /* |cmp == 0| */ |
| 33 | return p; |
| 34 | } |
| 35 | |
| 36 | return NULL; |
| 37 | } |
| 38 | |
| 39 | /* Inserts |item| into |tree| and returns a pointer to |item|'s address. |
| 40 | If a duplicate item is found in the tree, |
| 41 | returns a pointer to the duplicate without inserting |item|. |
| 42 | */ |
| 43 | avl_t *avl_insert(avl_tree_type *tree, avl_t *item) { |
| 44 | avl_t *y, *z; /* Top node to update balance factor, and parent. */ |
| 45 | avl_t *p, *q; /* Iterator, and parent. */ |
| 46 | avl_t *n; /* Newly inserted node. */ |
| 47 | avl_t *w; /* New root of rebalanced subtree. */ |
| 48 | unsigned char dir; /* Direction to descend. */ |
| 49 | |
| 50 | unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */ |
| 51 | int k = 0; /* Number of cached results. */ |
| 52 | |
| 53 | // assert(tree != NULL && item != NULL); |
| 54 | |
| 55 | z = (avl_t *) &tree->root; |
| 56 | y = tree->root; |
| 57 | dir = 0; |
| 58 | for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) { |
| 59 | int cmp = tree->compar(item, p); |
| 60 | if (cmp == 0) |
| 61 | return p; |
| 62 | |
| 63 | if (p->avl_balance != 0) |
| 64 | z = q, y = p, k = 0; |
| 65 | da[k++] = dir = (unsigned char)(cmp > 0); |
| 66 | } |
| 67 | |
| 68 | n = q->avl_link[dir] = item; |
| 69 | |
| 70 | // tree->avl_count++; |
| 71 | n->avl_link[0] = n->avl_link[1] = NULL; |
| 72 | n->avl_balance = 0; |
| 73 | if (y == NULL) return n; |
| 74 | |
| 75 | for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++) |
| 76 | if (da[k] == 0) |
| 77 | p->avl_balance--; |
| 78 | else |
| 79 | p->avl_balance++; |
| 80 | |
| 81 | if (y->avl_balance == -2) { |
| 82 | avl_t *x = y->avl_link[0]; |
| 83 | if (x->avl_balance == -1) { |
| 84 | w = x; |
| 85 | y->avl_link[0] = x->avl_link[1]; |
| 86 | x->avl_link[1] = y; |
| 87 | x->avl_balance = y->avl_balance = 0; |
| 88 | } |
| 89 | else { |
| 90 | // assert (x->avl_balance == +1); |
| 91 | w = x->avl_link[1]; |
| 92 | x->avl_link[1] = w->avl_link[0]; |
| 93 | w->avl_link[0] = x; |
| 94 | y->avl_link[0] = w->avl_link[1]; |
| 95 | w->avl_link[1] = y; |
| 96 | if (w->avl_balance == -1) |
| 97 | x->avl_balance = 0, y->avl_balance = +1; |
| 98 | else if (w->avl_balance == 0) |
| 99 | x->avl_balance = y->avl_balance = 0; |
| 100 | else /* |w->avl_balance == +1| */ |
| 101 | x->avl_balance = -1, y->avl_balance = 0; |
| 102 | w->avl_balance = 0; |
| 103 | } |
| 104 | } |
| 105 | else if (y->avl_balance == +2) { |
| 106 | avl_t *x = y->avl_link[1]; |
| 107 | if (x->avl_balance == +1) { |
| 108 | w = x; |
| 109 | y->avl_link[1] = x->avl_link[0]; |
| 110 | x->avl_link[0] = y; |
| 111 | x->avl_balance = y->avl_balance = 0; |
| 112 | } |
| 113 | else { |
| 114 | // assert (x->avl_balance == -1); |
| 115 | w = x->avl_link[0]; |
| 116 | x->avl_link[0] = w->avl_link[1]; |
| 117 | w->avl_link[1] = x; |
| 118 | y->avl_link[1] = w->avl_link[0]; |
| 119 | w->avl_link[0] = y; |
| 120 | if (w->avl_balance == +1) |
| 121 | x->avl_balance = 0, y->avl_balance = -1; |
| 122 | else if (w->avl_balance == 0) |
| 123 | x->avl_balance = y->avl_balance = 0; |
| 124 | else /* |w->avl_balance == -1| */ |
| 125 | x->avl_balance = +1, y->avl_balance = 0; |
| 126 | w->avl_balance = 0; |
| 127 | } |
| 128 | } |
| 129 | else return n; |
| 130 | |
| 131 | z->avl_link[y != z->avl_link[0]] = w; |
| 132 | |
| 133 | // tree->avl_generation++; |
| 134 | return n; |
| 135 | } |
| 136 | |
| 137 | /* Deletes from |tree| and returns an item matching |item|. |
| 138 | Returns a null pointer if no matching item found. */ |
| 139 | avl_t *avl_remove(avl_tree_type *tree, avl_t *item) { |
| 140 | /* Stack of nodes. */ |
| 141 | avl_t *pa[AVL_MAX_HEIGHT]; /* Nodes. */ |
| 142 | unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */ |
| 143 | int k; /* Stack pointer. */ |
| 144 | |
| 145 | avl_t *p; /* Traverses tree to find node to delete. */ |
| 146 | int cmp; /* Result of comparison between |item| and |p|. */ |
| 147 | |
| 148 | // assert (tree != NULL && item != NULL); |
| 149 | |
| 150 | k = 0; |
| 151 | p = (avl_t *) &tree->root; |
| 152 | for(cmp = -1; cmp != 0; cmp = tree->compar(item, p)) { |
| 153 | unsigned char dir = (unsigned char)(cmp > 0); |
| 154 | |
| 155 | pa[k] = p; |
| 156 | da[k++] = dir; |
| 157 | |
| 158 | p = p->avl_link[dir]; |
| 159 | if(p == NULL) return NULL; |
| 160 | } |
| 161 | |
| 162 | item = p; |
| 163 | |
| 164 | if (p->avl_link[1] == NULL) |
| 165 | pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0]; |
| 166 | else { |
| 167 | avl_t *r = p->avl_link[1]; |
| 168 | if (r->avl_link[0] == NULL) { |
| 169 | r->avl_link[0] = p->avl_link[0]; |
| 170 | r->avl_balance = p->avl_balance; |
| 171 | pa[k - 1]->avl_link[da[k - 1]] = r; |
| 172 | da[k] = 1; |
| 173 | pa[k++] = r; |
| 174 | } |
| 175 | else { |
| 176 | avl_t *s; |
| 177 | int j = k++; |
| 178 | |
| 179 | for (;;) { |
| 180 | da[k] = 0; |
| 181 | pa[k++] = r; |
| 182 | s = r->avl_link[0]; |
| 183 | if (s->avl_link[0] == NULL) break; |
| 184 | |
| 185 | r = s; |
| 186 | } |
| 187 | |
| 188 | s->avl_link[0] = p->avl_link[0]; |
| 189 | r->avl_link[0] = s->avl_link[1]; |
| 190 | s->avl_link[1] = p->avl_link[1]; |
| 191 | s->avl_balance = p->avl_balance; |
| 192 | |
| 193 | pa[j - 1]->avl_link[da[j - 1]] = s; |
| 194 | da[j] = 1; |
| 195 | pa[j] = s; |
| 196 | } |
| 197 | } |
| 198 | |
| 199 | // assert (k > 0); |
| 200 | while (--k > 0) { |
| 201 | avl_t *y = pa[k]; |
| 202 | |
| 203 | if (da[k] == 0) { |
| 204 | y->avl_balance++; |
| 205 | if (y->avl_balance == +1) break; |
| 206 | else if (y->avl_balance == +2) { |
| 207 | avl_t *x = y->avl_link[1]; |
| 208 | if (x->avl_balance == -1) { |
| 209 | avl_t *w; |
| 210 | // assert (x->avl_balance == -1); |
| 211 | w = x->avl_link[0]; |
| 212 | x->avl_link[0] = w->avl_link[1]; |
| 213 | w->avl_link[1] = x; |
| 214 | y->avl_link[1] = w->avl_link[0]; |
| 215 | w->avl_link[0] = y; |
| 216 | if (w->avl_balance == +1) |
| 217 | x->avl_balance = 0, y->avl_balance = -1; |
| 218 | else if (w->avl_balance == 0) |
| 219 | x->avl_balance = y->avl_balance = 0; |
| 220 | else /* |w->avl_balance == -1| */ |
| 221 | x->avl_balance = +1, y->avl_balance = 0; |
| 222 | w->avl_balance = 0; |
| 223 | pa[k - 1]->avl_link[da[k - 1]] = w; |
| 224 | } |
| 225 | else { |
| 226 | y->avl_link[1] = x->avl_link[0]; |
| 227 | x->avl_link[0] = y; |
| 228 | pa[k - 1]->avl_link[da[k - 1]] = x; |
| 229 | if (x->avl_balance == 0) { |
| 230 | x->avl_balance = -1; |
| 231 | y->avl_balance = +1; |
| 232 | break; |
| 233 | } |
| 234 | else x->avl_balance = y->avl_balance = 0; |
| 235 | } |
| 236 | } |
| 237 | } |
| 238 | else |
| 239 | { |
| 240 | y->avl_balance--; |
| 241 | if (y->avl_balance == -1) break; |
| 242 | else if (y->avl_balance == -2) { |
| 243 | avl_t *x = y->avl_link[0]; |
| 244 | if (x->avl_balance == +1) { |
| 245 | avl_t *w; |
| 246 | // assert (x->avl_balance == +1); |
| 247 | w = x->avl_link[1]; |
| 248 | x->avl_link[1] = w->avl_link[0]; |
| 249 | w->avl_link[0] = x; |
| 250 | y->avl_link[0] = w->avl_link[1]; |
| 251 | w->avl_link[1] = y; |
| 252 | if (w->avl_balance == -1) |
| 253 | x->avl_balance = 0, y->avl_balance = +1; |
| 254 | else if (w->avl_balance == 0) |
| 255 | x->avl_balance = y->avl_balance = 0; |
| 256 | else /* |w->avl_balance == +1| */ |
| 257 | x->avl_balance = -1, y->avl_balance = 0; |
| 258 | w->avl_balance = 0; |
| 259 | pa[k - 1]->avl_link[da[k - 1]] = w; |
| 260 | } |
| 261 | else { |
| 262 | y->avl_link[0] = x->avl_link[1]; |
| 263 | x->avl_link[1] = y; |
| 264 | pa[k - 1]->avl_link[da[k - 1]] = x; |
| 265 | if (x->avl_balance == 0) { |
| 266 | x->avl_balance = +1; |
| 267 | y->avl_balance = -1; |
| 268 | break; |
| 269 | } |
| 270 | else x->avl_balance = y->avl_balance = 0; |
| 271 | } |
| 272 | } |
| 273 | } |
| 274 | } |
| 275 | |
| 276 | // tree->avl_count--; |
| 277 | // tree->avl_generation++; |
| 278 | return item; |
| 279 | } |
| 280 | |
| 281 | /* ------------------------------------------------------------------------- */ |
| 282 | // below are functions by Copyright 2018-2025 Netdata Inc. |
| 283 | |
| 284 | // --------------------------- |
| 285 | // traversing |
| 286 | |
| 287 | int avl_walker(avl_t *node, int (*callback)(void * /*entry*/, void * /*data*/), void *data) { |
| 288 | int total = 0, ret = 0; |
| 289 | |
| 290 | if(node->avl_link[0]) { |
| 291 | ret = avl_walker(node->avl_link[0], callback, data); |
| 292 | if(ret < 0) return ret; |
| 293 | total += ret; |
| 294 | } |
| 295 | |
| 296 | ret = callback(node, data); |
| 297 | if(ret < 0) return ret; |
| 298 | total += ret; |
| 299 | |
| 300 | if(node->avl_link[1]) { |
| 301 | ret = avl_walker(node->avl_link[1], callback, data); |
| 302 | if (ret < 0) return ret; |
| 303 | total += ret; |
| 304 | } |
| 305 | |
| 306 | return total; |
| 307 | } |
| 308 | |
| 309 | int avl_traverse(avl_tree_type *tree, int (*callback)(void * /*entry*/, void * /*data*/), void *data) { |
| 310 | if(tree->root) |
| 311 | return avl_walker(tree->root, callback, data); |
| 312 | else |
| 313 | return 0; |
| 314 | } |
| 315 | |
| 316 | // --------------------------- |
| 317 | // locks |
| 318 | |
| 319 | static inline void avl_read_lock(avl_tree_lock *t) { |
| 320 | #if defined(AVL_LOCK_WITH_RWLOCK) |
| 321 | netdata_rwlock_rdlock(&t->rwlock); |
| 322 | #else |
| 323 | rw_spinlock_read_lock(&t->rwlock); |
| 324 | #endif |
| 325 | } |
| 326 | |
| 327 | static inline void avl_write_lock(avl_tree_lock *t) { |
| 328 | #if defined(AVL_LOCK_WITH_RWLOCK) |
| 329 | netdata_rwlock_wrlock(&t->rwlock); |
| 330 | #else |
| 331 | rw_spinlock_write_lock(&t->rwlock); |
| 332 | #endif |
| 333 | } |
| 334 | |
| 335 | static inline void avl_read_unlock(avl_tree_lock *t) { |
| 336 | #if defined(AVL_LOCK_WITH_RWLOCK) |
| 337 | netdata_rwlock_rdunlock(&t->rwlock); |
| 338 | #else |
| 339 | rw_spinlock_read_unlock(&t->rwlock); |
| 340 | #endif |
| 341 | } |
| 342 | |
| 343 | static inline void avl_write_unlock(avl_tree_lock *t) { |
| 344 | #if defined(AVL_LOCK_WITH_RWLOCK) |
| 345 | netdata_rwlock_wrunlock(&t->rwlock); |
| 346 | #else |
| 347 | rw_spinlock_write_unlock(&t->rwlock); |
| 348 | #endif |
| 349 | } |
| 350 | |
| 351 | // --------------------------- |
| 352 | // operations with locking |
| 353 | |
| 354 | void avl_init_lock(avl_tree_lock *tree, int (*compar)(void * /*a*/, void * /*b*/)) { |
| 355 | avl_init(&tree->avl_tree, compar); |
| 356 | |
| 357 | #if defined(AVL_LOCK_WITH_RWLOCK) |
| 358 | if(netdata_rwlock_init(&tree->rwlock) != 0) |
| 359 | fatal("Failed to initialize AVL rwlock"); |
| 360 | #else |
| 361 | rw_spinlock_init(&tree->rwlock); |
| 362 | #endif |
| 363 | } |
| 364 | |
| 365 | void avl_destroy_lock(avl_tree_lock *tree __maybe_unused) { |
| 366 | #if defined(AVL_LOCK_WITH_RWLOCK) |
| 367 | if(netdata_rwlock_destroy(&tree->rwlock) != 0) |
| 368 | fatal("Failed to destroy AVL rwlock"); |
| 369 | #endif |
| 370 | } |
| 371 | |
| 372 | avl_t *avl_search_lock(avl_tree_lock *tree, avl_t *item) { |
| 373 | avl_read_lock(tree); |
| 374 | avl_t *ret = avl_search(&tree->avl_tree, item); |
| 375 | avl_read_unlock(tree); |
| 376 | return ret; |
| 377 | } |
| 378 | |
| 379 | avl_t * avl_remove_lock(avl_tree_lock *tree, avl_t *item) { |
| 380 | avl_write_lock(tree); |
| 381 | avl_t *ret = avl_remove(&tree->avl_tree, item); |
| 382 | avl_write_unlock(tree); |
| 383 | return ret; |
| 384 | } |
| 385 | |
| 386 | avl_t *avl_insert_lock(avl_tree_lock *tree, avl_t *item) { |
| 387 | avl_write_lock(tree); |
| 388 | avl_t * ret = avl_insert(&tree->avl_tree, item); |
| 389 | avl_write_unlock(tree); |
| 390 | return ret; |
| 391 | } |
| 392 | |
| 393 | int avl_traverse_lock(avl_tree_lock *tree, int (*callback)(void * /*entry*/, void * /*data*/), void *data) { |
| 394 | avl_read_lock(tree); |
| 395 | int ret = avl_traverse(&tree->avl_tree, callback, data); |
| 396 | avl_read_unlock(tree); |
| 397 | return ret; |
| 398 | } |
| 399 | |
| 400 | void avl_init(avl_tree_type *tree, int (*compar)(void * /*a*/, void * /*b*/)) { |
| 401 | tree->root = NULL; |
| 402 | tree->compar = compar; |
| 403 | } |
| 404 | |
| 405 | // ------------------ |