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

diff --git a/src/splay_tree.c b/src/splay_tree.c
index aed91561..2d694719 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-2013 Guus Sliepen <guus@meshlink.io>
+    Copyright (C) 2014-2017 Guus Sliepen <guus@meshlink.io>
 
     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
@@ -25,14 +25,19 @@
 /* Splay operation */
 
 static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *result) {
-	splay_node_t left = {NULL}, right = {NULL};
+	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)
+		if(result) {
 			*result = 0;
+		}
+
 		return NULL;
 	}
 
@@ -45,8 +50,9 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 				child->parent = rightbottom;
 				rightbottom = child;
 
-				if((root->left = child->right))
+				if((root->left = child->right)) {
 					child->right->parent = root;
+				}
 
 				child->right = root;
 				root->parent = child;
@@ -55,7 +61,7 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 				grandchild->parent = NULL;
 
 				root = grandchild;
-			} else if (c > 0 && (grandchild = child->right)) {
+			} else if(c > 0 && (grandchild = child->right)) {
 				leftbottom->right = child;
 				child->parent = leftbottom;
 				leftbottom = child;
@@ -89,8 +95,9 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 				child->parent = leftbottom;
 				leftbottom = child;
 
-				if((root->right = child->left))
+				if((root->right = child->left)) {
 					child->left->parent = root;
+				}
 
 				child->left = root;
 				root->parent = child;
@@ -99,7 +106,7 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 				grandchild->parent = NULL;
 
 				root = grandchild;
-			} else if (c < 0 && (grandchild = child->left)) {
+			} else if(c < 0 && (grandchild = child->left)) {
 				rightbottom->left = child;
 				child->parent = rightbottom;
 				rightbottom = child;
@@ -137,6 +144,7 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 			leftbottom->right = root->left;
 			root->left->parent = leftbottom;
 		}
+
 		root->left = left.right;
 		left.right->parent = root;
 	}
@@ -146,6 +154,7 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 			rightbottom->left = root->right;
 			root->right->parent = rightbottom;
 		}
+
 		root->right = right.left;
 		right.left->parent = root;
 	}
@@ -153,8 +162,10 @@ static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *r
 	/* Return result */
 
 	tree->root = root;
-	if(result)
+
+	if(result) {
 		*result = c;
+	}
 
 	return tree->root;
 }
@@ -165,12 +176,16 @@ static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
 	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 {
-				if((parent->right = node->left))
+				if((parent->right = node->left)) {
 					parent->right->parent = parent;
+				}
+
 				node->left = parent;
 			}
 
@@ -180,52 +195,69 @@ static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
 			greatgrandparent = grandparent->parent;
 
 			if(node == parent->left && parent == grandparent->left) { /* left zig-zig */
-				if((grandparent->left = parent->right))
+				if((grandparent->left = parent->right)) {
 					grandparent->left->parent = grandparent;
+				}
+
 				parent->right = grandparent;
 				grandparent->parent = parent;
 
-				if((parent->left = node->right))
+				if((parent->left = node->right)) {
 					parent->left->parent = parent;
+				}
+
 				node->right = parent;
 				parent->parent = node;
 			} else if(node == parent->right && parent == grandparent->right) { /* right zig-zig */
-				if((grandparent->right = parent->left))
+				if((grandparent->right = parent->left)) {
 					grandparent->right->parent = grandparent;
+				}
+
 				parent->left = grandparent;
 				grandparent->parent = parent;
 
-				if((parent->right = node->left))
+				if((parent->right = node->left)) {
 					parent->right->parent = parent;
+				}
+
 				node->left = parent;
 				parent->parent = node;
 			} else if(node == parent->right && parent == grandparent->left) { /* left-right zig-zag */
-				if((parent->right = node->left))
+				if((parent->right = node->left)) {
 					parent->right->parent = parent;
+				}
+
 				node->left = parent;
 				parent->parent = node;
 
-				if((grandparent->left = node->right))
+				if((grandparent->left = node->right)) {
 					grandparent->left->parent = grandparent;
+				}
+
 				node->right = grandparent;
 				grandparent->parent = node;
 			} else { /* right-left zig-zag */
-				if((parent->left = node->right))
+				if((parent->left = node->right)) {
 					parent->left->parent = parent;
+				}
+
 				node->right = parent;
 				parent->parent = node;
 
-				if((grandparent->right = node->left))
+				if((grandparent->right = node->left)) {
 					grandparent->right->parent = grandparent;
+				}
+
 				node->left = grandparent;
 				grandparent->parent = node;
 			}
 
 			if((node->parent = greatgrandparent)) {
-				if(grandparent == greatgrandparent->left)
+				if(grandparent == greatgrandparent->left) {
 					greatgrandparent->left = node;
-				else
+				} else {
 					greatgrandparent->right = node;
+				}
 			}
 		}
 	}
