1 /* SPDX-License-Identifier: GPL-2.0-or-later */
5 * Derived from include/linux/interval_tree.h and its dependencies.
8 #ifndef QEMU_INTERVAL_TREE_H
9 #define QEMU_INTERVAL_TREE_H
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.
18 /* Encodes parent with color in the lsb. */
19 uintptr_t rb_parent_color;
20 struct RBNode *rb_right;
21 struct RBNode *rb_left;
29 typedef struct RBRootLeftCached {
34 typedef struct IntervalTreeNode
38 uint64_t start; /* Start of interval */
39 uint64_t last; /* Last location _in_ interval */
40 uint64_t subtree_last;
43 typedef RBRootLeftCached IntervalTreeRoot;
46 * interval_tree_is_empty
47 * @root: root of the tree.
49 * Returns true if the tree contains no nodes.
51 static inline bool interval_tree_is_empty(const IntervalTreeRoot *root)
53 return root->rb_root.rb_node == NULL;
57 * interval_tree_insert
58 * @node: node to insert,
59 * @root: root of the tree.
61 * Insert @node into @root, and rebalance.
63 void interval_tree_insert(IntervalTreeNode *node, IntervalTreeRoot *root);
66 * interval_tree_remove
67 * @node: node to remove,
68 * @root: root of the tree.
70 * Remove @node from @root, and rebalance.
72 void interval_tree_remove(IntervalTreeNode *node, IntervalTreeRoot *root);
75 * interval_tree_iter_first:
76 * @root: root of the tree,
77 * @start, @last: the inclusive interval [start, last].
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.
83 IntervalTreeNode *interval_tree_iter_first(IntervalTreeRoot *root,
84 uint64_t start, uint64_t last);
87 * interval_tree_iter_next:
88 * @node: previous search result
89 * @start, @last: the inclusive interval [start, last].
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
96 IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node,
97 uint64_t start, uint64_t last);
99 #endif /* QEMU_INTERVAL_TREE_H */