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
59typedef void (*ib_rbt_print_node)(
const ib_rbt_node_t* node);
60typedef int (*ib_rbt_compare)(
const void* p1,
const void* p2);
76 ib_rbt_node_t* parent;
93 ib_rbt_compare compare;
109#define rbt_size(t) (t->n_nodes)
112#define rbt_empty(t) (rbt_size(t) == 0)
115#define rbt_value(t, n) ((t*) &n->value[0])
118#define rbt_compare(t, k, n) (t->compare(k, n->value))
135 ib_rbt_compare compare);
167 const ib_rbt_t* tree,
188 ib_rbt_bound_t* parent,
198 const ib_rbt_t* tree);
206 const ib_rbt_t* tree);
214 const ib_rbt_t* tree,
224 const ib_rbt_t* tree,
234 const ib_rbt_t* tree,
243 const ib_rbt_t* tree,
254 const ib_rbt_t* tree,
255 ib_rbt_bound_t* parent,
266 const ib_rbt_t* tree,
267 ib_rbt_bound_t* parent,
269 ib_rbt_compare compare);
285 const ib_rbt_t* src);
307 const ib_rbt_t* tree);
314 const ib_rbt_t* tree,
315 ib_rbt_print_node print);
UNIV_INTERN ib_rbt_node_t * rbt_remove_node(ib_rbt_t *tree, const ib_rbt_node_t *node)
UNIV_INTERN void rbt_free(ib_rbt_t *tree)
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_first(const ib_rbt_t *tree)
UNIV_INTERN void rbt_clear(ib_rbt_t *tree)
UNIV_INTERN const ib_rbt_node_t * rbt_add_node(ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *value)
UNIV_INTERN ibool rbt_validate(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 int rbt_search(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key)
UNIV_INTERN ib_rbt_t * rbt_create(size_t sizeof_value, ib_rbt_compare compare)
UNIV_INTERN const ib_rbt_node_t * rbt_last(const ib_rbt_t *tree)
UNIV_INTERN ulint rbt_merge_uniq(ib_rbt_t *dst, const ib_rbt_t *src)
UNIV_INTERN void rbt_print(const ib_rbt_t *tree, ib_rbt_print_node print)
UNIV_INTERN const ib_rbt_node_t * rbt_upper_bound(const ib_rbt_t *tree, const void *key)
UNIV_INTERN ulint rbt_merge_uniq_destructive(ib_rbt_t *dst, ib_rbt_t *src)
UNIV_INTERN int rbt_search_cmp(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key, ib_rbt_compare compare)
UNIV_INTERN const ib_rbt_node_t * rbt_lower_bound(const ib_rbt_t *tree, const void *key)
UNIV_INTERN ibool rbt_delete(ib_rbt_t *tree, const void *key)
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_insert(ib_rbt_t *tree, const void *key, const void *value)