libctru  v1.6.0
Data Structures | Macros | Typedefs | Functions | Variables
rbtree.h File Reference

Red-black trees. More...

#include <stdint.h>
#include <stddef.h>

Go to the source code of this file.

Data Structures

struct  rbtree_node_t
 An rbtree node. More...
 
struct  rbtree_t
 An rbtree. More...
 

Macros

#define rbtree_item(ptr, type, member)   ((type*)(((char*)ptr) - offsetof(type, member)))
 Retrieves an rbtree item.
 

Typedefs

typedef void(* rbtree_node_destructor_t) (rbtree_node_t *Node)
 rbtree node destructor.
 
typedef int(* rbtree_node_comparator_t) (const rbtree_node_t *lhs, const rbtree_node_t *rhs)
 rbtree node comparator.
 

Functions

void rbtree_init (rbtree_t *tree, rbtree_node_comparator_t comparator)
 Initializes an rbtree. More...
 
int rbtree_empty (const rbtree_t *tree)
 Gets whether an rbtree is empty. More...
 
size_t rbtree_size (const rbtree_t *tree)
 Gets the size of an rbtree. More...
 
 __attribute__ ((warn_unused_result)) rbtree_node_t *rbtree_insert(rbtree_t *tree
 Inserts a node into an rbtree. More...
 
void rbtree_insert_multi (rbtree_t *tree, rbtree_node_t *node)
 Inserts multiple nodes into an rbtree. More...
 
rbtree_node_t * rbtree_find (const rbtree_t *tree, const rbtree_node_t *node)
 Finds a node within an rbtree. More...
 
rbtree_node_t * rbtree_min (const rbtree_t *tree)
 Gets the minimum node of an rbtree. More...
 
rbtree_node_t * rbtree_max (const rbtree_t *tree)
 Gets the maximum node of an rbtree. More...
 
rbtree_node_t * rbtree_node_next (const rbtree_node_t *node)
 Gets the next node from an rbtree node. More...
 
rbtree_node_t * rbtree_node_prev (const rbtree_node_t *node)
 Gets the previous node from an rbtree node. More...
 
rbtree_node_t * rbtree_remove (rbtree_t *tree, rbtree_node_t *node, rbtree_node_destructor_t destructor)
 Removes a node from an rbtree. More...
 
void rbtree_clear (rbtree_t *tree, rbtree_node_destructor_t destructor)
 Clears an rbtree. More...
 

Variables

rbtree_node_t * node
 

Detailed Description

Red-black trees.

Function Documentation

◆ __attribute__()

__attribute__ ( (warn_unused_result)  )

Inserts a node into an rbtree.

Parameters
treePointer to the tree.
nodePointer to the node.
Returns
The inserted node.
Examples
network/sockets/source/sockets.c.

◆ rbtree_clear()

void rbtree_clear ( rbtree_t *  tree,
rbtree_node_destructor_t  destructor 
)

Clears an rbtree.

Parameters
treePointer to the tree.
destructorDestructor to use when clearing the tree's nodes.

◆ rbtree_empty()

int rbtree_empty ( const rbtree_t *  tree)

Gets whether an rbtree is empty.

Parameters
treePointer to the tree.
Returns
A non-zero value if the tree is not empty.

◆ rbtree_find()

rbtree_node_t* rbtree_find ( const rbtree_t *  tree,
const rbtree_node_t *  node 
)

Finds a node within an rbtree.

Parameters
treePointer to the tree.
nodePointer to the node.
Returns
The located node.

◆ rbtree_init()

void rbtree_init ( rbtree_t *  tree,
rbtree_node_comparator_t  comparator 
)

Initializes an rbtree.

Parameters
treePointer to the tree.
comparatorComparator to use.

◆ rbtree_insert_multi()

void rbtree_insert_multi ( rbtree_t *  tree,
rbtree_node_t *  node 
)

Inserts multiple nodes into an rbtree.

Parameters
treePointer to the tree.
nodePointer to the nodes.

◆ rbtree_max()

rbtree_node_t* rbtree_max ( const rbtree_t *  tree)

Gets the maximum node of an rbtree.

Parameters
treePointer to the tree.
Returns
The maximum node.

◆ rbtree_min()

rbtree_node_t* rbtree_min ( const rbtree_t *  tree)

Gets the minimum node of an rbtree.

Parameters
treePointer to the tree.
Returns
The minimum node.

◆ rbtree_node_next()

rbtree_node_t* rbtree_node_next ( const rbtree_node_t *  node)

Gets the next node from an rbtree node.

Parameters
nodePointer to the node.
Returns
The next node.

◆ rbtree_node_prev()

rbtree_node_t* rbtree_node_prev ( const rbtree_node_t *  node)

Gets the previous node from an rbtree node.

Parameters
nodePointer to the node.
Returns
The previous node.

◆ rbtree_remove()

rbtree_node_t* rbtree_remove ( rbtree_t *  tree,
rbtree_node_t *  node,
rbtree_node_destructor_t  destructor 
)

Removes a node from an rbtree.

Parameters
treePointer to the tree.
nodePointer to the node.
destructorDestructor to use when removing the node.
Returns
The removed node.

◆ rbtree_size()

size_t rbtree_size ( const rbtree_t *  tree)

Gets the size of an rbtree.

Parameters
treePointer to the tree.