1 | /* SPDX-License-Identifier: GPL-2.0 */ |
2 | #ifndef _LINUX_INTERVAL_TREE_H |
3 | #define _LINUX_INTERVAL_TREE_H |
4 | |
5 | #include <linux/rbtree.h> |
6 | |
7 | struct interval_tree_node { |
8 | struct rb_node rb; |
9 | unsigned long start; /* Start of interval */ |
10 | unsigned long last; /* Last location _in_ interval */ |
11 | unsigned long __subtree_last; |
12 | }; |
13 | |
14 | extern void |
15 | interval_tree_insert(struct interval_tree_node *node, |
16 | struct rb_root_cached *root); |
17 | |
18 | extern void |
19 | interval_tree_remove(struct interval_tree_node *node, |
20 | struct rb_root_cached *root); |
21 | |
22 | extern struct interval_tree_node * |
23 | interval_tree_iter_first(struct rb_root_cached *root, |
24 | unsigned long start, unsigned long last); |
25 | |
26 | extern struct interval_tree_node * |
27 | interval_tree_iter_next(struct interval_tree_node *node, |
28 | unsigned long start, unsigned long last); |
29 | |
30 | /** |
31 | * struct interval_tree_span_iter - Find used and unused spans. |
32 | * @start_hole: Start of an interval for a hole when is_hole == 1 |
33 | * @last_hole: Inclusive end of an interval for a hole when is_hole == 1 |
34 | * @start_used: Start of a used interval when is_hole == 0 |
35 | * @last_used: Inclusive end of a used interval when is_hole == 0 |
36 | * @is_hole: 0 == used, 1 == is_hole, -1 == done iteration |
37 | * |
38 | * This iterator travels over spans in an interval tree. It does not return |
39 | * nodes but classifies each span as either a hole, where no nodes intersect, or |
40 | * a used, which is fully covered by nodes. Each iteration step toggles between |
41 | * hole and used until the entire range is covered. The returned spans always |
42 | * fully cover the requested range. |
43 | * |
44 | * The iterator is greedy, it always returns the largest hole or used possible, |
45 | * consolidating all consecutive nodes. |
46 | * |
47 | * Use interval_tree_span_iter_done() to detect end of iteration. |
48 | */ |
49 | struct interval_tree_span_iter { |
50 | /* private: not for use by the caller */ |
51 | struct interval_tree_node *nodes[2]; |
52 | unsigned long first_index; |
53 | unsigned long last_index; |
54 | |
55 | /* public: */ |
56 | union { |
57 | unsigned long start_hole; |
58 | unsigned long start_used; |
59 | }; |
60 | union { |
61 | unsigned long last_hole; |
62 | unsigned long last_used; |
63 | }; |
64 | int is_hole; |
65 | }; |
66 | |
67 | void interval_tree_span_iter_first(struct interval_tree_span_iter *state, |
68 | struct rb_root_cached *itree, |
69 | unsigned long first_index, |
70 | unsigned long last_index); |
71 | void interval_tree_span_iter_advance(struct interval_tree_span_iter *iter, |
72 | struct rb_root_cached *itree, |
73 | unsigned long new_index); |
74 | void interval_tree_span_iter_next(struct interval_tree_span_iter *state); |
75 | |
76 | static inline bool |
77 | interval_tree_span_iter_done(struct interval_tree_span_iter *state) |
78 | { |
79 | return state->is_hole == -1; |
80 | } |
81 | |
82 | #define interval_tree_for_each_span(span, itree, first_index, last_index) \ |
83 | for (interval_tree_span_iter_first(span, itree, \ |
84 | first_index, last_index); \ |
85 | !interval_tree_span_iter_done(span); \ |
86 | interval_tree_span_iter_next(span)) |
87 | |
88 | #endif /* _LINUX_INTERVAL_TREE_H */ |
89 | |