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 | * indexes that started at the original nodes[1]->start. nodes[1] is now the |
24 | * first node starting the next used span. A hole span is between nodes[0]->last |
25 | * and nodes[1]->start. nodes[1] must be !NULL. |
26 | */ |
27 | static void |
28 | interval_tree_span_iter_next_gap(struct interval_tree_span_iter *state) |
29 | { |
30 | struct interval_tree_node *cur = state->nodes[1]; |
31 | |
32 | state->nodes[0] = cur; |
33 | do { |
34 | if (cur->last > state->nodes[0]->last) |
35 | state->nodes[0] = cur; |
36 | cur = interval_tree_iter_next(cur, state->first_index, |
37 | state->last_index); |
38 | } while (cur && (state->nodes[0]->last >= cur->start || |
39 | state->nodes[0]->last + 1 == cur->start)); |
40 | state->nodes[1] = cur; |
41 | } |
42 | |
43 | void interval_tree_span_iter_first(struct interval_tree_span_iter *iter, |
44 | struct rb_root_cached *itree, |
45 | unsigned long first_index, |
46 | unsigned long last_index) |
47 | { |
48 | iter->first_index = first_index; |
49 | iter->last_index = last_index; |
50 | iter->nodes[0] = NULL; |
51 | iter->nodes[1] = |
52 | interval_tree_iter_first(itree, first_index, last_index); |
53 | if (!iter->nodes[1]) { |
54 | /* No nodes intersect the span, whole span is hole */ |
55 | iter->start_hole = first_index; |
56 | iter->last_hole = last_index; |
57 | iter->is_hole = 1; |
58 | return; |
59 | } |
60 | if (iter->nodes[1]->start > first_index) { |
61 | /* Leading hole on first iteration */ |
62 | iter->start_hole = first_index; |
63 | iter->last_hole = iter->nodes[1]->start - 1; |
64 | iter->is_hole = 1; |
65 | interval_tree_span_iter_next_gap(state: iter); |
66 | return; |
67 | } |
68 | |
69 | /* Starting inside a used */ |
70 | iter->start_used = first_index; |
71 | iter->is_hole = 0; |
72 | interval_tree_span_iter_next_gap(state: iter); |
73 | iter->last_used = iter->nodes[0]->last; |
74 | if (iter->last_used >= last_index) { |
75 | iter->last_used = last_index; |
76 | iter->nodes[0] = NULL; |
77 | iter->nodes[1] = NULL; |
78 | } |
79 | } |
80 | EXPORT_SYMBOL_GPL(interval_tree_span_iter_first); |
81 | |
82 | void interval_tree_span_iter_next(struct interval_tree_span_iter *iter) |
83 | { |
84 | if (!iter->nodes[0] && !iter->nodes[1]) { |
85 | iter->is_hole = -1; |
86 | return; |
87 | } |
88 | |
89 | if (iter->is_hole) { |
90 | iter->start_used = iter->last_hole + 1; |
91 | iter->last_used = iter->nodes[0]->last; |
92 | if (iter->last_used >= iter->last_index) { |
93 | iter->last_used = iter->last_index; |
94 | iter->nodes[0] = NULL; |
95 | iter->nodes[1] = NULL; |
96 | } |
97 | iter->is_hole = 0; |
98 | return; |
99 | } |
100 | |
101 | if (!iter->nodes[1]) { |
102 | /* Trailing hole */ |
103 | iter->start_hole = iter->nodes[0]->last + 1; |
104 | iter->last_hole = iter->last_index; |
105 | iter->nodes[0] = NULL; |
106 | iter->is_hole = 1; |
107 | return; |
108 | } |
109 | |
110 | /* must have both nodes[0] and [1], interior hole */ |
111 | iter->start_hole = iter->nodes[0]->last + 1; |
112 | iter->last_hole = iter->nodes[1]->start - 1; |
113 | iter->is_hole = 1; |
114 | interval_tree_span_iter_next_gap(state: iter); |
115 | } |
116 | EXPORT_SYMBOL_GPL(interval_tree_span_iter_next); |
117 | |
118 | /* |
119 | * Advance the iterator index to a specific position. The returned used/hole is |
120 | * updated to start at new_index. This is faster than calling |
121 | * interval_tree_span_iter_first() as it can avoid full searches in several |
122 | * cases where the iterator is already set. |
123 | */ |
124 | void interval_tree_span_iter_advance(struct interval_tree_span_iter *iter, |
125 | struct rb_root_cached *itree, |
126 | unsigned long new_index) |
127 | { |
128 | if (iter->is_hole == -1) |
129 | return; |
130 | |
131 | iter->first_index = new_index; |
132 | if (new_index > iter->last_index) { |
133 | iter->is_hole = -1; |
134 | return; |
135 | } |
136 | |
137 | /* Rely on the union aliasing hole/used */ |
138 | if (iter->start_hole <= new_index && new_index <= iter->last_hole) { |
139 | iter->start_hole = new_index; |
140 | return; |
141 | } |
142 | if (new_index == iter->last_hole + 1) |
143 | interval_tree_span_iter_next(iter); |
144 | else |
145 | interval_tree_span_iter_first(iter, itree, new_index, |
146 | iter->last_index); |
147 | } |
148 | EXPORT_SYMBOL_GPL(interval_tree_span_iter_advance); |
149 | #endif |
150 | |