X-Git-Url: https://git.octo.it/?p=collectd.git;a=blobdiff_plain;f=src%2Futils_avltree.h;h=1e0f271fc187ce4e35f8bb015dbedc4bbe947448;hp=0ac6087e96ce1d721185b53cf7a66f31e52b4c60;hb=633c3966f770e4d46651a2fe219a18d8a9907a9f;hpb=f5111b586d044b932ab4454ccdfbb659c1d874d4 diff --git a/src/utils_avltree.h b/src/utils_avltree.h index 0ac6087e..1e0f271f 100644 --- a/src/utils_avltree.h +++ b/src/utils_avltree.h @@ -2,36 +2,40 @@ * 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 + * 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: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * 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 + * Florian octo Forster **/ #ifndef UTILS_AVLTREE_H #define UTILS_AVLTREE_H 1 -struct avl_tree_s; -typedef struct avl_tree_s avl_tree_t; +struct c_avl_tree_s; +typedef struct c_avl_tree_s c_avl_tree_t; -struct avl_iterator_s; -typedef struct avl_iterator_s avl_iterator_t; +struct c_avl_iterator_s; +typedef struct c_avl_iterator_s c_avl_iterator_t; /* * NAME - * avl_create + * c_avl_create * * DESCRIPTION * Allocates a new AVL-tree. @@ -45,24 +49,24 @@ typedef struct avl_iterator_s avl_iterator_t; * function from the libc here. * * RETURN VALUE - * A avl_tree_t-pointer upon success or NULL upon failure. + * A c_avl_tree_t-pointer upon success or NULL upon failure. */ -avl_tree_t *avl_create (int (*compare) (const void *, const void *)); +c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *)); /* * NAME - * avl_destroy + * c_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); +void c_avl_destroy (c_avl_tree_t *t); /* * NAME - * avl_insert + * c_avl_insert * * DESCRIPTION * Stores the key-value-pair in the AVL-tree pointed to by `t'. @@ -70,18 +74,21 @@ void avl_destroy (avl_tree_t *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. + * the value again. The pointer is stored in an internal structure + * and _not_ copied. So the memory pointed to may _not_ be freed + * before this entry is removed. You can use the `rkey' argument + * to `avl_remove' to get the original pointer back and free it. * `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. + * Zero upon success, non-zero otherwise. It's less than zero if an error + * occurred or greater than zero if the key is already stored in the tree. */ -int avl_insert (avl_tree_t *t, void *key, void *value); +int c_avl_insert (c_avl_tree_t *t, void *key, void *value); /* * NAME - * avl_remove + * c_avl_remove * * DESCRIPTION * Removes a key-value-pair from the tree t. The stored key and value may be @@ -91,16 +98,20 @@ int avl_insert (avl_tree_t *t, void *key, void *value); * `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. + * Since the `key' pointer is not copied when creating an entry, + * the pointer may not be available anymore from outside the tree. + * You can use this argument to get the actual pointer back and + * free the memory pointed to by it. * `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, const void *key, void **rkey, void **rvalue); +int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue); /* * NAME - * avl_get + * c_avl_get * * DESCRIPTION * Retrieve the `value' belonging to `key'. @@ -113,11 +124,11 @@ int avl_remove (avl_tree_t *t, const void *key, void **rkey, void **rvalue); * 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); +int c_avl_get (c_avl_tree_t *t, const void *key, void **value); /* * NAME - * avl_pick + * c_avl_pick * * DESCRIPTION * Remove a (pseudo-)random element from the tree and return it's `key' and @@ -134,11 +145,26 @@ int avl_get (avl_tree_t *t, const void *key, void **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); +int c_avl_pick (c_avl_tree_t *t, void **key, void **value); + +c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t); +int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value); +int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value); +void c_avl_iterator_destroy (c_avl_iterator_t *iter); -avl_iterator_t *avl_get_iterator (avl_tree_t *t); -int avl_iterator_next (avl_iterator_t *iter, void **key, void **value); -int avl_iterator_prev (avl_iterator_t *iter, void **key, void **value); -void avl_iterator_destroy (avl_iterator_t *iter); +/* + * NAME + * c_avl_size + * + * DESCRIPTION + * Return the size (number of nodes) of the specified tree. + * + * PARAMETERS + * `t' AVL-tree to get the size of. + * + * RETURN VALUE + * Number of nodes in the tree, 0 if the tree is empty or NULL. + */ +int c_avl_size (c_avl_tree_t *t); #endif /* UTILS_AVLTREE_H */