1 // SPDX-License-Identifier: GPL-2.0-only
7 #define START(node) ((node)->start)
8 #define LAST(node)  ((node)->last)  macro
12 		     START, LAST,, interval_tree)
22  * span of nodes. This makes nodes[0]->last the end of that contiguous used span
23  * of indexes that started at the original nodes[1]->start.
26  * next used span. A hole span is between nodes[0]->last and nodes[1]->start.
29  * nodes[0]->last and last_index.
31  * If the contiguous used range span to last_index, nodes[1] is set to NULL.
36 	struct interval_tree_node *cur = state->nodes[1];  in interval_tree_span_iter_next_gap()
38 	state->nodes[0] = cur;  in interval_tree_span_iter_next_gap()
40 		if (cur->last > state->nodes[0]->last)  in interval_tree_span_iter_next_gap()
41 			state->nodes[0] = cur;  in interval_tree_span_iter_next_gap()
42 		cur = interval_tree_iter_next(cur, state->first_index,  in interval_tree_span_iter_next_gap()
43 					      state->last_index);  in interval_tree_span_iter_next_gap()
44 	} while (cur && (state->nodes[0]->last >= cur->start ||  in interval_tree_span_iter_next_gap()
45 			 state->nodes[0]->last + 1 == cur->start));  in interval_tree_span_iter_next_gap()
46 	state->nodes[1] = cur;  in interval_tree_span_iter_next_gap()
54 	iter->first_index = first_index;  in interval_tree_span_iter_first()
55 	iter->last_index = last_index;  in interval_tree_span_iter_first()
56 	iter->nodes[0] = NULL;  in interval_tree_span_iter_first()
57 	iter->nodes[1] =  in interval_tree_span_iter_first()
59 	if (!iter->nodes[1]) {  in interval_tree_span_iter_first()
61 		iter->start_hole = first_index;  in interval_tree_span_iter_first()
62 		iter->last_hole = last_index;  in interval_tree_span_iter_first()
63 		iter->is_hole = 1;  in interval_tree_span_iter_first()
66 	if (iter->nodes[1]->start > first_index) {  in interval_tree_span_iter_first()
68 		iter->start_hole = first_index;  in interval_tree_span_iter_first()
69 		iter->last_hole = iter->nodes[1]->start - 1;  in interval_tree_span_iter_first()
70 		iter->is_hole = 1;  in interval_tree_span_iter_first()
75 	/* Starting inside a used */  in interval_tree_span_iter_first()
76 	iter->start_used = first_index;  in interval_tree_span_iter_first()
77 	iter->is_hole = 0;  in interval_tree_span_iter_first()
79 	iter->last_used = iter->nodes[0]->last;  in interval_tree_span_iter_first()
80 	if (iter->last_used >= last_index) {  in interval_tree_span_iter_first()
81 		iter->last_used = last_index;  in interval_tree_span_iter_first()
82 		iter->nodes[0] = NULL;  in interval_tree_span_iter_first()
83 		iter->nodes[1] = NULL;  in interval_tree_span_iter_first()
90 	if (!iter->nodes[0] && !iter->nodes[1]) {  in interval_tree_span_iter_next()
91 		iter->is_hole = -1;  in interval_tree_span_iter_next()
95 	if (iter->is_hole) {  in interval_tree_span_iter_next()
96 		iter->start_used = iter->last_hole + 1;  in interval_tree_span_iter_next()
97 		iter->last_used = iter->nodes[0]->last;  in interval_tree_span_iter_next()
98 		if (iter->last_used >= iter->last_index) {  in interval_tree_span_iter_next()
99 			iter->last_used = iter->last_index;  in interval_tree_span_iter_next()
100 			iter->nodes[0] = NULL;  in interval_tree_span_iter_next()
101 			iter->nodes[1] = NULL;  in interval_tree_span_iter_next()
103 		iter->is_hole = 0;  in interval_tree_span_iter_next()
107 	if (!iter->nodes[1]) {  in interval_tree_span_iter_next()
109 		iter->start_hole = iter->nodes[0]->last + 1;  in interval_tree_span_iter_next()
110 		iter->last_hole = iter->last_index;  in interval_tree_span_iter_next()
111 		iter->nodes[0] = NULL;  in interval_tree_span_iter_next()
112 		iter->is_hole = 1;  in interval_tree_span_iter_next()
117 	iter->start_hole = iter->nodes[0]->last + 1;  in interval_tree_span_iter_next()
118 	iter->last_hole = iter->nodes[1]->start - 1;  in interval_tree_span_iter_next()
119 	iter->is_hole = 1;  in interval_tree_span_iter_next()
125  * Advance the iterator index to a specific position. The returned used/hole is
134 	if (iter->is_hole == -1)  in interval_tree_span_iter_advance()
137 	iter->first_index = new_index;  in interval_tree_span_iter_advance()
138 	if (new_index > iter->last_index) {  in interval_tree_span_iter_advance()
139 		iter->is_hole = -1;  in interval_tree_span_iter_advance()
143 	/* Rely on the union aliasing hole/used */  in interval_tree_span_iter_advance()
144 	if (iter->start_hole <= new_index && new_index <= iter->last_hole) {  in interval_tree_span_iter_advance()
145 		iter->start_hole = new_index;  in interval_tree_span_iter_advance()
148 	if (new_index == iter->last_hole + 1)  in interval_tree_span_iter_advance()
152 					      iter->last_index);  in interval_tree_span_iter_advance()