rbtree.c File Reference

#include <stdio.h>
#include <rz_util/rz_rbtree.h>
#include <rz_util.h>

Go to the source code of this file.

Classes
struct	rcrb_cmp_wrap_t

Typedefs
typedef struct rcrb_cmp_wrap_t	RCRBCmpWrap

Functions
static bool	red (RBNode *x)
static RBNode *	zag (RBNode *x, int dir, RBNodeSum sum)
static RBNode *	zig_zag (RBNode *x, int dir, RBNodeSum sum)
static RBIter	bound_iter (RBNode *x, void *data, RBComparator cmp, bool upper, void *user)
RZ_API bool	rz_rbtree_aug_delete (RBNode **root, void *data, RBComparator cmp, void *cmp_user, RBNodeFree freefn, void *free_user, RBNodeSum sum)
	Returns true if a node with an equal key is deleted. More...
RZ_API bool	rz_rbtree_aug_insert (RBNode **root, void *data, RBNode *node, RBComparator cmp, void *cmp_user, RBNodeSum sum)
	Returns true if the node was inserted successfully. More...
RZ_API bool	rz_rbtree_aug_update_sum (RBNode *root, void *data, RBNode *node, RBComparator cmp, void *cmp_user, RBNodeSum sum)
	Returns true if the sum has been updated, false if node has not been found. More...
RZ_API bool	rz_rbtree_delete (RBNode **root, void *data, RBComparator cmp, void *cmp_user, RBNodeFree freefn, void *free_user)
	Returns true if a node with an equal key is deleted. More...
RZ_API RBNode *	rz_rbtree_find (RBNode *x, void *data, RBComparator cmp, void *user)
RZ_API void	rz_rbtree_free (RZ_NULLABLE RBNode *x, RBNodeFree freefn, void *user)
RZ_API bool	rz_rbtree_insert (RBNode **root, void *data, RBNode *node, RBComparator cmp, void *user)
	Returns true if the node was inserted successfully. More...
RZ_API RBNode *	rz_rbtree_lower_bound (RBNode *x, void *data, RBComparator cmp, void *user)
RZ_API RBIter	rz_rbtree_lower_bound_forward (RBNode *root, void *data, RBComparator cmp, void *user)
RZ_API RBNode *	rz_rbtree_upper_bound (RBNode *x, void *data, RBComparator cmp, void *user)
RZ_API RBIter	rz_rbtree_upper_bound_backward (RBNode *root, void *data, RBComparator cmp, void *user)
static RBIter	_first (RBNode *x, int dir)
RZ_API RBIter	rz_rbtree_first (RBNode *tree)
RZ_API RBIter	rz_rbtree_last (RBNode *tree)
static void	_next (RBIter *it, int dir)
RZ_API void	rz_rbtree_iter_next (RBIter *it)
RZ_API void	rz_rbtree_iter_prev (RBIter *it)
RZ_API RZ_OWN RContRBTree *	rz_rbtree_cont_new (void)
RZ_API RZ_OWN RContRBTree *	rz_rbtree_cont_newf (RContRBFree f)
static int	cont_rbtree_cmp_wrapper (const void *incoming, const RBNode *in_tree, void *user)
static int	cont_rbtree_search_cmp_wrapper (const void *incoming, const RBNode *in_tree, void *user)
static int	cont_rbtree_free_cmp_wrapper (const void *data, const RBNode *in_tree, void *user)
RZ_API bool	rz_rbtree_cont_insert (RContRBTree *tree, void *data, RContRBCmp cmp, void *user)
static void	cont_node_free (RBNode *node, void *user)
RZ_API bool	rz_rbtree_cont_delete (RContRBTree *tree, void *data, RContRBCmp cmp, void *user)
RZ_API void *	rz_rbtree_cont_find (RContRBTree *tree, void *data, RContRBCmp cmp, void *user)
RZ_API void	rz_rbtree_cont_free (RContRBTree *tree)

Typedef Documentation

RCRBCmpWrap

typedef struct rcrb_cmp_wrap_t RCRBCmpWrap

Function Documentation

_first()

static RBIter _first ( RBNode *  x, int  dir  )

