* Florian octo Forster <octo at collectd.org>
**/
-#include <stdlib.h>
#include <assert.h>
+#include <stdlib.h>
#include "utils_avltree.h"
-#define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
- - (((n)->right == NULL) ? 0 : (n)->right->height))
+#define BALANCE(n) \
+ ((((n)->left == NULL) ? 0 : (n)->left->height) - \
+ (((n)->right == NULL) ? 0 : (n)->right->height))
/*
* private data types
*/
-struct c_avl_node_s
-{
- void *key;
- void *value;
-
- int height;
- struct c_avl_node_s *left;
- struct c_avl_node_s *right;
- struct c_avl_node_s *parent;
+struct c_avl_node_s {
+ void *key;
+ void *value;
+
+ int height;
+ struct c_avl_node_s *left;
+ struct c_avl_node_s *right;
+ struct c_avl_node_s *parent;
};
typedef struct c_avl_node_s c_avl_node_t;
-struct c_avl_tree_s
-{
- c_avl_node_t *root;
- int (*compare) (const void *, const void *);
- int size;
+struct c_avl_tree_s {
+ c_avl_node_t *root;
+ int (*compare)(const void *, const void *);
+ int size;
};
-struct c_avl_iterator_s
-{
- c_avl_tree_t *tree;
- c_avl_node_t *node;
+struct c_avl_iterator_s {
+ c_avl_tree_t *tree;
+ c_avl_node_t *node;
};
/*
assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
} /* void verify_tree */
#else
-# define verify_tree(n) /**/
+#define verify_tree(n) /**/
#endif
-static void free_node (c_avl_node_t *n)
-{
- if (n == NULL)
- return;
+static void free_node(c_avl_node_t *n) {
+ if (n == NULL)
+ return;
- if (n->left != NULL)
- free_node (n->left);
- if (n->right != NULL)
- free_node (n->right);
+ if (n->left != NULL)
+ free_node(n->left);
+ if (n->right != NULL)
+ free_node(n->right);
- free (n);
+ free(n);
}
-static int calc_height (c_avl_node_t *n)
-{
- int height_left;
- int height_right;
+static int calc_height(c_avl_node_t *n) {
+ int height_left;
+ int height_right;
- if (n == NULL)
- return (0);
+ if (n == NULL)
+ return 0;
- height_left = (n->left == NULL) ? 0 : n->left->height;
- height_right = (n->right == NULL) ? 0 : n->right->height;
+ height_left = (n->left == NULL) ? 0 : n->left->height;
+ height_right = (n->right == NULL) ? 0 : n->right->height;
- return (((height_left > height_right)
- ? height_left
- : height_right) + 1);
+ return ((height_left > height_right) ? height_left : height_right) + 1;
} /* int calc_height */
-static c_avl_node_t *search (c_avl_tree_t *t, const void *key)
-{
- c_avl_node_t *n;
- int cmp;
-
- n = t->root;
- while (n != NULL)
- {
- cmp = t->compare (key, n->key);
- if (cmp == 0)
- return (n);
- else if (cmp < 0)
- n = n->left;
- else
- n = n->right;
- }
-
- return (NULL);
+static c_avl_node_t *search(c_avl_tree_t *t, const void *key) {
+ c_avl_node_t *n;
+ int cmp;
+
+ n = t->root;
+ while (n != NULL) {
+ cmp = t->compare(key, n->key);
+ if (cmp == 0)
+ return n;
+ else if (cmp < 0)
+ n = n->left;
+ else
+ n = n->right;
+ }
+
+ return NULL;
}
/* (x) (y)
* / a\ /_b\ /_b\ /_c\
* /____\
*/
-static c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
-{
- c_avl_node_t *p;
- c_avl_node_t *y;
- c_avl_node_t *b;
-
- assert (x != NULL);
- assert (x->left != NULL);
-
- p = x->parent;
- y = x->left;
- b = y->right;
-
- x->left = b;
- if (b != NULL)
- b->parent = x;
-
- x->parent = y;
- y->right = x;
-
- y->parent = p;
- assert ((p == NULL) || (p->left == x) || (p->right == x));
- if (p == NULL)
- t->root = y;
- else if (p->left == x)
- p->left = y;
- else
- p->right = y;
-
- x->height = calc_height (x);
- y->height = calc_height (y);
-
- return (y);
+static c_avl_node_t *rotate_right(c_avl_tree_t *t, c_avl_node_t *x) {
+ c_avl_node_t *p;
+ c_avl_node_t *y;
+ c_avl_node_t *b;
+
+ assert(x != NULL);
+ assert(x->left != NULL);
+
+ p = x->parent;
+ y = x->left;
+ b = y->right;
+
+ x->left = b;
+ if (b != NULL)
+ b->parent = x;
+
+ x->parent = y;
+ y->right = x;
+
+ y->parent = p;
+ assert((p == NULL) || (p->left == x) || (p->right == x));
+ if (p == NULL)
+ t->root = y;
+ else if (p->left == x)
+ p->left = y;
+ else
+ p->right = y;
+
+ x->height = calc_height(x);
+ y->height = calc_height(y);
+
+ return y;
} /* void rotate_right */
/*
* /_b\ / c\ /_a\ /_b\
* /____\
*/
-static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
-{
- c_avl_node_t *p;
- c_avl_node_t *y;
- c_avl_node_t *b;
-
- assert (x != NULL);
- assert (x->right != NULL);
-
- p = x->parent;
- y = x->right;
- b = y->left;
-
- x->right = b;
- if (b != NULL)
- b->parent = x;
-
- x->parent = y;
- y->left = x;
-
- y->parent = p;
- assert ((p == NULL) || (p->left == x) || (p->right == x));
- if (p == NULL)
- t->root = y;
- else if (p->left == x)
- p->left = y;
- else
- p->right = y;
-
- x->height = calc_height (x);
- y->height = calc_height (y);
-
- return (y);
+static c_avl_node_t *rotate_left(c_avl_tree_t *t, c_avl_node_t *x) {
+ c_avl_node_t *p;
+ c_avl_node_t *y;
+ c_avl_node_t *b;
+
+ assert(x != NULL);
+ assert(x->right != NULL);
+
+ p = x->parent;
+ y = x->right;
+ b = y->left;
+
+ x->right = b;
+ if (b != NULL)
+ b->parent = x;
+
+ x->parent = y;
+ y->left = x;
+
+ y->parent = p;
+ assert((p == NULL) || (p->left == x) || (p->right == x));
+ if (p == NULL)
+ t->root = y;
+ else if (p->left == x)
+ p->left = y;
+ else
+ p->right = y;
+
+ x->height = calc_height(x);
+ y->height = calc_height(y);
+
+ return y;
} /* void rotate_left */
-static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
-{
- rotate_left (t, x->left);
- return (rotate_right (t, x));
+static c_avl_node_t *rotate_left_right(c_avl_tree_t *t, c_avl_node_t *x) {
+ rotate_left(t, x->left);
+ return rotate_right(t, x);
} /* void rotate_left_right */
-static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
-{
- rotate_right (t, x->right);
- return (rotate_left (t, x));
+static c_avl_node_t *rotate_right_left(c_avl_tree_t *t, c_avl_node_t *x) {
+ rotate_right(t, x->right);
+ return rotate_left(t, x);
} /* void rotate_right_left */
-static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
-{
- int b_top;
- int b_bottom;
-
- while (n != NULL)
- {
- b_top = BALANCE (n);
- assert ((b_top >= -2) && (b_top <= 2));
-
- if (b_top == -2)
- {
- assert (n->right != NULL);
- b_bottom = BALANCE (n->right);
- assert ((b_bottom >= -1) && (b_bottom <= 1));
- if (b_bottom == 1)
- n = rotate_right_left (t, n);
- else
- n = rotate_left (t, n);
- }
- else if (b_top == 2)
- {
- assert (n->left != NULL);
- b_bottom = BALANCE (n->left);
- assert ((b_bottom >= -1) && (b_bottom <= 1));
- if (b_bottom == -1)
- n = rotate_left_right (t, n);
- else
- n = rotate_right (t, n);
- }
- else
- {
- int height = calc_height (n);
- if (height == n->height)
- break;
- n->height = height;
- }
-
- assert (n->height == calc_height (n));
-
- n = n->parent;
- } /* while (n != NULL) */
+static void rebalance(c_avl_tree_t *t, c_avl_node_t *n) {
+ int b_top;
+ int b_bottom;
+
+ while (n != NULL) {
+ b_top = BALANCE(n);
+ assert((b_top >= -2) && (b_top <= 2));
+
+ if (b_top == -2) {
+ assert(n->right != NULL);
+ b_bottom = BALANCE(n->right);
+ assert((b_bottom >= -1) && (b_bottom <= 1));
+ if (b_bottom == 1)
+ n = rotate_right_left(t, n);
+ else
+ n = rotate_left(t, n);
+ } else if (b_top == 2) {
+ assert(n->left != NULL);
+ b_bottom = BALANCE(n->left);
+ assert((b_bottom >= -1) && (b_bottom <= 1));
+ if (b_bottom == -1)
+ n = rotate_left_right(t, n);
+ else
+ n = rotate_right(t, n);
+ } else {
+ int height = calc_height(n);
+ if (height == n->height)
+ break;
+ n->height = height;
+ }
+
+ assert(n->height == calc_height(n));
+
+ n = n->parent;
+ } /* while (n != NULL) */
} /* void rebalance */
-static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
-{
- c_avl_node_t *r; /* return node */
-
- if (n == NULL)
- {
- return (NULL);
- }
-
- /* If we can't descent any further, we have to backtrack to the first
- * parent that's bigger than we, i. e. who's _left_ child we are. */
- if (n->right == NULL)
- {
- r = n->parent;
- while ((r != NULL) && (r->parent != NULL))
- {
- if (r->left == n)
- break;
- n = r;
- r = n->parent;
- }
-
- /* n->right == NULL && r == NULL => t is root and has no next
- * r->left != n => r->right = n => r->parent == NULL */
- if ((r == NULL) || (r->left != n))
- {
- assert ((r == NULL) || (r->parent == NULL));
- return (NULL);
- }
- else
- {
- assert (r->left == n);
- return (r);
- }
- }
- else
- {
- r = n->right;
- while (r->left != NULL)
- r = r->left;
- }
-
- return (r);
+static c_avl_node_t *c_avl_node_next(c_avl_node_t *n) {
+ c_avl_node_t *r; /* return node */
+
+ if (n == NULL) {
+ return NULL;
+ }
+
+ /* If we can't descent any further, we have to backtrack to the first
+ * parent that's bigger than we, i. e. who's _left_ child we are. */
+ if (n->right == NULL) {
+ r = n->parent;
+ while ((r != NULL) && (r->parent != NULL)) {
+ if (r->left == n)
+ break;
+ n = r;
+ r = n->parent;
+ }
+
+ /* n->right == NULL && r == NULL => t is root and has no next
+ * r->left != n => r->right = n => r->parent == NULL */
+ if ((r == NULL) || (r->left != n)) {
+ assert((r == NULL) || (r->parent == NULL));
+ return NULL;
+ } else {
+ assert(r->left == n);
+ return r;
+ }
+ } else {
+ r = n->right;
+ while (r->left != NULL)
+ r = r->left;
+ }
+
+ return r;
} /* c_avl_node_t *c_avl_node_next */
-static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
-{
- c_avl_node_t *r; /* return node */
-
- if (n == NULL)
- {
- return (NULL);
- }
-
- /* If we can't descent any further, we have to backtrack to the first
- * parent that's smaller than we, i. e. who's _right_ child we are. */
- if (n->left == NULL)
- {
- r = n->parent;
- while ((r != NULL) && (r->parent != NULL))
- {
- if (r->right == n)
- break;
- n = r;
- r = n->parent;
- }
-
- /* n->left == NULL && r == NULL => t is root and has no next
- * r->right != n => r->left = n => r->parent == NULL */
- if ((r == NULL) || (r->right != n))
- {
- assert ((r == NULL) || (r->parent == NULL));
- return (NULL);
- }
- else
- {
- assert (r->right == n);
- return (r);
- }
- }
- else
- {
- r = n->left;
- while (r->right != NULL)
- r = r->right;
- }
-
- return (r);
+static c_avl_node_t *c_avl_node_prev(c_avl_node_t *n) {
+ c_avl_node_t *r; /* return node */
+
+ if (n == NULL) {
+ return NULL;
+ }
+
+ /* If we can't descent any further, we have to backtrack to the first
+ * parent that's smaller than we, i. e. who's _right_ child we are. */
+ if (n->left == NULL) {
+ r = n->parent;
+ while ((r != NULL) && (r->parent != NULL)) {
+ if (r->right == n)
+ break;
+ n = r;
+ r = n->parent;
+ }
+
+ /* n->left == NULL && r == NULL => t is root and has no next
+ * r->right != n => r->left = n => r->parent == NULL */
+ if ((r == NULL) || (r->right != n)) {
+ assert((r == NULL) || (r->parent == NULL));
+ return NULL;
+ } else {
+ assert(r->right == n);
+ return r;
+ }
+ } else {
+ r = n->left;
+ while (r->right != NULL)
+ r = r->right;
+ }
+
+ return r;
} /* c_avl_node_t *c_avl_node_prev */
-static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
-{
- assert ((t != NULL) && (n != NULL));
-
- if ((n->left != NULL) && (n->right != NULL))
- {
- c_avl_node_t *r; /* replacement node */
- if (BALANCE (n) > 0) /* left subtree is higher */
- {
- assert (n->left != NULL);
- r = c_avl_node_prev (n);
-
- }
- else /* right subtree is higher */
- {
- assert (n->right != NULL);
- r = c_avl_node_next (n);
- }
-
- assert ((r->left == NULL) || (r->right == NULL));
-
- /* copy content */
- n->key = r->key;
- n->value = r->value;
-
- n = r;
- }
-
- assert ((n->left == NULL) || (n->right == NULL));
-
- if ((n->left == NULL) && (n->right == NULL))
- {
- /* Deleting a leave is easy */
- if (n->parent == NULL)
- {
- assert (t->root == n);
- t->root = NULL;
- }
- else
- {
- assert ((n->parent->left == n)
- || (n->parent->right == n));
- if (n->parent->left == n)
- n->parent->left = NULL;
- else
- n->parent->right = NULL;
-
- rebalance (t, n->parent);
- }
-
- free_node (n);
- }
- else if (n->left == NULL)
- {
- assert (BALANCE (n) == -1);
- assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
- if (n->parent == NULL)
- {
- assert (t->root == n);
- t->root = n->right;
- }
- else if (n->parent->left == n)
- {
- n->parent->left = n->right;
- }
- else
- {
- n->parent->right = n->right;
- }
- n->right->parent = n->parent;
-
- if (n->parent != NULL)
- rebalance (t, n->parent);
-
- n->right = NULL;
- free_node (n);
- }
- else if (n->right == NULL)
- {
- assert (BALANCE (n) == 1);
- assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
- if (n->parent == NULL)
- {
- assert (t->root == n);
- t->root = n->left;
- }
- else if (n->parent->left == n)
- {
- n->parent->left = n->left;
- }
- else
- {
- n->parent->right = n->left;
- }
- n->left->parent = n->parent;
-
- if (n->parent != NULL)
- rebalance (t, n->parent);
-
- n->left = NULL;
- free_node (n);
- }
- else
- {
- assert (0);
- }
-
- return (0);
+static int _remove(c_avl_tree_t *t, c_avl_node_t *n) {
+ assert((t != NULL) && (n != NULL));
+
+ if ((n->left != NULL) && (n->right != NULL)) {
+ c_avl_node_t *r; /* replacement node */
+ if (BALANCE(n) > 0) /* left subtree is higher */
+ {
+ assert(n->left != NULL);
+ r = c_avl_node_prev(n);
+
+ } else /* right subtree is higher */
+ {
+ assert(n->right != NULL);
+ r = c_avl_node_next(n);
+ }
+
+ assert((r->left == NULL) || (r->right == NULL));
+
+ /* copy content */
+ n->key = r->key;
+ n->value = r->value;
+
+ n = r;
+ }
+
+ assert((n->left == NULL) || (n->right == NULL));
+
+ if ((n->left == NULL) && (n->right == NULL)) {
+ /* Deleting a leave is easy */
+ if (n->parent == NULL) {
+ assert(t->root == n);
+ t->root = NULL;
+ } else {
+ assert((n->parent->left == n) || (n->parent->right == n));
+ if (n->parent->left == n)
+ n->parent->left = NULL;
+ else
+ n->parent->right = NULL;
+
+ rebalance(t, n->parent);
+ }
+
+ free_node(n);
+ } else if (n->left == NULL) {
+ assert(BALANCE(n) == -1);
+ assert((n->parent == NULL) || (n->parent->left == n) ||
+ (n->parent->right == n));
+ if (n->parent == NULL) {
+ assert(t->root == n);
+ t->root = n->right;
+ } else if (n->parent->left == n) {
+ n->parent->left = n->right;
+ } else {
+ n->parent->right = n->right;
+ }
+ n->right->parent = n->parent;
+
+ if (n->parent != NULL)
+ rebalance(t, n->parent);
+
+ n->right = NULL;
+ free_node(n);
+ } else if (n->right == NULL) {
+ assert(BALANCE(n) == 1);
+ assert((n->parent == NULL) || (n->parent->left == n) ||
+ (n->parent->right == n));
+ if (n->parent == NULL) {
+ assert(t->root == n);
+ t->root = n->left;
+ } else if (n->parent->left == n) {
+ n->parent->left = n->left;
+ } else {
+ n->parent->right = n->left;
+ }
+ n->left->parent = n->parent;
+
+ if (n->parent != NULL)
+ rebalance(t, n->parent);
+
+ n->left = NULL;
+ free_node(n);
+ } else {
+ assert(0);
+ }
+
+ return 0;
} /* void *_remove */
/*
* public functions
*/
-c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
-{
- c_avl_tree_t *t;
+c_avl_tree_t *c_avl_create(int (*compare)(const void *, const void *)) {
+ c_avl_tree_t *t;
- if (compare == NULL)
- return (NULL);
+ if (compare == NULL)
+ return NULL;
- if ((t = malloc (sizeof (*t))) == NULL)
- return (NULL);
+ if ((t = malloc(sizeof(*t))) == NULL)
+ return NULL;
- t->root = NULL;
- t->compare = compare;
- t->size = 0;
+ t->root = NULL;
+ t->compare = compare;
+ t->size = 0;
- return (t);
+ return t;
}
-void c_avl_destroy (c_avl_tree_t *t)
-{
- if (t == NULL)
- return;
- free_node (t->root);
- free (t);
+void c_avl_destroy(c_avl_tree_t *t) {
+ if (t == NULL)
+ return;
+ free_node(t->root);
+ free(t);
}
-int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
-{
- c_avl_node_t *new;
- c_avl_node_t *nptr;
- int cmp;
-
- if ((new = malloc (sizeof (*new))) == NULL)
- return (-1);
-
- new->key = key;
- new->value = value;
- new->height = 1;
- new->left = NULL;
- new->right = NULL;
-
- if (t->root == NULL)
- {
- new->parent = NULL;
- t->root = new;
- t->size = 1;
- return (0);
- }
-
- nptr = t->root;
- while (42)
- {
- cmp = t->compare (nptr->key, new->key);
- if (cmp == 0)
- {
- free_node (new);
- return (1);
- }
- else if (cmp < 0)
- {
- /* nptr < new */
- if (nptr->right == NULL)
- {
- nptr->right = new;
- new->parent = nptr;
- rebalance (t, nptr);
- break;
- }
- else
- {
- nptr = nptr->right;
- }
- }
- else /* if (cmp > 0) */
- {
- /* nptr > new */
- if (nptr->left == NULL)
- {
- nptr->left = new;
- new->parent = nptr;
- rebalance (t, nptr);
- break;
- }
- else
- {
- nptr = nptr->left;
- }
- }
- } /* while (42) */
-
- verify_tree (t->root);
- ++t->size;
- return (0);
+int c_avl_insert(c_avl_tree_t *t, void *key, void *value) {
+ c_avl_node_t *new;
+ c_avl_node_t *nptr;
+ int cmp;
+
+ if ((new = malloc(sizeof(*new))) == NULL)
+ return -1;
+
+ new->key = key;
+ new->value = value;
+ new->height = 1;
+ new->left = NULL;
+ new->right = NULL;
+
+ if (t->root == NULL) {
+ new->parent = NULL;
+ t->root = new;
+ t->size = 1;
+ return 0;
+ }
+
+ nptr = t->root;
+ while (42) {
+ cmp = t->compare(nptr->key, new->key);
+ if (cmp == 0) {
+ free_node(new);
+ return 1;
+ } else if (cmp < 0) {
+ /* nptr < new */
+ if (nptr->right == NULL) {
+ nptr->right = new;
+ new->parent = nptr;
+ rebalance(t, nptr);
+ break;
+ } else {
+ nptr = nptr->right;
+ }
+ } else /* if (cmp > 0) */
+ {
+ /* nptr > new */
+ if (nptr->left == NULL) {
+ nptr->left = new;
+ new->parent = nptr;
+ rebalance(t, nptr);
+ break;
+ } else {
+ nptr = nptr->left;
+ }
+ }
+ } /* while (42) */
+
+ verify_tree(t->root);
+ ++t->size;
+ return 0;
} /* int c_avl_insert */
-int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
-{
- c_avl_node_t *n;
- int status;
+int c_avl_remove(c_avl_tree_t *t, const void *key, void **rkey, void **rvalue) {
+ c_avl_node_t *n;
+ int status;
- assert (t != NULL);
+ assert(t != NULL);
- n = search (t, key);
- if (n == NULL)
- return (-1);
+ n = search(t, key);
+ if (n == NULL)
+ return -1;
- if (rkey != NULL)
- *rkey = n->key;
- if (rvalue != NULL)
- *rvalue = n->value;
+ if (rkey != NULL)
+ *rkey = n->key;
+ if (rvalue != NULL)
+ *rvalue = n->value;
- status = _remove (t, n);
- verify_tree (t->root);
- --t->size;
- return (status);
+ status = _remove(t, n);
+ verify_tree(t->root);
+ --t->size;
+ return status;
} /* void *c_avl_remove */
-int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
-{
- c_avl_node_t *n;
+int c_avl_get(c_avl_tree_t *t, const void *key, void **value) {
+ c_avl_node_t *n;
- assert (t != NULL);
+ assert(t != NULL);
- n = search (t, key);
- if (n == NULL)
- return (-1);
+ n = search(t, key);
+ if (n == NULL)
+ return -1;
- if (value != NULL)
- *value = n->value;
+ if (value != NULL)
+ *value = n->value;
- return (0);
+ return 0;
}
-int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
-{
- c_avl_node_t *n;
- c_avl_node_t *p;
-
- if ((key == NULL) || (value == NULL))
- return (-1);
- if (t->root == NULL)
- return (-1);
-
- n = t->root;
- while ((n->left != NULL) || (n->right != NULL))
- {
- if (n->left == NULL)
- {
- n = n->right;
- continue;
- }
- else if (n->right == NULL)
- {
- n = n->left;
- continue;
- }
-
- if (n->left->height > n->right->height)
- n = n->left;
- else
- n = n->right;
- }
-
- p = n->parent;
- if (p == NULL)
- t->root = NULL;
- else if (p->left == n)
- p->left = NULL;
- else
- p->right = NULL;
-
- *key = n->key;
- *value = n->value;
-
- free_node (n);
- --t->size;
- rebalance (t, p);
-
- return (0);
+int c_avl_pick(c_avl_tree_t *t, void **key, void **value) {
+ c_avl_node_t *n;
+ c_avl_node_t *p;
+
+ assert(t != NULL);
+
+ if ((key == NULL) || (value == NULL))
+ return -1;
+ if (t->root == NULL)
+ return -1;
+
+ n = t->root;
+ while ((n->left != NULL) || (n->right != NULL)) {
+ if (n->left == NULL) {
+ n = n->right;
+ continue;
+ } else if (n->right == NULL) {
+ n = n->left;
+ continue;
+ }
+
+ if (n->left->height > n->right->height)
+ n = n->left;
+ else
+ n = n->right;
+ }
+
+ p = n->parent;
+ if (p == NULL)
+ t->root = NULL;
+ else if (p->left == n)
+ p->left = NULL;
+ else
+ p->right = NULL;
+
+ *key = n->key;
+ *value = n->value;
+
+ free_node(n);
+ --t->size;
+ rebalance(t, p);
+
+ return 0;
} /* int c_avl_pick */
-c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
-{
- c_avl_iterator_t *iter;
+c_avl_iterator_t *c_avl_get_iterator(c_avl_tree_t *t) {
+ c_avl_iterator_t *iter;
- if (t == NULL)
- return (NULL);
+ if (t == NULL)
+ return NULL;
- iter = calloc (1, sizeof (*iter));
- if (iter == NULL)
- return (NULL);
- iter->tree = t;
+ iter = calloc(1, sizeof(*iter));
+ if (iter == NULL)
+ return NULL;
+ iter->tree = t;
- return (iter);
+ return iter;
} /* c_avl_iterator_t *c_avl_get_iterator */
-int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
-{
- c_avl_node_t *n;
-
- if ((iter == NULL) || (key == NULL) || (value == NULL))
- return (-1);
-
- if (iter->node == NULL)
- {
- for (n = iter->tree->root; n != NULL; n = n->left)
- if (n->left == NULL)
- break;
- iter->node = n;
- }
- else
- {
- n = c_avl_node_next (iter->node);
- }
+int c_avl_iterator_next(c_avl_iterator_t *iter, void **key, void **value) {
+ c_avl_node_t *n;
- if (n == NULL)
- return (-1);
+ if ((iter == NULL) || (key == NULL) || (value == NULL))
+ return -1;
+
+ if (iter->node == NULL) {
+ for (n = iter->tree->root; n != NULL; n = n->left)
+ if (n->left == NULL)
+ break;
+ iter->node = n;
+ } else {
+ n = c_avl_node_next(iter->node);
+ }
+
+ if (n == NULL)
+ return -1;
- iter->node = n;
- *key = n->key;
- *value = n->value;
+ iter->node = n;
+ *key = n->key;
+ *value = n->value;
- return (0);
+ return 0;
} /* int c_avl_iterator_next */
-int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
-{
- c_avl_node_t *n;
-
- if ((iter == NULL) || (key == NULL) || (value == NULL))
- return (-1);
-
- if (iter->node == NULL)
- {
- for (n = iter->tree->root; n != NULL; n = n->left)
- if (n->right == NULL)
- break;
- iter->node = n;
- }
- else
- {
- n = c_avl_node_prev (iter->node);
- }
+int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value) {
+ c_avl_node_t *n;
- if (n == NULL)
- return (-1);
+ if ((iter == NULL) || (key == NULL) || (value == NULL))
+ return -1;
+
+ if (iter->node == NULL) {
+ for (n = iter->tree->root; n != NULL; n = n->left)
+ if (n->right == NULL)
+ break;
+ iter->node = n;
+ } else {
+ n = c_avl_node_prev(iter->node);
+ }
+
+ if (n == NULL)
+ return -1;
- iter->node = n;
- *key = n->key;
- *value = n->value;
+ iter->node = n;
+ *key = n->key;
+ *value = n->value;
- return (0);
+ return 0;
} /* int c_avl_iterator_prev */
-void c_avl_iterator_destroy (c_avl_iterator_t *iter)
-{
- free (iter);
-}
+void c_avl_iterator_destroy(c_avl_iterator_t *iter) { free(iter); }
-int c_avl_size (c_avl_tree_t *t)
-{
- if (t == NULL)
- return (0);
- return (t->size);
+int c_avl_size(c_avl_tree_t *t) {
+ if (t == NULL)
+ return 0;
+ return t->size;
}
projects / collectd.git / blobdiff