linux-imx

/*

 * mm/interval_tree.c - interval tree for mapping->i_mmap

 *

 * Copyright (C) 2012, Michel Lespinasse <walken@google.com>

 *

 * This file is released under the GPL v2.

 */

​

#include <linux/mm.h>

#include <linux/fs.h>

#include <linux/rmap.h>

#include <linux/interval_tree_generic.h>

​

static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)

{

    return v->vm_pgoff;

}

​

static inline unsigned long vma_last_pgoff(struct vm_area_struct *v)

{

    return v->vm_pgoff + vma_pages(v) - 1;

}

​

INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb,

             unsigned long, shared.rb_subtree_last,

             vma_start_pgoff, vma_last_pgoff,, vma_interval_tree)

​

/* Insert node immediately after prev in the interval tree */

void vma_interval_tree_insert_after(struct vm_area_struct *node,

                    struct vm_area_struct *prev,

                    struct rb_root_cached *root)

{

    struct rb_node **link;

    struct vm_area_struct *parent;

    unsigned long last = vma_last_pgoff(node);

​

    VM_BUG_ON_VMA(vma_start_pgoff(node) != vma_start_pgoff(prev), node);

​

    if (!prev->shared.rb.rb_right) {

        parent = prev;

        link = &prev->shared.rb.rb_right;

    } else {

        parent = rb_entry(prev->shared.rb.rb_right,

                  struct vm_area_struct, shared.rb);

        if (parent->shared.rb_subtree_last < last)

            parent->shared.rb_subtree_last = last;

        while (parent->shared.rb.rb_left) {

            parent = rb_entry(parent->shared.rb.rb_left,

                struct vm_area_struct, shared.rb);

            if (parent->shared.rb_subtree_last < last)

                parent->shared.rb_subtree_last = last;

        }

        link = &parent->shared.rb.rb_left;

    }

​

    node->shared.rb_subtree_last = last;

    rb_link_node(&node->shared.rb, &parent->shared.rb, link);

    rb_insert_augmented(&node->shared.rb, &root->rb_root,

                &vma_interval_tree_augment);

}

​

static inline unsigned long avc_start_pgoff(struct anon_vma_chain *avc)

{