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
60 typedef int (*ib_rbt_compare)(
const void* p1,
const void* p2);
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);
269 ib_rbt_compare compare);
315 ib_rbt_print_node print);
UNIV_INTERN void rbt_clear(ib_rbt_t *tree)
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_last(const ib_rbt_t *tree)
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_lookup(const ib_rbt_t *tree, const void *key)
UNIV_INTERN void rbt_print(const ib_rbt_t *tree, 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 ibool rbt_delete(ib_rbt_t *tree, const void *key)
UNIV_INTERN ib_rbt_t * rbt_create(size_t sizeof_value, ib_rbt_compare compare)
UNIV_INTERN ibool rbt_validate(const ib_rbt_t *tree)
UNIV_INTERN ulint rbt_merge_uniq_destructive(ib_rbt_t *dst, ib_rbt_t *src)
UNIV_INTERN ulint rbt_merge_uniq(ib_rbt_t *dst, const ib_rbt_t *src)
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_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 const ib_rbt_node_t * rbt_first(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 void rbt_free(ib_rbt_t *tree)