[mirror_qemu.git] / include / qemu / interval-tree.h

/* SPDX-License-Identifier: GPL-2.0-or-later */
/*
 * Interval trees.
 *
 * Derived from include/linux/interval_tree.h and its dependencies.
 */

#ifndef QEMU_INTERVAL_TREE_H
#define QEMU_INTERVAL_TREE_H

/*
 * For now, don't expose Linux Red-Black Trees separately, but retain the
 * separate type definitions to keep the implementation sane, and allow
 * the possibility of disentangling them later.
 */
typedef struct RBNode
{
    /* Encodes parent with color in the lsb. */
    uintptr_t rb_parent_color;
    struct RBNode *rb_right;
    struct RBNode *rb_left;
} RBNode;

typedef struct RBRoot
{
    RBNode *rb_node;
} RBRoot;

typedef struct RBRootLeftCached {
    RBRoot rb_root;
    RBNode *rb_leftmost;
} RBRootLeftCached;

typedef struct IntervalTreeNode
{
    RBNode rb;

    uint64_t start;    /* Start of interval */
    uint64_t last;     /* Last location _in_ interval */
    uint64_t subtree_last;
} IntervalTreeNode;

typedef RBRootLeftCached IntervalTreeRoot;

/**
 * interval_tree_is_empty
 * @root: root of the tree.
 *
 * Returns true if the tree contains no nodes.
 */
static inline bool interval_tree_is_empty(const IntervalTreeRoot *root)
{
    return root->rb_root.rb_node == NULL;
}

/**
 * interval_tree_insert
 * @node: node to insert,
 * @root: root of the tree.
 *
 * Insert @node into @root, and rebalance.
 */
void interval_tree_insert(IntervalTreeNode *node, IntervalTreeRoot *root);

/**
 * interval_tree_remove
 * @node: node to remove,
 * @root: root of the tree.
 *
 * Remove @node from @root, and rebalance.
 */
void interval_tree_remove(IntervalTreeNode *node, IntervalTreeRoot *root);

/**
 * interval_tree_iter_first:
 * @root: root of the tree,
 * @start, @last: the inclusive interval [start, last].
 *
 * Locate the "first" of a set of nodes within the tree at @root
 * that overlap the interval, where "first" is sorted by start.
 * Returns NULL if no overlap found.
 */
IntervalTreeNode *interval_tree_iter_first(IntervalTreeRoot *root,
                                           uint64_t start, uint64_t last);

/**
 * interval_tree_iter_next:
 * @node: previous search result
 * @start, @last: the inclusive interval [start, last].
 *
 * Locate the "next" of a set of nodes within the tree that overlap the
 * interval; @next is the result of a previous call to
 * interval_tree_iter_{first,next}.  Returns NULL if @next was the last
 * node in the set.
 */
IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node,
                                          uint64_t start, uint64_t last);

#endif /* QEMU_INTERVAL_TREE_H */
Commit	Line	Data
0d99d37a RH	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 */