static

Definition at line 331 of file rbtree.c.

                                         {
    RBIter it;
    it.len = 0;
    for (; x; x = x->child[dir]) {
        it.path[it.len++] = x;
    }
    return it;
}

References rz_rb_iter_t::len, rz_rb_iter_t::path, and x.

Referenced by rz_rbtree_first(), and rz_rbtree_last().

_next()

static void _next ( RBIter *  it, int  dir  )

inlinestatic

Definition at line 348 of file rbtree.c.

                                              {
    RBNode *x = it->path[--it->len];
    for (x = x->child[!dir]; x; x = x->child[dir]) {
        it->path[it->len++] = x;
    }
}

References rz_rb_iter_t::len, rz_rb_iter_t::path, and x.

Referenced by rz_rbtree_iter_next(), and rz_rbtree_iter_prev().

bound_iter()

static RBIter bound_iter ( RBNode *  x, void *  data, RBComparator  cmp, bool  upper, void *  user  )

inlinestatic

Definition at line 40 of file rbtree.c.

                                                                                                 {
    RBIter it = { 0 };
    while (x) {
        int d = cmp(data, x, user);
 
        if (d == 0) {
            it.path[it.len++] = x;
            return it;
        }
 
        if (d < 0) {
            if (!upper) {
                it.path[it.len++] = x;
            }
            x = x->child[0];
        } else {
            if (upper) {
                it.path[it.len++] = x;
            }
            x = x->child[1];
        }
    }
 
    return it;
}

References cmp(), d, rz_rb_iter_t::len, rz_rb_iter_t::path, and x.

Referenced by rz_rbtree_lower_bound_forward(), and rz_rbtree_upper_bound_backward().

cont_node_free()

static void cont_node_free ( RBNode *  node, void *  user  )

static

Definition at line 435 of file rbtree.c.

                                                     {
    RContRBNode *contnode = container_of(node, RContRBNode, node);
    if (user) {
        ((RContRBFree)user)(contnode->data);
    }
    free(contnode);
}

References container_of, rz_containing_rb_node_t::data, and free().

Referenced by rz_rbtree_cont_delete(), and rz_rbtree_cont_free().

cont_rbtree_cmp_wrapper()

static int cont_rbtree_cmp_wrapper ( const void *  incoming, const RBNode *  in_tree, void *  user  )

static

Definition at line 381 of file rbtree.c.

                                                                                            {
    RCRBCmpWrap *cmp_wrap = (RCRBCmpWrap *)user;
    RContRBNode *incoming_node = (RContRBNode *)incoming;
    RContRBNode *in_tree_node = container_of((RBNode *)in_tree, RContRBNode, node);
    return cmp_wrap->cmp(incoming_node->data, in_tree_node->data, cmp_wrap->user);
}

References rcrb_cmp_wrap_t::cmp, container_of, rz_containing_rb_node_t::data, and rcrb_cmp_wrap_t::user.

Referenced by cont_rbtree_free_cmp_wrapper(), and rz_rbtree_cont_insert().

cont_rbtree_free_cmp_wrapper()

static int cont_rbtree_free_cmp_wrapper ( const void *  data, const RBNode *  in_tree, void *  user  )

static

Definition at line 394 of file rbtree.c.

                                                                                             {
    RCRBCmpWrap *cmp_wrap = (RCRBCmpWrap *)user;
    const int ret = cont_rbtree_cmp_wrapper((void *)data, in_tree, user);
    if (!ret && cmp_wrap->free) { // this is for deleting
        RContRBNode *in_tree_node = container_of((void *)in_tree, RContRBNode, node);
        cmp_wrap->free(in_tree_node->data);
    }
    return ret;
}

References cont_rbtree_cmp_wrapper(), container_of, rz_containing_rb_node_t::data, and rcrb_cmp_wrap_t::free.

Referenced by rz_rbtree_cont_delete().

cont_rbtree_search_cmp_wrapper()

static int cont_rbtree_search_cmp_wrapper ( const void *  incoming, const RBNode *  in_tree, void *  user  )

static

