2 * mm/interval_tree.c - interval tree for mapping->i_mmap
4 * Copyright (C) 2012, Michel Lespinasse <walken@google.com>
6 * This file is released under the GPL v2.
11 #include <linux/rmap.h>
12 #include <linux/interval_tree_generic.h>
14 static inline unsigned long vma_start_pgoff(struct vm_area_struct
*v
)
19 static inline unsigned long vma_last_pgoff(struct vm_area_struct
*v
)
21 return v
->vm_pgoff
+ ((v
->vm_end
- v
->vm_start
) >> PAGE_SHIFT
) - 1;
24 INTERVAL_TREE_DEFINE(struct vm_area_struct
, shared
.linear
.rb
,
25 unsigned long, shared
.linear
.rb_subtree_last
,
26 vma_start_pgoff
, vma_last_pgoff
,, vma_interval_tree
)
28 /* Insert node immediately after prev in the interval tree */
29 void vma_interval_tree_insert_after(struct vm_area_struct
*node
,
30 struct vm_area_struct
*prev
,
33 struct rb_node
**link
;
34 struct vm_area_struct
*parent
;
35 unsigned long last
= vma_last_pgoff(node
);
37 VM_BUG_ON(vma_start_pgoff(node
) != vma_start_pgoff(prev
));
39 if (!prev
->shared
.linear
.rb
.rb_right
) {
41 link
= &prev
->shared
.linear
.rb
.rb_right
;
43 parent
= rb_entry(prev
->shared
.linear
.rb
.rb_right
,
44 struct vm_area_struct
, shared
.linear
.rb
);
45 if (parent
->shared
.linear
.rb_subtree_last
< last
)
46 parent
->shared
.linear
.rb_subtree_last
= last
;
47 while (parent
->shared
.linear
.rb
.rb_left
) {
48 parent
= rb_entry(parent
->shared
.linear
.rb
.rb_left
,
49 struct vm_area_struct
, shared
.linear
.rb
);
50 if (parent
->shared
.linear
.rb_subtree_last
< last
)
51 parent
->shared
.linear
.rb_subtree_last
= last
;
53 link
= &parent
->shared
.linear
.rb
.rb_left
;
56 node
->shared
.linear
.rb_subtree_last
= last
;
57 rb_link_node(&node
->shared
.linear
.rb
, &parent
->shared
.linear
.rb
, link
);
58 rb_insert_augmented(&node
->shared
.linear
.rb
, root
,
59 &vma_interval_tree_augment
);
62 static inline unsigned long avc_start_pgoff(struct anon_vma_chain
*avc
)
64 return vma_start_pgoff(avc
->vma
);
67 static inline unsigned long avc_last_pgoff(struct anon_vma_chain
*avc
)
69 return vma_last_pgoff(avc
->vma
);
72 INTERVAL_TREE_DEFINE(struct anon_vma_chain
, rb
, unsigned long, rb_subtree_last
,
73 avc_start_pgoff
, avc_last_pgoff
,, anon_vma_interval_tree
)