| 1 | // SPDX-License-Identifier: LGPL-3.0-or-later |
| 2 | |
| 3 | #ifndef _AVL_H |
| 4 | #define _AVL_H 1 |
| 5 | |
| 6 | #include "../libnetdata.h" |
| 7 | |
| 8 | /* Maximum AVL tree height. */ |
| 9 | #ifndef AVL_MAX_HEIGHT |
| 10 | #define AVL_MAX_HEIGHT 92 |
| 11 | #endif |
| 12 | |
| 13 | #if defined(AVL_LOCK_WITH_RWLOCK) |
| 14 | #define AVL_LOCK_INITIALIZER NETDATA_RWLOCK_INITIALIZER |
| 15 | #else |
| 16 | #define AVL_LOCK_INITIALIZER RW_SPINLOCK_INITIALIZER |
| 17 | #endif |
| 18 | |
| 19 | /* Data structures */ |
| 20 | |
| 21 | /* One element of the AVL tree */ |
| 22 | typedef struct avl_element { |
| 23 | struct avl_element *avl_link[2]; /* Subtrees. */ |
| 24 | signed char avl_balance; /* Balance factor. */ |
| 25 | } avl_t; |
| 26 | |
| 27 | typedef struct __attribute__((packed)) avl_element_packed { |
| 28 | struct avl_element *avl_link[2]; /* Subtrees. */ |
| 29 | signed char avl_balance; /* Balance factor. */ |
| 30 | } avl_t_packed; |
| 31 | |
| 32 | /* An AVL tree */ |
| 33 | typedef struct avl_tree_type { |
| 34 | avl_t *root; |
| 35 | int (*compar)(void *a, void *b); |
| 36 | } avl_tree_type; |
| 37 | |
| 38 | typedef struct avl_tree_lock { |
| 39 | avl_tree_type avl_tree; |
| 40 | |
| 41 | #if defined(AVL_LOCK_WITH_RWLOCK) |
| 42 | netdata_rwlock_t rwlock; |
| 43 | #else |
| 44 | RW_SPINLOCK rwlock; |
| 45 | #endif |
| 46 | } avl_tree_lock; |
| 47 | |
| 48 | /* Public methods */ |
| 49 | |
| 50 | /* Insert element a into the AVL tree t |
| 51 | * returns the added element a, or a pointer the |
| 52 | * element that is equal to a (as returned by t->compar()) |
| 53 | * a is linked directly to the tree, so it has to |
| 54 | * be properly allocated by the caller. |
| 55 | */ |
| 56 | avl_t *avl_insert_lock(avl_tree_lock *tree, avl_t *item) NEVERNULL WARNUNUSED; |
| 57 | avl_t *avl_insert(avl_tree_type *tree, avl_t *item) NEVERNULL WARNUNUSED; |
| 58 | |
| 59 | /* Remove an element a from the AVL tree t |
| 60 | * returns a pointer to the removed element |
| 61 | * or NULL if an element equal to a is not found |
| 62 | * (equal as returned by t->compar()) |
| 63 | */ |
| 64 | avl_t *avl_remove_lock(avl_tree_lock *tree, avl_t *item) WARNUNUSED; |
| 65 | avl_t *avl_remove(avl_tree_type *tree, avl_t *item) WARNUNUSED; |
| 66 | |
| 67 | /* Find the element into the tree that equal to a |
| 68 | * (equal as returned by t->compar()) |
| 69 | * returns NULL is no element is equal to a |
| 70 | */ |
| 71 | avl_t *avl_search_lock(avl_tree_lock *tree, avl_t *item); |
| 72 | avl_t *avl_search(avl_tree_type *tree, avl_t *item); |
| 73 | |
| 74 | /* Initialize the avl_tree_lock |
| 75 | */ |
| 76 | void avl_init_lock(avl_tree_lock *tree, int (*compar)(void *a, void *b)); |
| 77 | void avl_init(avl_tree_type *tree, int (*compar)(void *a, void *b)); |
| 78 | |
| 79 | /* Destroy the avl_tree_lock locks |
| 80 | */ |
| 81 | void avl_destroy_lock(avl_tree_lock *tree); |
| 82 | |
| 83 | int avl_traverse_lock(avl_tree_lock *tree, int (*callback)(void *entry, void *data), void *data); |
| 84 | int avl_traverse(avl_tree_type *tree, int (*callback)(void *entry, void *data), void *data); |
| 85 | |
| 86 | #endif /* avl.h */ |