rz_rbtree.h File Reference

#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include "rz_list.h"

Go to the source code of this file.

Classes
struct	rz_rb_node_t
struct	rz_rb_iter_t
struct	rz_containing_rb_node_t
struct	rz_containing_rb_tree_t

Macros
#define	RZ_RBTREE_MAX_HEIGHT   62
#define	rz_rbtree_iter_get(it, struc, rb)   (container_of((it)->path[(it)->len - 1], struc, rb))
#define	rz_rbtree_iter_has(it)   ((it)->len)
#define	rz_rbtree_iter_while(it, data, struc, rb)    for (; rz_rbtree_iter_has(&it) && (data = rz_rbtree_iter_get(&it, struc, rb)); rz_rbtree_iter_next(&(it)))
#define	rz_rbtree_iter_while_prev(it, data, struc, rb)    for (; rz_rbtree_iter_has(&it) && (data = rz_rbtree_iter_get(&it, struc, rb)); rz_rbtree_iter_prev(&(it)))
#define	rz_rbtree_foreach(root, it, data, struc, rb)    for ((it) = rz_rbtree_first(root); rz_rbtree_iter_has(&it) && (data = rz_rbtree_iter_get(&it, struc, rb)); rz_rbtree_iter_next(&(it)))
#define	rz_rbtree_foreach_prev(root, it, data, struc, rb)    for ((it) = rz_rbtree_last(root); rz_rbtree_iter_has(&it) && (data = rz_rbtree_iter_get(&it, struc, rb)); rz_rbtree_iter_prev(&(it)))
#define	rz_rbtree_cont_foreach(tree, it, dat)    for ((it) = rz_rbtree_first((tree)->root ? &(tree)->root->node : NULL); rz_rbtree_iter_has(&it) && (dat = rz_rbtree_iter_get(&it, RContRBNode, node)->data); rz_rbtree_iter_next(&(it)))
#define	rz_rbtree_cont_foreach_prev(tree, it, dat)    for ((it) = rz_rbtree_last((tree)->root ? &(tree)->root->node : NULL); rz_rbtree_iter_has(&it) && (dat = rz_rbtree_iter_get(&it, RContRBNode, node)->data); rz_rbtree_iter_prev(&(it)))

Typedefs
typedef struct rz_rb_node_t	RBNode
typedef RBNode *	RBTree
typedef int(*	RBComparator) (const void *incoming, const RBNode *in_tree, void *user)
typedef void(*	RBNodeFree) (RBNode *node, void *user)
typedef void(*	RBNodeSum) (RBNode *node)
typedef struct rz_rb_iter_t	RBIter
typedef int(*	RContRBCmp) (void *incoming, void *in, void *user)
typedef void(*	RContRBFree) (void *)
typedef struct rz_containing_rb_node_t	RContRBNode
typedef struct rz_containing_rb_tree_t	RContRBTree

Functions
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 *root, void *data, RBComparator cmp, void *user)
RZ_API void	rz_rbtree_free (RZ_NULLABLE RBNode *root, 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 *root, void *data, RBComparator cmp, void *user)
RZ_API RBNode *	rz_rbtree_upper_bound (RBNode *root, void *data, RBComparator cmp, void *user)
RZ_API RBIter	rz_rbtree_first (RBNode *root)
RZ_API RBIter	rz_rbtree_last (RBNode *root)
RZ_API RBIter	rz_rbtree_lower_bound_forward (RBNode *root, void *data, RBComparator cmp, void *user)
RZ_API RBIter	rz_rbtree_upper_bound_backward (RBNode *root, void *data, RBComparator cmp, void *user)
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)
RZ_API bool	rz_rbtree_cont_insert (RContRBTree *tree, void *data, RContRBCmp cmp, 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)

Macro Definition Documentation

rz_rbtree_cont_foreach

