X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Favl_tree.c;h=96d3d4335cf9bfb3a072f4c8caebdb07493c74a2;hp=0d122bf6919fad8d78084e32c62a96b91167cc0b;hb=3fae14fae5a347823679ef694ab630b4991a201d;hpb=985d19caf20058db3c764f0f6fbeafa8bcc59fcc

diff --git a/src/avl_tree.c b/src/avl_tree.c
index 0d122bf6..96d3d433 100644
--- a/src/avl_tree.c
+++ b/src/avl_tree.c
@@ -50,14 +50,14 @@
 #endif
 
 #ifndef AVL_DEPTH
-static int lg(unsigned int u) __attribute__ ((__const__));
+static int lg(unsigned int u) __attribute__((__const__));
 
-static int lg(unsigned int u)
-{
+static int lg(unsigned int u) {
 	int r = 1;
 
-	if(!u)
+	if(!u) {
 		return 0;
+	}
 
 	if(u & 0xffff0000) {
 		u >>= 16;
@@ -79,8 +79,9 @@ static int lg(unsigned int u)
 		r += 2;
 	}
 
-	if(u & 0x00000002)
+	if(u & 0x00000002) {
 		r++;
+	}
 
 	return r;
 }
@@ -88,8 +89,7 @@ static int lg(unsigned int u)
 
 /* Internal helper functions */
 
-static int avl_check_balance(const avl_node_t *node)
-{
+static int avl_check_balance(const avl_node_t *node) {
 #ifdef AVL_DEPTH
 	int d;
 
@@ -97,27 +97,28 @@ static int avl_check_balance(const avl_node_t *node)
 
 	return d < -1 ? -1 : d > 1 ? 1 : 0;
 #else
-/*      int d;
- *      d = lg(AVL_R_COUNT(node)) - lg(AVL_L_COUNT(node));
- *      d = d<-1?-1:d>1?1:0;
- */
+	/*      int d;
+	 *      d = lg(AVL_R_COUNT(node)) - lg(AVL_L_COUNT(node));
+	 *      d = d<-1?-1:d>1?1:0;
+	 */
 	int pl, r;
 
 	pl = lg(AVL_L_COUNT(node));
 	r = AVL_R_COUNT(node);
 
-	if(r >> pl + 1)
+	if(r >> pl + 1) {
 		return 1;
+	}
 
-	if(pl < 2 || r >> pl - 2)
+	if(pl < 2 || r >> pl - 2) {
 		return 0;
+	}
 
 	return -1;
 #endif
 }
 
-static void avl_rebalance(avl_tree_t *tree, avl_node_t *node)
-{
+static void avl_rebalance(avl_tree_t *tree, avl_node_t *node) {
 	avl_node_t *child;
 	avl_node_t *gchild;
 	avl_node_t *parent;
@@ -127,135 +128,154 @@ static void avl_rebalance(avl_tree_t *tree, avl_node_t *node)
 		parent = node->parent;
 
 		superparent =
-			parent ? node ==
-			parent->left ? &parent->left : &parent->right : &tree->root;
+		        parent ? node ==
+		        parent->left ? &parent->left : &parent->right : &tree->root;
 
-		switch (avl_check_balance(node)) {
-			case -1:
-				child = node->left;
+		switch(avl_check_balance(node)) {
+		case -1:
+			child = node->left;
 #ifdef AVL_DEPTH
-				if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) {
+
+			if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) {
 #else
-				if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) {
+
+			if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) {
 #endif
-					node->left = child->right;
-					if(node->left)
-						node->left->parent = node;
-
-					child->right = node;
-					node->parent = child;
-					*superparent = child;
-					child->parent = parent;
+				node->left = child->right;
+
+				if(node->left) {
+					node->left->parent = node;
+				}
+
+				child->right = node;
+				node->parent = child;
+				*superparent = child;
+				child->parent = parent;
 #ifdef AVL_COUNT
-					node->count = AVL_CALC_COUNT(node);
-					child->count = AVL_CALC_COUNT(child);
+				node->count = AVL_CALC_COUNT(node);
+				child->count = AVL_CALC_COUNT(child);
 #endif
 #ifdef AVL_DEPTH
-					node->depth = AVL_CALC_DEPTH(node);
-					child->depth = AVL_CALC_DEPTH(child);
+				node->depth = AVL_CALC_DEPTH(node);
+				child->depth = AVL_CALC_DEPTH(child);
 #endif
-				} else {
-					gchild = child->right;
-					node->left = gchild->right;
+			} else {
+				gchild = child->right;
+				node->left = gchild->right;
 
-					if(node->left)
-						node->left->parent = node;
-					child->right = gchild->left;
+				if(node->left) {
+					node->left->parent = node;
+				}
+
+				child->right = gchild->left;
+
+				if(child->right) {
+					child->right->parent = child;
+				}
 
-					if(child->right)
-						child->right->parent = child;
-					gchild->right = node;
+				gchild->right = node;
 
-					gchild->right->parent = gchild;
-					gchild->left = child;
+				gchild->right->parent = gchild;
+				gchild->left = child;
 
-					gchild->left->parent = gchild;
+				gchild->left->parent = gchild;
 
-					*superparent = gchild;
-					gchild->parent = parent;
+				*superparent = gchild;
+				gchild->parent = parent;
 #ifdef AVL_COUNT
-					node->count = AVL_CALC_COUNT(node);
-					child->count = AVL_CALC_COUNT(child);
-					gchild->count = AVL_CALC_COUNT(gchild);
+				node->count = AVL_CALC_COUNT(node);
+				child->count = AVL_CALC_COUNT(child);
+				gchild->count = AVL_CALC_COUNT(gchild);
 #endif
 #ifdef AVL_DEPTH
-					node->depth = AVL_CALC_DEPTH(node);
-					child->depth = AVL_CALC_DEPTH(child);
-					gchild->depth = AVL_CALC_DEPTH(gchild);
+				node->depth = AVL_CALC_DEPTH(node);
+				child->depth = AVL_CALC_DEPTH(child);
+				gchild->depth = AVL_CALC_DEPTH(gchild);
 #endif
-				}
-				break;
+			}
+
+			break;
 
-			case 1:
-				child = node->right;
+		case 1:
+			child = node->right;
 #ifdef AVL_DEPTH
-				if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) {
+
+			if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) {
 #else
-				if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) {
+
+			if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) {
 #endif
-					node->right = child->left;
-					if(node->right)
-						node->right->parent = node;
-					child->left = node;
-					node->parent = child;
-					*superparent = child;
-					child->parent = parent;
+				node->right = child->left;
+
+				if(node->right) {
+					node->right->parent = node;
+				}
+
+				child->left = node;
+				node->parent = child;
+				*superparent = child;
+				child->parent = parent;
 #ifdef AVL_COUNT
-					node->count = AVL_CALC_COUNT(node);
-					child->count = AVL_CALC_COUNT(child);
+				node->count = AVL_CALC_COUNT(node);
+				child->count = AVL_CALC_COUNT(child);
 #endif
 #ifdef AVL_DEPTH
-					node->depth = AVL_CALC_DEPTH(node);
-					child->depth = AVL_CALC_DEPTH(child);
+				node->depth = AVL_CALC_DEPTH(node);
+				child->depth = AVL_CALC_DEPTH(child);
 #endif
-				} else {
-					gchild = child->left;
-					node->right = gchild->left;
+			} else {
+				gchild = child->left;
+				node->right = gchild->left;
+
+				if(node->right) {
+					node->right->parent = node;
+				}
 
-					if(node->right)
-						node->right->parent = node;
-					child->left = gchild->right;
+				child->left = gchild->right;
+
+				if(child->left) {
+					child->left->parent = child;
+				}
 
-					if(child->left)
-						child->left->parent = child;
-					gchild->left = node;
+				gchild->left = node;
 
-					gchild->left->parent = gchild;
-					gchild->right = child;
+				gchild->left->parent = gchild;
+				gchild->right = child;
 
-					gchild->right->parent = gchild;
+				gchild->right->parent = gchild;
 
-					*superparent = gchild;
-					gchild->parent = parent;
+				*superparent = gchild;
+				gchild->parent = parent;
 #ifdef AVL_COUNT
-					node->count = AVL_CALC_COUNT(node);
-					child->count = AVL_CALC_COUNT(child);
-					gchild->count = AVL_CALC_COUNT(gchild);
+				node->count = AVL_CALC_COUNT(node);
+				child->count = AVL_CALC_COUNT(child);
+				gchild->count = AVL_CALC_COUNT(gchild);
 #endif
 #ifdef AVL_DEPTH
-					node->depth = AVL_CALC_DEPTH(node);
-					child->depth = AVL_CALC_DEPTH(child);
-					gchild->depth = AVL_CALC_DEPTH(gchild);
+				node->depth = AVL_CALC_DEPTH(node);
+				child->depth = AVL_CALC_DEPTH(child);
+				gchild->depth = AVL_CALC_DEPTH(gchild);
 #endif
-				}
-				break;
+			}
 
-			default:
+			break;
+
+		default:
 #ifdef AVL_COUNT
-				node->count = AVL_CALC_COUNT(node);
+			node->count = AVL_CALC_COUNT(node);
 #endif
 #ifdef AVL_DEPTH
-				node->depth = AVL_CALC_DEPTH(node);
+			node->depth = AVL_CALC_DEPTH(node);
 #endif
 		}
+
 		node = parent;
 	}
 }
 
 /* (De)constructors */
 
-avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete)
-{
+avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete) {
 	avl_tree_t *tree;
 
 	tree = xmalloc_and_zero(sizeof(avl_tree_t));
@@ -265,28 +285,25 @@ avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete)
 	return tree;
 }
 
-void avl_free_tree(avl_tree_t *tree)
-{
+void avl_free_tree(avl_tree_t *tree) {
 	free(tree);
 }
 
-avl_node_t *avl_alloc_node(void)
-{
+avl_node_t *avl_alloc_node(void) {
 	return xmalloc_and_zero(sizeof(avl_node_t));
 }
 
-void avl_free_node(avl_tree_t *tree, avl_node_t *node)
-{
-	if(node->data && tree->delete)
+void avl_free_node(avl_tree_t *tree, avl_node_t *node) {
+	if(node->data && tree->delete) {
 		tree->delete(node->data);
+	}
 
 	free(node);
 }
 
 /* Searching */
 
-void *avl_search(const avl_tree_t *tree, const void *data)
-{
+void *avl_search(const avl_tree_t *tree, const void *data) {
 	avl_node_t *node;
 
 	node = avl_search_node(tree, data);
@@ -294,8 +311,7 @@ void *avl_search(const avl_tree_t *tree, const void *data)
 	return node ? node->data : NULL;
 }
 
-void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result)
-{
+void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result) {
 	avl_node_t *node;
 
 	node = avl_search_closest_node(tree, data, result);
@@ -303,8 +319,7 @@ void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result)
 	return node ? node->data : NULL;
 }
 
-void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data)
-{
+void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data) {
 	avl_node_t *node;
 
 	node = avl_search_closest_smaller_node(tree, data);
@@ -312,8 +327,7 @@ void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data)
 	return node ? node->data : NULL;
 }
 
