Interval Tree

Classes
struct	_wmem_range_t

Typedefs
typedef struct _wmem_tree_t	wmem_itree_t

Functions
WS_DLL_PUBLIC wmem_itree_t *	wmem_itree_new (wmem_allocator_t *allocator) G_GNUC_MALLOC
WS_DLL_PUBLIC bool	wmem_itree_is_empty (wmem_itree_t *tree)
WS_DLL_PUBLIC void	wmem_itree_insert (wmem_itree_t *tree, const uint64_t low, const uint64_t high, void *data)
WS_DLL_PUBLIC wmem_list_t *	wmem_itree_find_intervals (wmem_itree_t *tree, wmem_allocator_t *allocator, uint64_t low, uint64_t high)
void	wmem_print_itree (wmem_itree_t *tree)

Detailed Description

http://www.geeksforgeeks.org/interval-tree/ The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc ... to maintain a set of intervals so that all operations can be done in O(Logn) time.

Following wikipedia's convention this is an augmented tree rather then an interval tree http://www.wikiwand.com/en/Interval_tree

Function Documentation

wmem_itree_insert()

WS_DLL_PUBLIC void wmem_itree_insert	(	wmem_itree_t *	tree,
		const uint64_t	low,
		const uint64_t	high,
		void *	data
	)

Inserts a range low-high indexed by "low" in O(log(n)). As in wmem_tree, if a key "low" already exists, it will be overwritten with the new data

wmem_itree_is_empty()

WS_DLL_PUBLIC bool wmem_itree_is_empty

(

wmem_itree_t *

tree

)

Returns true if the tree is empty (has no nodes).

wmem_print_itree()

void wmem_print_itree

(

wmem_itree_t *

tree

)

Print ranges along the tree