MySQL  8.0.20
Source Code Documentation
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_trbt_create (size_t sizeof_value, ib_rbt_compare compare)
 Create an instance of a red black tree. More...
 
ib_rbt_trbt_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...
 
ibool rbt_delete (ib_rbt_t *tree, const void *key)
 Delete a node from the red black tree, identified by key. More...
 
ib_rbt_node_trbt_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_trbt_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_trbt_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_trbt_first (const ib_rbt_t *tree)
 Return the left most data node in the tree. More...
 
const ib_rbt_node_trbt_last (const ib_rbt_t *tree)
 Return the right most data node in the tree. More...
 
const ib_rbt_node_trbt_next (const ib_rbt_t *tree, const ib_rbt_node_t *current)
 Return the next node from current. More...
 
const ib_rbt_node_trbt_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 retuned 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 retuned 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...
 
ibool 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

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
treein: rb tree
parentin: bounds
valuein: 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_valuein: sizeof data item
comparein: 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_valuein: sizeof data item
comparein: fn to compare items
cmp_argin: compare fn arg

◆ rbt_delete()

ibool 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
treein: rb tree
keyin: 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
treein: 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
treein: rb tree
keyin: key for ordering
valuein: 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
treein: 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
dstin: dst rb tree
srcin: 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
treein: rb tree
currentin: 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
precedessor node to current that is passed in

Return the prev node from current.

Returns
node prev from current
Parameters
treein: rb tree
currentin: 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
treein: rb tree
const_nodein: 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 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

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

Returns
value of result
Parameters
treein: rb tree
parentin: search bounds
keyin: 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 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

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

But use the supplied comparison function.

Returns
value of result
Parameters
treein: rb tree
parentin: search bounds
keyin: key to search
comparein: fn to compare items
arg_comparein: fn to compare items with argument

◆ rbt_validate()

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

Verify the integrity of the RB tree.

Returns
true if OK false otherwise
Parameters
treein: RB tree to validate