summaryrefslogtreecommitdiffstats
path: root/drivers/gpu/nvgpu/common/rbtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/gpu/nvgpu/common/rbtree.c')
-rw-r--r--drivers/gpu/nvgpu/common/rbtree.c435
1 files changed, 435 insertions, 0 deletions
diff --git a/drivers/gpu/nvgpu/common/rbtree.c b/drivers/gpu/nvgpu/common/rbtree.c
new file mode 100644
index 00000000..d1f79cbb
--- /dev/null
+++ b/drivers/gpu/nvgpu/common/rbtree.c
@@ -0,0 +1,435 @@
1/*
2 * Copyright (c) 2017, NVIDIA CORPORATION. All rights reserved.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
21 */
22
23#include <nvgpu/rbtree.h>
24
25/*
26 * rotate node x to left
27 */
28static void rotate_left(struct nvgpu_rbtree_node **root,
29 struct nvgpu_rbtree_node *x)
30{
31 struct nvgpu_rbtree_node *y = x->right;
32
33 /* establish x->right link */
34 x->right = y->left;
35 if (y->left)
36 y->left->parent = x;
37
38 /* establish y->parent link */
39 y->parent = x->parent;
40 if (x->parent) {
41 if (x == x->parent->left)
42 x->parent->left = y;
43 else
44 x->parent->right = y;
45 } else {
46 *root = y;
47 }
48
49 /* link x and y */
50 y->left = x;
51 x->parent = y;
52}
53
54/*
55 * rotate node x to right
56 */
57static void rotate_right(struct nvgpu_rbtree_node **root,
58 struct nvgpu_rbtree_node *x)
59{
60 struct nvgpu_rbtree_node *y = x->left;
61
62 /* establish x->left link */
63 x->left = y->right;
64 if (y->right)
65 y->right->parent = x;
66
67 /* establish y->parent link */
68 y->parent = x->parent;
69 if (x->parent) {
70 if (x == x->parent->right)
71 x->parent->right = y;
72 else
73 x->parent->left = y;
74 } else {
75 *root = y;
76 }
77
78 /* link x and y */
79 y->right = x;
80 x->parent = y;
81}
82
83/*
84 * maintain red-black tree balance after inserting node x
85 */
86static void insert_fixup(struct nvgpu_rbtree_node **root,
87 struct nvgpu_rbtree_node *x)
88{
89 /* check red-black properties */
90 while ((x != *root) && x->parent->is_red) {
91 /* we have a violation */
92 if (x->parent == x->parent->parent->left) {
93 struct nvgpu_rbtree_node *y = x->parent->parent->right;
94
95 if (y && y->is_red) {
96 /* uncle is RED */
97 x->parent->is_red = false;
98 y->is_red = false;
99 x->parent->parent->is_red = true;
100 x = x->parent->parent;
101 } else {
102 /* uncle is BLACK */
103 if (x == x->parent->right) {
104 /* make x a left child */
105 x = x->parent;
106 rotate_left(root, x);
107 }
108
109 /* recolor and rotate */
110 x->parent->is_red = false;
111 x->parent->parent->is_red = true;
112 rotate_right(root, x->parent->parent);
113 }
114 } else {
115 /* mirror image of above code */
116 struct nvgpu_rbtree_node *y = x->parent->parent->left;
117
118 if (y && y->is_red) {
119 /* uncle is RED */
120 x->parent->is_red = false;
121 y->is_red = false;
122 x->parent->parent->is_red = true;
123 x = x->parent->parent;
124 } else {
125 /* uncle is BLACK */
126 if (x == x->parent->left) {
127 x = x->parent;
128 rotate_right(root, x);
129 }
130 x->parent->is_red = false;
131 x->parent->parent->is_red = true;
132 rotate_left(root, x->parent->parent);
133 }
134 }
135 }
136
137 (*root)->is_red = false;
138}
139
140void nvgpu_rbtree_insert(struct nvgpu_rbtree_node *new_node,
141 struct nvgpu_rbtree_node **root)
142{
143 struct nvgpu_rbtree_node *curr;
144 struct nvgpu_rbtree_node *parent;
145
146 /* find future parent */
147 curr = *root;
148 parent = NULL;
149
150 while (curr) {
151 parent = curr;
152 if (new_node->key_start < curr->key_start)
153 curr = curr->left;
154 else if (new_node->key_start > curr->key_start)
155 curr = curr->right;
156 else
157 return; /* duplicate entry */
158 }
159
160 /* the caller allocated the node already, just fix the links */
161 new_node->parent = parent;
162 new_node->left = NULL;
163 new_node->right = NULL;
164 new_node->is_red = true;
165
166 /* insert node in tree */
167 if (parent) {
168 if (new_node->key_start < parent->key_start)
169 parent->left = new_node;
170 else
171 parent->right = new_node;
172 } else {
173 *root = new_node;
174 }
175
176 insert_fixup(root, new_node);
177}
178
179/*
180 * maintain red-black tree balance after deleting node x
181 */
182static void _delete_fixup(struct nvgpu_rbtree_node **root,
183 struct nvgpu_rbtree_node *parent_of_x,
184 struct nvgpu_rbtree_node *x)
185{
186 while ((x != *root) && (!x || !x->is_red)) {
187 /*
188 * NULL nodes are sentinel nodes. If we delete a sentinel
189 * node (x==NULL) it must have a parent node (or be the root).
190 * Hence, parent_of_x == NULL with
191 * x==NULL is never possible (tree invariant)
192 */
193
194 if ((parent_of_x != NULL) && (x == parent_of_x->left)) {
195 struct nvgpu_rbtree_node *w = parent_of_x->right;
196
197 if (w && w->is_red) {
198 w->is_red = false;
199 parent_of_x->is_red = true;
200 rotate_left(root, parent_of_x);
201 w = parent_of_x->right;
202 }
203
204 if (!w || ((!w->left || !w->left->is_red)
205 && (!w->right || !w->right->is_red))) {
206 if (w)
207 w->is_red = true;
208 x = parent_of_x;
209 } else {
210 if (!w->right || !w->right->is_red) {
211 w->left->is_red = false;
212 w->is_red = true;
213 rotate_right(root, w);
214 w = parent_of_x->right;
215 }
216 w->is_red = parent_of_x->is_red;
217 parent_of_x->is_red = false;
218 w->right->is_red = false;
219 rotate_left(root, parent_of_x);
220 x = *root;
221 }
222 } else if (parent_of_x != NULL) {
223 struct nvgpu_rbtree_node *w = parent_of_x->left;
224
225 if (w && w->is_red) {
226 w->is_red = false;
227 parent_of_x->is_red = true;
228 rotate_right(root, parent_of_x);
229 w = parent_of_x->left;
230 }
231
232 if (!w || ((!w->right || !w->right->is_red)
233 && (!w->left || !w->left->is_red))) {
234 if (w)
235 w->is_red = true;
236 x = parent_of_x;
237 } else {
238 if (!w->left || !w->left->is_red) {
239 w->right->is_red = false;
240 w->is_red = true;
241 rotate_left(root, w);
242 w = parent_of_x->left;
243 }
244 w->is_red = parent_of_x->is_red;
245 parent_of_x->is_red = false;
246 w->left->is_red = false;
247 rotate_right(root, parent_of_x);
248 x = *root;
249 }
250 }
251 parent_of_x = x->parent;
252 }
253
254 if (x)
255 x->is_red = false;
256}
257
258void nvgpu_rbtree_unlink(struct nvgpu_rbtree_node *node,
259 struct nvgpu_rbtree_node **root)
260{
261 struct nvgpu_rbtree_node *x;
262 struct nvgpu_rbtree_node *y;
263 struct nvgpu_rbtree_node *z;
264 struct nvgpu_rbtree_node *parent_of_x;
265 bool y_was_black;
266
267 z = node;
268
269 /* unlink */
270 if (!z->left || !z->right) {
271 /* y has a SENTINEL node as a child */
272 y = z;
273 } else {
274 /* find tree successor */
275 y = z->right;
276 while (y->left)
277 y = y->left;
278 }
279
280 /* x is y's only child */
281 if (y->left)
282 x = y->left;
283 else
284 x = y->right;
285
286 /* remove y from the parent chain */
287 parent_of_x = y->parent;
288 if (x)
289 x->parent = parent_of_x;
290
291 if (y->parent) {
292 if (y == y->parent->left)
293 y->parent->left = x;
294 else
295 y->parent->right = x;
296 } else {
297 *root = x;
298 }
299
300 y_was_black = !y->is_red;
301 if (y != z) {
302 /* we need to replace z with y so
303 * the memory for z can be freed
304 */
305 y->parent = z->parent;
306 if (z->parent) {
307 if (z == z->parent->left)
308 z->parent->left = y;
309 else
310 z->parent->right = y;
311 } else {
312 *root = y;
313 }
314
315 y->is_red = z->is_red;
316
317 y->left = z->left;
318 if (z->left)
319 z->left->parent = y;
320
321 y->right = z->right;
322 if (z->right)
323 z->right->parent = y;
324
325 if (parent_of_x == z)
326 parent_of_x = y;
327 }
328
329 if (y_was_black)
330 _delete_fixup(root, parent_of_x, x);
331}
332
333void nvgpu_rbtree_search(u64 key_start, struct nvgpu_rbtree_node **node,
334 struct nvgpu_rbtree_node *root)
335{
336 struct nvgpu_rbtree_node *curr = root;
337
338 while (curr) {
339 if (key_start < curr->key_start) {
340 curr = curr->left;
341 } else if (key_start > curr->key_start) {
342 curr = curr->right;
343 } else {
344 *node = curr;
345 return;
346 }
347 }
348
349 *node = NULL;
350}
351
352void nvgpu_rbtree_range_search(u64 key,
353 struct nvgpu_rbtree_node **node,
354 struct nvgpu_rbtree_node *root)
355{
356 struct nvgpu_rbtree_node *curr = root;
357
358 while (curr) {
359 if (key >= curr->key_start &&
360 key < curr->key_end) {
361 *node = curr;
362 return;
363 } else if (key < curr->key_start) {
364 curr = curr->left;
365 } else {
366 curr = curr->right;
367 }
368 }
369
370 *node = NULL;
371}
372
373void nvgpu_rbtree_less_than_search(u64 key_start,
374 struct nvgpu_rbtree_node **node,
375 struct nvgpu_rbtree_node *root)
376{
377 struct nvgpu_rbtree_node *curr = root;
378
379 while (curr) {
380 if (key_start <= curr->key_start) {
381 curr = curr->left;
382 } else {
383 *node = curr;
384 curr = curr->right;
385 }
386 }
387}
388
389void nvgpu_rbtree_enum_start(u64 key_start, struct nvgpu_rbtree_node **node,
390 struct nvgpu_rbtree_node *root)
391{
392 *node = NULL;
393
394 if (root) {
395 struct nvgpu_rbtree_node *curr = root;
396
397 while (curr) {
398 if (key_start < curr->key_start) {
399 *node = curr;
400 curr = curr->left;
401 } else if (key_start > curr->key_start) {
402 curr = curr->right;
403 } else {
404 *node = curr;
405 break;
406 }
407 }
408 }
409}
410
411void nvgpu_rbtree_enum_next(struct nvgpu_rbtree_node **node,
412 struct nvgpu_rbtree_node *root)
413{
414 struct nvgpu_rbtree_node *curr = NULL;
415
416 if (root && *node) {
417 /* if we don't have a right subtree return the parent */
418 curr = *node;
419
420 /* pick the leftmost node of the right subtree ? */
421 if (curr->right) {
422 curr = curr->right;
423 for (; curr->left;)
424 curr = curr->left;
425 } else {
426 /* go up until we find the right inorder node */
427 for (curr = curr->parent; curr; curr = curr->parent) {
428 if (curr->key_start > (*node)->key_start)
429 break;
430 }
431 }
432 }
433
434 *node = curr;
435}
generated by cgit v1.2.2 (git 2.25.0) at 2024-08-22 13:47:55 -0400