1 /* SPDX-License-Identifier: GPL-2.0 */
2 /* Copyright (c) 2022, NVIDIA CORPORATION & AFFILIATES.
3 */
4 #ifndef __IOMMUFD_DOUBLE_SPAN_H
5 #define __IOMMUFD_DOUBLE_SPAN_H
6
7 #include <linux/interval_tree.h>
8
9 /*
10 * This is a variation of the general interval_tree_span_iter that computes the
11 * spans over the union of two different interval trees. Used ranges are broken
12 * up and reported based on the tree that provides the interval. The first span
13 * always takes priority. Like interval_tree_span_iter it is greedy and the same
14 * value of is_used will not repeat on two iteration cycles.
15 */
16 struct interval_tree_double_span_iter {
17 struct rb_root_cached *itrees[2];
18 struct interval_tree_span_iter spans[2];
19 union {
20 unsigned long start_hole;
21 unsigned long start_used;
22 };
23 union {
24 unsigned long last_hole;
25 unsigned long last_used;
26 };
27 /* 0 = hole, 1 = used span[0], 2 = used span[1], -1 done iteration */
28 int is_used;
29 };
30
31 void interval_tree_double_span_iter_update(
32 struct interval_tree_double_span_iter *iter);
33 void interval_tree_double_span_iter_first(
34 struct interval_tree_double_span_iter *iter,
35 struct rb_root_cached *itree1, struct rb_root_cached *itree2,
36 unsigned long first_index, unsigned long last_index);
37 void interval_tree_double_span_iter_next(
38 struct interval_tree_double_span_iter *iter);
39
40 static inline bool
interval_tree_double_span_iter_done(struct interval_tree_double_span_iter * state)41 interval_tree_double_span_iter_done(struct interval_tree_double_span_iter *state)
42 {
43 return state->is_used == -1;
44 }
45
46 #define interval_tree_for_each_double_span(span, itree1, itree2, first_index, \
47 last_index) \
48 for (interval_tree_double_span_iter_first(span, itree1, itree2, \
49 first_index, last_index); \
50 !interval_tree_double_span_iter_done(span); \
51 interval_tree_double_span_iter_next(span))
52
53 #endif
54