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 |
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 | |