ut0rbt.h File Reference

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

Include dependency graph for ut0rbt.h:

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

Go to the source code of this file.

Data Structures
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

Copyright (c) 2007, 2010, Oracle and/or its affiliates. All Rights Reserved.

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

Enumeration Type Documentation

enum ib_rbt_color_t

Red black tree color types

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

Parameters

tree	in: rb tree
parent	in: parent

UNIV_INTERN void rbt_clear

(

ib_rbt_t *

tree

)

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

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

Parameters

sizeof_value

in: size in bytes

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

Parameters

sizeof_value	in: size in bytes
compare	in: comparator

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

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

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

UNIV_INTERN void rbt_free

(

ib_rbt_t *

tree

)

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

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.

Parameters

tree	in: rb tree
key	in: key for ordering

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

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

Parameters

tree	in: rb tree to search

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

Parameters

tree	in: rb tree

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

Parameters

dst	in: dst rb tree

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

Parameters

dst	in: dst rb tree

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.

Parameters

tree	in: rb tree

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

Parameters

tree	in: rb tree

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

Parameters

tree	in: tree to traverse

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

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.

Parameters

tree	in: rb tree

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

Parameters

tree	in: rb tree
parent	in: search bounds

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

Parameters

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

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

Parameters

tree	in: rb tree

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