X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=lib%2Favl_tree.c;h=fc3c27e7b039b52eeb27aad62bb0b3feb1dbd60a;hp=009c680b29f27ad16e922999410c40cc7a81647b;hb=085d33e6265e139bb08cdfda3d7498993190d187;hpb=9f38e394636a177c00a4545de2a99c661de36386 diff --git a/lib/avl_tree.c b/lib/avl_tree.c index 009c680b..fc3c27e7 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-2003 Ivo Timmermans , + 2000-2003 Guus Sliepen + 2000-2003 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 @@ -29,7 +29,7 @@ library for inclusion into tinc (http://tinc.nl.linux.org/) by Guus Sliepen . - $Id: avl_tree.c,v 1.1.2.10 2002/09/09 21:49:16 guus Exp $ + $Id: avl_tree.c,v 1.1.2.15 2003/07/12 17:48:38 guus Exp $ */ #include @@ -53,7 +53,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 +91,7 @@ int lg(unsigned int u) /* Internal helper functions */ -int avl_check_balance(avl_node_t * node) +static int avl_check_balance(avl_node_t *node) { #ifdef AVL_DEPTH int d; @@ -117,7 +119,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; @@ -272,7 +274,7 @@ 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); } @@ -282,7 +284,7 @@ avl_node_t *avl_alloc_node(void) return (avl_node_t *)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); @@ -292,7 +294,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; @@ -301,7 +303,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; @@ -310,7 +312,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; @@ -319,7 +321,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; @@ -328,7 +330,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; @@ -338,7 +340,7 @@ avl_node_t *avl_search_node(const avl_tree_t * tree, const void *data) return result ? NULL : node; } -avl_node_t *avl_search_closest_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) { avl_node_t *node; @@ -381,7 +383,7 @@ avl_node_t *avl_search_closest_node(const avl_tree_t * tree, const void *data, return node; } -avl_node_t *avl_search_closest_smaller_node(const avl_tree_t * tree, +avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree, const void *data) { avl_node_t *node; @@ -395,7 +397,7 @@ avl_node_t *avl_search_closest_smaller_node(const avl_tree_t * tree, return node; } -avl_node_t *avl_search_closest_greater_node(const avl_tree_t * tree, +avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, const void *data) { avl_node_t *node; @@ -411,7 +413,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; @@ -451,7 +453,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; @@ -485,24 +487,31 @@ 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) +void avl_insert_before(avl_tree_t *tree, avl_node_t *before, + avl_node_t *node) { - if(!before) - return tree->tail ? avl_insert_after(tree, tree->tail, node) : avl_insert_top(tree, node); + if(!before) { + if(tree->tail) + avl_insert_after(tree, tree->tail, node); + else + avl_insert_top(tree, node); + return; + } node->next = before; node->parent = before; node->prev = before->prev; - if(before->left) - return avl_insert_after(tree, before->prev, node); + if(before->left) { + avl_insert_after(tree, before->prev, node); + return; + } if(before->prev) before->prev->next = node; @@ -512,18 +521,23 @@ void avl_insert_before(avl_tree_t * tree, avl_node_t * before, before->prev = node; before->left = node; - avl_rebalance(tree, before->parent); + 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) - return tree->head ? avl_insert_before(tree, tree->head, - node) : avl_insert_top(tree, - node); + if(!after) { + if(tree->head) + avl_insert_before(tree, tree->head, node); + else + avl_insert_top(tree, node); + return; + } - if(after->right) - return avl_insert_before(tree, after->next, node); + if(after->right) { + avl_insert_before(tree, after->next, node); + return; + } node->prev = after; node->parent = after; @@ -537,10 +551,10 @@ void avl_insert_after(avl_tree_t * tree, avl_node_t * after, avl_node_t * node) after->next = node; after->right = node; - avl_rebalance(tree, after->parent); + 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; @@ -552,7 +566,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; @@ -621,13 +635,13 @@ 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; @@ -639,7 +653,7 @@ 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; @@ -653,7 +667,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(avl_tree_t *tree, avl_action_t action) { avl_node_t *node, *next; @@ -663,7 +677,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(avl_tree_t *tree, avl_action_t action) { avl_node_t *node, *next; @@ -676,12 +690,12 @@ 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(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; @@ -704,7 +718,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; @@ -721,7 +735,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(avl_tree_t *tree) { return AVL_NODE_DEPTH(tree->root); }