diff options
Diffstat (limited to 'include/nvgpu/rbtree.h')
| -rw-r--r-- | include/nvgpu/rbtree.h | 130 |
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 | |||
| 28 | struct 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 | */ | ||
| 48 | void 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 | */ | ||
| 57 | void 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 | */ | ||
| 71 | void 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 | */ | ||
| 86 | void 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 | */ | ||
| 102 | void 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 | */ | ||
| 115 | void 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 | */ | ||
| 127 | void nvgpu_rbtree_enum_next(struct nvgpu_rbtree_node **node, | ||
| 128 | struct nvgpu_rbtree_node *root); | ||
| 129 | |||
| 130 | #endif /* NVGPU_RBTREE_H */ | ||