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
10INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
11 unsigned long, __subtree_last,
12 START, LAST,, interval_tree)
13
14EXPORT_SYMBOL_GPL(interval_tree_insert);
15EXPORT_SYMBOL_GPL(interval_tree_remove);
16EXPORT_SYMBOL_GPL(interval_tree_iter_first);
17EXPORT_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 */
33static void
34interval_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
49void 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}
86EXPORT_SYMBOL_GPL(interval_tree_span_iter_first);
87
88void 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}
122EXPORT_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 */
130void 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}
154EXPORT_SYMBOL_GPL(interval_tree_span_iter_advance);
155#endif
156