drivers/iommu/iommufd/double_span.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 /* Copyright (c) 2022, NVIDIA CORPORATION & AFFILIATES.
   3  */
   4 #ifndef __IOMMUFD_DOUBLE_SPAN_H
   5 #define __IOMMUFD_DOUBLE_SPAN_H
   6
   7 #include <linux/interval_tree.h>
   8
   9 /*
  10  * This is a variation of the general interval_tree_span_iter that computes the
  11  * spans over the union of two different interval trees. Used ranges are broken
  12  * up and reported based on the tree that provides the interval. The first span
  13  * always takes priority. Like interval_tree_span_iter it is greedy and the same
  14  * value of is_used will not repeat on two iteration cycles.
  15  */
  16 struct interval_tree_double_span_iter {
  17         struct rb_root_cached *itrees[2];
  18         struct interval_tree_span_iter spans[2];
  19         union {
  20                 unsigned long start_hole;
  21                 unsigned long start_used;
  22         };
  23         union {
  24                 unsigned long last_hole;
  25                 unsigned long last_used;
  26         };
  27         /* 0 = hole, 1 = used span[0], 2 = used span[1], -1 done iteration */
  28         int is_used;
  29 };
  30
  31 void interval_tree_double_span_iter_update(
  32         struct interval_tree_double_span_iter *iter);
  33 void interval_tree_double_span_iter_first(
  34         struct interval_tree_double_span_iter *iter,
  35         struct rb_root_cached *itree1, struct rb_root_cached *itree2,
  36         unsigned long first_index, unsigned long last_index);
  37 void interval_tree_double_span_iter_next(
  38         struct interval_tree_double_span_iter *iter);
  39
  40 static inline bool
  41 interval_tree_double_span_iter_done(struct interval_tree_double_span_iter *state)
  42 {
  43         return state->is_used == -1;
  44 }
  45
  46 #define interval_tree_for_each_double_span(span, itree1, itree2, first_index, \
  47                                            last_index)                        \
  48         for (interval_tree_double_span_iter_first(span, itree1, itree2,       \
  49                                                   first_index, last_index);   \
  50              !interval_tree_double_span_iter_done(span);                      \
  51              interval_tree_double_span_iter_next(span))
  52
  53 #endif