1 // SPDX-License-Identifier: GPL-2.0
7  * interval_end  -  return end of @node
13 	return this->end;  in interval_end()
16 #define NODE_END(node) ((node)->sector + ((node)->size >> 9))
22  * drbd_insert_interval  -  insert a new interval into a tree
27 	struct rb_node **new = &root->rb_node, *parent = NULL;  in drbd_insert_interval()
28 	sector_t this_end = this->sector + (this->size >> 9);  in drbd_insert_interval()
30 	BUG_ON(!IS_ALIGNED(this->size, 512));  in drbd_insert_interval()
37 		if (here->end < this_end)  in drbd_insert_interval()
38 			here->end = this_end;  in drbd_insert_interval()
39 		if (this->sector < here->sector)  in drbd_insert_interval()
40 			new = &(*new)->rb_left;  in drbd_insert_interval()
41 		else if (this->sector > here->sector)  in drbd_insert_interval()
42 			new = &(*new)->rb_right;  in drbd_insert_interval()
44 			new = &(*new)->rb_left;  in drbd_insert_interval()
46 			new = &(*new)->rb_right;  in drbd_insert_interval()
51 	this->end = this_end;  in drbd_insert_interval()
52 	rb_link_node(&this->rb, parent, new);  in drbd_insert_interval()
53 	rb_insert_augmented(&this->rb, root, &augment_callbacks);  in drbd_insert_interval()
58  * drbd_contains_interval  -  check if a tree contains a given interval
72 	struct rb_node *node = root->rb_node;  in drbd_contains_interval()
78 		if (sector < here->sector)  in drbd_contains_interval()
79 			node = node->rb_left;  in drbd_contains_interval()
80 		else if (sector > here->sector)  in drbd_contains_interval()
81 			node = node->rb_right;  in drbd_contains_interval()
83 			node = node->rb_left;  in drbd_contains_interval()
85 			node = node->rb_right;  in drbd_contains_interval()
93  * drbd_remove_interval  -  remove an interval from a tree
98 	rb_erase_augmented(&this->rb, root, &augment_callbacks);  in drbd_remove_interval()
102  * drbd_find_overlap  - search for an interval overlapping with [sector, sector + size)
105  * @size:	size, aligned to 512 bytes
110  * overlapping intervals will be on the right side of the tree, reachable with
116 	struct rb_node *node = root->rb_node;  in drbd_find_overlap()
126 		if (node->rb_left &&  in drbd_find_overlap()
127 		    sector < interval_end(node->rb_left)) {  in drbd_find_overlap()
129 			node = node->rb_left;  in drbd_find_overlap()
130 		} else if (here->sector < end &&  in drbd_find_overlap()
131 			   sector < here->sector + (here->size >> 9)) {  in drbd_find_overlap()
134 		} else if (sector >= here->sector) {  in drbd_find_overlap()
135 			/* Overlap if any must be on right side */  in drbd_find_overlap()
136 			node = node->rb_right;  in drbd_find_overlap()
150 		node = rb_next(&i->rb);  in drbd_next_overlap()
154 		if (i->sector >= end)  in drbd_next_overlap()
156 		if (sector < i->sector + (i->size >> 9))  in drbd_next_overlap()