include/linux/interval_tree.h

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