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  * indexes that started at the original nodes[1]->start. nodes[1] is now the
24  * first node starting the next used span. A hole span is between nodes[0]->last
25  * and nodes[1]->start. nodes[1] must be !NULL.
30 	struct interval_tree_node *cur = state->nodes[1];  in interval_tree_span_iter_next_gap()
32 	state->nodes[0] = cur;  in interval_tree_span_iter_next_gap()
34 		if (cur->last > state->nodes[0]->last)  in interval_tree_span_iter_next_gap()
35 			state->nodes[0] = cur;  in interval_tree_span_iter_next_gap()
36 		cur = interval_tree_iter_next(cur, state->first_index,  in interval_tree_span_iter_next_gap()
37 					      state->last_index);  in interval_tree_span_iter_next_gap()
38 	} while (cur && (state->nodes[0]->last >= cur->start ||  in interval_tree_span_iter_next_gap()
39 			 state->nodes[0]->last + 1 == cur->start));  in interval_tree_span_iter_next_gap()
40 	state->nodes[1] = cur;  in interval_tree_span_iter_next_gap()
48 	iter->first_index = first_index;  in interval_tree_span_iter_first()
49 	iter->last_index = last_index;  in interval_tree_span_iter_first()
50 	iter->nodes[0] = NULL;  in interval_tree_span_iter_first()
51 	iter->nodes[1] =  in interval_tree_span_iter_first()
53 	if (!iter->nodes[1]) {  in interval_tree_span_iter_first()
55 		iter->start_hole = first_index;  in interval_tree_span_iter_first()
56 		iter->last_hole = last_index;  in interval_tree_span_iter_first()
57 		iter->is_hole = 1;  in interval_tree_span_iter_first()
60 	if (iter->nodes[1]->start > first_index) {  in interval_tree_span_iter_first()
62 		iter->start_hole = first_index;  in interval_tree_span_iter_first()
63 		iter->last_hole = iter->nodes[1]->start - 1;  in interval_tree_span_iter_first()
64 		iter->is_hole = 1;  in interval_tree_span_iter_first()
69 	/* Starting inside a used */  in interval_tree_span_iter_first()
70 	iter->start_used = first_index;  in interval_tree_span_iter_first()
71 	iter->is_hole = 0;  in interval_tree_span_iter_first()
73 	iter->last_used = iter->nodes[0]->last;  in interval_tree_span_iter_first()
74 	if (iter->last_used >= last_index) {  in interval_tree_span_iter_first()
75 		iter->last_used = last_index;  in interval_tree_span_iter_first()
76 		iter->nodes[0] = NULL;  in interval_tree_span_iter_first()
77 		iter->nodes[1] = NULL;  in interval_tree_span_iter_first()
84 	if (!iter->nodes[0] && !iter->nodes[1]) {  in interval_tree_span_iter_next()
85 		iter->is_hole = -1;  in interval_tree_span_iter_next()
89 	if (iter->is_hole) {  in interval_tree_span_iter_next()
90 		iter->start_used = iter->last_hole + 1;  in interval_tree_span_iter_next()
91 		iter->last_used = iter->nodes[0]->last;  in interval_tree_span_iter_next()
92 		if (iter->last_used >= iter->last_index) {  in interval_tree_span_iter_next()
93 			iter->last_used = iter->last_index;  in interval_tree_span_iter_next()
94 			iter->nodes[0] = NULL;  in interval_tree_span_iter_next()
95 			iter->nodes[1] = NULL;  in interval_tree_span_iter_next()
97 		iter->is_hole = 0;  in interval_tree_span_iter_next()
101 	if (!iter->nodes[1]) {  in interval_tree_span_iter_next()
103 		iter->start_hole = iter->nodes[0]->last + 1;  in interval_tree_span_iter_next()
104 		iter->last_hole = iter->last_index;  in interval_tree_span_iter_next()
105 		iter->nodes[0] = NULL;  in interval_tree_span_iter_next()
106 		iter->is_hole = 1;  in interval_tree_span_iter_next()
111 	iter->start_hole = iter->nodes[0]->last + 1;  in interval_tree_span_iter_next()
112 	iter->last_hole = iter->nodes[1]->start - 1;  in interval_tree_span_iter_next()
113 	iter->is_hole = 1;  in interval_tree_span_iter_next()
119  * Advance the iterator index to a specific position. The returned used/hole is
128 	if (iter->is_hole == -1)  in interval_tree_span_iter_advance()
131 	iter->first_index = new_index;  in interval_tree_span_iter_advance()
132 	if (new_index > iter->last_index) {  in interval_tree_span_iter_advance()
133 		iter->is_hole = -1;  in interval_tree_span_iter_advance()
137 	/* Rely on the union aliasing hole/used */  in interval_tree_span_iter_advance()
138 	if (iter->start_hole <= new_index && new_index <= iter->last_hole) {  in interval_tree_span_iter_advance()
139 		iter->start_hole = new_index;  in interval_tree_span_iter_advance()
142 	if (new_index == iter->last_hole + 1)  in interval_tree_span_iter_advance()
146 					      iter->last_index);  in interval_tree_span_iter_advance()