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