X-Git-Url: https://git.octo.it/?p=collectd.git;a=blobdiff_plain;f=src%2Fdaemon%2Futils_avltree.c;h=87568fb243ffbed70e390f9a45dd402a41a03052;hp=e1c41ecf8fb95c122c9fb2a20c6746a5271e8e5d;hb=1159cb5d383c55a80a0db100b8f7aadcf44740a5;hpb=23faf977688c7123d624b2911e69e2c9f4d0f78c

diff --git a/src/daemon/utils_avltree.c b/src/daemon/utils_avltree.c
index e1c41ecf..87568fb2 100644
--- a/src/daemon/utils_avltree.c
+++ b/src/daemon/utils_avltree.c
@@ -24,40 +24,38 @@
  *   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;
 };
 
 /*
@@ -76,56 +74,50 @@ static void verify_tree (c_avl_node_t *n)
 	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)
@@ -136,39 +128,38 @@ static c_avl_node_t *search (c_avl_tree_t *t, const void *key)
  *  / 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 */
 
 /*
@@ -180,561 +171,478 @@ static c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
  *     /_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;
 }