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>

1 files changed, 124 insertions, 0 deletions

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 @@
+/*
+ * Copyright (c) 2017, NVIDIA CORPORATION.  All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef __NVGPU_RBTREE_H__
+#define __NVGPU_RBTREE_H__
+
+#include <nvgpu/types.h>
+
+struct nvgpu_rbtree_node {
+        u64 key_start;
+        u64 key_end;
+
+        bool is_red; /* !IsRed == IsBlack */
+
+        struct nvgpu_rbtree_node *parent;
+        struct nvgpu_rbtree_node *left;
+        struct nvgpu_rbtree_node *right;
+};
+
+/**
+ * nvgpu_rbtree_insert - insert a new node into rbtree
+ *
+ * @new_node    Pointer to new node.
+ * @root        Pointer to root of tree
+ *
+ * Nodes with duplicate key_start and overlapping ranges
+ * are not allowed
+ */
+void nvgpu_rbtree_insert(struct nvgpu_rbtree_node *new_node,
+                    struct nvgpu_rbtree_node **root);
+
+/**
+ * nvgpu_rbtree_unlink - delete a node from rbtree
+ *
+ * @node        Pointer to node to be deleted
+ * @root        Pointer to root of tree
+ */
+void nvgpu_rbtree_unlink(struct nvgpu_rbtree_node *node,
+                    struct nvgpu_rbtree_node **root);
+
+/**
+ * nvgpu_rbtree_search - search a given key in rbtree
+ *
+ * @key_start   Key to be searched in rbtree
+ * @node        Node pointer to be returned
+ * @root        Pointer to root of tree
+ *
+ * This API will match given key against key_start of each node
+ * In case of a hit, node points to a node with given key
+ * In case of a miss, node is NULL
+ */
+void nvgpu_rbtree_search(u64 key_start, struct nvgpu_rbtree_node **node,
+                             struct nvgpu_rbtree_node *root);
+
+/**
+ * nvgpu_rbtree_range_search - search a node with key falling in range
+ *
+ * @key         Key to be searched in rbtree
+ * @node        Node pointer to be returned
+ * @root        Pointer to root of tree
+ *
+ * This API will match given key and find a node where key value
+ * falls within range of {start, end} keys
+ * In case of a hit, node points to a node with given key
+ * In case of a miss, node is NULL
+ */
+void nvgpu_rbtree_range_search(u64 key,
+                               struct nvgpu_rbtree_node **node,
+                               struct nvgpu_rbtree_node *root);
+
+/**
+ * nvgpu_rbtree_less_than_search - search a node with key lesser than given key
+ *
+ * @key_start   Key to be searched in rbtree
+ * @node        Node pointer to be returned
+ * @root        Pointer to root of tree
+ *
+ * This API will match given key and find a node with highest
+ * key value lesser than given key
+ * In case of a hit, node points to a node with given key
+ * In case of a miss, node is NULL
+ */
+void nvgpu_rbtree_less_than_search(u64 key_start,
+                               struct nvgpu_rbtree_node **node,
+                               struct nvgpu_rbtree_node *root);
+
+/**
+ * nvgpu_rbtree_enum_start - enumerate tree starting at the node with specified value
+ *
+ * @key_start   Key value to begin enumeration from
+ * @node        Pointer to first node in the tree
+ * @root        Pointer to root of tree
+ *
+ * This API returns node pointer pointing to first node in the rbtree
+ */
+void nvgpu_rbtree_enum_start(u64 key_start,
+                        struct nvgpu_rbtree_node **node,
+                        struct nvgpu_rbtree_node *root);
+
+/**
+ * nvgpu_rbtree_enum_next - find next node in enumeration
+ *
+ * @node        Pointer to next node in the tree
+ * @root        Pointer to root of tree
+ *
+ * This API returns node pointer pointing to next node in the rbtree
+ */
+void nvgpu_rbtree_enum_next(struct nvgpu_rbtree_node **node,
+                       struct nvgpu_rbtree_node *root);
+
+#endif /* __NVGPU_RBTREE_H__ */