#define rz_rbtree_cont_foreach	(		tree,
			it,
			dat
	)		for ((it) = rz_rbtree_first((tree)->root ? &(tree)->root->node : NULL); rz_rbtree_iter_has(&it) && (dat = rz_rbtree_iter_get(&it, RContRBNode, node)->data); rz_rbtree_iter_next(&(it)))

Definition at line 113 of file rz_rbtree.h.

rz_rbtree_cont_foreach_prev

#define rz_rbtree_cont_foreach_prev	(		tree,
			it,
			dat
	)		for ((it) = rz_rbtree_last((tree)->root ? &(tree)->root->node : NULL); rz_rbtree_iter_has(&it) && (dat = rz_rbtree_iter_get(&it, RContRBNode, node)->data); rz_rbtree_iter_prev(&(it)))

Definition at line 116 of file rz_rbtree.h.

rz_rbtree_foreach

#define rz_rbtree_foreach	(		root,
			it,
			data,
			struc,
			rb
	)		for ((it) = rz_rbtree_first(root); rz_rbtree_iter_has(&it) && (data = rz_rbtree_iter_get(&it, struc, rb)); rz_rbtree_iter_next(&(it)))

Definition at line 101 of file rz_rbtree.h.

rz_rbtree_foreach_prev

#define rz_rbtree_foreach_prev	(		root,
			it,
			data,
			struc,
			rb
	)		for ((it) = rz_rbtree_last(root); rz_rbtree_iter_has(&it) && (data = rz_rbtree_iter_get(&it, struc, rb)); rz_rbtree_iter_prev(&(it)))

Definition at line 104 of file rz_rbtree.h.

rz_rbtree_iter_get

#define rz_rbtree_iter_get	(		it,
			struc,
			rb
	)		(container_of((it)->path[(it)->len - 1], struc, rb))

Definition at line 85 of file rz_rbtree.h.

rz_rbtree_iter_has

#define rz_rbtree_iter_has

(

it

)

((it)->len)

Definition at line 87 of file rz_rbtree.h.

rz_rbtree_iter_while

#define rz_rbtree_iter_while	(		it,
			data,
			struc,
			rb
	)		for (; rz_rbtree_iter_has(&it) && (data = rz_rbtree_iter_get(&it, struc, rb)); rz_rbtree_iter_next(&(it)))

Definition at line 94 of file rz_rbtree.h.

rz_rbtree_iter_while_prev

#define rz_rbtree_iter_while_prev	(		it,
			data,
			struc,
			rb
	)		for (; rz_rbtree_iter_has(&it) && (data = rz_rbtree_iter_get(&it, struc, rb)); rz_rbtree_iter_prev(&(it)))

Definition at line 98 of file rz_rbtree.h.

RZ_RBTREE_MAX_HEIGHT

#define RZ_RBTREE_MAX_HEIGHT   62

Definition at line 16 of file rz_rbtree.h.

Typedef Documentation

RBComparator

typedef int(* RBComparator) (const void *incoming, const RBNode *in_tree, void *user)

Definition at line 29 of file rz_rbtree.h.

RBIter

typedef struct rz_rb_iter_t RBIter

RBNode

typedef struct rz_rb_node_t RBNode

RBNodeFree

typedef void(* RBNodeFree) (RBNode *node, void *user)

Definition at line 31 of file rz_rbtree.h.

RBNodeSum

typedef void(* RBNodeSum) (RBNode *node)

Definition at line 32 of file rz_rbtree.h.

RBTree

typedef RBNode* RBTree

Definition at line 24 of file rz_rbtree.h.

RContRBCmp

typedef int(* RContRBCmp) (void *incoming, void *in, void *user)

Definition at line 46 of file rz_rbtree.h.

RContRBFree

typedef void(* RContRBFree) (void *)

Definition at line 47 of file rz_rbtree.h.

RContRBNode

typedef struct rz_containing_rb_node_t RContRBNode

RContRBTree

typedef struct rz_containing_rb_tree_t RContRBTree

Function Documentation

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 *	root,
		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 *

root

)

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 *	root,
		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 *

root

)

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 *	root,
		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 *	root,
		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.