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