On 06/29/2012 07:46 PM, Michel Lespinasse wrote:
I have the free_gap(node) function now.
rb_link_node(&vma->vm_rb, rb_parent, rb_link);
rb_insert_color(&vma->vm_rb,&mm->mm_rb);
+ adjust_free_gap(vma);
+ /* Propagate the new free gap between next and us up the tree. */
+ if (vma->vm_next)
+ adjust_free_gap(vma->vm_next);
}
So this will work, and may be fine for a first implementation. However,
the augmented rbtree support really seems inadequate here. What we
would want is for adjust_free_gap to adjust the node's free_gap as
well as its parents, and *stop* when it reaches a node that already
has the desired free_gap instead of going all the way to the root as
it does now. But, to do that we would also need rb_insert_color() to
adjust free_gap as needed when doing tree rotations, and it doesn't
have the necessary support there.
Basically, I think lib/rbtree.c should provide augmented rbtree support
in the form of (versions of) rb_insert_color() and rb_erase() being able to
callback to adjust the augmented node information around tree rotations,
instead of using (conservative, overkill) loops to adjust the augmented
node information after the fact
That is what I originally worked on.
I threw out that code after people told me (at LSF/MM) in
no uncertain terms that I should use the augmented rbtree
code :)
Will CC you on the next version.
--
All rights reversed
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>