summaryrefslogtreecommitdiffstats
path: root/libnetdata/avl
diff options
context:
space:
mode:
Diffstat (limited to 'libnetdata/avl')
-rw-r--r--libnetdata/avl/avl.c56
-rw-r--r--libnetdata/avl/avl.h20
2 files changed, 38 insertions, 38 deletions
diff --git a/libnetdata/avl/avl.c b/libnetdata/avl/avl.c
index 52198518..b05b97ac 100644
--- a/libnetdata/avl/avl.c
+++ b/libnetdata/avl/avl.c
@@ -17,8 +17,8 @@
/* Search |tree| for an item matching |item|, and return it if found.
Otherwise return |NULL|. */
-avl *avl_search(avl_tree_type *tree, avl *item) {
- avl *p;
+avl_t *avl_search(avl_tree_type *tree, avl_t *item) {
+ avl_t *p;
// assert (tree != NULL && item != NULL);
@@ -40,11 +40,11 @@ avl *avl_search(avl_tree_type *tree, avl *item) {
If a duplicate item is found in the tree,
returns a pointer to the duplicate without inserting |item|.
*/
-avl *avl_insert(avl_tree_type *tree, avl *item) {
- avl *y, *z; /* Top node to update balance factor, and parent. */
- avl *p, *q; /* Iterator, and parent. */
- avl *n; /* Newly inserted node. */
- avl *w; /* New root of rebalanced subtree. */
+avl_t *avl_insert(avl_tree_type *tree, avl_t *item) {
+ avl_t *y, *z; /* Top node to update balance factor, and parent. */
+ avl_t *p, *q; /* Iterator, and parent. */
+ avl_t *n; /* Newly inserted node. */
+ avl_t *w; /* New root of rebalanced subtree. */
unsigned char dir; /* Direction to descend. */
unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */
@@ -52,7 +52,7 @@ avl *avl_insert(avl_tree_type *tree, avl *item) {
// assert(tree != NULL && item != NULL);
- z = (avl *) &tree->root;
+ z = (avl_t *) &tree->root;
y = tree->root;
dir = 0;
for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) {
@@ -79,7 +79,7 @@ avl *avl_insert(avl_tree_type *tree, avl *item) {
p->avl_balance++;
if (y->avl_balance == -2) {
- avl *x = y->avl_link[0];
+ avl_t *x = y->avl_link[0];
if (x->avl_balance == -1) {
w = x;
y->avl_link[0] = x->avl_link[1];
@@ -103,7 +103,7 @@ avl *avl_insert(avl_tree_type *tree, avl *item) {
}
}
else if (y->avl_balance == +2) {
- avl *x = y->avl_link[1];
+ avl_t *x = y->avl_link[1];
if (x->avl_balance == +1) {
w = x;
y->avl_link[1] = x->avl_link[0];
@@ -136,19 +136,19 @@ avl *avl_insert(avl_tree_type *tree, avl *item) {
/* Deletes from |tree| and returns an item matching |item|.
Returns a null pointer if no matching item found. */
-avl *avl_remove(avl_tree_type *tree, avl *item) {
+avl_t *avl_remove(avl_tree_type *tree, avl_t *item) {
/* Stack of nodes. */
- avl *pa[AVL_MAX_HEIGHT]; /* Nodes. */
+ avl_t *pa[AVL_MAX_HEIGHT]; /* Nodes. */
unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */
int k; /* Stack pointer. */
- avl *p; /* Traverses tree to find node to delete. */
+ avl_t *p; /* Traverses tree to find node to delete. */
int cmp; /* Result of comparison between |item| and |p|. */
// assert (tree != NULL && item != NULL);
k = 0;
- p = (avl *) &tree->root;
+ p = (avl_t *) &tree->root;
for(cmp = -1; cmp != 0; cmp = tree->compar(item, p)) {
unsigned char dir = (unsigned char)(cmp > 0);
@@ -164,7 +164,7 @@ avl *avl_remove(avl_tree_type *tree, avl *item) {
if (p->avl_link[1] == NULL)
pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];
else {
- avl *r = p->avl_link[1];
+ avl_t *r = p->avl_link[1];
if (r->avl_link[0] == NULL) {
r->avl_link[0] = p->avl_link[0];
r->avl_balance = p->avl_balance;
@@ -173,7 +173,7 @@ avl *avl_remove(avl_tree_type *tree, avl *item) {
pa[k++] = r;
}
else {
- avl *s;
+ avl_t *s;
int j = k++;
for (;;) {
@@ -198,15 +198,15 @@ avl *avl_remove(avl_tree_type *tree, avl *item) {
// assert (k > 0);
while (--k > 0) {
- avl *y = pa[k];
+ avl_t *y = pa[k];
if (da[k] == 0) {
y->avl_balance++;
if (y->avl_balance == +1) break;
else if (y->avl_balance == +2) {
- avl *x = y->avl_link[1];
+ avl_t *x = y->avl_link[1];
if (x->avl_balance == -1) {
- avl *w;
+ avl_t *w;
// assert (x->avl_balance == -1);
w = x->avl_link[0];
x->avl_link[0] = w->avl_link[1];
@@ -240,9 +240,9 @@ avl *avl_remove(avl_tree_type *tree, avl *item) {
y->avl_balance--;
if (y->avl_balance == -1) break;
else if (y->avl_balance == -2) {
- avl *x = y->avl_link[0];
+ avl_t *x = y->avl_link[0];
if (x->avl_balance == +1) {
- avl *w;
+ avl_t *w;
// assert (x->avl_balance == +1);
w = x->avl_link[1];
x->avl_link[1] = w->avl_link[0];
@@ -284,7 +284,7 @@ avl *avl_remove(avl_tree_type *tree, avl *item) {
// ---------------------------
// traversing
-int avl_walker(avl *node, int (*callback)(void * /*entry*/, void * /*data*/), void *data) {
+int avl_walker(avl_t *node, int (*callback)(void * /*entry*/, void * /*data*/), void *data) {
int total = 0, ret = 0;
if(node->avl_link[0]) {
@@ -383,23 +383,23 @@ void avl_destroy_lock(avl_tree_lock *tree) {
#endif /* AVL_WITHOUT_PTHREADS */
}
-avl *avl_search_lock(avl_tree_lock *tree, avl *item) {
+avl_t *avl_search_lock(avl_tree_lock *tree, avl_t *item) {
avl_read_lock(tree);
- avl *ret = avl_search(&tree->avl_tree, item);
+ avl_t *ret = avl_search(&tree->avl_tree, item);
avl_unlock(tree);
return ret;
}
-avl * avl_remove_lock(avl_tree_lock *tree, avl *item) {
+avl_t * avl_remove_lock(avl_tree_lock *tree, avl_t *item) {
avl_write_lock(tree);
- avl *ret = avl_remove(&tree->avl_tree, item);
+ avl_t *ret = avl_remove(&tree->avl_tree, item);
avl_unlock(tree);
return ret;
}
-avl *avl_insert_lock(avl_tree_lock *tree, avl *item) {
+avl_t *avl_insert_lock(avl_tree_lock *tree, avl_t *item) {
avl_write_lock(tree);
- avl * ret = avl_insert(&tree->avl_tree, item);
+ avl_t * ret = avl_insert(&tree->avl_tree, item);
avl_unlock(tree);
return ret;
}
diff --git a/libnetdata/avl/avl.h b/libnetdata/avl/avl.h
index 32e3f27a..eba967fd 100644
--- a/libnetdata/avl/avl.h
+++ b/libnetdata/avl/avl.h
@@ -28,14 +28,14 @@
/* Data structures */
/* One element of the AVL tree */
-typedef struct avl {
- struct avl *avl_link[2]; /* Subtrees. */
+typedef struct avl_element {
+ struct avl_element *avl_link[2]; /* Subtrees. */
signed char avl_balance; /* Balance factor. */
-} avl;
+} avl_t;
/* An AVL tree */
typedef struct avl_tree_type {
- avl *root;
+ avl_t *root;
int (*compar)(void *a, void *b);
} avl_tree_type;
@@ -59,23 +59,23 @@ typedef struct avl_tree_lock {
* a is linked directly to the tree, so it has to
* be properly allocated by the caller.
*/
-avl *avl_insert_lock(avl_tree_lock *tree, avl *item) NEVERNULL WARNUNUSED;
-avl *avl_insert(avl_tree_type *tree, avl *item) NEVERNULL WARNUNUSED;
+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 *avl_remove_lock(avl_tree_lock *tree, avl *item) WARNUNUSED;
-avl *avl_remove(avl_tree_type *tree, avl *item) WARNUNUSED;
+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 *avl_search_lock(avl_tree_lock *tree, avl *item);
-avl *avl_search(avl_tree_type *tree, avl *item);
+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
*/
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-16 00:33:55 +0000