Commit | Line | Data |
---|---|---|
b2441318 | 1 | /* SPDX-License-Identifier: GPL-2.0 */ |
fff3fd8a ML |
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 | |
f808c13f DB |
15 | interval_tree_insert(struct interval_tree_node *node, |
16 | struct rb_root_cached *root); | |
fff3fd8a ML |
17 | |
18 | extern void | |
f808c13f DB |
19 | interval_tree_remove(struct interval_tree_node *node, |
20 | struct rb_root_cached *root); | |
fff3fd8a ML |
21 | |
22 | extern struct interval_tree_node * | |
f808c13f | 23 | interval_tree_iter_first(struct rb_root_cached *root, |
fff3fd8a ML |
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 | ||
5fe93786 JG |
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 | ||
fff3fd8a | 88 | #endif /* _LINUX_INTERVAL_TREE_H */ |