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