diff options
Diffstat (limited to 'libnetdata/avl/avl.c')
| -rw-r--r-- | libnetdata/avl/avl.c | 56 |
1 files changed, 28 insertions, 28 deletions
diff --git a/libnetdata/avl/avl.c b/libnetdata/avl/avl.c index 521985189..b05b97acb 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; } |