Definition at line 388 of file rbtree.c.

                                                                                                   {
    RCRBCmpWrap *cmp_wrap = (RCRBCmpWrap *)user;
    RContRBNode *in_tree_node = container_of((RBNode *)in_tree, RContRBNode, node);
    return cmp_wrap->cmp((void *)incoming, in_tree_node->data, cmp_wrap->user);
}

References rcrb_cmp_wrap_t::cmp, container_of, rz_containing_rb_node_t::data, and rcrb_cmp_wrap_t::user.

Referenced by rz_rbtree_cont_find().

red()

static bool red ( RBNode *  x )

inlinestatic

Definition at line 9 of file rbtree.c.

                                  {
    return x && x->red;
}

References x.

Referenced by rz_rbtree_aug_delete(), and rz_rbtree_aug_insert().

rz_rbtree_aug_delete()

RZ_API bool rz_rbtree_aug_delete	(	RBNode **	root,
		void *	data,
		RBComparator	cmp,
		void *	cmp_user,
		RBNodeFree	freefn,
		void *	free_user,
		RBNodeSum	sum
	)

Returns true if a node with an equal key is deleted.

Definition at line 67 of file rbtree.c.

                                                                                                                                                 {
    RBNode head, *del = NULL, **del_link = NULL, *g = NULL, *p = NULL, *q = &head, *path[RZ_RBTREE_MAX_HEIGHT];
    int d = 1, d2, dep = 0;
    head.child[0] = NULL;
    head.child[1] = *root;
    while (q->child[d]) {
        d2 = d;
        g = p;
        p = q;
        if (del_link) {
            d = 1;
        } else {
            d = cmp(data, q->child[d2], cmp_user);
            if (d < 0) {
                d = 0;
            } else if (d > 0) {
                d = 1;
            } else {
                del_link = &q->child[d2];
            }
        }
        if (q != &head) {
            if (dep >= RZ_RBTREE_MAX_HEIGHT) {
                RZ_LOG_ERROR("Red-black tree depth is too big\n");
                break;
            }
            path[dep++] = q;
        }
        q = q->child[d2];
        if (q->red || red(q->child[d])) {
            continue;
        }
        if (red(q->child[!d])) {
            if (del_link && *del_link == q) {
                del_link = &q->child[!d]->child[d];
            }
            p->child[d2] = zag(q, !d, sum);
            p = p->child[d2];
            if (dep >= RZ_RBTREE_MAX_HEIGHT) {
                RZ_LOG_ERROR("Red-black tree depth is too big\n");
                break;
            }
            path[dep++] = p;
        } else {
            RBNode *s = p->child[!d2];
            if (!s) {
                continue;
            }
            if (!red(s->child[0]) && !red(s->child[1])) {
                p->red = false;
                q->red = s->red = true;
            } else {
                int d3 = g->child[0] != p;
                RBNode *t;
                if (red(s->child[d2])) {
                    if (del_link && *del_link == p) {
                        del_link = &s->child[d2]->child[d2];
                    }
                    t = zig_zag(p, !d2, sum);
                } else {
                    if (del_link && *del_link == p) {
                        del_link = &s->child[d2];
                    }
                    t = zag(p, !d2, sum);
                }
                t->red = q->red = true;
                t->child[0]->red = t->child[1]->red = false;
                g->child[d3] = t;
                path[dep - 1] = t;
                path[dep++] = p;
            }
        }
    }
    if (del_link) {
        del = *del_link;
        p->child[q != p->child[0]] = q->child[q->child[0] == NULL];
        if (del != q) {
            *q = *del;
            *del_link = q;
        }
        if (freefn) {
            freefn(del, free_user);
        }
    }
    if (sum) {
        while (dep--) {
            sum(path[dep] == del ? q : path[dep]);
        }
    }
    if ((*root = head.child[1])) {
        (*root)->red = false;
    }
    return del;
}

References rz_rb_node_t::child, cmp(), d, d2, d3, del(), freefn(), g, test-lz4-versions::head, NULL, p, path, rz_rb_node_t::red, red(), root, RZ_LOG_ERROR, RZ_RBTREE_MAX_HEIGHT, s, zag(), and zig_zag().

