1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 /*
3 Interval Trees
4 (C) 2012 Michel Lespinasse <walken@google.com>
5
6
7 include/linux/interval_tree_generic.h
8 */
9
10 #include <linux/rbtree_augmented.h>
11
12 /*
13 * Template for implementing interval trees
14 *
15 * ITSTRUCT: struct type of the interval tree nodes
16 * ITRB: name of struct rb_node field within ITSTRUCT
17 * ITTYPE: type of the interval endpoints
18 * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
19 * ITSTART(n): start endpoint of ITSTRUCT node n
20 * ITLAST(n): last endpoint of ITSTRUCT node n
21 * ITSTATIC: 'static' or empty
22 * ITPREFIX: prefix to use for the inline tree definitions
23 *
24 * Note - before using this, please consider if generic version
25 * (interval_tree.h) would work for you...
26 */
27
28 #define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \
29 ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
30 \
31 /* Callbacks for augmented rbtree insert and remove */ \
32 \
33 RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \
34 ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST) \
35 \
36 /* Insert / remove interval nodes from the tree */ \
37 \
38 ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
39 struct rb_root_cached *root) \
40 { \
41 struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \
42 ITTYPE start = ITSTART(node), last = ITLAST(node); \
43 ITSTRUCT *parent; \
44 bool leftmost = true; \
45 \
46 while (*link) { \
47 rb_parent = *link; \
48 parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \
49 if (parent->ITSUBTREE < last) \
50 parent->ITSUBTREE = last; \
51 if (start < ITSTART(parent)) \
52 link = &parent->ITRB.rb_left; \
53 else { \
54 link = &parent->ITRB.rb_right; \
55 leftmost = false; \
56 } \
57 } \
58 \
59 node->ITSUBTREE = last; \
60 rb_link_node(&node->ITRB, rb_parent, link); \
61 rb_insert_augmented_cached(&node->ITRB, root, \
62 leftmost, &ITPREFIX ## _augment); \
63 } \
64 \
65 ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
66 struct rb_root_cached *root) \
67 { \
68 rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \
69 } \
70 \
71 /* \
72 * Iterate over intervals intersecting [start;last] \
73 * \
74 * Note that a node's interval intersects [start;last] iff: \
75 * Cond1: ITSTART(node) <= last \
76 * and \
77 * Cond2: start <= ITLAST(node) \
78 */ \
79 \
80 static ITSTRUCT * \
81 ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
82 { \
83 while (true) { \
84 /* \
85 * Loop invariant: start <= node->ITSUBTREE \
86 * (Cond2 is satisfied by one of the subtree nodes) \
87 */ \
88 if (node->ITRB.rb_left) { \
89 ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \
90 ITSTRUCT, ITRB); \
91 if (start <= left->ITSUBTREE) { \
92 /* \
93 * Some nodes in left subtree satisfy Cond2. \
94 * Iterate to find the leftmost such node N. \
95 * If it also satisfies Cond1, that's the \
96 * match we are looking for. Otherwise, there \
97 * is no matching interval as nodes to the \
98 * right of N can't satisfy Cond1 either. \
99 */ \
100 node = left; \
101 continue; \
102 } \
103 } \
104 if (ITSTART(node) <= last) { /* Cond1 */ \
105 if (start <= ITLAST(node)) /* Cond2 */ \
106 return node; /* node is leftmost match */ \
107 if (node->ITRB.rb_right) { \
108 node = rb_entry(node->ITRB.rb_right, \
109 ITSTRUCT, ITRB); \
110 if (start <= node->ITSUBTREE) \
111 continue; \
112 } \
113 } \
114 return NULL; /* No match */ \
115 } \
116 } \
117 \
118 ITSTATIC ITSTRUCT * \
119 ITPREFIX ## _iter_first(struct rb_root_cached *root, \
120 ITTYPE start, ITTYPE last) \
121 { \
122 ITSTRUCT *node, *leftmost; \
123 \
124 if (!root->rb_root.rb_node) \
125 return NULL; \
126 \
127 /* \
128 * Fastpath range intersection/overlap between A: [a0, a1] and \
129 * B: [b0, b1] is given by: \
130 * \
131 * a0 <= b1 && b0 <= a1 \
132 * \
133 * ... where A holds the lock range and B holds the smallest \
134 * 'start' and largest 'last' in the tree. For the later, we \
135 * rely on the root node, which by augmented interval tree \
136 * property, holds the largest value in its last-in-subtree. \
137 * This allows mitigating some of the tree walk overhead for \
138 * for non-intersecting ranges, maintained and consulted in O(1). \
139 */ \
140 node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \
141 if (node->ITSUBTREE < start) \
142 return NULL; \
143 \
144 leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \
145 if (ITSTART(leftmost) > last) \
146 return NULL; \
147 \
148 return ITPREFIX ## _subtree_search(node, start, last); \
149 } \
150 \
151 ITSTATIC ITSTRUCT * \
152 ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
153 { \
154 struct rb_node *rb = node->ITRB.rb_right, *prev; \
155 \
156 while (true) { \
157 /* \
158 * Loop invariants: \
159 * Cond1: ITSTART(node) <= last \
160 * rb == node->ITRB.rb_right \
161 * \
162 * First, search right subtree if suitable \
163 */ \
164 if (rb) { \
165 ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \
166 if (start <= right->ITSUBTREE) \
167 return ITPREFIX ## _subtree_search(right, \
168 start, last); \
169 } \
170 \
171 /* Move up the tree until we come from a node's left child */ \
172 do { \
173 rb = rb_parent(&node->ITRB); \
174 if (!rb) \
175 return NULL; \
176 prev = &node->ITRB; \
177 node = rb_entry(rb, ITSTRUCT, ITRB); \
178 rb = node->ITRB.rb_right; \
179 } while (prev == rb); \
180 \
181 /* Check if the node intersects [start;last] */ \
182 if (last < ITSTART(node)) /* !Cond1 */ \
183 return NULL; \
184 else if (start <= ITLAST(node)) /* Cond2 */ \
185 return node; \
186 } \
187 }