1 #include "drbd_interval.h"
4 * interval_end - return end of @node
7 sector_t interval_end(struct rb_node *node)
9 struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
14 * update_interval_end - recompute end of @node
16 * The end of an interval is the highest (start + (size >> 9)) value of this
17 * node and of its children. Called for @node and its parents whenever the end
21 update_interval_end(struct rb_node *node, void *__unused)
23 struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
26 end = this->sector + (this->size >> 9);
28 sector_t left = interval_end(node->rb_left);
33 sector_t right = interval_end(node->rb_right);
41 * drbd_insert_interval - insert a new interval into a tree
44 drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)
46 struct rb_node **new = &root->rb_node, *parent = NULL;
48 BUG_ON(!IS_ALIGNED(this->size, 512));
51 struct drbd_interval *here =
52 rb_entry(*new, struct drbd_interval, rb);
55 if (this->sector < here->sector)
56 new = &(*new)->rb_left;
57 else if (this->sector > here->sector)
58 new = &(*new)->rb_right;
60 new = &(*new)->rb_left;
62 new = &(*new)->rb_right;
67 rb_link_node(&this->rb, parent, new);
68 rb_insert_color(&this->rb, root);
69 rb_augment_insert(&this->rb, update_interval_end, NULL);
74 * drbd_contains_interval - check if a tree contains a given interval
75 * @sector: start sector of @interval
76 * @interval: may not be a valid pointer
78 * Returns if the tree contains the node @interval with start sector @start.
79 * Does not dereference @interval until @interval is known to be a valid object
80 * in @tree. Returns %false if @interval is in the tree but with a different
84 drbd_contains_interval(struct rb_root *root, sector_t sector,
85 struct drbd_interval *interval)
87 struct rb_node *node = root->rb_node;
90 struct drbd_interval *here =
91 rb_entry(node, struct drbd_interval, rb);
93 if (sector < here->sector)
95 else if (sector > here->sector)
96 node = node->rb_right;
97 else if (interval < here)
99 else if (interval > here)
100 node = node->rb_right;
108 * drbd_remove_interval - remove an interval from a tree
111 drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
113 struct rb_node *deepest;
115 deepest = rb_augment_erase_begin(&this->rb);
116 rb_erase(&this->rb, root);
117 rb_augment_erase_end(deepest, update_interval_end, NULL);
121 * drbd_find_overlap - search for an interval overlapping with [sector, sector + size)
122 * @sector: start sector
123 * @size: size, aligned to 512 bytes
125 * Returns an interval overlapping with [sector, sector + size), or NULL if
126 * there is none. When there is more than one overlapping interval in the
127 * tree, the interval with the lowest start sector is returned, and all other
128 * overlapping intervals will be on the right side of the tree, reachable with
131 struct drbd_interval *
132 drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
134 struct rb_node *node = root->rb_node;
135 struct drbd_interval *overlap = NULL;
136 sector_t end = sector + (size >> 9);
138 BUG_ON(!IS_ALIGNED(size, 512));
141 struct drbd_interval *here =
142 rb_entry(node, struct drbd_interval, rb);
145 sector < interval_end(node->rb_left)) {
146 /* Overlap if any must be on left side */
147 node = node->rb_left;
148 } else if (here->sector < end &&
149 sector < here->sector + (here->size >> 9)) {
152 } else if (sector >= here->sector) {
153 /* Overlap if any must be on right side */
154 node = node->rb_right;
161 struct drbd_interval *
162 drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size)
164 sector_t end = sector + (size >> 9);
165 struct rb_node *node;
168 node = rb_next(&i->rb);
171 i = rb_entry(node, struct drbd_interval, rb);
172 if (i->sector >= end)
174 if (sector < i->sector + (i->size >> 9))