Referenced by rz_analysis_block_merge(), rz_analysis_block_relocate(), rz_analysis_block_unref(), rz_interval_tree_delete(), rz_rbtree_cont_delete(), and rz_rbtree_delete().

rz_rbtree_aug_insert()

RZ_API bool rz_rbtree_aug_insert	(	RBNode **	root,
		void *	data,
		RBNode *	node,
		RBComparator	cmp,
		void *	cmp_user,
		RBNodeSum	sum
	)

Returns true if the node was inserted successfully.

Definition at line 163 of file rbtree.c.

                                                                                                                           {
    node->child[0] = node->child[1] = NULL;
    if (!*root) {
        *root = node;
        node->red = false;
        if (sum) {
            sum(node);
        }
        return true;
    }
    RBNode *t = NULL, *g = NULL, *p = NULL, *q = *root;
    int d = 0, dep = 0;
    bool done = false;
    RBNode *path[RZ_RBTREE_MAX_HEIGHT];
    for (;;) {
        if (!q) {
            q = node;
            q->red = true;
            p->child[d] = q;
            done = true;
        } else if (red(q->child[0]) && red(q->child[1])) {
            q->child[0]->red = q->child[1]->red = false;
            if (q != *root) {
                q->red = true;
            }
        }
        if (q->red && p && p->red) {
            int d3 = t ? t->child[0] != g : -1, d2 = g->child[0] != p;
            if (p->child[d2] == q) {
                g = zag(g, d2, sum);
                dep--;
                path[dep - 1] = g;
            } else {
                g = zig_zag(g, d2, sum);
                dep -= 2;
            }
            if (t) {
                t->child[d3] = g;
            } else {
                *root = g;
            }
        }
        if (done) {
            break;
        }
        d = cmp(data, q, cmp_user);
        t = g;
        g = p;
        p = q;
        if (dep >= RZ_RBTREE_MAX_HEIGHT) {
            RZ_LOG_ERROR("Red-black tree depth is too big\n");
            break;
        }
        path[dep++] = q;
        if (d < 0) {
            d = 0;
            q = q->child[0];
        } else {
            d = 1;
            q = q->child[1];
        }
    }
    if (sum) {
        sum(q);
        while (dep) {
            sum(path[--dep]);
        }
    }
    return done;
}

References rz_rb_node_t::child, cmp(), d, d2, d3, done, g, NULL, p, path, rz_rb_node_t::red, red(), root, RZ_LOG_ERROR, RZ_RBTREE_MAX_HEIGHT, zag(), and zig_zag().

Referenced by rz_analysis_block_relocate(), rz_analysis_block_split(), rz_analysis_create_block(), rz_analysis_var_global_add(), rz_interval_tree_insert(), rz_rbtree_cont_insert(), and rz_rbtree_insert().

rz_rbtree_aug_update_sum()

RZ_API bool rz_rbtree_aug_update_sum	(	RBNode *	root,
		void *	data,
		RBNode *	node,
		RBComparator	cmp,
		void *	cmp_user,
		RBNodeSum	sum
	)

Returns true if the sum has been updated, false if node has not been found.

Definition at line 235 of file rbtree.c.

                                                                                                                              {
    size_t dep = 0;
    RBNode *path[RZ_RBTREE_MAX_HEIGHT];
    RBNode *cur = root;
    for (;;) {
        if (!cur) {
            return false;
        }
        if (dep >= RZ_RBTREE_MAX_HEIGHT) {
            RZ_LOG_ERROR("Red-black tree depth is too big\n");
            return false;
        }
        path[dep] = cur;
        dep++;
        if (cur == node) {
            break;
        }
        int d = cmp(data, cur, cmp_user);
        cur = cur->child[(d < 0) ? 0 : 1];
    }
 
    for (; dep > 0; dep--) {
        sum(path[dep - 1]);
    }
    return true;
}

References rz_rb_node_t::child, cmp(), d, path, root, RZ_LOG_ERROR, and RZ_RBTREE_MAX_HEIGHT.

Referenced by rz_analysis_block_set_size(), and rz_interval_tree_resize().

rz_rbtree_cont_delete()

