X-Git-Url: https://tinc-vpn.org/git/browse?a=blobdiff_plain;f=lib%2Favl_tree.c;h=dd21b80ef4b1e5ae17c0c2597be50149f59f13f7;hb=7ea85043ac1fb2096baea44f6b0af27ac0d0b2cf;hp=53d82eb413fb7d0d8f772da43bbfa2227ad69658;hpb=1401faf608e1c8af0d0754e545b0ec79d2bd5d93;p=tinc diff --git a/lib/avl_tree.c b/lib/avl_tree.c index 53d82eb4..dd21b80e 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.14 2003/07/06 23:16:27 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,10 +50,9 @@ #endif #ifndef AVL_DEPTH -static int lg(unsigned int u) __attribute__ ((const)); +static int lg(unsigned int u) __attribute__ ((__const__)); -static int lg(unsigned int u) -{ +static int lg(unsigned int u) { int r = 1; if(!u) @@ -91,8 +87,7 @@ static int lg(unsigned int u) /* Internal helper functions */ -static int avl_check_balance(avl_node_t *node) -{ +static int avl_check_balance(const avl_node_t *node) { #ifdef AVL_DEPTH int d; @@ -119,8 +114,7 @@ static int avl_check_balance(avl_node_t *node) #endif } -static 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; avl_node_t *parent; @@ -263,8 +257,7 @@ static void avl_rebalance(avl_tree_t *tree, avl_node_t *node) /* (De)constructors */ -avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete) -{ +avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete) { avl_tree_t *tree; tree = xmalloc_and_zero(sizeof(avl_tree_t)); @@ -274,18 +267,15 @@ avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete) return tree; } -void avl_free_tree(avl_tree_t *tree) -{ +void avl_free_tree(avl_tree_t *tree) { free(tree); } -avl_node_t *avl_alloc_node(void) -{ - return (avl_node_t *)xmalloc_and_zero(sizeof(avl_node_t)); +avl_node_t *avl_alloc_node(void) { + return xmalloc_and_zero(sizeof(avl_node_t)); } -void avl_free_node(avl_tree_t *tree, avl_node_t *node) -{ +void avl_free_node(avl_tree_t *tree, avl_node_t *node) { if(node->data && tree->delete) tree->delete(node->data); @@ -294,8 +284,7 @@ void avl_free_node(avl_tree_t *tree, avl_node_t *node) /* Searching */ -void *avl_search(const avl_tree_t *tree, const void *data) -{ +void *avl_search(const avl_tree_t *tree, const void *data) { avl_node_t *node; node = avl_search_node(tree, data); @@ -303,8 +292,7 @@ void *avl_search(const avl_tree_t *tree, const void *data) return node ? node->data : NULL; } -void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result) -{ +void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result) { avl_node_t *node; node = avl_search_closest_node(tree, data, result); @@ -312,8 +300,7 @@ void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result) return node ? node->data : NULL; } -void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data) -{ +void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data) { avl_node_t *node; node = avl_search_closest_smaller_node(tree, data); @@ -321,8 +308,7 @@ void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data) return node ? node->data : NULL; } -void *avl_search_closest_greater(const avl_tree_t *tree, const void *data) -{ +void *avl_search_closest_greater(const avl_tree_t *tree, const void *data) { avl_node_t *node; node = avl_search_closest_greater_node(tree, data); @@ -330,8 +316,7 @@ void *avl_search_closest_greater(const avl_tree_t *tree, const void *data) return node ? node->data : NULL; } -avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data) -{ +avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data) { avl_node_t *node; int result; @@ -341,8 +326,7 @@ avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data) } avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data, - int *result) -{ + int *result) { avl_node_t *node; int c; @@ -384,8 +368,7 @@ avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data, } avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree, - const void *data) -{ + const void *data) { avl_node_t *node; int result; @@ -398,8 +381,7 @@ avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree, } avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, - const void *data) -{ + const void *data) { avl_node_t *node; int result; @@ -413,8 +395,7 @@ avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, /* Insertion and deletion */ -avl_node_t *avl_insert(avl_tree_t *tree, void *data) -{ +avl_node_t *avl_insert(avl_tree_t *tree, void *data) { avl_node_t *closest, *new; int result; @@ -453,8 +434,7 @@ avl_node_t *avl_insert(avl_tree_t *tree, void *data) return new; } -avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) -{ +avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) { avl_node_t *closest; int result; @@ -487,15 +467,13 @@ avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) return node; } -void avl_insert_top(avl_tree_t *tree, avl_node_t *node) -{ +void avl_insert_top(avl_tree_t *tree, avl_node_t *node) { node->prev = node->next = node->parent = NULL; tree->head = tree->tail = tree->root = node; } void avl_insert_before(avl_tree_t *tree, avl_node_t *before, - avl_node_t *node) -{ + avl_node_t *node) { if(!before) { if(tree->tail) avl_insert_after(tree, tree->tail, node); @@ -524,8 +502,7 @@ void avl_insert_before(avl_tree_t *tree, avl_node_t *before, avl_rebalance(tree, before); } -void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node) -{ +void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node) { if(!after) { if(tree->head) avl_insert_before(tree, tree->head, node); @@ -554,8 +531,7 @@ void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node) avl_rebalance(tree, after); } -avl_node_t *avl_unlink(avl_tree_t *tree, void *data) -{ +avl_node_t *avl_unlink(avl_tree_t *tree, void *data) { avl_node_t *node; node = avl_search_node(tree, data); @@ -566,8 +542,7 @@ avl_node_t *avl_unlink(avl_tree_t *tree, void *data) return node; } -void avl_unlink_node(avl_tree_t *tree, avl_node_t *node) -{ +void avl_unlink_node(avl_tree_t *tree, avl_node_t *node) { avl_node_t *parent; avl_node_t **superparent; avl_node_t *subst, *left, *right; @@ -635,14 +610,12 @@ void avl_unlink_node(avl_tree_t *tree, avl_node_t *node) #endif } -void avl_delete_node(avl_tree_t *tree, avl_node_t *node) -{ +void avl_delete_node(avl_tree_t *tree, avl_node_t *node) { avl_unlink_node(tree, node); avl_free_node(tree, node); } -void avl_delete(avl_tree_t *tree, void *data) -{ +void avl_delete(avl_tree_t *tree, void *data) { avl_node_t *node; node = avl_search_node(tree, data); @@ -653,11 +626,10 @@ void avl_delete(avl_tree_t *tree, void *data) /* Fast tree cleanup */ -void avl_delete_tree(avl_tree_t *tree) -{ +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); } @@ -667,8 +639,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; for(node = tree->head; node; node = next) { @@ -677,8 +648,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; for(node = tree->head; node; node = next) { @@ -690,13 +660,11 @@ 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); } -avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index) -{ +avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index) { avl_node_t *node; unsigned int c; @@ -718,8 +686,7 @@ avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index) return NULL; } -unsigned int avl_index(const avl_node_t *node) -{ +unsigned int avl_index(const avl_node_t *node) { avl_node_t *next; unsigned int index; @@ -735,8 +702,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); } #endif