diff options
author | Deepak Nibade <dnibade@nvidia.com> | 2017-03-30 05:10:09 -0400 |
---|---|---|
committer | mobile promotions <svcmobile_promotions@nvidia.com> | 2017-04-06 13:57:22 -0400 |
commit | 6dda47a114d1ecbef4f5fa77e8100d795ee23ff1 (patch) | |
tree | 87c3fecc7e473dc669256fab16cbf0dba765a995 /drivers/gpu | |
parent | 335b3fa2fe89de3ae37d01a8e9605dc74554f777 (diff) |
gpu: nvgpu: add rbtree implementation
In order to remove nvgpu's dependency from Linux,
add nvgpu's own rbtree implementation
Define a rbtree node as
struct nvgpu_rbtree_node *node;
Add below APIs to support rbtree operations
nvgpu_rbtree_insert()
- insert a new node into tree
nvgpu_rbtree_unlink()
- remove a node from tree
nvgpu_rbtree_search()
- search a key in tree
nvgpu_rbtree_range_search()
- search a node with key falling in range
nvgpu_rbtree_less_than_search()
- search a node with key lesser than given key
nvgpu_rbtree_enum_start()
- start enumerating a tree
nvgpu_rbtree_enum_next()
- find next node in enumeration
Jira NVGPU-13
Change-Id: Idceb375dc20d9411799c92608b0264e59886bf68
Signed-off-by: Deepak Nibade <dnibade@nvidia.com>
Reviewed-on: http://git-master/r/1331537
Reviewed-by: mobile promotions <svcmobile_promotions@nvidia.com>
Tested-by: mobile promotions <svcmobile_promotions@nvidia.com>
Diffstat (limited to 'drivers/gpu')
-rw-r--r-- | drivers/gpu/nvgpu/Makefile.nvgpu | 1 | ||||
-rw-r--r-- | drivers/gpu/nvgpu/common/rbtree.c | 429 | ||||
-rw-r--r-- | drivers/gpu/nvgpu/include/nvgpu/rbtree.h | 124 |
3 files changed, 554 insertions, 0 deletions
diff --git a/drivers/gpu/nvgpu/Makefile.nvgpu b/drivers/gpu/nvgpu/Makefile.nvgpu index b8a3f033..16c54849 100644 --- a/drivers/gpu/nvgpu/Makefile.nvgpu +++ b/drivers/gpu/nvgpu/Makefile.nvgpu | |||
@@ -40,6 +40,7 @@ nvgpu-y := \ | |||
40 | common/nvgpu_common.o \ | 40 | common/nvgpu_common.o \ |
41 | common/semaphore.o \ | 41 | common/semaphore.o \ |
42 | common/as.o \ | 42 | common/as.o \ |
43 | common/rbtree.o \ | ||
43 | common/vbios/bios.o \ | 44 | common/vbios/bios.o \ |
44 | gk20a/gk20a.o \ | 45 | gk20a/gk20a.o \ |
45 | gk20a/bus_gk20a.o \ | 46 | gk20a/bus_gk20a.o \ |
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 | } | ||
diff --git a/drivers/gpu/nvgpu/include/nvgpu/rbtree.h b/drivers/gpu/nvgpu/include/nvgpu/rbtree.h new file mode 100644 index 00000000..c29957c2 --- /dev/null +++ b/drivers/gpu/nvgpu/include/nvgpu/rbtree.h | |||
@@ -0,0 +1,124 @@ | |||
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 | #ifndef __NVGPU_RBTREE_H__ | ||
18 | #define __NVGPU_RBTREE_H__ | ||
19 | |||
20 | #include <nvgpu/types.h> | ||
21 | |||
22 | struct nvgpu_rbtree_node { | ||
23 | u64 key_start; | ||
24 | u64 key_end; | ||
25 | |||
26 | bool is_red; /* !IsRed == IsBlack */ | ||
27 | |||
28 | struct nvgpu_rbtree_node *parent; | ||
29 | struct nvgpu_rbtree_node *left; | ||
30 | struct nvgpu_rbtree_node *right; | ||
31 | }; | ||
32 | |||
33 | /** | ||
34 | * nvgpu_rbtree_insert - insert a new node into rbtree | ||
35 | * | ||
36 | * @new_node Pointer to new node. | ||
37 | * @root Pointer to root of tree | ||
38 | * | ||
39 | * Nodes with duplicate key_start and overlapping ranges | ||
40 | * are not allowed | ||
41 | */ | ||
42 | void nvgpu_rbtree_insert(struct nvgpu_rbtree_node *new_node, | ||
43 | struct nvgpu_rbtree_node **root); | ||
44 | |||
45 | /** | ||
46 | * nvgpu_rbtree_unlink - delete a node from rbtree | ||
47 | * | ||
48 | * @node Pointer to node to be deleted | ||
49 | * @root Pointer to root of tree | ||
50 | */ | ||
51 | void nvgpu_rbtree_unlink(struct nvgpu_rbtree_node *node, | ||
52 | struct nvgpu_rbtree_node **root); | ||
53 | |||
54 | /** | ||
55 | * nvgpu_rbtree_search - search a given key in rbtree | ||
56 | * | ||
57 | * @key_start Key to be searched in rbtree | ||
58 | * @node Node pointer to be returned | ||
59 | * @root Pointer to root of tree | ||
60 | * | ||
61 | * This API will match given key against key_start of each node | ||
62 | * In case of a hit, node points to a node with given key | ||
63 | * In case of a miss, node is NULL | ||
64 | */ | ||
65 | void nvgpu_rbtree_search(u64 key_start, struct nvgpu_rbtree_node **node, | ||
66 | struct nvgpu_rbtree_node *root); | ||
67 | |||
68 | /** | ||
69 | * nvgpu_rbtree_range_search - search a node with key falling in range | ||
70 | * | ||
71 | * @key Key to be searched in rbtree | ||
72 | * @node Node pointer to be returned | ||
73 | * @root Pointer to root of tree | ||
74 | * | ||
75 | * This API will match given key and find a node where key value | ||
76 | * falls within range of {start, end} keys | ||
77 | * In case of a hit, node points to a node with given key | ||
78 | * In case of a miss, node is NULL | ||
79 | */ | ||
80 | void nvgpu_rbtree_range_search(u64 key, | ||
81 | struct nvgpu_rbtree_node **node, | ||
82 | struct nvgpu_rbtree_node *root); | ||
83 | |||
84 | /** | ||
85 | * nvgpu_rbtree_less_than_search - search a node with key lesser than given key | ||
86 | * | ||
87 | * @key_start Key to be searched in rbtree | ||
88 | * @node Node pointer to be returned | ||
89 | * @root Pointer to root of tree | ||
90 | * | ||
91 | * This API will match given key and find a node with highest | ||
92 | * key value lesser than given key | ||
93 | * In case of a hit, node points to a node with given key | ||
94 | * In case of a miss, node is NULL | ||
95 | */ | ||
96 | void nvgpu_rbtree_less_than_search(u64 key_start, | ||
97 | struct nvgpu_rbtree_node **node, | ||
98 | struct nvgpu_rbtree_node *root); | ||
99 | |||
100 | /** | ||
101 | * nvgpu_rbtree_enum_start - enumerate tree starting at the node with specified value | ||
102 | * | ||
103 | * @key_start Key value to begin enumeration from | ||
104 | * @node Pointer to first node in the tree | ||
105 | * @root Pointer to root of tree | ||
106 | * | ||
107 | * This API returns node pointer pointing to first node in the rbtree | ||
108 | */ | ||
109 | void nvgpu_rbtree_enum_start(u64 key_start, | ||
110 | struct nvgpu_rbtree_node **node, | ||
111 | struct nvgpu_rbtree_node *root); | ||
112 | |||
113 | /** | ||
114 | * nvgpu_rbtree_enum_next - find next node in enumeration | ||
115 | * | ||
116 | * @node Pointer to next node in the tree | ||
117 | * @root Pointer to root of tree | ||
118 | * | ||
119 | * This API returns node pointer pointing to next node in the rbtree | ||
120 | */ | ||
121 | void nvgpu_rbtree_enum_next(struct nvgpu_rbtree_node **node, | ||
122 | struct nvgpu_rbtree_node *root); | ||
123 | |||
124 | #endif /* __NVGPU_RBTREE_H__ */ | ||