RZ_API bool rz_rbtree_cont_delete	(	RContRBTree *	tree,
		void *	data,
		RContRBCmp	cmp,
		void *	user
	)

Definition at line 443 of file rbtree.c.

                                                                                             {
    if (!(tree && cmp && tree->root)) {
        return false;
    }
    RCRBCmpWrap cmp_wrap = { cmp, tree->free, user };
    RContRBNode data_wrap = { { { NULL, NULL }, false }, data };
    RBNode *root_node = &tree->root->node;
    const bool ret = rz_rbtree_aug_delete(&root_node, &data_wrap, cont_rbtree_free_cmp_wrapper, &cmp_wrap, cont_node_free, NULL, NULL);
    if (root_node != (&tree->root->node)) {
        tree->root = container_of(root_node, RContRBNode, node);
    }
    return ret;
}

References cmp(), cont_node_free(), cont_rbtree_free_cmp_wrapper(), container_of, rz_containing_rb_tree_t::free, rz_containing_rb_node_t::node, NULL, rz_containing_rb_tree_t::root, and rz_rbtree_aug_delete().

rz_rbtree_cont_find()

RZ_API void* rz_rbtree_cont_find	(	RContRBTree *	tree,
		void *	data,
		RContRBCmp	cmp,
		void *	user
	)

Definition at line 457 of file rbtree.c.

                                                                                            {
    rz_return_val_if_fail(tree && cmp, NULL);
    if (!tree->root) {
        return NULL;
    }
    RCRBCmpWrap cmp_wrap = { cmp, NULL, user };
    // RBNode search_node = tree->root->node;
    RBNode *result_node = rz_rbtree_find(&tree->root->node, data, cont_rbtree_search_cmp_wrapper, &cmp_wrap);
    if (result_node) {
        return (container_of(result_node, RContRBNode, node))->data;
    }
    return NULL;
}

References cmp(), cont_rbtree_search_cmp_wrapper(), container_of, rz_containing_rb_node_t::node, NULL, rz_containing_rb_tree_t::root, rz_rbtree_find(), and rz_return_val_if_fail.

rz_rbtree_cont_free()

RZ_API void rz_rbtree_cont_free

(

RContRBTree *

tree

)

Definition at line 471 of file rbtree.c.

                                                   {
    if (tree && tree->root) {
        rz_rbtree_free(&tree->root->node, cont_node_free, tree->free);
    }
    free(tree);
}

References cont_node_free(), rz_containing_rb_tree_t::free, free(), rz_containing_rb_node_t::node, rz_containing_rb_tree_t::root, and rz_rbtree_free().

rz_rbtree_cont_insert()

RZ_API bool rz_rbtree_cont_insert	(	RContRBTree *	tree,
		void *	data,
		RContRBCmp	cmp,
		void *	user
	)

Definition at line 404 of file rbtree.c.

                                                                                             {
    rz_return_val_if_fail(tree && cmp, false);
    if (!tree->root) {
        tree->root = RZ_NEW0(RContRBNode);
        if (!tree->root) {
            RZ_LOG_ERROR("Failed to allocate new red-black tree root\n");
            return false;
        }
        tree->root->data = data;
        return true;
    }
    RContRBNode *incoming_node = RZ_NEW0(RContRBNode);
    if (!incoming_node) {
        RZ_LOG_ERROR("Failed to allocate new red-black tree node\n");
        return false;
    }
    incoming_node->data = data;
    RCRBCmpWrap cmp_wrap = { cmp, NULL, user };
    RBNode *root_node = &tree->root->node;
    const bool ret = rz_rbtree_aug_insert(&root_node, incoming_node,
        &incoming_node->node, cont_rbtree_cmp_wrapper, &cmp_wrap, NULL);
    if (root_node != (&tree->root->node)) {
        tree->root = container_of(root_node, RContRBNode, node);
    }
    if (!ret) {
        RZ_LOG_ERROR("Failed to insert new red-black tree node\n");
        free(incoming_node);
    }
    return ret;
}

