]>
Commit | Line | Data |
---|---|---|
6b2dbba8 ML |
1 | /* |
2 | * mm/interval_tree.c - interval tree for mapping->i_mmap | |
3 | * | |
4 | * Copyright (C) 2012, Michel Lespinasse <walken@google.com> | |
5 | * | |
6 | * This file is released under the GPL v2. | |
7 | */ | |
8 | ||
9 | #include <linux/mm.h> | |
10 | #include <linux/fs.h> | |
9826a516 | 11 | #include <linux/interval_tree_generic.h> |
6b2dbba8 | 12 | |
9826a516 ML |
13 | static inline unsigned long vma_start_pgoff(struct vm_area_struct *v) |
14 | { | |
15 | return v->vm_pgoff; | |
16 | } | |
17 | ||
18 | static inline unsigned long vma_last_pgoff(struct vm_area_struct *v) | |
19 | { | |
20 | return v->vm_pgoff + ((v->vm_end - v->vm_start) >> PAGE_SHIFT) - 1; | |
21 | } | |
22 | ||
23 | INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.linear.rb, | |
24 | unsigned long, shared.linear.rb_subtree_last, | |
25 | vma_start_pgoff, vma_last_pgoff,, vma_interval_tree) | |
26 | ||
27 | /* Insert node immediately after prev in the interval tree */ | |
28 | void vma_interval_tree_insert_after(struct vm_area_struct *node, | |
29 | struct vm_area_struct *prev, | |
30 | struct rb_root *root) | |
6b2dbba8 ML |
31 | { |
32 | struct rb_node **link; | |
33 | struct vm_area_struct *parent; | |
9826a516 | 34 | unsigned long last = vma_last_pgoff(node); |
6b2dbba8 | 35 | |
9826a516 | 36 | VM_BUG_ON(vma_start_pgoff(node) != vma_start_pgoff(prev)); |
6b2dbba8 | 37 | |
9826a516 ML |
38 | if (!prev->shared.linear.rb.rb_right) { |
39 | parent = prev; | |
40 | link = &prev->shared.linear.rb.rb_right; | |
6b2dbba8 | 41 | } else { |
9826a516 | 42 | parent = rb_entry(prev->shared.linear.rb.rb_right, |
6b2dbba8 ML |
43 | struct vm_area_struct, shared.linear.rb); |
44 | if (parent->shared.linear.rb_subtree_last < last) | |
45 | parent->shared.linear.rb_subtree_last = last; | |
46 | while (parent->shared.linear.rb.rb_left) { | |
47 | parent = rb_entry(parent->shared.linear.rb.rb_left, | |
48 | struct vm_area_struct, shared.linear.rb); | |
49 | if (parent->shared.linear.rb_subtree_last < last) | |
50 | parent->shared.linear.rb_subtree_last = last; | |
51 | } | |
52 | link = &parent->shared.linear.rb.rb_left; | |
53 | } | |
54 | ||
9826a516 ML |
55 | node->shared.linear.rb_subtree_last = last; |
56 | rb_link_node(&node->shared.linear.rb, &parent->shared.linear.rb, link); | |
57 | rb_insert_augmented(&node->shared.linear.rb, root, | |
58 | &vma_interval_tree_augment); | |
6b2dbba8 | 59 | } |