@@ -245,17 +277,14 @@ 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));
 }
 
 void splay_free_node(splay_tree_t *tree, splay_node_t *node) {
-	if(node->data && tree->delete)
+	if(node->data && tree->delete) {
 		tree->delete(node->data);
+	}
 
 	free(node);
 }
@@ -310,8 +339,10 @@ splay_node_t *splay_search_closest_node_nosplay(const splay_tree_t *tree, const
 	node = tree->root;
 
 	if(!node) {
-		if(result)
+		if(result) {
 			*result = 0;
+		}
+
 		return NULL;
 	}
 
@@ -319,22 +350,26 @@ splay_node_t *splay_search_closest_node_nosplay(const splay_tree_t *tree, const
 		c = tree->compare(data, node->data);
 
 		if(c < 0) {
-			if(node->left)
+			if(node->left) {
 				node = node->left;
-			else
+			} else {
 				break;
+			}
 		} else if(c > 0) {
-			if(node->right)
+			if(node->right) {
 				node = node->right;
-			else
+			} else {
 				break;
+			}
 		} else {
 			break;
 		}
 	}
 
-	if(result)
+	if(result) {
 		*result = c;
+	}
+
 	return node;
 }
 
@@ -348,8 +383,9 @@ splay_node_t *splay_search_closest_smaller_node(splay_tree_t *tree, const void *
 
 	node = splay_search_closest_node(tree, data, &result);
 
-	if(result < 0)
+	if(result < 0) {
 		node = node->prev;
+	}
 
 	return node;
 }
@@ -360,91 +396,53 @@ splay_node_t *splay_search_closest_greater_node(splay_tree_t *tree, const void *
 
 	node = splay_search_closest_node(tree, data, &result);
 
-	if(result > 0)
+	if(result > 0) {
 		node = node->next;
+	}
 
 	return node;
 }
 
 /* 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)
+		if(tree->tail) {
 			splay_insert_after(tree, tree->tail, node);
-		else
+		} else {
 			splay_insert_top(tree, node);
+		}
+
 		return;
 	}
 
 	node->next = before;
-	if((node->prev = before->prev))
+
+	if((node->prev = before->prev)) {
 		before->prev->next = node;
-	else
+	} else {
 		tree->head = node;
+	}
+
 	before->prev = node;
 
 	splay_bottom_up(tree, before);
 
 	node->right = before;
 	before->parent = node;
-	if((node->left = before->left))
+
+	if((node->left = before->left)) {
 		before->left->parent = node;
+	}
+
 	before->left = NULL;
 
 	node->parent = NULL;
@@ -452,28 +450,36 @@ 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)
+		if(tree->head) {
 			splay_insert_before(tree, tree->head, node);
-		else
+		} else {
 			splay_insert_top(tree, node);
+		}
+
 		return;
 	}
 
 	node->prev = after;
-	if((node->next = after->next))
+
+	if((node->next = after->next)) {
 		after->next->prev = node;
-	else
+	} else {
 		tree->tail = node;
+	}
+
 	after->next = node;
 
 	splay_bottom_up(tree, after);
 
 	node->left = after;
 	after->parent = node;
-	if((node->right = after->right))
+
+	if((node->right = after->right)) {
 		after->right->parent = node;
+	}
+
 	after->right = NULL;
 
 	node->parent = NULL;
@@ -481,35 +487,97 @@ 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;
 
 	node = splay_search_node(tree, data);
 
-	if(node)
+	if(node) {
 		splay_unlink_node(tree, node);
+	}
 
 	return node;
 }
 
 void splay_unlink_node(splay_tree_t *tree, splay_node_t *node) {
-	if(node->prev)
+	assert(tree->count);
+	assert(node->prev || tree->head == node);
+	assert(node->next || tree->tail == node);
+
+	if(node->prev) {
 		node->prev->next = node->next;
-	else
+	} else {
 		tree->head = node->next;
+	}
 
-	if(node->next)
+	if(node->next) {
 		node->next->prev = node->prev;
-	else
+	} else {
 		tree->tail = node->prev;
+	}
 
 	splay_bottom_up(tree, node);
 
 	if(node->prev) {
 		node->left->parent = NULL;
 		tree->root = node->left;
-		if((node->prev->right = node->right))
+
+		if((node->prev->right = node->right)) {
 			node->right->parent = node->prev;
+		}
 	} else if(node->next) {
 		tree->root = node->right;
 		node->right->parent = NULL;
@@ -530,8 +598,9 @@ void splay_delete(splay_tree_t *tree, void *data) {
 
 	node = splay_search_node(tree, data);
 
-	if(node)
+	if(node) {
 		splay_delete_node(tree, node);
+	}
 }
 
 /* Fast tree cleanup */
@@ -540,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 */