 |
MySQL
8.0.23
Source Code Documentation
|
Go to the documentation of this file.
32 #ifndef INNOBASE_UT0RBT_H
33 #define INNOBASE_UT0RBT_H
35 #if !defined(IB_RBT_TESTING)
44 #define ut_malloc malloc
46 #define ulint unsigned long
47 #define ut_a(c) assert(c)
48 #define ut_error assert(0)
49 #define ibool unsigned int
103 #define rbt_size(t) (t->n_nodes)
106 #define rbt_empty(t) (rbt_size(t) == 0)
109 #define rbt_value(t, n) ((t *)&n->value[0])
112 #define rbt_compare(t, k, n) (t->compare(k, n->value))
189 #if defined UNIV_DEBUG || defined IB_RBT_TESTING
ulint n_nodes
Definition: ut0rbt.h:83
ulint rbt_merge_uniq(ib_rbt_t *dst, const ib_rbt_t *src)
Merge the node from dst into src.
Definition: ut0rbt.cc:951
ib_rbt_node_t * root
Definition: ut0rbt.h:79
@ IB_RBT_BLACK
Definition: ut0rbt.h:60
ulint sizeof_value
Definition: ut0rbt.h:88
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.
Definition: ut0rbt.cc:656
ib_rbt_compare compare
Definition: ut0rbt.h:85
ib_rbt_t * rbt_create(size_t sizeof_value, ib_rbt_compare compare)
Create an instance of a red black tree.
Definition: ut0rbt.cc:674
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.
Definition: ut0rbt.cc:830
ib_rbt_node_t * nil
Definition: ut0rbt.h:75
ib_rbt_color_t
Red black tree color types.
Definition: ut0rbt.h:60
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,...
Definition: ut0rbt.cc:811
const string value("\"Value\"")
static const char * key
Definition: suite_stubs.c:14
ib_rbt_node_t * left
Definition: ut0rbt.h:66
ib_rbt_node_t * parent
Definition: ut0rbt.h:68
int(* ib_rbt_compare)(const void *p1, const void *p2)
Definition: ut0rbt.h:56
The result of searching for a key in the tree, this is useful for a speedy lookup and insert if key d...
Definition: ut0rbt.h:94
int result
Definition: ut0rbt.h:97
const ib_rbt_node_t * rbt_prev(const ib_rbt_t *tree, const ib_rbt_node_t *current)
Return the prev node from current.
Definition: ut0rbt.cc:942
Red black tree node.
Definition: ut0rbt.h:63
const ib_rbt_node_t * last
Definition: ut0rbt.h:95
Red black tree instance.
Definition: ut0rbt.h:74
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.
Definition: ut0rbt.cc:865
const ib_rbt_node_t * rbt_first(const ib_rbt_t *tree)
Return the left most data node in the tree.
Definition: ut0rbt.cc:901
ib_rbt_color_t color
Definition: ut0rbt.h:64
@ IB_RBT_RED
Definition: ut0rbt.h:60
void rbt_free(ib_rbt_t *tree)
Free an instance of a red black tree.
Definition: ut0rbt.cc:646
static int compare(size_t a, size_t b)
Function to compare two size_t integers for their relative order.
Definition: rpl_utility.cc:104
int(* ib_rbt_arg_compare)(const void *, const void *p1, const void *p2)
Definition: ut0rbt.h:57
char value[1]
Definition: ut0rbt.h:70
ib_rbt_node_t * right
Definition: ut0rbt.h:67
ib_rbt_arg_compare compare_with_arg
Definition: ut0rbt.h:86
void(* ib_rbt_print_node)(const ib_rbt_node_t *node)
Definition: ut0rbt.h:55
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.
Definition: ut0rbt.cc:729
void * cmp_arg
Definition: ut0rbt.h:89
const ib_rbt_node_t * rbt_next(const ib_rbt_t *tree, const ib_rbt_node_t *current)
Return the next node from current.
Definition: ut0rbt.cc:933
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!)
Definition: ut0rbt.cc:704
ibool rbt_validate(const ib_rbt_t *tree)
Verify the integrity of the RB tree.
Definition: ut0rbt.cc:976
const ib_rbt_node_t * rbt_last(const ib_rbt_t *tree)
Return the right most data node in the tree.
Definition: ut0rbt.cc:918
ibool rbt_delete(ib_rbt_t *tree, const void *key)
Delete a node from the red black tree, identified by key.
Definition: ut0rbt.cc:792