From 77509da76c61b881c9967bfb7cdafeaf6b56eb6d Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Fri, 5 Jan 2001 23:50:56 +0000 Subject: [PATCH] - AVL tree routines: faster than RBL, and also more stable. --- lib/Makefile.am | 6 +- lib/avl_tree.c | 677 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/avl_tree.h | 145 +++++++++++ 3 files changed, 825 insertions(+), 3 deletions(-) create mode 100644 lib/avl_tree.c create mode 100644 lib/avl_tree.h diff --git a/lib/Makefile.am b/lib/Makefile.am index 355493cd..f7f2798a 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -1,15 +1,15 @@ ## Process this file with automake to produce Makefile.in -# $Id: Makefile.am,v 1.2.4.5 2000/11/28 23:23:41 zarq Exp $ +# $Id: Makefile.am,v 1.2.4.6 2001/01/05 23:50:55 guus Exp $ noinst_LIBRARIES = libvpn.a INCLUDES = -I. -I$(top_builddir) -I$(top_srcdir)/intl -libvpn_a_SOURCES = xmalloc.c pidfile.c utils.c getopt.c getopt1.c list.c rbl.c dropin.c +libvpn_a_SOURCES = xmalloc.c pidfile.c utils.c getopt.c getopt1.c list.c avl_tree.c dropin.c libvpn_a_LIBADD = @LIBOBJS@ @ALLOCA@ libvpn_a_DEPENDENCIES = $(libvpn_a_LIBADD) -noinst_HEADERS = xalloc.h pidfile.h utils.h getopt.h list.h rbl.h dropin.h +noinst_HEADERS = xalloc.h pidfile.h utils.h getopt.h list.h avl_tree.h dropin.h EXTRA_DIST = README diff --git a/lib/avl_tree.c b/lib/avl_tree.c new file mode 100644 index 00000000..df7a0361 --- /dev/null +++ b/lib/avl_tree.c @@ -0,0 +1,677 @@ +/* + avl_tree.c -- avl_ tree and linked list convenience + Copyright (C) 1998 Michael H. Buselli + 2000 Ivo Timmermans , + 2000 Guus Sliepen + 2000 Wessel Dankers + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + Original AVL tree library by Michael H. Buselli . + + 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.1 2001/01/05 23:50:56 guus Exp $ +*/ + +#include +#include +#include + +#include "avl_tree.h" + +#ifdef AVL_COUNT +#define AVL_NODE_COUNT(n) ((n) ? (n)->count : 0) +#define AVL_L_COUNT(n) (AVL_NODE_COUNT((n)->left)) +#define AVL_R_COUNT(n) (AVL_NODE_COUNT((n)->right)) +#define AVL_CALC_COUNT(n) (AVL_L_COUNT(n) + AVL_R_COUNT(n) + 1) +#endif + +#ifdef AVL_DEPTH +#define AVL_NODE_DEPTH(n) ((n) ? (n)->depth : 0) +#define L_AVL_DEPTH(n) (AVL_NODE_DEPTH((n)->left)) +#define R_AVL_DEPTH(n) (AVL_NODE_DEPTH((n)->right)) +#define AVL_CALC_DEPTH(n) ((L_AVL_DEPTH(n)>R_AVL_DEPTH(n)?L_AVL_DEPTH(n):R_AVL_DEPTH(n)) + 1) +#endif + +#ifndef AVL_DEPTH +int lg(unsigned int u) +{ + int r = 1; + if (!u) + return 0; + if (u & 0xffff0000) + { + u >>= 16; + r += 16; + } + if (u & 0x0000ff00) + { + u >>= 8; + r += 8; + } + if (u & 0x000000f0) + { + u >>= 4; + r += 4; + } + if (u & 0x0000000c) + { + u >>= 2; + r += 2; + } + if (u & 0x00000002) + r++; + return r; +} +#endif + +/* Internal helper functions */ + +int avl_check_balance(avl_node_t *node) +{ +#ifdef AVL_DEPTH + int d; + d = R_AVL_DEPTH(node) - L_AVL_DEPTH(node); + return d < -1 ? -1 : d > 1 ? 1 : 0; +#else +/* int d; + * d = lg(AVL_R_COUNT(node)) - lg(AVL_L_COUNT(node)); + * d = d<-1?-1:d>1?1:0; + */ + int pl, r; + + pl = lg(AVL_L_COUNT(node)); + r = AVL_R_COUNT(node); + + if (r >> pl + 1) + return 1; + if (pl < 2 || r >> pl - 2) + return 0; + return -1; +#endif +} + +void avl_rebalance(avl_tree_t *tree, avl_node_t *node) +{ + avl_node_t *child; + avl_node_t *gchild; + avl_node_t *parent; + avl_node_t **superparent; + + parent = node; + + while (node) + { + parent = node->parent; + + superparent = parent ? node == parent->left ? &parent->left : &parent->right : &tree->root; + + switch (avl_check_balance(node)) + { + case -1: + child = node->left; +#ifdef AVL_DEPTH + if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) { +#else + if (AVL_L_COUNT(child) >= AVL_R_COUNT(child)) + { +#endif + node->left = child->right; + if (node->left) + node->left->parent = node; + child->right = node; + node->parent = child; + *superparent = child; + child->parent = parent; +#ifdef AVL_COUNT + node->count = AVL_CALC_COUNT(node); + child->count = AVL_CALC_COUNT(child); +#endif +#ifdef AVL_DEPTH + node->depth = AVL_CALC_DEPTH(node); + child->depth = AVL_CALC_DEPTH(child); +#endif + } else + { + gchild = child->right; + node->left = gchild->right; + if (node->left) + node->left->parent = node; + child->right = gchild->left; + if (child->right) + child->right->parent = child; + gchild->right = node; + if (gchild->right) + gchild->right->parent = gchild; + gchild->left = child; + if (gchild->left) + gchild->left->parent = gchild; + *superparent = gchild; + gchild->parent = parent; +#ifdef AVL_COUNT + node->count = AVL_CALC_COUNT(node); + child->count = AVL_CALC_COUNT(child); + gchild->count = AVL_CALC_COUNT(gchild); +#endif +#ifdef AVL_DEPTH + node->depth = AVL_CALC_DEPTH(node); + child->depth = AVL_CALC_DEPTH(child); + gchild->depth = AVL_CALC_DEPTH(gchild); +#endif + } + break; + case 1: + child = node->right; +#ifdef AVL_DEPTH + if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) { +#else + if (AVL_R_COUNT(child) >= AVL_L_COUNT(child)) + { +#endif + node->right = child->left; + if (node->right) + node->right->parent = node; + child->left = node; + node->parent = child; + *superparent = child; + child->parent = parent; +#ifdef AVL_COUNT + node->count = AVL_CALC_COUNT(node); + child->count = AVL_CALC_COUNT(child); +#endif +#ifdef AVL_DEPTH + node->depth = AVL_CALC_DEPTH(node); + child->depth = AVL_CALC_DEPTH(child); +#endif + } else + { + gchild = child->left; + node->right = gchild->left; + if (node->right) + node->right->parent = node; + child->left = gchild->right; + if (child->left) + child->left->parent = child; + gchild->left = node; + if (gchild->left) + gchild->left->parent = gchild; + gchild->right = child; + if (gchild->right) + gchild->right->parent = gchild; + *superparent = gchild; + gchild->parent = parent; +#ifdef AVL_COUNT + node->count = AVL_CALC_COUNT(node); + child->count = AVL_CALC_COUNT(child); + gchild->count = AVL_CALC_COUNT(gchild); +#endif +#ifdef AVL_DEPTH + node->depth = AVL_CALC_DEPTH(node); + child->depth = AVL_CALC_DEPTH(child); + gchild->depth = AVL_CALC_DEPTH(gchild); +#endif + } + break; + default: +#ifdef AVL_COUNT + node->count = AVL_CALC_COUNT(node); +#endif +#ifdef AVL_DEPTH + node->depth = AVL_CALC_DEPTH(node); +#endif + } + node = parent; + } +} + +/* (De)constructors */ + +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)); + tree->compare = compare; + tree->delete = delete; + + return tree; +} + +void avl_free_tree(avl_tree_t *tree) +{ + free(tree); +} + +avl_node_t *avl_alloc_node(void) +{ + avl_node_t *node; + + node = xmalloc_and_zero(sizeof(avl_node_t)); + + return node; +} + +void avl_free_node(avl_tree_t *tree, avl_node_t *node) +{ + if(node->data && tree->delete) + tree->delete(node->data); + free(node); +} + +/* Searching */ + +void *avl_search(const avl_tree_t *tree, const void *data) +{ + avl_node_t *node; + + node = avl_search_node(tree, data); + + return node?node->data:NULL; +} + +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); + + return node?node->data:NULL; +} + +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); + + return node?node->data:NULL; +} + +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); + + return node?node->data:NULL; +} + +avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data) +{ + avl_node_t *node; + int result; + + node = avl_search_closest_node(tree, data, &result); + + return result?NULL:node; +} + +avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data, int *result) +{ + avl_node_t *node; + int c; + + node = tree->root; + + if (!node) + { + if(result) + *result = 0; + return NULL; + } + + for (;;) + { + c = tree->compare(data, node->data); + + if (c < 0) + { + if (node->left) + node = node->left; + else + { + if(result) + *result = -1; + break; + } + } + else if (c > 0) + { + if (node->right) + node = node->right; + else + { + if(result) + *result = 1; + break; + } + } + else + { + if(result) + *result = 0; + break; + } + } + + return node; +} + +avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree, const void *data) +{ + avl_node_t *node; + int result; + + node = avl_search_closest_node(tree, data, &result); + + if(result > 0) + node = node->prev; + + return node; +} + +avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, const void *data) +{ + avl_node_t *node; + int result; + + node = avl_search_closest_node(tree, data, &result); + + if(result < 0) + node = node->next; + + return node; +} + +/* Insertion and deletion */ + +avl_node_t *avl_insert(avl_tree_t *tree, void *data) +{ + avl_node_t *node; + + node = avl_alloc_node(); + node->data = data; + + return avl_insert_node(tree, node); +} + +avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) +{ + avl_node_t *closest; + int result; + + if (!tree->root) + avl_insert_top(tree, node); + else + { + closest = avl_search_closest_node(tree, node->data, &result); + switch(result) + { + case -1: + avl_insert_before(tree, closest, node); + break; + case 1: + avl_insert_after(tree, closest, node); + break; + case 0: + return closest; + } + } + +#ifdef AVL_COUNT + node->count = 1; +#endif +#ifdef AVL_DEPTH + node->depth = 1; +#endif + + return 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) +{ + if (!before) + return tree->tail ? avl_insert_after(tree, tree->tail, node) : avl_insert_top(tree, node); + + node->next = before; + node->parent = before; + node->prev = before->prev; + + if (before->prev) + before->prev->next = node; + else + tree->head = node; + + before->prev = node; + before->left = node; + + avl_rebalance(tree, before->parent); +} + +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); + + node->prev = after; + node->parent = after; + node->next = after->next; + + if (after->next) + after->next->prev = node; + else + tree->tail = node; + + after->next = node; + after->right = node; + + avl_rebalance(tree, after->parent); +} + +avl_node_t *avl_unlink(avl_tree_t *tree, void *data) +{ + avl_node_t *node; + + node = avl_search_node(tree, data); + + if(node) + avl_unlink_node(tree, node); + + return 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; + avl_node_t *balnode; + + if (node->prev) + node->prev->next = node->next; + else + tree->head = node->next; + if (node->next) + node->next->prev = node->prev; + else + tree->tail = node->prev; + + parent = node->parent; + + superparent = parent ? node == parent->left ? &parent->left : &parent->right : &tree->root; + + left = node->left; + right = node->right; + if (!left) + { + *superparent = right; + if (right) + right->parent = parent; + balnode = parent; + } else if (!right) + { + *superparent = left; + left->parent = parent; + balnode = parent; + } else + { + subst = node->prev; + if (subst == left) + { + balnode = subst; + } else + { + balnode = subst->parent; + balnode->right = subst->left; + if (balnode->right) + balnode->right->parent = balnode; + subst->left = left; + left->parent = subst; + } + subst->right = right; + subst->parent = parent; + right->parent = subst; + *superparent = subst; + } + + avl_rebalance(tree, balnode); +} + +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) +{ + avl_node_t *node; + + node = avl_search_node(tree, data); + + if (node) + avl_delete_node(tree, node); +} + +/* Fast tree cleanup */ + +void avl_delete_tree(avl_tree_t *tree) +{ + avl_node_t *node, *next; + + for(node = tree->root; node; node = next) + { + next = node->next; + avl_free_node(tree, node); + } + + avl_free_tree(tree); +} + +/* Tree walking */ + +void avl_foreach(avl_tree_t *tree, avl_action_t action) +{ + avl_node_t *node, *next; + + for(node = tree->head; node; node = next) + { + next = node->next; + action(node->data); + } +} + +void avl_foreach_node(avl_tree_t *tree, avl_action_t action) +{ + avl_node_t *node, *next; + + for(node = tree->head; node; node = next) + { + next = node->next; + action(node); + } +} + +/* Indexing */ + +#ifdef AVL_COUNT +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 *node; + unsigned int c; + + node = tree->root; + + while (node) + { + c = AVL_L_COUNT(node); + + if (index < c) + { + node = node->left; + } else if (index > c) + { + node = node->right; + index -= c + 1; + } else + { + return node; + } + } + + return NULL; +} + +unsigned int avl_index(const avl_node_t *node) +{ + avl_node_t *next; + unsigned int index; + + index = AVL_L_COUNT(node); + + while ((next = node->parent)) + { + if (node == next->right) + index += AVL_L_COUNT(next) + 1; + node = next; + } + + return index; +} +#endif +#ifdef AVL_DEPTH +unsigned int avl_depth(avl_tree_t *tree) +{ + return AVL_NODE_DEPTH(tree->root); +} +#endif diff --git a/lib/avl_tree.h b/lib/avl_tree.h new file mode 100644 index 00000000..6e07b92b --- /dev/null +++ b/lib/avl_tree.h @@ -0,0 +1,145 @@ +/* + avl_tree.h -- header file for avl_tree.c + Copyright (C) 1998 Michael H. Buselli + 2000 Ivo Timmermans , + 2000 Guus Sliepen + 2000 Wessel Dankers + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + Original AVL tree library by Michael H. Buselli . + + 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.h,v 1.1.2.1 2001/01/05 23:50:56 guus Exp $ +*/ + + +#ifndef __AVL_TREE_H__ +#define __AVL_TREE_H__ + +#ifndef AVL_DEPTH + #ifndef AVL_COUNT + #define AVL_DEPTH + #endif +#endif + +typedef struct avl_node_t { + + /* Linked list part */ + + struct avl_node_t *next; + struct avl_node_t *prev; + + /* Tree part */ + + struct avl_node_t *parent; + struct avl_node_t *left; + struct avl_node_t *right; + +#ifdef AVL_COUNT + unsigned int count; +#endif +#ifdef AVL_DEPTH + unsigned char depth; +#endif + + /* Payload */ + + void *data; + +} avl_node_t; + +typedef int (*avl_compare_t) (const void *, const void *); +typedef void (*avl_action_t) (const void *); +typedef void (*avl_action_node_t) (const avl_node_t *); + +typedef struct avl_tree_t { + + /* Linked list part */ + + avl_node_t *head; + avl_node_t *tail; + + /* Tree part */ + + avl_node_t *root; + + avl_compare_t compare; + avl_action_t delete; + +} avl_tree_t; + +/* (De)constructors */ + +extern avl_tree_t *avl_alloc_tree(avl_compare_t, avl_action_t); +extern void avl_free_tree(avl_tree_t *); + +extern avl_node_t *avl_alloc_node(void); +extern void avl_free_node(avl_tree_t *tree, avl_node_t *); + +/* Insertion and deletion */ + +extern avl_node_t *avl_insert(avl_tree_t *, void *); +extern avl_node_t *avl_insert_node(avl_tree_t *, avl_node_t *); + +extern void avl_insert_top(avl_tree_t *, avl_node_t *); +extern void avl_insert_before(avl_tree_t *, avl_node_t *, avl_node_t *); +extern void avl_insert_after(avl_tree_t *, avl_node_t *, avl_node_t *); + +extern avl_node_t *avl_unlink(avl_tree_t *, void *); +extern void avl_unlink_node(avl_tree_t *tree, avl_node_t *); +extern void avl_delete(avl_tree_t *, void *); +extern void avl_delete_node(avl_tree_t *, avl_node_t *); + +/* Fast tree cleanup */ + +extern void avl_delete_tree(avl_tree_t *); + +/* Searching */ + +extern void *avl_search(const avl_tree_t *, const void *); +extern void *avl_search_closest(const avl_tree_t *, const void *, int *); +extern void *avl_search_closest_smaller(const avl_tree_t *, const void *); +extern void *avl_search_closest_greater(const avl_tree_t *, const void *); + +extern avl_node_t *avl_search_node(const avl_tree_t *, const void *); +extern avl_node_t *avl_search_closest_node(const avl_tree_t *, const void *, int *); +extern avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *, const void *); +extern avl_node_t *avl_search_closest_greater_node(const avl_tree_t *, const void *); + +/* Tree walking */ + +extern void avl_foreach(avl_tree_t *, avl_action_t); +extern void avl_foreach_node(avl_tree_t *, avl_action_t); + +/* Indexing */ + +#ifdef AVL_COUNT +extern unsigned int avl_count(avl_tree_t *); +extern avl_node_t *avl_get_node(const avl_tree_t *, unsigned int); +extern unsigned int avl_index(const avl_node_t *); +#endif +#ifdef AVL_DEPTH +extern unsigned int avl_depth(avl_tree_t *); +#endif + +#endif /* __AVL_TREE_H__ */ -- 2.20.1