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