ut0rbt.cc File Reference

#include "ut0rbt.h"
#include "univ.i"
#include "ut0new.h"

Functions
static ib_rbt_node_t *	ROOT (const ib_rbt_t *t)
	Red-Black tree implementation. More...
static size_t	SIZEOF_NODE (const ib_rbt_t *t)
static bool	rbt_check_ordering (const ib_rbt_t *tree)
	Verify that the keys are in order. More...
static ulint	rbt_count_black_nodes (const ib_rbt_t *tree, const ib_rbt_node_t *node)
	Check that every path from the root to the leaves has the same count. More...
static void	rbt_rotate_left (const ib_rbt_node_t *nil, ib_rbt_node_t *node)
	Turn the node's right child's left sub-tree into node's right sub-tree. More...
static void	rbt_rotate_right (const ib_rbt_node_t *nil, ib_rbt_node_t *node)
	Turn the node's left child's right sub-tree into node's left sub-tree. More...
static ib_rbt_node_t *	rbt_tree_add_child (const ib_rbt_t *tree, ib_rbt_bound_t *parent, ib_rbt_node_t *node)
	Append a node to the tree. More...
static ib_rbt_node_t *	rbt_tree_insert (ib_rbt_t *tree, const void *key, ib_rbt_node_t *node)
	Generic binary tree insert. More...
static void	rbt_balance_tree (const ib_rbt_t *tree, ib_rbt_node_t *node)
	Balance a tree after inserting a node. More...
static ib_rbt_node_t *	rbt_find_successor (const ib_rbt_t *tree, const ib_rbt_node_t *current)
	Find the given node's successor. More...
static ib_rbt_node_t *	rbt_find_predecessor (const ib_rbt_t *tree, const ib_rbt_node_t *current)
	Find the given node's precedecessor. More...
static void	rbt_eject_node (ib_rbt_node_t *eject, ib_rbt_node_t *node)
	Replace node with child. More...
static void	rbt_replace_node (ib_rbt_node_t *replace, ib_rbt_node_t *node)
	Replace a node with another node. More...
static ib_rbt_node_t *	rbt_detach_node (const ib_rbt_t *tree, ib_rbt_node_t *node)
	Detach node from the tree replacing it with one of it's children. More...
static ib_rbt_node_t *	rbt_balance_right (const ib_rbt_node_t *nil, ib_rbt_node_t *parent, ib_rbt_node_t *sibling)
	Rebalance the right sub-tree after deletion. More...
static ib_rbt_node_t *	rbt_balance_left (const ib_rbt_node_t *nil, ib_rbt_node_t *parent, ib_rbt_node_t *sibling)
	Rebalance the left sub-tree after deletion. More...
static void	rbt_remove_node_and_rebalance (ib_rbt_t *tree, ib_rbt_node_t *node)
	Delete the node and rebalance the tree if necessary. More...
static void	rbt_free_node (ib_rbt_node_t *node, ib_rbt_node_t *nil)
	Recursively free the nodes. More...
void	rbt_free (ib_rbt_t *tree)
	Free all the nodes and free the 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...
ib_rbt_t *	rbt_create (size_t sizeof_value, ib_rbt_compare compare)
	Create an instance of a red black tree. More...
const ib_rbt_node_t *	rbt_insert (ib_rbt_t *tree, const void *key, const void *value)
	Generic insert of a value in the rb tree. 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...
static const ib_rbt_node_t *	rbt_lookup (const ib_rbt_t *tree, const void *key)
	Find a matching node in the rb tree. More...
bool	rbt_delete (ib_rbt_t *tree, const void *key)
	Delete a node identified by key. More...
ib_rbt_node_t *	rbt_remove_node (ib_rbt_t *tree, const ib_rbt_node_t *const_node)
	Remove a node from the rb tree, the node is not free'd, that is the callers responsibility. More...
int	rbt_search (const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key)
	Find the node that has the greatest key that is <= key. 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)
	Find the node that has the greatest key that is <= key. More...
const ib_rbt_node_t *	rbt_first (const ib_rbt_t *tree)
	Return the left most node in the tree. More...
const ib_rbt_node_t *	rbt_last (const ib_rbt_t *tree)
	Return the right most 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. More...
const ib_rbt_node_t *	rbt_prev (const ib_rbt_t *tree, const ib_rbt_node_t *current)
	Return the previous node. 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)
	Check that every path from the root to the leaves has the same count and the tree nodes are in order. More...

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

Parameters

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

rbt_balance_left()

static ib_rbt_node_t * rbt_balance_left ( const ib_rbt_node_t *  nil, ib_rbt_node_t *  parent, ib_rbt_node_t *  sibling  )

static

Rebalance the left sub-tree after deletion.

Returns

node to rebalance if more rebalancing required else NULL

Parameters

nil	in: rb tree nil node
parent	in: parent node
sibling	in: sibling node

rbt_balance_right()

static ib_rbt_node_t * rbt_balance_right ( const ib_rbt_node_t *  nil, ib_rbt_node_t *  parent, ib_rbt_node_t *  sibling  )

static

Rebalance the right sub-tree after deletion.

Returns

node to rebalance if more rebalancing required else NULL

Parameters

nil	in: rb tree nil node
parent	in: parent node
sibling	in: sibling node

rbt_balance_tree()

static void rbt_balance_tree ( const ib_rbt_t *  tree, ib_rbt_node_t *  node  )

static

Balance a tree after inserting a node.

Parameters

tree	in: tree to balance
node	in: node that was inserted

