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