1
2#include <asm/bug.h>
3#include <linux/rbtree_augmented.h>
4#include "drbd_interval.h"
5
6
7
8
9static inline
10sector_t interval_end(struct rb_node *node)
11{
12 struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
13 return this->end;
14}
15
16
17
18
19
20
21
22
23static inline sector_t
24compute_subtree_last(struct drbd_interval *node)
25{
26 sector_t max = node->sector + (node->size >> 9);
27
28 if (node->rb.rb_left) {
29 sector_t left = interval_end(node->rb.rb_left);
30 if (left > max)
31 max = left;
32 }
33 if (node->rb.rb_right) {
34 sector_t right = interval_end(node->rb.rb_right);
35 if (right > max)
36 max = right;
37 }
38 return max;
39}
40
41RB_DECLARE_CALLBACKS(static, augment_callbacks, struct drbd_interval, rb,
42 sector_t, end, compute_subtree_last);
43
44
45
46
47bool
48drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)
49{
50 struct rb_node **new = &root->rb_node, *parent = NULL;
51 sector_t this_end = this->sector + (this->size >> 9);
52
53 BUG_ON(!IS_ALIGNED(this->size, 512));
54
55 while (*new) {
56 struct drbd_interval *here =
57 rb_entry(*new, struct drbd_interval, rb);
58
59 parent = *new;
60 if (here->end < this_end)
61 here->end = this_end;
62 if (this->sector < here->sector)
63 new = &(*new)->rb_left;
64 else if (this->sector > here->sector)
65 new = &(*new)->rb_right;
66 else if (this < here)
67 new = &(*new)->rb_left;
68 else if (this > here)
69 new = &(*new)->rb_right;
70 else
71 return false;
72 }
73
74 this->end = this_end;
75 rb_link_node(&this->rb, parent, new);
76 rb_insert_augmented(&this->rb, root, &augment_callbacks);
77 return true;
78}
79
80
81
82
83
84
85
86
87
88
89
90bool
91drbd_contains_interval(struct rb_root *root, sector_t sector,
92 struct drbd_interval *interval)
93{
94 struct rb_node *node = root->rb_node;
95
96 while (node) {
97 struct drbd_interval *here =
98 rb_entry(node, struct drbd_interval, rb);
99
100 if (sector < here->sector)
101 node = node->rb_left;
102 else if (sector > here->sector)
103 node = node->rb_right;
104 else if (interval < here)
105 node = node->rb_left;
106 else if (interval > here)
107 node = node->rb_right;
108 else
109 return true;
110 }
111 return false;
112}
113
114
115
116
117void
118drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
119{
120 rb_erase_augmented(&this->rb, root, &augment_callbacks);
121}
122
123
124
125
126
127
128
129
130
131
132
133
134struct drbd_interval *
135drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
136{
137 struct rb_node *node = root->rb_node;
138 struct drbd_interval *overlap = NULL;
139 sector_t end = sector + (size >> 9);
140
141 BUG_ON(!IS_ALIGNED(size, 512));
142
143 while (node) {
144 struct drbd_interval *here =
145 rb_entry(node, struct drbd_interval, rb);
146
147 if (node->rb_left &&
148 sector < interval_end(node->rb_left)) {
149
150 node = node->rb_left;
151 } else if (here->sector < end &&
152 sector < here->sector + (here->size >> 9)) {
153 overlap = here;
154 break;
155 } else if (sector >= here->sector) {
156
157 node = node->rb_right;
158 } else
159 break;
160 }
161 return overlap;
162}
163
164struct drbd_interval *
165drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size)
166{
167 sector_t end = sector + (size >> 9);
168 struct rb_node *node;
169
170 for (;;) {
171 node = rb_next(&i->rb);
172 if (!node)
173 return NULL;
174 i = rb_entry(node, struct drbd_interval, rb);
175 if (i->sector >= end)
176 return NULL;
177 if (sector < i->sector + (i->size >> 9))
178 return i;
179 }
180}
181