rbt_check_ordering()

static bool rbt_check_ordering ( const ib_rbt_t *  tree )

static

Verify that the keys are in order.

Parameters

[in]

tree

tree to verify

Returns

true of OK. false if not ordered

rbt_count_black_nodes()

static ulint rbt_count_black_nodes ( const ib_rbt_t *  tree, const ib_rbt_node_t *  node  )

static

Check that every path from the root to the leaves has the same count.

Count is expressed in the number of black nodes.

Returns

0 on failure else black height of the subtree

Parameters

tree	in: tree to verify
node	in: start of sub-tree

rbt_create()

ib_rbt_t * rbt_create	(	size_t	sizeof_value,
		ib_rbt_compare	compare
	)

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

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

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 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_detach_node()

static ib_rbt_node_t * rbt_detach_node ( const ib_rbt_t *  tree, ib_rbt_node_t *  node  )

static

Detach node from the tree replacing it with one of it's children.

Returns

the child node that now occupies the position of the detached node

Parameters

tree	in: rb tree
node	in: node to detach

rbt_eject_node()

static void rbt_eject_node ( ib_rbt_node_t *  eject, ib_rbt_node_t *  node  )

static

Replace node with child.

After applying transformations eject becomes an orphan.

Parameters

eject	in: node to eject
node	in: node to replace with

rbt_find_predecessor()

static ib_rbt_node_t * rbt_find_predecessor ( const ib_rbt_t *  tree, const ib_rbt_node_t *  current  )

static

Find the given node's precedecessor.

Returns

predecessor node or NULL if no predecessor

Parameters

tree	in: rb tree
current	in: this is declared const because it can be called via rbt_prev()

rbt_find_successor()

static ib_rbt_node_t * rbt_find_successor ( const ib_rbt_t *  tree, const ib_rbt_node_t *  current  )

static

Find the given node's successor.

Returns

successor node or NULL if no successor

Parameters

tree	in: rb tree
current	in: this is declared const because it can be called via rbt_next()

rbt_first()

const ib_rbt_node_t * rbt_first

(

const ib_rbt_t *

tree

)

Return the left most node in the tree.

Return the left most data node in the tree.

rbt_free()

void rbt_free

(

ib_rbt_t *

tree

)

Free all the nodes and free the tree.

Free an instance of a red black tree.

Parameters

tree	in: rb tree to free

rbt_free_node()

static void rbt_free_node ( ib_rbt_node_t *  node, ib_rbt_node_t *  nil  )

static

Recursively free the nodes.

Parameters

node	in: node to free
nil	in: rb tree nil node

rbt_insert()

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

Generic insert of a value in the rb tree.

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

Return the right most data node in the tree.

Returns

the rightmost node or NULL

Parameters

tree	in: rb tree

rbt_lookup()

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

static

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

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

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.

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 previous node.

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 rb tree, the node is not free'd, that is the callers responsibility.

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_remove_node_and_rebalance()

static void rbt_remove_node_and_rebalance ( ib_rbt_t *  tree, ib_rbt_node_t *  node  )

static

Delete the node and rebalance the tree if necessary.

Parameters

tree	in: rb tree
node	in: node to remove

rbt_replace_node()

static void rbt_replace_node ( ib_rbt_node_t *  replace, ib_rbt_node_t *  node  )

static

Replace a node with another node.

Parameters

replace	in: node to replace
node	in: node to replace with

rbt_rotate_left()

static void rbt_rotate_left ( const ib_rbt_node_t *  nil, ib_rbt_node_t *  node  )

static

Turn the node's right child's left sub-tree into node's right sub-tree.

This will also make node's right child it's parent.

Parameters

nil	in: nil node of the tree
node	in: node to rotate

rbt_rotate_right()

static void rbt_rotate_right ( const ib_rbt_node_t *  nil, ib_rbt_node_t *  node  )

static

Turn the node's left child's right sub-tree into node's left sub-tree.

This also make node's left child it's parent.

Parameters

nil	in: nil node of tree
node	in: node to rotate

rbt_search()

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

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

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
	)

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

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_tree_add_child()

static ib_rbt_node_t * rbt_tree_add_child ( const ib_rbt_t *  tree, ib_rbt_bound_t *  parent, ib_rbt_node_t *  node  )

static

Append a node to the tree.

rbt_tree_insert()

static ib_rbt_node_t * rbt_tree_insert ( ib_rbt_t *  tree, const void *  key, ib_rbt_node_t *  node  )

static

Generic binary tree insert.

rbt_validate()

bool rbt_validate

(

const ib_rbt_t *

tree

)

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

Verify the integrity of the RB tree.

Returns

true if OK false otherwise

Parameters

tree	in: RB tree to validate

ROOT()

static ib_rbt_node_t * ROOT ( const ib_rbt_t *  t )

inlinestatic

Red-Black tree implementation.

(c) 2007 Oracle/Innobase Oy

Created 2007-03-20 Sunny Bains

Definition of a red-black tree

A red-black tree is a binary search tree which has the following red-black properties:

1. Every node is either red or black.
2. Every leaf (NULL - in our case tree->nil) is black.
3. If a node is red, then both its children are black.
4. Every simple path from a node to a descendant leaf contains the same number of black nodes.

from (3) above, the implication is that on any path from the root to a leaf, red nodes must not be adjacent.

However, any number of black nodes may appear in a sequence.

SIZEOF_NODE()

static size_t SIZEOF_NODE ( const ib_rbt_t *  t )

inlinestatic