Commit | Line | Data |
---|---|---|
457c8996 | 1 | // SPDX-License-Identifier: GPL-2.0-only |
fff3fd8a | 2 | #include <linux/interval_tree.h> |
9826a516 | 3 | #include <linux/interval_tree_generic.h> |
85c5e27c RV |
4 | #include <linux/compiler.h> |
5 | #include <linux/export.h> | |
fff3fd8a | 6 | |
9826a516 ML |
7 | #define START(node) ((node)->start) |
8 | #define LAST(node) ((node)->last) | |
6b2dbba8 | 9 | |
9826a516 ML |
10 | INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, |
11 | unsigned long, __subtree_last, | |
12 | START, LAST,, interval_tree) | |
a88cc108 CW |
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); | |
5fe93786 JG |
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(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(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(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 |