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