drbd_interval.c revision 3e05146f0a9f28ef5959403eabf3239869476315 
1#include "drbd_interval.h"
2
3/**
4 * interval_end  -  return end of @node
5 */
6static inline
7sector_t interval_end(struct rb_node *node)
8{
9	struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
10	return this->end;
11}
12
13/**
14 * update_interval_end  -  recompute end of @node
15 *
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
18 * may have changed.
19 */
20static void
21update_interval_end(struct rb_node *node, void *__unused)
22{
23	struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
24	sector_t end;
25
26	end = this->sector + (this->size >> 9);
27	if (node->rb_left) {
28		sector_t left = interval_end(node->rb_left);
29		if (left > end)
30			end = left;
31	}
32	if (node->rb_right) {
33		sector_t right = interval_end(node->rb_right);
34		if (right > end)
35			end = right;
36	}
37	this->end = end;
38}
39
40/**
41 * drbd_insert_interval  -  insert a new interval into a tree
42 */
43bool
44drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)
45{
46	struct rb_node **new = &root->rb_node, *parent = NULL;
47
48	BUG_ON(!IS_ALIGNED(this->size, 512));
49
50	while (*new) {
51		struct drbd_interval *here =
52			rb_entry(*new, struct drbd_interval, rb);
53
54		parent = *new;
55		if (this->sector < here->sector)
56			new = &(*new)->rb_left;
57		else if (this->sector > here->sector)
58			new = &(*new)->rb_right;
59		else if (this < here)
60			new = &(*new)->rb_left;
61		else if (this > here)
62			new = &(*new)->rb_right;
63		else
64			return false;
65	}
66
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);
70	return true;
71}
72
73/**
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
77 *
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
81 * sector number.
82 */
83bool
84drbd_contains_interval(struct rb_root *root, sector_t sector,
85		       struct drbd_interval *interval)
86{
87	struct rb_node *node = root->rb_node;
88
89	while (node) {
90		struct drbd_interval *here =
91			rb_entry(node, struct drbd_interval, rb);
92
93		if (sector < here->sector)
94			node = node->rb_left;
95		else if (sector > here->sector)
96			node = node->rb_right;
97		else if (interval < here)
98			node = node->rb_left;
99		else if (interval > here)
100			node = node->rb_right;
101		else
102			return true;
103	}
104	return false;
105}
106
107/**
108 * drbd_remove_interval  -  remove an interval from a tree
109 */
110void
111drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
112{
113	struct rb_node *deepest;
114
115	deepest = rb_augment_erase_begin(&this->rb);
116	rb_erase(&this->rb, root);
117	rb_augment_erase_end(deepest, update_interval_end, NULL);
118}
119
120/**
121 * drbd_find_overlap  - search for an interval overlapping with [sector, sector + size)
122 * @sector:	start sector
123 * @size:	size, aligned to 512 bytes
124 *
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.
128 */
129struct drbd_interval *
130drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
131{
132	struct rb_node *node = root->rb_node;
133	struct drbd_interval *overlap = NULL;
134	sector_t end = sector + (size >> 9);
135
136	BUG_ON(!IS_ALIGNED(size, 512));
137
138	while (node) {
139		struct drbd_interval *here =
140			rb_entry(node, struct drbd_interval, rb);
141
142		if (node->rb_left &&
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)) {
148			overlap = here;
149			break;
150		} else if (sector >= here->sector) {
151			/* Overlap if any must be on right side */
152			node = node->rb_right;
153		} else
154			break;
155	}
156	return overlap;
157}
158