1 // SPDX-License-Identifier: GPL-2.0-only
19 __param(int, nsearches, 100, "Number of searches to the interval tree");
57 	 * Limit the search scope to what the user defined.  in init()
67 	int i, j;  in basic_check()  local
77 		for (j = 0; j < nnodes; j++)  in basic_check()
78 			interval_tree_insert(nodes + j, &root);  in basic_check()
79 		for (j = 0; j < nnodes; j++)  in basic_check()
80 			interval_tree_remove(nodes + j, &root);  in basic_check()
84 	time = time2 - time1;  in basic_check()
87 	printk(" -> %llu cycles\n", (unsigned long long)time);  in basic_check()
94 	int i, j;  in search_check()  local
102 	for (j = 0; j < nnodes; j++)  in search_check()
103 		interval_tree_insert(nodes + j, &root);  in search_check()
109 		for (j = 0; j < nsearches; j++) {  in search_check()
110 			unsigned long start = search_all ? 0 : queries[j];  in search_check()
111 			unsigned long last = search_all ? max_endpoint : queries[j];  in search_check()
117 	time = time2 - time1;  in search_check()
121 	printk(" -> %llu cycles (%lu results)\n",  in search_check()
124 	for (j = 0; j < nnodes; j++)  in search_check()
125 		interval_tree_remove(nodes + j, &root);  in search_check()
132 	int i, j, k;  in intersection_range_check()  local
142 		WARN_ON_ONCE("Failed to allocate intxn1\n");  in intersection_range_check()
143 		return -ENOMEM;  in intersection_range_check()
148 		WARN_ON_ONCE("Failed to allocate intxn2\n");  in intersection_range_check()
150 		return -ENOMEM;  in intersection_range_check()
156 		for (j = 0; j < nnodes; j++)  in intersection_range_check()
157 			interval_tree_insert(nodes + j, &root);  in intersection_range_check()
160 		for (k = 0; k < nsearches; k++) {  in intersection_range_check()
162 			if (!k) {  in intersection_range_check()
170 			/* Walk nodes to mark intersection nodes */  in intersection_range_check()
172 			for (j = 0; j < nnodes; j++) {  in intersection_range_check()
173 				node = nodes + j;  in intersection_range_check()
175 				if (start <= node->last && last >= node->start)  in intersection_range_check()
176 					bitmap_set(intxn1, j, 1);  in intersection_range_check()
179 			/* Iterate tree to clear intersection nodes */  in intersection_range_check()
183 				bitmap_set(intxn2, node - nodes, 1);  in intersection_range_check()
188 		for (j = 0; j < nnodes; j++)  in intersection_range_check()
189 			interval_tree_remove(nodes + j, &root);  in intersection_range_check()
199  * Helper function to get span of current position from maple tree point of
208 	if (mas->status == ma_overflow)  in mas_cur_span()
211 	/* walk to current position */  in mas_cur_span()
212 	state->is_hole = mas_walk(mas) ? 0 : 1;  in mas_cur_span()
214 	cur_start = mas->index < state->first_index ?  in mas_cur_span()
215 			state->first_index : mas->index;  in mas_cur_span()
220 		cur_last = mas->last > state->last_index ?  in mas_cur_span()
221 				state->last_index : mas->last;  in mas_cur_span()
223 		is_hole = mas_next_range(mas, state->last_index) ? 0 : 1;  in mas_cur_span()
225 	} while (mas->status != ma_overflow && is_hole == state->is_hole);  in mas_cur_span()
227 	if (state->is_hole) {  in mas_cur_span()
228 		state->start_hole = cur_start;  in mas_cur_span()
229 		state->last_hole = cur_last;  in mas_cur_span()
231 		state->start_used = cur_start;  in mas_cur_span()
232 		state->last_used = cur_last;  in mas_cur_span()
236 	if (mas->status != ma_overflow)  in mas_cur_span()
242 	int i, j, k;  in span_iteration_check()  local
255 		for (j = 0; j < nnodes; j++)  in span_iteration_check()
256 			interval_tree_insert(nodes + j, &root);  in span_iteration_check()
262 		for (j = 0; j < nnodes; j++)  in span_iteration_check()
263 			WARN_ON_ONCE(mtree_store_range(&tree, nodes[j].start,  in span_iteration_check()
264 					nodes[j].last, nodes + j, GFP_KERNEL));  in span_iteration_check()
267 		for (k = 0; k < nsearches; k++) {  in span_iteration_check()
269 			if (!k) {  in span_iteration_check()
279 			mas_span.is_hole = -1;  in span_iteration_check()
303 		for (j = 0; j < nnodes; j++)  in span_iteration_check()
304 			interval_tree_remove(nodes + j, &root);  in span_iteration_check()
317 		return -ENOMEM;  in interval_tree_test_init()
322 		return -ENOMEM;  in interval_tree_test_init()
335 	return -EAGAIN; /* Fail will directly unload the module */  in interval_tree_test_init()