rb_tree.c File Reference

#include "rb_tree.h"
#include <string.h>
#include "dict_private.h"
#include "tree_common.h"

Include dependency graph for rb_tree.c:

Go to the source code of this file.

Data Structures
struct	rb_node
struct	rb_tree
struct	rb_itor

Macros
#define	RB_RED   0
#define	RB_BLACK   1
#define	PARENT(node)
#define	COLOR(node)
#define	SET_RED(node)
#define	SET_BLACK(node)
#define	SET_PARENT(node, p)

Typedefs
typedef struct rb_node	rb_node

Functions
rb_tree *	rb_tree_new (dict_compare_func cmp_func)
dict *	rb_dict_new (dict_compare_func cmp_func)
size_t	rb_tree_free (rb_tree *tree, dict_delete_func delete_func)
size_t	rb_tree_clear (rb_tree *tree, dict_delete_func delete_func)
void **	rb_tree_search (rb_tree *tree, const void *key)
void **	rb_tree_search_le (rb_tree *tree, const void *key)
void **	rb_tree_search_lt (rb_tree *tree, const void *key)
void **	rb_tree_search_ge (rb_tree *tree, const void *key)
void **	rb_tree_search_gt (rb_tree *tree, const void *key)
dict_insert_result	rb_tree_insert (rb_tree *tree, void *key)
dict_remove_result	rb_tree_remove (rb_tree *tree, const void *key)
size_t	rb_tree_count (const rb_tree *tree)
size_t	rb_tree_min_path_length (const rb_tree *tree)
size_t	rb_tree_max_path_length (const rb_tree *tree)
size_t	rb_tree_total_path_length (const rb_tree *tree)
size_t	rb_tree_traverse (rb_tree *tree, dict_visit_func visit, void *user_data)
bool	rb_tree_select (rb_tree *tree, size_t n, const void **key, void **datum)
bool	rb_tree_verify (const rb_tree *tree)
rb_itor *	rb_itor_new (rb_tree *tree)
dict_itor *	rb_dict_itor_new (rb_tree *tree)
void	rb_itor_free (rb_itor *itor)
bool	rb_itor_valid (const rb_itor *itor)
void	rb_itor_invalidate (rb_itor *itor)
bool	rb_itor_next (rb_itor *itor)
bool	rb_itor_prev (rb_itor *itor)
bool	rb_itor_nextn (rb_itor *itor, size_t count)
bool	rb_itor_prevn (rb_itor *itor, size_t count)
bool	rb_itor_first (rb_itor *itor)
bool	rb_itor_last (rb_itor *itor)
bool	rb_itor_search (rb_itor *itor, const void *key)
bool	rb_itor_search_le (rb_itor *itor, const void *key)
bool	rb_itor_search_lt (rb_itor *itor, const void *key)
bool	rb_itor_search_ge (rb_itor *itor, const void *key)
bool	rb_itor_search_gt (rb_itor *itor, const void *key)
const void *	rb_itor_key (const rb_itor *itor)
void **	rb_itor_datum (rb_itor *itor)
int	rb_itor_compare (const rb_itor *i1, const rb_itor *i2)
bool	rb_itor_remove (rb_itor *it)

Macro Definition Documentation

COLOR

#define COLOR

(

node

)

Value:

((node)->color & RB_BLACK)

Definition at line 51 of file rb_tree.c.

PARENT

#define PARENT

(

node

)

Value:

((rb_node*)((node)->color & ~RB_BLACK))

Definition at line 50 of file rb_tree.c.

RB_BLACK

#define RB_BLACK   1

Definition at line 48 of file rb_tree.c.

RB_RED

#define RB_RED   0

Definition at line 47 of file rb_tree.c.

SET_BLACK

#define SET_BLACK

(

node

)

Value:

(node)->color |= ((intptr_t)RB_BLACK)

Definition at line 54 of file rb_tree.c.

SET_PARENT

#define SET_PARENT	(		node,
			p )

Value:

(node)->color = COLOR(node) | (intptr_t)(p)

Definition at line 55 of file rb_tree.c.

SET_RED

#define SET_RED

(

node

)

Value:

(node)->color &= (~(intptr_t)RB_BLACK)

Definition at line 53 of file rb_tree.c.

Typedef Documentation

rb_node

typedef struct rb_node rb_node

Definition at line 38 of file rb_tree.c.

Function Documentation

rb_dict_itor_new()

dict_itor * rb_dict_itor_new

(

rb_tree *

tree

)

Definition at line 573 of file rb_tree.c.

Here is the call graph for this function:

rb_dict_new()

dict * rb_dict_new

(

dict_compare_func

cmp_func

)

Definition at line 128 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_compare()

int rb_itor_compare	(	const rb_itor *	i1,
		const rb_itor *	i2 )

Definition at line 635 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_datum()

void ** rb_itor_datum

(

rb_itor *

itor

)

Definition at line 634 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_first()

bool rb_itor_first

(

rb_itor *

itor

)

Definition at line 626 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_free()

void rb_itor_free

(

rb_itor *

itor

)

Definition at line 586 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_invalidate()

void rb_itor_invalidate

(

rb_itor *

itor

)

Definition at line 588 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_key()

const void * rb_itor_key

(

const rb_itor *

itor

)

Definition at line 633 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_last()

bool rb_itor_last

(

rb_itor *

itor

)

Definition at line 627 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_new()

rb_itor * rb_itor_new

(

rb_tree *

tree

)

Definition at line 562 of file rb_tree.c.

rb_itor_next()

bool rb_itor_next

(

rb_itor *

itor

)

Definition at line 591 of file rb_tree.c.

rb_itor_nextn()

bool rb_itor_nextn	(	rb_itor *	itor,
		size_t	count )

Definition at line 607 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_prev()

bool rb_itor_prev

(

rb_itor *

itor

)

Definition at line 599 of file rb_tree.c.

rb_itor_prevn()

bool rb_itor_prevn	(	rb_itor *	itor,
		size_t	count )

Definition at line 617 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_remove()

bool rb_itor_remove

(

rb_itor *

it

)

Definition at line 638 of file rb_tree.c.

rb_itor_search()

bool rb_itor_search	(	rb_itor *	itor,
		const void *	key )

Definition at line 628 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_search_ge()

bool rb_itor_search_ge	(	rb_itor *	itor,
		const void *	key )

Definition at line 631 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_search_gt()

bool rb_itor_search_gt	(	rb_itor *	itor,
		const void *	key )

Definition at line 632 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_search_le()

bool rb_itor_search_le	(	rb_itor *	itor,
		const void *	key )

Definition at line 629 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_search_lt()

bool rb_itor_search_lt	(	rb_itor *	itor,
		const void *	key )

Definition at line 630 of file rb_tree.c.

Here is the call graph for this function:

rb_itor_valid()

bool rb_itor_valid

(

const rb_itor *

itor

)

Definition at line 587 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_clear()

size_t rb_tree_clear	(	rb_tree *	tree,
		dict_delete_func	delete_func )

Definition at line 149 of file rb_tree.c.

rb_tree_count()

size_t rb_tree_count

(

const rb_tree *

tree

)

Definition at line 379 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_free()

size_t rb_tree_free	(	rb_tree *	tree,
		dict_delete_func	delete_func )

Definition at line 142 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_insert()

dict_insert_result rb_tree_insert	(	rb_tree *	tree,
		void *	key )

Definition at line 177 of file rb_tree.c.

rb_tree_max_path_length()

size_t rb_tree_max_path_length

(

const rb_tree *

tree

)

Definition at line 381 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_min_path_length()

size_t rb_tree_min_path_length

(

const rb_tree *

tree

)

Definition at line 380 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_new()

rb_tree * rb_tree_new

(

dict_compare_func

cmp_func

)

Definition at line 113 of file rb_tree.c.

rb_tree_remove()

dict_remove_result rb_tree_remove	(	rb_tree *	tree,
		const void *	key )

Definition at line 294 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_search()

void ** rb_tree_search	(	rb_tree *	tree,
		const void *	key )

Definition at line 170 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_search_ge()

void ** rb_tree_search_ge	(	rb_tree *	tree,
		const void *	key )

Definition at line 173 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_search_gt()

void ** rb_tree_search_gt	(	rb_tree *	tree,
		const void *	key )

Definition at line 174 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_search_le()

void ** rb_tree_search_le	(	rb_tree *	tree,
		const void *	key )

Definition at line 171 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_search_lt()

void ** rb_tree_search_lt	(	rb_tree *	tree,
		const void *	key )

Definition at line 172 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_select()

bool rb_tree_select	(	rb_tree *	tree,
		size_t	n,
		const void **	key,
		void **	datum )

Definition at line 400 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_total_path_length()

size_t rb_tree_total_path_length

(

const rb_tree *

tree

)

Definition at line 382 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_traverse()

size_t rb_tree_traverse	(	rb_tree *	tree,
		dict_visit_func	visit,
		void *	user_data )

Definition at line 385 of file rb_tree.c.

Here is the call graph for this function:

rb_tree_verify()

bool rb_tree_verify

(

const rb_tree *

tree

)

Definition at line 545 of file rb_tree.c.