References cmp(), cont_rbtree_cmp_wrapper(), container_of, rz_containing_rb_node_t::data, free(), rz_containing_rb_node_t::node, NULL, rz_containing_rb_tree_t::root, RZ_LOG_ERROR, RZ_NEW0, rz_rbtree_aug_insert(), and rz_return_val_if_fail.

rz_rbtree_cont_new()

RZ_API RZ_OWN RContRBTree* rz_rbtree_cont_new

(

void

)

Definition at line 363 of file rbtree.c.

                                                    {
    return RZ_NEW0(RContRBTree);
}

References RZ_NEW0.

Referenced by rz_rbtree_cont_newf().

rz_rbtree_cont_newf()

RZ_API RZ_OWN RContRBTree* rz_rbtree_cont_newf

(

RContRBFree

f

)

Definition at line 367 of file rbtree.c.

                                                              {
    RContRBTree *tree = rz_rbtree_cont_new();
    if (tree) {
        tree->free = f;
    }
    return tree;
}

References f, rz_containing_rb_tree_t::free, and rz_rbtree_cont_new().

rz_rbtree_delete()

RZ_API bool rz_rbtree_delete	(	RBNode **	root,
		void *	data,
		RBComparator	cmp,
		void *	cmp_user,
		RBNodeFree	freefn,
		void *	free_user
	)

Returns true if a node with an equal key is deleted.

Definition at line 263 of file rbtree.c.

                                                                                                                              {
    return rz_rbtree_aug_delete(root, data, cmp, cmp_user, freefn, free_user, NULL);
}

References cmp(), freefn(), NULL, root, and rz_rbtree_aug_delete().

Referenced by rz_analysis_hint_unset_arch(), rz_analysis_hint_unset_bits(), rz_analysis_var_global_delete(), rz_spaces_rename(), and spaces_unset_single().

rz_rbtree_find()

RZ_API RBNode* rz_rbtree_find	(	RBNode *	x,
		void *	data,
		RBComparator	cmp,
		void *	user
	)

Definition at line 267 of file rbtree.c.

                                                                                   {
    while (x) {
        int d = cmp(data, x, user);
        if (d < 0) {
            x = x->child[0];
        } else if (d > 0) {
            x = x->child[1];
        } else {
            return x;
        }
    }
    return NULL;
}

References cmp(), d, NULL, and x.

Referenced by ensure_ranged_hint_record(), rz_analysis_get_block_at(), rz_analysis_var_global_get_byaddr_at(), rz_bin_pdb_get_type_by_index(), rz_rbtree_cont_find(), and rz_spaces_get().

rz_rbtree_first()

RZ_API RBIter rz_rbtree_first

(

RBNode *

tree

)

Definition at line 340 of file rbtree.c.

                                            {
    return _first(tree, 0);
}

References _first().

Referenced by rz_spaces_is_empty().

rz_rbtree_free()

RZ_API void rz_rbtree_free	(	RZ_NULLABLE RBNode *	x,
		RBNodeFree	freefn,
		void *	user
	)

Definition at line 281 of file rbtree.c.

                                                                                 {
    if (!x) {
        return;
    }
    rz_rbtree_free(x->child[0], freefn, user);
    rz_rbtree_free(x->child[1], freefn, user);
    freefn(x, user);
}

References freefn(), rz_rbtree_free(), and x.

Referenced by free_tpi_stream(), rz_analysis_free(), rz_analysis_hint_storage_fini(), rz_core_analysis_hint_list_print(), rz_core_analysis_hint_print(), rz_interval_tree_fini(), rz_rbtree_cont_free(), rz_rbtree_free(), rz_spaces_fini(), and rz_spaces_purge().

rz_rbtree_insert()

RZ_API bool rz_rbtree_insert	(	RBNode **	root,
		void *	data,
		RBNode *	node,
		RBComparator	cmp,
		void *	user
	)

Returns true if the node was inserted successfully.

Definition at line 291 of file rbtree.c.

                                                                                                    {
    return rz_rbtree_aug_insert(root, data, node, cmp, user, NULL);
}

References cmp(), NULL, root, and rz_rbtree_aug_insert().

Referenced by ensure_ranged_hint_record(), parse_simple_type(), parse_tpi_stream(), print_addr_hint_cb(), print_arch_hint_cb(), print_bits_hint_cb(), rz_spaces_add(), and rz_spaces_rename().

