From: "Paul F. Dietz" <dietz@interaccess.com>
To: linux-kernel@vger.rutgers.edu
Cc: linux-mm@kvack.org
Subject: Small patch to mm/mmap_avl.c
Date: Tue, 16 Mar 1999 22:55:31 -0600 [thread overview]
Message-ID: <36EF35C3.E0EFC58D@interaccess.com> (raw)
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/
next reply other threads:[~1999-03-17 4:56 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
1999-03-17 4:55 Paul F. Dietz [this message]
1999-03-17 5:47 ` Ben Pfaff
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=36EF35C3.E0EFC58D@interaccess.com \
--to=dietz@interaccess.com \
--cc=linux-kernel@vger.rutgers.edu \
--cc=linux-mm@kvack.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox