rbtree.c File Reference

#include <freeradius-devel/libradius.h>

Include dependency graph for rbtree.c:

Go to the source code of this file.

Data Structures
struct	rbnode_t
struct	rbtree_t

Macros
#define	NIL   &sentinel /* all leafs are sentinels */
#define	PTHREAD_MUTEX_LOCK(_x)
#define	PTHREAD_MUTEX_UNLOCK(_x)
#define	RBTREE_MAGIC   (0x5ad09c42)

Enumerations
enum	node_colour_t {   BLACK,   RED,   BLACK,   RED }

Functions
static void	delete_fixup (rbtree_t *tree, rbnode_t *x, rbnode_t *parent)
	Maintain RED-BLACK tree balance after deleting node x. More...
static void	free_walker (rbtree_t *tree, rbnode_t *x)
	Walks the tree to delete all nodes Does NOT re-balance it! More...
static void	insert_fixup (rbtree_t *tree, rbnode_t *x)
	Maintain red-black tree balance after inserting node x. More...
rbtree_t *	rbtree_create (TALLOC_CTX *ctx, rb_comparator_t compare, rb_free_t node_free, int flags)
	Create a new RED-BLACK tree. More...
void	rbtree_delete (rbtree_t *tree, rbnode_t *z)
static void	rbtree_delete_internal (rbtree_t *tree, rbnode_t *z, bool skiplock)
	Delete an element (z) from the tree. More...
bool	rbtree_deletebydata (rbtree_t *tree, void const *data)
	Delete a node from the tree, based on given data, which MUST have come from rbtree_finddata(). More...
rbnode_t *	rbtree_find (rbtree_t *tree, void const *data)
	Find an element in the tree, returning the data, not the node. More...
void *	rbtree_finddata (rbtree_t *tree, void const *data)
	Find the user data. More...
void	rbtree_free (rbtree_t *tree)
bool	rbtree_insert (rbtree_t *tree, void *data)
rbnode_t *	rbtree_insert_node (rbtree_t *tree, void *data)
	Insert an element into the tree. More...
void *	rbtree_node2data (UNUSED rbtree_t *tree, rbnode_t *node)
uint32_t	rbtree_num_elements (rbtree_t *tree)
int	rbtree_walk (rbtree_t *tree, rb_order_t order, rb_walker_t compare, void *context)
static void	rotate_left (rbtree_t *tree, rbnode_t *x)
	Rotate Node x to left. More...
static void	rotate_right (rbtree_t *tree, rbnode_t *x)
	Rotate Node x to right. More...
static int	walk_delete_order (rbtree_t *tree, rb_walker_t compare, void *context)
	rbtree_delete_order More...
static int	walk_node_in_order (rbnode_t *x, rb_walker_t compare, void *context)
	rbtree_in_order More...
static int	walk_node_post_order (rbnode_t *x, rb_walker_t compare, void *context)
	rbtree_post_order More...
static int	walk_node_pre_order (rbnode_t *x, rb_walker_t compare, void *context)
	Walk the tree, Pre-order. More...

Variables
static rbnode_t	sentinel = { NIL, NIL, NULL, BLACK, NULL}

---

Data Structure Documentation

struct rbnode_t

Definition at line 43 of file rbtree.c.

Collaboration diagram for rbnode_t:

Data Fields
node_colour_t	colour	Node colour (BLACK, RED)
void *	data	data stored in node
rbnode_t *	left	Left child. left child
rbnode_t *	parent	Parent.
rbnode_t *	right	Right child. right child

struct rbtree_t

Definition at line 54 of file rbtree.c.

Collaboration diagram for rbtree_t:

Data Fields
rb_comparator_t	compare
rb_free_t	free
uint32_t	magic
int	num_elements
bool	replace
rbnode_t *	root

Macro Definition Documentation

#define NIL   &sentinel /* all leafs are sentinels */

Definition at line 51 of file rbtree.c.

#define PTHREAD_MUTEX_LOCK

(

_x

)

Definition at line 33 of file rbtree.c.

#define PTHREAD_MUTEX_UNLOCK

(

_x

)

Definition at line 34 of file rbtree.c.

#define RBTREE_MAGIC   (0x5ad09c42)

Definition at line 68 of file rbtree.c.

Enumeration Type Documentation

enum node_colour_t

Enumerator
BLACK
RED
BLACK
RED

