rz_intervaltree.h File Reference

#include "rz_rbtree.h"
#include "../rz_types.h"

Go to the source code of this file.

Classes
struct	rz_interval_node_t
struct	rz_interval_tree_t

Macros
#define	rz_interval_tree_foreach(tree, it, dat)    for ((it) = rz_rbtree_first(&(tree)->root->node); rz_rbtree_iter_has(&it) && (dat = rz_interval_tree_iter_get(&it)->data); rz_rbtree_iter_next(&(it)))
#define	rz_interval_tree_foreach_prev(tree, it, dat)    for ((it) = rz_rbtree_last(&(tree)->root->node); rz_rbtree_iter_has(&it) && (dat = rz_rbtree_iter_get(&it, RzIntervalNode, node)->data); rz_rbtree_iter_prev(&(it)))

Typedefs
typedef struct rz_interval_node_t	RzIntervalNode
typedef void(*	RzIntervalNodeFree) (void *data)
typedef struct rz_interval_tree_t	RzIntervalTree
typedef bool(*	RzIntervalIterCb) (RzIntervalNode *node, void *user)
typedef RBIter	RzIntervalTreeIter

Functions
RZ_API void	rz_interval_tree_init (RzIntervalTree *tree, RzIntervalNodeFree free)
RZ_API void	rz_interval_tree_fini (RzIntervalTree *tree)
RZ_API bool	rz_interval_tree_insert (RzIntervalTree *tree, ut64 start, ut64 end, void *data)
RZ_API bool	rz_interval_tree_delete (RzIntervalTree *tree, RzIntervalNode *node, bool free)
RZ_API bool	rz_interval_tree_resize (RzIntervalTree *tree, RzIntervalNode *node, ut64 new_start, ut64 new_end)
RZ_API RBIter	rz_interval_tree_first_at (RzIntervalTree *tree, ut64 start)
RZ_API RzIntervalNode *	rz_interval_tree_node_at (RzIntervalTree *tree, ut64 start)
RZ_API RzIntervalNode *	rz_interval_tree_node_at_data (RzIntervalTree *tree, ut64 start, void *data)
static void *	rz_interval_tree_at (RzIntervalTree *tree, ut64 start)
RZ_API bool	rz_interval_tree_all_at (RzIntervalTree *tree, ut64 start, RzIntervalIterCb cb, void *user)
RZ_API bool	rz_interval_tree_all_in (RzIntervalTree *tree, ut64 value, bool end_inclusive, RzIntervalIterCb cb, void *user)
RZ_API bool	rz_interval_tree_all_intersect (RzIntervalTree *tree, ut64 start, ut64 end, bool end_inclusive, RzIntervalIterCb cb, void *user)
static RzIntervalNode *	rz_interval_tree_iter_get (RzIntervalTreeIter *it)
static bool	rz_interval_tree_empty (RzIntervalTree *tree)

Macro Definition Documentation

rz_interval_tree_foreach

#define rz_interval_tree_foreach	(		tree,
			it,
			dat
	)		for ((it) = rz_rbtree_first(&(tree)->root->node); rz_rbtree_iter_has(&it) && (dat = rz_interval_tree_iter_get(&it)->data); rz_rbtree_iter_next(&(it)))

Definition at line 95 of file rz_intervaltree.h.

rz_interval_tree_foreach_prev

#define rz_interval_tree_foreach_prev	(		tree,
			it,
			dat
	)		for ((it) = rz_rbtree_last(&(tree)->root->node); rz_rbtree_iter_has(&it) && (dat = rz_rbtree_iter_get(&it, RzIntervalNode, node)->data); rz_rbtree_iter_prev(&(it)))

Definition at line 98 of file rz_intervaltree.h.

Typedef Documentation

RzIntervalIterCb

typedef bool(* RzIntervalIterCb) (RzIntervalNode *node, void *user)

Definition at line 72 of file rz_intervaltree.h.

RzIntervalNode

typedef struct rz_interval_node_t RzIntervalNode

RzIntervalNodeFree

typedef void(* RzIntervalNodeFree) (void *data)

Definition at line 31 of file rz_intervaltree.h.

RzIntervalTree

typedef struct rz_interval_tree_t RzIntervalTree

RzIntervalTreeIter

typedef RBIter RzIntervalTreeIter

Definition at line 85 of file rz_intervaltree.h.

Function Documentation

rz_interval_tree_all_at()

RZ_API bool rz_interval_tree_all_at	(	RzIntervalTree *	tree,
		ut64	start,
		RzIntervalIterCb	cb,
		void *	user
	)

Definition at line 221 of file intervaltree.c.

                                                                                                       {
    RBIter it = rz_interval_tree_first_at(tree, start);
    bool ret = true;
    while (rz_rbtree_iter_has(&it)) {
        RzIntervalNode *intervalnode = rz_rbtree_iter_get(&it, RzIntervalNode, node);
        if (intervalnode->start != start) {
            break;
        }
        ret = cb(intervalnode, user);
        if (!ret) {
            break;
        }
        rz_rbtree_iter_next(&it);
    }
    return ret;
}

