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 the interval overlapping with [sector, sector + size), or NULL.
126 * When there is more than one overlapping interval in the tree, the interval
127 * with the lowest start sector is returned.
129 struct drbd_interval *
130 drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
132 struct rb_node *node = root->rb_node;
133 struct drbd_interval *overlap = NULL;
134 sector_t end = sector + (size >> 9);
136 BUG_ON(!IS_ALIGNED(size, 512));
139 struct drbd_interval *here =
140 rb_entry(node, struct drbd_interval, rb);
143 sector < interval_end(node->rb_left)) {
144 /* Overlap if any must be on left side */
145 node = node->rb_left;
146 } else if (here->sector < end &&
147 sector < here->sector + (here->size >> 9)) {
150 } else if (sector >= here->sector) {
151 /* Overlap if any must be on right side */
152 node = node->rb_right;