-void *avl_search_closest_greater(const avl_tree_t *tree, const void *data)
-{
+void *avl_search_closest_greater(const avl_tree_t *tree, const void *data) {
 	avl_node_t *node;
 
 	node = avl_search_closest_greater_node(tree, data);
@@ -321,8 +335,7 @@ void *avl_search_closest_greater(const avl_tree_t *tree, const void *data)
 	return node ? node->data : NULL;
 }
 
-avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data)
-{
+avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data) {
 	avl_node_t *node;
 	int result;
 
@@ -332,16 +345,17 @@ avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data)
 }
 
 avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data,
-									int *result)
-{
+                                    int *result) {
 	avl_node_t *node;
 	int c;
 
 	node = tree->root;
 
 	if(!node) {
-		if(result)
+		if(result) {
 			*result = 0;
+		}
+
 		return NULL;
 	}
 
@@ -349,24 +363,30 @@ avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data,
 		c = tree->compare(data, node->data);
 
 		if(c < 0) {
-			if(node->left)
+			if(node->left) {
 				node = node->left;
-			else {
-				if(result)
+			} else {
+				if(result) {
 					*result = -1;
+				}
+
 				break;
 			}
 		} else if(c > 0) {
-			if(node->right)
+			if(node->right) {
 				node = node->right;
-			else {
-				if(result)
+			} else {
+				if(result) {
 					*result = 1;
+				}
+
 				break;
 			}
 		} else {
-			if(result)
+			if(result) {
 				*result = 0;
+			}
+
 			break;
 		}
 	}
@@ -375,37 +395,36 @@ avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data,
 }
 
 avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree,
-											const void *data)
-{
+                const void *data) {
 	avl_node_t *node;
 	int result;
 
 	node = avl_search_closest_node(tree, data, &result);
 
-	if(result < 0)
+	if(result < 0) {
 		node = node->prev;
+	}
 
 	return node;
 }
 
 avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree,
