1 // SPDX-License-Identifier: GPL-2.0-only 2 #include <linux/interval_tree.h> 3 #include <linux/interval_tree_generic.h> 4 #include <linux/compiler.h> 5 #include <linux/export.h> 6 7 #define START(node) ((node)->start) 8 #define LAST(node) ((node)->last) 9 10 INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, 11 unsigned long, __subtree_last, 12 START, LAST,, interval_tree) 13 14 EXPORT_SYMBOL_GPL(interval_tree_insert); 15 EXPORT_SYMBOL_GPL(interval_tree_remove); 16 EXPORT_SYMBOL_GPL(interval_tree_iter_first); 17 EXPORT_SYMBOL_GPL(interval_tree_iter_next); 18 19 #ifdef CONFIG_INTERVAL_TREE_SPAN_ITER 20 /* 21 * Roll nodes[1] into nodes[0] by advancing nodes[1] to the end of a contiguous 22 * span of nodes. This makes nodes[0]->last the end of that contiguous used span 23 * of indexes that started at the original nodes[1]->start. 24 * 25 * If there is an interior hole, nodes[1] is now the first node starting the 26 * next used span. A hole span is between nodes[0]->last and nodes[1]->start. 27 * 28 * If there is a tailing hole, nodes[1] is now NULL. A hole span is between 29 * nodes[0]->last and last_index. 30 * 31 * If the contiguous used range span to last_index, nodes[1] is set to NULL. 32 */ 33 static void 34 interval_tree_span_iter_next_gap(struct interval_tree_span_iter *state) 35 { 36 struct interval_tree_node *cur = state->nodes[1]; 37 38 state->nodes[0] = cur; 39 do { 40 if (cur->last > state->nodes[0]->last) 41 state->nodes[0] = cur; 42 cur = interval_tree_iter_next(cur, state->first_index, 43 state->last_index); 44 } while (cur && (state->nodes[0]->last >= cur->start || 45 state->nodes[0]->last + 1 == cur->start)); 46 state->nodes[1] = cur; 47 } 48 49 void interval_tree_span_iter_first(struct interval_tree_span_iter *iter, 50 struct rb_root_cached *itree, 51 unsigned long first_index, 52 unsigned long last_index) 53 { 54 iter->first_index = first_index; 55 iter->last_index = last_index; 56 iter->nodes[0] = NULL; 57 iter->nodes[1] = 58 interval_tree_iter_first(itree, first_index, last_index); 59 if (!iter->nodes[1]) { 60 /* No nodes intersect the span, whole span is hole */ 61 iter->start_hole = first_index; 62 iter->last_hole = last_index; 63 iter->is_hole = 1; 64 return; 65 } 66 if (iter->nodes[1]->start > first_index) { 67 /* Leading hole on first iteration */ 68 iter->start_hole = first_index; 69 iter->last_hole = iter->nodes[1]->start - 1; 70 iter->is_hole = 1; 71 interval_tree_span_iter_next_gap(iter); 72 return; 73 } 74 75 /* Starting inside a used */ 76 iter->start_used = first_index; 77 iter->is_hole = 0; 78 interval_tree_span_iter_next_gap(iter); 79 iter->last_used = iter->nodes[0]->last; 80 if (iter->last_used >= last_index) { 81 iter->last_used = last_index; 82 iter->nodes[0] = NULL; 83 iter->nodes[1] = NULL; 84 } 85 } 86 EXPORT_SYMBOL_GPL(interval_tree_span_iter_first); 87 88 void interval_tree_span_iter_next(struct interval_tree_span_iter *iter) 89 { 90 if (!iter->nodes[0] && !iter->nodes[1]) { 91 iter->is_hole = -1; 92 return; 93 } 94 95 if (iter->is_hole) { 96 iter->start_used = iter->last_hole + 1; 97 iter->last_used = iter->nodes[0]->last; 98 if (iter->last_used >= iter->last_index) { 99 iter->last_used = iter->last_index; 100 iter->nodes[0] = NULL; 101 iter->nodes[1] = NULL; 102 } 103 iter->is_hole = 0; 104 return; 105 } 106 107 if (!iter->nodes[1]) { 108 /* Trailing hole */ 109 iter->start_hole = iter->nodes[0]->last + 1; 110 iter->last_hole = iter->last_index; 111 iter->nodes[0] = NULL; 112 iter->is_hole = 1; 113 return; 114 } 115 116 /* must have both nodes[0] and [1], interior hole */ 117 iter->start_hole = iter->nodes[0]->last + 1; 118 iter->last_hole = iter->nodes[1]->start - 1; 119 iter->is_hole = 1; 120 interval_tree_span_iter_next_gap(iter); 121 } 122 EXPORT_SYMBOL_GPL(interval_tree_span_iter_next); 123 124 /* 125 * Advance the iterator index to a specific position. The returned used/hole is 126 * updated to start at new_index. This is faster than calling 127 * interval_tree_span_iter_first() as it can avoid full searches in several 128 * cases where the iterator is already set. 129 */ 130 void interval_tree_span_iter_advance(struct interval_tree_span_iter *iter, 131 struct rb_root_cached *itree, 132 unsigned long new_index) 133 { 134 if (iter->is_hole == -1) 135 return; 136 137 iter->first_index = new_index; 138 if (new_index > iter->last_index) { 139 iter->is_hole = -1; 140 return; 141 } 142 143 /* Rely on the union aliasing hole/used */ 144 if (iter->start_hole <= new_index && new_index <= iter->last_hole) { 145 iter->start_hole = new_index; 146 return; 147 } 148 if (new_index == iter->last_hole + 1) 149 interval_tree_span_iter_next(iter); 150 else 151 interval_tree_span_iter_first(iter, itree, new_index, 152 iter->last_index); 153 } 154 EXPORT_SYMBOL_GPL(interval_tree_span_iter_advance); 155 #endif 156