Lely core libraries 2.3.4
|
This file is part of the utilities library; it contains the implementation of the red-black tree. More...
Go to the source code of this file.
Functions | |
static struct rbnode * | rbnode_get_parent (const struct rbnode *node) |
Returns the parent of node. node MUST NOT be NULL. | |
static void | rbnode_set_parent (struct rbnode *node, const struct rbnode *parent) |
Sets the parent of node to parent. More... | |
static int | rbnode_get_color (const struct rbnode *node) |
Returns the color of node, or 0 (black) if node is NULL. | |
static void | rbnode_set_color (struct rbnode *node, int color) |
Sets the color of node to 0 (black) if color is 0, or to 1 (red) otherwise. More... | |
static struct rbnode * | rbnode_min (struct rbnode *node) |
Returns the leftmost descendant of node. | |
static struct rbnode * | rbnode_max (struct rbnode *node) |
Returns the rightmost descendant of node. | |
static void | rbtree_rol (struct rbtree *tree, struct rbnode *node) |
Rotates node counter-clockwise (left), i.e., it is replaced in the tree by its right child, while becoming that child's left child. | |
static void | rbtree_ror (struct rbtree *tree, struct rbnode *node) |
Rotates node clockwise (right), i.e., it is replaced in the tree by its left child, while becoming that child's right child. | |
static void | rbtree_replace (struct rbtree *tree, struct rbnode *old_node, struct rbnode *new_node) |
Replaces old_node by new_node in tree by updating its parent. | |
struct rbnode * | rbnode_prev (const struct rbnode *node) |
Returns a pointer to the previous (in-order) node in a red-black tree with respect to node. More... | |
struct rbnode * | rbnode_next (const struct rbnode *node) |
Returns a pointer to the next (in-order) node in a red-black tree with respect to node. More... | |
void | rbtree_insert (struct rbtree *tree, struct rbnode *node) |
Inserts a node into a red-black tree. More... | |
void | rbtree_remove (struct rbtree *tree, struct rbnode *node) |
Removes a node from a red-black tree. More... | |
struct rbnode * | rbtree_find (const struct rbtree *tree, const void *key) |
Finds a node in a red-black tree. More... | |
int | rbtree_contains (const struct rbtree *tree, const struct rbnode *node) |
Checks if a node is part of a red-black tree. More... | |
struct rbnode * | rbtree_first (const struct rbtree *tree) |
Returns a pointer to the first (leftmost) node in a red-black tree. More... | |
struct rbnode * | rbtree_last (const struct rbtree *tree) |
Returns a pointer to the last (rightmost) node in a red-black tree. More... | |
This file is part of the utilities library; it contains the implementation of the red-black tree.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
Definition in file rbtree.c.
|
inlinestatic |
Returns a pointer to the previous (in-order) node in a red-black tree with respect to node.
This is, at worst, an O(log(n)) operation.
Returns a pointer to the next (in-order) node in a red-black tree with respect to node.
This is, at worst, an O(log(n)) operation. However, visiting all nodes in order is an O(n) operation, and therefore, on average, O(1) for each node.
Inserts a node into a red-black tree.
This is an O(log(n)) operation. This function does not check whether a node with the same key already exists, or whether the node is already part of another tree.
Finds a node in a red-black tree.
This is an O(log(n)) operation.
Returns a pointer to the first (leftmost) node in a red-black tree.
This is an O(log(n)) operation.
Returns a pointer to the last (rightmost) node in a red-black tree.
This is an O(log(n)) operation.