1 // SPDX-License-Identifier: GPL-2.0-only
7  * interval_end  -  return end of @node
10 sector_t interval_end(struct rb_node *node)  in interval_end()  argument
12 	struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);  in interval_end()
13 	return this->end;  in interval_end()
16 #define NODE_END(node) ((node)->sector + ((node)->size >> 9))  argument
22  * drbd_insert_interval  -  insert a new interval into a tree
25 drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)  in drbd_insert_interval()  argument
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
59  * @root:	red black tree root
63  * Returns if the tree contains the node @interval with start sector @start.
69 drbd_contains_interval(struct rb_root *root, sector_t sector,  in drbd_contains_interval()  argument
72 	struct rb_node *node = root->rb_node;  in drbd_contains_interval()  local
74 	while (node) {  in drbd_contains_interval()
76 			rb_entry(node, struct drbd_interval, rb);  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
96 drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)  in drbd_remove_interval()  argument
102 	rb_erase_augmented(&this->rb, root, &augment_callbacks);  in drbd_remove_interval()
106  * drbd_find_overlap  - search for an interval overlapping with [sector, sector + size)
107  * @root:	red black tree root
118 drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)  in drbd_find_overlap()  argument
120 	struct rb_node *node = root->rb_node;  in drbd_find_overlap()  local
126 	while (node) {  in drbd_find_overlap()
128 			rb_entry(node, struct drbd_interval, rb);  in drbd_find_overlap()
130 		if (node->rb_left &&  in drbd_find_overlap()
131 		    sector < interval_end(node->rb_left)) {  in drbd_find_overlap()
133 			node = node->rb_left;  in drbd_find_overlap()
134 		} else if (here->sector < end &&  in drbd_find_overlap()
135 			   sector < here->sector + (here->size >> 9)) {  in drbd_find_overlap()
138 		} else if (sector >= here->sector) {  in drbd_find_overlap()
140 			node = node->rb_right;  in drbd_find_overlap()
151 	struct rb_node *node;  in drbd_next_overlap()  local
154 		node = rb_next(&i->rb);  in drbd_next_overlap()
155 		if (!node)  in drbd_next_overlap()
157 		i = rb_entry(node, struct drbd_interval, rb);  in drbd_next_overlap()
158 		if (i->sector >= end)  in drbd_next_overlap()
160 		if (sector < i->sector + (i->size >> 9))  in drbd_next_overlap()