X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Fsplay_tree.c;h=bd0f06b657709c908409537b81696a1892457b6d;hp=135ba06b492ea6e1928af830ea0efbdbc0e11409;hb=c2dc3784f127ef6db6e9960a4abecc1aab6f4e31;hpb=19be9cf7150858311f7898fa3fb525d692d02f64

diff --git a/src/splay_tree.c b/src/splay_tree.c
index 135ba06b..bd0f06b6 100644
--- a/src/splay_tree.c
+++ b/src/splay_tree.c
@@ -1,6 +1,6 @@
 /*
     splay_tree.c -- splay tree and linked list convenience
-    Copyright (C) 2004-2006 Guus Sliepen <guus@tinc-vpn.org>
+    Copyright (C) 2004-2013 Guus Sliepen <guus@tinc-vpn.org>
 
     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
@@ -44,10 +44,10 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 				rightbottom->left = child;
 				child->parent = rightbottom;
 				rightbottom = child;
-				
+
 				if((root->left = child->right))
 					child->right->parent = root;
-				
+
 				child->right = root;
 				root->parent = child;
 
@@ -74,7 +74,7 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 				rightbottom->left = root;
 				root->parent = rightbottom;
 				rightbottom = root;
-				
+
 				root->left = NULL;
 				child->parent = NULL;
 
@@ -88,10 +88,10 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 				leftbottom->right = child;
 				child->parent = leftbottom;
 				leftbottom = child;
-				
+
 				if((root->right = child->left))
 					child->left->parent = root;
-				
+
 				child->left = root;
 				root->parent = child;
 
@@ -158,14 +158,14 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 
 	return tree->root;
 }
-			
+
 static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
 	splay_node_t *parent, *grandparent, *greatgrandparent;
 
 	while((parent = node->parent)) {
 		if(!(grandparent = parent->parent)) { /* zig */
 			if(node == parent->left) {
-				if((parent->left = node->right))				
+				if((parent->left = node->right))
 					parent->left->parent = parent;
 				node->right = parent;
 			} else {
@@ -238,7 +238,7 @@ static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
 splay_tree_t *splay_alloc_tree(splay_compare_t compare, splay_action_t delete) {
 	splay_tree_t *tree;
 
-	tree = xmalloc_and_zero(sizeof(splay_tree_t));
+	tree = xzalloc(sizeof(splay_tree_t));
 	tree->compare = compare;
 	tree->delete = delete;
 
@@ -250,7 +250,7 @@ void splay_free_tree(splay_tree_t *tree) {
 }
 
 splay_node_t *splay_alloc_node(void) {
-	return xmalloc_and_zero(sizeof(splay_node_t));
+	return xzalloc(sizeof(splay_node_t));
 }
 
 void splay_free_node(splay_tree_t *tree, splay_node_t *node) {
@@ -326,7 +326,7 @@ splay_node_t *splay_search_closest_node_nosplay(const splay_tree_t *tree, const
 		} else if(c > 0) {
 			if(node->right)
 				node = node->right;
-			else 
+			else
 				break;
 		} else {
 			break;
@@ -384,12 +384,12 @@ splay_node_t *splay_insert(splay_tree_t *tree, void *data) {
 
 		new = splay_alloc_node();
 		new->data = data;
-		
+
 		if(result < 0)
 			splay_insert_before(tree, closest, new);
 		else
 			splay_insert_after(tree, closest, new);
-	}			
+	}
 
 	return new;
 }
@@ -398,11 +398,13 @@ splay_node_t *splay_insert_node(splay_tree_t *tree, splay_node_t *node) {
 	splay_node_t *closest;
 	int result;
 
+	node->left = node->right = node->parent = node->next = node->prev = NULL;
+
 	if(!tree->root)
 		splay_insert_top(tree, node);
 	else {
 		closest = splay_search_closest_node(tree, node->data, &result);
-		
+
 		if(!result)
 			return NULL;
 
@@ -418,6 +420,7 @@ splay_node_t *splay_insert_node(splay_tree_t *tree, splay_node_t *node) {
 void splay_insert_top(splay_tree_t *tree, splay_node_t *node) {
 	node->prev = node->next = node->left = node->right = node->parent = NULL;
 	tree->head = tree->tail = tree->root = node;
+	tree->count++;
 }
 
 void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t *node) {
@@ -446,6 +449,7 @@ void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t
 
 	node->parent = NULL;
 	tree->root = node;
+	tree->count++;
 }
 
 void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
@@ -474,6 +478,7 @@ void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *n
 
 	node->parent = NULL;
 	tree->root = node;
+	tree->count++;
 }
 
 splay_node_t *splay_unlink(splay_tree_t *tree, void *data) {
@@ -511,6 +516,8 @@ void splay_unlink_node(splay_tree_t *tree, splay_node_t *node) {
 	} else {
 		tree->root = NULL;
 	}
+
+	tree->count--;
 }
 
 void splay_delete_node(splay_tree_t *tree, splay_node_t *node) {
@@ -530,9 +537,7 @@ void splay_delete(splay_tree_t *tree, void *data) {
 /* Fast tree cleanup */
 
 void splay_delete_tree(splay_tree_t *tree) {
-	splay_node_t *node, *next;
-
-	for(node = tree->head; node; node = next) {
+	for(splay_node_t *node = tree->head, *next; node; node = next) {
 		next = node->next;
 		splay_free_node(tree, node);
 	}
@@ -543,18 +548,14 @@ void splay_delete_tree(splay_tree_t *tree) {
 /* Tree walking */
 
 void splay_foreach(const splay_tree_t *tree, splay_action_t action) {
-	splay_node_t *node, *next;
-
-	for(node = tree->head; node; node = next) {
+	for(splay_node_t *node = tree->head, *next; node; node = next) {
 		next = node->next;
 		action(node->data);
 	}
 }
 
 void splay_foreach_node(const splay_tree_t *tree, splay_action_t action) {
-	splay_node_t *node, *next;
-
-	for(node = tree->head; node; node = next) {
+	for(splay_node_t *node = tree->head, *next; node; node = next) {
 		next = node->next;
 		action(node);
 	}