aboutsummaryrefslogtreecommitdiffstats
path: root/include/nvgpu/rbtree.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/nvgpu/rbtree.h')
-rw-r--r--include/nvgpu/rbtree.h130
1 files changed, 130 insertions, 0 deletions
diff --git a/include/nvgpu/rbtree.h b/include/nvgpu/rbtree.h
new file mode 100644
index 0000000..bcbbabb
--- /dev/null
+++ b/include/nvgpu/rbtree.h
@@ -0,0 +1,130 @@
1/*
2 * Copyright (c) 2017-2018, 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#ifndef NVGPU_RBTREE_H
24#define NVGPU_RBTREE_H
25
26#include <nvgpu/types.h>
27
28struct nvgpu_rbtree_node {
29 u64 key_start;
30 u64 key_end;
31
32 bool is_red; /* !IsRed == IsBlack */
33
34 struct nvgpu_rbtree_node *parent;
35 struct nvgpu_rbtree_node *left;
36 struct nvgpu_rbtree_node *right;
37};
38
39/**
40 * nvgpu_rbtree_insert - insert a new node into rbtree
41 *
42 * @new_node Pointer to new node.
43 * @root Pointer to root of tree
44 *
45 * Nodes with duplicate key_start and overlapping ranges
46 * are not allowed
47 */
48void nvgpu_rbtree_insert(struct nvgpu_rbtree_node *new_node,
49 struct nvgpu_rbtree_node **root);
50
51/**
52 * nvgpu_rbtree_unlink - delete a node from rbtree
53 *
54 * @node Pointer to node to be deleted
55 * @root Pointer to root of tree
56 */
57void nvgpu_rbtree_unlink(struct nvgpu_rbtree_node *node,
58 struct nvgpu_rbtree_node **root);
59
60/**
61 * nvgpu_rbtree_search - search a given key in rbtree
62 *
63 * @key_start Key to be searched in rbtree
64 * @node Node pointer to be returned
65 * @root Pointer to root of tree
66 *
67 * This API will match given key against key_start of each node
68 * In case of a hit, node points to a node with given key
69 * In case of a miss, node is NULL
70 */
71void nvgpu_rbtree_search(u64 key_start, struct nvgpu_rbtree_node **node,
72 struct nvgpu_rbtree_node *root);
73
74/**
75 * nvgpu_rbtree_range_search - search a node with key falling in range
76 *
77 * @key Key to be searched in rbtree
78 * @node Node pointer to be returned
79 * @root Pointer to root of tree
80 *
81 * This API will match given key and find a node where key value
82 * falls within range of {start, end} keys
83 * In case of a hit, node points to a node with given key
84 * In case of a miss, node is NULL
85 */
86void nvgpu_rbtree_range_search(u64 key,
87 struct nvgpu_rbtree_node **node,
88 struct nvgpu_rbtree_node *root);
89
90/**
91 * nvgpu_rbtree_less_than_search - search a node with key lesser than given key
92 *
93 * @key_start Key to be searched in rbtree
94 * @node Node pointer to be returned
95 * @root Pointer to root of tree
96 *
97 * This API will match given key and find a node with highest
98 * key value lesser than given key
99 * In case of a hit, node points to a node with given key
100 * In case of a miss, node is NULL
101 */
102void nvgpu_rbtree_less_than_search(u64 key_start,
103 struct nvgpu_rbtree_node **node,
104 struct nvgpu_rbtree_node *root);
105
106/**
107 * nvgpu_rbtree_enum_start - enumerate tree starting at the node with specified value
108 *
109 * @key_start Key value to begin enumeration from
110 * @node Pointer to first node in the tree
111 * @root Pointer to root of tree
112 *
113 * This API returns node pointer pointing to first node in the rbtree
114 */
115void nvgpu_rbtree_enum_start(u64 key_start,
116 struct nvgpu_rbtree_node **node,
117 struct nvgpu_rbtree_node *root);
118
119/**
120 * nvgpu_rbtree_enum_next - find next node in enumeration
121 *
122 * @node Pointer to next node in the tree
123 * @root Pointer to root of tree
124 *
125 * This API returns node pointer pointing to next node in the rbtree
126 */
127void nvgpu_rbtree_enum_next(struct nvgpu_rbtree_node **node,
128 struct nvgpu_rbtree_node *root);
129
130#endif /* NVGPU_RBTREE_H */