#include <errno.h>
#include <sys/types.h>
#include "types.h"
#include "queue.h"
#include "utils.h"

Include dependency graph for rbt.h:

Data Structures
struct	s_rbt_node
	A node in a red-black tree. More...

struct	s_rbt
	A left-leaning red-black binary search tree. More...

Typedefs
typedef enum e_rbt_node_color	t_rbt_node_color

typedef struct s_rbt_node	t_rbt_node

typedef struct s_rbt	t_rbt

Enumerations
enum	e_rbt_node_color { RBT_RED, RBT_BLACK }
	The color of a node in a red-black tree. More...

Functions
t_rbt *	rbt_new (const t_type key_type, const t_type val_type)
	Initializes a new empty tree. More...

void	rbt_put (t_rbt rbt, const void key, const void *val)
	Adds a new item to the tree or overwrites an existing one. More...

void *	rbt_get (const t_rbt rbt, const void key)
	Returns the value associated with a specified key. More...

size_t	rbt_size (const t_rbt *rbt)
	Returns the number of elements in this tree. More...

void	rbt_delete (t_rbt *rbt)
	Deletes this tree and free all its items and the associated data. More...

size_t	rbt_height (const t_rbt *rbt)
	Returns the number of tiers in the tree. More...

void *	rbt_min (const t_rbt *rbt)
	Returns the smallest key in the tree. More...

void *	rbt_max (const t_rbt *rbt)
	Returns the largest key in the tree. More...

void *	rbt_floor (const t_rbt rbt, const void key)
	Returns the largest key less than or equal to the specified key. More...

void *	rbt_ceil (const t_rbt rbt, const void key)
	Returns the smallest key greater than or equal to the specified key. More...

size_t	rbt_rank (const t_rbt rbt, const void key)
	Returns the number of keys in the tree strictly less than the specified key. More...

t_queue *	rbt_keys (const t_rbt *rbt)
	Returns a queue with all the keys in the tree, sorted in the ascending order. More...

t_queue *	rbt_vals (const t_rbt *rbt)
	Returns a queue with all the value in the tree, sorted by the associated keys in the ascending order. More...

int	rbt_contains (const t_rbt rbt, const void key)
	Does the tree contain the specified key? More...

void *	rbt_nth (const t_rbt *rbt, size_t n)
	Returns the key of the nth element in the tree. More...

Enumeration Type Documentation

◆ e_rbt_node_color

enum e_rbt_node_color

The color of a node in a red-black tree.

Definition at line 29 of file rbt.h.

Function Documentation

◆ rbt_ceil()

void* rbt_ceil	(	const t_rbt *	rbt,
		const void *	key
	)

Returns the smallest key greater than or equal to the specified key.

Parameters

key The key

Returns: The key greater than or equal to the specified key, or NULL, if the tree is empty.

Definition at line 33 of file rbt_ceil.c.

◆ rbt_contains()

int rbt_contains	(	const t_rbt *	rbt,
		const void *	key
	)

Does the tree contain the specified key?

Parameters

key The key

Returns: 1 if tree contains the specified key, 0 otherwise

Definition at line 16 of file rbt_contains.c.

◆ rbt_delete()

void rbt_delete ( t_rbt * rbt )

Deletes this tree and free all its items and the associated data.

Does nothing if the argument is NULL.

Definition at line 34 of file rbt_delete.c.

◆ rbt_floor()

void* rbt_floor	(	const t_rbt *	rbt,
		const void *	key
	)

Returns the largest key less than or equal to the specified key.

Parameters

key The key

Returns: The smallest key in the tree, or NULL, if the tree is empty.

Definition at line 33 of file rbt_floor.c.

◆ rbt_get()

void* rbt_get	(	const t_rbt *	rbt,
		const void *	key
	)

Returns the value associated with a specified key.

Parameters

key	The key to search for

Returns: The value associated with the key, or NULL if the key is not in the tree.

Definition at line 16 of file rbt_get.c.

◆ rbt_height()

size_t rbt_height ( const t_rbt * rbt )

Returns the number of tiers in the tree.

Returns: The number of tiers

Note: (used primarily for debugging purposes)

Definition at line 28 of file rbt_height.c.

◆ rbt_keys()

t_queue* rbt_keys ( const t_rbt * rbt )

Returns a queue with all the keys in the tree, sorted in the ascending order.

Returns: a queue with all the keys in the tree, sorted in the ascending order

Definition at line 26 of file rbt_keys.c.

◆ rbt_max()

void* rbt_max ( const t_rbt * rbt )

Returns the largest key in the tree.

Returns: The largest key in the tree, or NULL, if the tree is empty.

Definition at line 16 of file rbt_max.c.

◆ rbt_min()

void* rbt_min ( const t_rbt * rbt )

Returns the smallest key in the tree.

Returns: The value associated with the smallest key in the tree, or NULL, if the tree is empty.

Definition at line 16 of file rbt_min.c.

◆ rbt_new()

t_rbt* rbt_new	(	const t_type *	key_type,
		const t_type *	val_type
	)

Initializes a new empty tree.

Parameters

key_type	The type of keys
val_type	The type of values

Returns: The new tree, or NULL on failure. In case of an error, errno is set accordingly.

Remarks: For this function to work, the datatype in this array must be comparable (i.e. implement the cmp function).

Definition at line 16 of file rbt_new.c.

◆ rbt_nth()

void* rbt_nth	(	const t_rbt *	rbt,
		size_t	n
	)

Returns the key of the nth element in the tree.

Parameters

n The index

Returns: The key of the nth element in the tree

Definition at line 30 of file rbt_nth.c.

◆ rbt_put()

void rbt_put	(	t_rbt *	rbt,
		const void *	key,
		const void *	val
	)

Adds a new item to the tree or overwrites an existing one.

Parameters

key	The key to be copied
val	The value to be copied

Definition at line 45 of file rbt_put.c.

◆ rbt_rank()

size_t rbt_rank	(	const t_rbt *	rbt,
		const void *	key
	)

Returns the number of keys in the tree strictly less than the specified key.

Parameters

key The key

Returns: the number of keys in the tree strictly less than the specified key

Definition at line 34 of file rbt_rank.c.

◆ rbt_size()

size_t rbt_size ( const t_rbt * rbt )

Returns the number of elements in this tree.

Returns: the number of elements in this tree.

Definition at line 17 of file rbt_size.c.

◆ rbt_vals()

t_queue* rbt_vals ( const t_rbt * rbt )

Returns a queue with all the value in the tree, sorted by the associated keys in the ascending order.

Returns: a queue with all the keys in the tree, sorted by the associated keys in the ascending order

Definition at line 26 of file rbt_vals.c.

Data Structures

Typedefs

Enumerations

Functions

Enumeration Type Documentation

◆ e_rbt_node_color

Function Documentation

◆ rbt_ceil()

◆ rbt_contains()

◆ rbt_delete()

◆ rbt_floor()

◆ rbt_get()

◆ rbt_height()

◆ rbt_keys()

◆ rbt_max()

◆ rbt_min()

◆ rbt_new()

◆ rbt_nth()

◆ rbt_put()

◆ rbt_rank()

◆ rbt_size()

◆ rbt_vals()