X-Git-Url: http://git.meshlink.io/?p=meshlink;a=blobdiff_plain;f=src%2Fsplay_tree.c;h=2d69471971caa8eb379b717ce93ebf961a1224ca;hp=006b4d5ed6889779197e6eb93681ef79eb3f3b0c;hb=963c5055505f2fc117cd5efa06eaa02c9b2bf85d;hpb=b67296418c51784d39a24c3041e2cb199bee06f2

diff --git a/src/splay_tree.c b/src/splay_tree.c
index 006b4d5e..2d694719 100644
--- a/src/splay_tree.c
+++ b/src/splay_tree.c
@@ -25,11 +25,14 @@
 /* Splay operation */
 
 static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *result) {
-	splay_node_t left = {}, right = {};
+	splay_node_t left, right;
 	splay_node_t *leftbottom = &left, *rightbottom = &right, *child, *grandchild;
 	splay_node_t *root = tree->root;
 	int c;
 
+	memset(&left, 0, sizeof(left));
+	memset(&right, 0, sizeof(right));
+
 	if(!root) {
 		if(result) {
 			*result = 0;
@@ -274,10 +277,6 @@ splay_tree_t *splay_alloc_tree(splay_compare_t compare, splay_action_t delete) {
 	return tree;
 }
 
-void splay_free_tree(splay_tree_t *tree) {
-	free(tree);
-}
-
 splay_node_t *splay_alloc_node(void) {
 	return xzalloc(sizeof(splay_node_t));
 }
@@ -406,66 +405,15 @@ splay_node_t *splay_search_closest_greater_node(splay_tree_t *tree, const void *
 
 /* Insertion and deletion */
 
-splay_node_t *splay_insert(splay_tree_t *tree, void *data) {
-	splay_node_t *closest, *new;
-	int result;
-
-	if(!tree->root) {
-		new = splay_alloc_node();
-		new->data = data;
-		splay_insert_top(tree, new);
-	} else {
-		closest = splay_search_closest_node(tree, data, &result);
-
-		if(!result) {
-			return NULL;
-		}
-
-		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;
-}
-
-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;
-		}
-
-		if(result < 0) {
-			splay_insert_before(tree, closest, node);
-		} else {
-			splay_insert_after(tree, closest, node);
-		}
-	}
-
-	return node;
-}
-
-void splay_insert_top(splay_tree_t *tree, splay_node_t *node) {
+static 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) {
+static void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node);
+
+static void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t *node) {
 	if(!before) {
 		if(tree->tail) {
 			splay_insert_after(tree, tree->tail, node);
@@ -502,7 +450,7 @@ void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t
 	tree->count++;
 }
 
-void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
+static void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
 	if(!after) {
 		if(tree->head) {
 			splay_insert_before(tree, tree->head, node);
@@ -539,6 +487,59 @@ void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *n
 	tree->count++;
 }
 
+splay_node_t *splay_insert(splay_tree_t *tree, void *data) {
+	splay_node_t *closest, *new;
+	int result;
+
+	if(!tree->root) {
+		new = splay_alloc_node();
+		new->data = data;
+		splay_insert_top(tree, new);
+	} else {
+		closest = splay_search_closest_node(tree, data, &result);
+
+		if(!result) {
+			return NULL;
+		}
+
+		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;
+}
+
+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;
+		}
+
+		if(result < 0) {
+			splay_insert_before(tree, closest, node);
+		} else {
+			splay_insert_after(tree, closest, node);
+		}
+	}
+
+	return node;
+}
+
 splay_node_t *splay_unlink(splay_tree_t *tree, void *data) {
 	splay_node_t *node;
 
@@ -552,6 +553,10 @@ splay_node_t *splay_unlink(splay_tree_t *tree, void *data) {
 }
 
 void splay_unlink_node(splay_tree_t *tree, splay_node_t *node) {
+	assert(tree->count);
+	assert(node->prev || tree->head == node);
+	assert(node->next || tree->tail == node);
+
 	if(node->prev) {
 		node->prev->next = node->next;
 	} else {
@@ -604,9 +609,11 @@ void splay_delete_tree(splay_tree_t *tree) {
 	for(splay_node_t *node = tree->head, *next; node; node = next) {
 		next = node->next;
 		splay_free_node(tree, node);
+		tree->count--;
 	}
 
-	splay_free_tree(tree);
+	assert(!tree->count);
+	free(tree);
 }
 
 /* Tree walking */