include/qemu/interval-tree.h

   1 /* SPDX-License-Identifier: GPL-2.0-or-later */
   2 /*
   3  * Interval trees.
   4  *
   5  * Derived from include/linux/interval_tree.h and its dependencies.
   6  */
   7
   8 #ifndef QEMU_INTERVAL_TREE_H
   9 #define QEMU_INTERVAL_TREE_H
  10
  11 /*
  12  * For now, don't expose Linux Red-Black Trees separately, but retain the
  13  * separate type definitions to keep the implementation sane, and allow
  14  * the possibility of disentangling them later.
  15  */
  16 typedef struct RBNode
  17 {
  18     /* Encodes parent with color in the lsb. */
  19     uintptr_t rb_parent_color;
  20     struct RBNode *rb_right;
  21     struct RBNode *rb_left;
  22 } RBNode;
  23
  24 typedef struct RBRoot
  25 {
  26     RBNode *rb_node;
  27 } RBRoot;
  28
  29 typedef struct RBRootLeftCached {
  30     RBRoot rb_root;
  31     RBNode *rb_leftmost;
  32 } RBRootLeftCached;
  33
  34 typedef struct IntervalTreeNode
  35 {
  36     RBNode rb;
  37
  38     uint64_t start;    /* Start of interval */
  39     uint64_t last;     /* Last location _in_ interval */
  40     uint64_t subtree_last;
  41 } IntervalTreeNode;
  42
  43 typedef RBRootLeftCached IntervalTreeRoot;
  44
  45 /**
  46  * interval_tree_is_empty
  47  * @root: root of the tree.
  48  *
  49  * Returns true if the tree contains no nodes.
  50  */
  51 static inline bool interval_tree_is_empty(const IntervalTreeRoot *root)
  52 {
  53     return root->rb_root.rb_node == NULL;
  54 }
  55
  56 /**
  57  * interval_tree_insert
  58  * @node: node to insert,
  59  * @root: root of the tree.
  60  *
  61  * Insert @node into @root, and rebalance.
  62  */
  63 void interval_tree_insert(IntervalTreeNode *node, IntervalTreeRoot *root);
  64
  65 /**
  66  * interval_tree_remove
  67  * @node: node to remove,
  68  * @root: root of the tree.
  69  *
  70  * Remove @node from @root, and rebalance.
  71  */
  72 void interval_tree_remove(IntervalTreeNode *node, IntervalTreeRoot *root);
  73
  74 /**
  75  * interval_tree_iter_first:
  76  * @root: root of the tree,
  77  * @start, @last: the inclusive interval [start, last].
  78  *
  79  * Locate the "first" of a set of nodes within the tree at @root
  80  * that overlap the interval, where "first" is sorted by start.
  81  * Returns NULL if no overlap found.
  82  */
  83 IntervalTreeNode *interval_tree_iter_first(IntervalTreeRoot *root,
  84                                            uint64_t start, uint64_t last);
  85
  86 /**
  87  * interval_tree_iter_next:
  88  * @node: previous search result
  89  * @start, @last: the inclusive interval [start, last].
  90  *
  91  * Locate the "next" of a set of nodes within the tree that overlap the
  92  * interval; @next is the result of a previous call to
  93  * interval_tree_iter_{first,next}.  Returns NULL if @next was the last
  94  * node in the set.
  95  */
  96 IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node,
  97                                           uint64_t start, uint64_t last);
  98
  99 #endif /* QEMU_INTERVAL_TREE_H */