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
interval_tree_span_iter_done(struct interval_tree_span_iter * state)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