X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=lib%2Favl_tree.c;h=a8bf5d5f733c99863c31cdcd9e19bdf86a0c8fca;hp=7bacc20e111053e97ac238841ad77450b5f36080;hb=16e6769feef21a5bf58f6022d990452987bb5efb;hpb=cf63cbef2bcb6a1f21ded439cbb09842581b9020 diff --git a/lib/avl_tree.c b/lib/avl_tree.c index 7bacc20e..a8bf5d5f 100644 --- a/lib/avl_tree.c +++ b/lib/avl_tree.c @@ -1,9 +1,9 @@ /* avl_tree.c -- avl_ tree and linked list convenience Copyright (C) 1998 Michael H. Buselli - 2000,2001 Ivo Timmermans , - 2000,2001 Guus Sliepen - 2000,2001 Wessel Dankers + 2000-2005 Ivo Timmermans, + 2000-2006 Guus Sliepen + 2000-2005 Wessel Dankers 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 @@ -15,28 +15,25 @@ 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., 675 Mass Ave, Cambridge, MA 02139, USA. + 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 Street, Fifth Floor, Boston, MA 02110-1301 USA. Original AVL tree library by Michael H. Buselli . - Modified 2000-11-28 by Wessel Dankers to use counts + Modified 2000-11-28 by Wessel Dankers to use counts instead of depths, to add the ->next and ->prev and to generally obfuscate the code. Mail me if you found a bug. Cleaned up and incorporated some of the ideas from the red-black tree - library for inclusion into tinc (http://tinc.nl.linux.org/) by - Guus Sliepen . - - $Id: avl_tree.c,v 1.1.2.13 2003/06/11 19:39:02 guus Exp $ + library for inclusion into tinc (http://www.tinc-vpn.org/) by + Guus Sliepen . */ -#include -#include -#include +#include "system.h" #include "avl_tree.h" +#include "xalloc.h" #ifdef AVL_COUNT #define AVL_NODE_COUNT(n) ((n) ? (n)->count : 0) @@ -53,7 +50,9 @@ #endif #ifndef AVL_DEPTH -int lg(unsigned int u) +static int lg(unsigned int u) __attribute__ ((__const__)); + +static int lg(unsigned int u) { int r = 1; @@ -89,7 +88,7 @@ int lg(unsigned int u) /* Internal helper functions */ -int avl_check_balance(avl_node_t *node) +static int avl_check_balance(const avl_node_t *node) { #ifdef AVL_DEPTH int d; @@ -117,7 +116,7 @@ int avl_check_balance(avl_node_t *node) #endif } -void avl_rebalance(avl_tree_t *tree, avl_node_t *node) +static void avl_rebalance(avl_tree_t *tree, avl_node_t *node) { avl_node_t *child; avl_node_t *gchild; @@ -279,7 +278,7 @@ void avl_free_tree(avl_tree_t *tree) avl_node_t *avl_alloc_node(void) { - return (avl_node_t *)xmalloc_and_zero(sizeof(avl_node_t)); + return xmalloc_and_zero(sizeof(avl_node_t)); } void avl_free_node(avl_tree_t *tree, avl_node_t *node) @@ -655,7 +654,7 @@ void avl_delete_tree(avl_tree_t *tree) { avl_node_t *node, *next; - for(node = tree->root; node; node = next) { + for(node = tree->head; node; node = next) { next = node->next; avl_free_node(tree, node); } @@ -665,7 +664,7 @@ void avl_delete_tree(avl_tree_t *tree) /* Tree walking */ -void avl_foreach(avl_tree_t *tree, avl_action_t action) +void avl_foreach(const avl_tree_t *tree, avl_action_t action) { avl_node_t *node, *next; @@ -675,7 +674,7 @@ void avl_foreach(avl_tree_t *tree, avl_action_t action) } } -void avl_foreach_node(avl_tree_t *tree, avl_action_t action) +void avl_foreach_node(const avl_tree_t *tree, avl_action_t action) { avl_node_t *node, *next; @@ -688,7 +687,7 @@ void avl_foreach_node(avl_tree_t *tree, avl_action_t action) /* Indexing */ #ifdef AVL_COUNT -unsigned int avl_count(avl_tree_t *tree) +unsigned int avl_count(const avl_tree_t *tree) { return AVL_NODE_COUNT(tree->root); } @@ -733,7 +732,7 @@ unsigned int avl_index(const avl_node_t *node) } #endif #ifdef AVL_DEPTH -unsigned int avl_depth(avl_tree_t *tree) +unsigned int avl_depth(const avl_tree_t *tree) { return AVL_NODE_DEPTH(tree->root); }