rz_rbtree_iter_next()

RZ_API void rz_rbtree_iter_next

(

RBIter *

it

)

Definition at line 355 of file rbtree.c.

                                            {
    _next(it, 0);
}

References _next().

Referenced by rz_interval_tree_all_at(), and rz_interval_tree_node_at_data().

rz_rbtree_iter_prev()

RZ_API void rz_rbtree_iter_prev

(

RBIter *

it

)

Definition at line 359 of file rbtree.c.

                                            {
    _next(it, 1);
}

References _next().

rz_rbtree_last()

RZ_API RBIter rz_rbtree_last

(

RBNode *

tree

)

Definition at line 344 of file rbtree.c.

                                           {
    return _first(tree, 1);
}

References _first().

rz_rbtree_lower_bound()

RZ_API RBNode* rz_rbtree_lower_bound	(	RBNode *	x,
		void *	data,
		RBComparator	cmp,
		void *	user
	)

Definition at line 295 of file rbtree.c.

                                                                                          {
    RBNode *ret = NULL;
    while (x) {
        int d = cmp(data, x, user);
        if (d <= 0) {
            ret = x;
            x = x->child[0];
        } else {
            x = x->child[1];
        }
    }
    return ret;
}

References cmp(), d, NULL, and x.

Referenced by rz_analysis_hint_del().

rz_rbtree_lower_bound_forward()

RZ_API RBIter rz_rbtree_lower_bound_forward	(	RBNode *	root,
		void *	data,
		RBComparator	cmp,
		void *	user
	)

Definition at line 309 of file rbtree.c.

                                                                                                    {
    return bound_iter(root, data, cmp, false, user);
}

References bound_iter(), cmp(), and root.

rz_rbtree_upper_bound()

RZ_API RBNode* rz_rbtree_upper_bound	(	RBNode *	x,
		void *	data,
		RBComparator	cmp,
		void *	user
	)

Definition at line 313 of file rbtree.c.

                                                                                          {
    void *ret = NULL;
    while (x) {
        int d = cmp(data, x, user);
        if (d < 0) {
            x = x->child[0];
        } else {
            ret = x;
            x = x->child[1];
        }
    }
    return ret;
}

References cmp(), d, NULL, and x.

Referenced by rz_analysis_hint_arch_at(), rz_analysis_hint_bits_at(), and rz_analysis_var_global_get_byaddr_in().

rz_rbtree_upper_bound_backward()

RZ_API RBIter rz_rbtree_upper_bound_backward	(	RBNode *	root,
		void *	data,
		RBComparator	cmp,
		void *	user
	)

Definition at line 327 of file rbtree.c.

                                                                                                     {
    return bound_iter(root, data, cmp, true, user);
}

References bound_iter(), cmp(), and root.

zag()

static RBNode* zag ( RBNode *  x, int  dir, RBNodeSum  sum  )

inlinestatic

Definition at line 13 of file rbtree.c.

                                                             {
    RBNode *y = x->child[dir];
    x->child[dir] = y->child[!dir];
    y->child[!dir] = x;
    x->red = true;
    y->red = false;
    if (sum) {
        sum(x);
    }
    return y;
}

References rz_rb_node_t::child, rz_rb_node_t::red, and x.

Referenced by rz_rbtree_aug_delete(), and rz_rbtree_aug_insert().

zig_zag()

static RBNode* zig_zag ( RBNode *  x, int  dir, RBNodeSum  sum  )

inlinestatic

Definition at line 25 of file rbtree.c.

                                                                 {
    RBNode *y = x->child[dir], *z = y->child[!dir];
    y->child[!dir] = z->child[dir];
    z->child[dir] = y;
    x->child[dir] = z->child[!dir];
    z->child[!dir] = x;
    x->red = y->red = true;
    z->red = false;
    if (sum) {
        sum(x);
        sum(y);
    }
    return z;
}

References rz_rb_node_t::child, rz_rb_node_t::red, and x.

Referenced by rz_rbtree_aug_delete(), and rz_rbtree_aug_insert().