ut0rbt.h File Reference

Various utilities. More...

#include "univ.i"
#include "ut0mem.h"

Go to the source code of this file.

Classes
struct	ib_rbt_node_t
	Red black tree node. More...
struct	ib_rbt_t
	Red black tree instance. More...
struct	ib_rbt_bound_t
	The result of searching for a key in the tree, this is useful for a speedy lookup and insert if key doesn't exist. More...

Macros
#define	rbt_size(t)   (t->n_nodes)
#define	rbt_empty(t)   (rbt_size(t) == 0)
#define	rbt_value(t, n)   ((t *)&n->value[0])
#define	rbt_compare(t, k, n)   (t->compare(k, n->value))

Typedefs
typedef void(*	ib_rbt_print_node) (const ib_rbt_node_t *node)
typedef int(*	ib_rbt_compare) (const void *p1, const void *p2)
typedef int(*	ib_rbt_arg_compare) (const void *, const void *p1, const void *p2)

Enumerations
enum	ib_rbt_color_t { IB_RBT_RED , IB_RBT_BLACK }
	Red black tree color types. More...

Functions
void	rbt_free (ib_rbt_t *tree)
	Free an instance of a red black tree. More...
ib_rbt_t *	rbt_create (size_t sizeof_value, ib_rbt_compare compare)
	Create an instance of a red black tree. More...
ib_rbt_t *	rbt_create_arg_cmp (size_t sizeof_value, ib_rbt_arg_compare compare, void *cmp_arg)
	Create an instance of a red black tree, whose comparison function takes an argument. More...
bool	rbt_delete (ib_rbt_t *tree, const void *key)
	Delete a node from the red black tree, identified by key. More...
ib_rbt_node_t *	rbt_remove_node (ib_rbt_t *tree, const ib_rbt_node_t *node)
	Remove a node from the red black tree, NOTE: This function will not delete the node instance, THAT IS THE CALLERS RESPONSIBILITY. More...
const ib_rbt_node_t *	rbt_insert (ib_rbt_t *tree, const void *key, const void *value)
	Add data to the red black tree, identified by key (no dups yet!) More...
const ib_rbt_node_t *	rbt_add_node (ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *value)
	Add a new node to the tree, useful for data that is pre-sorted. More...
const ib_rbt_node_t *	rbt_first (const ib_rbt_t *tree)
	Return the left most data node in the tree. More...
const ib_rbt_node_t *	rbt_last (const ib_rbt_t *tree)
	Return the right most data node in the tree. More...
const ib_rbt_node_t *	rbt_next (const ib_rbt_t *tree, const ib_rbt_node_t *current)
	Return the next node from current. More...
const ib_rbt_node_t *	rbt_prev (const ib_rbt_t *tree, const ib_rbt_node_t *current)
	Return the prev node from current. More...
int	rbt_search (const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key)
	Search for the key, a node will be returned in parent.last, whether it was found or not. More...
int	rbt_search_cmp (const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key, ib_rbt_compare compare, ib_rbt_arg_compare arg_compare)
	Search for the key, a node will be returned in parent.last, whether it was found or not. More...
ulint	rbt_merge_uniq (ib_rbt_t *dst, const ib_rbt_t *src)
	Merge the node from dst into src. More...
bool	rbt_validate (const ib_rbt_t *tree)
	Verify the integrity of the RB tree. More...

Detailed Description

Various utilities.

Created 2007-03-20 Sunny Bains

Macro Definition Documentation

rbt_compare

#define rbt_compare	(		t,
			k,
			n
	)		(t->compare(k, n->value))

rbt_empty

#define rbt_empty

(

t

)

(rbt_size(t) == 0)

rbt_size

#define rbt_size

(

t

)

(t->n_nodes)

rbt_value

#define rbt_value	(		t,
			n
	)		((t *)&n->value[0])

Typedef Documentation

ib_rbt_arg_compare

typedef int(* ib_rbt_arg_compare) (const void *, const void *p1, const void *p2)

ib_rbt_compare

typedef int(* ib_rbt_compare) (const void *p1, const void *p2)

ib_rbt_print_node

typedef void(* ib_rbt_print_node) (const ib_rbt_node_t *node)

Enumeration Type Documentation

ib_rbt_color_t

enum ib_rbt_color_t

Red black tree color types.

Enumerator
IB_RBT_RED
IB_RBT_BLACK

Function Documentation

rbt_add_node()

const ib_rbt_node_t * rbt_add_node	(	ib_rbt_t *	tree,
		ib_rbt_bound_t *	parent,
		const void *	value
	)

Add a new node to the tree, useful for data that is pre-sorted.

Returns

appended node in: this value is copied to the node

appended node

Parameters

tree	in: rb tree
parent	in: bounds
value	in: this value is copied to the node

rbt_create()

ib_rbt_t * rbt_create	(	size_t	sizeof_value,
		ib_rbt_compare	compare
	)

Create an instance of a red black tree.

Returns

rb tree instance in: comparator

an empty rb tree

Parameters

sizeof_value	in: sizeof data item
compare	in: fn to compare items

rbt_create_arg_cmp()

