Lely core libraries 2.3.4
|
This header file is part of the utilities library; it contains the red-black tree declarations. More...
Go to the source code of this file.
Data Structures | |
struct | rbnode |
A node in a red-black tree. More... | |
struct | rbtree |
A red-black tree. More... | |
Macros | |
#define | RBNODE_INIT |
The static initializer for rbnode. | |
#define | RBTREE_INIT |
The static initializer for rbtree. | |
#define | rbnode_foreach(first, node) rbnode_foreach_(__LINE__, first, node) |
Iterates over each node in a red-black tree in ascending order. | |
#define | rbtree_foreach(tree, node) rbnode_foreach (rbtree_first(tree), node) |
Iterates over each node in a red-black tree in ascending order. | |
Typedefs | |
typedef int | rbtree_cmp_t(const void *, const void *) |
The type of a comparison function suitable for use in a red-black tree. | |
Functions | |
void | rbnode_init (struct rbnode *node, const void *key) |
Initializes a node in a red-black tree. | |
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. | |
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. | |
void | rbtree_init (struct rbtree *tree, rbtree_cmp_t *cmp) |
Initializes a red-black tree. | |
int | rbtree_empty (const struct rbtree *tree) |
Returns 1 if the red-black tree is empty, and 0 if not. | |
size_t | rbtree_size (const struct rbtree *tree) |
Returns the size (in number of nodes) of a red-black tree. | |
void | rbtree_insert (struct rbtree *tree, struct rbnode *node) |
Inserts a node into a red-black tree. | |
void | rbtree_remove (struct rbtree *tree, struct rbnode *node) |
Removes a node from a red-black tree. | |
int | rbtree_contains (const struct rbtree *tree, const struct rbnode *node) |
Checks if a node is part of a red-black tree. | |
struct rbnode * | rbtree_find (const struct rbtree *tree, const void *key) |
Finds a node in a red-black tree. | |
struct rbnode * | rbtree_first (const struct rbtree *tree) |
Returns a pointer to the first (leftmost) node in a red-black tree. | |
struct rbnode * | rbtree_last (const struct rbtree *tree) |
Returns a pointer to the last (rightmost) node in a red-black tree. | |
struct rbnode * | rbtree_root (const struct rbtree *tree) |
Returns a pointer to the root node in a red-black tree. | |
This header file is part of the utilities library; it contains the red-black tree declarations.
A red-black tree is a type of self-balancing binary tree. This implementation is based on chapters 12 and 13 in:
T. H. Cormen et al., Introduction to Algorithms (third edition), MIT Press (2009).
The red-black tree implemented here is generic and can be used for any kind of key-value pair; only (void) pointers to keys are stored. Upon initialization of the tree, the user is responsible for providing a suitable comparison function (rbtree_cmp_t).
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.h.
#define rbnode_foreach | ( | first, | |
node | |||
) | rbnode_foreach_(__LINE__, first, node) |
Iterates over each node in a red-black tree in ascending order.
It is safe to remove the current node during the iteration.
first | a pointer to the first node. |
node | the name of the pointer to the nodes. This variable is declared in the scope of the loop. |
#define rbtree_foreach | ( | tree, | |
node | |||
) | rbnode_foreach (rbtree_first(tree), node) |
Iterates over each node in a red-black tree in ascending order.
typedef int rbtree_cmp_t(const void *, const void *) |
The type of a comparison function suitable for use in a red-black tree.
p1 and p2 MUST be NULL or point to objects of the same type.
|
inline |
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.
|
inline |
|
inline |
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.