Lely core libraries 2.3.4
rbtree.h File Reference

This header file is part of the utilities library; it contains the red-black tree declarations. More...

#include <lely/features.h>
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
Include dependency graph for rbtree.h:
This graph shows which files directly or indirectly include this file:

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 rbnoderbnode_prev (const struct rbnode *node)
 Returns a pointer to the previous (in-order) node in a red-black tree with respect to node.
 
struct rbnoderbnode_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 rbnoderbtree_find (const struct rbtree *tree, const void *key)
 Finds a node in a red-black tree.
 
struct rbnoderbtree_first (const struct rbtree *tree)
 Returns a pointer to the first (leftmost) node in a red-black tree.
 
struct rbnoderbtree_last (const struct rbtree *tree)
 Returns a pointer to the last (rightmost) node in a red-black tree.
 
struct rbnoderbtree_root (const struct rbtree *tree)
 Returns a pointer to the root node in a red-black tree.
 

Detailed Description

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).

Author
J. S. Seldenthuis jseld.nosp@m.enth.nosp@m.uis@l.nosp@m.ely..nosp@m.com

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.

Macro Definition Documentation

◆ rbnode_foreach

#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.

Parameters
firsta pointer to the first node.
nodethe name of the pointer to the nodes. This variable is declared in the scope of the loop.
See also
rbnode_next()

Definition at line 146 of file rbtree.h.

◆ rbtree_foreach

#define rbtree_foreach (   tree,
  node 
)    rbnode_foreach (rbtree_first(tree), node)

Iterates over each node in a red-black tree in ascending order.

See also
rbnode_foreach(), rbtree_first()

Definition at line 234 of file rbtree.h.

Typedef Documentation

◆ rbtree_cmp_t

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.

Returns
an integer greater than, equal to, or less than 0 if the object at p1 is greater than, equal to, or less than the object at p2.

Definition at line 88 of file rbtree.h.

Function Documentation

◆ rbnode_init()

void rbnode_init ( struct rbnode node,
const void *  key 
)
inline

Initializes a node in a red-black tree.

Parameters
nodea pointer to the node to be initialized.
keya pointer to the key for this node. The key MUST NOT be modified while the node is part of a tree.

Definition at line 237 of file rbtree.h.

◆ rbnode_prev()

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.

This is, at worst, an O(log(n)) operation.

See also
rbnode_next()

Definition at line 74 of file rbtree.c.

◆ rbnode_next()

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.

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.

See also
rbnode_prev()

Definition at line 91 of file rbtree.c.

◆ rbtree_init()

void rbtree_init ( struct rbtree tree,
rbtree_cmp_t cmp 
)
inline

Initializes a red-black tree.

Parameters
treea pointer to the tree to be initialized.
cmpa pointer to the function used to compare two keys.

Definition at line 248 of file rbtree.h.

◆ rbtree_size()

size_t rbtree_size ( const struct rbtree tree)
inline

Returns the size (in number of nodes) of a red-black tree.

This is an O(1) operation.

Definition at line 265 of file rbtree.h.

◆ rbtree_insert()

void rbtree_insert ( struct rbtree tree,
struct rbnode 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.

See also
rbtree_remove(), rbtree_find()

Definition at line 108 of file rbtree.c.

◆ rbtree_remove()

void rbtree_remove ( struct rbtree tree,
struct rbnode node 
)

Removes a node from a red-black tree.

This is an O(log(n)) operation.

See also
rbtree_insert()

Definition at line 187 of file rbtree.c.

◆ rbtree_contains()

int rbtree_contains ( const struct rbtree tree,
const struct rbnode node 
)

Checks if a node is part of a red-black tree.

Returns
1 if the node was found in the tree, and 0 if not.

Definition at line 322 of file rbtree.c.

◆ rbtree_find()

struct rbnode * rbtree_find ( const struct rbtree tree,
const void *  key 
)

Finds a node in a red-black tree.

This is an O(log(n)) operation.

Returns
a pointer to the node if found, or NULL if not.
See also
rbtree_insert()

Definition at line 306 of file rbtree.c.

◆ rbtree_first()

struct rbnode * rbtree_first ( const struct rbtree tree)

Returns a pointer to the first (leftmost) node in a red-black tree.

This is an O(log(n)) operation.

See also
rbtree_last()

Definition at line 335 of file rbtree.c.

◆ rbtree_last()

struct rbnode * rbtree_last ( const struct rbtree tree)

Returns a pointer to the last (rightmost) node in a red-black tree.

This is an O(log(n)) operation.

See also
rbtree_first()

Definition at line 343 of file rbtree.c.

◆ rbtree_root()

struct rbnode * rbtree_root ( const struct rbtree tree)
inline

Returns a pointer to the root node in a red-black tree.

This is an O(1) operation.

Definition at line 273 of file rbtree.h.