ib_rbt_t * rbt_create_arg_cmp	(	size_t	sizeof_value,
		ib_rbt_arg_compare	compare,
		void *	cmp_arg
	)

Create an instance of a red black tree, whose comparison function takes an argument.

Returns

rb tree instance in: compare fn arg

an empty rb tree

Parameters

sizeof_value	in: sizeof data item
compare	in: fn to compare items
cmp_arg	in: compare fn arg

rbt_delete()

bool rbt_delete	(	ib_rbt_t *	tree,
		const void *	key
	)

Delete a node from the red black tree, identified by key.

Delete a node from the red black tree, identified by key.

Returns

true if success false if not found

Parameters

tree	in: rb tree
key	in: key to delete

rbt_first()

const ib_rbt_node_t * rbt_first

(

const ib_rbt_t *

tree

)

Return the left most data node in the tree.

Returns

left most node in: rb tree

Return the left most data node in the tree.

rbt_free()

void rbt_free

(

ib_rbt_t *

tree

)

Free an instance of a red black tree.

in: rb tree to free

Free an instance of a red black tree.

Parameters

tree	in: rb tree to free

rbt_insert()

const ib_rbt_node_t * rbt_insert	(	ib_rbt_t *	tree,
		const void *	key,
		const void *	value
	)

Add data to the red black tree, identified by key (no dups yet!)

Returns

inserted node in: data that will be copied to the node.

Add data to the red black tree, identified by key (no dups yet!)

Returns

inserted node

Parameters

tree	in: rb tree
key	in: key for ordering
value	in: value of key, this value is copied to the node

rbt_last()

const ib_rbt_node_t * rbt_last

(

const ib_rbt_t *

tree

)

Return the right most data node in the tree.

Returns

right most node in: rb tree

Return the right most data node in the tree.

Returns

the rightmost node or NULL

Parameters

tree	in: rb tree

rbt_merge_uniq()

ulint rbt_merge_uniq	(	ib_rbt_t *	dst,
		const ib_rbt_t *	src
	)

Merge the node from dst into src.

Return the number of nodes merged.

Returns

no. of recs merged in: src rb tree

Return the number of nodes merged.

Returns

no. of recs merged

Parameters

dst	in: dst rb tree
src	in: src rb tree

rbt_next()

const ib_rbt_node_t * rbt_next	(	const ib_rbt_t *	tree,
		const ib_rbt_node_t *	current
	)

Return the next node from current.

Returns

successor node to current that is passed in.

Return the next node from current.

Returns

node next from current

Parameters

tree	in: rb tree
current	in: current node

rbt_prev()

const ib_rbt_node_t * rbt_prev	(	const ib_rbt_t *	tree,
		const ib_rbt_node_t *	current
	)

Return the prev node from current.

Returns

predecessor node to current that is passed in

Return the prev node from current.

Returns

node prev from current

Parameters

tree	in: rb tree
current	in: current node

rbt_remove_node()

ib_rbt_node_t * rbt_remove_node	(	ib_rbt_t *	tree,
		const ib_rbt_node_t *	const_node
	)

Remove a node from the red black tree, NOTE: This function will not delete the node instance, THAT IS THE CALLERS RESPONSIBILITY.

Returns

the deleted node with the const. in: node to delete, this is a fudge and declared const because the caller has access only to const nodes.

Remove a node from the red black tree, NOTE: This function will not delete the node instance, THAT IS THE CALLERS RESPONSIBILITY.

Returns

deleted node but without the const

Parameters

tree	in: rb tree
const_node	in: node to delete, this is a fudge and declared const because the caller can access only const nodes

rbt_search()

int rbt_search	(	const ib_rbt_t *	tree,
		ib_rbt_bound_t *	parent,
		const void *	key
	)

Search for the key, a node will be returned in parent.last, whether it was found or not.

If not found then parent.last will contain the parent node for the possibly new key otherwise the matching node.

Returns

result of last comparison in: key to search

Search for the key, a node will be returned in parent.last, whether it was found or not.

Returns

value of result

Parameters

tree	in: rb tree
parent	in: search bounds
key	in: key to search

rbt_search_cmp()

int rbt_search_cmp	(	const ib_rbt_t *	tree,
		ib_rbt_bound_t *	parent,
		const void *	key,
		ib_rbt_compare	compare,
		ib_rbt_arg_compare	arg_compare
	)

Search for the key, a node will be returned in parent.last, whether it was found or not.

If not found then parent.last will contain the parent node for the possibly new key otherwise the matching node.

Returns

result of last comparison in: fn to compare items with argument

Search for the key, a node will be returned in parent.last, whether it was found or not.

But use the supplied comparison function.

Returns

value of result

Parameters

tree	in: rb tree
parent	in: search bounds
key	in: key to search
compare	in: fn to compare items
arg_compare	in: fn to compare items with argument

rbt_validate()

bool rbt_validate

(

const ib_rbt_t *

tree

)

Verify the integrity of the RB tree.

For debugging. 0 failure else height of tree (in count of black nodes).

Returns

true if OK false if tree invalid. in: tree to validate

Verify the integrity of the RB tree.

Returns

true if OK false otherwise

Parameters

tree	in: RB tree to validate