Commit | Line | Data |
---|---|---|
98683650 PR |
1 | #include <asm/bug.h> |
2 | #include <linux/rbtree_augmented.h> | |
0939b0e5 AG |
3 | #include "drbd_interval.h" |
4 | ||
5 | /** | |
6 | * interval_end - return end of @node | |
7 | */ | |
8 | static inline | |
9 | sector_t interval_end(struct rb_node *node) | |
10 | { | |
11 | struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb); | |
12 | return this->end; | |
13 | } | |
14 | ||
15 | /** | |
98683650 | 16 | * compute_subtree_last - compute end of @node |
0939b0e5 AG |
17 | * |
18 | * The end of an interval is the highest (start + (size >> 9)) value of this | |
19 | * node and of its children. Called for @node and its parents whenever the end | |
20 | * may have changed. | |
21 | */ | |
98683650 PR |
22 | static inline sector_t |
23 | compute_subtree_last(struct drbd_interval *node) | |
0939b0e5 | 24 | { |
98683650 | 25 | sector_t max = node->sector + (node->size >> 9); |
0939b0e5 | 26 | |
98683650 PR |
27 | if (node->rb.rb_left) { |
28 | sector_t left = interval_end(node->rb.rb_left); | |
29 | if (left > max) | |
30 | max = left; | |
31 | } | |
32 | if (node->rb.rb_right) { | |
33 | sector_t right = interval_end(node->rb.rb_right); | |
34 | if (right > max) | |
35 | max = right; | |
0939b0e5 | 36 | } |
98683650 PR |
37 | return max; |
38 | } | |
39 | ||
40 | static void augment_propagate(struct rb_node *rb, struct rb_node *stop) | |
41 | { | |
42 | while (rb != stop) { | |
43 | struct drbd_interval *node = rb_entry(rb, struct drbd_interval, rb); | |
44 | sector_t subtree_last = compute_subtree_last(node); | |
45 | if (node->end == subtree_last) | |
46 | break; | |
47 | node->end = subtree_last; | |
48 | rb = rb_parent(&node->rb); | |
0939b0e5 | 49 | } |
0939b0e5 AG |
50 | } |
51 | ||
98683650 PR |
52 | static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) |
53 | { | |
54 | struct drbd_interval *old = rb_entry(rb_old, struct drbd_interval, rb); | |
55 | struct drbd_interval *new = rb_entry(rb_new, struct drbd_interval, rb); | |
56 | ||
57 | new->end = old->end; | |
58 | } | |
59 | ||
60 | static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) | |
61 | { | |
62 | struct drbd_interval *old = rb_entry(rb_old, struct drbd_interval, rb); | |
63 | struct drbd_interval *new = rb_entry(rb_new, struct drbd_interval, rb); | |
64 | ||
65 | new->end = old->end; | |
66 | old->end = compute_subtree_last(old); | |
67 | } | |
68 | ||
69 | static const struct rb_augment_callbacks augment_callbacks = { | |
70 | augment_propagate, | |
71 | augment_copy, | |
72 | augment_rotate, | |
73 | }; | |
74 | ||
0939b0e5 AG |
75 | /** |
76 | * drbd_insert_interval - insert a new interval into a tree | |
77 | */ | |
78 | bool | |
79 | drbd_insert_interval(struct rb_root *root, struct drbd_interval *this) | |
80 | { | |
81 | struct rb_node **new = &root->rb_node, *parent = NULL; | |
82 | ||
83 | BUG_ON(!IS_ALIGNED(this->size, 512)); | |
84 | ||
85 | while (*new) { | |
86 | struct drbd_interval *here = | |
87 | rb_entry(*new, struct drbd_interval, rb); | |
88 | ||
89 | parent = *new; | |
90 | if (this->sector < here->sector) | |
91 | new = &(*new)->rb_left; | |
92 | else if (this->sector > here->sector) | |
93 | new = &(*new)->rb_right; | |
94 | else if (this < here) | |
95 | new = &(*new)->rb_left; | |
6618bf16 | 96 | else if (this > here) |
0939b0e5 | 97 | new = &(*new)->rb_right; |
6618bf16 | 98 | else |
0939b0e5 AG |
99 | return false; |
100 | } | |
101 | ||
102 | rb_link_node(&this->rb, parent, new); | |
98683650 | 103 | rb_insert_augmented(&this->rb, root, &augment_callbacks); |
0939b0e5 AG |
104 | return true; |
105 | } | |
106 | ||
107 | /** | |
108 | * drbd_contains_interval - check if a tree contains a given interval | |
109 | * @sector: start sector of @interval | |
110 | * @interval: may not be a valid pointer | |
111 | * | |
112 | * Returns if the tree contains the node @interval with start sector @start. | |
113 | * Does not dereference @interval until @interval is known to be a valid object | |
114 | * in @tree. Returns %false if @interval is in the tree but with a different | |
115 | * sector number. | |
116 | */ | |
117 | bool | |
118 | drbd_contains_interval(struct rb_root *root, sector_t sector, | |
119 | struct drbd_interval *interval) | |
120 | { | |
121 | struct rb_node *node = root->rb_node; | |
122 | ||
123 | while (node) { | |
124 | struct drbd_interval *here = | |
125 | rb_entry(node, struct drbd_interval, rb); | |
126 | ||
127 | if (sector < here->sector) | |
128 | node = node->rb_left; | |
129 | else if (sector > here->sector) | |
130 | node = node->rb_right; | |
131 | else if (interval < here) | |
132 | node = node->rb_left; | |
133 | else if (interval > here) | |
134 | node = node->rb_right; | |
135 | else | |
3e05146f | 136 | return true; |
0939b0e5 AG |
137 | } |
138 | return false; | |
139 | } | |
140 | ||
141 | /** | |
142 | * drbd_remove_interval - remove an interval from a tree | |
143 | */ | |
144 | void | |
145 | drbd_remove_interval(struct rb_root *root, struct drbd_interval *this) | |
146 | { | |
98683650 | 147 | rb_erase_augmented(&this->rb, root, &augment_callbacks); |
0939b0e5 AG |
148 | } |
149 | ||
150 | /** | |
151 | * drbd_find_overlap - search for an interval overlapping with [sector, sector + size) | |
152 | * @sector: start sector | |
153 | * @size: size, aligned to 512 bytes | |
154 | * | |
70b19876 AG |
155 | * Returns an interval overlapping with [sector, sector + size), or NULL if |
156 | * there is none. When there is more than one overlapping interval in the | |
157 | * tree, the interval with the lowest start sector is returned, and all other | |
158 | * overlapping intervals will be on the right side of the tree, reachable with | |
159 | * rb_next(). | |
0939b0e5 AG |
160 | */ |
161 | struct drbd_interval * | |
162 | drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size) | |
163 | { | |
164 | struct rb_node *node = root->rb_node; | |
165 | struct drbd_interval *overlap = NULL; | |
166 | sector_t end = sector + (size >> 9); | |
167 | ||
168 | BUG_ON(!IS_ALIGNED(size, 512)); | |
169 | ||
170 | while (node) { | |
171 | struct drbd_interval *here = | |
172 | rb_entry(node, struct drbd_interval, rb); | |
173 | ||
174 | if (node->rb_left && | |
175 | sector < interval_end(node->rb_left)) { | |
176 | /* Overlap if any must be on left side */ | |
177 | node = node->rb_left; | |
178 | } else if (here->sector < end && | |
179 | sector < here->sector + (here->size >> 9)) { | |
180 | overlap = here; | |
181 | break; | |
182 | } else if (sector >= here->sector) { | |
183 | /* Overlap if any must be on right side */ | |
184 | node = node->rb_right; | |
185 | } else | |
186 | break; | |
187 | } | |
188 | return overlap; | |
189 | } | |
d0e22a26 AG |
190 | |
191 | struct drbd_interval * | |
192 | drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size) | |
193 | { | |
194 | sector_t end = sector + (size >> 9); | |
195 | struct rb_node *node; | |
196 | ||
197 | for (;;) { | |
198 | node = rb_next(&i->rb); | |
199 | if (!node) | |
200 | return NULL; | |
201 | i = rb_entry(node, struct drbd_interval, rb); | |
202 | if (i->sector >= end) | |
203 | return NULL; | |
204 | if (sector < i->sector + (i->size >> 9)) | |
205 | return i; | |
206 | } | |
207 | } |