X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=lib%2Fsplay_tree.c;h=62e9e3160b8cb8040199ef3a6d8625d769ddefc6;hp=1b320cc0acd43b71911a684423131957c764e59f;hb=e8f08ced76bf1b9a94dd0dc874ad22761ad8900b;hpb=719cb95ea4fa7a2e6f4291aed607323f290c7a91

diff --git a/lib/splay_tree.c b/lib/splay_tree.c
index 1b320cc0..62e9e316 100644
--- a/lib/splay_tree.c
+++ b/lib/splay_tree.c
@@ -1,6 +1,6 @@
 /*
     splay_tree.c -- splay tree and linked list convenience
-    Copyright (C) 2004 Guus Sliepen <guus@tinc-vpn.org>
+    Copyright (C) 2004-2006 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
@@ -28,194 +28,206 @@
 
 static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *result) {
 	splay_node_t left = {0}, right = {0};
-	splay_node_t *leftbottom = &left, *rightbottom = &right, *child;
-	splay_node_t *node = tree->root;
+	splay_node_t *leftbottom = &left, *rightbottom = &right, *child, *grandchild;
+	splay_node_t *root = tree->root;
 	int c;
 
-	while((c = tree->compare(data, node->data))) {
-		if(c < 0) {
-			child = node->left;
+	if(!root) {
+		if(result)
+			*result = 0;
+		return NULL;
+	}
 
-			if(child) {
-				c = tree->compare(data, child->data);
+	while((c = tree->compare(data, root->data))) {
+		if(c < 0 && (child = root->left)) {
+			c = tree->compare(data, child->data);
+
+			if(c < 0 && (grandchild = child->left)) {
+				rightbottom->left = child;
+				child->parent = rightbottom;
+				rightbottom = child;
+				
+				if((root->left = child->right))
+					child->right->parent = root;
 				
-				if(c < 0) {
-					rightbottom->left = child;
-					child->parent = rightbottom;
-					rightbottom = child;
-
-					node->left = child->right;
-					child->right = node;
-					node->parent = child;
-					node = child->left;
-					child->left = NULL;
-				} else if (c > 0) {
-					if(!child->right)
-						break;
-
-					leftbottom->right = child;
-					child->parent = leftbottom;
-					leftbottom = child;
-
-					rightbottom->left = node;
-					node->parent = rightbottom;
-					rightbottom = node;
-
-					node->left = NULL;
-					node = child->right;
-					child->right = NULL;
-				} else {
-					rightbottom->left = node;
-					node->parent = rightbottom;
-					rightbottom = node;
-
-					node->left = NULL;
-					child->parent = NULL;
-					node = child;
-					break;
-				}
+				child->right = root;
+				root->parent = child;
+
+				child->left = NULL;
+				grandchild->parent = NULL;
+
+				root = grandchild;
+			} else if (c > 0 && (grandchild = child->right)) {
+				leftbottom->right = child;
+				child->parent = leftbottom;
+				leftbottom = child;
+
+				child->right = NULL;
+				grandchild->parent = NULL;
+
+				rightbottom->left = root;
+				root->parent = rightbottom;
+				rightbottom = root;
+
+				root->left = NULL;
+
+				root = grandchild;
 			} else {
+				rightbottom->left = root;
+				root->parent = rightbottom;
+				rightbottom = root;
+				
+				root->left = NULL;
+				child->parent = NULL;
+
+				root = child;
 				break;
 			}
-		} else {
-			child = node->right;
+		} else if(c > 0 && (child = root->right)) {
+			c = tree->compare(data, child->data);
 
-			if(child) {
-				c = tree->compare(data, child->data);
+			if(c > 0 && (grandchild = child->right)) {
+				leftbottom->right = child;
+				child->parent = leftbottom;
+				leftbottom = child;
+				
+				if((root->right = child->left))
+					child->left->parent = root;
 				
-				if(c > 0) {
-					leftbottom->right = child;
-					child->parent = leftbottom;
-					leftbottom = child;
-
-					node->right = child->left;
-					child->left = node;
-					node->parent = child;
-					node = child->right;
-					child->right = NULL;
-				} else if (c < 0) {
-					if(!child->left)
-						break;
-
-					rightbottom->left = child;
-					child->parent = rightbottom;
-					rightbottom = child;
-
-					leftbottom->right = node;
-					node->parent = leftbottom;
-					leftbottom = node;
-
-					node->right = NULL;
-					node = child->left;
-					child->left = NULL;
-				} else {
-					leftbottom->right = node;
-					node->parent = leftbottom;
-					leftbottom = node;
-
-					node->right = NULL;
-					child->parent = NULL;
-					node = child;
-					break;
-				}
+				child->left = root;
+				root->parent = child;
+
+				child->right = NULL;
+				grandchild->parent = NULL;
+
+				root = grandchild;
+			} else if (c < 0 && (grandchild = child->left)) {
+				rightbottom->left = child;
+				child->parent = rightbottom;
+				rightbottom = child;
+
+				child->left = NULL;
+				grandchild->parent = NULL;
+
+				leftbottom->right = root;
+				root->parent = leftbottom;
+				leftbottom = root;
+
+				root->right = NULL;
+
+				root = grandchild;
 			} else {
+				leftbottom->right = root;
+				root->parent = leftbottom;
+				leftbottom = root;
+
+				root->right = NULL;
+				child->parent = NULL;
+
+				root = child;
 				break;
 			}
+		} else {
+			break;
 		}
 	}
 
-	tree->root = node;
-
 	/* Merge trees */
 
 	if(left.right) {
-		if(node->left) {
-			leftbottom->right = node->left;
-			node->left->parent = leftbottom;
+		if(root->left) {
+			leftbottom->right = root->left;
+			root->left->parent = leftbottom;
 		}
-		node->left = left.right;
-		left.right->parent = node;
+		root->left = left.right;
+		left.right->parent = root;
 	}
 
 	if(right.left) {
-		if(node->right) {
-			rightbottom->left = node->right;
-			node->right->parent = rightbottom;
+		if(root->right) {
+			rightbottom->left = root->right;
+			root->right->parent = rightbottom;
 		}
-		node->right = right.left;
-		right.left->parent = node;
+		root->right = right.left;
+		right.left->parent = root;
 	}
 
+	/* Return result */
+
+	tree->root = root;
 	if(result)
 		*result = c;
 
-	return node;
+	return tree->root;
 }
-				
-		
+			
 static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
-	splay_node_t *parent, *grandparent;
+	splay_node_t *parent, *grandparent, *greatgrandparent;
 
-	while(node->parent) {
-		parent = node->parent;
-		grandparent = node->parent->parent;
-
-		if(!grandparent) { /* zig */
+	while((parent = node->parent)) {
+		if(!(grandparent = parent->parent)) { /* zig */
 			if(node == parent->left) {
-				parent->left = node->right;
+				if((parent->left = node->right))				
+					parent->left->parent = parent;
 				node->right = parent;
 			} else {
-				parent->right = node->left;
+				if((parent->right = node->left))
+					parent->right->parent = parent;
 				node->left = parent;
 			}
 
 			parent->parent = node;
 			node->parent = NULL;
 		} else {
-			if(node == grandparent->left->left) { /* left zig-zig */
-				grandparent->left = parent->right;
+			greatgrandparent = grandparent->parent;
+
+			if(node == parent->left && parent == grandparent->left) { /* left zig-zig */
+				if((grandparent->left = parent->right))
+					grandparent->left->parent = grandparent;
 				parent->right = grandparent;
 				grandparent->parent = parent;
 
-				parent->left = node->right;
+				if((parent->left = node->right))
+					parent->left->parent = parent;
 				node->right = parent;
 				parent->parent = node;
-
-			} else if(node == grandparent->right->right) { /* right zig-zig */
-				grandparent->right = parent->left;
+			} else if(node == parent->right && parent == grandparent->right) { /* right zig-zig */
+				if((grandparent->right = parent->left))
+					grandparent->right->parent = grandparent;
 				parent->left = grandparent;
 				grandparent->parent = parent;
 
-				parent->right = node->left;
+				if((parent->right = node->left))
+					parent->right->parent = parent;
 				node->left = parent;
 				parent->parent = node;
-
-			} else if(node == grandparent->left->right) { /* left-right zig-zag */
-				parent->right = node->left;
+			} else if(node == parent->right && parent == grandparent->left) { /* left-right zig-zag */
+				if((parent->right = node->left))
+					parent->right->parent = parent;
 				node->left = parent;
 				parent->parent = node;
 
-				grandparent->left = node->right;
+				if((grandparent->left = node->right))
+					grandparent->left->parent = grandparent;
 				node->right = grandparent;
 				grandparent->parent = node;
-
 			} else { /* right-left zig-zag */
-				parent->left = node->right;
+				if((parent->left = node->right))
+					parent->left->parent = parent;
 				node->right = parent;
 				parent->parent = node;
 
-				grandparent->right = node->left;
+				if((grandparent->right = node->left))
+					grandparent->right->parent = grandparent;
 				node->left = grandparent;
 				grandparent->parent = node;
 			}
 
-			node->parent = grandparent->parent;
-
-			if(node->parent) {
-				if(grandparent == node->parent->left)
-					node->parent->left = node;
+			if((node->parent = greatgrandparent)) {
+				if(grandparent == greatgrandparent->left)
+					greatgrandparent->left = node;
 				else
-					node->parent->right = node;
+					greatgrandparent->right = node;
 			}
 		}
 	}
@@ -311,26 +323,20 @@ splay_node_t *splay_search_closest_node_nosplay(const splay_tree_t *tree, const
 		if(c < 0) {
 			if(node->left)
 				node = node->left;
-			else {
-				if(result)
-					*result = -1;
+			else
 				break;
-			}
 		} else if(c > 0) {
 			if(node->right)
 				node = node->right;
-			else {
-				if(result)
-					*result = 1;
+			else 
 				break;
-			}
 		} else {
-			if(result)
-				*result = 0;
 			break;
 		}
 	}
 
+	if(result)
+		*result = c;
 	return node;
 }
 
@@ -373,7 +379,7 @@ splay_node_t *splay_insert(splay_tree_t *tree, void *data) {
 		new->data = data;
 		splay_insert_top(tree, new);
 	} else {
-		closest = splay_search_closest_node_nosplay(tree, data, &result);
+		closest = splay_search_closest_node(tree, data, &result);
 
 		if(!result)
 			return NULL;
@@ -397,7 +403,7 @@ splay_node_t *splay_insert_node(splay_tree_t *tree, splay_node_t *node) {
 	if(!tree->root)
 		splay_insert_top(tree, node);
 	else {
-		closest = splay_search_closest_node_nosplay(tree, node->data, &result);
+		closest = splay_search_closest_node(tree, node->data, &result);
 		
 		if(!result)
 			return NULL;
@@ -412,7 +418,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->parent = NULL;
+	node->prev = node->next = node->left = node->right = node->parent = NULL;
 	tree->head = tree->tail = tree->root = node;
 }
 
@@ -426,23 +432,22 @@ void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t
 	}
 
 	node->next = before;
-	node->parent = before;
-	node->prev = before->prev;
-
-	if(before->left) {
-		splay_insert_after(tree, before->prev, node);
-		return;
-	}
-
-	if(before->prev)
+	if((node->prev = before->prev))
 		before->prev->next = node;
 	else
 		tree->head = node;
-
 	before->prev = node;
-	before->left = node;
 
-	splay_bottom_up(tree, node);
+	splay_bottom_up(tree, before);
+
+	node->right = before;
+	before->parent = node;
+	if((node->left = before->left))
+		before->left->parent = node;
+	before->left = NULL;
+
+	node->parent = NULL;
+	tree->root = node;
 }
 
 void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
@@ -454,33 +459,31 @@ void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *n
 		return;
 	}
 
-	if(after->right) {
-		splay_insert_before(tree, after->next, node);
-		return;
-	}
-
 	node->prev = after;
-	node->parent = after;
-	node->next = after->next;
-
-	if(after->next)
+	if((node->next = after->next))
 		after->next->prev = node;
 	else
 		tree->tail = node;
-
 	after->next = node;
-	after->right = node;
 
-	splay_bottom_up(tree, node);
+	splay_bottom_up(tree, after);
+
+	node->left = after;
+	after->parent = node;
+	if((node->right = after->right))
+		after->right->parent = node;
+	after->right = NULL;
+
+	node->parent = NULL;
+	tree->root = node;
 }
 
 splay_node_t *splay_unlink(splay_tree_t *tree, void *data) {
 	splay_node_t *node;
-	int result;
 
-	node = splay_search_closest_node_nosplay(tree, data, &result);
+	node = splay_search_node(tree, data);
 
-	if(node && !result)
+	if(node)
 		splay_unlink_node(tree, node);
 
 	return node;
@@ -497,18 +500,18 @@ void splay_unlink_node(splay_tree_t *tree, splay_node_t *node) {
 	else
 		tree->tail = node->prev;
 
-	if(node->left) {
+	splay_bottom_up(tree, node);
+
+	if(node->prev) {
 		node->left->parent = NULL;
 		tree->root = node->left;
-
-		if(node->right) {
-			splay_bottom_up(tree, node->prev);
-			node->prev->right = node->right;
+		if((node->prev->right = node->right))
 			node->right->parent = node->prev;
-		}
-	} else {
-		node->right->parent = NULL;
+	} else if(node->next) {
 		tree->root = node->right;
+		node->right->parent = NULL;
+	} else {
+		tree->root = NULL;
 	}
 }
 
@@ -531,7 +534,7 @@ void splay_delete(splay_tree_t *tree, void *data) {
 void splay_delete_tree(splay_tree_t *tree) {
 	splay_node_t *node, *next;
 
-	for(node = tree->root; node; node = next) {
+	for(node = tree->head; node; node = next) {
 		next = node->next;
 		splay_free_node(tree, node);
 	}