From 4bc394a3e29f2f90434bbbfc9f23d5587398471b Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Tue, 6 Feb 2001 10:13:22 +0000 Subject: [PATCH] Fix memory leak in avl_insert() if item was already inserted. --- lib/avl_tree.c | 45 ++++++++++++++++++++++++++++++++++++++------- lib/avl_tree.h | 4 ++-- 2 files changed, 40 insertions(+), 9 deletions(-) diff --git a/lib/avl_tree.c b/lib/avl_tree.c index 341ffeb6..8630d4d0 100644 --- a/lib/avl_tree.c +++ b/lib/avl_tree.c @@ -26,10 +26,10 @@ 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 + library for inclusion into tinc (http://tinc.nl.linux.org/) by Guus Sliepen . - $Id: avl_tree.c,v 1.1.2.4 2001/01/08 21:32:00 guus Exp $ + $Id: avl_tree.c,v 1.1.2.5 2001/02/06 10:13:21 guus Exp $ */ #include @@ -406,12 +406,43 @@ avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, const void * avl_node_t *avl_insert(avl_tree_t *tree, void *data) { - avl_node_t *node; + avl_node_t *closest, *new; + int result; - node = avl_alloc_node(); - node->data = data; + if (!tree->root) + { + new = avl_alloc_node(); + new->data = data; + avl_insert_top(tree, new); + } + else + { + closest = avl_search_closest_node(tree, data, &result); + switch(result) + { + case -1: + new = avl_alloc_node(); + new->data = data; + avl_insert_before(tree, closest, new); + break; + case 1: + new = avl_alloc_node(); + new->data = data; + avl_insert_after(tree, closest, new); + break; + case 0: + return NULL; + } + } + +#ifdef AVL_COUNT + new->count = 1; +#endif +#ifdef AVL_DEPTH + new->depth = 1; +#endif - return avl_insert_node(tree, node); + return new; } avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) @@ -433,7 +464,7 @@ avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) avl_insert_after(tree, closest, node); break; case 0: - return closest; + return NULL; } } diff --git a/lib/avl_tree.h b/lib/avl_tree.h index 49bca181..d1ad6189 100644 --- a/lib/avl_tree.h +++ b/lib/avl_tree.h @@ -26,10 +26,10 @@ 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 + library for inclusion into tinc (http://tinc.nl.linux.org/) by Guus Sliepen . - $Id: avl_tree.h,v 1.1.2.3 2001/01/07 17:08:49 guus Exp $ + $Id: avl_tree.h,v 1.1.2.4 2001/02/06 10:13:22 guus Exp $ */ -- 2.39.5