Small patch to mm/mmap_avl.c

Small patch to mm/mmap_avl.c

[Paul F. Dietz]

I want to rewrite the AVL tree code in mm/mmap_avl.c.
Before I do that, though, I wanted to clean up the
existing code a bit.  Here's a small patch to 2.2.3 that
gets rid of some unnecessary counters.  After this,
I want to recode using the AVL tree routines from
Knuth vol. 3, storing the height difference of the
children at each node, rather than the height itself.

===============================================================
--- linux-backup/mm/mmap_avl.c	Thu Mar 11 06:34:07 1999
+++ linux/mm/mmap_avl.c	Sun Mar 14 20:56:06 1999
@@ -84,9 +84,10 @@
  * nodes[0]..nodes[k-1] such that
  * nodes[0] is the root and nodes[i+1] = nodes[i]->{vm_avl_left|vm_avl_right}.
  */
-static void avl_rebalance (struct vm_area_struct *** nodeplaces_ptr, int count)
+static void avl_rebalance (struct vm_area_struct *** nodeplaces_ptr,
+			   struct vm_area_struct *** nodeplaces_base)
 {
-	for ( ; count > 0 ; count--) {
+	while (nodeplaces_ptr > nodeplaces_base) {
 		struct vm_area_struct ** nodeplace = *--nodeplaces_ptr;
 		struct vm_area_struct * node = *nodeplace;
 		struct vm_area_struct * nodeleft = node->vm_avl_left;
@@ -166,13 +167,12 @@
 	vm_avl_key_t key = new_node->vm_avl_key;
 	struct vm_area_struct ** nodeplace = ptree;
 	struct vm_area_struct ** stack[avl_maxheight];
-	int stack_count = 0;
-	struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
+	struct vm_area_struct *** stack_ptr = &stack[0];
 	for (;;) {
 		struct vm_area_struct * node = *nodeplace;
 		if (node == vm_avl_empty)
 			break;
-		*stack_ptr++ = nodeplace; stack_count++;
+		*stack_ptr++ = nodeplace;
 		if (key < node->vm_avl_key)
 			nodeplace = &node->vm_avl_left;
 		else
@@ -182,7 +182,7 @@
 	new_node->vm_avl_right = vm_avl_empty;
 	new_node->vm_avl_height = 1;
 	*nodeplace = new_node;
-	avl_rebalance(stack_ptr,stack_count);
+	avl_rebalance(stack_ptr,&stack[0]);
 }
 
 /* Insert a node into a tree, and
@@ -194,14 +194,13 @@
 	vm_avl_key_t key = new_node->vm_avl_key;
 	struct vm_area_struct ** nodeplace = ptree;
 	struct vm_area_struct ** stack[avl_maxheight];
-	int stack_count = 0;
-	struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
+	struct vm_area_struct *** stack_ptr = &stack[0];
 	*to_the_left = *to_the_right = NULL;
 	for (;;) {
 		struct vm_area_struct * node = *nodeplace;
 		if (node == vm_avl_empty)
 			break;
-		*stack_ptr++ = nodeplace; stack_count++;
+		*stack_ptr++ = nodeplace;
 		if (key < node->vm_avl_key) {
 			*to_the_right = node;
 			nodeplace = &node->vm_avl_left;
@@ -214,7 +213,7 @@
 	new_node->vm_avl_right = vm_avl_empty;
 	new_node->vm_avl_height = 1;
 	*nodeplace = new_node;
-	avl_rebalance(stack_ptr,stack_count);
+	avl_rebalance(stack_ptr,&stack[0]);
 }
 
 /* Removes a node out of a tree. */
@@ -223,8 +222,7 @@
 	vm_avl_key_t key = node_to_delete->vm_avl_key;
 	struct vm_area_struct ** nodeplace = ptree;
 	struct vm_area_struct ** stack[avl_maxheight];
-	int stack_count = 0;
-	struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
+	struct vm_area_struct *** stack_ptr = &stack[0];
 	struct vm_area_struct ** nodeplace_to_delete;
 	for (;;) {
 		struct vm_area_struct * node = *nodeplace;
@@ -235,7 +233,7 @@
 			return;
 		}
 #endif
-		*stack_ptr++ = nodeplace; stack_count++;
+		*stack_ptr++ = nodeplace;
 		if (key == node->vm_avl_key)
 			break;
 		if (key < node->vm_avl_key)
@@ -247,7 +245,7 @@
 	/* Have to remove node_to_delete = *nodeplace_to_delete. */
 	if (node_to_delete->vm_avl_left == vm_avl_empty) {
 		*nodeplace_to_delete = node_to_delete->vm_avl_right;
-		stack_ptr--; stack_count--;
+		stack_ptr--;
 	} else {
 		struct vm_area_struct *** stack_ptr_to_delete = stack_ptr;
 		struct vm_area_struct ** nodeplace = &node_to_delete->vm_avl_left;
@@ -256,7 +254,7 @@
 			node = *nodeplace;
 			if (node->vm_avl_right == vm_avl_empty)
 				break;
-			*stack_ptr++ = nodeplace; stack_count++;
+			*stack_ptr++ = nodeplace;
 			nodeplace = &node->vm_avl_right;
 		}
 		*nodeplace = node->vm_avl_left;
@@ -267,7 +265,7 @@
 		*nodeplace_to_delete = node; /* replace node_to_delete */
 		*stack_ptr_to_delete = &node->vm_avl_left; /* replace
&node_to_delete->vm_avl_left */
 	}
-	avl_rebalance(stack_ptr,stack_count);
+	avl_rebalance(stack_ptr,&stack[0]);
 }
 
 #ifdef DEBUG_AVL
--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: Small patch to mm/mmap_avl.c

[Ben Pfaff]

"Paul F. Dietz" <dietz@interaccess.com> writes:

   I want to rewrite the AVL tree code in mm/mmap_avl.c.
   Before I do that, though, I wanted to clean up the
   existing code a bit.  Here's a small patch to 2.2.3 that
   gets rid of some unnecessary counters.  After this,
   I want to recode using the AVL tree routines from
   Knuth vol. 3, storing the height difference of the
   children at each node, rather than the height itself.

If you want to do it using Knuth vol. 3, then you might want to take a
look at my libavl, which uses his algorithm for insertion and an
algorithm I developed from his outline for deletion.  All iterative,
of course, given the way that Knuth writes his algorithms.

You can find libavl at ftp://ftp.gnu.org/pub/gnu/avl.  Currently
version 1.2.4 is there but 1.2.8 with minor nits fixed should be moved
there soon; 1.2.8 is currently in ftp://alpha.gnu.org/gnu.
--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/