Include nvgpu headers

These are needed to build on NVIDIA's Jetson boards for the time
being. Only a couple structs are required, so it should be fairly
easy to remove this dependency at some point in the future.

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 @@
+/*
+ * Copyright (c) 2017-2018, NVIDIA CORPORATION.  All rights reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+#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 */