Definition at line 38 of file rbtree.c.

Function Documentation

static void delete_fixup ( rbtree_t *  tree, rbnode_t *  x, rbnode_t *  parent  )

static

Maintain RED-BLACK tree balance after deleting node x.

Definition at line 338 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

static void free_walker ( rbtree_t *  tree, rbnode_t *  x  )

static

Walks the tree to delete all nodes Does NOT re-balance it!

Definition at line 73 of file rbtree.c.

Here is the caller graph for this function:

static void insert_fixup ( rbtree_t *  tree, rbnode_t *  x  )

static

Maintain red-black tree balance after inserting node x.

Definition at line 198 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rbtree_t* rbtree_create	(	TALLOC_CTX *	ctx,
		rb_comparator_t	compare,
		rb_free_t	node_free,
		int	flags
	)

Create a new RED-BLACK tree.

Definition at line 112 of file rbtree.c.

Here is the caller graph for this function:

void rbtree_delete	(	rbtree_t *	tree,
		rbnode_t *	z
	)

Definition at line 488 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

static void rbtree_delete_internal ( rbtree_t *  tree, rbnode_t *  z, bool  skiplock  )

static

Delete an element (z) from the tree.

Definition at line 404 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

bool rbtree_deletebydata	(	rbtree_t *	tree,
		void const *	data
	)

Delete a node from the tree, based on given data, which MUST have come from rbtree_finddata().

Definition at line 496 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rbnode_t* rbtree_find	(	rbtree_t *	tree,
		void const *	data
	)

Find an element in the tree, returning the data, not the node.

Definition at line 511 of file rbtree.c.

Here is the caller graph for this function:

void* rbtree_finddata	(	rbtree_t *	tree,
		void const *	data
	)

Find the user data.

Definition at line 537 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

void rbtree_free

(

rbtree_t *

tree

)

Definition at line 84 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

bool rbtree_insert	(	rbtree_t *	tree,
		void *	data
	)

Definition at line 329 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rbnode_t* rbtree_insert_node	(	rbtree_t *	tree,
		void *	data
	)

Insert an element into the tree.

Definition at line 258 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

void* rbtree_node2data	(	UNUSED rbtree_t *	tree,
		rbnode_t *	node
	)

Definition at line 737 of file rbtree.c.

uint32_t rbtree_num_elements

(

rbtree_t *

tree

)

Definition at line 727 of file rbtree.c.

Here is the caller graph for this function:

int rbtree_walk	(	rbtree_t *	tree,
		rb_order_t	order,
		rb_walker_t	compare,
		void *	context
	)

Definition at line 693 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

static void rotate_left ( rbtree_t *  tree, rbnode_t *  x  )

static

Rotate Node x to left.

Definition at line 141 of file rbtree.c.

Here is the caller graph for this function:

static void rotate_right ( rbtree_t *  tree, rbnode_t *  x  )

static

Rotate Node x to right.

Definition at line 170 of file rbtree.c.

Here is the caller graph for this function:

static int walk_delete_order ( rbtree_t *  tree, rb_walker_t  compare, void *  context  )

static

rbtree_delete_order

This executes an rbtree_in_order-like walk that adapts to changes in the tree above it, which may occur because we allow the compare to tell us to delete the current node.

The compare should return:

< 0  - on error
0    - continue walking, don't delete the node
1    - delete the node and stop walking
2    - delete the node and continue walking

Definition at line 640 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

static int walk_node_in_order ( rbnode_t *  x, rb_walker_t  compare, void *  context  )

static

rbtree_in_order

Definition at line 579 of file rbtree.c.

Here is the caller graph for this function:

static int walk_node_post_order ( rbnode_t *  x, rb_walker_t  compare, void *  context  )

static

rbtree_post_order

Definition at line 606 of file rbtree.c.

Here is the caller graph for this function:

static int walk_node_pre_order ( rbnode_t *  x, rb_walker_t  compare, void *  context  )

static

Walk the tree, Pre-order.

We call ourselves recursively for each function, but that's OK, as the stack is only log(N) deep, which is ~12 entries deep.

Definition at line 552 of file rbtree.c.

Here is the caller graph for this function:

Variable Documentation

rbnode_t sentinel = { NIL, NIL, NULL, BLACK, NULL}

static

Definition at line 52 of file rbtree.c.