On Thu, 2012-06-21 at 17:57 -0400, Rik van Riel wrote:

+static unsigned long largest_free_gap(struct rb_node *node)
+{
+       struct vm_area_struct *vma, *prev, *left = NULL, *right = NULL;
+       unsigned long largest = 0;
+
+       if (node->rb_left)
+               left = rb_to_vma(node->rb_left);
+       if (node->rb_right)
+               right = rb_to_vma(node->rb_right);
+
+       /* Calculate the free gap size between us and the VMA to our left. */
+       vma = rb_to_vma(node);
+       prev = vma->vm_prev;
+
+       if (prev)
+               largest = vma->vm_start - prev->vm_end;
+       else
+               largest = vma->vm_start;
+
+       /* We propagate the largest of our own, or our children's free gaps. */
+       if (left)
+               largest = max(largest, left->free_gap);
+       if (right)
+               largest = max(largest, right->free_gap);
+
+       return largest;
+} 

If you introduce helpers like:

static inline struct vm_area_struct *vma_of(struct rb_node *node)
{
        return container_of(node, struct vm_area_struct, vm_rb);
}

static inline unsigned long max_gap_of(struct rb_node *node)
{
        return vma_of(node)->free_gap;
}

static unsigned long gap_of(struct rb_node *node)
{
        struct vm_area_struct *vma = vma_of(node);

        if (!vma->vm_prev)
                return vma->vm_start;

        return vma->vm_start - vma->vm_prev->vm_end;
}

You can write your largest free gap as:

unsigned long largest_gap(struct rb_node *node)
{
	unsigned long gap = gap_of(node);

	if (node->rb_left)
		gap = max(gap, max_gap_of(node->rb_left));
	if (node->rb_right)
		gap = max(gap, max_gap_of(node->rb_right));

	return gap;
}

And as shown, you can re-used those {max_,}gap_of() function in the
lookup function in the next patch.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>