diff options
author | Federico Ceratto <federico.ceratto@gmail.com> | 2016-03-30 21:40:42 +0000 |
---|---|---|
committer | Federico Ceratto <federico.ceratto@gmail.com> | 2016-03-30 21:40:42 +0000 |
commit | 9ce153ce7167c11adba8ac225edc7a707e97c6eb (patch) | |
tree | 9f6e849cce2dcc7e5b4e9e6252c843dc2d0787a2 /src/avl.c | |
download | netdata-9ce153ce7167c11adba8ac225edc7a707e97c6eb.tar.xz netdata-9ce153ce7167c11adba8ac225edc7a707e97c6eb.zip |
Imported Upstream version 1.0.0upstream/1.0.0
Diffstat (limited to 'src/avl.c')
-rwxr-xr-x | src/avl.c | 398 |
1 files changed, 398 insertions, 0 deletions
diff --git a/src/avl.c b/src/avl.c new file mode 100755 index 00000000..4eb0ce0e --- /dev/null +++ b/src/avl.c @@ -0,0 +1,398 @@ +/* + * ANSI C Library for maintainance of AVL Balanced Trees + * + * ref.: + * G. M. Adelson-Velskij & E. M. Landis + * Doklady Akad. Nauk SSSR 146 (1962), 263-266 + * + * see also: + * D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching) + * + * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics + * Released under GNU General Public License (GPL) version 2 + * + */ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif +#include "avl.h" + +/* Private methods */ +int _avl_removeroot(avl_tree* t); + +/* Swing to the left + * Warning: no balance maintainance + */ +void avl_swl(avl** root) { + avl* a = *root; + avl* b = a->right; + *root = b; + a->right = b->left; + b->left = a; +} + +/* Swing to the right + * Warning: no balance maintainance + */ +void avl_swr(avl** root) { + avl* a = *root; + avl* b = a->left; + *root = b; + a->left = b->right; + b->right = a; +} + +/* Balance maintainance after especially nasty swings + */ +void avl_nasty(avl* root) { + switch (root->balance) { + case -1: + root->left->balance = 0; + root->right->balance = 1; + break; + case 1: + root->left->balance = -1; + root->right->balance = 0; + break; + case 0: + root->left->balance = 0; + root->right->balance = 0; + } + root->balance = 0; +} + +/* Public methods */ + +/* Insert element a into the AVL tree t + * returns 1 if the depth of the tree has grown + * Warning: do not insert elements already present + */ +int _avl_insert(avl_tree* t, avl* a) { + /* initialize */ + a->left = 0; + a->right = 0; + a->balance = 0; + /* insert into an empty tree */ + if (!t->root) { + t->root = a; + return 1; + } + + if (t->compar(t->root, a) > 0) { + /* insert into the left subtree */ + if (t->root->left) { + avl_tree left_subtree; + left_subtree.root = t->root->left; + left_subtree.compar = t->compar; + if (_avl_insert(&left_subtree, a)) { + switch (t->root->balance--) { + case 1: + return 0; + case 0: + return 1; + } + if (t->root->left->balance < 0) { + avl_swr(&(t->root)); + t->root->balance = 0; + t->root->right->balance = 0; + } else { + avl_swl(&(t->root->left)); + avl_swr(&(t->root)); + avl_nasty(t->root); + } + } else + t->root->left = left_subtree.root; + return 0; + } else { + t->root->left = a; + if (t->root->balance--) + return 0; + return 1; + } + } else { + /* insert into the right subtree */ + if (t->root->right) { + avl_tree right_subtree; + right_subtree.root = t->root->right; + right_subtree.compar = t->compar; + if (_avl_insert(&right_subtree, a)) { + switch (t->root->balance++) { + case -1: + return 0; + case 0: + return 1; + } + if (t->root->right->balance > 0) { + avl_swl(&(t->root)); + t->root->balance = 0; + t->root->left->balance = 0; + } else { + avl_swr(&(t->root->right)); + avl_swl(&(t->root)); + avl_nasty(t->root); + } + } else + t->root->right = right_subtree.root; + return 0; + } else { + t->root->right = a; + if (t->root->balance++) + return 0; + return 1; + } + } +} +int avl_insert(avl_tree* t, avl* a) { +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_lock(&t->mutex); +#else + pthread_rwlock_wrlock(&t->rwlock); +#endif + + int ret = _avl_insert(t, a); + +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_unlock(&t->mutex); +#else + pthread_rwlock_unlock(&t->rwlock); +#endif + return ret; +} + +/* Remove an element a from the AVL tree t + * returns -1 if the depth of the tree has shrunk + * Warning: if the element is not present in the tree, + * returns 0 as if it had been removed succesfully. + */ +int _avl_remove(avl_tree* t, avl* a) { + int b; + if (t->root == a) + return _avl_removeroot(t); + b = t->compar(t->root, a); + if (b >= 0) { + /* remove from the left subtree */ + int ch; + avl_tree left_subtree; + if ((left_subtree.root = t->root->left)) { + left_subtree.compar = t->compar; + ch = _avl_remove(&left_subtree, a); + t->root->left = left_subtree.root; + if (ch) { + switch (t->root->balance++) { + case -1: + return -1; + case 0: + return 0; + } + switch (t->root->right->balance) { + case 0: + avl_swl(&(t->root)); + t->root->balance = -1; + t->root->left->balance = 1; + return 0; + case 1: + avl_swl(&(t->root)); + t->root->balance = 0; + t->root->left->balance = 0; + return -1; + } + avl_swr(&(t->root->right)); + avl_swl(&(t->root)); + avl_nasty(t->root); + return -1; + } + } + } + if (b <= 0) { + /* remove from the right subtree */ + int ch; + avl_tree right_subtree; + if ((right_subtree.root = t->root->right)) { + right_subtree.compar = t->compar; + ch = _avl_remove(&right_subtree, a); + t->root->right = right_subtree.root; + if (ch) { + switch (t->root->balance--) { + case 1: + return -1; + case 0: + return 0; + } + switch (t->root->left->balance) { + case 0: + avl_swr(&(t->root)); + t->root->balance = 1; + t->root->right->balance = -1; + return 0; + case -1: + avl_swr(&(t->root)); + t->root->balance = 0; + t->root->right->balance = 0; + return -1; + } + avl_swl(&(t->root->left)); + avl_swr(&(t->root)); + avl_nasty(t->root); + return -1; + } + } + } + return 0; +} + +int avl_remove(avl_tree* t, avl* a) { +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_lock(&t->mutex); +#else + pthread_rwlock_wrlock(&t->rwlock); +#endif + + int ret = _avl_remove(t, a); + +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_unlock(&t->mutex); +#else + pthread_rwlock_unlock(&t->rwlock); +#endif + return ret; +} + +/* Remove the root of the AVL tree t + * Warning: dumps core if t is empty + */ +int _avl_removeroot(avl_tree* t) { + int ch; + avl* a; + if (!t->root->left) { + if (!t->root->right) { + t->root = 0; + return -1; + } + t->root = t->root->right; + return -1; + } + if (!t->root->right) { + t->root = t->root->left; + return -1; + } + if (t->root->balance < 0) { + /* remove from the left subtree */ + a = t->root->left; + while (a->right) + a = a->right; + } else { + /* remove from the right subtree */ + a = t->root->right; + while (a->left) + a = a->left; + } + ch = _avl_remove(t, a); + a->left = t->root->left; + a->right = t->root->right; + a->balance = t->root->balance; + t->root = a; + if (a->balance == 0) + return ch; + return 0; +} + +int avl_removeroot(avl_tree* t) { +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_lock(&t->mutex); +#else + pthread_rwlock_wrlock(&t->rwlock); +#endif + + int ret = _avl_removeroot(t); + +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_unlock(&t->mutex); +#else + pthread_rwlock_unlock(&t->rwlock); +#endif + return ret; +} + +/* Iterate through elements in t from a range between a and b (inclusive) + * for each element calls iter(a) until it returns 0 + * returns the last value returned by iterator or 0 if there were no calls + * Warning: a<=b must hold + */ +int _avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) { + int x, c = 0; + if (!t->root) + return 0; + x = t->compar(t->root, a); + if (a != b) { + if (x < 0) { + x = t->compar(t->root, b); + if (x > 0) + x = 0; + } + } + if (x >= 0) { + /* search in the left subtree */ + avl_tree left_subtree; + if ((left_subtree.root = t->root->left)) { + left_subtree.compar = t->compar; + if (!(c = _avl_range(&left_subtree, a, b, iter, ret))) + if (x > 0) + return 0; + } + } + if (x == 0) { + if (!(c = iter(t->root))) { + if (ret) + *ret = t->root; + return 0; + } + } + if (x <= 0) { + /* search in the right subtree */ + avl_tree right_subtree; + if ((right_subtree.root = t->root->right)) { + right_subtree.compar = t->compar; + if (!(c = _avl_range(&right_subtree, a, b, iter, ret))) + if (x < 0) + return 0; + } + } + return c; +} + +int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) { +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_lock(&t->mutex); +#else + pthread_rwlock_wrlock(&t->rwlock); +#endif + + int ret2 = _avl_range(t, a, b, iter, ret); + +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_unlock(&t->mutex); +#else + pthread_rwlock_unlock(&t->rwlock); +#endif + + return ret2; +} + +/* Iterate through elements in t equal to a + * for each element calls iter(a) until it returns 0 + * returns the last value returned by iterator or 0 if there were no calls + */ +int avl_search(avl_tree* t, avl* a, int (*iter)(avl* a), avl** ret) { + return avl_range(t, a, a, iter, ret); +} + +void avl_init(avl_tree* t, int (*compar)(void* a, void* b)) { + t->root = NULL; + t->compar = compar; +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_init(&t->mutex, NULL); +#else + pthread_rwlock_init(&t->rwlock, NULL); +#endif +} |