References cb, rz_interval_tree_first_at(), rz_rbtree_iter_get, rz_rbtree_iter_has, rz_rbtree_iter_next(), rz_interval_node_t::start, and start.

Referenced by collect_nodes_at(), and find_node_at().

rz_interval_tree_all_in()

RZ_API bool rz_interval_tree_all_in	(	RzIntervalTree *	tree,
		ut64	value,
		bool	end_inclusive,
		RzIntervalIterCb	cb,
		void *	user
	)

Definition at line 262 of file intervaltree.c.

                                                                                                                           {
    // all in! 🂡
    return rz_interval_node_all_in(tree->root, value, end_inclusive, cb, user);
}

References cb, rz_interval_tree_t::root, rz_interval_node_all_in(), and value.

Referenced by collect_nodes_in(), find_node_in(), and rz_reg_filter_items_covered().

rz_interval_tree_all_intersect()

RZ_API bool rz_interval_tree_all_intersect	(	RzIntervalTree *	tree,
		ut64	start,
		ut64	end,
		bool	end_inclusive,
		RzIntervalIterCb	cb,
		void *	user
	)

Definition at line 291 of file intervaltree.c.

                                                                                                                                            {
    return rz_interval_node_all_intersect(tree->root, start, end, end_inclusive, cb, user);
}

References cb, test_evm::end, rz_interval_tree_t::root, rz_interval_node_all_intersect(), and start.

Referenced by collect_nodes_intersect().

rz_interval_tree_at()

static void* rz_interval_tree_at ( RzIntervalTree *  tree, ut64  start  )

inlinestatic

Definition at line 67 of file rz_intervaltree.h.

                                                                          {
    RzIntervalNode *node = rz_interval_tree_node_at(tree, start);
    return node ? node->data : NULL;
}

References rz_interval_node_t::data, NULL, rz_interval_tree_node_at(), and start.

rz_interval_tree_delete()

RZ_API bool rz_interval_tree_delete	(	RzIntervalTree *	tree,
		RzIntervalNode *	node,
		bool	free
	)

Definition at line 139 of file intervaltree.c.

                                                                                           {
    RBNode *root = &tree->root->node;
    RBIter path_cache = { 0 };
    bool r = rz_rbtree_aug_delete(&root, node, cmp_exact_node, &path_cache, interval_node_free, free ? tree->free : NULL, node_max);
    tree->root = unwrap(root);
    return r;
}

References cmp_exact_node(), rz_interval_tree_t::free, free(), interval_node_free(), rz_interval_node_t::node, node_max(), NULL, r, rz_interval_tree_t::root, root, rz_rbtree_aug_delete(), and unwrap.

Referenced by del(), and rz_interval_tree_resize().

rz_interval_tree_empty()

static bool rz_interval_tree_empty ( RzIntervalTree *  tree )

inlinestatic

Definition at line 91 of file rz_intervaltree.h.

                                                                {
    return tree->root == NULL;
}

References NULL, and rz_interval_tree_t::root.

Referenced by rz_serialize_analysis_meta_save().

rz_interval_tree_fini()

RZ_API void rz_interval_tree_fini

(

RzIntervalTree *

tree

)

Definition at line 114 of file intervaltree.c.

                                                        {
    if (!tree || !tree->root) {
        return;
    }
    rz_rbtree_free(&tree->root->node, interval_node_free, tree->free);
}

References rz_interval_tree_t::free, interval_node_free(), rz_interval_node_t::node, rz_interval_tree_t::root, and rz_rbtree_free().

Referenced by rz_analysis_free(), rz_analysis_purge(), rz_meta_rebase(), and rz_reg_filter_items_covered().

rz_interval_tree_first_at()

RZ_API RBIter rz_interval_tree_first_at	(	RzIntervalTree *	tree,
		ut64	start
	)

Definition at line 183 of file intervaltree.c.

                                                                          {
    RBIter it = { 0 };
 
    // Find the topmost node matching start so we have a sub-tree with all entries that we want to find.
    RzIntervalNode *top_intervalnode = rz_interval_tree_node_at(tree, start);
    if (!top_intervalnode) {
        return it;
    }
 
    // If there are more nodes with the same key, they can be in both children.
    RBNode *node = &top_intervalnode->node;
    while (node) {
        if (start <= unwrap(node)->start) {
            it.path[it.len++] = node;
            node = node->child[0];
        } else {
            node = node->child[1];
        }
    }
 
    return it;
}

References rz_rb_node_t::child, rz_rb_iter_t::len, rz_interval_node_t::node, rz_rb_iter_t::path, rz_interval_tree_node_at(), start, and unwrap.

Referenced by rz_interval_tree_all_at(), and rz_interval_tree_node_at_data().

rz_interval_tree_init()

RZ_API void rz_interval_tree_init	(	RzIntervalTree *	tree,
		RzIntervalNodeFree	free
	)

Definition at line 101 of file intervaltree.c.

                                                                                 {
    tree->root = NULL;
    tree->free = free;
}