-											const void *data)
-{
+                const void *data) {
 	avl_node_t *node;
 	int result;
 
 	node = avl_search_closest_node(tree, data, &result);
 
-	if(result > 0)
+	if(result > 0) {
 		node = node->next;
+	}
 
 	return node;
 }
 
 /* Insertion and deletion */
 
-avl_node_t *avl_insert(avl_tree_t *tree, void *data)
-{
+avl_node_t *avl_insert(avl_tree_t *tree, void *data) {
 	avl_node_t *closest, *new;
 	int result;
 
@@ -416,21 +435,21 @@ avl_node_t *avl_insert(avl_tree_t *tree, void *data)
 	} 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;
+		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 1:
+			new = avl_alloc_node();
+			new->data = data;
+			avl_insert_after(tree, closest, new);
+			break;
 
-			default:
-				return NULL;
+		default:
+			return NULL;
 		}
 	}
 
@@ -444,27 +463,26 @@ avl_node_t *avl_insert(avl_tree_t *tree, void *data)
 	return new;
 }
 
-avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node)
-{
+avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) {
 	avl_node_t *closest;
 	int result;
 
-	if(!tree->root)
+	if(!tree->root) {
 		avl_insert_top(tree, node);
-	else {
+	} else {
 		closest = avl_search_closest_node(tree, node->data, &result);
 
-		switch (result) {
-			case -1:
-				avl_insert_before(tree, closest, node);
-				break;
+		switch(result) {
+		case -1:
+			avl_insert_before(tree, closest, node);
+			break;
 
-			case 1:
-				avl_insert_after(tree, closest, node);
-				break;
+		case 1:
+			avl_insert_after(tree, closest, node);
+			break;
 
-			case 0:
-				return NULL;
+		case 0:
+			return NULL;
 		}
 	}
 
@@ -478,20 +496,20 @@ avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node)
 	return node;
 }
 
-void avl_insert_top(avl_tree_t *tree, avl_node_t *node)
-{
+void avl_insert_top(avl_tree_t *tree, avl_node_t *node) {
 	node->prev = node->next = node->parent = NULL;
 	tree->head = tree->tail = tree->root = node;
 }
 
 void avl_insert_before(avl_tree_t *tree, avl_node_t *before,
-					   avl_node_t *node)
-{
+                       avl_node_t *node) {
 	if(!before) {
-		if(tree->tail)
+		if(tree->tail) {
 			avl_insert_after(tree, tree->tail, node);
-		else
+		} else {
 			avl_insert_top(tree, node);
+		}
+
 		return;
 	}
 
@@ -504,10 +522,11 @@ void avl_insert_before(avl_tree_t *tree, avl_node_t *before,
 		return;
 	}
 
-	if(before->prev)
+	if(before->prev) {
 		before->prev->next = node;
-	else
+	} else {
 		tree->head = node;
+	}
 
 	before->prev = node;
 	before->left = node;
@@ -515,13 +534,14 @@ void avl_insert_before(avl_tree_t *tree, avl_node_t *before,
 	avl_rebalance(tree, before);
 }
 
-void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
-{
+void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node) {
 	if(!after) {
-		if(tree->head)
+		if(tree->head) {
 			avl_insert_before(tree, tree->head, node);
-		else
+		} else {
 			avl_insert_top(tree, node);
+		}
+
 		return;
 	}
 
@@ -534,10 +554,11 @@ void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
 	node->parent = after;
 	node->next = after->next;
 
-	if(after->next)
+	if(after->next) {
 		after->next->prev = node;
-	else
+	} else {
 		tree->tail = node;
+	}
 
 	after->next = node;
 	after->right = node;
@@ -545,47 +566,51 @@ void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
 	avl_rebalance(tree, after);
 }
 
-avl_node_t *avl_unlink(avl_tree_t *tree, void *data)
-{
+avl_node_t *avl_unlink(avl_tree_t *tree, void *data) {
 	avl_node_t *node;
 
 	node = avl_search_node(tree, data);
 
-	if(node)
+	if(node) {
 		avl_unlink_node(tree, node);
+	}
 
 	return node;
 }
 
-void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
-{
+void avl_unlink_node(avl_tree_t *tree, avl_node_t *node) {
 	avl_node_t *parent;
 	avl_node_t **superparent;
 	avl_node_t *subst, *left, *right;
 	avl_node_t *balnode;
 
-	if(node->prev)
+	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;
+	}
 
 	parent = node->parent;
 
 	superparent =
-		parent ? node ==
-		parent->left ? &parent->left : &parent->right : &tree->root;
+	        parent ? node ==
+	        parent->left ? &parent->left : &parent->right : &tree->root;
 
 	left = node->left;
 	right = node->right;
+
 	if(!left) {
 		*superparent = right;
 
-		if(right)
+		if(right) {
 			right->parent = parent;
+		}
 
 		balnode = parent;
 	} else if(!right) {
@@ -594,8 +619,10 @@ void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
 		balnode = parent;
 	} else {
 		subst = node->prev;
-		if(!subst) // This only happens if node is not actually in a tree at all.
+
+		if(!subst) { // This only happens if node is not actually in a tree at all.
 			abort();
+		}
 
 		if(subst == left) {
 			balnode = subst;
@@ -603,8 +630,9 @@ void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
 			balnode = subst->parent;
 			balnode->right = subst->left;
 
-			if(balnode->right)
+			if(balnode->right) {
 				balnode->right->parent = balnode;
+			}
 
 			subst->left = left;
 			left->parent = subst;
@@ -628,26 +656,24 @@ void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
 #endif
 }
 
-void avl_delete_node(avl_tree_t *tree, avl_node_t *node)
-{
+void avl_delete_node(avl_tree_t *tree, avl_node_t *node) {
 	avl_unlink_node(tree, node);
 	avl_free_node(tree, node);
 }
 
-void avl_delete(avl_tree_t *tree, void *data)
-{
+void avl_delete(avl_tree_t *tree, void *data) {
 	avl_node_t *node;
 
 	node = avl_search_node(tree, data);
 
-	if(node)
+	if(node) {
 		avl_delete_node(tree, node);
+	}
 }
 
 /* Fast tree cleanup */
 
-void avl_delete_tree(avl_tree_t *tree)
-{
+void avl_delete_tree(avl_tree_t *tree) {
 	avl_node_t *node, *next;
 
 	for(node = tree->head; node; node = next) {
@@ -660,8 +686,7 @@ void avl_delete_tree(avl_tree_t *tree)
 
 /* Tree walking */
 
-void avl_foreach(const avl_tree_t *tree, avl_action_t action)
-{
+void avl_foreach(const avl_tree_t *tree, avl_action_t action) {
 	avl_node_t *node, *next;
 
 	for(node = tree->head; node; node = next) {
@@ -670,8 +695,7 @@ void avl_foreach(const avl_tree_t *tree, avl_action_t action)
 	}
 }
 
-void avl_foreach_node(const avl_tree_t *tree, avl_action_t action)
-{
+void avl_foreach_node(const avl_tree_t *tree, avl_action_t action) {
 	avl_node_t *node, *next;
 
 	for(node = tree->head; node; node = next) {
@@ -683,13 +707,11 @@ void avl_foreach_node(const avl_tree_t *tree, avl_action_t action)
 /* Indexing */
 
 #ifdef AVL_COUNT
-unsigned int avl_count(const avl_tree_t *tree)
-{
+unsigned int avl_count(const avl_tree_t *tree) {
 	return AVL_NODE_COUNT(tree->root);
 }
 
-avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index)
-{
+avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index) {
 	avl_node_t *node;
 	unsigned int c;
 
@@ -711,16 +733,17 @@ avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index)
 	return NULL;
 }
 
-unsigned int avl_index(const avl_node_t *node)
-{
+unsigned int avl_index(const avl_node_t *node) {
 	avl_node_t *next;
 	unsigned int index;
 
 	index = AVL_L_COUNT(node);
 
 	while((next = node->parent)) {
-		if(node == next->right)
+		if(node == next->right) {
 			index += AVL_L_COUNT(next) + 1;
+		}
+
 		node = next;
 	}
 
@@ -728,8 +751,7 @@ unsigned int avl_index(const avl_node_t *node)
 }
 #endif
 #ifdef AVL_DEPTH
-unsigned int avl_depth(const avl_tree_t *tree)
-{
+unsigned int avl_depth(const avl_tree_t *tree) {
 	return AVL_NODE_DEPTH(tree->root);
 }
 #endif