* collectd - src/utils_avltree.c
* Copyright (C) 2006,2007 Florian octo Forster
*
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version.
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
*
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
*
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write to the Free Software Foundation, Inc.,
- * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
*
* Authors:
- * Florian octo Forster <octo at verplant.org>
+ * Florian octo Forster <octo at collectd.org>
**/
#include "config.h"
/*
* private data types
*/
-struct avl_node_s
+struct c_avl_node_s
{
void *key;
void *value;
int height;
- struct avl_node_s *left;
- struct avl_node_s *right;
- struct avl_node_s *parent;
+ struct c_avl_node_s *left;
+ struct c_avl_node_s *right;
+ struct c_avl_node_s *parent;
};
-typedef struct avl_node_s avl_node_t;
+typedef struct c_avl_node_s c_avl_node_t;
-struct avl_tree_s
+struct c_avl_tree_s
{
- avl_node_t *root;
+ c_avl_node_t *root;
int (*compare) (const void *, const void *);
+ int size;
};
-struct avl_iterator_s
+struct c_avl_iterator_s
{
- avl_tree_t *tree;
- avl_node_t *node;
+ c_avl_tree_t *tree;
+ c_avl_node_t *node;
};
/*
* private functions
*/
#if 0
-static void verify_tree (avl_node_t *n)
+static void verify_tree (c_avl_node_t *n)
{
if (n == NULL)
return;
# define verify_tree(n) /**/
#endif
-static void free_node (avl_node_t *n)
+static void free_node (c_avl_node_t *n)
{
if (n == NULL)
return;
free (n);
}
-static int calc_height (avl_node_t *n)
+static int calc_height (c_avl_node_t *n)
{
int height_left;
int height_right;
: height_right) + 1);
} /* int calc_height */
-static avl_node_t *search (avl_tree_t *t, const void *key)
+static c_avl_node_t *search (c_avl_tree_t *t, const void *key)
{
- avl_node_t *n;
+ c_avl_node_t *n;
int cmp;
n = t->root;
* / a\ /_b\ /_b\ /_c\
* /____\
*/
-static avl_node_t *rotate_right (avl_tree_t *t, avl_node_t *x)
+static c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
{
- avl_node_t *p;
- avl_node_t *y;
- avl_node_t *b;
+ c_avl_node_t *p;
+ c_avl_node_t *y;
+ c_avl_node_t *b;
p = x->parent;
y = x->left;
* /_b\ / c\ /_a\ /_b\
* /____\
*/
-static avl_node_t *rotate_left (avl_tree_t *t, avl_node_t *x)
+static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
{
- avl_node_t *p;
- avl_node_t *y;
- avl_node_t *b;
+ c_avl_node_t *p;
+ c_avl_node_t *y;
+ c_avl_node_t *b;
p = x->parent;
y = x->right;
return (y);
} /* void rotate_left */
-static avl_node_t *rotate_left_right (avl_tree_t *t, avl_node_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 avl_node_t *rotate_right_left (avl_tree_t *t, avl_node_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 (avl_tree_t *t, avl_node_t *n)
+static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
{
int b_top;
int b_bottom;
} /* while (n != NULL) */
} /* void rebalance */
-static avl_node_t *avl_node_next (avl_tree_t *t, avl_node_t *n)
+static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
{
- avl_node_t *r; /* return node */
+ c_avl_node_t *r; /* return node */
if (n == NULL)
{
}
return (r);
-} /* avl_node_t *avl_node_next */
+} /* c_avl_node_t *c_avl_node_next */
-static avl_node_t *avl_node_prev (avl_tree_t *t, avl_node_t *n)
+static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
{
- avl_node_t *r; /* return node */
+ c_avl_node_t *r; /* return node */
if (n == NULL)
{
}
return (r);
-} /* avl_node_t *avl_node_prev */
+} /* c_avl_node_t *c_avl_node_prev */
-static int _remove (avl_tree_t *t, avl_node_t *n)
+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))
{
- avl_node_t *r; /* replacement node */
+ c_avl_node_t *r; /* replacement node */
if (BALANCE (n) > 0) /* left subtree is higher */
{
assert (n->left != NULL);
- r = avl_node_prev (t, n);
+ r = c_avl_node_prev (n);
}
else /* right subtree is higher */
{
assert (n->right != NULL);
- r = avl_node_next (t, n);
+ r = c_avl_node_next (n);
}
assert ((r->left == NULL) || (r->right == NULL));
/*
* public functions
*/
-avl_tree_t *avl_create (int (*compare) (const void *, const void *))
+c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
{
- avl_tree_t *t;
+ c_avl_tree_t *t;
if (compare == NULL)
return (NULL);
- if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
+ if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
return (NULL);
t->root = NULL;
t->compare = compare;
+ t->size = 0;
return (t);
}
-void avl_destroy (avl_tree_t *t)
+void c_avl_destroy (c_avl_tree_t *t)
{
+ if (t == NULL)
+ return;
free_node (t->root);
free (t);
}
-int avl_insert (avl_tree_t *t, void *key, void *value)
+int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
{
- avl_node_t *new;
- avl_node_t *nptr;
+ c_avl_node_t *new;
+ c_avl_node_t *nptr;
int cmp;
- if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
+ if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
return (-1);
new->key = key;
{
new->parent = NULL;
t->root = new;
+ t->size = 1;
return (0);
}
if (cmp == 0)
{
free_node (new);
- return (-1);
+ return (1);
}
else if (cmp < 0)
{
} /* while (42) */
verify_tree (t->root);
+ ++t->size;
return (0);
-} /* int avl_insert */
+} /* int c_avl_insert */
-int avl_remove (avl_tree_t *t, const void *key, void **rkey, void **rvalue)
+int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
{
- avl_node_t *n;
+ c_avl_node_t *n;
int status;
assert (t != NULL);
status = _remove (t, n);
verify_tree (t->root);
+ --t->size;
return (status);
-} /* void *avl_remove */
+} /* void *c_avl_remove */
-int avl_get (avl_tree_t *t, const void *key, void **value)
+int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
{
- avl_node_t *n;
+ c_avl_node_t *n;
- assert (value != NULL);
+ assert (t != NULL);
n = search (t, key);
if (n == NULL)
return (-1);
- *value = n->value;
+ if (value != NULL)
+ *value = n->value;
return (0);
}
-int avl_pick (avl_tree_t *t, void **key, void **value)
+int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
{
- avl_node_t *n;
- avl_node_t *p;
+ c_avl_node_t *n;
+ c_avl_node_t *p;
if ((key == NULL) || (value == NULL))
return (-1);
rebalance (t, p);
return (0);
-} /* int avl_pick */
+} /* int c_avl_pick */
-avl_iterator_t *avl_get_iterator (avl_tree_t *t)
+c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
{
- avl_iterator_t *iter;
+ c_avl_iterator_t *iter;
if (t == NULL)
return (NULL);
- iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
+ iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
if (iter == NULL)
return (NULL);
- memset (iter, '\0', sizeof (avl_iterator_t));
+ memset (iter, '\0', sizeof (c_avl_iterator_t));
iter->tree = t;
return (iter);
-} /* avl_iterator_t *avl_get_iterator */
+} /* c_avl_iterator_t *c_avl_get_iterator */
-int avl_iterator_next (avl_iterator_t *iter, void **key, void **value)
+int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
{
- avl_node_t *n;
+ c_avl_node_t *n;
if ((iter == NULL) || (key == NULL) || (value == NULL))
return (-1);
}
else
{
- n = avl_node_next (iter->tree, iter->node);
+ n = c_avl_node_next (iter->node);
}
if (n == NULL)
*value = n->value;
return (0);
-} /* int avl_iterator_next */
+} /* int c_avl_iterator_next */
-int avl_iterator_prev (avl_iterator_t *iter, void **key, void **value)
+int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
{
- avl_node_t *n;
+ c_avl_node_t *n;
if ((iter == NULL) || (key == NULL) || (value == NULL))
return (-1);
}
else
{
- n = avl_node_prev (iter->tree, iter->node);
+ n = c_avl_node_prev (iter->node);
}
if (n == NULL)
*value = n->value;
return (0);
-} /* int avl_iterator_prev */
+} /* int c_avl_iterator_prev */
-void avl_iterator_destroy (avl_iterator_t *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);
+}
projects / collectd.git / blobdiff