References rz_interval_tree_t::free, free(), NULL, and rz_interval_tree_t::root.

Referenced by rz_analysis_new(), rz_analysis_purge(), rz_meta_rebase(), and rz_reg_filter_items_covered().

rz_interval_tree_insert()

RZ_API bool rz_interval_tree_insert	(	RzIntervalTree *	tree,
		ut64	start,
		ut64	end,
		void *	data
	)

Definition at line 121 of file intervaltree.c.

                                                                                            {
    rz_return_val_if_fail(end >= start, false);
    RzIntervalNode *node = RZ_NEW0(RzIntervalNode);
    if (!node) {
        return false;
    }
    node->start = start;
    node->end = end;
    node->data = data;
    RBNode *root = tree->root ? &tree->root->node : NULL;
    bool r = rz_rbtree_aug_insert(&root, &start, &node->node, cmp, NULL, node_max);
    tree->root = unwrap(root);
    if (!r) {
        free(node);
    }
    return r;
}

References cmp(), rz_interval_node_t::data, rz_interval_node_t::end, test_evm::end, free(), rz_interval_node_t::node, node_max(), NULL, r, rz_interval_tree_t::root, root, RZ_NEW0, rz_rbtree_aug_insert(), rz_return_val_if_fail, rz_interval_node_t::start, start, and unwrap.

Referenced by meta_load_cb(), meta_set(), rz_interval_tree_resize(), rz_meta_rebase(), and rz_reg_filter_items_covered().

rz_interval_tree_iter_get()

static RzIntervalNode* rz_interval_tree_iter_get ( RzIntervalTreeIter *  it )

inlinestatic

Definition at line 87 of file rz_intervaltree.h.

                                                                                {
    return rz_rbtree_iter_get(it, RzIntervalNode, node);
}

References rz_rbtree_iter_get.

Referenced by DEFINE_HANDLE_TS_FCN_AND_SYMBOL(), del(), print_meta_list(), rz_core_cmd_foreach3(), rz_core_visual_comments(), rz_core_visual_hudstuff(), rz_meta_get_size(), rz_meta_rebase(), and rz_serialize_analysis_meta_save().

rz_interval_tree_node_at()

RZ_API RzIntervalNode* rz_interval_tree_node_at	(	RzIntervalTree *	tree,
		ut64	start
	)

Definition at line 169 of file intervaltree.c.

                                                                                  {
    RzIntervalNode *node = tree->root;
    while (node) {
        if (start < node->start) {
            node = unwrap(node->node.child[0]);
        } else if (start > node->start) {
            node = unwrap(node->node.child[1]);
        } else {
            return node;
        }
    }
    return NULL;
}

References rz_rb_node_t::child, rz_interval_node_t::node, NULL, rz_interval_tree_t::root, rz_interval_node_t::start, start, and unwrap.

Referenced by rz_interval_tree_at(), and rz_interval_tree_first_at().

rz_interval_tree_node_at_data()

RZ_API RzIntervalNode* rz_interval_tree_node_at_data	(	RzIntervalTree *	tree,
		ut64	start,
		void *	data
	)

Definition at line 206 of file intervaltree.c.

                                                                                                   {
    RBIter it = rz_interval_tree_first_at(tree, start);
    while (rz_rbtree_iter_has(&it)) {
        RzIntervalNode *intervalnode = rz_rbtree_iter_get(&it, RzIntervalNode, node);
        if (intervalnode->start != start) {
            break;
        }
        if (intervalnode->data == data) {
            return intervalnode;
        }
        rz_rbtree_iter_next(&it);
    }
    return NULL;
}

References rz_interval_node_t::data, NULL, rz_interval_tree_first_at(), rz_rbtree_iter_get, rz_rbtree_iter_has, rz_rbtree_iter_next(), rz_interval_node_t::start, and start.

rz_interval_tree_resize()

RZ_API bool rz_interval_tree_resize	(	RzIntervalTree *	tree,
		RzIntervalNode *	node,
		ut64	new_start,
		ut64	new_end
	)

Definition at line 147 of file intervaltree.c.

                                                                                                              {
    rz_return_val_if_fail(new_end >= new_start, false);
    if (node->start != new_start) {
        // Start change means the tree needs a different structure
        void *data = node->data;
        if (!rz_interval_tree_delete(tree, node, false)) {
            return false;
        }
        return rz_interval_tree_insert(tree, new_start, new_end, data);
    }
    if (node->end != new_end) {
        // Only end change just needs the updated augmented max value to be propagated upwards
        node->end = new_end;
        RBIter path_cache = { 0 };
        return rz_rbtree_aug_update_sum(&tree->root->node, node, &node->node, cmp_exact_node, &path_cache, node_max);
    }
    // no change
    return true;
}

References cmp_exact_node(), rz_interval_node_t::data, rz_interval_node_t::end, rz_interval_node_t::node, node_max(), rz_interval_tree_t::root, rz_interval_tree_delete(), rz_interval_tree_insert(), rz_rbtree_aug_update_sum(), rz_return_val_if_fail, and rz_interval_node_t::start.

Referenced by meta_set().