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
	Create a new interval tree using the specified memory allocator.
WS_DLL_PUBLIC bool	wmem_itree_is_empty (wmem_itree_t *tree)
	Check whether an interval tree is empty.
WS_DLL_PUBLIC void	wmem_itree_insert (wmem_itree_t *tree, const uint64_t low, const uint64_t high, void *data)
	Insert an interval into the interval tree.
WS_DLL_PUBLIC wmem_list_t *	wmem_itree_find_intervals (wmem_itree_t *tree, wmem_allocator_t *allocator, uint64_t low, uint64_t high)
	Find all intervals overlapping a given range in an interval tree.
void	wmem_print_itree (wmem_itree_t *tree)
	Print all intervals stored in the interval 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 than an interval tree http://www.wikiwand.com/en/Interval_tree

Function Documentation

wmem_itree_find_intervals()

WS_DLL_PUBLIC wmem_list_t * wmem_itree_find_intervals	(	wmem_itree_t *	tree,
		wmem_allocator_t *	allocator,
		uint64_t	low,
		uint64_t	high
	)

Find all intervals overlapping a given range in an interval tree.

Searches the specified wmem_itree_t for all intervals that overlap with the range [low, high], and stores the results in a newly allocated wmem_list_t using the provided allocator. The list is always created, even if no matching intervals are found.

Parameters

tree	Pointer to the interval tree to search.
allocator	Memory allocator used to allocate the result list.
low	Lower bound of the search range (inclusive).
high	Upper bound of the search range (inclusive).

Returns

A pointer to a wmem_list_t containing all overlapping intervals.

wmem_itree_insert()

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

Insert an interval into the interval tree.

Inserts a range defined by [low, high] into the given wmem_itree_t in O(log(n)) time. The interval is indexed by its low value, and associated with the provided data pointer. If an interval with the same low value already exists, it will be overwritten.

Parameters

tree	Pointer to the interval tree.
low	Lower bound of the interval (inclusive).
high	Upper bound of the interval (inclusive).
data	Pointer to user-defined data associated with the interval.

wmem_itree_is_empty()

WS_DLL_PUBLIC bool wmem_itree_is_empty

(

wmem_itree_t *

tree

)

Check whether an interval tree is empty.

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

Parameters

tree	Pointer to the interval tree to check.

Returns

true if the tree has no nodes, false otherwise.

wmem_itree_new()

WS_DLL_PUBLIC wmem_itree_t * wmem_itree_new

(

wmem_allocator_t *

allocator

)

Create a new interval tree using the specified memory allocator.

Allocates and initializes a new wmem_itree_t structure for managing intervals. The tree is created using the provided wmem_allocator_t, which controls memory allocation and cleanup.

Parameters

allocator

Pointer to the memory allocator to use for tree allocation.

Returns

Pointer to the newly created interval tree.

wmem_print_itree()

void wmem_print_itree

(

wmem_itree_t *

tree

)

Print all intervals stored in the interval tree.

Traverses the given wmem_itree_t and prints each stored interval range. This is typically used for debugging or inspection purposes to visualize the contents of the tree.

Parameters

tree	Pointer to the interval tree to print.