From e00f829437e24dfc52f2aeeced75fd36467da7a2 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Thu, 15 Feb 2007 09:47:37 +0100 Subject: [PATCH] src/utils_avltree.[ch]: Documented the interface of the AVL-tree. The iterator-code has been disabled, because it's not very practical and `utils_llist' should be used if order matters. `avl_node_{next,prev}' have been made `static', because they're not exported. --- src/utils_avltree.c | 44 +++++++++++------- src/utils_avltree.h | 130 +++++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 151 insertions(+), 23 deletions(-) diff --git a/src/utils_avltree.c b/src/utils_avltree.c index 830b711f..b107b03d 100644 --- a/src/utils_avltree.c +++ b/src/utils_avltree.c @@ -260,6 +260,8 @@ static void rebalance (avl_tree_t *t, avl_node_t *n) } /* while (n != NULL) */ } /* void rebalance */ +#if 0 +/* This code disabled until a need arises. */ static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n) { avl_iterator_t *iter; @@ -273,8 +275,9 @@ static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n) return (iter); } +#endif -void *avl_node_next (avl_tree_t *t, avl_node_t *n) +static void *avl_node_next (avl_tree_t *t, avl_node_t *n) { avl_node_t *r; /* return node */ @@ -304,7 +307,7 @@ void *avl_node_next (avl_tree_t *t, avl_node_t *n) return (r); } -void *avl_node_prev (avl_tree_t *t, avl_node_t *n) +static void *avl_node_prev (avl_tree_t *t, avl_node_t *n) { avl_node_t *r; /* return node */ @@ -451,6 +454,9 @@ avl_tree_t *avl_create (int (*compare) (const void *, const void *)) { avl_tree_t *t; + if (compare == NULL) + return (NULL); + if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL) return (NULL); @@ -569,26 +575,13 @@ int avl_get (avl_tree_t *t, const void *key, void **value) return (0); } -avl_iterator_t *avl_get_iterator (avl_tree_t *t) -{ - avl_node_t *n; - - if (t == NULL) - return (NULL); - - for (n = t->root; n != NULL; n = n->left) - if (n->left == NULL) - break; - - return (avl_create_iterator (t, n)); -} /* avl_iterator_t *avl_get_iterator */ - int avl_pick (avl_tree_t *t, void **key, void **value) { avl_node_t *n; avl_node_t *p; - assert ((key != NULL) && (value != NULL)); + if ((key == NULL) || (value == NULL)) + return (-1); if (t->root == NULL) return (-1); @@ -621,6 +614,22 @@ int avl_pick (avl_tree_t *t, void **key, void **value) return (0); } /* int avl_pick */ +#if 0 +/* This code disabled until a need arises. */ +avl_iterator_t *avl_get_iterator (avl_tree_t *t) +{ + avl_node_t *n; + + if (t == NULL) + return (NULL); + + for (n = t->root; n != NULL; n = n->left) + if (n->left == NULL) + break; + + return (avl_create_iterator (t, n)); +} /* avl_iterator_t *avl_get_iterator */ + void *avl_iterator_next (avl_iterator_t *iter) { avl_node_t *n; @@ -659,3 +668,4 @@ void avl_iterator_destroy (avl_iterator_t *iter) { free (iter); } +#endif /* 0 */ diff --git a/src/utils_avltree.h b/src/utils_avltree.h index 7875e0b2..37af5e48 100644 --- a/src/utils_avltree.h +++ b/src/utils_avltree.h @@ -1,3 +1,25 @@ +/** + * collectd - src/utils_avltree.h + * 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. + * + * 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. + * + * 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 + * + * Authors: + * Florian octo Forster + **/ + #ifndef UTILS_AVLTREE_H #define UTILS_AVLTREE_H 1 @@ -7,23 +29,119 @@ typedef struct avl_tree_s avl_tree_t; struct avl_iterator_s; typedef struct avl_iterator_s avl_iterator_t; -struct avl_keyval_s -{ - void *key; - void *value; -}; - +/* + * NAME + * avl_create + * + * DESCRIPTION + * Allocates a new AVL-tree. + * + * PARAMETERS + * `compare' The function-pointer `compare' is used to compare two keys. It + * has to return less than zero if it's first argument is smaller + * then the second argument, more than zero if the first argument + * is bigger than the second argument and zero if they are equal. + * If your keys are char-pointers, you can use the `strcmp' + * function from the libc here. + * + * RETURN VALUE + * A avl_tree_t-pointer upon success or NULL upon failure. + */ avl_tree_t *avl_create (int (*compare) (const void *, const void *)); + + +/* + * NAME + * avl_destroy + * + * DESCRIPTION + * Deallocates an AVL-tree. Stored value- and key-pointer are lost, but of + * course not freed. + */ void avl_destroy (avl_tree_t *t); +/* + * NAME + * avl_insert + * + * DESCRIPTION + * Stores the key-value-pair in the AVL-tree pointed to by `t'. + * + * PARAMETERS + * `t' AVL-tree to store the data in. + * `key' Key used to store the value under. This is used to get back to + * the value again. + * `value' Value to be stored. + * + * RETURN VALUE + * Zero upon success and non-zero upon failure and if the key is already + * stored in the tree. + */ int avl_insert (avl_tree_t *t, void *key, void *value); + +/* + * NAME + * avl_remove + * + * DESCRIPTION + * Removes a key-value-pair from the tree t. The stored key and value may be + * returned in `rkey' and `rvalue'. + * + * PARAMETERS + * `t' AVL-tree to remove key-value-pair from. + * `key' Key to identify the entry. + * `rkey' Pointer to a pointer in which to store the key. May be NULL. + * `rvalue' Pointer to a pointer in which to store the value. May be NULL. + * + * RETURN VALUE + * Zero upon success or non-zero if the key isn't found in the tree. + */ int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue); +/* + * NAME + * avl_get + * + * DESCRIPTION + * Retrieve the `value' belonging to `key'. + * + * PARAMETERS + * `t' AVL-tree to get the value from. + * `key' Key to identify the entry. + * `value' Pointer to a pointer in which to store the value. May be NULL. + * + * RETURN VALUE + * Zero upon success or non-zero if the key isn't found in the tree. + */ int avl_get (avl_tree_t *t, const void *key, void **value); +/* + * NAME + * avl_pick + * + * DESCRIPTION + * Remove a (pseudo-)random element from the tree and return it's `key' and + * `value'. Entries are not returned in any particular order. This function + * is intended for cache-flushes that don't care about the order but simply + * want to remove all elements, one at a time. + * + * PARAMETERS + * `t' AVL-tree to get the value from. + * `key' Pointer to a pointer in which to store the key. + * `value' Pointer to a pointer in which to store the value. + * + * RETURN VALUE + * Zero upon success or non-zero if the tree is empty or key or value is + * NULL. + */ +int avl_pick (avl_tree_t *t, void **key, void **value); + +#if 0 +/* This code disabled until a need arises. */ avl_iterator_t *avl_get_iterator (avl_tree_t *t); void *avl_iterator_next (avl_iterator_t *iter); void *avl_iterator_prev (avl_iterator_t *iter); void avl_iterator_destroy (avl_iterator_t *iter); +#endif #endif /* UTILS_AVLTREE_H */ -- 2.11.0