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

Include dependency graph for ut0rbt.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	ib_rbt_node_t
struct	ib_rbt_t
struct	ib_rbt_bound_t

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 }

Functions
UNIV_INTERN void	rbt_free (ib_rbt_t *tree)
UNIV_INTERN ib_rbt_t *	rbt_create (size_t sizeof_value, ib_rbt_compare compare)
UNIV_INTERN ib_rbt_t *	rbt_create_arg_cmp (size_t sizeof_value, ib_rbt_arg_compare compare, void *cmp_arg)
UNIV_INTERN ibool	rbt_delete (ib_rbt_t tree, const void key)
UNIV_INTERN ib_rbt_node_t *	rbt_remove_node (ib_rbt_t tree, const ib_rbt_node_t node)
UNIV_INTERN const ib_rbt_node_t *	rbt_lookup (const ib_rbt_t tree, const void key)
UNIV_INTERN const ib_rbt_node_t *	rbt_insert (ib_rbt_t tree, const void key, const void *value)
UNIV_INTERN const ib_rbt_node_t *	rbt_add_node (ib_rbt_t tree, ib_rbt_bound_t parent, const void *value)
UNIV_INTERN const ib_rbt_node_t *	rbt_first (const ib_rbt_t *tree)
UNIV_INTERN const ib_rbt_node_t *	rbt_last (const ib_rbt_t *tree)
UNIV_INTERN const ib_rbt_node_t *	rbt_next (const ib_rbt_t tree, const ib_rbt_node_t current)
UNIV_INTERN const ib_rbt_node_t *	rbt_prev (const ib_rbt_t tree, const ib_rbt_node_t current)
UNIV_INTERN const ib_rbt_node_t *	rbt_lower_bound (const ib_rbt_t tree, const void key)
UNIV_INTERN const ib_rbt_node_t *	rbt_upper_bound (const ib_rbt_t tree, const void key)
UNIV_INTERN int	rbt_search (const ib_rbt_t tree, ib_rbt_bound_t parent, const void *key)
UNIV_INTERN 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)
UNIV_INTERN void	rbt_clear (ib_rbt_t *tree)
UNIV_INTERN ulint	rbt_merge_uniq (ib_rbt_t dst, const ib_rbt_t src)
UNIV_INTERN ulint	rbt_merge_uniq_destructive (ib_rbt_t dst, ib_rbt_t src)
UNIV_INTERN ibool	rbt_validate (const ib_rbt_t *tree)
UNIV_INTERN void	rbt_print (const ib_rbt_t *tree, ib_rbt_print_node print)

Detailed Description

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA

Various utilities

Created 2007-03-20 Sunny Bains

Definition in file ut0rbt.h.

Enumeration Type Documentation

enum ib_rbt_color_t

Red black tree color types

Definition at line 53 of file ut0rbt.h.

Function Documentation

UNIV_INTERN 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

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

Returns: appended node

Parameters

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

Definition at line 861 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN void rbt_clear ( ib_rbt_t * tree )

Clear the tree, deletes (and free's) all the nodes. in: rb tree

Reset the tree. Delete all the nodes.

Parameters

tree	in: rb tree

Definition at line 1214 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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

Create an instance of a red black tree.

Returns: an empty rb tree

Parameters

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

Definition at line 794 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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

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

Returns: an empty rb tree

Parameters

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

Definition at line 771 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN ibool rbt_delete	(	ib_rbt_t *	tree,
		const void *	key
	)

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

Delete a node indentified by key.

Returns: TRUE if success FALSE if not found

Parameters

tree	in: rb tree
key	in: key to delete

Definition at line 934 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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 node in the tree.

Definition at line 1148 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN void rbt_free ( ib_rbt_t * tree )

Free an instance of a red black tree in: rb tree to free

Free all the nodes and free the tree.

Parameters

tree	in: rb tree to free

Definition at line 756 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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.

Generic insert of a value in the rb tree.

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

Definition at line 832 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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 node in the tree.

Returns: the rightmost node or NULL

Parameters

tree	in: rb tree

Definition at line 1169 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN const ib_rbt_node_t* rbt_lookup	(	const ib_rbt_t *	tree,
		const void *	key
	)

Return a node from the red black tree, identified by key, NULL if not found

Returns: node if found else return NULL in: key to lookup

Find a matching node in the rb tree.

Returns: NULL if not found else the node where key was found

Parameters

tree	in: rb tree
key	in: key to use for search

Definition at line 899 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN const ib_rbt_node_t* rbt_lower_bound	(	const ib_rbt_t *	tree,
		const void *	key
	)

Find the node that has the lowest key that is >= key.

Returns: node that satisfies the lower bound constraint or NULL in: key to search

Find the node that has the lowest key that is >= key.

Returns: node satisfying the lower bound constraint or NULL

Parameters

tree	in: rb tree
key	in: key to search

Definition at line 981 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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

Merge the node from dst into src. Return the number of nodes merged.

Returns: no. of recs merged

Parameters

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

Definition at line 1229 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN ulint rbt_merge_uniq_destructive	(	ib_rbt_t *	dst,
		ib_rbt_t *	src
	)

Merge the node from dst into src. Return the number of nodes merged. Delete the nodes from src after copying node to dst. As a side effect the duplicates will be left untouched in the src, since we don't support duplicates (yet). NOTE: src and dst must be similar, the function doesn't check for this condition (yet).

Returns: no. of recs merged in: src rb tree

Merge the node from dst into src. Return the number of nodes merged. Delete the nodes from src after copying node to dst. As a side effect the duplicates will be left untouched in the src.

Returns: no. of recs merged

Parameters

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

Definition at line 1260 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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.

Returns: node next from current

Parameters

tree	in: rb tree
current	in: current node

Definition at line 1189 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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: precedessor node to current that is passed in

Return the previous node.

Returns: node prev from current

Parameters

tree	in: rb tree
current	in: current node

Definition at line 1202 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN void rbt_print	(	const ib_rbt_t *	tree,
		ib_rbt_print_node	print
	)

Iterate over the tree in depth first order. in: print function

Iterate over the tree in depth first order.

Parameters

tree	in: tree to traverse
print	in: print function

Definition at line 1322 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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 rb tree, the node is not free'd, 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

Definition at line 958 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Search for the key, a node will be retuned 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

Find the node that has the greatest key that is <= key.

Returns: value of result

Parameters

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

Definition at line 1063 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN 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 retuned 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

Find the node that has the greatest key that is <= key. 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

Definition at line 1104 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN const ib_rbt_node_t* rbt_upper_bound	(	const ib_rbt_t *	tree,
		const void *	key
	)

Find the node that has the greatest key that is <= key.

Returns: node that satisifies the upper bound constraint or NULL in: key to search

Find the node that has the greatest key that is <= key.

Returns: node satisfying the upper bound constraint or NULL

Parameters

tree	in: rb tree
key	in: key to search

Definition at line 1022 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

UNIV_INTERN ibool 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

Check that every path from the root to the leaves has the same count and the tree nodes are in order.

Returns: TRUE if OK FALSE otherwise

Parameters

tree	in: RB tree to validate

Definition at line 1307 of file ut0rbt.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

Classes

Macros

Typedefs

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

Function Documentation