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